#ifndef __STD_SET__
#define __STD_SET__
//
//
//  Copyright Digital Equipment Corporation 1996,1998. All rights reserved.
//
//  Restricted Rights: Use, duplication, or disclosure by the U.S.
//  Government is subject to restrictions as set forth in subparagraph
//  (c) (1) (ii) of DFARS 252.227-7013, or in FAR 52.227-19, or in FAR
//  52.227-14 Alt. III, as applicable.
//
//  This software is proprietary to and embodies the confidential
//  technology of Digital Equipment Corporation. Possession, use, or
//  copying of this software and media is authorized only pursuant to a
//  valid written license from Digital or an authorized sublicensor.
//
//

/***************************************************************************
 *
 * set - declarations for the Standard Library set class
 *
 * $Id: set,v 1.49 1996/09/11 23:03:17 smithey Exp $
 *
 ***************************************************************************
 *
 * 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.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994-1996 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/

#include <stdcomp>

#ifdef __BORLANDC__
#pragma warn -inl
#endif

#ifndef _RWSTD_HEADER_REQUIRES_HPP
#include <memory>
#include <tree>
#else
#include <memory.hpp>
#include <tree.hpp>
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __save
#      pragma __environment __header_defaults
#   endif
#endif

#ifndef _RWSTD_NO_NAMESPACE
namespace __rwstd {
#endif

//
// This is used in the implementation of set and multiset.
//

template <class T, class U>
struct ident : public _RW_STD::unary_function<T, U>
{
    const U& operator() (const T& x) const { return x; }
};

#ifndef _RWSTD_NO_NAMESPACE
}

namespace std {
#endif

//
// Note that _RWSTD_SIMPLE_DEFAULT(x) and _RWSTD_COMPLEX_DEFAULT(x)
// will expand to: ' = x', or nothing,
// depending on your compiler's capabilities and/or
// flag settings (see stdcomp).
//
template <class Key, 
          class Compare _RWSTD_COMPLEX_DEFAULT(less<Key>), 
          class Allocator _RWSTD_SIMPLE_DEFAULT(allocator<Key>) >  
class set
{
  public:
    //
    // Types
    //
    typedef Key                key_type;
    typedef Key                value_type;
    typedef Compare            key_compare;
    typedef Compare            value_compare;
    typedef Allocator          allocator_type;

  private:
    
    typedef __RWSTD::__rb_tree<key_type, value_type, 
                    __RWSTD::ident<value_type, key_type>, 
                    key_compare, allocator_type> rep_type;
    rep_type t;

  public:
    //
    // Types
    //
    typedef _TYPENAME rep_type::const_reference         reference;
    typedef _TYPENAME rep_type::const_reference         const_reference;
    typedef _TYPENAME rep_type::const_iterator          iterator;
    typedef _TYPENAME rep_type::const_iterator          const_iterator;
    typedef _TYPENAME rep_type::size_type               size_type;
    typedef _TYPENAME rep_type::difference_type         difference_type;
    typedef _TYPENAME rep_type::reverse_iterator        reverse_iterator;
    typedef _TYPENAME rep_type::const_reverse_iterator  const_reverse_iterator;

    //
    // construct/copy/destroy
    //
    _EXPLICIT set (const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()),
         const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) : t(_RWSTD_COMP, false, alloc) {}

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    set () : t(Compare(), false, Allocator()) {}

    _EXPLICIT set (const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare())) : t(_RWSTD_COMP, false, Allocator()) {}
#endif

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    set (InputIterator first, InputIterator last,
         const Compare& comp = Compare(),
         const Allocator& alloc = Allocator()) : t(comp, false, alloc)
    {
        while (first != last) t.insert(*first++);
    }
#else
    set (const value_type* first, const value_type* last,
         const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()),
         const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) : t(_RWSTD_COMP, false, alloc)
    {
        while (first != last) t.insert(*first++);
    }
    
    set (const_iterator first, const_iterator last,
         const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()),
         const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) : t(_RWSTD_COMP, false, alloc)
    {
        while (first != last) t.insert(*first++);
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    set (const value_type* first, const value_type* last) : t(Compare(), false, Allocator())
    {
        while (first != last) t.insert(*first++);
    }
    
    set (const value_type* first, const value_type* last,
         const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare())) : t(_RWSTD_COMP, false, Allocator())
    {
        while (first != last) t.insert(*first++);
    }
    
    set (const_iterator first, const_iterator last) : t(Compare(), false, Allocator())
    {
        while (first != last) t.insert(*first++);
    }

    set (const_iterator first, const_iterator last,
         const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare())) : t(_RWSTD_COMP, false, Allocator())
    {
        while (first != last) t.insert(*first++);
    }
#endif
#endif

    set (const set<Key, Compare, Allocator>& x) : t(x.t, false) {}
    set<Key, Compare, Allocator>& operator= (const set<Key, Compare, Allocator>& x)
    {
          t = x.t; return *this;
    }
    allocator_type get_allocator() const
    {
        return t.get_allocator();
    }

    //
    // iterators
    //
    iterator                 begin  ()       { return t.begin();  }
    const_iterator           begin  () const { return t.begin();  }
    iterator                 end    ()       { return t.end();    }
    const_iterator           end    () const { return t.end();    }
    reverse_iterator         rbegin ()       { return t.rbegin(); } 
    const_reverse_iterator   rbegin () const { return t.rbegin(); } 
    reverse_iterator         rend   ()       { return t.rend();   }
    const_reverse_iterator   rend   () const { return t.rend();   }

    //
    // capacity
    //
    bool        empty    () const { return t.empty();    }
    size_type   size     () const { return t.size();     }
    size_type   max_size () const { return t.max_size(); }

    //
    // modifiers
    //
#ifdef _RWSTD_NO_MEMBER_TYPE_TPARAM
    typedef _TYPENAME rep_type::iterator t_iterator;
#endif
#ifndef _RWSTD_NO_RET_TEMPLATE
    pair<iterator,bool> insert (const value_type& x)
#else
    typedef pair<iterator, bool> pair_iterator_bool;
    //
    // typedef done to get around compiler bug.
    //
    pair_iterator_bool insert (const value_type& x)
#endif
    {
#ifndef _RWSTD_NO_MEMBER_TYPE_TPARAM
        pair<_TYPENAME rep_type::iterator, bool> p = t.insert(x); 
#else
        pair<t_iterator,bool> p = t.insert(x); 
#endif
        return pair<iterator, bool>(p.first, p.second);
    }
    iterator insert (iterator position, const value_type& x)
    {
#ifndef HPPA_WA       
        return t.insert(_RWSTD_REINTERPRET_CAST(_TYPENAME rep_type::iterator&,position), x);
#else
        return t.insert(*(_TYPENAME rep_type::iterator*&)&position, x);
#endif
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void insert (InputIterator first, InputIterator last)
    {
        while (first != last) t.insert(*first++);
    }
#else
    void insert (const value_type* first, const value_type* last)
    {
        while (first != last) t.insert(*first++);
    }
    void insert (const_iterator first, const_iterator last)
    {
        while (first != last) t.insert(*first++);
    }
#endif

    iterator erase (iterator position)
    {
#ifndef HPPA_WA
        return t.erase((_TYPENAME rep_type::iterator&)position);
#else
        return t.erase(*(_TYPENAME rep_type::iterator*&)&position);
#endif
    }
    size_type erase (const key_type& x)
    {
        return t.erase(x); 
    }
    iterator erase (iterator first, iterator last)
    {
#ifndef HPPA_WA
        return t.erase(_RWSTD_REINTERPRET_CAST(_TYPENAME rep_type::iterator&,first),
		       _RWSTD_REINTERPRET_CAST(_TYPENAME rep_type::iterator&,last));
#else
        return t.erase(*(_TYPENAME rep_type::iterator*&)&first,
                       *(_TYPENAME rep_type::iterator*&)&last);
#endif
    }
    void clear ()   { erase(begin(),end()); }
    void swap (set<Key, Compare, Allocator>& x) { t.swap(x.t); }

    //
    // observers
    //
    key_compare        key_comp   () const { return t.key_comp(); }
    value_compare      value_comp () const { return t.key_comp(); }

    //
    // set operations
    //
    iterator  find        (const key_type& x) const { return t.find(x);       }
    size_type count       (const key_type& x) const { return t.count(x);      }
    iterator  lower_bound (const key_type& x) const { return t.lower_bound(x);}
    iterator  upper_bound (const key_type& x) const { return t.upper_bound(x);}

#ifndef _RWSTD_NO_RET_TEMPLATE
    pair<iterator,iterator> equal_range(const key_type& x) const
#else
    typedef  pair<iterator, iterator> pair_iterator_iterator;
    //
    // typedef done to get around compiler bug
    //
    pair_iterator_iterator equal_range (const key_type& x) const
#endif
    {
        return t.equal_range(x);
    }
};

//
// Note that _RWSTD_SIMPLE_DEFAULT(x) and _RWSTD_COMPLEX_DEFAULT(x)
// will expand to: ' = x', or nothing,
// depending on your compiler's capabilities and/or
// flag settings (see stdcomp).
//
template <class Key, 
          class Compare _RWSTD_COMPLEX_DEFAULT(less<Key>), 
          class Allocator _RWSTD_SIMPLE_DEFAULT(allocator<Key>) > 
class multiset
{
  public:
    //  
    // types
    //
    typedef Key       key_type;
    typedef Key       value_type;
    typedef Compare   key_compare;
    typedef Compare   value_compare;
    typedef Allocator allocator_type;
  private:
    
    typedef __RWSTD::__rb_tree<key_type, value_type, 
                    __RWSTD::ident<value_type, key_type>, 
                    key_compare, allocator_type> rep_type;
    rep_type t;

  public:
    //
    // types
    //
    typedef _TYPENAME rep_type::const_reference         reference;
    typedef _TYPENAME rep_type::const_reference         const_reference;
    typedef _TYPENAME rep_type::const_iterator          iterator;
    typedef _TYPENAME rep_type::const_iterator          const_iterator;
    typedef _TYPENAME rep_type::size_type               size_type;
    typedef _TYPENAME rep_type::difference_type         difference_type;
    typedef _TYPENAME rep_type::reverse_iterator        reverse_iterator;
    typedef _TYPENAME rep_type::const_reverse_iterator  const_reverse_iterator;

    //
    // construct/copy/destroy
    //
    _EXPLICIT multiset (const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()),
         const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) : t(_RWSTD_COMP, true, alloc) {}

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    _EXPLICIT multiset (void) : t(Compare(), true, Allocator()) {}

    _EXPLICIT multiset (const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare())) : t(_RWSTD_COMP, true, Allocator()) {}
#endif

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    multiset (InputIterator first, InputIterator last, 
              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()),
         const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) : t(_RWSTD_COMP, true, alloc)
    {
        while (first != last) t.insert(*first++);
    }
#else
    multiset (const value_type* first, const value_type* last, 
              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()),
         const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) : t(_RWSTD_COMP, true, alloc)
    {
        while (first != last) t.insert(*first++);
    }
    multiset (const_iterator first, const_iterator last, 
              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare()),
         const Allocator& alloc _RWSTD_DEFAULT_ARG(Allocator())) : t(_RWSTD_COMP, true, alloc)
    {
        while (first != last) t.insert(*first++);
    }

#ifdef _RWSTD_NO_DEFAULT_TEMPLATE_ARGS
    multiset (const value_type* first, const value_type* last) : t(Compare(), true, Allocator())
    {
        while (first != last) t.insert(*first++);
    }

    multiset (const value_type* first, const value_type* last, 
              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare())) : t(_RWSTD_COMP, true, Allocator())
    {
        while (first != last) t.insert(*first++);
    }

    multiset (const_iterator first, const_iterator last) : t(Compare(), true, Allocator())
    {
        while (first != last) t.insert(*first++);
    }

    multiset (const_iterator first, const_iterator last, 
              const Compare& _RWSTD_COMP _RWSTD_DEFAULT_ARG(Compare())) : t(_RWSTD_COMP, true, Allocator())
    {
        while (first != last) t.insert(*first++);
    }
#endif

#endif

    multiset (const multiset<Key, Compare, Allocator>& x) : t(x.t, true) {}
    multiset<Key, Compare, Allocator>& 
        operator= (const multiset<Key, Compare, Allocator>& x)
    {
        t = x.t; return *this;
    }
    allocator_type get_allocator() const
    {
        return t.get_allocator();
    }

    //
    // iterators
    //
    iterator                 begin  ()       { return t.begin();  }
    const_iterator           begin  () const { return t.begin();  }
    iterator                 end    ()       { return t.end();    }
    const_iterator           end    () const { return t.end();    }
    reverse_iterator         rbegin ()       { return t.rbegin(); } 
    const_reverse_iterator   rbegin () const { return t.rbegin(); } 
    reverse_iterator         rend   ()       { return t.rend();   }
    const_reverse_iterator   rend   () const { return t.rend();   }

    //
    // capacity
    //
    bool       empty    () const { return t.empty();    }
    size_type  size     () const { return t.size();     }
    size_type  max_size () const { return t.max_size(); }

    //
    // modifiers
    //
    iterator insert (const value_type& x) { return t.insert(x).first; }
    iterator insert (iterator position, const value_type& x)
    {
#ifndef HPPA_WA
        return t.insert(_RWSTD_REINTERPRET_CAST(_TYPENAME rep_type::iterator&,position), x);
#else
        return t.insert(*(_TYPENAME rep_type::iterator*&)&position, x);
#endif
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES
    template<class InputIterator>
    void insert (InputIterator first, InputIterator last)
    {
        while (first != last) t.insert(*first++);
    }
#else
    void insert (const value_type* first, const value_type* last)
    {
        while (first != last) t.insert(*first++);
    }
    void insert (const_iterator first, const_iterator last)
    {
        while (first != last) t.insert(*first++);
    }
#endif

    iterator erase (iterator position)
    {
#ifndef HPPA_WA
        return t.erase(_RWSTD_REINTERPRET_CAST(_TYPENAME rep_type::iterator&,position));
#else
        return t.erase(*(_TYPENAME rep_type::iterator*&)&position);
#endif 
    }
    size_type erase (const key_type& x) { return t.erase(x); }
    iterator erase (iterator first, iterator last)
    {
#ifndef HPPA_WA
      return t.erase(_RWSTD_REINTERPRET_CAST(_TYPENAME rep_type::iterator&,first),
		     _RWSTD_REINTERPRET_CAST(_TYPENAME rep_type::iterator&,last)); 
#else
      return t.erase(*(_TYPENAME rep_type::iterator*&)&first,
                     *(_TYPENAME rep_type::iterator*&)&last);
#endif
    }
    void clear ()   { erase(begin(),end()); }
    void swap (multiset<Key, Compare, Allocator>& x) { t.swap(x.t); }

    //
    // observers
    //
    key_compare   key_comp   () const { return t.key_comp(); }
    value_compare value_comp () const { return t.key_comp(); }

    //
    // set operations
    //
    iterator  find        (const key_type& x) const { return t.find(x);  }
    size_type count       (const key_type& x) const { return t.count(x); }
    iterator  lower_bound (const key_type& x) const
    {
        return t.lower_bound(x);
    }
    iterator  upper_bound (const key_type& x) const
    {
        return t.upper_bound(x); 
    }
#ifndef _RWSTD_NO_RET_TEMPLATE
    pair<iterator,iterator> equal_range (const key_type& x) const
#else
    typedef  pair<iterator, iterator> pair_iterator_iterator; 
    //
    // typedef done to get around compiler bug
    //
    pair_iterator_iterator equal_range (const key_type& x) const
#endif
    {
        return t.equal_range(x);
    }
};

template <class Key, class Compare, class Allocator>
inline bool operator== (const set<Key, Compare, Allocator>& x, 
                        const set<Key, Compare, Allocator>& y)
{
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

template <class Key, class Compare, class Allocator>
inline bool operator< (const set<Key, Compare, Allocator>& x, 
                       const set<Key, Compare, Allocator>& y)
{
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
template <class Key, class Compare, class Allocator>
inline bool operator!= (const set<Key,Compare,Allocator>& x, 
                        const set<Key,Compare,Allocator>& y)
{
    return !(x == y);
}

template <class Key, class Compare, class Allocator>
inline bool operator> (const set<Key,Compare,Allocator>& x, 
                       const set<Key,Compare,Allocator>& y)
{
    return y < x;
}

template <class Key, class Compare, class Allocator>
inline bool operator>= (const set<Key,Compare,Allocator>& x, 
                        const set<Key,Compare,Allocator>& y)
{
    return !(x < y);
}

template <class Key, class Compare, class Allocator>
inline bool operator<= (const set<Key,Compare,Allocator>& x, 
                        const set<Key,Compare,Allocator>& y)
{
    return !(y <  x);
}
#endif

#ifndef _RWSTD_MS40_NO_OVERLOAD_SWAP
template <class Key, class Compare, class Allocator>
void swap(set<Key,Compare,Allocator>& a, 
          set<Key,Compare,Allocator>& b)
{
    a.swap(b);
}
#endif

template <class Key, class Compare, class Allocator>
inline bool operator== (const multiset<Key, Compare, Allocator>& x, 
                        const multiset<Key, Compare, Allocator>& y)
{
    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

template <class Key, class Compare, class Allocator>
inline bool operator< (const multiset<Key, Compare, Allocator>& x, 
                       const multiset<Key, Compare, Allocator>& y)
{
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

#if !defined(_RWSTD_NO_NAMESPACE) || !defined(_RWSTD_NO_PART_SPEC_OVERLOAD)
template <class Key, class Compare, class Allocator>
inline bool operator!= (const multiset<Key,Compare,Allocator>& x, 
                        const multiset<Key,Compare,Allocator>& y)
{
    return !(x == y);
}

template <class Key, class Compare, class Allocator>
inline bool operator> (const multiset<Key,Compare,Allocator>& x, 
                       const multiset<Key,Compare,Allocator>& y)
{
    return y < x;
}

template <class Key, class Compare, class Allocator>
inline bool operator>= (const multiset<Key,Compare,Allocator>& x, 
                        const multiset<Key,Compare,Allocator>& y)
{
    return !(x < y);
}

template <class Key, class Compare, class Allocator>
inline bool operator<= (const multiset<Key,Compare,Allocator>& x, 
                        const multiset<Key,Compare,Allocator>& y)
{
    return !(y <  x);
}
#endif

#ifndef _RWSTD_MS40_NO_OVERLOAD_SWAP
template <class Key, class Compare, class Allocator>
void swap(multiset<Key,Compare,Allocator>& a, 
          multiset<Key,Compare,Allocator>& b)
{
    a.swap(b);
}
#endif

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __restore
#   endif
#endif

#endif