unorderedIntervalSet.ipp

/* Copyright (c) 2008, Juan Hernando <jhernando@fi.upm.es>
 *               2013, Daniel Nachbaur <danielnachbaur@epfl.ch>
 *
 * This library is free software; you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License version 2.1 as published
 * by the Free Software Foundation.
 *
 * This library is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include <lunchbox/debug.h>

#include <boost/iterator/iterator_facade.hpp>

namespace lunchbox
{

template< typename T >
class UnorderedIntervalSet< T >::const_iterator :
    public boost::iterator_facade<
        typename UnorderedIntervalSet< T >::const_iterator,
        T, std::forward_iterator_tag, T >
{
public:
    // Default constructor to an end() iterator.
    const_iterator()
    {}

private:
    friend class boost::iterator_core_access;
    friend class UnorderedIntervalSet;

    typedef typename UnorderedIntervalSet< T >::EdgeSet::const_iterator
                     edge_iterator;

    const_iterator( const UnorderedIntervalSet& set,
                    const edge_iterator& interval)
        : _intervalIteratorEnd( set._intervals.end( ))
        , _startEdge( interval )
    {
        if (_startEdge != _intervalIteratorEnd )
            _value = _startEdge->first;
    }

    const_iterator( const UnorderedIntervalSet & set,
                    const edge_iterator & interval, const T& current )
        : _value( current )
        , _intervalIteratorEnd( set._intervals.end( ))
        , _startEdge( interval )
    {
    }

    void increment()
    {
        if( _startEdge == _intervalIteratorEnd )
            return;

        edge_iterator endEdge = _startEdge;
        ++endEdge;
        // Next element is inside the current interval.
        if( _value >= _startEdge->first && _value < endEdge->first )
            ++_value;
        else
        {
            ++_startEdge;
            ++_startEdge;
            if( _startEdge != _intervalIteratorEnd )
                _value = _startEdge->first;
        }
    }

    bool equal( const const_iterator& rhs ) const
    {
        return (_startEdge == _intervalIteratorEnd &&
                rhs._startEdge == _intervalIteratorEnd) ||
               (_startEdge == rhs._startEdge && _value == rhs._value );
    }

    T dereference() const
    {
        return _value;
    }

    T _value;
    edge_iterator _intervalIteratorEnd;
    edge_iterator _startEdge;
};

template < typename T >
UnorderedIntervalSet< T >::UnorderedIntervalSet()
    : _size( 0 )
{}

template < typename T >
void UnorderedIntervalSet< T >::insert( const T& element )
{
    insert( element, element );
}

template < typename T >
void UnorderedIntervalSet< T >::erase( const T& element )
{
    erase( element, element );
}

template < typename T >
void UnorderedIntervalSet< T >::insert( const T& startElement,
                                        const T& endElement )
{
    LBASSERT( startElement <= endElement );

    Edge startValue( startElement, true );
    Edge endValue( endElement, false );

    if( _intervals.empty( ))
    {
        _intervals.insert( startValue );
        _intervals.insert( endValue );
        _size = endElement - startElement + 1;
        return;
    }

    // Finding the first edge whose value is less or equal than startElement.
    typename EdgeSet::iterator previous_to_start =
            _intervals.lower_bound( startValue );
    if( previous_to_start != _intervals.end( ))
    {
        if (previous_to_start == _intervals.begin( ))
            previous_to_start = _intervals.end();
        else
            previous_to_start--;
    }
    else
        previous_to_start = (++_intervals.rbegin()).base();

    // Adding start edge as needed.
    typename EdgeSet::iterator position;
    bool fallsInside;
    size_t overlappingPortion = 0;
    T overlappingStart = T(); // initialized to silent a warning.

    if( previous_to_start == _intervals.end( ))
    {
        // Previous element doesn't exist and there is neither any of
        // equal value.
        // We have to insert start.
        position = _intervals.insert( startValue );
        fallsInside = false;
    }
    else if( !previous_to_start->second )
    {
        // Previous element is the end of one interval.
        if( previous_to_start->first + 1 == startElement )
        {
            // The end of previous interval end is one unit less than the start
            // of this interval. Removing the edge to fuse both.
            position = previous_to_start;
            position--;
            _intervals.erase( previous_to_start );
        }
        else
            // We have to insert start.
            position = _intervals.insert( previous_to_start, startValue );
        fallsInside = false;
    }
    else
    {
        // Start has fallen inside another interval we don't have to insert it.
        position = previous_to_start;
        fallsInside = true;
        overlappingStart = startElement;
    }

    // Now we have to check where the end goes.
    ++position;
    while( position != _intervals.end() && position->first <= endElement )
    {
        // Calculating the length of a possible interval overlapping the
        // interval being inserted.
        if( fallsInside )
        {
            // Previous position was the start of an overlapping interval.
            LBASSERT( !position->second );
            overlappingPortion += position->first - overlappingStart + 1;
        }
        else
            overlappingStart = position->first;

        fallsInside = position->second;

        // Note that the post-increment is evaluated before the function call
        // So position is actually pointing to the next one before the previous
        // element is erased.
        _intervals.erase( position++ );
    }

    if( position != _intervals.end() &&
        position->second && position->first == endElement + 1 )
    {
        // The end of the interval connects with the start of the next one.
        // We remove the start of the following one and don't insert this
        // edge.
        _intervals.erase(position);
    }
    else if( !fallsInside )
    {
        // End edge is not inside a previously existing interval so we
        // have to add it.
        _intervals.insert(position, endValue);
    }
    else
        overlappingPortion += endElement - overlappingStart + 1;

    _size += size_t(endElement - startElement + 1) - overlappingPortion;
    LBASSERT( _intervals.size() % 2 == 0 );
}

template < typename T >
void UnorderedIntervalSet< T >::erase( const T& startElement,
                                       const T& endElement )
{
    LBASSERT( startElement <= endElement );

    if( _intervals.empty( ))
        return;

    // Finding the first edge whose value is less or equal than startElement.
    typename EdgeSet::iterator nextToStart =
        _intervals.lower_bound( std::make_pair( startElement, true ));
    typename EdgeSet::iterator previousToStart = nextToStart;
    if( nextToStart == _intervals.begin( ))
        previousToStart = _intervals.end();
    else if( nextToStart == _intervals.end( ))
        // Nothing to remove here
        return;
    else
        --previousToStart;

    typename EdgeSet::iterator position;
    bool inside;
    T overlappingStart = 0;
    size_t overlapping_portion = 0;

    if( previousToStart != _intervals.end( ))
    {
        // startElement is greater or equal than some interval edge.
        if( previousToStart->second )
        {
            // Inserting the new end of the interval starting at
            // previous_to_start.
            position =
                _intervals.insert( std::make_pair( startElement - 1, false ));
            inside = true;
            overlappingStart = startElement;
        }
        else
        {
            position = previousToStart;
            inside = false;
        }
        ++position;
    }
    else
    {
        // startElement is less than the start of any interval.
        inside = false;
        position = _intervals.begin();
        overlappingStart = position->first;
    }
    // Position has the next edge after the last interval before the removal
    // interval.

    while( position != _intervals.end() && position->first <= endElement )
    {
        if (inside)
            overlapping_portion += position->first - overlappingStart + 1;
        else
            overlappingStart = position->first;

        inside = position->second;

        // Note that the post-increment is evaluated before the function call
        // So position is actually pointing to the next one before the previous
        // element is erased.
        _intervals.erase( position++ );
    }

    if( inside )
    {
        LBASSERT( position != _intervals.end( ));
        // End edge is not inside a previously existing interval so we
        // have to add it.
        _intervals.insert (std::make_pair( endElement + 1, true ));
        overlapping_portion += endElement - overlappingStart + 1;
    }

    _size -= overlapping_portion;
    LBASSERT( _intervals.size() % 2 == 0 );
}

template < typename T >
void UnorderedIntervalSet< T >::insert( const UnorderedIntervalSet& rhs )
{
    for( typename EdgeSet::const_iterator i = rhs._intervals.begin();
         i != rhs._intervals.end(); ++i )
    {
        insert( i->first, i->second );
    }
}

template < typename T >
void UnorderedIntervalSet< T >::clear()
{
    _intervals.clear();
    _size = 0;
}

template < typename T >
bool UnorderedIntervalSet< T >::exists( const T& element ) const
{
    return find( element ) != end();
}

template < typename T >
typename UnorderedIntervalSet< T >::const_iterator
UnorderedIntervalSet< T >::find( const T& element ) const
{
    if( _intervals.empty( ))
        return end();

    typename EdgeSet::const_iterator next =
        _intervals.lower_bound( std::make_pair( element, false ));
    // Note that if x equals the start edge of any interval then
    // next will be the end edge due to the use of (x, false) in the
    // search.
    if( next == _intervals.end() || next == _intervals.begin( ))
        // x cannot be inside any interval.
        return end();

    typename EdgeSet::const_iterator previous = next;
    --previous;
    if( previous->second )
        return const_iterator( *this, previous, element );
    return end();
}

template < typename T >
typename UnorderedIntervalSet< T >::const_iterator
UnorderedIntervalSet< T >::begin() const
{
    if( _intervals.empty( ))
        return end();
    return const_iterator( *this, _intervals.begin( ));
}

template < typename T >
typename UnorderedIntervalSet< T >::const_iterator
UnorderedIntervalSet< T >::end() const
{
    return const_iterator( *this, _intervals.end());
}

template < typename T >
size_t UnorderedIntervalSet< T >::size() const
{
    return _size;
}

template < typename T >
bool UnorderedIntervalSet< T >::empty() const
{
    return size() == 0;
}

template < typename T >
void UnorderedIntervalSet< T >::swap( UnorderedIntervalSet& rhs )
{
    _intervals.swap( rhs._intervals );
}

}