LCOV - code coverage report
Current view: top level - include/o3tl - sorted_vector.hxx (source / functions) Hit Total Coverage
Test: commit 10e77ab3ff6f4314137acd6e2702a6e5c1ce1fae Lines: 63 67 94.0 %
Date: 2014-11-03 Functions: 261 335 77.9 %
Legend: Lines: hit not hit

          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: */

Generated by: LCOV version 1.10