← Back to branch summary

~ubuntu-branches/debian/sid/boost1.49/sid

« back to all changes in this revision

Viewing changes to libs/unordered/test/unordered/erase_tests.cpp

  • Committer: Package Import Robot
  • Author(s): Steve M. Robbins
  • Date: 2012-02-26 00:31:44 UTC
  • Revision ID: package-import@ubuntu.com-20120226003144-eaytp12cbf6ubpms
Tags: upstream-1.49.0
Import upstream version 1.49.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
libs/unordered/test/unordered/erase_tests.cpp
 
1
 
 
2
// Copyright 2006-2009 Daniel James.
 
3
// Distributed under the Boost Software License, Version 1.0. (See accompanying
 
4
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 
5
 
 
6
#include "../helpers/prefix.hpp"
 
7
 
 
8
#include <boost/unordered_set.hpp>
 
9
#include <boost/unordered_map.hpp>
 
10
#include "../helpers/test.hpp"
 
11
#include <boost/next_prior.hpp>
 
12
#include "../objects/test.hpp"
 
13
#include "../helpers/random_values.hpp"
 
14
#include "../helpers/tracker.hpp"
 
15
#include "../helpers/equivalent.hpp"
 
16
#include "../helpers/helpers.hpp"
 
17
 
 
18
#include <iostream>
 
19
 
 
20
namespace erase_tests
 
21
{
 
22
 
 
23
test::seed_t seed(85638);
 
24
 
 
25
template <class Container>
 
26
void erase_tests1(Container*,
 
27
    test::random_generator generator = test::default_generator)
 
28
{
 
29
    std::cerr<<"Erase by key.\n";
 
30
    {
 
31
        test::check_instances check_;
 
32
 
 
33
        test::random_values<Container> v(1000, generator);
 
34
        Container x(v.begin(), v.end());
 
35
        for(BOOST_DEDUCED_TYPENAME test::random_values<Container>::iterator
 
36
            it = v.begin(); it != v.end(); ++it)
 
37
        {
 
38
            std::size_t count = x.count(test::get_key<Container>(*it));
 
39
            std::size_t old_size = x.size();
 
40
            BOOST_TEST(count == x.erase(test::get_key<Container>(*it)));
 
41
            BOOST_TEST(x.size() == old_size - count);
 
42
            BOOST_TEST(x.count(test::get_key<Container>(*it)) == 0);
 
43
            BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end());
 
44
        }
 
45
    }
 
46
 
 
47
    std::cerr<<"erase(begin()).\n";
 
48
    {
 
49
        test::check_instances check_;
 
50
 
 
51
        test::random_values<Container> v(1000, generator);
 
52
        Container x(v.begin(), v.end());
 
53
        std::size_t size = x.size();
 
54
        while(size > 0 && !x.empty())
 
55
        {
 
56
            BOOST_DEDUCED_TYPENAME Container::key_type
 
57
                key = test::get_key<Container>(*x.begin());
 
58
            std::size_t count = x.count(key);
 
59
            BOOST_DEDUCED_TYPENAME Container::iterator
 
60
                pos = x.erase(x.begin());
 
61
            --size;
 
62
            BOOST_TEST(pos == x.begin());
 
63
            BOOST_TEST(x.count(key) == count - 1);
 
64
            BOOST_TEST(x.size() == size);
 
65
        }
 
66
        BOOST_TEST(x.empty());
 
67
    }
 
68
 
 
69
    std::cerr<<"erase(random position).\n";
 
70
    {
 
71
        test::check_instances check_;
 
72
 
 
73
        test::random_values<Container> v(1000, generator);
 
74
        Container x(v.begin(), v.end());
 
75
        std::size_t size = x.size();
 
76
        while(size > 0 && !x.empty())
 
77
        {
 
78
            using namespace std;
 
79
            int index = rand() % (int) x.size();
 
80
            BOOST_DEDUCED_TYPENAME Container::const_iterator prev, pos, next;
 
81
            if(index == 0) {
 
82
                prev = pos = x.begin();
 
83
            }
 
84
            else {
 
85
                prev = boost::next(x.begin(), index - 1);
 
86
                pos = boost::next(prev);
 
87
            }
 
88
            next = boost::next(pos);
 
89
            BOOST_DEDUCED_TYPENAME Container::key_type
 
90
                key = test::get_key<Container>(*pos);
 
91
            std::size_t count = x.count(key);
 
92
            BOOST_TEST(next == x.erase(pos));
 
93
            --size;
 
94
            if(size > 0)
 
95
                BOOST_TEST(index == 0 ? next == x.begin() :
 
96
                        next == boost::next(prev));
 
97
            BOOST_TEST(x.count(key) == count - 1);
 
98
            BOOST_TEST(x.size() == size);
 
99
        }
 
100
        BOOST_TEST(x.empty());
 
101
    }
 
102
 
 
103
    std::cerr<<"erase(ranges).\n";
 
104
    {
 
105
        test::check_instances check_;
 
106
 
 
107
        test::random_values<Container> v(500, generator);
 
108
        Container x(v.begin(), v.end());
 
109
 
 
110
        std::size_t size = x.size();
 
111
 
 
112
        // I'm actually stretching it a little here, as the standard says it
 
113
        // returns 'the iterator immediately following the erase elements'
 
114
        // and if nothing is erased, then there's nothing to follow. But I
 
115
        // think this is the only sensible option...
 
116
        BOOST_TEST(x.erase(x.end(), x.end()) == x.end());
 
117
        BOOST_TEST(x.erase(x.begin(), x.begin()) == x.begin());
 
118
        BOOST_TEST(x.size() == size);
 
119
 
 
120
        BOOST_TEST(x.erase(x.begin(), x.end()) == x.end());
 
121
        BOOST_TEST(x.empty());
 
122
        BOOST_TEST(x.begin() == x.end());
 
123
 
 
124
        BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin());
 
125
    }
 
