1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * This file is part of the LibreOffice project.
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/.
10 #ifndef INCLUDED_O3TL_SORTED_VECTOR_HXX
11 #define INCLUDED_O3TL_SORTED_VECTOR_HXX
17 #include <type_traits>
22 // forward declared because it's default template arg for sorted_vector
23 template<class Value
, class Compare
>
26 /** Represents a sorted vector of values.
28 @tpl Value class of item to be stored in container
29 @tpl Compare comparison method
30 @tpl Find look up index of a Value in the array
34 typename Compare
= std::less
<Value
>,
35 template<typename
, typename
> class Find
= find_unique
,
36 bool = std::is_copy_constructible
<Value
>::value
>
40 typedef Find
<Value
, Compare
> Find_t
;
41 typedef typename
std::vector
<Value
> vector_t
;
42 typedef typename
std::vector
<Value
>::iterator iterator
;
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
;
50 std::pair
<const_iterator
,bool> insert( Value
&& x
)
52 std::pair
<const_iterator
, bool> const ret(Find_t()(m_vector
.begin(), m_vector
.end(), x
));
55 const_iterator
const it
= m_vector
.insert(m_vector
.begin() + (ret
.first
- m_vector
.begin()), std::move(x
));
56 return std::make_pair(it
, true);
58 return std::make_pair(ret
.first
, false);
61 std::pair
<const_iterator
,bool> insert( const Value
& x
)
63 std::pair
<const_iterator
, bool> const ret(Find_t()(m_vector
.begin(), m_vector
.end(), x
));
66 const_iterator
const it
= m_vector
.insert(m_vector
.begin() + (ret
.first
- m_vector
.begin()), x
);
67 return std::make_pair(it
, true);
69 return std::make_pair(ret
.first
, false);
72 size_type
erase( const Value
& x
)
74 std::pair
<const_iterator
, bool> const ret(Find_t()(m_vector
.begin(), m_vector
.end(), x
));
77 m_vector
.erase(m_vector
.begin() + (ret
.first
- m_vector
.begin()));
83 void erase( size_t index
)
85 m_vector
.erase(m_vector
.begin() + index
);
88 // like C++ 2011: erase with const_iterator (doesn't change sort order)
89 void erase(const_iterator
const& position
)
90 { // C++98 has vector::erase(iterator), so call that
91 m_vector
.erase(m_vector
.begin() + (position
- m_vector
.begin()));
94 void erase(const_iterator
const& first
, const_iterator
const& last
)
96 m_vector
.erase(m_vector
.begin() + (first
- m_vector
.begin()),
97 m_vector
.begin() + (last
- m_vector
.begin()));
101 * make erase return the removed element, otherwise there is no useful way of extracting a std::unique_ptr
104 Value
erase_extract( size_t index
)
106 Value val
= std::move(m_vector
[index
]);
107 m_vector
.erase(m_vector
.begin() + index
);
116 void swap(sorted_vector
& other
)
118 m_vector
.swap(other
.m_vector
);
121 void reserve(size_type amount
)
123 m_vector
.reserve(amount
);
128 size_type
size() const
130 return m_vector
.size();
135 return m_vector
.empty();
138 // Only return a const iterator, so that the vector cannot be directly updated.
139 const_iterator
begin() const
141 return m_vector
.begin();
144 // Only return a const iterator, so that the vector cannot be directly updated.
145 const_iterator
end() const
147 return m_vector
.end();
150 const Value
& front() const
152 return m_vector
.front();
155 const Value
& back() const
157 return m_vector
.back();
160 const Value
& operator[]( size_t index
) const
162 return m_vector
.operator[]( index
);
167 const_iterator
lower_bound( const Value
& x
) const
169 return std::lower_bound( m_vector
.begin(), m_vector
.end(), x
, Compare() );
172 const_iterator
upper_bound( const Value
& x
) const
174 return std::upper_bound( m_vector
.begin(), m_vector
.end(), x
, Compare() );
177 /* Searches the container for an element with a value of x
178 * and returns an iterator to it if found, otherwise it returns an
179 * iterator to sorted_vector::end (the element past the end of the container).
181 * Only return a const iterator, so that the vector cannot be directly updated.
183 const_iterator
find( const Value
& x
) const
185 std::pair
<const_iterator
, bool> const ret(Find_t()(m_vector
.begin(), m_vector
.end(), x
));
186 return (ret
.second
) ? ret
.first
: m_vector
.end();
189 void insert(sorted_vector
<Value
,Compare
,Find
> const& rOther
)
191 // optimization for the rather common case that we are overwriting this with the contents
192 // of another sorted vector
195 m_vector
.insert(m_vector
.begin(), rOther
.m_vector
.begin(), rOther
.m_vector
.end());
199 for (const_iterator it
= rOther
.m_vector
.begin(); it
!= rOther
.m_vector
.end(); ++it
)
206 /* Clear() elements in the vector, and free them one by one. */
207 void DeleteAndDestroyAll()
209 for (const_iterator it
= m_vector
.begin(); it
!= m_vector
.end(); ++it
)
217 // fdo#58793: some existing code in Writer (SwpHintsArray)
218 // routinely modifies the members of the vector in a way that
219 // violates the sort order, and then re-sorts the array.
220 // This is a kludge to enable that code to work.
221 // If you are calling this function, you are Doing It Wrong!
224 std::stable_sort(m_vector
.begin(), m_vector
.end(), Compare());
232 /* Specialise the template for cases like Value = std::unique_ptr<T>, where
233 MSVC2017 needs some help
238 template<typename
, typename
> class Find
>
239 class sorted_vector
<Value
,Compare
,Find
,false> : public sorted_vector
<Value
, Compare
, Find
, true>
242 using sorted_vector
<Value
, Compare
, Find
, true>::sorted_vector
;
243 typedef sorted_vector
<Value
, Compare
, Find
, true> super_sorted_vector
;
245 sorted_vector(sorted_vector
const&) = delete;
246 sorted_vector
& operator=(sorted_vector
const&) = delete;
248 sorted_vector() = default;
249 sorted_vector(sorted_vector
&&) = default;
250 sorted_vector
& operator=(sorted_vector
&&) = default;
253 * implement find for sorted_vectors containing std::unique_ptr
255 typename
super_sorted_vector::const_iterator
find( typename
Value::element_type
const * x
) const
257 Value
tmp(const_cast<typename
Value::element_type
*>(x
));
258 auto ret
= super_sorted_vector::find(tmp
);
263 * implement upper_bound for sorted_vectors containing std::unique_ptr
265 typename
super_sorted_vector::const_iterator
upper_bound( typename
Value::element_type
const * x
) const
267 Value
tmp(const_cast<typename
Value::element_type
*>(x
));
268 auto ret
= super_sorted_vector::upper_bound(tmp
);
273 * implement lower_bound for sorted_vectors containing std::unique_ptr
275 typename
super_sorted_vector::const_iterator
lower_bound( typename
Value::element_type
const * x
) const
277 Value
tmp(const_cast<typename
Value::element_type
*>(x
));
278 auto ret
= super_sorted_vector::lower_bound(tmp
);
285 /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
286 Very useful for the cases where we put pointers to objects inside a sorted_vector.
288 template <class T
> struct less_ptr_to
290 bool operator() ( T
* const& lhs
, T
* const& rhs
) const
292 return (*lhs
) < (*rhs
);
296 template <class T
> struct less_uniqueptr_to
298 bool operator() ( std::unique_ptr
<T
> const& lhs
, std::unique_ptr
<T
> const& rhs
) const
300 return (*lhs
) < (*rhs
);
304 /** the elements are totally ordered by Compare,
305 for no 2 elements !Compare(a,b) && !Compare(b,a) is true
307 template<class Value
, class Compare
>
310 typedef typename sorted_vector
<Value
, Compare
,
311 o3tl::find_unique
> ::const_iterator const_iterator
;
312 std::pair
<const_iterator
, bool> operator()(
313 const_iterator first
, const_iterator last
,
316 const_iterator
const it
= std::lower_bound(first
, last
, v
, Compare());
317 return std::make_pair(it
, (it
!= last
&& !Compare()(v
, *it
)));
321 /** the elements are partially ordered by Compare,
322 2 elements are allowed if they are not the same element (pointer equal)
324 template<class Value
, class Compare
>
325 struct find_partialorder_ptrequals
327 typedef typename sorted_vector
<Value
, Compare
,
328 o3tl::find_partialorder_ptrequals
>::const_iterator const_iterator
;
329 std::pair
<const_iterator
, bool> operator()(
330 const_iterator first
, const_iterator last
,
333 std::pair
<const_iterator
, const_iterator
> const its
=
334 std::equal_range(first
, last
, v
, Compare());
335 for (const_iterator it
= its
.first
; it
!= its
.second
; ++it
)
339 return std::make_pair(it
, true);
342 return std::make_pair(its
.first
, false);
349 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */