// set standard header
#ifndef _SET_
#define _SET_

/* This file is for use only in conjunction with a valid license for
Microsoft Visual C++ V5.0. Microsoft Corporation is in no way involved
with the production or release of this file. The file is offered on an
``as is'' basis.

DINKUMWARE, LTD. AND P.J. PLAUGER MAKE NO REPRESENTATIONS OR WARRANTIES
ABOUT THE SUITABILITY OF THIS FILES, EITHER EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. DINKUMWARE, LTD.
AND P.J. PLAUGER SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY
LICENSEE AS A RESULT OF USING THIS FILE.

For additional information, contact Dinkumware, Ltd. (+1-888-4DINKUM or
support@dinkumware.com).

Version date: 25 June 1998
 */

#include <functional>
#include "XTREE"

#ifdef  _MSC_VER
#pragma pack(push,8)
#endif  /* _MSC_VER */

_STD_BEGIN
        // TEMPLATE CLASS set
template<class _K, class _Pr = less<_K>,
    class _A = allocator<_K> >
    class set {
public:
    typedef set<_K, _Pr, _A> _Myt;
    typedef _K value_type;
    struct _Kfn : public unary_function<value_type, _K> {
        const _K& operator()(const value_type& _X) const
        {return (_X); }
        };
    typedef _Pr value_compare;
    typedef _K key_type;
    typedef _Pr key_compare;
    typedef _A allocator_type;
    typedef _Tree<_K, value_type, _Kfn, _Pr, _A> _Imp;
    typedef _Imp::size_type size_type;
    typedef _Imp::difference_type difference_type;
    typedef _Imp::const_reference reference;
    typedef _Imp::const_reference const_reference;
    typedef _Imp::const_iterator iterator;
    typedef _Imp::const_iterator const_iterator;
    typedef _Imp::const_reverse_iterator reverse_iterator;
    typedef _Imp::const_reverse_iterator const_reverse_iterator;
    typedef pair<iterator, bool> _Pairib;
    typedef pair<const_iterator, const_iterator> _Paircc;
    explicit set(const _Pr& _Pred = _Pr(), const _A& _Al = _A())
        : _Tr(_Pred, false, _Al) {}
    typedef const value_type *_It;
    set(_It _F, _It _L, const _Pr& _Pred = _Pr(),
        const _A& _Al = _A())
        : _Tr(_Pred, false, _Al)
        {for (; _F != _L; ++_F)
            _Tr.insert(*_F); }
    const_iterator begin() const
        {return (_Tr.begin()); }
    const_iterator end() const
        {return (_Tr.end()); }
    const_reverse_iterator rbegin() const
        {return (_Tr.rbegin()); }
    const_reverse_iterator rend() const
        {return (_Tr.rend()); }
    size_type size() const
        {return (_Tr.size()); }
    size_type max_size() const
        {return (_Tr.max_size()); }
    bool empty() const
        {return (_Tr.empty()); }
    _A get_allocator() const
        {return (_Tr.get_allocator()); }
    _Pairib insert(const value_type& _X)
        {_Imp::_Pairib _Ans = _Tr.insert(_X);
        return (_Pairib(_Ans.first, _Ans.second)); }
    iterator insert(iterator _P, const value_type& _X)
        {return (_Tr.insert((_Imp::iterator&)_P, _X)); }
    void insert(_It _F, _It _L)
        {for (; _F != _L; ++_F)
            _Tr.insert(*_F); }
    iterator erase(iterator _P)
        {return (_Tr.erase((_Imp::iterator&)_P)); }
    iterator erase(iterator _F, iterator _L)
        {return (_Tr.erase((_Imp::iterator&)_F,
            (_Imp::iterator&)_L)); }
    size_type erase(const _K& _Kv)
        {return (_Tr.erase(_Kv)); }
    void clear()
        {_Tr.clear(); }
    void swap(_Myt& _X)
        {std::swap(_Tr, _X._Tr); }
    friend void swap(_Myt& _X, _Myt& _Y)
        {_X.swap(_Y); }
    key_compare key_comp() const
        {return (_Tr.key_comp()); }
    value_compare value_comp() const
        {return (_Tr.key_comp()); }
    const_iterator find(const _K& _Kv) const
        {return (_Tr.find(_Kv)); }
    size_type count(const _K& _Kv) const
        {return (_Tr.count(_Kv)); }
    const_iterator lower_bound(const _K& _Kv) const
        {return (_Tr.lower_bound(_Kv)); }
    const_iterator upper_bound(const _K& _Kv) const
        {return (_Tr.upper_bound(_Kv)); }
    _Paircc equal_range(const _K& _Kv) const
        {return (_Tr.equal_range(_Kv)); }
protected:
    _Imp _Tr;
    };
        // set TEMPLATE OPERATORS
