/elec/propeller-clock

To get this branch, use:
bzr branch http://bzr.ed.am/elec/propeller-clock

« back to all changes in this revision

Viewing changes to src/utility/set

  • Committer: Dan
  • Date: 2011-11-02 22:15:18 UTC
  • Revision ID: dan@waxworlds.org-20111102221518-b5j2m5l2pd71f4t1
Added Test whilst testing

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
/*      Copyright (C) 2004 Garrett A. Kajmowicz
2
 
        This file is part of the uClibc++ Library.
3
 
 
4
 
        This library is free software; you can redistribute it and/or
5
 
        modify it under the terms of the GNU Lesser General Public
6
 
        License as published by the Free Software Foundation; either
7
 
        version 2.1 of the License, or (at your option) any later version.
8
 
 
9
 
        This library is distributed in the hope that it will be useful,
10
 
        but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12
 
        Lesser General Public License for more details.
13
 
 
14
 
        You should have received a copy of the GNU Lesser General Public
15
 
        License along with this library; if not, write to the Free Software
16
 
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
 
*/
18
 
 
19
 
 
20
 
 
21
 
#include<memory>
22
 
#include<utility.h>
23
 
#include<iterator>
24
 
#include <deque>
25
 
#include<functional>
26
 
#include <associative_base>
27
 
 
28
 
#ifndef __STD_HEADER_SET
29
 
#define __STD_HEADER_SET
30
 
 
31
 
#pragma GCC visibility push(default)
32
 
 
33
 
namespace std{
34
 
 
35
 
 
36
 
template<class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;
37
 
template<class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class multiset;
38
 
 
39
 
 
40
 
/* This is the implementation for the set container.  As noted above, it deviates
41
 
 * from ISO spec by deriving from a base class in order to reduce code redundancy.
42
 
 * More code could be reduced by convirting to virtual functions (thus allowing
43
 
 * much of the erase and insert code to be duplicated), but that would deviate from
44
 
 * the specifications too much to be worth the risk.
45
 
 */
46
 
 
47
 
 
48
 
//Implementation of set
49
 
 
50
 
 
51
 
template<class Key, class Compare, class Allocator> class _UCXXEXPORT set
52
 
        : public __single_associative<Key, Key, Compare, Allocator>
53
 
{
54
 
                //Default value of allocator does not meet C++ standard specs, but it works for this library
55
 
                //Deal with it
56
 
public:
57
 
 
58
 
        typedef __single_associative<Key, Key, Compare, Allocator>      base;
59
 
        typedef typename base::key_type                                 key_type;
60
 
        typedef typename base::value_type                               value_type;
61
 
        typedef typename base::key_compare                              key_compare;
62
 
        typedef typename base::allocator_type                           allocator_type;
63
 
        typedef typename base::reference                                reference;
64
 
        typedef typename base::const_reference                          const_reference;
65
 
        typedef typename base::iterator                                 iterator;
66
 
        typedef typename base::const_iterator                           const_iterator;
67
 
        typedef typename base::size_type                                size_type;
68
 
        typedef typename base::difference_type                          difference_type;
69
 
        typedef typename base::pointer                                  pointer;
70
 
        typedef typename base::const_pointer                            const_pointer;
71
 
        typedef typename base::reverse_iterator                         reverse_iterator;
72
 
        typedef typename base::const_reverse_iterator                   const_reverse_iterator;
73
 
 
74
 
//      using base::value_compare;
75
 
 
76
 
        static const key_type v_t_k(const value_type v){
77
 
                return v;
78
 
        }
79
 
 
80
 
        explicit set(const Compare& comp = Compare(), const Allocator& al = Allocator())
81
 
                : base(comp, al, v_t_k) {  }
82
 
 
83
 
        template <class InputIterator> set(InputIterator first, InputIterator last,
84
 
                const Compare& comp = Compare(), const Allocator& al = Allocator())
85
 
                : base(first, last, comp, al, v_t_k) {  }
86
 
 
87
 
        set(const set<Key, Compare,Allocator>& x) : base(x) {  }
88
 
        ~set() {  }
89
 
 
90
 
        using base::operator=;
91
 
        using base::operator==;
92
 
        using base::operator!=;
93
 
 
94
 
        using base::insert;
95
 
        using base::erase;
96
 
 
97
 
        using base::begin;
98
 
        using base::end;
99
 
        using base::rbegin;
100
 
        using base::rend;
101
 
 
102
 
        using base::empty;
103
 
        using base::size;
104
 
        using base::max_size;
105
 
 
106
 
 
107
 
        using base::find;
108
 
        using base::count;
109
 
        using base::lower_bound;
110
 
        using base::upper_bound;
111
 
        using base::equal_range;
112
 
 
113
 
protected:
114
 
 
115
 
};
116
 
 
117
 
 
118
 
//Implementation of multiset
119
 
 
120
 
 
121
 
template<class Key, class Compare, class Allocator> class _UCXXEXPORT multiset
122
 
