[crisscross commit] r881 - in trunk/source: . crisscross

0 views

Skip to first unread message

codesite...@google.com

unread,

Nov 6, 2008, 6:17:50 PM11/6/08

to crisscr...@googlegroups.com

Author: steven.noonan
Date: Thu Nov 6 15:16:33 2008
New Revision: 881

Modified:
trunk/source/core_io_reader.cpp
trunk/source/crisscross/avltree.cpp
trunk/source/crisscross/avltree.h
trunk/source/crisscross/rbtree.cpp
trunk/source/crisscross/rbtree.h
trunk/source/crisscross/splaytree.cpp
trunk/source/crisscross/splaytree.h

Log:
git sync w/ commit: eab816cb1d93503f8a3b7fec94c18b54d49f38d5

Modified: trunk/source/core_io_reader.cpp
==============================================================================
--- trunk/source/core_io_reader.cpp (original)
+++ trunk/source/core_io_reader.cpp Thu Nov 6 15:16:33 2008
@@ -232,7 +232,7 @@
if (c == (char)EOF)
return 0;

- static std::string buffer;
+ std::string buffer;

while (c != (char)EOF && c != '\n') {
buffer += c;

Modified: trunk/source/crisscross/avltree.cpp
==============================================================================
--- trunk/source/crisscross/avltree.cpp (original)
+++ trunk/source/crisscross/avltree.cpp Thu Nov 6 15:16:33 2008
@@ -214,29 +214,6 @@
}

template <class Key, class Data>
- DArray<Data> *AVLTree<Key, Data>::findAll(Key const &_key) const
- {
- AVLNode<Key, Data> *p_current = findNode(_key);
- DArray<Data> *data = new DArray<Data>();
- findRecursive(data, _key, p_current);
- return data;
- }
-
- template <class Key, class Data>
- void AVLTree<Key, Data>::findRecursive(DArray<Data> *_array, Key const
&_key, AVLNode<Key, Data> *_node) const
- {
- CoreAssert(_array);
- if (!_node) return;
-
- findRecursive(_array, _key, _node->left);
- if (Compare(_node->id, _key) == 0) {
- _array->insert(_node->data);
- }
-
- findRecursive(_array, _key, _node->right);
- }
-
- template <class Key, class Data>
Data AVLTree<Key, Data>::find(Key const &_key) const
{
AVLNode<Key, Data> *p_current = findNode(_key);
@@ -647,12 +624,15 @@
return BALANCE;
}

- if (Compare(_key, (*_node)->id) < 0) {
+ int ret = Compare(_key, (*_node)->id);
+ if (ret < 0) {
if ((result = insert(_node, &(*_node)->left, _key, _data)) == BALANCE)
result = balanceLeftGrown(_node);
- } else { /* obj >= nodeobj */
+ } else if (ret > 0) { /* obj >= nodeobj */
if ((result = insert(_node, &(*_node)->right, _key, _data)) == BALANCE)
result = balanceRightGrown(_node);
+ } else {
+ return Result::Error;
}

return result;

Modified: trunk/source/crisscross/avltree.h
==============================================================================
--- trunk/source/crisscross/avltree.h (original)
+++ trunk/source/crisscross/avltree.h Thu Nov 6 15:16:33 2008
@@ -183,14 +183,6 @@
*/
void RecursiveConvertToDArray(DArray <Data> *_darray, AVLNode<Key,
Data> *_btree) const;

- /*! \brief Recursively find all nodes with the specified key */
- /*!
- * \param _darray Array to insert data into
- * \param _key Identifier of nodes to find
- * \param _node The node being traversed
- */
- void findRecursive(DArray<Data> *_darray, Key const &_key,
AVLNode<Key, Data> *_node) const;
-
/*! \brief Verifies that a node is valid. */
/*!
* \param _node A node pointer.
@@ -251,14 +243,6 @@
* \sa find
*/
_CC_DEPRECATE_FUNCTION(find) Data find(Key const &_key) const;
-
- /*! \brief Finds all instances of the specified key in the tree. */
- /*!
- * \param _key The key of the node to find.
- * \return A DArray containing the data with key _key.
- * \warning Delete the returned DArray when done with it to avoid
memory leaks.
- */
- DArray<Data> *findAll(Key const &_key) const;

/*! \brief Tests whether a key is in the tree or not. */
/*!

Modified: trunk/source/crisscross/rbtree.cpp
==============================================================================
--- trunk/source/crisscross/rbtree.cpp (original)
+++ trunk/source/crisscross/rbtree.cpp Thu Nov 6 15:16:33 2008
@@ -174,8 +174,13 @@
current = rootNode;
while (valid(current)) {
parent = current;
- current = (Compare(key, keyPool[current->id_ind]) <= 0) ?
- current->left : current->right;
+ int ret = Compare(key, keyPool[current->id_ind]);
+ if (ret < 0)
+ current = current->left;
+ else if (ret > 0)
+ current = current->right;
+ else
+ return false;
}

/* setup new node */
@@ -477,29 +482,6 @@
killAll(rootNode);
rootNode = nullNode;
m_cachedSize = 0;
- }
-
- template <class Key, class Data>
- DArray<Data> *RedBlackTree<Key, Data>::findAll(Key const &_key) const
- {
- RedBlackNode<Key, Data> *p_current = findNode(_key);
- DArray<Data> *data = new DArray<Data>();
- findRecursive(data, _key, p_current);
- return data;
- }
-
- template <class Key, class Data>
- void RedBlackTree<Key, Data>::findRecursive(DArray<Data> *_array, Key
const &_key, RedBlackNode<Key, Data> *_node) const
- {
- CoreAssert(_array);
- if (!valid(_node)) return;
-
- findRecursive(_array, _key, _node->left);
- if (Compare(keyPool[_node->id_ind], _key) == 0) {
- _array->insert(dataPool[_node->data_ind]);
- }
-
- findRecursive(_array, _key, _node->right);
}

