00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00038 #ifndef BLOCXX_SORTED_VECTOR_MAP_HPP_
00039 #define BLOCXX_SORTED_VECTOR_MAP_HPP_
00040 #include "blocxx/BLOCXX_config.h"
00041 #include "blocxx/COWReference.hpp"
00042 #include "blocxx/vector.hpp"
00043 #include "blocxx/CommonFwd.hpp"
00044 #include <utility>
00045 #include <functional>
00046 #include <algorithm>
00047
00048 namespace BLOCXX_NAMESPACE
00049 {
00050
00051 template <class Key, class T, class Compare>
00052 class SortedVectorMapDataCompare
00053 {
00054 typedef std::pair<Key, T> Data;
00055 public:
00056 bool operator()(const Data& lhs, const Data& rhs) const
00057 {
00058 return keyLess(lhs.first, rhs.first);
00059 }
00060
00061 bool operator()(const Data& lhs, const typename Data::first_type& k) const
00062 {
00063 return keyLess(lhs.first, k);
00064 }
00065
00066 bool operator()(const typename Data::first_type& k, const Data& rhs) const
00067 {
00068 return keyLess(k, rhs.first);
00069 }
00070 bool operator()(const typename Data::first_type& k, const typename Data::first_type& rhs) const
00071 {
00072 return keyLess(k, rhs);
00073 }
00074 private:
00075 bool keyLess(const typename Data::first_type& k1,
00076 const typename Data::first_type& k2) const
00077 {
00078 return Compare()(k1, k2);
00079 }
00080 };
00081
00082
00083
00084 template<class Key, class T, class Compare>
00085 inline bool operator==(const SortedVectorMap<Key, T, Compare>& x,
00086 const SortedVectorMap<Key, T, Compare>& y);
00087
00088 template<class Key, class T, class Compare>
00089 inline bool operator<(const SortedVectorMap<Key, T, Compare>& x,
00090 const SortedVectorMap<Key, T, Compare>& y);
00091
00092 template <class Key, class T, class Compare>
00093 inline void swap(SortedVectorMap<Key, T, Compare>& x,
00094 SortedVectorMap<Key, T, Compare>& y);
00095
00096 template<class Key, class T, class Compare>
00097 class SortedVectorMap
00098 {
00099 typedef std::pair<Key, T> Data;
00100 typedef std::vector<Data> container_t;
00101 COWReference<container_t> m_impl;
00102 public:
00103 typedef Key key_type;
00104 typedef T data_type;
00105 typedef std::pair<const key_type, data_type> value_type;
00106 typedef Compare key_compare;
00107 typedef Compare value_compare;
00108 typedef typename container_t::pointer pointer;
00109 typedef typename container_t::reference reference;
00110 typedef typename container_t::const_reference const_reference;
00111 typedef typename container_t::iterator iterator;
00112 typedef typename container_t::const_iterator const_iterator;
00113 typedef typename container_t::reverse_iterator reverse_iterator;
00114 typedef typename container_t::const_reverse_iterator const_reverse_iterator;
00115 typedef typename container_t::size_type size_type;
00116 typedef typename container_t::difference_type difference_type;
00117 SortedVectorMap() : m_impl(new container_t) { }
00118 explicit SortedVectorMap(container_t* toWrap) : m_impl(toWrap)
00119 {
00120 std::sort(m_impl->begin(), m_impl->end(), Compare());
00121 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
00122 }
00123 template <class InputIterator>
00124 SortedVectorMap(InputIterator first, InputIterator last) :
00125 m_impl(new container_t(first, last))
00126 {
00127 std::sort(m_impl->begin(), m_impl->end(), Compare());
00128 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
00129 }
00130 const_iterator begin() const
00131 {
00132 return m_impl->begin();
00133 }
00134 const_iterator end() const
00135 {
00136 return m_impl->end();
00137 }
00138
00139 iterator begin()
00140 {
00141 return m_impl->begin();
00142 }
00143 iterator end()
00144 {
00145 return m_impl->end();
00146 }
00147 const_reverse_iterator rbegin() const
00148 {
00149 return m_impl->rbegin();
00150 }
00151 const_reverse_iterator rend() const
00152 {
00153 return m_impl->rend();
00154 }
00155 bool empty() const
00156 {
00157 return m_impl->empty();
00158 }
00159 size_type size() const
00160 {
00161 return m_impl->size();
00162 }
00163 size_type max_size() const
00164 {
00165 return m_impl->max_size();
00166 }
00167 data_type& operator[](const key_type& k)
00168 {
00169 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), k, Compare());
00170 if (i != m_impl->end() && equivalent(i->first, k))
00171 {
00172 return i->second;
00173 }
00174 return (*(m_impl->insert(i, value_type(k, data_type())))).second;
00175 }
00176 void swap(SortedVectorMap<Key, T, Compare>& x)
00177 {
00178 m_impl.swap(x.m_impl);
00179 }
00180 std::pair<iterator, bool> insert(const value_type& x)
00181 {
00182 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00183 if (i != m_impl->end() && equivalent(i->first, x.first))
00184 {
00185 return std::pair<iterator, bool>(i, false);
00186 }
00187 else
00188 {
00189 return std::pair<iterator, bool>(m_impl->insert(i, x), true);
00190 }
00191 }
00192 iterator insert(iterator, const value_type& x)
00193 {
00194 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00195
00196 return m_impl->insert(i, x);
00197 }
00198 template <class InputIterator>
00199 void insert(InputIterator first, InputIterator last)
00200 {
00201 m_impl->insert(m_impl->end(), first, last);
00202 std::sort(m_impl->begin(), m_impl->end(), Compare());
00203 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end());
00204 }
00205 iterator erase(iterator position)
00206 {
00207 return m_impl->erase(position);
00208 }
00209 size_type erase(const key_type& x)
00210 {
00211 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00212 if (i != m_impl->end() && equivalent(i->first, x))
00213 {
00214 m_impl->erase(i);
00215 return 1;
00216 }
00217 else
00218 {
00219 return 0;
00220 }
00221 }
00222 iterator erase(iterator first, iterator last)
00223 {
00224 return m_impl->erase(first, last);
00225 }
00226 void clear()
00227 {
00228 m_impl->clear();
00229 }
00230 const_iterator find(const key_type& x) const
00231 {
00232 const_iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00233 if (pos != m_impl->end() && equivalent(pos->first, x))
00234 {
00235 return pos;
00236 }
00237 else
00238 {
00239 return m_impl->end();
00240 }
00241 }
00242 iterator find(const key_type& x)
00243 {
00244 iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00245 if (pos != m_impl->end() && equivalent(pos->first, x))
00246 {
00247 return pos;
00248 }
00249 else
00250 {
00251 return m_impl->end();
00252 }
00253 }
00254 size_type count(const key_type& x) const
00255 {
00256 if (std::binary_search(m_impl->begin(), m_impl->end(), x, Compare()))
00257 {
00258 return 1;
00259 }
00260 else
00261 {
00262 return 0;
00263 }
00264 }
00265 const_iterator lower_bound(const key_type& x) const
00266 {
00267 return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare());
00268 }
00269 const_iterator upper_bound(const key_type& x) const
00270 {
00271 return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare());
00272 }
00273 std::pair<const_iterator, const_iterator>
00274 equal_range(const key_type& x) const
00275 {
00276 return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare());
00277 }
00278 friend bool operator== <>(const SortedVectorMap<Key, T, Compare>& x,
00279 const SortedVectorMap<Key, T, Compare>& y);
00280 friend bool operator< <>(const SortedVectorMap<Key, T, Compare>& x,
00281 const SortedVectorMap<Key, T, Compare>& y);
00282 private:
00283 static bool equivalent(const key_type& x, const key_type& y)
00284 {
00285
00286 return (!Compare()(x, y) && !Compare()(y, x));
00287 }
00288 };
00289 template<class Key, class T, class Compare>
00290 inline bool operator==(const SortedVectorMap<Key, T, Compare>& x,
00291 const SortedVectorMap<Key, T, Compare>& y)
00292 {
00293 return *x.m_impl == *y.m_impl;
00294 }
00295 template<class Key, class T, class Compare>
00296 inline bool operator<(const SortedVectorMap<Key, T, Compare>& x,
00297 const SortedVectorMap<Key, T, Compare>& y)
00298 {
00299 return *x.m_impl < *y.m_impl;
00300 }
00301 template <class Key, class T, class Compare>
00302 inline void swap(SortedVectorMap<Key, T, Compare>& x,
00303 SortedVectorMap<Key, T, Compare>& y)
00304 {
00305 x.swap(y);
00306 }
00307
00308 }
00309
00310 #endif