AVLTreeMap::MakeEmpty should set fTree.fRoot to NULL

Fix #8643: AVLTreeMap strategy Auto discards const

Signed-off-by: Ingo Weinhold <ingo_weinhold@gmx.de>

AVLTreeMap fixes

* AVLTreeMap::_GetKey(): Change return type from const Key& to Key, so
the strategy can do that as well and doesn't have have a Key object in
the node.
* Fix the Auto strategy: It was using the undefined _GetKey() instead
of GetKey().

AVLTreeMap/TwoKeyAVLTree: More access to nodes

both:
* Add Previous()/Next().
* Add Insert() version that returns a Node* instead of an Iterator.
* Add Remove() version that takes a Node* instead of a key.

TwoKeyAVLTree:
* Add GetIterator() version that takes an additional Node*, i.e.
initializing an iterator to point to the node.
* Add Iterator::CurrentNode().

AVLTreeMap fixes

* AVLTreeMap::_GetKey(): Change return type from const Key& to Key, so
the strategy can do that as well and doesn't have have a Key object in
the node.
* Fix the Auto strategy: It was using the undefined _GetKey() instead
of GetKey().

AVLTreeMap/TwoKeyAVLTree: More access to nodes

both:
* Add Previous()/Next().
* Add Insert() version that returns a Node* instead of an Iterator.
* Add Remove() version that takes a Node* instead of a key.

TwoKeyAVLTree:
* Add GetIterator() version that takes an additional Node*, i.e.
initializing an iterator to point to the node.
* Add Iterator::CurrentNode().

* AVLTree:
- Renamed to AVLTreeBase and moved it into its own header/source file.
- Renamed FindClose() to FindClosest().
- Added CheckTree() method for debugging purposes. It checks the validity
of the tree.
* Added a templatized class AVLTree which doesn't offer a map-like interface
like AVLTreeMap, but rather one similar to BOpenHashMap and SplayTree. It
is more convenient to use, if one wants to store objects that already
contain the key.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34526 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added Iterator::NextValuePointer().
* Made reference returned by _GetKey() const. That's sufficient.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@33898 a95241bf-73f2-0310-859d-f6bbb57e9c96

fixed gcc4 build


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21896 a95241bf-73f2-0310-859d-f6bbb57e9c96

Revised the AVLTreeMap code:
* Pulled the actual tree code into a non-templatized class AVLTree to
reduce the amount of code generated each time the template is
instantiated.
* Changed the iterator interface to Java-style.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21892 a95241bf-73f2-0310-859d-f6bbb57e9c96

Replaced <new> with <util/kernel_cpp.h> - this is the kernel.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7913 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed invalid default argument. Not that the compiler eats the file now...


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@3743 a95241bf-73f2-0310-859d-f6bbb57e9c96

The beginning of an AVL tree based map implementation. Well, the tree part
is complete, the interface needs work.
Unfortunately our ancient compiler chokes on this (`Internal Compiler
Error'). I got around the problem by restructuring parts of the code once,
but now I'm stuck -- no idea what I could change. So, there won't be
AVLTree{Map,Set} until we have a working compiler. :-(


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@3712 a95241bf-73f2-0310-859d-f6bbb57e9c96

AVLTreeMap::MakeEmpty should set fTree.fRoot to NULL

Fix #8643: AVLTreeMap strategy Auto discards const

Signed-off-by: Ingo Weinhold <ingo_weinhold@gmx.de>

AVLTreeMap fixes

* AVLTreeMap::_GetKey(): Change return type from const Key& to Key, so
the strategy can do that as well and doesn't have have a Key object in
the node.
* Fix the Auto strategy: It was using the undefined _GetKey() instead
of GetKey().

AVLTreeMap/TwoKeyAVLTree: More access to nodes

both:
* Add Previous()/Next().
* Add Insert() version that returns a Node* instead of an Iterator.
* Add Remove() version that takes a Node* instead of a key.

TwoKeyAVLTree:
* Add GetIterator() version that takes an additional Node*, i.e.
initializing an iterator to point to the node.
* Add Iterator::CurrentNode().

AVLTreeMap fixes

* AVLTreeMap::_GetKey(): Change return type from const Key& to Key, so
the strategy can do that as well and doesn't have have a Key object in
the node.
* Fix the Auto strategy: It was using the undefined _GetKey() instead
of GetKey().

AVLTreeMap/TwoKeyAVLTree: More access to nodes

both:
* Add Previous()/Next().
* Add Insert() version that returns a Node* instead of an Iterator.
* Add Remove() version that takes a Node* instead of a key.

TwoKeyAVLTree:
* Add GetIterator() version that takes an additional Node*, i.e.
initializing an iterator to point to the node.
* Add Iterator::CurrentNode().

* AVLTree:
- Renamed to AVLTreeBase and moved it into its own header/source file.
- Renamed FindClose() to FindClosest().
- Added CheckTree() method for debugging purposes. It checks the validity
of the tree.
* Added a templatized class AVLTree which doesn't offer a map-like interface
like AVLTreeMap, but rather one similar to BOpenHashMap and SplayTree. It
is more convenient to use, if one wants to store objects that already
contain the key.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34526 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Added Iterator::NextValuePointer().
* Made reference returned by _GetKey() const. That's sufficient.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@33898 a95241bf-73f2-0310-859d-f6bbb57e9c96

fixed gcc4 build


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21896 a95241bf-73f2-0310-859d-f6bbb57e9c96

Revised the AVLTreeMap code:
* Pulled the actual tree code into a non-templatized class AVLTree to
reduce the amount of code generated each time the template is
instantiated.
* Changed the iterator interface to Java-style.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21892 a95241bf-73f2-0310-859d-f6bbb57e9c96

Replaced <new> with <util/kernel_cpp.h> - this is the kernel.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7913 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed invalid default argument. Not that the compiler eats the file now...


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@3743 a95241bf-73f2-0310-859d-f6bbb57e9c96

The beginning of an AVL tree based map implementation. Well, the tree part
is complete, the interface needs work.
Unfortunately our ancient compiler chokes on this (`Internal Compiler
Error'). I got around the problem by restructuring parts of the code once,
but now I'm stuck -- no idea what I could change. So, there won't be
AVLTree{Map,Set} until we have a working compiler. :-(


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@3712 a95241bf-73f2-0310-859d-f6bbb57e9c96