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 <algorithm> 15 #include <functional> 16 #include <memory> 17 #include <type_traits> 18 19 namespace o3tl 20 { 21 22 // forward declared because it's default template arg for sorted_vector 23 template<class Value, class Compare> 24 struct find_unique; 25 26 /** Represents a sorted vector of values. 27 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 31 */ 32 template< 33 typename Value, 34 typename Compare = std::less<Value>, 35 template<typename, typename> class Find = find_unique, 36 bool = std::is_copy_constructible<Value>::value > 37 class sorted_vector 38 { 39 private: 40 typedef Find<Value, Compare> Find_t; 41 typedef typename std::vector<Value> vector_t; 42 typedef typename std::vector<Value>::iterator iterator; 43 public: 44 typedef typename std::vector<Value>::const_iterator const_iterator; 45 typedef typename std::vector<Value>::const_reverse_iterator const_reverse_iterator; 46 typedef typename std::vector<Value>::difference_type difference_type; 47 typedef typename std::vector<Value>::size_type size_type; 48 typedef Value value_type; 49 sorted_vector(std::initializer_list<Value> init)50 constexpr sorted_vector( std::initializer_list<Value> init ) 51 : m_vector(init) 52 { 53 std::sort(m_vector.begin(), m_vector.end(), Compare()); 54 } 55 sorted_vector() = default; 56 sorted_vector(sorted_vector const&) = default; 57 sorted_vector(sorted_vector&&) = default; 58 59 sorted_vector& operator=(sorted_vector const&) = default; 60 sorted_vector& operator=(sorted_vector&&) = default; 61 62 // MODIFIERS 63 insert(Value && x)64 std::pair<const_iterator,bool> insert( Value&& x ) 65 { 66 std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x)); 67 if (!ret.second) 68 { 69 const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), std::move(x)); 70 return std::make_pair(it, true); 71 } 72 return std::make_pair(ret.first, false); 73 } 74 insert(const Value & x)75 std::pair<const_iterator,bool> insert( const Value& x ) 76 { 77 std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x)); 78 if (!ret.second) 79 { 80 const_iterator const it = m_vector.insert(m_vector.begin() + (ret.first - m_vector.begin()), x); 81 return std::make_pair(it, true); 82 } 83 return std::make_pair(ret.first, false); 84 } 85 erase(const Value & x)86 size_type erase( const Value& x ) 87 { 88 std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x)); 89 if (ret.second) 90 { 91 m_vector.erase(m_vector.begin() + (ret.first - m_vector.begin())); 92 return 1; 93 } 94 return 0; 95 } 96 erase_at(size_t index)97 void erase_at(size_t index) 98 { 99 m_vector.erase(m_vector.begin() + index); 100 } 101 102 // like C++ 2011: erase with const_iterator (doesn't change sort order) erase(const_iterator const & position)103 const_iterator erase(const_iterator const& position) 104 { // C++98 has vector::erase(iterator), so call that 105 return m_vector.erase(m_vector.begin() + (position - m_vector.begin())); 106 } 107 erase(const_iterator const & first,const_iterator const & last)108 void erase(const_iterator const& first, const_iterator const& last) 109 { 110 m_vector.erase(m_vector.begin() + (first - m_vector.begin()), 111 m_vector.begin() + (last - m_vector.begin())); 112 } 113 114 /** 115 * make erase return the removed element, otherwise there is no useful way of extracting a std::unique_ptr 116 * from this. 117 */ erase_extract(size_t index)118 Value erase_extract( size_t index ) 119 { 120 Value val = std::move(m_vector[index]); 121 m_vector.erase(m_vector.begin() + index); 122 return val; 123 } 124 clear()125 void clear() 126 { 127 m_vector.clear(); 128 } 129 swap(sorted_vector & other)130 void swap(sorted_vector & other) 131 { 132 m_vector.swap(other.m_vector); 133 } 134 reserve(size_type amount)135 void reserve(size_type amount) 136 { 137 m_vector.reserve(amount); 138 } 139 140 // ACCESSORS 141 size() const142 size_type size() const 143 { 144 return m_vector.size(); 145 } 146 empty() const147 bool empty() const 148 { 149 return m_vector.empty(); 150 } 151 152 // Only return a const iterator, so that the vector cannot be directly updated. begin() const153 const_iterator begin() const 154 { 155 return m_vector.begin(); 156 } 157 158 // Only return a const iterator, so that the vector cannot be directly updated. end() const159 const_iterator end() const 160 { 161 return m_vector.end(); 162 } 163 164 // Only return a const iterator, so that the vector cannot be directly updated. rbegin() const165 const_reverse_iterator rbegin() const 166 { 167 return m_vector.rbegin(); 168 } 169 170 // Only return a const iterator, so that the vector cannot be directly updated. rend() const171 const_reverse_iterator rend() const 172 { 173 return m_vector.rend(); 174 } 175 front() const176 const Value& front() const 177 { 178 return m_vector.front(); 179 } 180 back() const181 const Value& back() const 182 { 183 return m_vector.back(); 184 } 185 operator [](size_t index) const186 const Value& operator[]( size_t index ) const 187 { 188 return m_vector.operator[]( index ); 189 } 190 191 // OPERATIONS 192 lower_bound(const Value & x) const193 const_iterator lower_bound( const Value& x ) const 194 { 195 return std::lower_bound( m_vector.begin(), m_vector.end(), x, Compare() ); 196 } 197 upper_bound(const Value & x) const198 const_iterator upper_bound( const Value& x ) const 199 { 200 return std::upper_bound( m_vector.begin(), m_vector.end(), x, Compare() ); 201 } 202 203 /* Searches the container for an element with a value of x 204 * and returns an iterator to it if found, otherwise it returns an 205 * iterator to sorted_vector::end (the element past the end of the container). 206 * 207 * Only return a const iterator, so that the vector cannot be directly updated. 208 */ find(const Value & x) const209 const_iterator find( const Value& x ) const 210 { 211 std::pair<const_iterator, bool> const ret(Find_t()(m_vector.begin(), m_vector.end(), x)); 212 return (ret.second) ? ret.first : m_vector.end(); 213 } 214 count(const Value & v) const215 size_type count(const Value& v) const 216 { 217 return find(v) != end() ? 1 : 0; 218 } 219 operator ==(const sorted_vector & other) const220 bool operator==(const sorted_vector & other) const 221 { 222 return m_vector == other.m_vector; 223 } 224 operator !=(const sorted_vector & other) const225 bool operator!=(const sorted_vector & other) const 226 { 227 return m_vector != other.m_vector; 228 } 229 insert(sorted_vector<Value,Compare,Find> const & rOther)230 void insert(sorted_vector<Value,Compare,Find> const& rOther) 231 { 232 // optimization for the rather common case that we are overwriting this with the contents 233 // of another sorted vector 234 if ( empty() ) 235 { 236 m_vector.insert(m_vector.begin(), rOther.m_vector.begin(), rOther.m_vector.end()); 237 } 238 else 239 { 240 for (const_iterator it = rOther.m_vector.begin(); it != rOther.m_vector.end(); ++it) 241 { 242 insert(*it); 243 } 244 } 245 } 246 247 /* Clear() elements in the vector, and free them one by one. */ DeleteAndDestroyAll()248 void DeleteAndDestroyAll() 249 { 250 for (const_iterator it = m_vector.begin(); it != m_vector.end(); ++it) 251 { 252 delete *it; 253 } 254 255 clear(); 256 } 257 258 // fdo#58793: some existing code in Writer (SwpHintsArray) 259 // routinely modifies the members of the vector in a way that 260 // violates the sort order, and then re-sorts the array. 261 // This is a kludge to enable that code to work. 262 // If you are calling this function, you are Doing It Wrong! Resort()263 void Resort() 264 { 265 std::stable_sort(m_vector.begin(), m_vector.end(), Compare()); 266 } 267 268 private: 269 270 vector_t m_vector; 271 }; 272 273 /* Specialise the template for cases like Value = std::unique_ptr<T>, where 274 MSVC2017 needs some help 275 */ 276 template< 277 typename Value, 278 typename Compare, 279 template<typename, typename> class Find > 280 class sorted_vector<Value,Compare,Find,false> : public sorted_vector<Value, Compare, Find, true> 281 { 282 public: 283 using sorted_vector<Value, Compare, Find, true>::sorted_vector; 284 typedef sorted_vector<Value, Compare, Find, true> super_sorted_vector; 285 286 sorted_vector(sorted_vector const&) = delete; 287 sorted_vector& operator=(sorted_vector const&) = delete; 288 289 sorted_vector() = default; 290 sorted_vector(sorted_vector&&) = default; 291 sorted_vector& operator=(sorted_vector&&) = default; 292 293 /** 294 * implement find for sorted_vectors containing std::unique_ptr 295 */ find(typename Value::element_type const * x) const296 typename super_sorted_vector::const_iterator find( typename Value::element_type const * x ) const 297 { 298 Value tmp(const_cast<typename Value::element_type*>(x)); 299 auto ret = super_sorted_vector::find(tmp); 300 tmp.release(); 301 return ret; 302 } 303 /** 304 * implement upper_bound for sorted_vectors containing std::unique_ptr 305 */ upper_bound(typename Value::element_type const * x) const306 typename super_sorted_vector::const_iterator upper_bound( typename Value::element_type const * x ) const 307 { 308 Value tmp(const_cast<typename Value::element_type*>(x)); 309 auto ret = super_sorted_vector::upper_bound(tmp); 310 tmp.release(); 311 return ret; 312 } 313 /** 314 * implement lower_bound for sorted_vectors containing std::unique_ptr 315 */ lower_bound(typename Value::element_type const * x) const316 typename super_sorted_vector::const_iterator lower_bound( typename Value::element_type const * x ) const 317 { 318 Value tmp(const_cast<typename Value::element_type*>(x)); 319 auto ret = super_sorted_vector::lower_bound(tmp); 320 tmp.release(); 321 return ret; 322 } 323 }; 324 325 326 /** Implements an ordering function over a pointer, where the comparison uses the < operator on the pointed-to types. 327 Very useful for the cases where we put pointers to objects inside a sorted_vector. 328 */ 329 template <class T> struct less_ptr_to 330 { operator ()o3tl::less_ptr_to331 bool operator() ( T* const& lhs, T* const& rhs ) const 332 { 333 return (*lhs) < (*rhs); 334 } 335 }; 336 337 template <class T> struct less_uniqueptr_to 338 { operator ()o3tl::less_uniqueptr_to339 bool operator() ( std::unique_ptr<T> const& lhs, std::unique_ptr<T> const& rhs ) const 340 { 341 return (*lhs) < (*rhs); 342 } 343 }; 344 345 /** the elements are totally ordered by Compare, 346 for no 2 elements !Compare(a,b) && !Compare(b,a) is true 347 */ 348 template<class Value, class Compare> 349 struct find_unique 350 { 351 typedef typename sorted_vector<Value, Compare, 352 o3tl::find_unique> ::const_iterator const_iterator; operator ()o3tl::find_unique353 std::pair<const_iterator, bool> operator()( 354 const_iterator first, const_iterator last, 355 Value const& v) 356 { 357 const_iterator const it = std::lower_bound(first, last, v, Compare()); 358 return std::make_pair(it, (it != last && !Compare()(v, *it))); 359 } 360 }; 361 362 /** the elements are partially ordered by Compare, 363 2 elements are allowed if they are not the same element (pointer equal) 364 */ 365 template<class Value, class Compare> 366 struct find_partialorder_ptrequals 367 { 368 typedef typename sorted_vector<Value, Compare, 369 o3tl::find_partialorder_ptrequals>::const_iterator const_iterator; operator ()o3tl::find_partialorder_ptrequals370 std::pair<const_iterator, bool> operator()( 371 const_iterator first, const_iterator last, 372 Value const& v) 373 { 374 std::pair<const_iterator, const_iterator> const its = 375 std::equal_range(first, last, v, Compare()); 376 for (const_iterator it = its.first; it != its.second; ++it) 377 { 378 if (v == *it) 379 { 380 return std::make_pair(it, true); 381 } 382 } 383 return std::make_pair(its.first, false); 384 } 385 }; 386 387 } // namespace o3tl 388 #endif 389 390 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */ 391