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