        : public __multi_associative<Key, Key, Compare, Allocator>
123
 
{
124
 
                //Default value of allocator does not meet C++ standard specs, but it works for this library
125
 
                //Deal with it
126
 
public:
127
 
 
128
 
        typedef __multi_associative<Key, Key, Compare, Allocator>       base;
129
 
        typedef typename base::key_type                                 key_type;
130
 
        typedef typename base::value_type                               value_type;
131
 
        typedef typename base::key_compare                              key_compare;
132
 
        typedef typename base::allocator_type                           allocator_type;
133
 
        typedef typename base::reference                                reference;
134
 
        typedef typename base::const_reference                          const_reference;
135
 
        typedef typename base::iterator                                 iterator;
136
 
        typedef typename base::const_iterator                           const_iterator;
137
 
        typedef typename base::size_type                                size_type;
138
 
        typedef typename base::difference_type                          difference_type;
139
 
        typedef typename base::pointer                                  pointer;
140
 
        typedef typename base::const_pointer                            const_pointer;
141
 
        typedef typename base::reverse_iterator                         reverse_iterator;
142
 
        typedef typename base::const_reverse_iterator                   const_reverse_iterator;
143
 
 
144
 
        static const key_type v_t_k(const value_type v){
145
 
                return v;
146
 
        }
147
 
 
148
 
        explicit multiset(const Compare& comp = Compare(), const Allocator& al = Allocator())
149
 
                : base(comp, al, v_t_k) {  }
150
 
 
151
 
        template <class InputIterator> multiset(InputIterator first, InputIterator last,
152
 
                const Compare& comp = Compare(), const Allocator& al = Allocator())
153
 
                : base(first, last, comp, al, v_t_k) {  }
154
 
 
155
 
 
156
 
        multiset(const multiset<Key, Compare, Allocator>& x) : base(x) {  }
157
 
        ~multiset() {  }
158
 
 
159
 
        using base::operator=;
160
 
        using base::operator==;
161
 
        using base::operator!=;
162
 
 
163
 
        using base::insert;
164
 
        using base::erase;
165
 
 
166
 
        using base::begin;
167
 
        using base::end;
168
 
        using base::rbegin;
169
 
        using base::rend;
170
 
 
171
 
        using base::empty;
172
 
        using base::size;
173
 
        using base::max_size;
174
 
 
175
 
        using base::find;
176
 
        using base::count;
177
 
        using base::lower_bound;
178
 
        using base::upper_bound;
179
 
        using base::equal_range;
180
 
 
181
 
 
182
 
protected:
183
 
 
184
 
};
185
 
 
186
 
 
187
 
/* Non-member functions.  These are at the end because they are not associated with any
188
 
   particular class.  These will be implemented as I figure out exactly what all of 
189
 
   them are supposed to do, and I have time.
190
 
 */
191
 
 
192
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator< 
193
 
