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 
49  constexpr sorted_vector( std::initializer_list<Value> init )
50  : m_vector(init)
51  {
52  std::sort(m_vector.begin(), m_vector.end(), Compare());
53  }
54  sorted_vector() = default;
55  sorted_vector(sorted_vector const&) = default;
56  sorted_vector(sorted_vector&&) = default;
57 
58  sorted_vector& operator=(sorted_vector const&) = default;
60 
61  // MODIFIERS
62 
63  std::pair<const_iterator,bool> insert( Value&& x )
64  {
65  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
66  if (!ret.second)
67  {
68  const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), std::move(x));
69  return std::make_pair(it, true);
70  }
71  return std::make_pair(ret.first, false);
72  }
73 
74  std::pair<const_iterator,bool> insert( const Value& x )
75  {
76  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
77  if (!ret.second)
78  {
79  const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), x);
80  return std::make_pair(it, true);
81  }
82  return std::make_pair(ret.first, false);
83  }
84 
85  size_type erase( const Value& x )
86  {
87  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
88  if (ret.second)
89  {
90  m_vector.erase(m_vector.begin() + (ret.first - m_vector.begin()));
91  return 1;
92  }
93  return 0;
94  }
95 
96  void erase( size_t index )
97  {
98  m_vector.erase(m_vector.begin() + index);
99  }
100 
101  // like C++ 2011: erase with const_iterator (doesn't change sort order)
102  const_iterator erase(const_iterator const& position)
103  { // C++98 has vector::erase(iterator), so call that
104  return m_vector.erase(m_vector.begin() + (position - m_vector.begin()));
105  }
106 
107  void erase(const_iterator const& first, const_iterator const& last)
108  {
109  m_vector.erase(m_vector.begin() + (first - m_vector.begin()),
110  m_vector.begin() + (last - m_vector.begin()));
111  }
112 
117  Value erase_extract( size_t index )
118  {
119  Value val = std::move(m_vector[index]);
120  m_vector.erase(m_vector.begin() + index);
121  return val;
122  }
123 
124  void clear()
125  {
126  m_vector.clear();
127  }
128 
129  void swap(sorted_vector & other)
130  {
131  m_vector.swap(other.m_vector);
132  }
133 
134  void reserve(size_type amount)
135  {
136  m_vector.reserve(amount);
137  }
138 
139  // ACCESSORS
140 
141  size_type size() const
142  {
143  return m_vector.size();
144  }
145 
146  bool empty() const
147  {
148  return m_vector.empty();
149  }
150 
151  // Only return a const iterator, so that the vector cannot be directly updated.
152  const_iterator begin() const
153  {
154  return m_vector.begin();
155  }
156 
157  // Only return a const iterator, so that the vector cannot be directly updated.
158  const_iterator end() const
159  {
160  return m_vector.end();
161  }
162 
163  // Only return a const iterator, so that the vector cannot be directly updated.
164  const_reverse_iterator rbegin() const
165  {
166  return m_vector.rbegin();
167  }
168 
169  // Only return a const iterator, so that the vector cannot be directly updated.
170  const_reverse_iterator rend() const
171  {
172  return m_vector.rend();
173  }
174 
175  const Value& front() const
176  {
177  return m_vector.front();
178  }
179 
180  const Value& back() const
181  {
182  return m_vector.back();
183  }
184 
185  const Value& operator[]( size_t index ) const
186  {
187  return m_vector.operator[]( index );
188  }
189 
190  // OPERATIONS
191 
192  const_iterator lower_bound( const Value& x ) const
193  {
194  return std::lower_bound( m_vector.begin(), m_vector.end(), x, Compare() );
195  }
196 
197  const_iterator upper_bound( const Value& x ) const
198  {
199  return std::upper_bound( m_vector.begin(), m_vector.end(), x, Compare() );
200  }
201 
202  /* Searches the container for an element with a value of x
203  * and returns an iterator to it if found, otherwise it returns an
204  * iterator to sorted_vector::end (the element past the end of the container).
205  *
206  * Only return a const iterator, so that the vector cannot be directly updated.
207  */
208  const_iterator find( const Value& x ) const
209  {
210  std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
211  return (ret.second) ? ret.first : m_vector.end();
212  }
213 
214  size_type count(const Value& v) const
215  {
216  return find(v) != end() ? 1 : 0;
217  }
218 
219  bool operator==(const sorted_vector & other) const
220  {
221  return m_vector == other.m_vector;
222  }
223 
224  bool operator!=(const sorted_vector & other) const
225  {
226  return m_vector != other.m_vector;
227  }
228 
230  {
231  // optimization for the rather common case that we are overwriting this with the contents
232  // of another sorted vector
233  if ( empty() )
234  {
235  m_vector.insert(m_vector.begin(), rOther.m_vector.begin(), rOther.m_vector.end());
236  }
237  else
238  {
239  for (const_iterator it = rOther.m_vector.begin(); it != rOther.m_vector.end(); ++it)
240  {
241  insert(*it);
242  }
243  }
244  }
245 
246  /* Clear() elements in the vector, and free them one by one. */
248  {
249  for (const_iterator it = m_vector.begin(); it != m_vector.end(); ++it)
250  {
251  delete *it;
252  }
253 
254  clear();
255  }
256 
257  // fdo#58793: some existing code in Writer (SwpHintsArray)
258  // routinely modifies the members of the vector in a way that
259  // violates the sort order, and then re-sorts the array.
260  // This is a kludge to enable that code to work.
261  // If you are calling this function, you are Doing It Wrong!
262  void Resort()
263  {
264  std::stable_sort(m_vector.begin(), m_vector.end(), Compare());
265  }
266 
267 private:
268 
269  vector_t m_vector;
270 };
271 
272 /* Specialise the template for cases like Value = std::unique_ptr<T>, where
273  MSVC2017 needs some help
274 */
275 template<
276  typename Value,
277  typename Compare,
278  template<typename, typename> class Find >
279 class sorted_vector<Value,Compare,Find,false> : public sorted_vector<Value, Compare, Find, true>
280 {
281 public:
284 
285  sorted_vector(sorted_vector const&) = delete;
286  sorted_vector& operator=(sorted_vector const&) = delete;
287 
288  sorted_vector() = default;
289  sorted_vector(sorted_vector&&) = default;
290  sorted_vector& operator=(sorted_vector&&) = default;
291 
295  typename super_sorted_vector::const_iterator find( typename Value::element_type const * x ) const
296  {
297  Value tmp(const_cast<typename Value::element_type*>(x));
298  auto ret = super_sorted_vector::find(tmp);
299  tmp.release();
300  return ret;
301  }
305  typename super_sorted_vector::const_iterator upper_bound( typename Value::element_type const * x ) const
306  {
307  Value tmp(const_cast<typename Value::element_type*>(x));
308  auto ret = super_sorted_vector::upper_bound(tmp);
309  tmp.release();
310  return ret;
311  }
315  typename super_sorted_vector::const_iterator lower_bound( typename Value::element_type const * x ) const
316  {
317  Value tmp(const_cast<typename Value::element_type*>(x));
318  auto ret = super_sorted_vector::lower_bound(tmp);
319  tmp.release();
320  return ret;
321  }
322 };
323 
324 
328 template <class T> struct less_ptr_to
329 {
330  bool operator() ( T* const& lhs, T* const& rhs ) const
331  {
332  return (*lhs) < (*rhs);
333  }
334 };
335 
336 template <class T> struct less_uniqueptr_to
337 {
338  bool operator() ( std::unique_ptr<T> const& lhs, std::unique_ptr<T> const& rhs ) const
339  {
340  return (*lhs) < (*rhs);
341  }
342 };
343 
347 template<class Value, class Compare>
348 struct find_unique
349 {
350  typedef typename sorted_vector<Value, Compare,
352  std::pair<const_iterator, bool> operator()(
353  const_iterator first, const_iterator last,
354  Value const& v)
355  {
356  const_iterator const it = std::lower_bound(first, last, v, Compare());
357  return std::make_pair(it, (it != last && !Compare()(v, *it)));
358  }
359 };
360 
364 template<class Value, class Compare>
366 {
367  typedef typename sorted_vector<Value, Compare,
369  std::pair<const_iterator, bool> operator()(
370  const_iterator first, const_iterator last,
371  Value const& v)
372  {
373  std::pair<const_iterator, const_iterator> const its =
374  std::equal_range(first, last, v, Compare());
375  for (const_iterator it = its.first; it != its.second; ++it)
376  {
377  if (v == *it)
378  {
379  return std::make_pair(it, true);
380  }
381  }
382  return std::make_pair(its.first, false);
383  }
384 };
385 
386 } // namespace o3tl
387 #endif
388 
389 /* 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
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
void erase(size_t index)
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)