LCOV - code coverage report
Current view: top level - lunchbox - unorderedIntervalSet.ipp (source / functions) Hit Total Coverage
Test: lcov2.info Lines: 133 147 90.5 %
Date: 2014-10-01 Functions: 17 17 100.0 %

          Line data    Source code
       1             : 
       2             : /* Copyright (c) 2008, Juan Hernando <jhernando@fi.upm.es>
       3             :  *               2013, Daniel Nachbaur <danielnachbaur@epfl.ch>
       4             :  *
       5             :  * This library is free software; you can redistribute it and/or modify it under
       6             :  * the terms of the GNU Lesser General Public License version 2.1 as published
       7             :  * by the Free Software Foundation.
       8             :  *
       9             :  * This library is distributed in the hope that it will be useful, but WITHOUT
      10             :  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
      11             :  * FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
      12             :  * details.
      13             :  *
      14             :  * You should have received a copy of the GNU Lesser General Public License
      15             :  * along with this library; if not, write to the Free Software Foundation, Inc.,
      16             :  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
      17             :  */
      18             : 
      19             : #include <lunchbox/debug.h>
      20             : 
      21             : #include <boost/iterator/iterator_facade.hpp>
      22             : 
      23             : /** @cond IGNORE */
      24             : namespace lunchbox
      25             : {
      26             : 
      27             : template< typename T >
      28             : class UnorderedIntervalSet< T >::const_iterator :
      29             :     public boost::iterator_facade<
      30             :         typename UnorderedIntervalSet< T >::const_iterator,
      31             :         T, std::forward_iterator_tag, T >
      32             : {
      33             : public:
      34             :     // Default constructor to an end() iterator.
      35             :     const_iterator()
      36             :     {}
      37             : 
      38             : private:
      39             :     friend class boost::iterator_core_access;
      40             :     friend class UnorderedIntervalSet;
      41             : 
      42             :     typedef typename UnorderedIntervalSet< T >::EdgeSet::const_iterator
      43             :                      edge_iterator;
      44             : 
      45          15 :     const_iterator( const UnorderedIntervalSet& set,
      46             :                     const edge_iterator& interval)
      47             :         : _intervalIteratorEnd( set._intervals.end( ))
      48          15 :         , _startEdge( interval )
      49             :     {
      50          15 :         if (_startEdge != _intervalIteratorEnd )
      51           2 :             _value = _startEdge->first;
      52          15 :     }
      53             : 
      54           4 :     const_iterator( const UnorderedIntervalSet & set,
      55             :                     const edge_iterator & interval, const T& current )
      56             :         : _value( current )
      57             :         , _intervalIteratorEnd( set._intervals.end( ))
      58           4 :         , _startEdge( interval )
      59             :     {
      60           4 :     }
      61             : 
      62           9 :     void increment()
      63             :     {
      64           9 :         if( _startEdge == _intervalIteratorEnd )
      65           9 :             return;
      66             : 
      67           9 :         edge_iterator endEdge = _startEdge;
      68           9 :         ++endEdge;
      69             :         // Next element is inside the current interval.
      70           9 :         if( _value >= _startEdge->first && _value < endEdge->first )
      71           7 :             ++_value;
      72             :         else
      73             :         {
      74           2 :             ++_startEdge;
      75           2 :             ++_startEdge;
      76           2 :             if( _startEdge != _intervalIteratorEnd )
      77           1 :                 _value = _startEdge->first;
      78             :         }
      79             :     }
      80             : 
      81          11 :     bool equal( const const_iterator& rhs ) const
      82             :     {
      83          11 :         return (_startEdge == _intervalIteratorEnd &&
      84           3 :                 rhs._startEdge == _intervalIteratorEnd) ||
      85          14 :                (_startEdge == rhs._startEdge && _value == rhs._value );
      86             :     }
      87             : 
      88          11 :     T dereference() const
      89             :     {
      90          11 :         return _value;
      91             :     }
      92             : 
      93             :     T _value;
      94             :     edge_iterator _intervalIteratorEnd;
      95             :     edge_iterator _startEdge;
      96             : };
      97             : 
      98             : template < typename T >
      99           1 : UnorderedIntervalSet< T >::UnorderedIntervalSet()
     100           1 :     : _size( 0 )
     101           1 : {}
     102             : 
     103             : template < typename T >
     104           1 : void UnorderedIntervalSet< T >::insert( const T& element )
     105             : {
     106           1 :     insert( element, element );
     107           1 : }
     108             : 
     109             : template < typename T >
     110           1 : void UnorderedIntervalSet< T >::erase( const T& element )
     111             : {
     112           1 :     erase( element, element );
     113           1 : }
     114             : 
     115             : template < typename T >
     116           6 : void UnorderedIntervalSet< T >::insert( const T& startElement,
     117             :                                         const T& endElement )
     118             : {
     119           6 :     LBASSERT( startElement <= endElement );
     120             : 
     121           6 :     Edge startValue( startElement, true );
     122           6 :     Edge endValue( endElement, false );
     123             : 
     124           6 :     if( _intervals.empty( ))
     125             :     {
     126           2 :         _intervals.insert( startValue );
     127           2 :         _intervals.insert( endValue );
     128           2 :         _size = endElement - startElement + 1;
     129           8 :         return;
     130             :     }
     131             : 
     132             :     // Finding the first edge whose value is less or equal than startElement.
     133             :     typename EdgeSet::iterator previous_to_start =
     134           4 :             _intervals.lower_bound( startValue );
     135           4 :     if( previous_to_start != _intervals.end( ))
     136             :     {
     137           3 :         if( previous_to_start == _intervals.begin( ))
     138             :         {
     139           2 :             if( startValue.first < previous_to_start->first )
     140           1 :                 previous_to_start = _intervals.end();
     141             :         }
     142             :         else
     143           1 :             previous_to_start--;
     144             :     }
     145             :     else
     146           1 :         previous_to_start = (++_intervals.rbegin()).base();
     147             : 
     148             :     // Adding start edge as needed.
     149           4 :     typename EdgeSet::iterator position;
     150             :     bool fallsInside;
     151           4 :     size_t overlappingPortion = 0;
     152           4 :     T overlappingStart = T(); // initialized to silent a warning.
     153             : 
     154           4 :     if( previous_to_start == _intervals.end( ))
     155             :     {
     156             :         // Previous element doesn't exist and there is neither any of
     157             :         // equal value.
     158             :         // We have to insert start.
     159           1 :         position = _intervals.insert( startValue );
     160           1 :         fallsInside = false;
     161             :     }
     162           3 :     else if( !previous_to_start->second )
     163             :     {
     164             :         // Previous element is the end of one interval.
     165           1 :         if( previous_to_start->first + 1 == startElement )
     166             :         {
     167             :             // The end of previous interval end is one unit less than the start
     168             :             // of this interval. Removing the edge to fuse both.
     169           0 :             position = previous_to_start;
     170           0 :             position--;
     171           0 :             _intervals.erase( previous_to_start );
     172             :         }
     173             :         else
     174             :             // We have to insert start.
     175           1 :             position = _intervals.insert( previous_to_start, startValue );
     176           1 :         fallsInside = false;
     177             :     }
     178             :     else
     179             :     {
     180             :         // Start has fallen inside another interval we don't have to insert it.
     181           2 :         position = previous_to_start;
     182           2 :         fallsInside = true;
     183           2 :         overlappingStart = startElement;
     184             :     }
     185             : 
     186             :     // Now we have to check where the end goes.
     187           4 :     ++position;
     188          11 :     while( position != _intervals.end() && position->first <= endElement )
     189             :     {
     190             :         // Calculating the length of a possible interval overlapping the
     191             :         // interval being inserted.
     192           3 :         if( fallsInside )
     193             :         {
     194             :             // Previous position was the start of an overlapping interval.
     195           2 :             LBASSERT( !position->second );
     196           2 :             overlappingPortion += position->first - overlappingStart + 1;
     197             :         }
     198             :         else
     199           1 :             overlappingStart = position->first;
     200             : 
     201           3 :         fallsInside = position->second;
     202             : 
     203             :         // Note that the post-increment is evaluated before the function call
     204             :         // So position is actually pointing to the next one before the previous
     205             :         // element is erased.
     206           3 :         _intervals.erase( position++ );
     207             :     }
     208             : 
     209           5 :     if( position != _intervals.end() &&
     210           1 :         position->second && position->first == endElement + 1 )
     211             :     {
     212             :         // The end of the interval connects with the start of the next one.
     213             :         // We remove the start of the following one and don't insert this
     214             :         // edge.
     215           0 :         _intervals.erase(position);
     216             :     }
     217           4 :     else if( !fallsInside )
     218             :     {
     219             :         // End edge is not inside a previously existing interval so we
     220             :         // have to add it.
     221           3 :         _intervals.insert(position, endValue);
     222             :     }
     223             :     else
     224           1 :         overlappingPortion += endElement - overlappingStart + 1;
     225             : 
     226           4 :     _size += size_t(endElement - startElement + 1) - overlappingPortion;
     227           4 :     LBASSERT( _intervals.size() % 2 == 0 );
     228             : }
     229             : 
     230             : template < typename T >
     231           4 : void UnorderedIntervalSet< T >::erase( const T& startElement,
     232             :                                        const T& endElement )
     233             : {
     234           4 :     LBASSERT( startElement <= endElement );
     235             : 
     236           4 :     if( _intervals.empty( ))
     237           1 :         return;
     238             : 
     239             :     // Finding the first edge whose value is less or equal than startElement.
     240             :     typename EdgeSet::iterator nextToStart =
     241           4 :         _intervals.lower_bound( std::make_pair( startElement, true ));
     242           4 :     typename EdgeSet::iterator previousToStart = nextToStart;
     243           4 :     if( nextToStart == _intervals.begin( ))
     244           0 :         previousToStart = _intervals.end();
     245           4 :     else if( nextToStart == _intervals.end( ))
     246             :         // Nothing to remove here
     247           1 :         return;
     248             :     else
     249           3 :         --previousToStart;
     250             : 
     251           3 :     typename EdgeSet::iterator position;
     252             :     bool inside;
     253           3 :     T overlappingStart = 0;
     254           3 :     size_t overlapping_portion = 0;
     255             : 
     256           3 :     if( previousToStart != _intervals.end( ))
     257             :     {
     258             :         // startElement is greater or equal than some interval edge.
     259           3 :         if( previousToStart->second )
     260             :         {
     261             :             // Inserting the new end of the interval starting at
     262             :             // previous_to_start.
     263           3 :             position =
     264           6 :                 _intervals.insert( std::make_pair( startElement - 1, false ));
     265           3 :             inside = true;
     266           3 :             overlappingStart = startElement;
     267             :         }
     268             :         else
     269             :         {
     270           0 :             position = previousToStart;
     271           0 :             inside = false;
     272             :         }
     273           3 :         ++position;
     274             :     }
     275             :     else
     276             :     {
     277             :         // startElement is less than the start of any interval.
     278           0 :         inside = false;
     279           0 :         position = _intervals.begin();
     280           0 :         overlappingStart = position->first;
     281             :     }
     282             :     // Position has the next edge after the last interval before the removal
     283             :     // interval.
     284             : 
     285           8 :     while( position != _intervals.end() && position->first <= endElement )
     286             :     {
     287           2 :         if (inside)
     288           2 :             overlapping_portion += position->first - overlappingStart + 1;
     289             :         else
     290           0 :             overlappingStart = position->first;
     291             : 
     292           2 :         inside = position->second;
     293             : 
     294             :         // Note that the post-increment is evaluated before the function call
     295             :         // So position is actually pointing to the next one before the previous
     296             :         // element is erased.
     297           2 :         _intervals.erase( position++ );
     298             :     }
     299             : 
     300           3 :     if( inside )
     301             :     {
     302           1 :         LBASSERT( position != _intervals.end( ));
     303             :         // End edge is not inside a previously existing interval so we
     304             :         // have to add it.
     305           1 :         _intervals.insert (std::make_pair( endElement + 1, true ));
     306           1 :         overlapping_portion += endElement - overlappingStart + 1;
     307             :     }
     308             : 
     309           3 :     _size -= overlapping_portion;
     310           3 :     LBASSERT( _intervals.size() % 2 == 0 );
     311             : }
     312             : 
     313             : template < typename T >
     314             : void UnorderedIntervalSet< T >::insert( const UnorderedIntervalSet& rhs )
     315             : {
     316             :     for( typename EdgeSet::const_iterator i = rhs._intervals.begin();
     317             :          i != rhs._intervals.end(); ++i )
     318             :     {
     319             :         insert( i->first, i->second );
     320             :     }
     321             : }
     322             : 
     323             : template < typename T >
     324           1 : void UnorderedIntervalSet< T >::clear()
     325             : {
     326           1 :     _intervals.clear();
     327           1 :     _size = 0;
     328           1 : }
     329             : 
     330             : template < typename T >
     331           3 : bool UnorderedIntervalSet< T >::exists( const T& element ) const
     332             : {
     333           3 :     return find( element ) != end();
     334             : }
     335             : 
     336             : template < typename T >
     337             : typename UnorderedIntervalSet< T >::const_iterator
     338           6 : UnorderedIntervalSet< T >::find( const T& element ) const
     339             : {
     340           6 :     if( _intervals.empty( ))
     341           0 :         return end();
     342             : 
     343             :     typename EdgeSet::const_iterator next =
     344           6 :         _intervals.lower_bound( std::make_pair( element, false ));
     345             :     // Note that if x equals the start edge of any interval then
     346             :     // next will be the end edge due to the use of (x, false) in the
     347             :     // search.
     348           6 :     if( next == _intervals.end() || next == _intervals.begin( ))
     349             :         // x cannot be inside any interval.
     350           2 :         return end();
     351             : 
     352           4 :     typename EdgeSet::const_iterator previous = next;
     353           4 :     --previous;
     354           4 :     if( previous->second )
     355           4 :         return const_iterator( *this, previous, element );
     356           0 :     return end();
     357             : }
     358             : 
     359             : template < typename T >
     360             : typename UnorderedIntervalSet< T >::const_iterator
     361           2 : UnorderedIntervalSet< T >::begin() const
     362             : {
     363           2 :     if( _intervals.empty( ))
     364           0 :         return end();
     365           2 :     return const_iterator( *this, _intervals.begin( ));
     366             : }
     367             : 
     368             : template < typename T >
     369             : typename UnorderedIntervalSet< T >::const_iterator
     370          13 : UnorderedIntervalSet< T >::end() const
     371             : {
     372          13 :     return const_iterator( *this, _intervals.end());
     373             : }
     374             : 
     375             : template < typename T >
     376          12 : size_t UnorderedIntervalSet< T >::size() const
     377             : {
     378          12 :     return _size;
     379             : }
     380             : 
     381             : template < typename T >
     382           2 : bool UnorderedIntervalSet< T >::empty() const
     383             : {
     384           2 :     return size() == 0;
     385             : }
     386             : 
     387             : template < typename T >
     388             : void UnorderedIntervalSet< T >::swap( UnorderedIntervalSet& rhs )
     389             : {
     390             :     _intervals.swap( rhs._intervals );
     391             : }
     392             : 
     393             : }
     394             : /** @endcond */

Generated by: LCOV version 1.10