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_SET_HPP_ 00039 #define BLOCXX_SORTED_VECTOR_SET_HPP_ 00040 #include "blocxx/BLOCXX_config.h" 00041 #include "blocxx/COWReference.hpp" 00042 #include "blocxx/vector.hpp" 00043 #include <utility> // for std::pair 00044 #include <functional> // for std::less 00045 #include <algorithm> 00046 00047 namespace BLOCXX_NAMESPACE 00048 { 00049 00050 template<class T, class Compare > 00051 class SortedVectorSet; 00052 00053 template<class T, class Compare> 00054 inline bool operator==(const SortedVectorSet<T, Compare>& x, 00055 const SortedVectorSet<T, Compare>& y); 00056 00057 template<class T, class Compare> 00058 inline bool operator<(const SortedVectorSet<T, Compare>& x, 00059 const SortedVectorSet<T, Compare>& y); 00060 00061 template<class T, class Compare = std::less<T> > 00062 class SortedVectorSet 00063 { 00064 typedef std::vector<T> container_t; 00065 #ifdef BLOCXX_WIN32 00066 #pragma warning (push) 00067 #pragma warning (disable: 4251) 00068 #endif 00069 COWReference<container_t> m_impl; 00070 #ifdef BLOCXX_WIN32 00071 #pragma warning (pop) 00072 #endif 00073 public: 00074 typedef T key_type; 00075 typedef T data_type; 00076 typedef T value_type; 00077 typedef Compare key_compare; 00078 typedef Compare value_compare; 00079 typedef typename container_t::pointer pointer; 00080 typedef typename container_t::const_pointer const_pointer; 00081 typedef typename container_t::reference reference; 00082 typedef typename container_t::const_reference const_reference; 00083 typedef typename container_t::iterator iterator; 00084 typedef typename container_t::const_iterator const_iterator; 00085 typedef typename container_t::reverse_iterator reverse_iterator; 00086 typedef typename container_t::const_reverse_iterator const_reverse_iterator; 00087 typedef typename container_t::size_type size_type; 00088 typedef typename container_t::difference_type difference_type; 00089 SortedVectorSet() : m_impl(new container_t) { } 00090 explicit SortedVectorSet(container_t* toWrap) : m_impl(toWrap) 00091 { 00092 std::sort(m_impl->begin(), m_impl->end(), Compare()); 00093 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end()); 00094 } 00095 template <class InputIterator> 00096 SortedVectorSet(InputIterator first, InputIterator last) : 00097 m_impl(new container_t(first, last)) 00098 { 00099 std::sort(m_impl->begin(), m_impl->end(), Compare()); 00100 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end()); 00101 } 00102 const_iterator begin() const { return m_impl->begin(); } 00103 const_iterator end() const { return m_impl->end(); } 00104 const_reverse_iterator rbegin() const { return m_impl->rbegin(); } 00105 const_reverse_iterator rend() const { return m_impl->rend(); } 00106 bool empty() const { return m_impl->empty(); } 00107 size_type size() const { return m_impl->size(); } 00108 size_type max_size() const { return m_impl->max_size(); } 00109 void swap(SortedVectorSet<T, Compare>& x) 00110 { 00111 m_impl.swap(x.m_impl); 00112 } 00113 std::pair<iterator, bool> insert(const value_type& x) 00114 { 00115 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00116 if (i != m_impl->end() && equivalent(*i, x)) 00117 { 00118 return std::pair<iterator, bool>(i, false); 00119 } 00120 else 00121 { 00122 return std::pair<iterator, bool>(m_impl->insert(i, x), true); 00123 } 00124 } 00125 iterator insert(iterator, const value_type& x) 00126 { 00127 return insert(x).first; 00128 } 00129 template <class InputIterator> 00130 void insert(InputIterator first, InputIterator last) 00131 { 00132 m_impl->insert(m_impl->end(), first, last); 00133 std::sort(m_impl->begin(), m_impl->end(), Compare()); 00134 m_impl->erase(std::unique(m_impl->begin(), m_impl->end(), &equivalent), m_impl->end()); 00135 } 00136 iterator erase(iterator position) 00137 { 00138 return m_impl->erase(position); 00139 } 00140 size_type erase(const key_type& x) 00141 { 00142 iterator i = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00143 if (i != m_impl->end() && equivalent(*i, x)) 00144 { 00145 m_impl->erase(i); 00146 return 1; 00147 } 00148 else 00149 { 00150 return 0; 00151 } 00152 } 00153 iterator erase(iterator first, iterator last) 00154 { 00155 return m_impl->erase(first, last); 00156 } 00157 void clear() 00158 { 00159 m_impl->clear(); 00160 } 00161 iterator find(const key_type& x) 00162 { 00163 iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00164 if (pos != m_impl->end() && equivalent(*pos, x)) 00165 { 00166 return pos; 00167 } 00168 else 00169 { 00170 return m_impl->end(); 00171 } 00172 } 00173 const_iterator find(const key_type& x) const 00174 { 00175 const_iterator pos = std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00176 if (pos != m_impl->end() && equivalent(*pos, x)) 00177 { 00178 return pos; 00179 } 00180 else 00181 { 00182 return m_impl->end(); 00183 } 00184 } 00185 size_type count(const key_type& x) const 00186 { 00187 if (std::binary_search(m_impl->begin(), m_impl->end(), x, Compare())) 00188 { 00189 return 1; 00190 } 00191 else 00192 { 00193 return 0; 00194 } 00195 } 00196 iterator lower_bound(const key_type& x) 00197 { 00198 return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00199 } 00200 const_iterator lower_bound(const key_type& x) const 00201 { 00202 return std::lower_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00203 } 00204 iterator upper_bound(const key_type& x) 00205 { 00206 return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00207 } 00208 const_iterator upper_bound(const key_type& x) const 00209 { 00210 return std::upper_bound(m_impl->begin(), m_impl->end(), x, Compare()); 00211 } 00212 00213 std::pair<iterator, iterator> 00214 equal_range(const key_type& x) 00215 { 00216 return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare()); 00217 } 00218 00219 std::pair<const_iterator, const_iterator> 00220 equal_range(const key_type& x) const 00221 { 00222 return std::equal_range(m_impl->begin(), m_impl->end(), x, Compare()); 00223 } 00224 00225 friend bool operator== <>(const SortedVectorSet<T, Compare>& x, 00226 const SortedVectorSet<T, Compare>& y); 00227 friend bool operator< <>(const SortedVectorSet<T, Compare>& x, 00228 const SortedVectorSet<T, Compare>& y); 00229 00230 private: 00231 static bool equivalent(const key_type& x, const key_type& y) 00232 { 00233 // Strict weak ordering: Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. 00234 return (!Compare()(x, y) && !Compare()(y, x)); 00235 } 00236 }; 00237 template<class T, class Compare> 00238 inline bool operator==(const SortedVectorSet<T, Compare>& x, 00239 const SortedVectorSet<T, Compare>& y) 00240 { 00241 return *x.m_impl == *y.m_impl; 00242 } 00243 template<class T, class Compare> 00244 inline bool operator<(const SortedVectorSet<T, Compare>& x, 00245 const SortedVectorSet<T, Compare>& y) 00246 { 00247 return *x.m_impl < *y.m_impl; 00248 } 00249 template <class T, class Compare> 00250 inline void swap(SortedVectorSet<T, Compare>& x, 00251 SortedVectorSet<T, Compare>& y) 00252 { 00253 x.swap(y); 00254 } 00255 00256 } // end namespace BLOCXX_NAMESPACE 00257 00258 #endif