Line data Source code
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 <functional>
15 : #include <algorithm>
16 :
17 : namespace o3tl
18 : {
19 :
20 : // forward declared because it's default tempate arg for sorted_vector
21 : template<class Value, class Compare>
22 : struct find_unique;
23 :
24 : /** Represents a sorted vector of values.
25 :
26 : @tpl Value class of item to be stored in container
27 : @tpl Compare comparison method
28 : @tpl Find look up index of a Value in the array
29 : */
30 : template<typename Value, typename Compare = std::less<Value>,
31 : template<typename, typename> class Find = find_unique >
32 27341 : class sorted_vector
33 : : private std::vector<Value>
34 : {
35 : private:
36 : typedef Find<Value, Compare> Find_t;
37 : typedef typename std::vector<Value> base_t;
38 : typedef typename std::vector<Value>::iterator iterator;
39 : public:
40 : typedef typename std::vector<Value>::const_iterator const_iterator;
41 : typedef typename std::vector<Value>::size_type size_type;
42 :
43 : using base_t::clear;
44 : using base_t::empty;
45 : using base_t::size;
46 :
47 : // MODIFIERS
48 :
49 29297 : std::pair<const_iterator,bool> insert( const Value& x )
50 : {
51 29297 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
52 29297 : if (!ret.second)
53 : {
54 : const_iterator const it = base_t::insert(
55 29268 : begin_nonconst() + (ret.first - begin()), x);
56 29268 : return std::make_pair(it, true);
57 : }
58 29 : return std::make_pair(ret.first, false);
59 : }
60 :
61 9535 : size_type erase( const Value& x )
62 : {
63 9535 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
64 9535 : if (ret.second)
65 : {
66 9530 : base_t::erase(begin_nonconst() + (ret.first - begin()));
67 9530 : return 1;
68 : }
69 5 : return 0;
70 : }
71 :
72 2 : void erase( size_t index )
73 : {
74 2 : base_t::erase( begin_nonconst() + index );
75 2 : }
76 :
77 : // like C++ 2011: erase with const_iterator (doesn't change sort order)
78 9411 : void erase(const_iterator const& position)
79 : { // C++98 has vector::erase(iterator), so call that
80 9411 : base_t::erase(begin_nonconst() + (position - begin()));
81 9411 : }
82 :
83 594 : void erase(const_iterator const& first, const_iterator const& last)
84 : {
85 594 : base_t::erase(begin_nonconst() + (first - begin()),
86 : begin_nonconst() + (last - begin()));
87 594 : }
88 :
89 : // ACCESSORS
90 :
91 : // Only return a const iterator, so that the vector cannot be directly updated.
92 121434 : const_iterator begin() const
93 : {
94 121434 : return base_t::begin();
95 : }
96 :
97 : // Only return a const iterator, so that the vector cannot be directly updated.
98 66090 : const_iterator end() const
99 : {
100 66090 : return base_t::end();
101 : }
102 :
103 254 : const Value& front() const
104 : {
105 254 : return base_t::front();
106 : }
107 :
108 2 : const Value& back() const
109 : {
110 2 : return base_t::back();
111 : }
112 :
113 1752716 : const Value& operator[]( size_t index ) const
114 : {
115 1752716 : return base_t::operator[]( index );
116 : }
117 :
118 : // OPERATIONS
119 :
120 2 : const_iterator lower_bound( const Value& x ) const
121 : {
122 2 : return std::lower_bound( base_t::begin(), base_t::end(), x, Compare() );
123 : }
124 :
125 : /* Searches the container for an element with a value of x
126 : * and returns an iterator to it if found, otherwise it returns an
127 : * iterator to sorted_vector::end (the element past the end of the container).
128 : *
129 : * Only return a const iterator, so that the vector cannot be directly updated.
130 : */
131 12154 : const_iterator find( const Value& x ) const
132 : {
133 12154 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
134 12154 : return (ret.second) ? ret.first : end();
135 : }
136 :
137 1 : void insert(sorted_vector<Value,Compare,Find> const& rOther)
138 : {
139 : // optimisation for the rather common case that we are overwriting this with the contents
140 : // of another sorted vector
141 1 : if ( empty() )
142 : {
143 1 : base_t::insert(begin_nonconst(), rOther.begin(), rOther.end());
144 : }
145 : else
146 0 : for( const_iterator it = rOther.begin(); it != rOther.end(); ++it )
147 0 : insert( *it );
148 1 : }
149 :
150 : /* Clear() elements in the vector, and free them one by one. */
151 280 : void DeleteAndDestroyAll()
152 : {
153 379 : for( const_iterator it = begin(); it != end(); ++it )
154 99 : delete *it;
155 280 : clear();
156 280 : }
157 :
158 : private:
159 :
160 49400 : typename base_t::iterator begin_nonconst() { return base_t::begin(); }
161 : typename base_t::iterator end_nonconst() { return base_t::end(); }
162 :
163 : };
164 :
165 :
166 : /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
167 : Very useful for the cases where we put pointers to objects inside a sorted_vector.
168 : */
169 : template <class T> struct less_ptr_to : public std::binary_function <T*,T*,bool>
170 : {
171 479 : bool operator() ( T* const& lhs, T* const& rhs ) const
172 : {
173 479 : return (*lhs) < (*rhs);
174 : }
175 : };
176 :
177 : /** the elements are totally ordered by Compare,
178 : for no 2 elements !Compare(a,b) && !Compare(b,a) is true
179 : */
180 : template<class Value, class Compare>
181 : struct find_unique
182 : {
183 : typedef typename sorted_vector<Value, Compare,
184 : o3tl::find_unique> ::const_iterator const_iterator;
185 7357 : std::pair<const_iterator, bool> operator()(
186 : const_iterator first, const_iterator last,
187 : Value const& v)
188 : {
189 7357 : const_iterator const it = std::lower_bound(first, last, v, Compare());
190 7357 : return std::make_pair(it, (it != last && !Compare()(v, *it)));
191 : }
192 : };
193 :
194 : /** the elments are partially ordered by Compare,
195 : 2 elements are allowed if they are not the same element (pointer equal)
196 : */
197 : template<class Value, class Compare>
198 : struct find_partialorder_ptrequals
199 : {
200 : typedef typename sorted_vector<Value, Compare,
201 : o3tl::find_partialorder_ptrequals>::const_iterator const_iterator;
202 43629 : std::pair<const_iterator, bool> operator()(
203 : const_iterator first, const_iterator last,
204 : Value const& v)
205 : {
206 : std::pair<const_iterator, const_iterator> const its =
207 43629 : std::equal_range(first, last, v, Compare());
208 43662 : for (const_iterator it = its.first; it != its.second; ++it)
209 : {
210 18109 : if (v == *it)
211 : {
212 18076 : return std::make_pair(it, true);
213 : }
214 : }
215 25553 : return std::make_pair(its.first, false);
216 : }
217 : };
218 :
219 : } // namespace o3tl
220 : #endif
221 :
222 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
