/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/map

  • 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

Lines of Context:
 
1
/*      Copyright (C) 2004-2007 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
 
 
29
#ifndef __STD_HEADER_MAP
 
30
#define __STD_HEADER_MAP
 
31
 
 
32
#pragma GCC visibility push(default)
 
33
 
 
34
namespace std{
 
35
 
 
36
 
 
37
template<class Key, class T, class Compare = less<Key>, class Allocator = allocator<T> > class map;
 
38
template<class Key, class T, class Compare = less<Key>, class Allocator = allocator<T> > class multimap;
 
39
 
 
40
 
 
41
        //Compare the keys of the two items
 
42
/*      template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT 
 
43
                __base_map<Key, T, Compare, Allocator>::value_compare : public binary_function<
 
44
                        typename map<Key, T, Compare, Allocator>::value_type,
 
45
                        typename map<Key, T, Compare, Allocator>::value_type,
 
46
                bool>
 
47
        {
 
48
                friend class __base_map<Key, T, Compare, Allocator>;
 
49
        protected:
 
50
                Compare comp;
 
51
                value_compare(Compare c) : comp(c) { }
 
52
                ~value_compare() {  }
 
53
        public:
 
54
                bool operator()(const value_type& x, const value_type& y) const {
 
55
                        return comp(x.first, y.first);
 
56
                }
 
57
        };
 
58
*/
 
59
 
 
60
//      value_compare value_comp() const;
 
61
 
 
62
 
 
63
 
 
64
/* This is the implementation for the map container.  As noted above, it deviates
 
65
 * from ISO spec by deriving from a base class in order to reduce code redundancy.
 
66
 * More code could be reduced by convirting to virtual functions (thus allowing
 
67
 * much of the erase and insert code to be duplicated), but that would deviate from
 
68
 * the specifications too much to be worth the risk.
 
69
 */
 
70
 
 
71
 
 
72
 
 
73
//Implementation of map
 
74
 
 
75
 
 
76
template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT map
 
77
        : public __single_associative<Key, pair<Key, T>, Compare, Allocator>
 
78
{
 
79
                //Default value of allocator does not meet C++ standard specs, but it works for this library
 
80
                //Deal with it
 
81
 
 
82
public:
 
83
 
 
84
        typedef __single_associative<Key, pair<Key, T>, Compare, Allocator>     base;
 
85
        typedef T                                                               mapped_type;
 
86
        typedef typename base::key_type                                         key_type;
 
87
        typedef typename base::value_type                                       value_type;
 
88
        typedef typename base::key_compare                                      key_compare;
 
89
        typedef typename base::allocator_type                                   allocator_type;
 
90
        typedef typename base::reference                                        reference;
 
91
        typedef typename base::const_reference                                  const_reference;
 
92
        typedef typename base::iterator                                         iterator;
 
93
        typedef typename base::const_iterator                                   const_iterator;
 
94
        typedef typename base::size_type                                        size_type;
 
95
        typedef typename base::difference_type                                  difference_type;
 
96
        typedef typename base::pointer                                          pointer;
 
97
        typedef typename base::const_pointer                                    const_pointer;
 
98
        typedef typename base::reverse_iterator                                 reverse_iterator;
 
99
        typedef typename base::const_reverse_iterator                           const_reverse_iterator;
 
100
 
 
101
        static const key_type v_t_k(const value_type v){
 
102
                return v.first;
 
103
        }
 
104
 
 
105
//      using base::value_compare;
 
106
 
 
107
        explicit map(const Compare& comp = Compare(), const Allocator& al = Allocator())
 
108
                : base(comp, al, v_t_k) {  }
 
109
 
 
110
        template <class InputIterator> map(InputIterator first, InputIterator last,
 
111
                const Compare& comp = Compare(), const Allocator& al = Allocator())
 
112
                : base(first, last, comp, al, v_t_k) {  }
 
113
 
 
114
        map(const map<Key,T,Compare,Allocator>& x) : base(x) {  }
 
115
        ~map() {  }
 
116
 
 
117
        using base::operator=;
 
118
        using base::operator==;
 
119
        using base::operator!=;
 
120
 
 
121
        using base::insert;
 
122
        using base::erase;
 
123
 
 
124
        using base::begin;
 
125
        using base::end;
 
126
        using base::rbegin;
 
127
        using base::rend;
 
128
 
 
129
        using base::empty;
 
130
        using base::size;
 
131
        using base::max_size;
 
132
 
 
133
        using base::find;
 
134
        using base::count;
 
135
        using base::lower_bound;
 
136
        using base::upper_bound;
 
137
        using base::equal_range;
 
138
        using base::swap;
 
139
 
 
140
        reference operator[](const key_type& k){
 
141
                iterator i = lower_bound(k);
 
142
                if (i == end() || base::c(k, i->first)) {
 
143
                        i = insert(make_pair(k, T())).first;
 
144
                }
 
145
                return i->second;
 
146
        }
 
147
 
 
148
protected:
 
149
        using base::backing;
 
150
};
 
