LibreOffice Module o3tl (master)  1
sorted_vector.hxx
Go to the documentation of this file.
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3  * This file is part of the LibreOffice project.
4  *
5  * This Source Code Form is subject to the terms of the Mozilla Public
6  * License, v. 2.0. If a copy of the MPL was not distributed with this
7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8  */
9 
10 #ifndef INCLUDED_O3TL_SORTED_VECTOR_HXX
11 #define INCLUDED_O3TL_SORTED_VECTOR_HXX
12 
13 #include <vector>
14 #include <algorithm>
15 #include <functional>
16 #include <memory>
17 #include <type_traits>
18 
19 namespace o3tl
20 {
21 
22 // forward declared because it's default template arg for sorted_vector
23 template<class Value, class Compare>
24 struct find_unique;
25 
32 template<
33  typename Value,
34  typename Compare = std::less<Value>,
35  template<typename, typename> class Find = find_unique,
36  bool = std::is_copy_constructible<Value>::value >
38 {
39 private:
40  typedef Find<Value, Compare> Find_t;
41  typedef typename std::vector<Value> vector_t;
42  typedef typename std::vector<Value>::iterator iterator;
43 public:
44  typedef typename std::vector<Value>::const_iterator const_iterator;
45  typedef typename std::vector<Value>::const_reverse_iterator const_reverse_iterator;
46  typedef typename std::vector<Value>::difference_type difference_type;
47  typedef typename std::vector<Value>::size_type size_type;
48  typedef Value value_type;
49 
50  constexpr sorted_vector( std::initializer_list<Value> init )
51  : m_vector(init)
52  {
53  std::sort(m_vector.begin(), m_vector.end(), Compare());
54  }
55  sorted_vector() = default;
56  sorted_vector(sorted_vector const&) = default;
57  sorted_vector(sorted_vector&&) = default;
58 
59  sorted_vector& operator=(sorted_vector const&) = default;
61 
62  // MODIFIERS
63 
64  std::pair<const_iterator,bool> insert( Value&& x )
65  {
66  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
67  if (!ret.second)
68  {
69  const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), std::move(x));
70  return std::make_pair(it, true);
71  }
72  return std::make_pair(ret.first, false);
73  }
74 
75  std::pair<const_iterator,bool> insert( const Value& x )
76  {
77  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
78  if (!ret.second)
79  {
80  const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), x);
81  return std::make_pair(it, true);
82  }
83  return std::make_pair(ret.first, false);
84  }
85 
86  size_type erase( const Value& x )
87  {
88  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
89  if (ret.second)
90  {
91  m_vector.erase(m_vector.begin() + (ret.first - m_vector.begin()));
92  return 1;
93  }
94  return 0;
95  }
96 
97  void erase_at(size_t index)
98  {
99  m_vector.erase(m_vector.begin() + index);
100  }
101 
102  // like C++ 2011: erase with const_iterator (doesn't change sort order)
103  const_iterator erase(const_iterator const& position)
104  { // C++98 has vector::erase(iterator), so call that
105  return m_vector.erase(m_vector.begin() + (position - m_vector.begin()));
106  }
107 
108  void erase(const_iterator const& first, const_iterator const& last)
109  {
110  m_vector.erase(m_vector.begin() + (first - m_vector.begin()),
111  m_vector.begin() + (last - m_vector.begin()));
112  }
113 
118  Value erase_extract( size_t index )
119  {
120  Value val = std::move(m_vector[index]);
121  m_vector.erase(m_vector.begin() + index);
122  return val;
123  }
124 
125  void clear()
126  {
127  m_vector.clear();
128  }
129 
130  void swap(sorted_vector & other)
131  {
132  m_vector.swap(other.m_vector);
133  }
134 
135  void reserve(size_type amount)
136  {
137  m_vector.reserve(amount);
138  }
139 
140  // ACCESSORS
141 
142  size_type size() const
143  {
144  return m_vector.size();
145  }
146 
147  bool empty() const
148  {
149  return m_vector.empty();
150  }
151 
152  // Only return a const iterator, so that the vector cannot be directly updated.
153  const_iterator begin() const
154  {
155  return m_vector.begin();
156  }
157 
158  // Only return a const iterator, so that the vector cannot be directly updated.
159  const_iterator end() const
160  {
161  return m_vector.end();
162  }
163 
164  // Only return a const iterator, so that the vector cannot be directly updated.
165  const_reverse_iterator rbegin() const
166  {
167  return m_vector.rbegin();
168  }
169 
170  // Only return a const iterator, so that the vector cannot be directly updated.
171  const_reverse_iterator rend() const
172  {
173  return m_vector.rend();
174  }
175 
176  const Value& front() const
177  {
178  return m_vector.front();
179  }
180 
181  const Value& back() const
182  {
183  return m_vector.back();
184  }
185 
186  const Value& operator[]( size_t index ) const
187  {
188  return m_vector.operator[]( index );
189  }
190 
191  // OPERATIONS
192 
193  const_iterator lower_bound( const Value& x ) const
194  {
195  return std::lower_bound( m_vector.begin(), m_vector.end(), x, Compare() );
196  }
197 
198  const_iterator upper_bound( const Value& x ) const
199  {
200  return std::upper_bound( m_vector.begin(), m_vector.end(), x, Compare() );
201  }
202 
203  /* Searches the container for an element with a value of x
204  * and returns an iterator to it if found, otherwise it returns an
205  * iterator to sorted_vector::end (the element past the end of the container).
206  *
207  * Only return a const iterator, so that the vector cannot be directly updated.
208  */
209  const_iterator find( const Value& x ) const
210  {
211  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
212  return (ret.second) ? ret.first : m_vector.end();
213  }
214 
215  size_type count(const Value& v) const
216  {
217  return find(v) != end() ? 1 : 0;
218  }
219 
220  bool operator==(const sorted_vector & other) const
221  {
222  return m_vector == other.m_vector;
223  }
224 
225  bool operator!=(const sorted_vector & other) const
226  {
227  return m_vector != other.m_vector;
228  }
229 
231  {
232  // optimization for the rather common case that we are overwriting this with the contents
233  // of another sorted vector
234  if ( empty() )
235  {
236  m_vector.insert(m_vector.begin(), rOther.m_vector.begin(), rOther.m_vector.end());
237  }
238  else
239  {
240  for (const_iterator it = rOther.m_vector.begin(); it != rOther.m_vector.end(); ++it)
241  {
242  insert(*it);
243  }
244  }
245  }
246 
247  /* Clear() elements in the vector, and free them one by one. */
249  {
250  for (const_iterator it = m_vector.begin(); it != m_vector.end(); ++it)
251  {
252  delete *it;
253  }
254 
255  clear();
256  }
257 
258  // fdo#58793: some existing code in Writer (SwpHintsArray)
259  // routinely modifies the members of the vector in a way that
260  // violates the sort order, and then re-sorts the array.
261  // This is a kludge to enable that code to work.
262  // If you are calling this function, you are Doing It Wrong!
263  void Resort()
264  {
265  std::stable_sort(m_vector.begin(), m_vector.end(), Compare());
266  }
267 
268 private:
269 
270  vector_t m_vector;
271 };
272 
273 /* Specialise the template for cases like Value = std::unique_ptr<T>, where
274  MSVC2017 needs some help
275 */
276 template<
277  typename Value,
278  typename Compare,
279  template<typename, typename> class Find >
280 class sorted_vector<Value,Compare,Find,false> : public sorted_vector<Value, Compare, Find, true>
281 {
282 public:
285 
286  sorted_vector(sorted_vector const&) = delete;
287  sorted_vector& operator=(sorted_vector const&) = delete;
288 
289  sorted_vector() = default;
290  sorted_vector(sorted_vector&&) = default;
291  sorted_vector& operator=(sorted_vector&&) = default;
292 
296  typename super_sorted_vector::const_iterator find( typename Value::element_type const * x ) const
297  {
298  Value tmp(const_cast<typename Value::element_type*>(x));
299  auto ret = super_sorted_vector::find(tmp);
300  tmp.release();
301  return ret;
302  }
306  typename super_sorted_vector::const_iterator upper_bound( typename Value::element_type const * x ) const
307  {
308  Value tmp(const_cast<typename Value::element_type*>(x));
309  auto ret = super_sorted_vector::upper_bound(tmp);
310  tmp.release();
311  return ret;
312  }
316  typename super_sorted_vector::const_iterator lower_bound( typename Value::element_type const * x ) const
317  {
318  Value tmp(const_cast<typename Value::element_type*>(x));
319  auto ret = super_sorted_vector::lower_bound(tmp);
320  tmp.release();
321  return ret;
322  }
323 };
324 
325 
329 template <class T> struct less_ptr_to
330 {
331  bool operator() ( T* const& lhs, T* const& rhs ) const
332  {
333  return (*lhs) < (*rhs);
334  }
335 };
336 
337 template <class T> struct less_uniqueptr_to
338 {
339  bool operator() ( std::unique_ptr<T> const& lhs, std::unique_ptr<T> const& rhs ) const
340  {
341  return (*lhs) < (*rhs);
342  }
343 };
344 
348 template<class Value, class Compare>
349 struct find_unique
350 {
351  typedef typename sorted_vector<Value, Compare,
353  std::pair<const_iterator, bool> operator()(
354  const_iterator first, const_iterator last,
355  Value const& v)
356  {
357  const_iterator const it = std::lower_bound(first, last, v, Compare());
358  return std::make_pair(it, (it != last && !Compare()(v, *it)));
359  }
360 };
361 
365 template<class Value, class Compare>
367 {
368  typedef typename sorted_vector<Value, Compare,
370  std::pair<const_iterator, bool> operator()(
371  const_iterator first, const_iterator last,
372  Value const& v)
373  {
374  std::pair<const_iterator, const_iterator> const its =
375  std::equal_range(first, last, v, Compare());
376  for (const_iterator it = its.first; it != its.second; ++it)
377  {
378  if (v == *it)
379  {
380  return std::make_pair(it, true);
381  }
382  }
383  return std::make_pair(its.first, false);
384  }
385 };
386 
387 } // namespace o3tl
388 #endif
389 
390 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
std::pair< const_iterator, bool > operator()(const_iterator first, const_iterator last, Value const &v)
const_iterator lower_bound(const Value &x) const
const Value & back() const
void insert(sorted_vector< Value, Compare, Find > const &rOther)
size_type count(const Value &v) const
std::pair< const_iterator, bool > insert(const Value &x)
std::vector< Value >::difference_type difference_type
super_sorted_vector::const_iterator lower_bound(typename Value::element_type const *x) const
implement lower_bound for sorted_vectors containing std::unique_ptr
std::vector< Value > vector_t
const_iterator find(const Value &x) const
void erase_at(size_t index)
sorted_vector()=default
void swap(sorted_vector &other)
float x
bool operator()(T *const &lhs, T *const &rhs) const
const Value & front() const
Implements an ordering function over a pointer, where the comparison uses the < operator on the point...
Value
super_sorted_vector::const_iterator find(typename Value::element_type const *x) const
implement find for sorted_vectors containing std::unique_ptr
bool operator==(const sorted_vector &other) const
void reserve(size_type amount)
size_type size() const
bool operator!=(const sorted_vector &other) const
const_iterator erase(const_iterator const &position)
const_iterator upper_bound(const Value &x) const
the elements are partially ordered by Compare, 2 elements are allowed if they are not the same elemen...
super_sorted_vector::const_iterator upper_bound(typename Value::element_type const *x) const
implement upper_bound for sorted_vectors containing std::unique_ptr
Find< Value, Compare > Find_t
std::vector< Value >::const_reverse_iterator const_reverse_iterator
sorted_vector & operator=(sorted_vector const &)=default
std::pair< const_iterator, bool > operator()(const_iterator first, const_iterator last, Value const &v)
const_iterator end() const
sorted_vector< Value, Compare, Find, true > super_sorted_vector
const_reverse_iterator rend() const
const_iterator begin() const
const_reverse_iterator rbegin() const
constexpr sorted_vector(std::initializer_list< Value > init)
Value erase_extract(size_t index)
make erase return the removed element, otherwise there is no useful way of extracting a std::unique_p...
bool operator()(std::unique_ptr< T > const &lhs, std::unique_ptr< T > const &rhs) const
const Value & operator[](size_t index) const
std::vector< Value >::iterator iterator
the elements are totally ordered by Compare, for no 2 elements !Compare(a,b) && !Compare(b,a) is true
sorted_vector< Value, Compare, o3tl::find_unique >::const_iterator const_iterator
std::pair< const_iterator, bool > insert(Value &&x)
void erase(const_iterator const &first, const_iterator const &last)
std::vector< Value >::size_type size_type
sorted_vector< Value, Compare, o3tl::find_partialorder_ptrequals >::const_iterator const_iterator
std::vector< Value >::const_iterator const_iterator
Represents a sorted vector of values.
size_type erase(const Value &x)