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