template <class Key, class Data>

Modified: trunk/source/crisscross/rbtree.h
==============================================================================
--- trunk/source/crisscross/rbtree.h (original)
+++ trunk/source/crisscross/rbtree.h Thu Nov 6 15:16:33 2008
@@ -65,8 +65,6 @@
void insertFixup(RedBlackNode<Key, Data> * _x);
void deleteFixup(RedBlackNode<Key, Data> * _x);

- void findRecursive(DArray<Data> *_array, Key const &_key,
RedBlackNode<Key, Data> *_node) const;
-
void killAll();
void killAll(RedBlackNode<Key, Data> *rec);

@@ -168,14 +166,6 @@
{
return m_cachedSize;
};
-
- /*! \brief Finds all instances of the specified key in the tree. */
- /*!
- * \param _key The key of the node to find.
- * \return A DArray containing the data with key _key.
- * \warning Delete the returned DArray when done with it.
- */
- DArray<Data> *findAll(Key const &_key) const;

/*! \brief Tests whether a key is in the tree or not. */
/*!

Modified: trunk/source/crisscross/splaytree.cpp
==============================================================================
--- trunk/source/crisscross/splaytree.cpp (original)
+++ trunk/source/crisscross/splaytree.cpp Thu Nov 6 15:16:33 2008
@@ -203,29 +203,6 @@
}

template <class Key, class Data>
- DArray<Data> *SplayTree<Key, Data>::findAll(Key const &_key) const
- {
- SplayNode<Key, Data> *p_current = findNode(_key);
- DArray<Data> *data = new DArray<Data>();
- findRecursive(data, _key, p_current);
- return data;
- }
-
- template <class Key, class Data>
- void SplayTree<Key, Data>::findRecursive(DArray<Data> *_array, Key const
&_key, SplayNode<Key, Data> *_node) const
- {
- CoreAssert(_array);
- if (!_node) return;
-
- findRecursive(_array, _key, _node->left);
- if (Compare(_node->id, _key) == 0) {
- _array->insert(_node->data);
- }
-
- findRecursive(_array, _key, _node->right);
- }
-
- template <class Key, class Data>
bool SplayTree<Key, Data>::replace(Key const &key, Data const &data)
{
splay(key, root);

Modified: trunk/source/crisscross/splaytree.h
==============================================================================
--- trunk/source/crisscross/splaytree.h (original)
+++ trunk/source/crisscross/splaytree.h Thu Nov 6 15:16:33 2008
@@ -62,8 +62,6 @@
void RecursiveConvertIndexToDArray(DArray <Key> *_darray,
SplayNode<Key, Data> *_btree) const;
void RecursiveConvertToDArray(DArray <Data> *_darray, SplayNode<Key,
Data> *_btree) const;

- void findRecursive(DArray<Data> *_array, Key const &_key,
SplayNode<Key, Data> *_node) const;
-
bool erase(Key const &key, Data const &rec, SplayNode<Key, Data>
*curnode);

bool killNode(SplayNode<Key, Data> * z);
@@ -125,14 +123,6 @@
* \sa find
*/
_CC_DEPRECATE_FUNCTION(find) Data find(Key const &_key) const;
-
- /*! \brief Finds all instances of the specified key in the tree. */
- /*!
- * \param _key The key of the node to find.
- * \return A DArray containing the data with key _key.
- * \warning Delete the returned DArray when done with it.
- */
- DArray<Data> *findAll(Key const &_key) const;