blocxx
|
00001 /******************************************************************************* 00002 * Copyright (C) 2005, Vintela, Inc. All rights reserved. 00003 * Copyright (C) 2006, Novell, Inc. All rights reserved. 00004 * 00005 * Redistribution and use in source and binary forms, with or without 00006 * modification, are permitted provided that the following conditions are met: 00007 * 00008 * * Redistributions of source code must retain the above copyright notice, 00009 * this list of conditions and the following disclaimer. 00010 * * Redistributions in binary form must reproduce the above copyright 00011 * notice, this list of conditions and the following disclaimer in the 00012 * documentation and/or other materials provided with the distribution. 00013 * * Neither the name of 00014 * Vintela, Inc., 00015 * nor Novell, Inc., 00016 * nor the names of its contributors or employees may be used to 00017 * endorse or promote products derived from this software without 00018 * specific prior written permission. 00019 * 00020 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 00021 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00022 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00023 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 00024 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 00025 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 00026 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00027 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 00028 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 00029 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00030 * POSSIBILITY OF SUCH DAMAGE. 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> // for std::pair 00045 #include <functional> // for std::less 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 // forward declarations are necessary for template friends. 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 // These are slightly dangerous, if you use them, DON'T CHANGE THE KEY! 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 // Strict weak ordering: Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. 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 } // end namespace BLOCXX_NAMESPACE 00309 00310 #endif