                (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
194
 
        {
195
 
                typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
196
 
                typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
197
 
                typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
198
 
                typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
199
 
 
200
 
                while(first1 != last1 && first2 != last2){
201
 
                        if( *first1 < *first2 ){
202
 
                                return true;
203
 
                        }
204
 
                        if( *first2 < *first1 ){
205
 
                                return false;
206
 
                        }
207
 
                        ++first1;
208
 
                        ++first2;
209
 
                }
210
 
                return first1==last1 && first2 != last2;
211
 
        }
212
 
 
213
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>
214
 
                (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
215
 
        {
216
 
                typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
217
 
                typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
218
 
                typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
219
 
                typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
220
 
 
221
 
                while(first1 != last1 && first2 != last2){
222
 
                        if( *first1 > *first2 ){
223
 
                                return true;
224
 
                        }
225
 
                        if( *first2 > *first1 ){
226
 
                                return false;
227
 
                        }
228
 
                        ++first1;
229
 
                        ++first2;
230
 
                }
231
 
                return first1!=last1 && first2 == last2;
232
 
        }
233
 
 
234
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>=
235
 
                (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
236
 
        {
237
 
                typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
238
 
                typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
239
 
                typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
240
 
                typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
241
 
 
242
 
                while(first1 != last1 && first2 != last2){
243
 
                        if( *first1 > *first2 ){
244
 
                                return true;
245
 
                        }
246
 
                        if( *first2 > *first1 ){
247
 
                                return false;
248
 
                        }
249
 
                        ++first1;
250
 
                        ++first2;
251
 
                }
252
 
                return first1!=last1;
253
 
        }
254
 
 
255
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<=
256
 
                (const set<Key,Compare,Allocator>& x, const set<Key,Compare,Allocator>& y)
257
 
        {
258
 
                typename set<Key,Compare,Allocator>::const_iterator first1 = x.begin();
259
 
                typename set<Key,Compare,Allocator>::const_iterator first2 = y.begin();
260
 
                typename set<Key,Compare,Allocator>::const_iterator last1 = x.end();
261
 
                typename set<Key,Compare,Allocator>::const_iterator last2 = y.end();
262
 
 
263
 
                while(first1 != last1 && first2 != last2){
264
 
                        if( *first1 < *first2 ){
265
 
                                return true;
266
 
                        }
267
 
                        if( *first2 < *first1 ){
268
 
                                return false;
269
 
                        }
270
 
                        ++first1;
271
 
                        ++first2;
272
 
                }
273
 
                return first2!=last2;
274
 
        }
275
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT void swap
276
 
                (set<Key,Compare,Allocator>& x, set<Key,Compare,Allocator>& y)
277
 
        {
278
 
                x.swap(y);
279
 
        }
280
 
 
281
 
 
282
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator==
283
 
                (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
284
 
        {
285
 
                if(x.data == y.data){
286
 
                        return true;
287
 
                }
288
 
                return false;
289
 
        }
290
 
 
291
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator< 
292
 
                (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
293
 
        {
294
 
                typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
295
 
                typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
296
 
                typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
297
 
                typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
298
 
 
299
 
                while(first1 != last1 && first2 != last2){
300
 
                        if( *first1 < *first2 ){
301
 
                                return true;
302
 
                        }
303
 
                        if( *first2 < *first1 ){
304
 
                                return false;
305
 
                        }
306
 
                        ++first1;
307
 
                        ++first2;
308
 
                }
309
 
                return first1==last1 && first2 != last2;
310
 
        }
311
 
 
312
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator!=
313
 
                (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
314
 
        {
315
 
                typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
316
 
                typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
317
 
                typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
318
 
                typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
319
 
 
320
 
                while(first1 != last1 && first2 != last2){
321
 
                        if( *first1 != *first2 ){
322
 
                                return true;
323
 
                        }
324
 
                        ++first1;
325
 
                        ++first2;
326
 
                }
327
 
                return first1!=last1 || first2 != last2;
328
 
        }
329
 
 
330
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator> 
331
 
                (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
332
 
        {
333
 
                typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
334
 
                typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
335
 
                typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
336
 
                typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
337
 
 
338
 
                while(first1 != last1 && first2 != last2){
339
 
                        if( *first1 > *first2 ){
340
 
                                return true;
341
 
                        }
342
 
                        if( *first2 > *first1 ){
343
 
                                return false;
344
 
                        }
345
 
                        ++first1;
346
 
                        ++first2;
347
 
                }
348
 
                return first1!=last1 && first2 == last2;
349
 
        }
350
 
 
351
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator>=
352
 
                (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
353
 
        {
354
 
                typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
355
 
                typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
356
 
                typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
357
 
                typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
358
 
 
359
 
                while(first1 != last1 && first2 != last2){
360
 
                        if( *first1 > *first2 ){
361
 
                                return true;
362
 
                        }
363
 
                        if( *first2 > *first1 ){
364
 
                                return false;
365
 
                        }
366
 
                        ++first1;
367
 
                        ++first2;
368
 
                }
369
 
                return first1!=last1;
370
 
        }
371
 
        
372
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT bool operator<=
373
 
                (const multiset<Key,Compare,Allocator>& x, const multiset<Key,Compare,Allocator>& y)
374
 
        {
375
 
                typename multiset<Key,Compare,Allocator>::const_iterator first1 = x.begin();
376
 
                typename multiset<Key,Compare,Allocator>::const_iterator first2 = y.begin();
377
 
                typename multiset<Key,Compare,Allocator>::const_iterator last1 = x.end();
378
 
                typename multiset<Key,Compare,Allocator>::const_iterator last2 = y.end();
379
 
 
380
 
                while(first1 != last1 && first2 != last2){
381
 
                        if( *first1 < *first2 ){
382
 
                                return true;
383
 
                        }
384
 
                        if( *first2 < *first1 ){
385
 
                                return false;
386
 
                        }
387
 
                        ++first1;
388
 
                        ++first2;
389
 
                }
390
 
                return first2!=last2;
391
 
        }
392
 
 
393
 
        template <class Key, class Compare, class Allocator> _UCXXEXPORT void swap
394
 
                (multiset<Key,Compare,Allocator>& x, multiset<Key,Compare,Allocator>& y)
395
 
        {
396
 
                x.swap(y);
397
 
        }
398
 
 
399
 
 
400
 
 
401
 
}
402
 
 
403
 
#pragma GCC visibility pop
404
 
 
405
 
#endif
406
 
 
407