From: igaztanaga_at_[hidden]
Date: 2007-11-18 05:45:00
Author: igaztanaga
Date: 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
New Revision: 41196
URL: http://svn.boost.org/trac/boost/changeset/41196
Log:
Added scapegoat trees and an option to store the hash value in the hook for unordered containers
Added:
trunk/libs/intrusive/example/doc_sg_set.cpp (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/sg_multiset/
trunk/libs/intrusive/proj/vc7ide/sg_multiset/sg_multiset.vcproj (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/sg_set/
trunk/libs/intrusive/proj/vc7ide/sg_set/sg_set.vcproj (contents, props changed)
trunk/libs/intrusive/test/generic_assoc_test.hpp (contents, props changed)
trunk/libs/intrusive/test/generic_multiset_test.hpp (contents, props changed)
trunk/libs/intrusive/test/generic_set_test.hpp (contents, props changed)
trunk/libs/intrusive/test/sg_multiset_test.cpp (contents, props changed)
trunk/libs/intrusive/test/sg_set_test.cpp (contents, props changed)
Text files modified:
trunk/libs/intrusive/doc/Jamfile.v2 | 3
trunk/libs/intrusive/doc/intrusive.qbk | 210 ++++++++++++++++
trunk/libs/intrusive/example/doc_avl_set.cpp | 8
trunk/libs/intrusive/example/doc_set.cpp | 8
trunk/libs/intrusive/example/doc_splay_set.cpp | 37 +-
trunk/libs/intrusive/proj/vc7ide/Intrusive.sln | 16 +
trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj | 24 +
trunk/libs/intrusive/proj/vc7ide/avl_multiset/avl_multiset.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/avl_set/avl_set.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/custom_bucket_traits/custom_bucket_traits.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/default_hook/default_hook.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/external_value_traits/external_value_traits.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/list/list.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/make_functions/make_functions.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/multiset/multiset.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/perf_test/perf_test.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/set/set.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/slist/slist.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/splay_multiset/splay_multiset.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/splay_set/splay_set.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/stateful_value_traits/stateful_value_traits.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/to-do.txt | 10
trunk/libs/intrusive/proj/vc7ide/unordered_multiset/unordered_multiset.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/unordered_set/unordered_set.vcproj | 3
trunk/libs/intrusive/proj/vc7ide/virtual_base/virtual_base.vcproj | 3
trunk/libs/intrusive/test/avl_multiset_test.cpp | 416 +++++----------------------------
trunk/libs/intrusive/test/avl_set_test.cpp | 311 +++----------------------
trunk/libs/intrusive/test/external_value_traits_test.cpp | 7
trunk/libs/intrusive/test/itestvalue.hpp | 35 ++
trunk/libs/intrusive/test/make_functions_test.cpp | 3
trunk/libs/intrusive/test/multiset_test.cpp | 328 +++-----------------------
trunk/libs/intrusive/test/set_test.cpp | 294 ++---------------------
trunk/libs/intrusive/test/splay_multiset_test.cpp | 489 ++++++---------------------------------
trunk/libs/intrusive/test/splay_set_test.cpp | 377 +++---------------------------
trunk/libs/intrusive/test/stateful_value_traits_test.cpp | 3
trunk/libs/intrusive/test/test_container.hpp | 4
36 files changed, 663 insertions(+), 1971 deletions(-)
Modified: trunk/libs/intrusive/doc/Jamfile.v2
==============================================================================
--- trunk/libs/intrusive/doc/Jamfile.v2 (original)
+++ trunk/libs/intrusive/doc/Jamfile.v2 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -33,6 +33,9 @@
"splay_set_impl=splay_set" \\
"splay_multiset_impl=splay_multiset" \\
"splaytree_impl=splaytree" \\
+ "sg_set_impl=sg_set" \\
+ "sg_multiset_impl=sg_multiset" \\
+ "sgtree_impl=sgtree" \\
"avl_set_impl=avl_set" \\
"avl_multiset_impl=avl_multiset" \\
"avltree_impl=avltree""
Modified: trunk/libs/intrusive/doc/intrusive.qbk
==============================================================================
--- trunk/libs/intrusive/doc/intrusive.qbk (original)
+++ trunk/libs/intrusive/doc/intrusive.qbk 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -1140,6 +1140,17 @@
internally in the hook and propagated to the container.
Default: `void_pointer<void*>`.
+Apart from them, these hooks offer additional options:
+
+* [*`store_hash<bool Enabled>`]: This option reserves additional space in
+ the hook to store the hash value of the object once it's introduced in the
+ container. When this option is used, the unordered container will store
+ the calculated hash value in the hook and rehashing operations won't need
+ to recalculate the hash of the value.
+ This option will improve the perfomance of unordered containers when
+ rehashing is frequent or hashing the value is a slow operation.
+ Default: `store_hash<false>`.
+
[endsect]
[section:unordered_set_unordered_multiset_containers unordered_set and unordered_multiset containers]
@@ -1269,7 +1280,7 @@
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].
+For more information on splay trees see [@http://en.wikipedia.org/wiki/Splay_tree Wikipedia entry].
[*Boost.Intrusive] offers 3 containers based on splay trees:
[classref boost::intrusive::splay_set splay_set],
@@ -1382,9 +1393,30 @@
[endsect]
+[section:splay_set_bst_hook Splay trees with BST hooks]
+
+Intrusive splay containers can also use plain binary search tree hooks
+[classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
+[classref boost::intrusive::bs_set_base_hook bs_set_base_hook].
+These hooks can be used by other intrusive containers like
+intrusive scapegoat containers
+[classref boost::intrusive::sg_set sg_set] and
+[classref boost::intrusive::sg_multiset sg_multiset] so a programmer
+might prefer using a binary search tree hook so that the same type
+can be introduced in some situations in an splay container but that
+can also be introduced in other compatible containers as well when
+the hook is not being used in an splay container.
+
+[classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
+[classref boost::intrusive::bs_set_base_hook bs_set_member_hook] admit
+the same options as [classref boost::intrusive::splay_set_base_hook splay_set_base_hook].
+
+[endsect]
+
[section:splay_set_multiset_example Example]
-Now let's see an small example using both hooks and
+Now let's see an small example using both splay hooks,
+binary search tree hooks and
[classref boost::intrusive::splay_set splay_set]/
[classref boost::intrusive::splay_multiset splay_multiset]
containers:
@@ -1396,7 +1428,6 @@
[endsect]
-
[section:avl_set_multiset Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree]
Similar to red-black trees, AVL trees are balanced binary trees.
@@ -1525,6 +1556,179 @@
[endsect]
+[section:sg_set_multiset Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree]
+
+A scapegoat tree is a self-balancing binary search tree, that provides worst-case O(log n)
+lookup time, and O(log n) amortized insertion and deletion time.
+Unlike other self-balancing binary search trees that provide worst case O(log n) lookup
+time, scapegoat trees have no additional per-node overhead compared to a regular binary
+search tree.
+
+A binary search tree is said to be weight balanced if half the nodes are on the left
+of the root, and half on the right. An α-height-balanced tree is defined with defined
+with the following equation:
+
+[*['height(tree) <= log1/α(tree.size())]]
+
+* [*['α == 1]]: A tree forming a linked list is considered balanced.
+* [*['α == 0.5]]: Only a perfectly balanced binary is considered balanced.
+
+Scapegoat trees are loosely ['α-height-balanced] so:
+
+[*['height(tree) <= log1/α(tree.size()) + 1]]
+
+Scapegoat trees support any α between 0.5 and 1. If α is higher, the tree is rebalanced
+less often, obtaining quicker insertions but slower searches. Lower
+α values improve search times. Scapegoat-trees implemented in [*Boost.Intrusive] offer the possibility of
+[*changing α at run-time] taking advantage of the flexibility of scapegoat trees.
+For more information on scapegoat trees see [@http://en.wikipedia.org/wiki/Scapegoat_tree Wikipedia entry].
+
+Scapegoat trees also have downsides:
+
+* They need additional storage of data on the
+ root (the size of the tree, for example) to achieve logarithmic complexity operations
+ so it's not possible to offer `auto_unlink` hooks. The size of an empty scapegoat
+ tree is also considerably increased.
+
+* The operations needed to determine if the tree is unbalanced require floating-point
+ operations like ['log1/α]. If the system has no floating point operations (like some
+ embedded systems), scapegoat tree operations might become slow.
+
+[*Boost.Intrusive] offers 3 containers based on scapegoat trees:
+[classref boost::intrusive::sg_set sg_set],
+[classref boost::intrusive::sg_multiset sg_multiset] and
+[classref boost::intrusive::sgtree sgtree]. 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 3
+pointers.
+
+An empty, [classref boost::intrusive::sg_set sg_set],
+[classref boost::intrusive::sg_multiset sg_multiset] or
+[classref boost::intrusive::sgtree sgtree]
+has also the size of 3 pointers, two integers and two floating point values
+(equivalent to the size of 7 pointers on most systems).
+
+[section:sg_set_multiset_hooks Using binary search tree hooks: bs_set_base_hook and bs_set_member_hook]
+
+[classref boost::intrusive::sg_set sg_set],
+[classref boost::intrusive::sg_multiset sg_multiset] and
+[classref boost::intrusive::sgtree sgtree] don't use their
+own hooks but plain binary search tree hooks. This has many advantages
+since binary search tree hooks can also be used to insert values in
+splay containers.
+
+[c++]
+
+ template <class ...Options>
+ class bs_set_base_hook;
+
+* [classref boost::intrusive::bs_set_base_hook bs_set_base_hook]:
+ the user class derives publicly from this class to make
+ it compatible with scapegoat tree based containers.
+
+[c++]
+
+ template <class ...Options>
+ class bs_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 scapegoat tree based containers.
+
+[classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
+[classref boost::intrusive::bs_set_member_hook bs_set_member_hook] receive
+the same options explained in the section
+[link intrusive.usage How to use Boost.Intrusive] plus an option to optimize
+the size of the node:
+
+* [*`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:sg_set_multiset_containers sg_set, sg_multiset and sgtree containers]
+
+[c++]
+
+ template <class T, class ...Options>
+ class sg_set;
+
+ template <class T, class ...Options>
+ class sg_multiset;
+
+ template <class T, class ...Options>
+ class sgtree;
+
+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].
+
+* [*`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 additional options:
+
+* [*`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> >`
+
+* [*`floating_point<bool Enable>`]:
+ When this option is deactivated, the scapegoat tree loses the ability to change
+ the balance factor α at run-time, but the size of an empty container is reduced
+ and no floating point operations are performed, normally increasing container
+ performance. The fixed α factor that is used when this option is activated
+ is ['1/sqrt(2) ~ 0,70711]. Default: `floating_point<true>`
+
+[endsect]
+
+[section:sg_set_multiset_example Example]
+
+Now let's see an small example using both hooks and
+[classref boost::intrusive::sg_set sg_set]/
+[classref boost::intrusive::sg_multiset sg_multiset]
+containers:
+
+[import ../example/doc_sg_set.cpp]
+[doc_sg_set_code]
+
+[endsect]
+
+[endsect]
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
[section:advanced_lookups_insertions Advanced lookup and insertion functions for associative containers]
[section:advanced_lookups Advanced lookups]
Modified: trunk/libs/intrusive/example/doc_avl_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_avl_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_avl_set.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -61,13 +61,11 @@
//Check that size optimization is deactivated in the member hook
assert(sizeof(avl_set_member_hook<>) > 3*sizeof(void*));
- //Now insert them in the reverse order in the base hook avl_set
- for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
+ //Now insert them in the sets
+ 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 avl_set
- for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
membermultiset.insert(*it);
+ }
//Now test avl_sets
{
Modified: trunk/libs/intrusive/example/doc_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_set.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -37,7 +37,7 @@
{ return a.int_ < b.int_; }
};
-//Define an set using the base hook that will store values in reverse order
+//Define a set using the base hook that will store values in reverse order
typedef set< MyClass, compare<std::greater<MyClass> > > BaseSet;
//Define an multiset using the member hook
@@ -62,12 +62,10 @@
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)
+ 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
{
Added: trunk/libs/intrusive/example/doc_sg_set.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_sg_set.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,85 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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.
+//
+/////////////////////////////////////////////////////////////////////////////
+//[doc_sg_set_code
+#include <boost/intrusive/sg_set.hpp>
+#include <vector>
+#include <algorithm>
+#include <cassert>
+
+using namespace boost::intrusive;
+
+class MyClass : public bs_set_base_hook<>
+{
+ int int_;
+
+ public:
+ //This is a member hook
+ bs_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 sg_set using the base hook that will store values in reverse order
+//and won't execute floating point operations.
+typedef sg_set
+ < MyClass, compare<std::greater<MyClass> >, floating_point<false> > BaseSet;
+
+//Define an multiset using the member hook
+typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption;
+typedef sg_multiset< MyClass, MemberOption> MemberMultiset;
+
+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));
+
+ BaseSet baseset;
+ MemberMultiset membermultiset;
+
+ //Now insert them in the reverse order in the base hook sg_set
+ for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
+ baseset.insert(*it);
+ membermultiset.insert(*it);
+ }
+
+ //Change balance factor
+ membermultiset.balance_factor(0.9f);
+
+ //Now test sg_sets
+ {
+ BaseSet::reverse_iterator rbit(baseset.rbegin()), rbitend(baseset.rend());
+ MemberMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end());
+ VectIt it(values.begin()), itend(values.end());
+
+ //Test the objects inserted in the base hook sg_set
+ for(; it != itend; ++it, ++rbit)
+ if(&*rbit != &*it) return 1;
+
+ //Test the objects inserted in the member hook sg_set
+ for(it = values.begin(); it != itend; ++it, ++mit)
+ if(&*mit != &*it) return 1;
+ }
+ return 0;
+}
+//]
Modified: trunk/libs/intrusive/example/doc_splay_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_splay_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_splay_set.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -11,13 +11,16 @@
/////////////////////////////////////////////////////////////////////////////
//[doc_splay_set_code
#include <boost/intrusive/splay_set.hpp>
+#include <boost/intrusive/bs_set_hook.hpp>
#include <vector>
#include <algorithm>
using namespace boost::intrusive;
- //This is a base hook
-class MyClass : public splay_set_base_hook<>
+class MyClass
+ : public splay_set_base_hook<> //This is an splay tree base hook
+ , public bs_set_base_hook<> //This is a binary search tree base hook
+
{
int int_;
@@ -36,9 +39,12 @@
{ return a.int_ < b.int_; }
};
-//Define an set using the base hook that will store values in reverse order
+//Define a set using the base hook that will store values in reverse order
typedef splay_set< MyClass, compare<std::greater<MyClass> > > BaseSplaySet;
+//Define a set using the binary search tree hook
+typedef splay_set< MyClass, base_hook<bs_set_base_hook<> > > BaseBsSplaySet;
+
//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;
@@ -52,30 +58,35 @@
std::vector<MyClass> values;
for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
- BaseSplaySet baseset;
+ BaseSplaySet baseset;
+ BaseBsSplaySet bsbaseset;
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)
+ //Insert values in the container
+ for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
+ baseset.insert(*it);
+ bsbaseset.insert(*it);
membermultiset.insert(*it);
+ }
//Now test sets
{
BaseSplaySet::reverse_iterator rbit(baseset.rbegin()), rbitend(baseset.rend());
+ BaseBsSplaySet::iterator bsit(bsbaseset.begin()), bsitend(bsbaseset.end());
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)
+ 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;
+ //Test the objects inserted in member and binary search hook sets
+ for(it = values.begin(); it != itend; ++it, ++bsit, ++mit){
+ if(&*bsit != &*it) return 1;
+ 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-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -71,6 +71,14 @@
ProjectSection(ProjectDependencies) = postProject
EndProjectSection
EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "sg_multiset", "sg_multiset\sg_multiset.vcproj", "{07022E76-6CB5-92C1-B47F-A10772A79B43}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "sg_set", "sg_set\sg_set.vcproj", "{1690A9E7-DB57-971C-F24A-09B752A942F7}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
Global
GlobalSection(SolutionConfiguration) = preSolution
Debug = Debug
@@ -151,6 +159,14 @@
{16909EE7-24AF-97C1-C76B-204B971BA959}.Debug.Build.0 = Debug|Win32
{16909EE7-24AF-97C1-C76B-204B971BA959}.Release.ActiveCfg = Release|Win32
{16909EE7-24AF-97C1-C76B-204B971BA959}.Release.Build.0 = Release|Win32
+ {07022E76-6CB5-92C1-B47F-A10772A79B43}.Debug.ActiveCfg = Debug|Win32
+ {07022E76-6CB5-92C1-B47F-A10772A79B43}.Debug.Build.0 = Debug|Win32
+ {07022E76-6CB5-92C1-B47F-A10772A79B43}.Release.ActiveCfg = Release|Win32
+ {07022E76-6CB5-92C1-B47F-A10772A79B43}.Release.Build.0 = Release|Win32
+ {1690A9E7-DB57-971C-F24A-09B752A942F7}.Debug.ActiveCfg = Debug|Win32
+ {1690A9E7-DB57-971C-F24A-09B752A942F7}.Debug.Build.0 = Debug|Win32
+ {1690A9E7-DB57-971C-F24A-09B752A942F7}.Release.ActiveCfg = Release|Win32
+ {1690A9E7-DB57-971C-F24A-09B752A942F7}.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-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -118,6 +118,9 @@
RelativePath="..\..\..\..\..\boost\intrusive\avltree_algorithms.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\bs_set_hook.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\circular_list_algorithms.hpp">
</File>
<File
@@ -166,6 +169,15 @@
RelativePath="..\..\..\..\..\boost\intrusive\set_hook.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\sg_set.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\sgtree.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\sgtree_algorithms.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\slist.hpp">
</File>
<File
@@ -268,6 +280,15 @@
RelativePath="..\..\..\test\common_functors.hpp">
</File>
<File
+ RelativePath="..\..\..\test\generic_assoc_test.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\test\generic_multiset_test.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\test\generic_set_test.hpp">
+ </File>
+ <File
RelativePath="..\..\..\test\itestvalue.hpp">
</File>
<File
@@ -344,6 +365,9 @@
RelativePath="..\..\..\example\doc_set.cpp">
</File>
<File
+ RelativePath="..\..\..\example\doc_sg_set.cpp">
+ </File>
+ <File
RelativePath="..\..\..\example\doc_slist.cpp">
</File>
<File
Modified: trunk/libs/intrusive/proj/vc7ide/avl_multiset/avl_multiset.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/avl_multiset/avl_multiset.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/avl_multiset/avl_multiset.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -26,9 +26,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/avl_set/avl_set.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/avl_set/avl_set.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/avl_set/avl_set.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -25,9 +25,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/custom_bucket_traits/custom_bucket_traits.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/custom_bucket_traits/custom_bucket_traits.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/custom_bucket_traits/custom_bucket_traits.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -28,9 +28,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/default_hook/default_hook.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/default_hook/default_hook.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/default_hook/default_hook.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -28,9 +28,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/external_value_traits/external_value_traits.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/external_value_traits/external_value_traits.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/external_value_traits/external_value_traits.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -28,9 +28,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/list/list.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/list/list.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/list/list.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -28,9 +28,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/make_functions/make_functions.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/make_functions/make_functions.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/make_functions/make_functions.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -28,9 +28,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/multiset/multiset.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/multiset/multiset.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/multiset/multiset.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -25,9 +25,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/perf_test/perf_test.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/perf_test/perf_test.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/perf_test/perf_test.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -25,9 +25,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/set/set.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/set/set.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/set/set.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -25,9 +25,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Added: trunk/libs/intrusive/proj/vc7ide/sg_multiset/sg_multiset.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/sg_multiset/sg_multiset.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,128 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="sg_multiset"
+ ProjectGUID="{07022E76-6CB5-92C1-B47F-A10772A79B43}"
+ 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"
+ TreatWChar_tAsBuiltInType="TRUE"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="4"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/sg_multiset.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/sg_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)/sg_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="{7F97AC3C-5426-8CA7-5D74-2B385DAA232F}">
+ <File
+ RelativePath="..\..\..\test\sg_multiset_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Added: trunk/libs/intrusive/proj/vc7ide/sg_set/sg_set.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/sg_set/sg_set.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,127 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="sg_set"
+ ProjectGUID="{1690A9E7-DB57-971C-F24A-09B752A942F7}"
+ 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"
+ TreatWChar_tAsBuiltInType="TRUE"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="4"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/sg_set.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/sg_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)/sg_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="{FC770E61-A263-71E5-72AF-2E7D2C33A42A}">
+ <File
+ RelativePath="..\..\..\test\sg_set_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Modified: trunk/libs/intrusive/proj/vc7ide/slist/slist.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/slist/slist.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/slist/slist.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -25,9 +25,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/splay_multiset/splay_multiset.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/splay_multiset/splay_multiset.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/splay_multiset/splay_multiset.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -26,9 +26,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/splay_set/splay_set.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/splay_set/splay_set.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/splay_set/splay_set.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -25,9 +25,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/stateful_value_traits/stateful_value_traits.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/stateful_value_traits/stateful_value_traits.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/stateful_value_traits/stateful_value_traits.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -28,9 +28,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
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-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -1,15 +1,7 @@
add includes needed for the snippets
add section explaining splice(...,n)
-(Node algorithms with custom NodeTraits)La sección deja al lector con la pregunta:
- ¿para qué sirve esto? debido a que los node traits no se ponen en conexión con
- los contenedores intrusivos, esto se explica más adelante en la siguiente sección,
- pero a lo mejor estaría bien comentarlo someramente aquí para que al lector le
- encajen los conceptos.
Faltaría, en mi opinión, una guía de qué headers incluyen a cuáles. P.ej.,
los *_hook.hpp típicamente están incluidos por el header del contenedor asociado, etc.
-Explain the default hook states for custom value_traits.
-Create a new assertion for each type of error
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.
+Optimize store_hash<true> to work with the same node and type traits as store_hash<false>
Modified: trunk/libs/intrusive/proj/vc7ide/unordered_multiset/unordered_multiset.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/unordered_multiset/unordered_multiset.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/unordered_multiset/unordered_multiset.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -26,9 +26,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/unordered_set/unordered_set.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/unordered_set/unordered_set.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/unordered_set/unordered_set.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -25,9 +25,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/proj/vc7ide/virtual_base/virtual_base.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/virtual_base/virtual_base.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/virtual_base/virtual_base.vcproj 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -28,9 +28,10 @@
BasicRuntimeChecks="3"
RuntimeLibrary="5"
DisableLanguageExtensions="FALSE"
+ TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
- WarningLevel="3"
+ WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="4"/>
<Tool
Modified: trunk/libs/intrusive/test/avl_multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/avl_multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/avl_multiset_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -15,296 +15,47 @@
#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>
+#include "generic_multiset_test.hpp"
-namespace boost { namespace intrusive { namespace test {
-
-template<class T, class O1, class O2, class O3, class O4>
-struct has_const_overloads<boost::intrusive::avl_multiset<T, O1, O2, O3, O4> >
-{
- static const bool value = false;
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::avl_multiset
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
};
-}}}
-
-using namespace boost::intrusive;
-template<class ValueTraits>
-struct test_avl_multiset
-{
- 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_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_avl_multiset<ValueTraits>::test_all
- (std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_multiset
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_multiset_type;
- {
- avl_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);
- test_insert(values);
- test_swap(values);
- test_find(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_avl_multiset<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 avl_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_avl_multiset<ValueTraits>::test_sort
-(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_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 avl_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_avl_multiset<ValueTraits>::test_insert
-(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_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_avl_multiset<ValueTraits>::test_swap
-(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_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]);
-}
-
-//test: find, equal_range (lower_bound, upper_bound):
-template<class ValueTraits>
-void test_avl_multiset<ValueTraits>::test_find
-(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_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_avl_multiset<ValueTraits>::test_clone
- (std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_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_avl_multiset<ValueTraits>::test_container_from_end
- (std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_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];
+ using namespace boost::intrusive;
+ typedef testvalue<VoidPointer, constant_time_size> value_type;
- test_avl_multiset < typename detail::get_base_value_traits
- < value_type
- , typename value_type::avl_set_base_hook_t
- >::type
- >::test_all(data);
- test_avl_multiset < typename detail::get_member_value_traits
- < value_type
- , member_hook< value_type
- , typename value_type::avl_set_member_hook_t
- , &value_type::avl_set_node_
- >
- >::type
- >::test_all(data);
- }
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::avl_set_member_hook_t
+ , &value_type::avl_set_node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
return 0;
}
};
@@ -315,80 +66,53 @@
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];
+ using namespace boost::intrusive;
+ typedef testvalue<VoidPointer, false> value_type;
- test_avl_multiset < typename detail::get_base_value_traits
- < value_type
- , typename value_type::avl_set_base_hook_t
- >::type
- >::test_all(data);
-
- test_avl_multiset < typename detail::get_member_value_traits
- < value_type
- , member_hook< value_type
- , typename value_type::avl_set_member_hook_t
- , &value_type::avl_set_node_
- >
- >::type
- >::test_all(data);
-
- test_avl_multiset < typename detail::get_base_value_traits
- < value_type
- , typename value_type::avl_set_auto_base_hook_t
- >::type
- >::test_all(data);
-
- test_avl_multiset < typename detail::get_member_value_traits
- < value_type
- , member_hook< value_type
- , typename value_type::avl_set_auto_member_hook_t
- , &value_type::avl_set_auto_node_
- >
- >::type
- >::test_all(data);
- }
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::avl_set_member_hook_t
+ , &value_type::avl_set_node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_auto_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::avl_set_auto_member_hook_t
+ , &value_type::avl_set_auto_node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
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<boost::intrusive::smart_ptr<void>, false>()();
test_main_template<void*, true>()();
- test_main_template<smart_ptr<void>, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
return boost::report_errors();
}
+
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/avl_set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/avl_set_test.cpp (original)
+++ trunk/libs/intrusive/test/avl_set_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -1,6 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007.
+// (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
@@ -11,284 +12,49 @@
/////////////////////////////////////////////////////////////////////////////
#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/avl_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>
+#include "generic_set_test.hpp"
-namespace boost { namespace intrusive { namespace test {
-
-template<class T, class O1, class O2, class O3, class O4>
-struct has_const_overloads<boost::intrusive::avl_set<T, O1, O2, O3, O4> >
-{
- static const bool value = false;
-};
-
-}}}
-
-using namespace boost::intrusive;
-
-template<class ValueTraits>
-struct test_avl_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_impl();
- static void test_clone(std::vector<value_type>& values);
- static void test_container_from_end(std::vector<value_type>& values);
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::avl_set
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
};
-template<class ValueTraits>
-void test_avl_set<ValueTraits>::test_all(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
- {
- avl_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_impl();
- test_clone(values);
- test_container_from_end(values);
-}
-
-//test case due to an error in tree implementation:
-template<class ValueTraits>
-void test_avl_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 avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
- avl_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_avl_set<ValueTraits>::test_sort(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
- avl_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 avl_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_avl_set<ValueTraits>::test_insert(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
- avl_set_type testset;
- testset.insert(&values[0] + 2, &values[0] + 5);
-
- const avl_set_type& const_testset = testset;
- { int init_values [] = { 1, 4, 5 };
- TEST_INTRUSIVE_SEQUENCE( init_values, const_testset.begin() ); }
-
- typename avl_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 = avl_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_avl_set<ValueTraits>::test_swap(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
- avl_set_type testset1 (&values[0], &values[0] + 2);
- avl_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]);
-}
-
-//test: find, equal_range (lower_bound, upper_bound):
-template<class ValueTraits>
-void test_avl_set<ValueTraits>::test_find(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
- avl_set_type testset (values.begin(), values.end());
- typedef typename avl_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_avl_set<ValueTraits>
- ::test_clone(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
-
- avl_set_type testset1 (&values[0], &values[0] + values.size());
- avl_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_avl_set<ValueTraits>
- ::test_container_from_end(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef avl_set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > avl_set_type;
- avl_set_type testset (&values[0], &values[0] + values.size());
- BOOST_TEST (testset == avl_set_type::container_from_end_iterator(testset.end()));
- BOOST_TEST (testset == avl_set_type::container_from_end_iterator(testset.cend()));
-}
-
template<class VoidPointer, bool constant_time_size>
class test_main_template
{
public:
int operator()()
{
+ using namespace boost::intrusive;
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_avl_set < typename detail::get_base_value_traits
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::avl_set_base_hook_t
>::type
- >::test_all(data);
- test_avl_set < typename detail::get_member_value_traits
+ , GetContainer
+ >::test_all();
+ test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::avl_set_member_hook_t
, &value_type::avl_set_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
return 0;
}
};
@@ -299,41 +65,42 @@
public:
int operator()()
{
+ using namespace boost::intrusive;
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_avl_set < typename detail::get_base_value_traits
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::avl_set_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_avl_set < typename detail::get_member_value_traits
+ test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::avl_set_member_hook_t
, &value_type::avl_set_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_avl_set < typename detail::get_base_value_traits
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::avl_set_auto_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_avl_set < typename detail::get_member_value_traits
+ test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::avl_set_auto_member_hook_t
, &value_type::avl_set_auto_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
return 0;
}
@@ -341,10 +108,12 @@
int main( int, char* [] )
{
+
test_main_template<void*, false>()();
- test_main_template<smart_ptr<void>, false>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, false>()();
test_main_template<void*, true>()();
- test_main_template<smart_ptr<void>, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
return boost::report_errors();
}
+
#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/external_value_traits_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/external_value_traits_test.cpp (original)
+++ trunk/libs/intrusive/test/external_value_traits_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -207,8 +207,7 @@
Rbtree &my_rbtree = static_cast<Rbtree &> (cont_holder);
Hash &my_hash = static_cast<Hash &> (cont_holder);
- //Now insert them in the reverse order
- //in the base hook intrusive list
+ //Now insert them in containers
for(MyClass * it(&values[0]), *itend(&values[NumElements])
; it != itend; ++it){
my_list.push_front(*it);
@@ -217,7 +216,7 @@
my_hash.insert_unique(*it);
}
- //Now test lists
+ //Now test containers
{
List::const_iterator list_it (my_list.cbegin());
Slist::const_iterator slist_it (my_slist.cbegin());
@@ -225,7 +224,7 @@
Hash::const_iterator hash_it (my_hash.cbegin());
MyClass *it_val(&values[NumElements] - 1), *it_rbeg_val(&values[0]-1);
- //Test the objects inserted in the base hook list
+ //Test inserted objects
for(; it_val != it_rbeg_val; --it_val, ++list_it, ++slist_it, ++rbtree_it){
if(&*list_it != &*it_val) return 1;
if(&*slist_it != &*it_val) return 1;
Added: trunk/libs/intrusive/test/generic_assoc_test.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/generic_assoc_test.hpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,328 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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 <vector> //vector
+#include <algorithm> //sort, random_shuffle
+#include <boost/intrusive/detail/config_begin.hpp>
+#include "common_functors.hpp"
+#include <boost/intrusive/options.hpp>
+#include <boost/detail/lightweight_test.hpp>
+#include "test_macros.hpp"
+#include "test_container.hpp"
+
+namespace boost{
+namespace intrusive{
+namespace test{
+
+template<class T>
+struct has_splay
+{
+ static const bool value = false;
+};
+
+template<class T>
+struct has_rebalance
+{
+ static const bool value = false;
+};
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+struct test_generic_assoc
+{
+ typedef typename ValueTraits::value_type value_type;
+ static void test_all(std::vector<value_type>& values);
+ static void test_clone(std::vector<value_type>& values);
+ static void test_insert_erase_burst();
+ static void test_container_from_end(std::vector<value_type>& values);
+ static void test_splay_up(std::vector<value_type>& values);
+ static void test_splay_up(std::vector<value_type>& values, boost::intrusive::detail::true_type);
+ static void test_splay_up(std::vector<value_type>& values, boost::intrusive::detail::false_type);
+ static void test_splay_down(std::vector<value_type>& values);
+ static void test_splay_down(std::vector<value_type>& values, boost::intrusive::detail::true_type);
+ static void test_splay_down(std::vector<value_type>& values, boost::intrusive::detail::false_type);
+ static void test_rebalance(std::vector<value_type>& values);
+ static void test_rebalance(std::vector<value_type>& values, boost::intrusive::detail::true_type);
+ static void test_rebalance(std::vector<value_type>& values, boost::intrusive::detail::false_type);
+};
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_insert_erase_burst()
+{
+ typedef typename ValueTraits::value_type value_type;
+
+ std::vector<value_type> values;
+ const int MaxValues = 100;
+ for(int i = 0; i != MaxValues; ++i){
+ values.push_back(value_type(i));
+ }
+
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ typedef typename assoc_type::iterator iterator;
+
+ //First ordered insertions
+ assoc_type testset (&values[0], &values[0] + values.size());
+ TEST_INTRUSIVE_SEQUENCE_EXPECTED(testset, testset.begin());
+
+ //Ordered erasure
+ iterator it(testset.begin()), itend(testset.end());
+ for(int i = 0; it != itend; ++i){
+ BOOST_TEST(&*it == &values[i]);
+ it = testset.erase(it);
+ }
+
+ BOOST_TEST(testset.empty());
+
+ //Now random insertions
+ std::random_shuffle(values.begin(), values.end());
+ testset.insert(&values[0], &values[0] + values.size());
+ std::sort(values.begin(), values.end());
+ TEST_INTRUSIVE_SEQUENCE_EXPECTED(testset, testset.begin());
+
+ //Random erasure
+ std::random_shuffle(values.begin(), values.end());
+ for(int i = 0; i != MaxValues; ++i){
+ it = testset.erase(testset.iterator_to(values[i]));
+ }
+
+ BOOST_TEST(testset.empty());
+}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_all(std::vector<typename ValueTraits::value_type>& values)
+{
+ test_clone(values);
+ test_container_from_end(values);
+ test_splay_up(values);
+ test_splay_down(values);
+ test_rebalance(values);
+ test_insert_erase_burst();
+}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>
+ ::test_clone(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+
+ assoc_type testset1 (&values[0], &values[0] + values.size());
+ assoc_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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>
+ ::test_container_from_end(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ assoc_type testset (&values[0], &values[0] + values.size());
+ BOOST_TEST (testset == assoc_type::container_from_end_iterator(testset.end()));
+ BOOST_TEST (testset == assoc_type::container_from_end_iterator(testset.cend()));
+}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_up
+(std::vector<typename ValueTraits::value_type>& values, boost::intrusive::detail::true_type)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ typedef typename assoc_type::iterator iterator;
+ typedef std::vector<value_type> orig_set_t;
+ std::size_t num_values;
+ orig_set_t original_testset;
+ {
+ assoc_type testset (values.begin(), values.end());
+ num_values = testset.size();
+ original_testset.insert(original_testset.end(), testset.begin(), testset.end());
+ }
+
+ for(std::size_t i = 0; i != num_values; ++i){
+ assoc_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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_up
+(std::vector<typename ValueTraits::value_type>&, boost::intrusive::detail::false_type)
+{}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_up
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ typedef typename detail::remove_const<assoc_type>::type Type;
+ typedef detail::bool_<has_splay<Type>::value> enabler;
+ test_splay_up(values, enabler());
+}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_down
+(std::vector<typename ValueTraits::value_type>& values, boost::intrusive::detail::true_type)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ typedef typename assoc_type::iterator iterator;
+ typedef std::vector<value_type> orig_set_t;
+ std::size_t num_values;
+ orig_set_t original_testset;
+ {
+ assoc_type testset (values.begin(), values.end());
+ num_values = testset.size();
+ original_testset.insert(original_testset.end(), testset.begin(), testset.end());
+ }
+
+ for(std::size_t i = 0; i != num_values; ++i){
+ assoc_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);
+ }
+ }
+}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_down
+(std::vector<typename ValueTraits::value_type>&, boost::intrusive::detail::false_type)
+{}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_splay_down
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ typedef typename detail::remove_const<assoc_type>::type Type;
+ typedef detail::bool_<has_splay<Type>::value> enabler;
+ test_splay_down(values, enabler());
+}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_rebalance
+(std::vector<typename ValueTraits::value_type>& values, boost::intrusive::detail::true_type)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ typedef std::vector<value_type> orig_set_t;
+ typedef typename orig_set_t::iterator iterator_t;
+ std::size_t num_values;
+ orig_set_t original_testset;
+ {
+ assoc_type testset (values.begin(), values.end());
+ num_values = testset.size();
+ original_testset.insert(original_testset.end(), testset.begin(), testset.end());
+ }
+ {
+ assoc_type testset(values.begin(), values.end());
+ testset.rebalance();
+ iterator_t it = original_testset.begin();
+ TEST_INTRUSIVE_SEQUENCE_EXPECTED(original_testset, testset.begin());
+ }
+
+ {
+ std::size_t numdata;
+ {
+ assoc_type testset(values.begin(), values.end());
+ numdata = testset.size();
+ }
+
+ for(int i = 0; i != (int)numdata; ++i){
+ assoc_type testset(values.begin(), values.end());
+ typename assoc_type::iterator it = testset.begin();
+ for(int j = 0; j != i; ++j) ++it;
+ testset.rebalance_subtree(it);
+ TEST_INTRUSIVE_SEQUENCE_EXPECTED(original_testset, testset.begin());
+ }
+ }
+}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_rebalance
+(std::vector<typename ValueTraits::value_type>&, boost::intrusive::detail::false_type)
+{}
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_assoc<ValueTraits, ContainerDefiner>::test_rebalance
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type assoc_type;
+ typedef typename detail::remove_const<assoc_type>::type Type;
+ typedef detail::bool_<has_rebalance<Type>::value> enabler;
+ test_rebalance(values, enabler());
+}
+
+}}} //namespace boost::intrusive::test
+
+#include <boost/intrusive/detail/config_end.hpp>
Added: trunk/libs/intrusive/test/generic_multiset_test.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/generic_multiset_test.hpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,227 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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 <vector>
+#include <boost/intrusive/detail/config_begin.hpp>
+#include "common_functors.hpp"
+#include <boost/detail/lightweight_test.hpp>
+#include <boost/intrusive/options.hpp>
+#include "test_macros.hpp"
+#include "test_container.hpp"
+#include "generic_assoc_test.hpp"
+
+namespace boost{
+namespace intrusive{
+namespace test{
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+struct test_generic_multiset
+{
+ typedef typename ValueTraits::value_type value_type;
+ static void test_all ();
+ 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_impl();
+};
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_multiset<ValueTraits, ContainerDefiner>::test_all ()
+{
+ typedef typename ValueTraits::value_type value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<value_type> values (6);
+ for (int i = 0; i < 6; ++i)
+ values[i].value_ = random_init[i];
+
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type multiset_type;
+ {
+ 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);
+ test_insert(values);
+ test_swap(values);
+ test_find(values);
+ test_impl();
+ test_generic_assoc<ValueTraits, ContainerDefiner>::test_all(values);
+}
+
+//test case due to an error in tree implementation:
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_multiset<ValueTraits, ContainerDefiner>::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 typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type 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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_multiset<ValueTraits, ContainerDefiner>::test_sort(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type 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 typename ContainerDefiner
+ <value_type
+ , compare<even_odd>
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type 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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_multiset<ValueTraits, ContainerDefiner>::test_insert(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ >::type 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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_multiset<ValueTraits, ContainerDefiner>::test_swap(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ >::type multiset_type;
+ multiset_type testset1 (&values[0], &values[0] + 2);
+ multiset_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.begin() == &values[3]);
+}
+
+//test: find, equal_range (lower_bound, upper_bound):
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_multiset<ValueTraits, ContainerDefiner>::test_find(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ >::type 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());
+}
+
+}}} //namespace boost::intrusive::test
+
+#include <boost/intrusive/detail/config_end.hpp>
Added: trunk/libs/intrusive/test/generic_set_test.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/generic_set_test.hpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,225 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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 <vector>
+#include <boost/intrusive/detail/config_begin.hpp>
+#include "common_functors.hpp"
+#include <boost/detail/lightweight_test.hpp>
+#include <boost/intrusive/options.hpp>
+#include "test_macros.hpp"
+#include "test_container.hpp"
+#include "generic_assoc_test.hpp"
+
+namespace boost{
+namespace intrusive{
+namespace test{
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+struct test_generic_set
+{
+ typedef typename ValueTraits::value_type value_type;
+ static void test_all();
+ 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_impl();
+};
+
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_set<ValueTraits, ContainerDefiner>::test_all()
+{
+ typedef typename ValueTraits::value_type value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<value_type> values (6);
+ for (int i = 0; i < 6; ++i)
+ values[i].value_ = random_init[i];
+
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type set_type;
+ {
+ 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_impl();
+ test_generic_assoc<ValueTraits, ContainerDefiner>::test_all(values);
+}
+
+//test case due to an error in tree implementation:
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_set<ValueTraits, ContainerDefiner>::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 typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type set_type;
+ 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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_set<ValueTraits, ContainerDefiner>::test_sort(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type set_type;
+ 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 typename ContainerDefiner
+ < value_type
+ , compare<even_odd>
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type 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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_set<ValueTraits, ContainerDefiner>::test_insert(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type set_type;
+ set_type testset;
+ testset.insert(&values[0] + 2, &values[0] + 5);
+
+ const set_type& const_testset = testset;
+ { int init_values [] = { 1, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, const_testset.begin() ); }
+
+ typename 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 = 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, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_set<ValueTraits, ContainerDefiner>::test_swap(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type set_type;
+ set_type testset1 (&values[0], &values[0] + 2);
+ 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]);
+}
+
+//test: find, equal_range (lower_bound, upper_bound):
+template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
+void test_generic_set<ValueTraits, ContainerDefiner>::test_find(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef typename ContainerDefiner
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ >::type set_type;
+ set_type testset (values.begin(), values.end());
+ typedef typename 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());
+}
+
+}}} //namespace boost::intrusive::test
+
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/itestvalue.hpp
==============================================================================
--- trunk/libs/intrusive/test/itestvalue.hpp (original)
+++ trunk/libs/intrusive/test/itestvalue.hpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -20,6 +20,7 @@
#include <boost/intrusive/unordered_set_hook.hpp>
#include <boost/intrusive/splay_set_hook.hpp>
#include <boost/intrusive/avl_set_hook.hpp>
+#include <boost/intrusive/bs_set_hook.hpp>
#include <boost/intrusive/options.hpp>
#include <boost/functional/hash.hpp>
#include "smart_ptr.hpp"
@@ -62,6 +63,14 @@
{ typedef splay_set_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
template<class VoidPointer>
+struct bs_set_base_hook_type
+{ typedef bs_set_base_hook<void_pointer<VoidPointer> > type; };
+
+template<class VoidPointer>
+struct bs_set_member_hook_type
+{ typedef bs_set_member_hook<void_pointer<VoidPointer> > type; };
+
+template<class VoidPointer>
struct avl_set_base_hook_type
{ typedef avl_set_base_hook<void_pointer<VoidPointer> > type; };
@@ -115,7 +124,11 @@
template<class VoidPointer>
struct uset_auto_base_hook_type
-{ typedef unordered_set_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag> > type; };
+{
+ typedef unordered_set_base_hook
+ < link_mode<auto_unlink>, void_pointer<VoidPointer>
+ , tag<my_tag>, store_hash<true> > type;
+};
template<class VoidPointer>
struct uset_member_hook_type
@@ -123,7 +136,11 @@
template<class VoidPointer>
struct uset_auto_member_hook_type
-{ typedef unordered_set_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
+{
+ typedef unordered_set_member_hook
+ < link_mode<auto_unlink>, void_pointer<VoidPointer>
+ , store_hash<true> > type;
+};
template<class VoidPointer, bool ConstantTimeSize>
struct testvalue
@@ -131,6 +148,7 @@
, set_auto_base_hook_type<VoidPointer>::type
, splay_set_base_hook_type<VoidPointer>::type
, splay_set_auto_base_hook_type<VoidPointer>::type
+ , bs_set_base_hook_type<VoidPointer>::type
, avl_set_base_hook_type<VoidPointer>::type
, avl_set_auto_base_hook_type<VoidPointer>::type
, list_base_hook_type<VoidPointer>::type
@@ -150,6 +168,9 @@
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 bs_set_base_hook_type<VoidPointer>::type bs_set_base_hook_t;
+ typedef typename bs_set_member_hook_type<VoidPointer>::type bs_set_member_hook_t;
+
typedef typename avl_set_auto_base_hook_type<VoidPointer>::type avl_set_auto_base_hook_t;
typedef typename avl_set_base_hook_type<VoidPointer>::type avl_set_base_hook_t;
typedef typename avl_set_auto_member_hook_type<VoidPointer>::type avl_set_auto_member_hook_t;
@@ -178,6 +199,9 @@
splay_set_member_hook_t splay_set_node_;
splay_set_auto_member_hook_t splay_set_auto_node_;
+ //ScapegoatSet members
+ bs_set_member_hook_t sg_set_node_;
+
//AvlSet members
avl_set_member_hook_t avl_set_node_;
avl_set_auto_member_hook_t avl_set_auto_node_;
@@ -224,6 +248,9 @@
this->splay_set_node_ = src.splay_set_node_;
this->splay_set_auto_node_ = src.splay_set_auto_node_;
+ bs_set_base_hook_t::operator=(src);
+ this->sg_set_node_ = src.sg_set_node_;
+
avl_set_base_hook_t::operator=(src);
avl_set_auto_base_hook_t::operator=(src);
this->avl_set_node_ = src.avl_set_node_;
@@ -262,6 +289,10 @@
splay_set_node_.swap_nodes(other.splay_set_node_);
splay_set_auto_node_.swap_nodes(other.splay_set_auto_node_);
+ //ScapeoatSet
+ bs_set_base_hook_t::swap_nodes(other);
+ sg_set_node_.swap_nodes(other.sg_set_node_);
+
//AvlSet
avl_set_base_hook_t::swap_nodes(other);
avl_set_auto_base_hook_t::swap_nodes(other);
Modified: trunk/libs/intrusive/test/make_functions_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/make_functions_test.cpp (original)
+++ trunk/libs/intrusive/test/make_functions_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -68,8 +68,7 @@
Set my_set;
USet my_uset(USet::bucket_traits(buckets, 100));
- //Now insert them in the reverse order
- //in the base hook intrusive list
+ //Now insert them in containers
for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
my_list.push_front(*it);
my_slist.push_front(*it);
Modified: trunk/libs/intrusive/test/multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/multiset_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -10,278 +10,51 @@
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////
-
#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/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 "generic_multiset_test.hpp"
-using namespace boost::intrusive;
-template<class ValueTraits>
-struct test_multiset
-{
- 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_impl();
- static void test_clone(std::vector<value_type>& values);
- static void test_container_from_end(std::vector<value_type>& values);
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::multiset
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
};
-template<class ValueTraits>
-void test_multiset<ValueTraits>::test_all (std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef multiset
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > multiset_type;
- {
- 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);
- test_insert(values);
- test_swap(values);
- test_find(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_multiset<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 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_multiset<ValueTraits>::test_sort(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef 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 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_multiset<ValueTraits>::test_insert(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef 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_multiset<ValueTraits>::test_swap(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef 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);
- 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]);
-}
-
-//test: find, equal_range (lower_bound, upper_bound):
-template<class ValueTraits>
-void test_multiset<ValueTraits>::test_find(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef 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_multiset<ValueTraits>
- ::test_clone(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef 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_multiset<ValueTraits>
- ::test_container_from_end(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef 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()()
{
+ using namespace boost::intrusive;
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_multiset < typename detail::get_base_value_traits
+ test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
, typename value_type::set_base_hook_t
>::type
- >::test_all(data);
- test_multiset < typename detail::get_member_value_traits
+ , GetContainer
+ >::test_all();
+ test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::set_member_hook_t
, &value_type::set_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
return 0;
}
};
@@ -292,78 +65,53 @@
public:
int operator()()
{
+ using namespace boost::intrusive;
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_multiset < typename detail::get_base_value_traits
+ test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
, typename value_type::set_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_multiset < typename detail::get_member_value_traits
+ test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::set_member_hook_t
, &value_type::set_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_multiset < typename detail::get_base_value_traits
+ test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
, typename value_type::set_auto_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_multiset < typename detail::get_member_value_traits
+ test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::set_auto_member_hook_t
, &value_type::set_auto_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
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<boost::intrusive::smart_ptr<void>, false>()();
test_main_template<void*, true>()();
- test_main_template<smart_ptr<void>, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
return boost::report_errors();
}
+
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/set_test.cpp (original)
+++ trunk/libs/intrusive/test/set_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -12,272 +12,49 @@
/////////////////////////////////////////////////////////////////////////////
#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/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 "generic_set_test.hpp"
-using namespace boost::intrusive;
-
-template<class ValueTraits>
-struct test_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_impl();
- static void test_clone(std::vector<value_type>& values);
- static void test_container_from_end(std::vector<value_type>& values);
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::set
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
};
-template<class ValueTraits>
-void test_set<ValueTraits>::test_all(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
- {
- 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_impl();
- test_clone(values);
- test_container_from_end(values);
-}
-
-//test case due to an error in tree implementation:
-template<class ValueTraits>
-void test_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 set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
- 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_set<ValueTraits>::test_sort(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
- 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 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_set<ValueTraits>::test_insert(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
- set_type testset;
- testset.insert(&values[0] + 2, &values[0] + 5);
-
- const set_type& const_testset = testset;
- { int init_values [] = { 1, 4, 5 };
- TEST_INTRUSIVE_SEQUENCE( init_values, const_testset.begin() ); }
-
- typename 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 = 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_set<ValueTraits>::test_swap(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
- set_type testset1 (&values[0], &values[0] + 2);
- 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]);
-}
-
-//test: find, equal_range (lower_bound, upper_bound):
-template<class ValueTraits>
-void test_set<ValueTraits>::test_find(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
- set_type testset (values.begin(), values.end());
- typedef typename 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_set<ValueTraits>
- ::test_clone(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
-
- set_type testset1 (&values[0], &values[0] + values.size());
- 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_set<ValueTraits>
- ::test_container_from_end(std::vector<typename ValueTraits::value_type>& values)
-{
- typedef typename ValueTraits::value_type value_type;
- typedef set
- < value_type
- , value_traits<ValueTraits>
- , constant_time_size<value_type::constant_time_size>
- > set_type;
- set_type testset (&values[0], &values[0] + values.size());
- BOOST_TEST (testset == set_type::container_from_end_iterator(testset.end()));
- BOOST_TEST (testset == set_type::container_from_end_iterator(testset.cend()));
-}
-
template<class VoidPointer, bool constant_time_size>
class test_main_template
{
public:
int operator()()
{
+ using namespace boost::intrusive;
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_set < typename detail::get_base_value_traits
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::set_base_hook_t
>::type
- >::test_all(data);
- test_set < typename detail::get_member_value_traits
+ , GetContainer
+ >::test_all();
+ test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::set_member_hook_t
, &value_type::set_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
return 0;
}
};
@@ -288,41 +65,42 @@
public:
int operator()()
{
+ using namespace boost::intrusive;
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_set < typename detail::get_base_value_traits
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::set_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_set < typename detail::get_member_value_traits
+ test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::set_member_hook_t
, &value_type::set_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_set < typename detail::get_base_value_traits
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::set_auto_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_set < typename detail::get_member_value_traits
+ test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
, typename value_type::set_auto_member_hook_t
, &value_type::set_auto_node_
>
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
return 0;
}
@@ -332,9 +110,9 @@
{
test_main_template<void*, false>()();
- test_main_template<smart_ptr<void>, false>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, false>()();
test_main_template<void*, true>()();
- test_main_template<smart_ptr<void>, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
return boost::report_errors();
}
#include <boost/intrusive/detail/config_end.hpp>
Added: trunk/libs/intrusive/test/sg_multiset_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/sg_multiset_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,108 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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/sg_set.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "generic_multiset_test.hpp"
+
+namespace boost { namespace intrusive { namespace test {
+
+template<class T, class O1, class O2, class O3, class O4>
+struct has_rebalance<boost::intrusive::sg_multiset<T, O1, O2, O3, O4> >
+{
+ static const bool value = true;
+};
+
+}}}
+
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::sg_multiset
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
+};
+
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainerFixedAlpha
+{
+ typedef boost::intrusive::sg_multiset
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ , boost::intrusive::floating_point<false>
+ > type;
+};
+
+template<class VoidPointer>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ using namespace boost::intrusive;
+ typedef testvalue<VoidPointer, true> value_type;
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::bs_set_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::bs_set_member_hook_t
+ , &value_type::sg_set_node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::bs_set_base_hook_t
+ >::type
+ , GetContainerFixedAlpha
+ >::test_all();
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::bs_set_member_hook_t
+ , &value_type::sg_set_node_
+ >
+ >::type
+ , GetContainerFixedAlpha
+ >::test_all();
+ return 0;
+ }
+};
+
+int main( int, char* [] )
+{
+ test_main_template<void*>()();
+ test_main_template<boost::intrusive::smart_ptr<void> >()();
+ return boost::report_errors();
+}
Added: trunk/libs/intrusive/test/sg_set_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/sg_set_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -0,0 +1,109 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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/sg_set.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "generic_set_test.hpp"
+
+namespace boost { namespace intrusive { namespace test {
+
+template<class T, class O1, class O2, class O3, class O4>
+struct has_rebalance<boost::intrusive::sg_set<T, O1, O2, O3, O4> >
+{
+ static const bool value = true;
+};
+
+}}}
+
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::sg_set
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
+};
+
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainerFixedAlpha
+{
+ typedef boost::intrusive::sg_set
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ , boost::intrusive::floating_point<false>
+ > type;
+};
+
+template<class VoidPointer>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ using namespace boost::intrusive;
+ typedef testvalue<VoidPointer, true> value_type;
+
+ test::test_generic_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::bs_set_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+ test::test_generic_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::bs_set_member_hook_t
+ , &value_type::sg_set_node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::bs_set_base_hook_t
+ >::type
+ , GetContainerFixedAlpha
+ >::test_all();
+ test::test_generic_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename value_type::bs_set_member_hook_t
+ , &value_type::sg_set_node_
+ >
+ >::type
+ , GetContainerFixedAlpha
+ >::test_all();
+ return 0;
+ }
+};
+
+int main( int, char* [] )
+{
+ test_main_template<void*>()();
+ test_main_template<boost::intrusive::smart_ptr<void> >()();
+ return boost::report_errors();
+}
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/splay_multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/splay_multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/splay_multiset_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -10,18 +10,12 @@
// 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>
+#include "generic_multiset_test.hpp"
namespace boost { namespace intrusive { namespace test {
@@ -31,327 +25,34 @@
static const bool value = false;
};
-}}}
-
-using namespace boost::intrusive;
-template<class ValueTraits>
-struct test_splay_multiset
+template<class T, class O1, class O2, class O3, class O4>
+struct has_splay<boost::intrusive::splay_multiset<T, O1, O2, O3, O4> >
{
- 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);
+ static const bool value = true;
};
-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)
+template<class T, class O1, class O2, class O3, class O4>
+struct has_rebalance<boost::intrusive::splay_multiset<T, O1, O2, O3, O4> >
{
- 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);
- }
- }
-}
+ static const bool value = true;
+};
-//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 ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::splay_multiset
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
+};
template<class VoidPointer, bool constant_time_size>
class test_main_template
@@ -359,27 +60,24 @@
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));
- }
+ using namespace boost::intrusive;
+ typedef testvalue<VoidPointer, constant_time_size> value_type;
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+ test::test_generic_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
+ , GetContainer
+ >::test_all();
return 0;
}
};
@@ -390,80 +88,51 @@
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));
- }
+ using namespace boost::intrusive;
+ typedef testvalue<VoidPointer, false> value_type;
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_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
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::splay_set_auto_base_hook_t
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_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
+ , GetContainer
+ >::test_all();
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<boost::intrusive::smart_ptr<void>, false>()();
test_main_template<void*, true>()();
- test_main_template<smart_ptr<void>, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
return boost::report_errors();
}
Modified: trunk/libs/intrusive/test/splay_set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/splay_set_test.cpp (original)
+++ trunk/libs/intrusive/test/splay_set_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -11,15 +11,9 @@
/////////////////////////////////////////////////////////////////////////////
#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>
+#include "generic_set_test.hpp"
namespace boost { namespace intrusive { namespace test {
@@ -29,315 +23,34 @@
static const bool value = false;
};
-}}}
-
-using namespace boost::intrusive;
-
-template<class ValueTraits>
-struct test_splay_set
+template<class T, class O1, class O2, class O3, class O4>
+struct has_splay<boost::intrusive::splay_set<T, O1, O2, O3, O4> >
{
- 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);
+ static const bool value = true;
};
-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)
+template<class T, class O1, class O2, class O3, class O4>
+struct has_rebalance<boost::intrusive::splay_set<T, O1, O2, O3, O4> >
{
- 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);
- }
- }
-}
+ static const bool value = true;
+};
-//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 ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::splay_set
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
+};
template<class VoidPointer, bool constant_time_size>
class test_main_template
@@ -345,25 +58,24 @@
public:
int operator()()
{
+ using namespace boost::intrusive;
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
+ test::test_generic_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
+ , GetContainer
+ >::test_all();
+ test::test_generic_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);
+ , GetContainer
+ >::test_all();
return 0;
}
};
@@ -374,41 +86,42 @@
public:
int operator()()
{
+ using namespace boost::intrusive;
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
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::splay_set_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_splay_set < typename detail::get_member_value_traits
+ test::test_generic_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);
+ , GetContainer
+ >::test_all();
- test_splay_set < typename detail::get_base_value_traits
+ test::test_generic_set < typename detail::get_base_value_traits
< value_type
, typename value_type::splay_set_auto_base_hook_t
>::type
- >::test_all(data);
+ , GetContainer
+ >::test_all();
- test_splay_set < typename detail::get_member_value_traits
+ test::test_generic_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);
+ , GetContainer
+ >::test_all();
return 0;
}
@@ -417,9 +130,9 @@
int main( int, char* [] )
{
test_main_template<void*, false>()();
- test_main_template<smart_ptr<void>, false>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, false>()();
test_main_template<void*, true>()();
- test_main_template<smart_ptr<void>, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
return boost::report_errors();
}
#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/stateful_value_traits_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/stateful_value_traits_test.cpp (original)
+++ trunk/libs/intrusive/test/stateful_value_traits_test.cpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -117,8 +117,7 @@
, slist_traits(values, uset_hook_array)
);
- //Now insert them in the reverse order
- //in the base hook intrusive list
+ //Now insert them in containers
for(MyClass * it(&values[0]), *itend(&values[NumElements])
; it != itend
; ++it){
Modified: trunk/libs/intrusive/test/test_container.hpp
==============================================================================
--- trunk/libs/intrusive/test/test_container.hpp (original)
+++ trunk/libs/intrusive/test/test_container.hpp 2007-11-18 05:44:56 EST (Sun, 18 Nov 2007)
@@ -185,7 +185,7 @@
}
template< class Container, class Data >
-void test_associative_container_invariants(Container & c, Data & d, boost::intrusive::detail::false_type)
+void test_associative_container_invariants(Container &, Data &, boost::intrusive::detail::false_type)
{}
template< class Container, class Data >
@@ -245,7 +245,7 @@
}
template< class Container, class Data >
-void test_unordered_associative_container_invariants(Container & c, Data & d, boost::intrusive::detail::false_type)
+void test_unordered_associative_container_invariants(Container &, Data &, boost::intrusive::detail::false_type)
{}
template< class Container, class Data >