← Back to branch summary

~ubuntu-branches/ubuntu/maverick/asc/maverick

« back to all changes in this revision

Viewing changes to source/libs/loki-0.1.6/include/loki/AssocVector.h

  • Committer: Bazaar Package Importer
  • Author(s): Moritz Muehlenhoff, Moritz Muehlenhoff, Barry deFreese, Alexander Reichle-Schmehl
  • Date: 2010-01-01 22:11:14 UTC
  • mfrom: (1.1.6 upstream) (2.1.4 sid)
  • Revision ID: james.westby@ubuntu.com-20100101221114-qfg9ogppdfcte4m7
Tags: 2.4.0.0-1
http://bugs.debian.org/534171
http://bugs.debian.org/538430
[ Moritz Muehlenhoff ]
* New upstream release. (2.4.0)
  - Drop obsolete patches
  - Initializes map_edit properly. (Closes: #534171).
* Update to standards version 3.8.3
* Switch to source format 3.0 (quilt) (Closes: #538430)
* Adding myself to uploaders

[ Barry deFreese ]
* New upstream release. (2.2.0)

[ Alexander Reichle-Schmehl ]
* Adopt debian/control to my new name.

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/libs/loki-0.1.6/include/loki/AssocVector.h
 
1
////////////////////////////////////////////////////////////////////////////////
 
2
// The Loki Library
 
3
// Copyright (c) 2001 by Andrei Alexandrescu
 
4
// This code accompanies the book:
 
5
// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
 
6
//     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
 
7
// Permission to use, copy, modify, distribute and sell this software for any 
 
8
//     purpose is hereby granted without fee, provided that the above copyright 
 
9
//     notice appear in all copies and that both that copyright notice and this 
 
10
//     permission notice appear in supporting documentation.
 
11
// The author or Addison-Wesley Longman make no representations about the 
 
12
//     suitability of this software for any purpose. It is provided "as is" 
 
13
//     without express or implied warranty.
 
14
////////////////////////////////////////////////////////////////////////////////
 
15
#ifndef LOKI_ASSOCVECTOR_INC_
 
16
#define LOKI_ASSOCVECTOR_INC_
 
17
 
 
18
// $Id: AssocVector.h,v 1.1 2008-06-24 18:20:55 mbickel Exp $
 
19
 
 
20
 
 
21
#include <algorithm>
 
22
#include <functional>
 
23
#include <vector>
 
24
#include <utility>
 
25
 
 
26
namespace Loki
 
27
{
 
28
////////////////////////////////////////////////////////////////////////////////
 
29
// class template AssocVectorCompare
 
30
// Used by AssocVector
 
31
////////////////////////////////////////////////////////////////////////////////
 
32
 
 
33
    namespace Private
 
34
    {
 
35
        template <class Value, class C>
 
36
        class AssocVectorCompare : public C
 
37
        {
 
38
            typedef std::pair<typename C::first_argument_type, Value>
 
39
                Data;
 
40
            typedef typename C::first_argument_type first_argument_type;
 
41
 
 
42
        public:
 
43
            AssocVectorCompare()
 
44
            {}
 
45
            
 
46
            AssocVectorCompare(const C& src) : C(src)
 
47
            {}
 
48
            
 
49
            bool operator()(const first_argument_type& lhs, 
 
50
                const first_argument_type& rhs) const
 
51
            { return C::operator()(lhs, rhs); }
 
52
            
 
53
            bool operator()(const Data& lhs, const Data& rhs) const
 
54
            { return operator()(lhs.first, rhs.first); }
 
55
            
 
56
            bool operator()(const Data& lhs, 
 
57
                const first_argument_type& rhs) const
 
58
            { return operator()(lhs.first, rhs); }
 
59
            
 
60
            bool operator()(const first_argument_type& lhs,
 
61
                const Data& rhs) const
 
62
            { return operator()(lhs, rhs.first); }
 
63
        };
 
64
    }
 
65
 
 
66
////////////////////////////////////////////////////////////////////////////////
 
67
// class template AssocVector
 
68
// An associative vector built as a syntactic drop-in replacement for std::map
 
69
// BEWARE: AssocVector doesn't respect all map's guarantees, the most important
 
70
//     being:
 
71
// * iterators are invalidated by insert and erase operations
 
72
// * the complexity of insert/erase is O(N) not O(log N)
 
73
// * value_type is std::pair<K, V> not std::pair<const K, V>
 
74
// * iterators are random
 
75
////////////////////////////////////////////////////////////////////////////////
 
76
 
 
77
 
 
78
    template
 
79
    <
 
80
        class K,
 
81
        class V,
 
82
        class C = std::less<K>,
 
83
        class A = std::allocator< std::pair<K, V> >
 
84
    >
 
85
    class AssocVector 
 
86
        : private std::vector< std::pair<K, V>, A >
 
87
        , private Private::AssocVectorCompare<V, C>
 
88
    {
 
89
        typedef std::vector<std::pair<K, V>, A> Base;
 
90
        typedef Private::AssocVectorCompare<V, C> MyCompare;
 
91
 
 
92
    public:
 
93
        typedef K key_type;
 
94
        typedef V mapped_type;
 
95
        typedef typename Base::value_type value_type;
 
96
 
 
97
        typedef C key_compare;
 
98
        typedef A allocator_type;
 
99
        typedef typename A::reference reference;
 
100
        typedef typename A::const_reference const_reference;
 
101
        typedef typename Base::iterator iterator;
 
102
        typedef typename Base::const_iterator const_iterator;
 
103
        typedef typename Base::size_type size_type;
 
104
        typedef typename Base::difference_type difference_type;
 
105
        typedef typename A::pointer pointer;
 
106
        typedef typename A::const_pointer const_pointer;
 
107
        typedef typename Base::reverse_iterator reverse_iterator;
 
108
        typedef typename Base::const_reverse_iterator const_reverse_iterator;
 
109
 
 
110
        class value_compare
 
111
            : public std::binary_function<value_type, value_type, bool>
 
112
            , private key_compare
 
113
        {
 
114
            friend class AssocVector;
 
115
        
 
116
        protected:
 
117
            value_compare(key_compare pred) : key_compare(pred)
 
118
            {}
 
119
 
 
120
        public:
 
121
            bool operator()(const value_type& lhs, const value_type& rhs) const
 
122
            { return key_compare::operator()(lhs.first, rhs.first); }
 
123
        };
 
124
        
 
125
        // 23.3.1.1 construct/copy/destroy
 
126
 
 
127
        explicit AssocVector(const key_compare& comp = key_compare(), 
 
128
            const A& alloc = A())
 
129
        : Base(alloc), MyCompare(comp)
 
130
        {}
 
131
        
 
132
        template <class InputIterator>
 
133
        AssocVector(InputIterator first, InputIterator last, 
 
134
            const key_compare& comp = key_compare(), 
 
135
            const A& alloc = A())
 
136
        : Base(first, last, alloc), MyCompare(comp)
 
137
        {
 
138
            MyCompare& me = *this;
 
139
            std::sort(begin(), end(), me);
 
140
        }
 
141
        
 
142
        AssocVector& operator=(const AssocVector& rhs)
 
143
        { 
 
144
            AssocVector(rhs).swap(*this); 
 
145
            return *this;
 
146
        }
 
147
 
 
148
        // iterators:
 
149
        // The following are here because MWCW gets 'using' wrong
 
150
        iterator begin() { return Base::begin(); }
 
151
        const_iterator begin() const { return Base::begin(); }
 
152
        iterator end() { return Base::end(); }
 
153
        const_iterator end() const { return Base::end(); }
 
154
        reverse_iterator rbegin() { return Base::rbegin(); }
 
155
        const_reverse_iterator rbegin() const { return Base::rbegin(); }
 
156
        reverse_iterator rend() { return Base::rend(); }
 
157
        const_reverse_iterator rend() const { return Base::rend(); }
 
158
        
 
159
        // capacity:
 
160
        bool empty() const { return Base::empty(); }
 
161
        size_type size() const { return Base::size(); }
 
162
        size_type max_size() { return Base::max_size(); }
 
163
 
 
164
        // 23.3.1.2 element access:
 
165
        mapped_type& operator[](const key_type& key)
 
166
        { return insert(value_type(key, mapped_type())).first->second; }
 
167
 
 
168
        // modifiers:
 
169
        std::pair<iterator, bool> insert(const value_type& val)
 
170
        {
 
171
            bool found(true);
 
172
            iterator i(lower_bound(val.first));
 
173
 
 
174
            if (i == end() || this->operator()(val.first, i->first))
 
175
            {
 
176
                i = Base::insert(i, val);
 
177
                found = false;
 
178
            }
 
179
            return std::make_pair(i, !found);
 
180
        }
 
181
        //Section [23.1.2], Table 69
 
182
        //http://developer.apple.com/documentation/DeveloperTools/gcc-3.3/libstdc++/23_containers/howto.html#4
 
183
        iterator insert(iterator pos, const value_type& val)
 
184
        {
 
185
            if( (pos == begin() || this->operator()(*(pos-1),val)) && 
 
186
                (pos == end()    || this->operator()(val, *pos)) )
 
187
            {
 
188
                return Base::insert(pos, val);
 
189
            }
 
190
            return insert(val).first;
 
191
        }
 
192
       
 
193
        template <class InputIterator>
 
194
        void insert(InputIterator first, InputIterator last)
 
195
        { for (; first != last; ++first) insert(*first); }
 
196
        
 
197
        void erase(iterator pos)
 
198
        { Base::erase(pos); }
 
199
 
 
200
        size_type erase(const key_type& k)
 
201
        {
 
202
            iterator i(find(k));
 
203
            if (i == end()) return 0;
 
204
            erase(i);
 
205
            return 1;
 
206
        }
 
207
 
 
208
        void erase(iterator first, iterator last)
 
209
        { Base::erase(first, last); }
 
210
 
 
211
        void swap(AssocVector& other)
 
212
        {
 
213
            Base::swap(other);
 
214
            MyCompare& me = *this;
 
215
            MyCompare& rhs = other;
 
216
            std::swap(me, rhs);
 
217
        }
 
218
        
 
219
        void clear()
 
220
        { Base::clear(); }
 
221
 
 
222
        // observers:
 
223
        key_compare key_comp() const
 
224
        { return *this; }
 
225
 
 
226
        value_compare value_comp() const
 
227
        {
 
228
            const key_compare& comp = *this;
 
229
            return value_compare(comp);
 
230
        }
 
231
 
 
232
        // 23.3.1.3 map operations:
 
233
        iterator find(const key_type& k)
 
234
        {
 
235
            iterator i(lower_bound(k));
 
236
            if (i != end() && this->operator()(k, i->first))
 
237
            {
 
238
                i = end();
 
239
            }
 
240
            return i;
 
241
        }
 
242
 
 
243
        const_iterator find(const key_type& k) const
 
244
        {       
 
245
            const_iterator i(lower_bound(k));
 
246
            if (i != end() && this->operator()(k, i->first))
 
247
            {
 
248
                i = end();
 
249
            }
 
250
            return i;
 
251
        }
 
252
 
 
253
        size_type count(const key_type& k) const
 
254
        { return find(k) != end(); }
 
255
 
 
256
        iterator lower_bound(const key_type& k)
 
257
        {
 
258
            MyCompare& me = *this;
 
259
            return std::lower_bound(begin(), end(), k, me);
 
260
        }
 
261
 
 
262
        const_iterator lower_bound(const key_type& k) const
 
263
        {
 
264
            const MyCompare& me = *this;
 
265
            return std::lower_bound(begin(), end(), k, me);
 
266
        }
 
267
 
 
268
        iterator upper_bound(const key_type& k)
 
269
        {
 
270
            MyCompare& me = *this;
 
271
            return std::upper_bound(begin(), end(), k, me);
 
272
        }
 
273
 
 
274
        const_iterator upper_bound(const key_type& k) const
 
275
        {
 
276
            const MyCompare& me = *this;
 
277
            return std::upper_bound(begin(), end(), k, me);
 
278
        }
 
279
 
 
280
        std::pair<iterator, iterator> equal_range(const key_type& k)
 
281
        {
 
282
            MyCompare& me = *this;
 
283
            return std::equal_range(begin(), end(), k, me);
 
284
        }
 
285
 
 
286
        std::pair<const_iterator, const_iterator> equal_range(
 
287
            const key_type& k) const
 
288
        {
 
289
            const MyCompare& me = *this;
 
290
            return std::equal_range(begin(), end(), k, me);
 
291
        }
 
292
 
 
293
        template <class K1, class V1, class C1, class A1>
 
294
        friend bool operator==(const AssocVector<K1, V1, C1, A1>& lhs,
 
295
                        const AssocVector<K1, V1, C1, A1>& rhs);
 
296
 
 
297
        bool operator<(const AssocVector& rhs) const
 
298
        {
 
299
            const Base& me = *this;
 
300
            const Base& yo = rhs;
 
301
            return me < yo;
 
302
        }
 
303
 
 
304
        template <class K1, class V1, class C1, class A1>
 
305
        friend bool operator!=(const AssocVector<K1, V1, C1, A1>& lhs,
 
306
                               const AssocVector<K1, V1, C1, A1>& rhs);
 
307
 
 
308
        template <class K1, class V1, class C1, class A1>
 
309
        friend bool operator>(const AssocVector<K1, V1, C1, A1>& lhs,
 
310
                              const AssocVector<K1, V1, C1, A1>& rhs);
 
311
 
 
312
        template <class K1, class V1, class C1, class A1>
 
313
        friend bool operator>=(const AssocVector<K1, V1, C1, A1>& lhs,
 
314
                               const AssocVector<K1, V1, C1, A1>& rhs);
 
315
 
 
316
        template <class K1, class V1, class C1, class A1>
 
317
        friend bool operator<=(const AssocVector<K1, V1, C1, A1>& lhs,
 
318
                               const AssocVector<K1, V1, C1, A1>& rhs);
 
319
    };
 
320
 
 
321
    template <class K, class V, class C, class A>
 
322
    inline bool operator==(const AssocVector<K, V, C, A>& lhs,
 
323
                           const AssocVector<K, V, C, A>& rhs)
 
324
    {
 
325
      const std::vector<std::pair<K, V>, A>& me = lhs;
 
326
      return me == rhs;
 
327
    }
 
328
 
 
329
    template <class K, class V, class C, class A>
 
330
    inline bool operator!=(const AssocVector<K, V, C, A>& lhs,
 
331
                           const AssocVector<K, V, C, A>& rhs)
 
332
    { return !(lhs == rhs); }
 
333
 
 
334
    template <class K, class V, class C, class A>
 
335
    inline bool operator>(const AssocVector<K, V, C, A>& lhs,
 
336
                          const AssocVector<K, V, C, A>& rhs)
 
337
    { return rhs < lhs; }
 
338
 
 
339
    template <class K, class V, class C, class A>
 
340
    inline bool operator>=(const AssocVector<K, V, C, A>& lhs,
 
341
                           const AssocVector<K, V, C, A>& rhs)
 
342
    { return !(lhs < rhs); }
 
343
 
 
344
    template <class K, class V, class C, class A>
 
345
    inline bool operator<=(const AssocVector<K, V, C, A>& lhs,
 
346
                           const AssocVector<K, V, C, A>& rhs)
 
347
    { return !(rhs < lhs); }
 
348
 
 
349
 
 
350
    // specialized algorithms:
 
351
    template <class K, class V, class C, class A>
 
352
    void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
 
353
    { lhs.swap(rhs); }
 
354
    
 
355
} // namespace Loki
 
356
 
 
357
#endif // end file guardian
 
358