151
 
 
152
 
 
153
//Implementation of multimap
 
154
 
 
155
 
 
156
template<class Key, class T, class Compare, class Allocator> class _UCXXEXPORT multimap
 
157
        : public __multi_associative<Key, pair<Key, T>, Compare, Allocator>
 
158
 
 
159
{
 
160
                //Default value of allocator does not meet C++ standard specs, but it works for this library
 
161
                //Deal with it
 
162
public:
 
163
 
 
164
        typedef __multi_associative<Key, pair<Key, T>, Compare, Allocator>      base;
 
165
        typedef T                                                               mapped_type;
 
166
        typedef typename base::key_type                                         key_type;
 
167
        typedef typename base::value_type                                       value_type;
 
168
        typedef typename base::key_compare                                      key_compare;
 
169
        typedef typename base::allocator_type                                   allocator_type;
 
170
        typedef typename base::reference                                        reference;
 
171
        typedef typename base::const_reference                                  const_reference;
 
172
        typedef typename base::iterator                                         iterator;
 
173
        typedef typename base::const_iterator                                   const_iterator;
 
174
        typedef typename base::size_type                                        size_type;
 
175
        typedef typename base::difference_type                                  difference_type;
 
176
        typedef typename base::pointer                                          pointer;
 
177
        typedef typename base::const_pointer                                    const_pointer;
 
178
        typedef typename base::reverse_iterator                                 reverse_iterator;
 
179
        typedef typename base::const_reverse_iterator                           const_reverse_iterator;
 
180
 
 
181
        static const key_type v_t_k(const value_type v){
 
182
                return v.first;
 
183
        }
 
184
 
 
185
        explicit multimap(const Compare& comp = Compare(), const Allocator& al = Allocator())
 
186
                : base(comp, al, v_t_k) {  }
 
187
 
 
188
        template <class InputIterator> multimap(InputIterator first, InputIterator last,
 
189
                const Compare& comp = Compare(), const Allocator& al = Allocator())
 
190
                : base(first, last, comp, al, v_t_k) {  }
 
191
 
 
192
 
 
193
        multimap(const multimap<Key,T,Compare,Allocator>& x) : base(x) {  }
 
194
        ~multimap() {  }
 
195
 
 
196
        using base::operator=;
 
197
        using base::operator==;
 
198
        using base::operator!=;
 
199
 
 
200
        using base::insert;
 
201
        using base::erase;
 
202
 
 
203
        using base::begin;
 
204
        using base::end;
 
205
        using base::rbegin;
 
206
        using base::rend;
 
207
 
 
208
        using base::empty;
 
209
        using base::size;
 
210
        using base::max_size;
 
211
 
 
212
        using base::find;
 
213
        using base::count;
 
214
        using base::lower_bound;
 
215
        using base::upper_bound;
 
216
        using base::equal_range;
 
217
        using base::swap;
 
218
 
 
219
protected:
 
220
 
 
221
        using base::c;
 
222
 
 
223
};
 
224
 
 
225
 
 
226
/* Non-member functions.  These are at the end because they are not associated with any
 
227
   particular class.  These will be implemented as I figure out exactly what all of 
 
228
   them are supposed to do, and I have time.
 
229
 */
 
230
 
 
231
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator< 
 
232
                (const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
 
233
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator!=
 
234
                (const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
 
235
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>
 
236
                (const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
 
237
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>=
 
238
                (const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
 
239
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator<=
 
240
                (const map<Key,T,Compare,Allocator>& x, const map<Key,T,Compare,Allocator>& y);
 
241
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT void swap
 
242
                (map<Key,T,Compare,Allocator>& x, map<Key,T,Compare,Allocator>& y);
 
243
 
 
244
 
 
245
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator==
 
246
                (const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
 
247
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator< 
 
248
                (const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
 
249
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator!=
 
250
                (const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
 
251
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator> 
 
252
                (const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
 
253
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator>=
 
254
                (const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
 
255
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT bool operator<=
 
256
                (const multimap<Key,T,Compare,Allocator>& x, const multimap<Key,T,Compare,Allocator>& y);
 
257
        template <class Key, class T, class Compare, class Allocator> _UCXXEXPORT void swap
 
258
                (multimap<Key,T,Compare,Allocator>& x, multimap<Key,T,Compare,Allocator>& y);
 
259
 
 
260
}
 
261
 
 
262
#pragma GCC visibility pop
 
263
 
 
264
#endif
 
265
 
 
266