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 1365951 : 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 418061 : std::pair<const_iterator,bool> insert( const Value& x )
50 : {
51 418061 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
52 418061 : if (!ret.second)
53 : {
54 : const_iterator const it = base_t::insert(
55 412315 : begin_nonconst() + (ret.first - begin()), x);
56 412315 : return std::make_pair(it, true);
57 : }
58 5746 : return std::make_pair(ret.first, false);
59 : }
60 :
61 89686 : size_type erase( const Value& x )
62 : {
63 89686 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
64 89686 : if (ret.second)
65 : {
66 89676 : base_t::erase(begin_nonconst() + (ret.first - begin()));
67 89676 : return 1;
68 : }
69 10 : return 0;
70 : }
71 :
72 86 : void erase( size_t index )
73 : {
74 86 : base_t::erase( begin_nonconst() + index );
75 86 : }
76 :
77 : // like C++ 2011: erase with const_iterator (doesn't change sort order)
78 87740 : void erase(const_iterator const& position)
79 : { // C++98 has vector::erase(iterator), so call that
80 87740 : base_t::erase(begin_nonconst() + (position - begin()));
81 87740 : }
82 :
83 12892 : void erase(const_iterator const& first, const_iterator const& last)
84 : {
85 38676 : base_t::erase(begin_nonconst() + (first - begin()),
86 51568 : begin_nonconst() + (last - begin()));
87 12892 : }
88 :
89 : // ACCESSORS
90 :
91 : // Only return a const iterator, so that the vector cannot be directly updated.
92 1550761 : const_iterator begin() const
93 : {
94 1550761 : return base_t::begin();
95 : }
96 :
97 : // Only return a const iterator, so that the vector cannot be directly updated.
98 919981 : const_iterator end() const
99 : {
100 919981 : return base_t::end();
101 : }
102 :
103 4212 : const Value& front() const
104 : {
105 4212 : return base_t::front();
106 : }
107 :
108 42 : const Value& back() const
109 : {
110 42 : return base_t::back();
111 : }
112 :
113 11004284 : const Value& operator[]( size_t index ) const
114 : {
115 11004284 : return base_t::operator[]( index );
116 : }
117 :
118 : // OPERATIONS
119 :
120 1588 : const_iterator lower_bound( const Value& x ) const
121 : {
122 1588 : return std::lower_bound( base_t::begin(), base_t::end(), x, Compare() );
123 : }
124 :
125 0 : const_iterator upper_bound( const Value& x ) const
126 : {
127 0 : return std::upper_bound( base_t::begin(), base_t::end(), x, Compare() );
128 : }
129 :
130 : /* Searches the container for an element with a value of x
131 : * and returns an iterator to it if found, otherwise it returns an
132 : * iterator to sorted_vector::end (the element past the end of the container).
133 : *
134 : * Only return a const iterator, so that the vector cannot be directly updated.
135 : */
136 169336 : const_iterator find( const Value& x ) const
137 : {
138 169336 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
139 169336 : return (ret.second) ? ret.first : end();
140 : }
141 :
142 28 : void insert(sorted_vector<Value,Compare,Find> const& rOther)
143 : {
144 : // optimization for the rather common case that we are overwriting this with the contents
145 : // of another sorted vector
146 28 : if ( empty() )
147 : {
148 28 : base_t::insert(begin_nonconst(), rOther.begin(), rOther.end());
149 : }
150 : else
151 0 : for( const_iterator it = rOther.begin(); it != rOther.end(); ++it )
152 0 : insert( *it );
153 28 : }
154 :
155 : /* Clear() elements in the vector, and free them one by one. */
156 9228 : void DeleteAndDestroyAll()
157 : {
158 14936 : for( const_iterator it = begin(); it != end(); ++it )
159 5708 : delete *it;
160 9228 : clear();
161 9228 : }
162 :
163 : // fdo#58793: some existing code in Writer (SwpHintsArray)
164 : // routinely modifies the members of the vector in a way that
165 : // violates the sort order, and then re-sorts the array.
166 : // This is a kludge to enable that code to work.
167 : // If you are calling this function, you are Doing It Wrong!
168 881516 : void Resort()
169 : {
170 881516 : std::stable_sort(begin_nonconst(), end_nonconst(), Compare());
171 881516 : }
172 :
173 : private:
174 :
175 1497145 : typename base_t::iterator begin_nonconst() { return base_t::begin(); }
176 881516 : typename base_t::iterator end_nonconst() { return base_t::end(); }
177 :
178 : };
179 :
180 :
181 : /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
182 : Very useful for the cases where we put pointers to objects inside a sorted_vector.
183 : */
184 : template <class T> struct less_ptr_to : public std::binary_function <T*,T*,bool>
185 : {
186 13026 : bool operator() ( T* const& lhs, T* const& rhs ) const
187 : {
188 13026 : return (*lhs) < (*rhs);
189 : }
190 : };
191 :
192 : /** the elements are totally ordered by Compare,
193 : for no 2 elements !Compare(a,b) && !Compare(b,a) is true
194 : */
195 : template<class Value, class Compare>
196 : struct find_unique
197 : {
198 : typedef typename sorted_vector<Value, Compare,
199 : o3tl::find_unique> ::const_iterator const_iterator;
200 183384 : std::pair<const_iterator, bool> operator()(
201 : const_iterator first, const_iterator last,
202 : Value const& v)
203 : {
204 183384 : const_iterator const it = std::lower_bound(first, last, v, Compare());
205 183384 : return std::make_pair(it, (it != last && !Compare()(v, *it)));
206 : }
207 : };
208 :
209 : /** the elements are partially ordered by Compare,
210 : 2 elements are allowed if they are not the same element (pointer equal)
211 : */
212 : template<class Value, class Compare>
213 : struct find_partialorder_ptrequals
214 : {
215 : typedef typename sorted_vector<Value, Compare,
216 : o3tl::find_partialorder_ptrequals>::const_iterator const_iterator;
217 493699 : std::pair<const_iterator, bool> operator()(
218 : const_iterator first, const_iterator last,
219 : Value const& v)
220 : {
221 : std::pair<const_iterator, const_iterator> const its =
222 493699 : std::equal_range(first, last, v, Compare());
223 494827 : for (const_iterator it = its.first; it != its.second; ++it)
224 : {
225 166110 : if (v == *it)
226 : {
227 164982 : return std::make_pair(it, true);
228 : }
229 : }
230 328717 : return std::make_pair(its.first, false);
231 : }
232 : };
233 :
234 : } // namespace o3tl
235 : #endif
236 :
237 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
