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