From: igaztanaga_at_[hidden]
Date: 2007-10-24 15:00:32
Author: igaztanaga
Date: 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
New Revision: 40429
URL: http://svn.boost.org/trac/boost/changeset/40429
Log:
Fixed Solaris-gcc errors and added splay trees
Added:
trunk/libs/intrusive/example/doc_splay_algorithms.cpp (contents, props changed)
trunk/libs/intrusive/example/doc_splay_set.cpp (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/splay_multiset/
trunk/libs/intrusive/proj/vc7ide/splay_multiset/splay_multiset.vcproj (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/splay_set/
trunk/libs/intrusive/proj/vc7ide/splay_set/splay_set.vcproj (contents, props changed)
trunk/libs/intrusive/test/splay_multiset_test.cpp (contents, props changed)
trunk/libs/intrusive/test/splay_set_test.cpp (contents, props changed)
Binary files modified:
trunk/libs/intrusive/doc/html/images/blank.png
trunk/libs/intrusive/doc/html/images/caution.png
trunk/libs/intrusive/doc/html/images/draft.png
trunk/libs/intrusive/doc/html/images/home.png
trunk/libs/intrusive/doc/html/images/important.png
trunk/libs/intrusive/doc/html/images/next.png
trunk/libs/intrusive/doc/html/images/note.png
trunk/libs/intrusive/doc/html/images/prev.png
trunk/libs/intrusive/doc/html/images/tip.png
trunk/libs/intrusive/doc/html/images/toc-blank.png
trunk/libs/intrusive/doc/html/images/toc-minus.png
trunk/libs/intrusive/doc/html/images/toc-plus.png
trunk/libs/intrusive/doc/html/images/warning.png
Text files modified:
trunk/libs/intrusive/doc/Jamfile.v2 | 25 +-
trunk/libs/intrusive/doc/intrusive.qbk | 271 ++++++++++++++++++++++++++++++++++++---
trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp | 4
trunk/libs/intrusive/example/doc_set.cpp | 16 +
trunk/libs/intrusive/proj/vc7ide/Intrusive.sln | 16 ++
trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj | 33 ++++
trunk/libs/intrusive/proj/vc7ide/to-do.txt | 1
trunk/libs/intrusive/test/itestvalue.hpp | 81 ++++++++---
trunk/libs/intrusive/test/test_container.hpp | 37 +++++
trunk/libs/intrusive/test/unordered_multiset_test.cpp | 6
trunk/libs/intrusive/test/unordered_set_test.cpp | 6
11 files changed, 422 insertions(+), 74 deletions(-)
Modified: trunk/libs/intrusive/doc/Jamfile.v2
==============================================================================
--- trunk/libs/intrusive/doc/Jamfile.v2 (original)
+++ trunk/libs/intrusive/doc/Jamfile.v2 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -21,19 +21,18 @@
<doxygen:param>EXTRACT_PRIVATE=NO
<doxygen:param>ENABLE_PREPROCESSING=YES
<doxygen:param>MACRO_EXPANSION=YES
-# <doxygen:param>EXPAND_ONLY_PREDEF=YES
-# <doxygen:param>SEARCH_INCLUDES=YES
-# <doxygen:param>INCLUDE_PATH=$(BOOST_ROOT)
- <doxygen:param>"PREDEFINED=\"BOOST_INTRUSIVE_DOXYGEN_INVOKED\" \\
- \"list_impl=list\" \\
- \"slist_impl=slist\" \\
- \"set_impl=set\" \\
- \"multiset_impl=multiset\" \\
- \"rbtree_impl=rbtree\" \\
- \"unordered_set_impl=unordered_set\" \\
- \"unordered_multiset_impl=unordered_multiset\" \\
- \"hashtable_impl=hashtable\" \\
- "
+ <doxygen:param>"PREDEFINED=BOOST_INTRUSIVE_DOXYGEN_INVOKED \\
+ "list_impl=list" \\
+ "slist_impl=slist" \\
+ "set_impl=set" \\
+ "multiset_impl=multiset" \\
+ "rbtree_impl=rbtree" \\
+ "unordered_set_impl=unordered_set" \\
+ "unordered_multiset_impl=unordered_multiset" \\
+ "hashtable_impl=hashtable" \\
+ "splay_set_impl=splay_set" \\
+ "splay_multiset_impl=splay_multiset" \\
+ "splaytree_impl=splaytree""
;
xml intrusive : intrusive.qbk ;
Modified: trunk/libs/intrusive/doc/html/images/blank.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/caution.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/draft.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/home.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/important.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/next.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/note.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/prev.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/tip.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/toc-blank.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/toc-minus.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/toc-plus.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/html/images/warning.png
==============================================================================
Binary files. No diff available.
Modified: trunk/libs/intrusive/doc/intrusive.qbk
==============================================================================
--- trunk/libs/intrusive/doc/intrusive.qbk (original)
+++ trunk/libs/intrusive/doc/intrusive.qbk 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -788,7 +788,7 @@
the section [link intrusive.usage How to use Boost.Intrusive]:
* [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one list hook.
+ so you can derive from more than one slist hook.
Default: `tag<default_tag>`.
* [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
@@ -920,29 +920,38 @@
[endsect]
-[section:set_multiset Intrusive associative containers: set, multiset]
+[section:set_multiset Intrusive associative containers: set, multiset, rbtree]
[*Boost.Intrusive] also offers associative containers that can be very useful
when creating more complex associative containers, like containers maintaining
-one or more indices with different sorting semantics.
-The memory overhead of these containers is usually 3 pointers and an integer. If
-pointers have 2 byte alignment (which is usually true in most systems),
-[*Boost.Intrusive] optimizes this overhead to 3 pointers.
-
-An empty, non constant-time size [classref boost::intrusive::set set] or
-[classref boost::intrusive::multiset multiset]
-has also the size of 3 pointers and an integer (3 pointers when optimized).
-[classref boost::intrusive::set set] and
-[classref boost::intrusive::multiset multiset] have logarithmic complexity in many
+one or more indices with different sorting semantics. Boost.Intrusive associative
+containers, like most STL associative container implemenatations are based on
+red-black trees.
+
+The memory overhead of these containers is usually 3 pointers and an integer.
+This size can be reduced to 3 pointers if pointers have even alignment
+(which is usually true in most systems).
+
+An empty, non constant-time size [classref boost::intrusive::set set],
+[classref boost::intrusive::multiset multiset] or
+[classref boost::intrusive::rbtree rbtree]
+has also the size of 3 pointers and an integer (3 pointers when optimized for size).
+These containers have logarithmic complexity in many
operations like
searches, insertions, erasures, etc... [classref boost::intrusive::set set] and
[classref boost::intrusive::multiset multiset] are the
intrusive equivalents of standard `std::set` and `std::multiset` containers.
-[section:set_multiset_hooks set and multiset hooks]
-
+[classref boost::intrusive::rbtree rbtree] is a superset of
[classref boost::intrusive::set set] and
-[classref boost::intrusive::multiset multiset] share the same hooks.
+[classref boost::intrusive::multiset multiset] containers that offers
+functions to insert unique and multiple keys.
+
+[section:set_multiset_hooks set, multiset and rbtree hooks]
+
+[classref boost::intrusive::set set],
+[classref boost::intrusive::multiset multiset] and
+[classref boost::intrusive::rbtree rbtree] share the same hooks.
This is an advantage, because the same
user type can be inserted first in a [classref boost::intrusive::multiset multiset]
and after that in [classref boost::intrusive::set set] without
@@ -971,10 +980,10 @@
[classref boost::intrusive::set_base_hook set_base_hook] and
[classref boost::intrusive::set_member_hook set_member_hook] receive
the same options explained in the section
-[link intrusive.usage How to use Boost.Intrusive]:
+[link intrusive.usage How to use Boost.Intrusive] plus a size optimization option:
* [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one list hook.
+ so you can derive from more than one base hook.
Default: `tag<default_tag>`.
* [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
@@ -984,9 +993,16 @@
internally in the hook and propagated to the container.
Default: `void_pointer<void*>`.
+* [*`optimize_size<bool Enable>`]: The hook will be optimized for size
+ instead of speed. The hook will embed the color bit of the red-black
+ tree node in the parent pointer if pointer alignment is even.
+ Optimizing the size will reduce speed performance a bit since masking
+ operations will be needed to access parent pointer and color attributes.
+ Default: `optimize_size<false>`.
+
[endsect]
-[section:set_multiset_containers set and multiset containers]
+[section:set_multiset_containers set, multiset and rbtree containers]
[c++]
@@ -996,8 +1012,11 @@
template <class T, class ...Options>
class multiset;
-[classref boost::intrusive::set set] and [classref boost::intrusive::multiset multiset]
-receive the same options explained in the section [link intrusive.usage How to use Boost.Intrusive]:
+ template <class T, class ...Options>
+ class rbtree;
+
+These containers receive the same options explained in the section
+[link intrusive.usage How to use Boost.Intrusive]:
* [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
[*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
@@ -1110,7 +1129,7 @@
[link intrusive.usage How to use Boost.Intrusive]:
* [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one list hook.
+ so you can derive from more than one base hook.
Default: `tag<default_tag>`.
* [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
@@ -1240,6 +1259,142 @@
[endsect]
+[section:splay_set_multiset Intrusive splay tree-based associative containers: splay_set, splay_multiset]
+
+C++ associative containers are usually based on red-black tree implementations (e.g.: STL,
+Boost.Intrusive associative containers). However, there are other interesting data structures
+that offer some advantages (and also disadvantages).
+
+Splay trees are self-adjusting binary search trees used tipically in caches, memory
+allocators and other applications, because splay trees have a "caching effect": recently
+accessed elements have better access times that elements accessed less frequently.
+For more information on splay trees see [@http://en.wikipedia.org/wiki/Splay_tree Wikipedia].
+
+[*Boost.Intrusive] offers 3 containers based on splay trees:
+[classref boost::intrusive::splay_set splay_set],
+[classref boost::intrusive::splay_multiset splay_multiset] and
+[classref boost::intrusive::splaytree splaytree]. The first two are similar to
+[classref boost::intrusive::set set] or
+[classref boost::intrusive::multiset multiset] and the latter is a generalization
+that offers functions both to insert unique and multiple keys.
+
+The memory overhead of these containers with Boost.Intrusive hooks is usually 3 pointers.
+An empty, non constant-time size splay container has also the size of 3 pointers.
+
+[section:splay_set_multiset_disadvantages Advantages and disadvantages of splay tree based containers]
+
+Splay tree based intrusive containers have logarithmic complexity in many
+operations like searches, insertions, erasures, etc... but if some elements are
+more frequently accessed than others, splay trees perform faster searches than equivalent
+balanced binary trees (such as red-black trees).
+
+The caching effect offered by splay trees comes with a cost: the tree must be
+rebalanced when a element is searched. This disallows const versions of search
+functions like `find()`, `lower_bound()`, `upper_bound()`, `equal_range()`,
+`count()`...
+
+Because of this, splay-tree based associative containers are not drop-in
+replacements of [classref boost::intrusive::set set]/
+[classref boost::intrusive::splay_set splay_set].
+
+Apart from this, if element searches are randomized, the tree will be rebalanced
+without taking advantage of the cache effect, so splay trees can offer worse
+performance than other balanced trees for some search patterns.
+
+[endsect]
+
+[section:splay_set_multiset_hooks splay_set, splay_multiset and splaytree hooks]
+
+[classref boost::intrusive::set set],
+[classref boost::intrusive::multiset multiset] and
+[classref boost::intrusive::splaytree splaytree]
+share the same hooks.
+
+[c++]
+
+ template <class ...Options>
+ class splay_set_base_hook;
+
+* [classref boost::intrusive::splay_set_base_hook splay_set_base_hook]:
+ the user class derives publicly from this class to make
+ it compatible with splay tree based containers.
+
+[c++]
+
+ template <class ...Options>
+ class splay_set_member_hook;
+
+* [classref boost::intrusive::set_member_hook set_member_hook]:
+ the user class contains a public member of this class to make
+ it compatible with splay tree based containers.
+
+[classref boost::intrusive::splay_set_base_hook splay_set_base_hook] and
+[classref boost::intrusive::splay_set_member_hook splay_set_member_hook] receive
+the same options explained in the section
+[link intrusive.usage How to use Boost.Intrusive]:
+
+* [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
+ so you can derive from more than one base hook.
+ Default: `tag<default_tag>`.
+
+* [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
+ Default: `link_mode<safe_link>`.
+
+* [*`void_pointer<class VoidPointer>`]: The pointer type to be used
+ internally in the hook and propagated to the container.
+ Default: `void_pointer<void*>`.
+
+[endsect]
+
+[section:set_multiset_containers splay_set, splay_multiset and splaytree containers]
+
+[c++]
+
+ template <class T, class ...Options>
+ class splay_set;
+
+ template <class T, class ...Options>
+ class splay_multiset;
+
+ template <class T, class ...Options>
+ class splaytree;
+
+These containers receive the same options explained in the section
+[link intrusive.usage How to use Boost.Intrusive]:
+
+* [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
+ [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
+ to configure the container (to know about value traits go to the section
+ titled [link intrusive.value_traits Containers with custom ValueTraits].
+
+* [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
+ Default: `constant_time_size<true>`
+
+* [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
+ of the container. Default: `size_type<std::size_t>`
+
+And they also can receive an additional option:
+
+* [*`compare<class Compare>`]: Comparison function for the objects to be inserted
+ in containers. The comparison functor must induce a strict weak ordering.
+ Default: `compare< std::less<T> >`
+
+[endsect]
+
+[section:splay_set_multiset_example Example]
+
+Now let's see an small example using both hooks and
+[classref boost::intrusive::splay_set splay_set]/
+[classref boost::intrusive::splay_multiset splay_multiset]
+containers:
+
+[import ../example/doc_splay_set.cpp]
+[doc_splay_set_code]
+
+[endsect]
+
+[endsect]
+
[section:advanced_lookups_insertions Advanced lookup and insertion functions for associative containers]
[section:advanced_lookups Advanced lookups]
@@ -1520,7 +1675,7 @@
have their `s_local_iterator_to` static alternatives.
Alternative static functions are available under certain circunstances
-explained in the [link: stateful_value_traits Stateful value traits] section,
+explained in the [link intrusive.value_traits.stateful_value_traits Stateful value traits] section,
but the programmer uses hooks provided by [*Boost.Intrusive], those functions
will be available.
@@ -1906,6 +2061,66 @@
[endsect]
+[section:splaytree_algorithms Intrusive splay tree algorithms]
+
+These algorithms are static
+members of the [classref boost::intrusive::rbtree_algorithms splaytree_algorithms] class:
+
+[c++]
+
+ template<class NodeTraits>
+ struct splaytree_algorithms;
+
+
+An empty tree is formed by a node whose pointer to the parent node is null,
+the pointers to the left and right nodes to itself.
+[classref boost::intrusive::splaytree_algorithms rbtree_algorithms]
+is configured with a NodeTraits class, which encapsulates
+the information about the node to be manipulated. NodeTraits must support the
+following interface:
+
+[*Typedefs]:
+
+* `node`: The type of the node that forms the circular rbtree
+
+* `node_ptr`: The type of a pointer to a node (usually node*)
+
+* `const_node_ptr`: The type of a pointer to a const node (usually const node*)
+
+[*Static functions]:
+
+* `static node_ptr get_parent(const_node_ptr n);`:
+ Returns a pointer to the parent node stored in "n".
+
+* `static void set_parent(node_ptr n, node_ptr p);`:
+ Sets the pointer to the parent node stored in "n" to "p".
+
+* `static node_ptr get_left(const_node_ptr n);`:
+ Returns a pointer to the left node stored in "n".
+
+* `static void set_left(node_ptr n, node_ptr l);`:
+ Sets the pointer to the left node stored in "n" to "l".
+
+* `static node_ptr get_right(const_node_ptr n);`:
+ Returns a pointer to the right node stored in "n".
+
+* `static void set_right(node_ptr n, node_ptr r);`:
+ Sets the pointer to the right node stored in "n" to "r".
+
+* `static color get_color(const_node_ptr n);`:
+ Returns the color stored in "n".
+
+Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
+with our nodes:
+
+[import ../example/doc_splaytree_algorithms.cpp]
+[doc_splaytree_algorithms_code]
+
+For a complete rbtree of functions see
+[classref boost::intrusive::splaytree_algorithms splaytree_algorithms reference].
+
+[endsect]
+
[endsect]
[section:value_traits Containers with custom ValueTraits]
@@ -2724,6 +2939,18 @@
[endsect]
+[section:references References]
+
+* SGI's [@http://www.sgi.com/tech/stl/ STL Programmer's Guide].
+ [*Boost.Intrusive] is based on STL concepts and interface.
+
+* Dr. Dobb's, September 1, 2005: [@http://www.ddj.com/architect/184402007 ['Implementing Splay Trees in C++] ].
+ [*Boost.Intrusive] splay containers code is based on this article.
+
+* Olaf's original intrusive container library: [@http://freenet-homepage.de/turtle++/intrusive.html ['STL-like intrusive containers] ].
+
+[endsect]
+
[section:acknowledgments Acknowledgements]
[*Olaf Krzikalla] would like to thank:
Modified: trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp (original)
+++ trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -73,10 +73,10 @@
assert(n == &three);
//Erase a node just using a pointer to it
- algo::unlink_and_rebalance(n);
+ algo::unlink(&two);
//Erase a node using also the header (faster)
- algo::erase(&header, n);
+ algo::erase(&header, &three);
return 0;
}
Modified: trunk/libs/intrusive/example/doc_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_set.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -13,11 +13,12 @@
#include <boost/intrusive/set.hpp>
#include <vector>
#include <algorithm>
+#include <cassert>
using namespace boost::intrusive;
- //This is a base hook
-class MyClass : public set_base_hook<>
+ //This is a base hook optimized for size
+class MyClass : public set_base_hook<optimize_size<true> >
{
int int_;
@@ -41,7 +42,7 @@
//Define an multiset using the member hook
typedef member_hook<MyClass, set_member_hook<>, &MyClass::member_hook_> MemberOption;
-typedef multiset< MyClass, MemberOption> MemberIMultiset;
+typedef multiset< MyClass, MemberOption> MemberMultiset;
int main()
{
@@ -53,7 +54,12 @@
for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
BaseSet baseset;
- MemberIMultiset membermultiset;
+ MemberMultiset membermultiset;
+
+ //Check that size optimization is activated in the base hook
+ assert(sizeof(set_base_hook<optimize_size<true> >) == 3*sizeof(void*));
+ //Check that size optimization is deactivated in the member hook
+ assert(sizeof(set_member_hook<>) > 3*sizeof(void*));
//Now insert them in the reverse order in the base hook set
for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
@@ -66,7 +72,7 @@
//Now test sets
{
BaseSet::reverse_iterator rbit(baseset.rbegin()), rbitend(baseset.rend());
- MemberIMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end());
+ MemberMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end());
VectIt it(values.begin()), itend(values.end());
//Test the objects inserted in the base hook set
Added: trunk/libs/intrusive/example/doc_splay_algorithms.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_splay_algorithms.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -0,0 +1,79 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2006-2007
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+//[doc_splaytree_algorithms_code
+#include <boost/intrusive/splaytree_algorithms.hpp>
+#include <cassert>
+
+struct my_node
+{
+ my_node(int i = 0)
+ : int_(i)
+ {}
+ my_node *parent_, *left_, *right_;
+ int color_;
+ //other members
+ int int_;
+};
+
+//Define our own splaytree_node_traits
+struct my_splaytree_node_traits
+{
+ typedef my_node node;
+ typedef my_node * node_ptr;
+ typedef const my_node * const_node_ptr;
+
+ static node_ptr get_parent(const_node_ptr n) { return n->parent_; }
+ static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; }
+ static node_ptr get_left(const_node_ptr n) { return n->left_; }
+ static void set_left(node_ptr n, node_ptr left) { n->left_ = left; }
+ static node_ptr get_right(const_node_ptr n) { return n->right_; }
+ static void set_right(node_ptr n, node_ptr right) { n->right_ = right; }
+};
+
+struct node_ptr_compare
+{
+ bool operator()(my_node *a, my_node *b)
+ { return a->int_ < b->int_; }
+};
+
+int main()
+{
+ typedef boost::intrusive::splaytree_algorithms<my_splaytree_node_traits> algo;
+ my_node header, two(2), three(3);
+
+ //Create an empty splaytree container:
+ //"header" will be the header node of the tree
+ algo::init_header(&header);
+
+ //Now insert node "two" in the tree using the sorting functor
+ algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());
+
+ //Now insert node "three" in the tree using the sorting functor
+ algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());
+
+ //Now take the first node (the left node of the header)
+ my_node *n = header.left_;
+ assert(n == &two);
+
+ //Now go to the next node
+ n = algo::next_node(n);
+ assert(n == &three);
+
+ //Erase a node just using a pointer to it
+ algo::unlink(&two);
+
+ //Erase a node using also the header (faster)
+ algo::erase(&header, &three);
+ return 0;
+}
+
+//]
\ No newline at end of file
Added: trunk/libs/intrusive/example/doc_splay_set.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_splay_set.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -0,0 +1,82 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2006-2007
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+//[doc_splay_set_code
+#include <boost/intrusive/splay_set.hpp>
+#include <vector>
+#include <algorithm>
+
+using namespace boost::intrusive;
+
+ //This is a base hook
+class MyClass : public splay_set_base_hook<>
+{
+ int int_;
+
+ public:
+ //This is a member hook
+ splay_set_member_hook<> member_hook_;
+
+ MyClass(int i)
+ : int_(i)
+ {}
+ friend bool operator< (const MyClass &a, const MyClass &b)
+ { return a.int_ < b.int_; }
+ friend bool operator> (const MyClass &a, const MyClass &b)
+ { return a.int_ > b.int_; }
+ friend bool operator== (const MyClass &a, const MyClass &b)
+ { return a.int_ < b.int_; }
+};
+
+//Define an set using the base hook that will store values in reverse order
+typedef splay_set< MyClass, compare<std::greater<MyClass> > > BaseSplaySet;
+
+//Define an multiset using the member hook
+typedef member_hook<MyClass, splay_set_member_hook<>, &MyClass::member_hook_> MemberOption;
+typedef splay_multiset< MyClass, MemberOption> MemberSplayMultiset;
+
+int main()
+{
+ typedef std::vector<MyClass>::iterator VectIt;
+ typedef std::vector<MyClass>::reverse_iterator VectRit;
+
+ //Create several MyClass objects, each one with a different value
+ std::vector<MyClass> values;
+ for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
+
+ BaseSplaySet baseset;
+ MemberSplayMultiset membermultiset;
+
+ //Now insert them in the reverse order in the base hook set
+ for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
+ baseset.insert(*it);
+
+ //Now insert them in the same order as in vector in the member hook set
+ for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
+ membermultiset.insert(*it);
+
+ //Now test sets
+ {
+ BaseSplaySet::reverse_iterator rbit(baseset.rbegin()), rbitend(baseset.rend());
+ MemberSplayMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end());
+ VectIt it(values.begin()), itend(values.end());
+
+ //Test the objects inserted in the base hook set
+ for(; it != itend; ++it, ++rbit)
+ if(&*rbit != &*it) return 1;
+
+ //Test the objects inserted in the member hook set
+ for(it = values.begin(); it != itend; ++it, ++mit)
+ if(&*mit != &*it) return 1;
+ }
+ return 0;
+}
+//]
Modified: trunk/libs/intrusive/proj/vc7ide/Intrusive.sln
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/Intrusive.sln (original)
+++ trunk/libs/intrusive/proj/vc7ide/Intrusive.sln 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -55,6 +55,14 @@
ProjectSection(ProjectDependencies) = postProject
EndProjectSection
EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "splay_multiset", "splay_multiset\splay_multiset.vcproj", "{01E70176-B6C5-BF47-2C91-A949077BA323}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "splay_set", "splay_set\splay_set.vcproj", "{1E6909E7-C971-F24A-6C7B-A92094B71B59}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
Global
GlobalSection(SolutionConfiguration) = preSolution
Debug = Debug
@@ -119,6 +127,14 @@
{97B69A72-B9D3-7389-17FB-74612F4A9543}.Debug.Build.0 = Debug|Win32
{97B69A72-B9D3-7389-17FB-74612F4A9543}.Release.ActiveCfg = Release|Win32
{97B69A72-B9D3-7389-17FB-74612F4A9543}.Release.Build.0 = Release|Win32
+ {01E70176-B6C5-BF47-2C91-A949077BA323}.Debug.ActiveCfg = Debug|Win32
+ {01E70176-B6C5-BF47-2C91-A949077BA323}.Debug.Build.0 = Debug|Win32
+ {01E70176-B6C5-BF47-2C91-A949077BA323}.Release.ActiveCfg = Release|Win32
+ {01E70176-B6C5-BF47-2C91-A949077BA323}.Release.Build.0 = Release|Win32
+ {1E6909E7-C971-F24A-6C7B-A92094B71B59}.Debug.ActiveCfg = Debug|Win32
+ {1E6909E7-C971-F24A-6C7B-A92094B71B59}.Debug.Build.0 = Debug|Win32
+ {1E6909E7-C971-F24A-6C7B-A92094B71B59}.Release.ActiveCfg = Release|Win32
+ {1E6909E7-C971-F24A-6C7B-A92094B71B59}.Release.Build.0 = Release|Win32
EndGlobalSection
GlobalSection(ExtensibilityGlobals) = postSolution
EndGlobalSection
Modified: trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -136,6 +136,9 @@
RelativePath="..\..\..\..\..\boost\intrusive\options.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\pointer_plus_bit.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\rbtree.hpp">
</File>
<File
@@ -154,6 +157,18 @@
RelativePath="..\..\..\..\..\boost\intrusive\slist_hook.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\splay_set.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\splay_set_hook.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\splaytree.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\splaytree_algorithms.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\trivial_value_traits.hpp">
</File>
<File
@@ -196,9 +211,6 @@
RelativePath="..\..\..\..\..\boost\intrusive\detail\parent_from_member.hpp">
</File>
<File
- RelativePath="..\..\..\..\..\boost\intrusive\pointer_plus_bit.hpp">
- </File>
- <File
RelativePath="..\..\..\..\..\boost\intrusive\detail\pointer_to_other.hpp">
</File>
<File
@@ -208,9 +220,18 @@
RelativePath="..\..\..\..\..\boost\intrusive\detail\slist_node.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\detail\splaytree_node.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\detail\transform_iterator.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\detail\tree_algorithms.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\detail\tree_node.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\detail\utilities.hpp">
</File>
</Filter>
@@ -308,6 +329,12 @@
RelativePath="..\..\..\example\doc_slist_algorithms.cpp">
</File>
<File
+ RelativePath="..\..\..\example\doc_splay_algorithms.cpp">
+ </File>
+ <File
+ RelativePath="..\..\..\example\doc_splay_set.cpp">
+ </File>
+ <File
RelativePath="..\..\..\example\doc_stateful_value_traits.cpp">
</File>
<File
Added: trunk/libs/intrusive/proj/vc7ide/splay_multiset/splay_multiset.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/splay_multiset/splay_multiset.vcproj 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -0,0 +1,127 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="splay_multiset"
+ ProjectGUID="{01E70176-B6C5-BF47-2C91-A949077BA323}"
+ Keyword="Win32Proj">
+ <Platforms>
+ <Platform
+ Name="Win32"/>
+ </Platforms>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="Debug"
+ IntermediateDirectory="Debug"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ GeneratePreprocessedFile="0"
+ MinimalRebuild="TRUE"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="5"
+ DisableLanguageExtensions="TRUE"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/splay_multiset.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/splay_multiset.pdb"
+ SubSystem="1"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="Release"
+ IntermediateDirectory="Release"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="4"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="3"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/splay_multiset.exe"
+ LinkIncremental="1"
+ GenerateDebugInformation="TRUE"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Source Files"
+ Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{C737F9AC-78CA-745E-5426-2DA33852B2FA}">
+ <File
+ RelativePath="..\..\..\test\splay_multiset_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Added: trunk/libs/intrusive/proj/vc7ide/splay_set/splay_set.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/splay_set/splay_set.vcproj 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -0,0 +1,126 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="splay_set"
+ ProjectGUID="{1E6909E7-C971-F24A-6C7B-A92094B71B59}"
+ Keyword="Win32Proj">
+ <Platforms>
+ <Platform
+ Name="Win32"/>
+ </Platforms>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="Debug"
+ IntermediateDirectory="Debug"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="TRUE"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="5"
+ DisableLanguageExtensions="TRUE"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/splay_set.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/splay_set.pdb"
+ SubSystem="1"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="Release"
+ IntermediateDirectory="Release"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="4"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="3"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/splay_set.exe"
+ LinkIncremental="1"
+ GenerateDebugInformation="TRUE"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Source Files"
+ Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{FF1C7761-72AF-26A3-71E5-2743AA32D2CA}">
+ <File
+ RelativePath="..\..\..\test\splay_set_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Modified: trunk/libs/intrusive/proj/vc7ide/to-do.txt
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/to-do.txt (original)
+++ trunk/libs/intrusive/proj/vc7ide/to-do.txt 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -12,3 +12,4 @@
Add resize() to list
Optimize rehash for when shrinking: there is no need to hash the values.
Add BOOST_STATIC_ASSERT to s_iterator_to functions and fix documentation on this issue.
+rbtree::count() is recursive.
Modified: trunk/libs/intrusive/test/itestvalue.hpp
==============================================================================
--- trunk/libs/intrusive/test/itestvalue.hpp (original)
+++ trunk/libs/intrusive/test/itestvalue.hpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -18,6 +18,7 @@
#include <boost/intrusive/list_hook.hpp>
#include <boost/intrusive/slist_hook.hpp>
#include <boost/intrusive/unordered_set_hook.hpp>
+#include <boost/intrusive/splay_set_hook.hpp>
#include <boost/intrusive/options.hpp>
#include <boost/functional/hash.hpp>
#include "smart_ptr.hpp"
@@ -33,17 +34,33 @@
template<class VoidPointer>
struct set_auto_base_hook_type
-{ typedef set_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag> > type; };
+{ typedef set_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag>, optimize_size<true> > type; };
template<class VoidPointer>
struct set_member_hook_type
-{ typedef set_member_hook<void_pointer<VoidPointer> > type; };
+{ typedef set_member_hook<void_pointer<VoidPointer>, optimize_size<true> > type; };
template<class VoidPointer>
struct set_auto_member_hook_type
{ typedef set_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
template<class VoidPointer>
+struct splay_set_base_hook_type
+{ typedef splay_set_base_hook<void_pointer<VoidPointer> > type; };
+
+template<class VoidPointer>
+struct splay_set_auto_base_hook_type
+{ typedef splay_set_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag> > type; };
+
+template<class VoidPointer>
+struct splay_set_member_hook_type
+{ typedef splay_set_member_hook<void_pointer<VoidPointer> > type; };
+
+template<class VoidPointer>
+struct splay_set_auto_member_hook_type
+{ typedef splay_set_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
+
+template<class VoidPointer>
struct list_base_hook_type
{ typedef list_base_hook<void_pointer<VoidPointer> > type; };
@@ -95,6 +112,8 @@
struct testvalue
: set_base_hook_type<VoidPointer>::type
, set_auto_base_hook_type<VoidPointer>::type
+ , splay_set_base_hook_type<VoidPointer>::type
+ , splay_set_auto_base_hook_type<VoidPointer>::type
, list_base_hook_type<VoidPointer>::type
, list_auto_base_hook_type<VoidPointer>::type
, slist_base_hook_type<VoidPointer>::type
@@ -102,30 +121,39 @@
, uset_base_hook_type<VoidPointer>::type
, uset_auto_base_hook_type<VoidPointer>::type
{
- typedef typename set_auto_base_hook_type<VoidPointer>::type set_auto_base_hook_t;
- typedef typename set_base_hook_type<VoidPointer>::type set_base_hook_t;
- typedef typename set_auto_member_hook_type<VoidPointer>::type set_auto_member_hook_t;
- typedef typename set_member_hook_type<VoidPointer>::type set_member_hook_t;
-
- typedef typename uset_auto_base_hook_type<VoidPointer>::type unordered_set_auto_base_hook_t;
- typedef typename uset_base_hook_type<VoidPointer>::type unordered_set_base_hook_t;
- typedef typename uset_auto_member_hook_type<VoidPointer>::type unordered_set_auto_member_hook_t;
- typedef typename uset_member_hook_type<VoidPointer>::type unordered_set_member_hook_t;
-
- typedef typename list_auto_base_hook_type<VoidPointer>::type list_auto_base_hook_t;
- typedef typename list_base_hook_type<VoidPointer>::type list_base_hook_t;
- typedef typename list_auto_member_hook_type<VoidPointer>::type list_auto_member_hook_t;
- typedef typename list_member_hook_type<VoidPointer>::type list_member_hook_t;
-
- typedef typename slist_auto_base_hook_type<VoidPointer>::type slist_auto_base_hook_t;
- typedef typename slist_base_hook_type<VoidPointer>::type slist_base_hook_t;
- typedef typename slist_auto_member_hook_type<VoidPointer>::type slist_auto_member_hook_t;
- typedef typename slist_member_hook_type<VoidPointer>::type slist_member_hook_t;
+ typedef typename set_auto_base_hook_type<VoidPointer>::type set_auto_base_hook_t;
+ typedef typename set_base_hook_type<VoidPointer>::type set_base_hook_t;
+ typedef typename set_auto_member_hook_type<VoidPointer>::type set_auto_member_hook_t;
+ typedef typename set_member_hook_type<VoidPointer>::type set_member_hook_t;
+
+ typedef typename splay_set_auto_base_hook_type<VoidPointer>::type splay_set_auto_base_hook_t;
+ typedef typename splay_set_base_hook_type<VoidPointer>::type splay_set_base_hook_t;
+ typedef typename splay_set_auto_member_hook_type<VoidPointer>::type splay_set_auto_member_hook_t;
+ typedef typename splay_set_member_hook_type<VoidPointer>::type splay_set_member_hook_t;
+
+ typedef typename uset_auto_base_hook_type<VoidPointer>::type unordered_set_auto_base_hook_t;
+ typedef typename uset_base_hook_type<VoidPointer>::type unordered_set_base_hook_t;
+ typedef typename uset_auto_member_hook_type<VoidPointer>::type unordered_set_auto_member_hook_t;
+ typedef typename uset_member_hook_type<VoidPointer>::type unordered_set_member_hook_t;
+
+ typedef typename list_auto_base_hook_type<VoidPointer>::type list_auto_base_hook_t;
+ typedef typename list_base_hook_type<VoidPointer>::type list_base_hook_t;
+ typedef typename list_auto_member_hook_type<VoidPointer>::type list_auto_member_hook_t;
+ typedef typename list_member_hook_type<VoidPointer>::type list_member_hook_t;
+
+ typedef typename slist_auto_base_hook_type<VoidPointer>::type slist_auto_base_hook_t;
+ typedef typename slist_base_hook_type<VoidPointer>::type slist_base_hook_t;
+ typedef typename slist_auto_member_hook_type<VoidPointer>::type slist_auto_member_hook_t;
+ typedef typename slist_member_hook_type<VoidPointer>::type slist_member_hook_t;
//Set members
set_member_hook_t set_node_;
set_auto_member_hook_t set_auto_node_;
+ //SplaySet members
+ splay_set_member_hook_t splay_set_node_;
+ splay_set_auto_member_hook_t splay_set_auto_node_;
+
//Unordered set members
unordered_set_member_hook_t unordered_set_node_;
unordered_set_auto_member_hook_t unordered_set_auto_node_;
@@ -163,6 +191,11 @@
this->set_node_ = src.set_node_;
this->set_auto_node_ = src.set_auto_node_;
+ splay_set_base_hook_t::operator=(src);
+ splay_set_auto_base_hook_t::operator=(src);
+ this->splay_set_node_ = src.splay_set_node_;
+ this->splay_set_auto_node_ = src.splay_set_auto_node_;
+
unordered_set_base_hook_t::operator=(src);
unordered_set_auto_base_hook_t::operator=(src);
this->unordered_set_node_ = src.unordered_set_node_;
@@ -190,6 +223,12 @@
set_node_.swap_nodes(other.set_node_);
set_auto_node_.swap_nodes(other.set_auto_node_);
+ //SplaySet
+ splay_set_base_hook_t::swap_nodes(other);
+ splay_set_auto_base_hook_t::swap_nodes(other);
+ splay_set_node_.swap_nodes(other.splay_set_node_);
+ splay_set_auto_node_.swap_nodes(other.splay_set_auto_node_);
+
//Unordered set
unordered_set_base_hook_t::swap_nodes(other);
unordered_set_auto_base_hook_t::swap_nodes(other);
Added: trunk/libs/intrusive/test/splay_multiset_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/splay_multiset_test.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -0,0 +1,469 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Olaf Krzikalla 2004-2006.
+// (C) Copyright Ion Gaztanaga 2006-2007.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+
+#include <boost/intrusive/detail/config_begin.hpp>
+#include <boost/intrusive/splay_set.hpp>
+#include <boost/intrusive/detail/pointer_to_other.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "common_functors.hpp"
+#include <vector>
+#include <boost/detail/lightweight_test.hpp>
+#include "test_macros.hpp"
+#include "test_container.hpp"
+#include <set>
+
+namespace boost { namespace intrusive { namespace test {
+
+template<class T, class O1, class O2, class O3, class O4>
+struct has_const_overloads<boost::intrusive::splay_multiset<T, O1, O2, O3, O4> >
+{
+ static const bool value = false;
+};
+
+}}}
+
+using namespace boost::intrusive;
+template<class ValueTraits>
+struct test_splay_multiset
+{
+ typedef typename ValueTraits::value_type value_type;
+ static void test_all (std::vector<value_type>& values, bool splay);
+ static void test_sort(std::vector<value_type>& values, bool splay);
+ static void test_insert(std::vector<value_type>& values, bool splay);
+ static void test_swap(std::vector<value_type>& values, bool splay);
+ static void test_find(std::vector<value_type>& values, bool splay);
+ static void test_splay_up(std::vector<value_type>& values);
+ static void test_splay_down(std::vector<value_type>& values);
+ static void test_impl(bool splay);
+ static void test_clone(std::vector<value_type>& values, bool splay);
+ static void test_container_from_end(std::vector<value_type>& values, bool splay);
+};
+
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_all
+ (std::vector<typename ValueTraits::value_type>& values, bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_multiset_type;
+ {
+ splay_multiset_type testset(values.begin(), values.end());
+ test::test_container(testset);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_common_unordered_and_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_non_unique_container(testset, values);
+ }
+ test_sort(values, splay);
+ test_insert(values, splay);
+ test_swap(values, splay);
+ test_find(values, splay);
+ test_splay_up(values);
+ test_splay_down(values);
+ test_impl(splay);
+ test_clone(values, splay);
+ test_container_from_end(values, splay);
+}
+
+//test case due to an error in tree implementation:
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_impl(bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ std::vector<value_type> values (5);
+ for (int i = 0; i < 5; ++i)
+ values[i].value_ = i;
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testset;
+ for (int i = 0; i < 5; ++i)
+ testset.insert (values[i]);
+
+ testset.erase (testset.iterator_to (values[0]));
+ testset.erase (testset.iterator_to (values[1]));
+ testset.insert (values[1]);
+
+ testset.erase (testset.iterator_to (values[2]));
+ testset.erase (testset.iterator_to (values[3]));
+}
+
+//test: constructor, iterator, clear, reverse_iterator, front, back, size:
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_sort
+(std::vector<typename ValueTraits::value_type>& values, bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testset1 (values.begin(), values.end());
+ { int init_values [] = { 1, 2, 2, 3, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ testset1.clear();
+ BOOST_TEST (testset1.empty());
+
+ typedef splay_multiset
+ <value_type
+ , compare<even_odd>
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type2;
+ multiset_type2 testset2 (&values[0], &values[0] + 6);
+ { int init_values [] = { 5, 3, 1, 4, 2, 2 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.rbegin() ); }
+
+ BOOST_TEST (testset2.begin()->value_ == 2);
+ BOOST_TEST (testset2.rbegin()->value_ == 5);
+}
+
+//test: insert, const_iterator, const_reverse_iterator, erase, iterator_to:
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_insert
+(std::vector<typename ValueTraits::value_type>& values, bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testset;
+ testset.insert(&values[0] + 2, &values[0] + 5);
+ { int init_values [] = { 1, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.begin() ); }
+
+ typename multiset_type::iterator i = testset.begin();
+ BOOST_TEST (i->value_ == 1);
+
+ i = testset.insert (i, values[0]);
+ BOOST_TEST (&*i == &values[0]);
+
+ { int init_values [] = { 5, 4, 3, 1 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.rbegin() ); }
+
+ i = testset.iterator_to (values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ i = multiset_type::s_iterator_to (values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ testset.erase(i);
+
+ { int init_values [] = { 1, 3, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.begin() ); }
+}
+
+//test: insert (seq-version), swap, erase (seq-version), size:
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_swap
+(std::vector<typename ValueTraits::value_type>& values, bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ multiset_type testset1 (&values[0], &values[0] + 2);
+ multiset_type testset2;
+ testset2.insert (&values[0] + 2, &values[0] + 6);
+
+ { int init_values [] = { 1, 2, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.begin() ); }
+ { int init_values [] = { 2, 3 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ testset1.swap (testset2);
+
+ { int init_values [] = { 1, 2, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+ { int init_values [] = { 2, 3 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.begin() ); }
+
+ testset1.erase (testset1.iterator_to(values[5]), testset1.end());
+ BOOST_TEST (testset1.size() == 1);
+ BOOST_TEST (&*testset1.begin() == &values[3]);
+}
+
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_splay_up
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ typedef typename multiset_type::iterator iterator;
+ typedef std::multiset<value_type> orig_multiset_t;
+ std::size_t num_values;
+ std::multiset<value_type> original_testset (values.begin(), values.end());
+ num_values = original_testset.size();
+
+ for(std::size_t i = 0; i != num_values; ++i){
+ multiset_type testset (values.begin(), values.end());
+ {
+ iterator it = testset.begin();
+ for(std::size_t j = 0; j != i; ++j, ++it){}
+ testset.splay_up(it);
+ }
+ BOOST_TEST (testset.size() == num_values);
+ iterator it = testset.begin();
+ for( typename orig_multiset_t::const_iterator origit = original_testset.begin()
+ , origitend = original_testset.end()
+ ; origit != origitend
+ ; ++origit, ++it){
+ BOOST_TEST(*origit == *it);
+ }
+ }
+}
+
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_splay_down
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ typedef typename multiset_type::iterator iterator;
+ typedef std::multiset<value_type> orig_multiset_t;
+ std::size_t num_values;
+ std::multiset<value_type> original_testset (values.begin(), values.end());
+ num_values = original_testset.size();
+
+ for(std::size_t i = 0; i != num_values; ++i){
+ multiset_type testset (values.begin(), values.end());
+ {
+ iterator it = testset.begin();
+ for(std::size_t j = 0; j != i; ++j, ++it){}
+ BOOST_TEST(*it == *testset.splay_down(*it));
+ }
+ BOOST_TEST (testset.size() == num_values);
+ iterator it = testset.begin();
+ for( typename orig_multiset_t::const_iterator origit = original_testset.begin()
+ , origitend = original_testset.end()
+ ; origit != origitend
+ ; ++origit, ++it){
+ BOOST_TEST(*origit == *it);
+ }
+ }
+}
+
+//test: find, equal_range (lower_bound, upper_bound):
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_find
+(std::vector<typename ValueTraits::value_type>& values, bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ multiset_type testset (values.begin(), values.end());
+ typedef typename multiset_type::iterator iterator;
+
+ value_type cmp_val;
+ cmp_val.value_ = 2;
+ iterator i = testset.find (cmp_val);
+ BOOST_TEST (i->value_ == 2);
+ BOOST_TEST ((++i)->value_ == 2);
+ std::pair<iterator,iterator> range = testset.equal_range (cmp_val);
+
+ BOOST_TEST (range.first->value_ == 2);
+ BOOST_TEST (range.second->value_ == 3);
+ BOOST_TEST (std::distance (range.first, range.second) == 2);
+
+ cmp_val.value_ = 7;
+ BOOST_TEST (testset.find (cmp_val) == testset.end());
+}
+
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_clone
+ (std::vector<typename ValueTraits::value_type>& values, bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ multiset_type testmultiset1 (&values[0], &values[0] + values.size());
+ multiset_type testmultiset2;
+
+ testmultiset2.clone_from(testmultiset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
+ BOOST_TEST (testmultiset2 == testmultiset1);
+ testmultiset2.clear_and_dispose(test::delete_disposer<value_type>());
+ BOOST_TEST (testmultiset2.empty());
+}
+
+template<class ValueTraits>
+void test_splay_multiset<ValueTraits>::test_container_from_end
+ (std::vector<typename ValueTraits::value_type>& values, bool splay)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testmultiset (&values[0], &values[0] + values.size());
+ BOOST_TEST (testmultiset == multiset_type::container_from_end_iterator(testmultiset.end()));
+ BOOST_TEST (testmultiset == multiset_type::container_from_end_iterator(testmultiset.cend()));
+}
+
+template<class VoidPointer, bool constant_time_size>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ for(int n = 0; n < 2; ++n){
+ typedef testvalue<VoidPointer, constant_time_size> value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<testvalue<VoidPointer, constant_time_size> > data (6);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_splay_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_base_hook_t
+ >::type
+ >::test_all(data, 0 != (n%2));
+ test_splay_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::splay_set_member_hook_t
+ , &value_type::splay_set_node_
+ >
+ >::type
+ >::test_all(data, 0 != (n%2));
+ }
+ return 0;
+ }
+};
+
+template<class VoidPointer>
+class test_main_template<VoidPointer, false>
+{
+ public:
+ int operator()()
+ {
+ for(int n = 0; n < 2; ++n){
+ typedef testvalue<VoidPointer, false> value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<testvalue<VoidPointer, false> > data (6);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_splay_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_base_hook_t
+ >::type
+ >::test_all(data, 0 != (n%2));
+
+ test_splay_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::splay_set_member_hook_t
+ , &value_type::splay_set_node_
+ >
+ >::type
+ >::test_all(data, 0 != (n%2));
+
+ test_splay_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_auto_base_hook_t
+ >::type
+ >::test_all(data, 0 != (n%2));
+
+ test_splay_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::splay_set_auto_member_hook_t
+ , &value_type::splay_set_auto_node_
+ >
+ >::type
+ >::test_all(data, 0 != (n%2));
+ }
+ return 0;
+ }
+};
+
+//Explicit instantiations of non-counted classes
+//template class multiset
+// <set_base_raw, std::less<set_base_raw::value_type>, false>;
+//template class multiset
+// <set_member_raw, std::less<set_member_raw::value_type>, false>;
+//template class multiset
+// <set_auto_base_raw, std::less<set_auto_base_raw::value_type>, false>;
+//template class multiset
+// <set_auto_member_raw, std::less<set_auto_member_raw::value_type>, false>;
+//template class multiset
+// <set_base_smart, std::less<set_base_smart::value_type>, false>;
+//template class multiset
+// <set_member_smart, std::less<set_member_smart::value_type>, false>;
+//template class multiset
+// <set_auto_base_smart, std::less<set_auto_base_smart::value_type>, false>;
+//template class multiset
+// <set_auto_member_smart, std::less<set_auto_member_smart::value_type>, false>;
+
+//Explicit instantiation of counted classes
+//template class multiset
+// <set_base_raw_t, std::less<set_base_raw_t::value_type>, true>;
+//template class multiset
+// <set_member_raw_t, std::less<set_member_raw_t::value_type>, true>;
+//template class multiset
+// <set_base_smart_t, std::less<set_base_smart_t::value_type>, true>;
+//template class multiset
+// <set_member_smart_t, std::less<set_member_smart_t::value_type>, true>;
+
+int main( int, char* [] )
+{
+ test_main_template<void*, false>()();
+ test_main_template<smart_ptr<void>, false>()();
+ test_main_template<void*, true>()();
+ test_main_template<smart_ptr<void>, true>()();
+ return boost::report_errors();
+}
Added: trunk/libs/intrusive/test/splay_set_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/splay_set_test.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -0,0 +1,425 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2007.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+#include <boost/intrusive/detail/config_begin.hpp>
+#include <boost/intrusive/splay_set.hpp>
+#include <boost/intrusive/detail/pointer_to_other.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "common_functors.hpp"
+#include <vector>
+#include <boost/detail/lightweight_test.hpp>
+#include "test_macros.hpp"
+#include "test_container.hpp"
+#include <set>
+
+namespace boost { namespace intrusive { namespace test {
+
+template<class T, class O1, class O2, class O3, class O4>
+struct has_const_overloads<boost::intrusive::splay_set<T, O1, O2, O3, O4> >
+{
+ static const bool value = false;
+};
+
+}}}
+
+using namespace boost::intrusive;
+
+template<class ValueTraits>
+struct test_splay_set
+{
+ typedef typename ValueTraits::value_type value_type;
+ static void test_all(std::vector<value_type>& values);
+ static void test_sort(std::vector<value_type>& values);
+ static void test_insert(std::vector<value_type>& values);
+ static void test_swap(std::vector<value_type>& values);
+ static void test_find(std::vector<value_type>& values);
+ static void test_splay_up(std::vector<value_type>& values);
+ static void test_splay_down(std::vector<value_type>& values);
+ static void test_impl();
+ static void test_clone(std::vector<value_type>& values);
+ static void test_container_from_end(std::vector<value_type>& values);
+};
+
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_all(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+ {
+ splay_set_type testset(values.begin(), values.end());
+ test::test_container(testset);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_common_unordered_and_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_unique_container(testset, values);
+ }
+
+ test_sort(values);
+ test_insert(values);
+ test_swap(values);
+ test_find(values);
+ test_splay_up(values);
+ test_splay_down(values);
+ test_impl();
+ test_clone(values);
+ test_container_from_end(values);
+}
+
+//test case due to an error in tree implementation:
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_impl()
+{
+ typedef typename ValueTraits::value_type value_type;
+ std::vector<value_type> values (5);
+ for (int i = 0; i < 5; ++i)
+ values[i].value_ = i;
+
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+ splay_set_type testset;
+ for (int i = 0; i < 5; ++i)
+ testset.insert (values[i]);
+
+ testset.erase (testset.iterator_to (values[0]));
+ testset.erase (testset.iterator_to (values[1]));
+ testset.insert (values[1]);
+
+ testset.erase (testset.iterator_to (values[2]));
+ testset.erase (testset.iterator_to (values[3]));
+}
+
+//test: constructor, iterator, clear, reverse_iterator, front, back, size:
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_sort(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+ splay_set_type testset1 (values.begin(), values.end());
+ { int init_values [] = { 1, 2, 3, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ testset1.clear();
+ BOOST_TEST (testset1.empty());
+
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , compare<even_odd>
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > set_type2;
+ set_type2 testset2 (&values[0], &values[0] + 6);
+ { int init_values [] = { 5, 3, 1, 4, 2 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.rbegin() ); }
+ BOOST_TEST (testset2.begin()->value_ == 2);
+ BOOST_TEST (testset2.rbegin()->value_ == 5);
+}
+
+//test: insert, const_iterator, const_reverse_iterator, erase, s_iterator_to:
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_insert(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+ splay_set_type testset;
+ testset.insert(&values[0] + 2, &values[0] + 5);
+
+ const splay_set_type& const_testset = testset;
+ { int init_values [] = { 1, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, const_testset.begin() ); }
+
+ typename splay_set_type::iterator i = testset.begin();
+ BOOST_TEST (i->value_ == 1);
+
+ i = testset.insert (i, values[0]);
+ BOOST_TEST (&*i == &values[0]);
+
+ { int init_values [] = { 5, 4, 3, 1 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.rbegin() ); }
+
+ i = testset.iterator_to (values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ i = splay_set_type::s_iterator_to(values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ testset.erase (i);
+ { int init_values [] = { 1, 3, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.begin() ); }
+}
+
+//test: insert (seq-version), swap, erase (seq-version), size:
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_swap(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+ splay_set_type testset1 (&values[0], &values[0] + 2);
+ splay_set_type testset2;
+ testset2.insert (&values[0] + 2, &values[0] + 6);
+ testset1.swap (testset2);
+
+ { int init_values [] = { 1, 2, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ { int init_values [] = { 2, 3 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.begin() ); }
+
+ testset1.erase (testset1.iterator_to(values[5]), testset1.end());
+ BOOST_TEST (testset1.size() == 1);
+ // BOOST_TEST (&testset1.front() == &values[3]);
+ BOOST_TEST (&*testset1.begin() == &values[3]);
+}
+
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_splay_up
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > set_type;
+ typedef typename set_type::iterator iterator;
+ typedef std::set<value_type> orig_set_t;
+ std::size_t num_values;
+ std::set<value_type> original_testset (values.begin(), values.end());
+ num_values = original_testset.size();
+
+ for(std::size_t i = 0; i != num_values; ++i){
+ set_type testset (values.begin(), values.end());
+ {
+ iterator it = testset.begin();
+ for(std::size_t j = 0; j != i; ++j, ++it){}
+ testset.splay_up(it);
+ }
+ BOOST_TEST (testset.size() == num_values);
+ iterator it = testset.begin();
+ for( typename orig_set_t::const_iterator origit = original_testset.begin()
+ , origitend = original_testset.end()
+ ; origit != origitend
+ ; ++origit, ++it){
+ BOOST_TEST(*origit == *it);
+ }
+ }
+}
+
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_splay_down
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > set_type;
+ typedef typename set_type::iterator iterator;
+ typedef std::set<value_type> orig_set_t;
+ std::size_t num_values;
+ std::set<value_type> original_testset (values.begin(), values.end());
+ num_values = original_testset.size();
+
+ for(std::size_t i = 0; i != num_values; ++i){
+ set_type testset (values.begin(), values.end());
+ BOOST_TEST(testset.size() == num_values);
+ {
+ iterator it = testset.begin();
+ for(std::size_t j = 0; j != i; ++j, ++it){}
+ BOOST_TEST(*it == *testset.splay_down(*it));
+ }
+ BOOST_TEST (testset.size() == num_values);
+ iterator it = testset.begin();
+ for( typename orig_set_t::const_iterator origit = original_testset.begin()
+ , origitend = original_testset.end()
+ ; origit != origitend
+ ; ++origit, ++it){
+ BOOST_TEST(*origit == *it);
+ }
+ }
+}
+
+//test: find, equal_range (lower_bound, upper_bound):
+template<class ValueTraits>
+void test_splay_set<ValueTraits>::test_find(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+ splay_set_type testset (values.begin(), values.end());
+ typedef typename splay_set_type::iterator iterator;
+
+ value_type cmp_val;
+ cmp_val.value_ = 2;
+ iterator i = testset.find (cmp_val);
+ BOOST_TEST (i->value_ == 2);
+ BOOST_TEST ((++i)->value_ != 2);
+ std::pair<iterator,iterator> range = testset.equal_range (cmp_val);
+
+ BOOST_TEST (range.first->value_ == 2);
+ BOOST_TEST (range.second->value_ == 3);
+ BOOST_TEST (std::distance (range.first, range.second) == 1);
+
+ cmp_val.value_ = 7;
+ BOOST_TEST (testset.find (cmp_val) == testset.end());
+}
+
+template<class ValueTraits>
+void test_splay_set<ValueTraits>
+ ::test_clone(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+
+ splay_set_type testset1 (&values[0], &values[0] + values.size());
+ splay_set_type testset2;
+
+ testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
+ BOOST_TEST (testset2 == testset1);
+ testset2.clear_and_dispose(test::delete_disposer<value_type>());
+ BOOST_TEST (testset2.empty());
+}
+
+template<class ValueTraits>
+void test_splay_set<ValueTraits>
+ ::test_container_from_end(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef splay_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > splay_set_type;
+ splay_set_type testset (&values[0], &values[0] + values.size());
+ BOOST_TEST (testset == splay_set_type::container_from_end_iterator(testset.end()));
+ BOOST_TEST (testset == splay_set_type::container_from_end_iterator(testset.cend()));
+}
+
+template<class VoidPointer, bool constant_time_size>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ typedef testvalue<VoidPointer, constant_time_size> value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<testvalue<VoidPointer, constant_time_size> > data (6);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_splay_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_base_hook_t
+ >::type
+ >::test_all(data);
+ test_splay_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::splay_set_member_hook_t
+ , &value_type::splay_set_node_
+ >
+ >::type
+ >::test_all(data);
+ return 0;
+ }
+};
+
+template<class VoidPointer>
+class test_main_template<VoidPointer, false>
+{
+ public:
+ int operator()()
+ {
+ typedef testvalue<VoidPointer, false> value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<testvalue<VoidPointer, false> > data (6);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_splay_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_base_hook_t
+ >::type
+ >::test_all(data);
+
+ test_splay_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::splay_set_member_hook_t
+ , &value_type::splay_set_node_
+ >
+ >::type
+ >::test_all(data);
+
+ test_splay_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_auto_base_hook_t
+ >::type
+ >::test_all(data);
+
+ test_splay_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::splay_set_auto_member_hook_t
+ , &value_type::splay_set_auto_node_
+ >
+ >::type
+ >::test_all(data);
+
+ return 0;
+ }
+};
+
+int main( int, char* [] )
+{
+ test_main_template<void*, false>()();
+ test_main_template<smart_ptr<void>, false>()();
+ test_main_template<void*, true>()();
+ test_main_template<smart_ptr<void>, true>()();
+ return boost::report_errors();
+}
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/test_container.hpp
==============================================================================
--- trunk/libs/intrusive/test/test_container.hpp (original)
+++ trunk/libs/intrusive/test/test_container.hpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -14,11 +14,18 @@
#define BOOST_INTRUSIVE_TEST_CONTAINER_HPP
#include <boost/detail/lightweight_test.hpp>
+#include <boost/intrusive/detail/mpl.hpp>
namespace boost {
namespace intrusive {
namespace test {
+template<class T>
+struct has_const_overloads
+{
+ static const bool value = true;
+};
+
template< class Container >
void test_container( Container & c )
{
@@ -151,7 +158,7 @@
}
template< class Container, class Data >
-void test_associative_container_invariants(Container & c, Data & d)
+void test_associative_container_invariants(Container & c, Data & d, boost::intrusive::detail::true_type)
{
typedef typename Container::const_iterator const_iterator;
for( typename Data::const_iterator di = d.begin(), de = d.end();
@@ -178,6 +185,19 @@
}
template< class Container, class Data >
+void test_associative_container_invariants(Container & c, Data & d, boost::intrusive::detail::false_type)
+{}
+
+template< class Container, class Data >
+void test_associative_container_invariants(Container & c, Data & d)
+{
+ using namespace boost::intrusive;
+ typedef typename detail::remove_const<Container>::type Type;
+ typedef detail::bool_<has_const_overloads<Type>::value> enabler;
+ test_associative_container_invariants(c, d, enabler());
+}
+
+template< class Container, class Data >
void test_associative_container(Container & c, Data & d)
{
typedef typename Container::const_iterator const_iterator;
@@ -194,7 +214,7 @@
}
template< class Container, class Data >
-void test_unordered_associative_container_invariants(Container & c, Data & d)
+void test_unordered_associative_container_invariants(Container & c, Data & d, boost::intrusive::detail::true_type)
{
typedef typename Container::size_type size_type;
typedef typename Container::const_iterator const_iterator;
@@ -225,6 +245,19 @@
}
template< class Container, class Data >
+void test_unordered_associative_container_invariants(Container & c, Data & d, boost::intrusive::detail::false_type)
+{}
+
+template< class Container, class Data >
+void test_unordered_associative_container_invariants(Container & c, Data & d)
+{
+ using namespace boost::intrusive;
+ typedef typename detail::remove_const<Container>::type Type;
+ typedef detail::bool_<has_const_overloads<Type>::value> enabler;
+ test_unordered_associative_container_invariants(c, d, enabler());
+}
+
+template< class Container, class Data >
void test_unordered_associative_container(Container & c, Data & d)
{
c.clear();
Modified: trunk/libs/intrusive/test/unordered_multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/unordered_multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/unordered_multiset_test.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -317,7 +317,7 @@
src(testset1.begin(), testset1.end());
std::multiset<typename ValueTraits::value_type>
dst(testset2.begin(), testset2.end());
- BOOST_TEST (src == dst);
+ BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
testset2.clear_and_dispose(test::delete_disposer<value_type>());
BOOST_TEST (testset2.empty());
}
@@ -334,7 +334,7 @@
src(testset1.begin(), testset1.end());
std::multiset<typename ValueTraits::value_type>
dst(testset2.begin(), testset2.end());
- BOOST_TEST (src == dst);
+ BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
testset2.clear_and_dispose(test::delete_disposer<value_type>());
BOOST_TEST (testset2.empty());
}
@@ -351,7 +351,7 @@
src(testset1.begin(), testset1.end());
std::multiset<typename ValueTraits::value_type>
dst(testset2.begin(), testset2.end());
- BOOST_TEST (src == dst);
+ BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
testset2.clear_and_dispose(test::delete_disposer<value_type>());
BOOST_TEST (testset2.empty());
}
Modified: trunk/libs/intrusive/test/unordered_set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/unordered_set_test.cpp (original)
+++ trunk/libs/intrusive/test/unordered_set_test.cpp 2007-10-24 15:00:30 EDT (Wed, 24 Oct 2007)
@@ -291,7 +291,7 @@
src(testset1.begin(), testset1.end());
std::set<typename ValueTraits::value_type>
dst(testset2.begin(), testset2.end());
- BOOST_TEST (src == dst );
+ BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
testset2.clear_and_dispose(test::delete_disposer<value_type>());
BOOST_TEST (testset2.empty());
}
@@ -308,7 +308,7 @@
src(testset1.begin(), testset1.end());
std::set<typename ValueTraits::value_type>
dst(testset2.begin(), testset2.end());
- BOOST_TEST (src == dst );
+ BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
testset2.clear_and_dispose(test::delete_disposer<value_type>());
BOOST_TEST (testset2.empty());
}
@@ -325,7 +325,7 @@
src(testset1.begin(), testset1.end());
std::set<typename ValueTraits::value_type>
dst(testset2.begin(), testset2.end());
- BOOST_TEST (src == dst );
+ BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
testset2.clear_and_dispose(test::delete_disposer<value_type>());
BOOST_TEST (testset2.empty());
}