Subversion Repositories Kolibri OS

/*

 *

 * 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.

 *

 *

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * 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.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 */

/* NOTE: This is an internal header file, included by other STL headers.

 *   You should not attempt to use it directly.

 */

#ifndef __SGI_STL_INTERNAL_QUEUE_H

#define __SGI_STL_INTERNAL_QUEUE_H

#include 

namespace std

{

// Forward declarations of operators < and ==, needed for friend declaration.

template 

          class _Sequence = deque<_Tp> >

class queue;

template 

inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);

template 

inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);

template 

class queue

{

  // concept requirements

  __glibcpp_class_requires(_Tp, _SGIAssignableConcept);

  __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept);

  __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept);

  typedef typename _Sequence::value_type _Sequence_value_type;

  __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);

  template 

  friend bool operator== (const queue<_Tp1, _Seq1>&,

                          const queue<_Tp1, _Seq1>&);

  template 

  friend bool operator< (const queue<_Tp1, _Seq1>&,

                         const queue<_Tp1, _Seq1>&);

public:

  typedef typename _Sequence::value_type      value_type;

  typedef typename _Sequence::size_type       size_type;

  typedef          _Sequence                  container_type;

  typedef typename _Sequence::reference       reference;

  typedef typename _Sequence::const_reference const_reference;

protected:

  _Sequence c;

public:

  explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {}

  bool empty() const { return c.empty(); }

  size_type size() const { return c.size(); }

  reference front() { return c.front(); }

  const_reference front() const { return c.front(); }

  reference back() { return c.back(); }

  const_reference back() const { return c.back(); }

  void push(const value_type& __x) { c.push_back(__x); }

  void pop() { c.pop_front(); }

};

template 

bool

operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)

{

  return __x.c == __y.c;

}

template 

bool

operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)

{

  return __x.c < __y.c;

}

template 

bool

operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)

{

  return !(__x == __y);

}

template 

bool

operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)

{

  return __y < __x;

}

template 

bool

operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)

{

  return !(__y < __x);

}

template 

bool

operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)

{

  return !(__x < __y);

}

template 

          class _Sequence = vector<_Tp>,

          class _Compare  = less >

class priority_queue

{

  // concept requirements

  __glibcpp_class_requires(_Tp, _SGIAssignableConcept);

  __glibcpp_class_requires(_Sequence, _SequenceConcept);

  __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept);

  typedef typename _Sequence::value_type _Sequence_value_type;

  __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);

  __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept);

public:

  typedef typename _Sequence::value_type      value_type;

  typedef typename _Sequence::size_type       size_type;

  typedef          _Sequence                  container_type;

  typedef typename _Sequence::reference       reference;

  typedef typename _Sequence::const_reference const_reference;

protected:

  _Sequence c;

  _Compare comp;

public:

  explicit priority_queue(const _Compare& __x = _Compare(),

			  const _Sequence& __s = _Sequence())

    : c(__s), comp(__x)

    { make_heap(c.begin(), c.end(), comp); }

  template 

  priority_queue(_InputIterator __first, _InputIterator __last,

                 const _Compare& __x = _Compare(),

		 const _Sequence& __s = _Sequence())

  : c(__s), comp(__x)

  {

    c.insert(c.end(), __first, __last);

    make_heap(c.begin(), c.end(), comp);

  }

  bool empty() const { return c.empty(); }

  size_type size() const { return c.size(); }

  const_reference top() const { return c.front(); }

  void push(const value_type& __x) {

    __STL_TRY {

      c.push_back(__x);

      push_heap(c.begin(), c.end(), comp);

    }

    __STL_UNWIND(c.clear());

  }

  void pop() {

    __STL_TRY {

      pop_heap(c.begin(), c.end(), comp);

      c.pop_back();

    }

    __STL_UNWIND(c.clear());

  }

};

// no equality is provided

} // namespace std

#endif /* __SGI_STL_INTERNAL_QUEUE_H */

// Local Variables:

// mode:C++

// End: