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