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 798245 : class sorted_vector
33 : {
34 : private:
35 : typedef Find<Value, Compare> Find_t;
36 : typedef typename std::vector<Value> vector_t;
37 : typedef typename std::vector<Value>::iterator iterator;
38 : public:
39 : typedef typename std::vector<Value>::const_iterator const_iterator;
40 : typedef typename std::vector<Value>::size_type size_type;
41 :
42 : // MODIFIERS
43 :
44 378562 : std::pair<const_iterator,bool> insert( const Value& x )
45 : {
46 378562 : std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
47 378562 : if (!ret.second)
48 : {
49 245157 : const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), x);
50 245157 : return std::make_pair(it, true);
51 : }
52 133405 : return std::make_pair(ret.first, false);
53 : }
54 :
55 48964 : size_type erase( const Value& x )
56 : {
57 48964 : std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
58 48964 : if (ret.second)
59 : {
60 48959 : m_vector.erase(m_vector.begin() + (ret.first - m_vector.begin()));
61 48959 : return 1;
62 : }
63 5 : return 0;
64 : }
65 :
66 71 : void erase( size_t index )
67 : {
68 71 : m_vector.erase(m_vector.begin() + index);
69 71 : }
70 :
71 : // like C++ 2011: erase with const_iterator (doesn't change sort order)
72 45826 : void erase(const_iterator const& position)
73 : { // C++98 has vector::erase(iterator), so call that
74 45826 : m_vector.erase(m_vector.begin() + (position - m_vector.begin()));
75 45826 : }
76 :
77 7808 : void erase(const_iterator const& first, const_iterator const& last)
78 : {
79 15616 : m_vector.erase(m_vector.begin() + (first - m_vector.begin()),
80 23424 : m_vector.begin() + (last - m_vector.begin()));
81 7808 : }
82 :
83 24192 : void clear()
84 : {
85 24192 : m_vector.clear();
86 24192 : }
87 :
88 : // ACCESSORS
89 :
90 132465864 : size_type size() const
91 : {
92 132465864 : return m_vector.size();
93 : }
94 :
95 27145015 : bool empty() const
96 : {
97 27145015 : return m_vector.empty();
98 : }
99 :
100 : // Only return a const iterator, so that the vector cannot be directly updated.
101 182385 : const_iterator begin() const
102 : {
103 182385 : return m_vector.begin();
104 : }
105 :
106 : // Only return a const iterator, so that the vector cannot be directly updated.
107 135025 : const_iterator end() const
108 : {
109 135025 : return m_vector.end();
110 : }
111 :
112 2497 : const Value& front() const
113 : {
114 2497 : return m_vector.front();
115 : }
116 :
117 27 : const Value& back() const
118 : {
119 27 : return m_vector.back();
120 : }
121 :
122 38858296 : const Value& operator[]( size_t index ) const
123 : {
124 38858296 : return m_vector.operator[]( index );
125 : }
126 :
127 : // OPERATIONS
128 :
129 1910 : const_iterator lower_bound( const Value& x ) const
130 : {
131 1910 : return std::lower_bound( m_vector.begin(), m_vector.end(), x, Compare() );
132 : }
133 :
134 0 : const_iterator upper_bound( const Value& x ) const
135 : {
136 0 : return std::upper_bound( m_vector.begin(), m_vector.end(), x, Compare() );
137 : }
138 :
139 : /* Searches the container for an element with a value of x
140 : * and returns an iterator to it if found, otherwise it returns an
141 : * iterator to sorted_vector::end (the element past the end of the container).
142 : *
143 : * Only return a const iterator, so that the vector cannot be directly updated.
144 : */
145 145041 : const_iterator find( const Value& x ) const
146 : {
147 145041 : std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x));
148 145041 : return (ret.second) ? ret.first : m_vector.end();
149 : }
150 :
151 26 : void insert(sorted_vector<Value,Compare,Find> const& rOther)
152 : {
153 : // optimization for the rather common case that we are overwriting this with the contents
154 : // of another sorted vector
155 26 : if ( empty() )
156 : {
157 26 : m_vector.insert(m_vector.begin(), rOther.m_vector.begin(), rOther.m_vector.end());
158 : }
159 : else
160 : {
161 0 : for (const_iterator it = rOther.m_vector.begin(); it != rOther.m_vector.end(); ++it)
162 : {
163 0 : insert(*it);
164 : }
165 : }
166 26 : }
167 :
168 : /* Clear() elements in the vector, and free them one by one. */
169 7323 : void DeleteAndDestroyAll()
170 : {
171 27187 : for (const_iterator it = m_vector.begin(); it != m_vector.end(); ++it)
172 : {
173 19864 : delete *it;
174 : }
175 :
176 7323 : clear();
177 7323 : }
178 :
179 : // fdo#58793: some existing code in Writer (SwpHintsArray)
180 : // routinely modifies the members of the vector in a way that
181 : // violates the sort order, and then re-sorts the array.
182 : // This is a kludge to enable that code to work.
183 : // If you are calling this function, you are Doing It Wrong!
184 462624 : void Resort()
185 : {
186 462624 : std::stable_sort(m_vector.begin(), m_vector.end(), Compare());
187 462624 : }
188 :
189 : private:
190 :
191 : vector_t m_vector;
192 : };
193 :
194 :
195 : /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
196 : Very useful for the cases where we put pointers to objects inside a sorted_vector.
197 : */
198 : template <class T> struct less_ptr_to : public std::binary_function <T*,T*,bool>
199 : {
200 162591 : bool operator() ( T* const& lhs, T* const& rhs ) const
201 : {
202 162591 : return (*lhs) < (*rhs);
203 : }
204 : };
205 :
206 : /** the elements are totally ordered by Compare,
207 : for no 2 elements !Compare(a,b) && !Compare(b,a) is true
208 : */
209 : template<class Value, class Compare>
210 : struct find_unique
211 : {
212 : typedef typename sorted_vector<Value, Compare,
213 : o3tl::find_unique> ::const_iterator const_iterator;
214 313855 : std::pair<const_iterator, bool> operator()(
215 : const_iterator first, const_iterator last,
216 : Value const& v)
217 : {
218 313855 : const_iterator const it = std::lower_bound(first, last, v, Compare());
219 313855 : return std::make_pair(it, (it != last && !Compare()(v, *it)));
220 : }
221 : };
222 :
223 : /** the elements are partially ordered by Compare,
224 : 2 elements are allowed if they are not the same element (pointer equal)
225 : */
226 : template<class Value, class Compare>
227 : struct find_partialorder_ptrequals
228 : {
229 : typedef typename sorted_vector<Value, Compare,
230 : o3tl::find_partialorder_ptrequals>::const_iterator const_iterator;
231 258712 : std::pair<const_iterator, bool> operator()(
232 : const_iterator first, const_iterator last,
233 : Value const& v)
234 : {
235 : std::pair<const_iterator, const_iterator> const its =
236 258712 : std::equal_range(first, last, v, Compare());
237 259276 : for (const_iterator it = its.first; it != its.second; ++it)
238 : {
239 87632 : if (v == *it)
240 : {
241 87068 : return std::make_pair(it, true);
242 : }
243 : }
244 171644 : return std::make_pair(its.first, false);
245 : }
246 : };
247 :
248 : } // namespace o3tl
249 : #endif
250 :
251 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
