// (C) Copyright 2008-2009 SDML (www.sdml.info)
//
// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// Copyright Andrew Sutton 2007
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_SETS_ORDERED_SET_HPP
#define BOOST_SETS_ORDERED_SET_HPP

// These implementations of the basic set interface is in these headers/
#include <set>
#include <algorithm>
#include <iterator>

// The Boost.Range library is part of the sets interface.
#include <boost/range.hpp>

namespace boost {
namespace sets {

    // Adapt the standard set type to the set interface. Note that this actually
    // specializes specifically to the standard set because a) we know that it's
    // ordered and b) we want to actively exclude non-set types from the
    // implementation.

    // Return the size (cardinality) of a set.
    template <typename T, typename C, typename A>
    inline bool
    size(const std::set<T,C,A>& s)
    { return s.size(); }

    // Return true if the set is empty.
    template <typename T, typename C, typename A>
    inline bool
    empty(const std::set<T,C,A>& s)
    { return s.empty(); }

    // Determine if a set contains the given elmenent.
    template <typename T, typename C, typename A>
    inline bool
    contains(const std::set<T,C,A>& s, const T& x)
    { return s.find(x) != s.end(); }

    // Determine if a set contains the elements in set T. Note that we use a
    // set here because the std includes method requires the elements in both
    // s and t to be in sorted order.
    template <typename T, typename C, typename A>
    inline bool
    contains(const std::set<T,C,A>& s, const std::set<T,C,A>& t)
    { return std::includes(s.begin(), s.end(), t.begin(), t.end()); }

    // Insert the given element into the set. This is essentially the same as.
    // s = s U {x}.
    template <typename T, typename C, typename A>
    inline std::pair<typename std::set<T,C,A>::iterator, bool>
    add(std::set<T,C,A>& s, const T& x)
    { return s.insert(x); }

    // Remove the given element from the set. Note that this requires a
    // finding the object, which is O(log n) but still slower than an erase
    // using an iterator to the object. This is essentially the operation
    // s = s - {x}.
    template <typename T, typename C, typename A>
    inline void
    remove(std::set<T,C,A>& s, const T& x)
    { s.erase(x); }

    // Remove the object referenced by the given iterator from the set.
    // Note that this is not a constant time operation since it probably has to
    // rebalance a tree after the removal. This is essentially the same as
    // s = s - {*i}.
    template <typename T, typename C, typename A>
    inline void
    remove(std::set<T,C,A>& s, typename std::set<T,C,A>::iterator i)
    { s.erase(i); }

    // Clear the given set (make it empty).
    template <typename T, typename C, typename A>
    void clear(std::set<T,C,A>& s)
    { s.clear(); }

} /* namespace sets */
} /* namespace boost */

#include <boost/sets/ordered_set/union.hpp>
#include <boost/sets/ordered_set/intersection.hpp>
#include <boost/sets/ordered_set/difference.hpp>

#endif