Branch data 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 : 271560 : 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 : 83074 : std::pair<const_iterator,bool> insert( const Value& x )
50 : : {
51 [ + - ][ + - ]: 83074 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
[ + - ]
52 [ + + ][ + + ]: 83074 : if (!ret.second)
[ + - ]
53 : : {
54 : : const_iterator const it = base_t::insert(
55 [ + - + - ]: 80657 : begin_nonconst() + (ret.first - begin()), x);
[ + + - ]
[ + + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
56 [ + - ][ + - ]: 80657 : return std::make_pair(it, true);
[ + - ]
57 : : }
58 [ + - ][ + - ]: 83074 : return std::make_pair(ret.first, false);
[ # # ]
59 : : }
60 : :
61 : 23859 : size_type erase( const Value& x )
62 : : {
63 [ + - ][ + - ]: 23859 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
64 [ + + ][ + + ]: 23859 : if (ret.second)
65 : : {
66 [ + - ][ + - ]: 23834 : base_t::erase(begin_nonconst() + (ret.first - begin()));
[ + - ][ + - ]
[ + - ][ + - ]
67 : 23834 : return 1;
68 : : }
69 : 23859 : return 0;
70 : : }
71 : :
72 : 10 : void erase( size_t index )
73 : : {
74 [ + - ][ + - ]: 10 : base_t::erase( begin_nonconst() + index );
[ + - ][ + - ]
75 : 10 : }
76 : :
77 : : // like C++ 2011: erase with const_iterator (doesn't change sort order)
78 : 23181 : void erase(const_iterator const& position)
79 : : { // C++98 has vector::erase(iterator), so call that
80 [ + - ][ + - ]: 23181 : base_t::erase(begin_nonconst() + (position - begin()));
[ + - ][ + - ]
[ + - ][ + - ]
81 : 23181 : }
82 : :
83 : 2128 : void erase(const_iterator const& first, const_iterator const& last)
84 : : {
85 [ + - ][ + - ]: 2128 : base_t::erase(begin_nonconst() + (first - begin()),
[ + - ][ + - ]
[ + - ]
86 : : begin_nonconst() + (last - begin()));
87 : 2128 : }
88 : :
89 : : // ACCESSORS
90 : :
91 : : // Only return a const iterator, so that the vector cannot be directly updated.
92 : 325332 : const_iterator begin() const
93 : : {
94 : 325332 : return base_t::begin();
95 : : }
96 : :
97 : : // Only return a const iterator, so that the vector cannot be directly updated.
98 : 181583 : const_iterator end() const
99 : : {
100 : 181583 : return base_t::end();
101 : : }
102 : :
103 : 648 : const Value& front() const
104 : : {
105 : 648 : return base_t::front();
106 : : }
107 : :
108 : 40 : const Value& back() const
109 : : {
110 : 40 : return base_t::back();
111 : : }
112 : :
113 : 3232712 : const Value& operator[]( size_t index ) const
114 : : {
115 : 3232712 : return base_t::operator[]( index );
116 : : }
117 : :
118 : : // OPERATIONS
119 : :
120 : 14 : const_iterator lower_bound( const Value& x ) const
121 : : {
122 [ + - ]: 14 : 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 : 22825 : const_iterator find( const Value& x ) const
132 : : {
133 [ + - ][ + - ]: 22825 : std::pair<const_iterator, bool> const ret(Find_t()(begin(), end(), x));
134 [ + + ][ + + ]: 22825 : return (ret.second) ? ret.first : end();
135 : : }
136 : :
137 : 35 : void insert( sorted_vector<Value,Compare,Find> &rOther )
138 : : {
139 : : // optimisation for the rather common case that we are overwriting this with the contents
140 : : // of another sorted vector
141 [ + - ]: 35 : if ( empty() )
142 : : {
143 : 35 : base_t::insert( begin_nonconst(),
144 : : rOther.begin_nonconst(), rOther.end_nonconst() );
145 : : }
146 : : else
147 [ # # ]: 0 : for( const_iterator it = rOther.begin(); it != rOther.end(); ++it )
[ # # # # ]
[ # # # # ]
148 [ # # # ]: 0 : insert( *it );
[ # # ]
149 : 35 : }
150 : :
151 : : /* Clear() elements in the vector, and free them one by one. */
152 : 4912 : void DeleteAndDestroyAll()
153 : : {
154 [ # # ][ + - : 6450 : for( const_iterator it = begin(); it != end(); ++it )
+ - # # ]
[ + - + +
+ # # ]
[ + + + + ]
[ + - ][ + -
+ + # ]
[ - + # # ]
155 [ + + - ]: 1538 : delete *it;
[ + - ]
[ # + - ]
[ # # ][ # # ]
156 : 4912 : clear();
157 : 4912 : }
158 : :
159 : : private:
160 : :
161 : 132008 : typename base_t::iterator begin_nonconst() { return base_t::begin(); }
162 : 35 : typename base_t::iterator end_nonconst() { return base_t::end(); }
163 : :
164 : : };
165 : :
166 : :
167 : : /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types.
168 : : Very useful for the cases where we put pointers to objects inside a sorted_vector.
169 : : */
170 : : template <class T> struct less_ptr_to : public std::binary_function <T*,T*,bool>
171 : : {
172 : 1182 : bool operator() ( T* const& lhs, T* const& rhs ) const
173 : : {
174 : 1182 : return (*lhs) < (*rhs);
175 : : }
176 : : };
177 : :
178 : : /** the elements are totally ordered by Compare,
179 : : for no 2 elements !Compare(a,b) && !Compare(b,a) is true
180 : : */
181 : : template<class Value, class Compare>
182 : : struct find_unique
183 : : {
184 : : typedef typename sorted_vector<Value, Compare,
185 : : o3tl::find_unique> ::const_iterator const_iterator;
186 : 30516 : std::pair<const_iterator, bool> operator()(
187 : : const_iterator first, const_iterator last,
188 : : Value const& v)
189 : : {
190 [ + - ][ # # ]: 30516 : const_iterator const it = std::lower_bound(first, last, v, Compare());
[ + - ]
191 [ + + + ]: 30516 : return std::make_pair(it, (it != last && !Compare()(v, *it)));
[ + + - ]
[ + + + + ]
[ + + + ]
[ + + ][ + - ]
[ + + + ]
[ + + + ]
[ + + ][ # # ]
[ # # ][ # # ]
[ # # # ]
[ # # # # ]
[ # # # #
# ]
[ # # # # ]
[ # # # # ]
[ # # # # ]
[ # # # #
# ][ # # # ]
[ # # ]
[ # # # # ]
[ # # # # ]
[ # # ][ # # ]
[ + - ][ - + ]
[ # # ][ + - ]
[ - + ][ # # ]
192 : : }
193 : : };
194 : :
195 : : /** the elments are partially ordered by Compare,
196 : : 2 elements are allowed if they are not the same element (pointer equal)
197 : : */
198 : : template<class Value, class Compare>
199 : : struct find_partialorder_ptrequals
200 : : {
201 : : typedef typename sorted_vector<Value, Compare,
202 : : o3tl::find_partialorder_ptrequals>::const_iterator const_iterator;
203 : 106662 : std::pair<const_iterator, bool> operator()(
204 : : const_iterator first, const_iterator last,
205 : : Value const& v)
206 : : {
207 : : std::pair<const_iterator, const_iterator> const its =
208 [ + - ][ + - ]: 106662 : std::equal_range(first, last, v, Compare());
209 [ + + + ]: 106827 : for (const_iterator it = its.first; it != its.second; ++it)
[ + + ][ + + ]
210 : : {
211 [ + + ][ + - ]: 42266 : if (v == *it)
212 : : {
213 : 42101 : return std::make_pair(it, true);
214 : : }
215 : : }
216 [ + - ][ + - ]: 106662 : return std::make_pair(its.first, false);
217 : : }
218 : : };
219 : :
220 : : } // namespace o3tl
221 : : #endif
222 : :
223 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
