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