intervalSet.h

/* Copyright (c) 2008-2016, Juan Hernando <jhernando@fi.upm.es>
 *                          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.
 */

#ifndef LUNCHBOX_INTERVALSET_H
#define LUNCHBOX_INTERVALSET_H

#include <lunchbox/types.h>
#include <set>

namespace lunchbox
{

template< typename T > class IntervalSet
{
public:
    class const_iterator;

    IntervalSet();

    void insert( const T& element );

    void insert( const T& startElement, const T& endElement );

    void insert( const IntervalSet& rhs );

    void erase( const T& element );

    void erase( const T& startElement, const T& endElement );

    void clear();

    void swap( IntervalSet& rhs );

    bool exists( const T& element ) const;

    const_iterator find( const T& element ) const;

    const_iterator begin() const;

    const_iterator end() const;

    size_t size() const;

    bool empty() const;


private:
    typedef std::pair< T, bool > Edge;

    struct EdgeCompare
    {
        bool operator()( const Edge & p1, const Edge & p2 ) const
        {
            if( p1.first < p2.first )
                return true;
            if( p1.first == p2.first )
                return p1.second && !p2.second;
            return false;
        }
    };

    // The first element of the pair is the edge value, the second element is
    // true for the start of an interval and false for the end.
    typedef std::multiset< Edge,  EdgeCompare > EdgeSet;
    EdgeSet _intervals;
    size_t _size;
};
}

#include "intervalSet.ipp" // template implementation

#endif // LUNCHBOX_INTERVALSET_H