126
 
 
127
    std::cerr<<"quick_erase(begin()).\n";
 
128
    {
 
129
        test::check_instances check_;
 
130
 
 
131
        test::random_values<Container> v(1000, generator);
 
132
        Container x(v.begin(), v.end());
 
133
        std::size_t size = x.size();
 
134
        while(size > 0 && !x.empty())
 
135
        {
 
136
            BOOST_DEDUCED_TYPENAME Container::key_type
 
137
                key = test::get_key<Container>(*x.begin());
 
138
            std::size_t count = x.count(key);
 
139
            x.quick_erase(x.begin());
 
140
            --size;
 
141
            BOOST_TEST(x.count(key) == count - 1);
 
142
            BOOST_TEST(x.size() == size);
 
143
        }
 
144
        BOOST_TEST(x.empty());
 
145
    }
 
146
 
 
147
    std::cerr<<"quick_erase(random position).\n";
 
148
    {
 
149
        test::check_instances check_;
 
150
 
 
151
        test::random_values<Container> v(1000, generator);
 
152
        Container x(v.begin(), v.end());
 
153
        std::size_t size = x.size();
 
154
        while(size > 0 && !x.empty())
 
155
        {
 
156
            using namespace std;
 
157
            int index = rand() % (int) x.size();
 
158
            BOOST_DEDUCED_TYPENAME Container::const_iterator prev, pos, next;
 
159
            if(index == 0) {
 
160
                prev = pos = x.begin();
 
161
            }
 
162
            else {
 
163
                prev = boost::next(x.begin(), index - 1);
 
164
                pos = boost::next(prev);
 
165
            }
 
166
            next = boost::next(pos);
 
167
            BOOST_DEDUCED_TYPENAME Container::key_type
 
168
                key = test::get_key<Container>(*pos);
 
169
            std::size_t count = x.count(key);
 
170
            x.quick_erase(pos);
 
171
            --size;
 
172
            if(size > 0)
 
173
                BOOST_TEST(index == 0 ? next == x.begin() :
 
174
                        next == boost::next(prev));
 
175
            BOOST_TEST(x.count(key) == count - 1);
 
176
            BOOST_TEST(x.size() == size);
 
177
        }
 
178
        BOOST_TEST(x.empty());
 
179
    }
 
180
 
 
181
 
 
182
    std::cerr<<"clear().\n";
 
183
    {
 
184
        test::check_instances check_;
 
185
 
 
186
        test::random_values<Container> v(500, generator);
 
187
        Container x(v.begin(), v.end());
 
188
        x.clear();
 
189
        BOOST_TEST(x.empty());
 
190
        BOOST_TEST(x.begin() == x.end());
 
191
    }
 
192
 
 
193
    std::cerr<<"\n";
 
194
}
 
195
 
 
196
boost::unordered_set<test::object,
 
197
    test::hash, test::equal_to,
 
198
    test::allocator<test::object> >* test_set;
 
199
boost::unordered_multiset<test::object,
 
200
    test::hash, test::equal_to,
 
201
    test::allocator<test::object> >* test_multiset;
 
202
boost::unordered_map<test::object, test::object,
 
203
    test::hash, test::equal_to,
 
204
    test::allocator<test::object> >* test_map;
 
205
boost::unordered_multimap<test::object, test::object,
 
206
    test::hash, test::equal_to,
 
207
    test::allocator<test::object> >* test_multimap;
 
208
 
 
209
using test::default_generator;
 
210
using test::generate_collisions;
 
211
 
 
212
UNORDERED_TEST(erase_tests1,
 
213
    ((test_set)(test_multiset)(test_map)(test_multimap))
 
214
    ((default_generator)(generate_collisions))
 
215
)
 
216
 
 
217
}
 
218
 
 
219
RUN_TESTS()