blocxx
SortedVectorMap.hpp
Go to the documentation of this file.
1/*******************************************************************************
2* Copyright (C) 2005, Vintela, Inc. All rights reserved.
3* Copyright (C) 2006, Novell, Inc. All rights reserved.
4*
5* Redistribution and use in source and binary forms, with or without
6* modification, are permitted provided that the following conditions are met:
7*
8* * Redistributions of source code must retain the above copyright notice,
9* this list of conditions and the following disclaimer.
10* * Redistributions in binary form must reproduce the above copyright
11* notice, this list of conditions and the following disclaimer in the
12* documentation and/or other materials provided with the distribution.
13* * Neither the name of
14* Vintela, Inc.,
15* nor Novell, Inc.,
16* nor the names of its contributors or employees may be used to
17* endorse or promote products derived from this software without
18* specific prior written permission.
19*
20* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30* POSSIBILITY OF SUCH DAMAGE.
31*******************************************************************************/
32
33
37
38#ifndef BLOCXX_SORTED_VECTOR_MAP_HPP_
39#define BLOCXX_SORTED_VECTOR_MAP_HPP_
40#include "blocxx/BLOCXX_config.h"
42#include "blocxx/vector.hpp"
43#include "blocxx/CommonFwd.hpp"
44#include <utility> // for std::pair
45#include <functional> // for std::less
46#include <algorithm>
47
48namespace BLOCXX_NAMESPACE
49{
50
51template <class Key, class T, class Compare>
53{
54 typedef std::pair<Key, T> Data;
55public:
56 bool operator()(const Data& lhs, const Data& rhs) const
57 {
58 return keyLess(lhs.first, rhs.first);
59 }
60
61 bool operator()(const Data& lhs, const typename Data::first_type& k) const
62 {
63 return keyLess(lhs.first, k);
64 }
65
66 bool operator()(const typename Data::first_type& k, const Data& rhs) const
67 {
68 return keyLess(k, rhs.first);
69 }
70 bool operator()(const typename Data::first_type& k, const typename Data::first_type& rhs) const
71 {
72 return keyLess(k, rhs);
73 }
74private:
75 bool keyLess(const typename Data::first_type& k1,
76 const typename Data::first_type& k2) const
77 {
78 return Compare()(k1, k2);
79 }
80};
81
82
83// forward declarations are necessary for template friends.
84template<class Key, class T, class Compare>
85inline bool operator==(const SortedVectorMap<Key, T, Compare>& x,
86 const SortedVectorMap<Key, T, Compare>& y);
87
88template<class Key, class T, class Compare>
89inline bool operator<(const SortedVectorMap<Key, T, Compare>& x,
90 const SortedVectorMap<Key, T, Compare>& y);
91
92template <class Key, class T, class Compare>
93inline void swap(SortedVectorMap<Key, T, Compare>& x,
94 SortedVectorMap<Key, T, Compare>& y);
95
96template<class Key, class T, class Compare>
98{
99 typedef std::pair<Key, T> Data;
100 typedef std::vector<Data> container_t;
102public:
103 typedef Key key_type;
104 typedef T data_type;
105 typedef std::pair<const key_type, data_type> value_type;
106 typedef Compare key_compare;
107 typedef Compare value_compare;
108 typedef typename container_t::pointer pointer;
109 typedef typename container_t::reference reference;
110 typedef typename container_t::const_reference const_reference;
111 typedef typename container_t::iterator iterator;
112 typedef typename container_t::const_iterator const_iterator;
113 typedef typename container_t::reverse_iterator reverse_iterator;
114 typedef typename container_t::const_reverse_iterator const_reverse_iterator;
115 typedef typename container_t::size_type size_type;
116 typedef typename container_t::difference_type difference_type;
118 explicit SortedVectorMap(container_t* toWrap) : m_impl(toWrap)
119 {
120 std::sort(m_impl->begin(), m_impl->end(), Compare());
121 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
122 }
123 template <class InputIterator>
124 SortedVectorMap(InputIterator first, InputIterator last) :
125 m_impl(new container_t(first, last))
126 {
127 std::sort(m_impl->begin(), m_impl->end(), Compare());
128 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
129 }
131 {
132 return m_impl->begin();
133 }
135 {
136 return m_impl->end();
137 }
138 // These are slightly dangerous, if you use them, DON'T CHANGE THE KEY!
140 {
141 return m_impl->begin();
142 }
144 {
145 return m_impl->end();
146 }
148 {
149 return m_impl->rbegin();
150 }
152 {
153 return m_impl->rend();
154 }
155 bool empty() const
156 {
157 return m_impl->empty();
158 }
160 {
161 return m_impl->size();
162 }
164 {
165 return m_impl->max_size();
166 }
168 {
169 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), k, Compare());
170 if (i != m_impl->end() && equivalent(i->first, k))
171 {
172 return i->second;
173 }
174 return (*(m_impl->insert(i, value_type(k, data_type())))).second;
175 }
177 {
178 m_impl.swap(x.m_impl);
179 }
180 std::pair<iterator, bool> insert(const value_type& x)
181 {
182 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
183 if (i != m_impl->end() && equivalent(i->first, x.first))
184 {
185 return std::pair<iterator, bool>(i, false);
186 }
187 else
188 {
189 return std::pair<iterator, bool>(m_impl->insert(i, x), true);
190 }
191 }
193 {
194 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
195
196 return m_impl->insert(i, x);
197 }
198 template <class InputIterator>
199 void insert(InputIterator first, InputIterator last)
200 {
201 m_impl->insert(m_impl->end(), first, last);
202 std::sort(m_impl->begin(), m_impl->end(), Compare());
203 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
204 }
206 {
207 return m_impl->erase(position);
208 }
210 {
211 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
212 if (i != m_impl->end() && equivalent(i->first, x))
213 {
214 m_impl->erase(i);
215 return 1;
216 }
217 else
218 {
219 return 0;
220 }
221 }
223 {
224 return m_impl->erase(first, last);
225 }
226 void clear()
227 {
228 m_impl->clear();
229 }
231 {
232 const_iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
233 if (pos != m_impl->end() && equivalent(pos->first, x))
234 {
235 return pos;
236 }
237 else
238 {
239 return m_impl->end();
240 }
241 }
243 {
244 iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
245 if (pos != m_impl->end() && equivalent(pos->first, x))
246 {
247 return pos;
248 }
249 else
250 {
251 return m_impl->end();
252 }
253 }
254 size_type count(const key_type& x) const
255 {
256 if (std::binary_search(m_impl->begin(), m_impl->end(), x, Compare()))
257 {
258 return 1;
259 }
260 else
261 {
262 return 0;
263 }
264 }
266 {
267 return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
268 }
270 {
271 return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare());
272 }
273 std::pair<const_iterator, const_iterator>
274 equal_range(const key_type& x) const
275 {
276 return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare());
277 }
280 friend bool operator< <>(const SortedVectorMap<Key, T, Compare>& x,
282private:
283 static bool equivalent(const key_type& x, const key_type& y)
284 {
285 // Strict weak ordering: Two objects x and y are equivalent if both f(x, y) and f(y, x) are false.
286 return (!Compare()(x, y) && !Compare()(y, x));
287 }
288};
289template<class Key, class T, class Compare>
292{
293 return *x.m_impl == *y.m_impl;
294}
295template<class Key, class T, class Compare>
298{
299 return *x.m_impl < *y.m_impl;
300}
301template <class Key, class T, class Compare>
307
308} // end namespace BLOCXX_NAMESPACE
309
310#endif
COWReference A smart pointer that uses non-intrusive reference counting.
bool operator()(const Data &lhs, const typename Data::first_type &k) const
bool operator()(const Data &lhs, const Data &rhs) const
bool keyLess(const typename Data::first_type &k1, const typename Data::first_type &k2) const
bool operator()(const typename Data::first_type &k, const Data &rhs) const
bool operator()(const typename Data::first_type &k, const typename Data::first_type &rhs) const
SortedVectorMap(InputIterator first, InputIterator last)
iterator insert(iterator, const value_type &x)
iterator erase(iterator first, iterator last)
const_reverse_iterator rend() const
std::pair< iterator, bool > insert(const value_type &x)
data_type & operator[](const key_type &k)
container_t::const_reverse_iterator const_reverse_iterator
std::pair< const_iterator, const_iterator > equal_range(const key_type &x) const
void swap(SortedVectorMap< Key, T, Compare > &x)
size_type count(const key_type &x) const
const_iterator upper_bound(const key_type &x) const
const_iterator find(const key_type &x) const
static bool equivalent(const key_type &x, const key_type &y)
const_iterator lower_bound(const key_type &x) const
size_type erase(const key_type &x)
const_reverse_iterator rbegin() const
friend bool operator==(const SortedVectorMap< Key, T, Compare > &x, const SortedVectorMap< Key, T, Compare > &y)
void insert(InputIterator first, InputIterator last)
std::pair< const key_type, data_type > value_type
iterator find(const key_type &x)
iterator erase(iterator position)
Taken from RFC 1321.
bool operator<(const Array< T > &x, const Array< T > &y)
bool operator==(const Array< T > &x, const Array< T > &y)
void swap(Array< T > &x, Array< T > &y)