/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: edam
  • Date: 2012-02-25 01:31:43 UTC
  • Revision ID: tim@ed.am-20120225013143-9fet2y2d3fjlrwez
added ulibc

Show diffs side-by-side

added added

removed removed

src/utility/set
 
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