template<class _K, class _Pr, class _A> inline
    bool operator==(const set<_K, _Pr, _A>& _X,
        const set<_K, _Pr, _A>& _Y)
    {return (_X.size() == _Y.size()
        && equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _K, class _Pr, class _A> inline
    bool operator!=(const set<_K, _Pr, _A>& _X,
        const set<_K, _Pr, _A>& _Y)
    {return (!(_X == _Y)); }
template<class _K, class _Pr, class _A> inline
    bool operator<(const set<_K, _Pr, _A>& _X,
        const set<_K, _Pr, _A>& _Y)
    {return (lexicographical_compare(_X.begin(), _X.end(),
        _Y.begin(), _Y.end())); }
template<class _K, class _Pr, class _A> inline
    bool operator>(const set<_K, _Pr, _A>& _X,
        const set<_K, _Pr, _A>& _Y)
    {return (_Y < _X); }
template<class _K, class _Pr, class _A> inline
    bool operator<=(const set<_K, _Pr, _A>& _X,
        const set<_K, _Pr, _A>& _Y)
    {return (!(_Y < _X)); }
template<class _K, class _Pr, class _A> inline
    bool operator>=(const set<_K, _Pr, _A>& _X,
        const set<_K, _Pr, _A>& _Y)
    {return (!(_X < _Y)); }
        // TEMPLATE CLASS multiset
template<class _K, class _Pr = less<_K>,
    class _A = allocator<_K> >
    class multiset {
public:
    typedef multiset<_K, _Pr, _A> _Myt;
    typedef _K value_type;
    struct _Kfn : public unary_function<value_type, _K> {
        const _K& operator()(const value_type& _X) const
        {return (_X); }
        };
    typedef _Pr value_compare;
    typedef _K key_type;
    typedef _Pr key_compare;
    typedef _A allocator_type;
    typedef _Tree<_K, value_type, _Kfn, _Pr, _A> _Imp;
    typedef _Imp::size_type size_type;
    typedef _Imp::difference_type difference_type;
    typedef _Imp::const_reference reference;
    typedef _Imp::const_reference const_reference;
    typedef _Imp::const_iterator iterator;
    typedef _Imp::const_iterator const_iterator;
    typedef _Imp::const_reverse_iterator reverse_iterator;
    typedef _Imp::const_reverse_iterator const_reverse_iterator;
    typedef pair<const_iterator, const_iterator> _Paircc;
    explicit multiset(const _Pr& _Pred = _Pr(),
        const _A& _Al = _A())
        : _Tr(_Pred, true, _Al) {}
    typedef const value_type *_It;
    multiset(_It _F, _It _L, const _Pr& _Pred = _Pr(),
            const _A& _Al = _A())
        : _Tr(_Pred, true, _Al)
        {for (; _F != _L; ++_F)
            _Tr.insert(*_F); }
    const_iterator begin() const
        {return (_Tr.begin()); }
    const_iterator end() const
        {return (_Tr.end()); }
    const_reverse_iterator rbegin() const
        {return (_Tr.rbegin()); }
    const_reverse_iterator rend() const
        {return (_Tr.rend()); }
    size_type size() const
        {return (_Tr.size()); }
    size_type max_size() const
        {return (_Tr.max_size()); }
    bool empty() const
        {return (_Tr.empty()); }
    _A get_allocator() const
        {return (_Tr.get_allocator()); }
    iterator insert(const value_type& _X)
        {return (_Tr.insert(_X).first); }
    iterator insert(iterator _P, const value_type& _X)
        {return (_Tr.insert((_Imp::iterator&)_P, _X)); }
    void insert(_It _F, _It _L)
        {for (; _F != _L; ++_F)
            _Tr.insert(*_F); }
    iterator erase(iterator _P)
        {return (_Tr.erase((_Imp::iterator&)_P)); }
    iterator erase(iterator _F, iterator _L)
        {return (_Tr.erase((_Imp::iterator&)_F,
            (_Imp::iterator&)_L)); }
    size_type erase(const _K& _Kv)
        {return (_Tr.erase(_Kv)); }
    void clear()
        {_Tr.clear(); }
    void swap(_Myt& _X)
        {std::swap(_Tr, _X._Tr); }
    friend void swap(_Myt& _X, _Myt& _Y)
        {_X.swap(_Y); }
    key_compare key_comp() const
        {return (_Tr.key_comp()); }
    value_compare value_comp() const
        {return (_Tr.key_comp()); }
    const_iterator find(const _K& _Kv) const
        {return (_Tr.find(_Kv)); }
    size_type count(const _K& _Kv) const
        {return (_Tr.count(_Kv)); }
    const_iterator lower_bound(const _K& _Kv) const
        {return (_Tr.lower_bound(_Kv)); }
    const_iterator upper_bound(const _K& _Kv) const
        {return (_Tr.upper_bound(_Kv)); }
    _Paircc equal_range(const _K& _Kv) const
        {return (_Tr.equal_range(_Kv)); }
protected:
    _Imp _Tr;
    };
        // multiset TEMPLATE OPERATORS
template<class _K, class _Pr, class _A> inline
    bool operator==(const multiset<_K, _Pr, _A>& _X,
        const multiset<_K, _Pr, _A>& _Y)
    {return (_X.size() == _Y.size()
        && equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _K, class _Pr, class _A> inline
    bool operator!=(const multiset<_K, _Pr, _A>& _X,
        const multiset<_K, _Pr, _A>& _Y)
    {return (!(_X == _Y)); }
template<class _K, class _Pr, class _A> inline
    bool operator<(const multiset<_K, _Pr, _A>& _X,
        const multiset<_K, _Pr, _A>& _Y)
    {return (lexicographical_compare(_X.begin(), _X.end(),
        _Y.begin(), _Y.end())); }
template<class _K, class _Pr, class _A> inline
    bool operator>(const multiset<_K, _Pr, _A>& _X,
        const multiset<_K, _Pr, _A>& _Y)
    {return (_Y < _X); }
template<class _K, class _Pr, class _A> inline
    bool operator<=(const multiset<_K, _Pr, _A>& _X,
        const multiset<_K, _Pr, _A>& _Y)
    {return (!(_Y < _X)); }
template<class _K, class _Pr, class _A> inline
    bool operator>=(const multiset<_K, _Pr, _A>& _X,
        const multiset<_K, _Pr, _A>& _Y)
    {return (!(_X < _Y)); }
_STD_END
#ifdef  _MSC_VER
#pragma pack(pop)
#endif  /* _MSC_VER */

#endif /* _SET_ */

/*
 * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

