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
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>
00044 #include <functional>
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
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 }
00257
00258 #endif