blob: b1875c90de7422ad2de4c503828780eb15362ec8 [file] [log] [blame]
// -*- C++ -*-
/***************************************************************************
*
* <queue> - definition of the C++ Standard Library queue class template
*
* $Id$
*
***************************************************************************
*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed
* with this work for additional information regarding copyright
* ownership. The ASF licenses this file to you under the Apache
* License, Version 2.0 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
* implied. See the License for the specific language governing
* permissions and limitations under the License.
*
* Copyright 1994-2006 Rogue Wave Software.
*
***************************************************************************
*
* 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.
*
**************************************************************************/
#ifndef _RWSTD_QUEUE_INCLUDED
#define _RWSTD_QUEUE_INCLUDED
#include <deque>
#include <functional>
#include <vector>
#include <rw/_heap.h>
#include <rw/_defs.h>
_RWSTD_NAMESPACE (std) {
template <class _TypeT, class _Container = deque<_TypeT> >
class queue;
template <class _TypeT, class _Container>
inline bool operator== (const queue<_TypeT, _Container>&,
const queue<_TypeT, _Container>&);
template <class _TypeT, class _Container>
inline bool operator< (const queue<_TypeT, _Container>&,
const queue<_TypeT, _Container>&);
template <class _TypeT, class _Container>
class queue
{
friend bool _RWSTD_SPECIALIZED_FRIEND (operator==)
(const queue&, const queue&);
friend bool _RWSTD_SPECIALIZED_FRIEND (operator<)
(const queue&, const queue&);
public:
typedef _Container container_type;
typedef typename container_type::value_type value_type;
typedef typename container_type::size_type size_type;
// lwg issue 307: additional typedefs
typedef typename container_type::reference reference;
typedef typename container_type::const_reference const_reference;
protected:
container_type c;
public:
explicit
queue (const container_type &__c = container_type ())
: c (__c) { }
bool empty () const {
return c.empty ();
}
size_type size () const {
return c.size ();
}
// lwg issue 307: return reference instead of value_type&
reference front () {
return c.front ();
}
// lwg issue 307: return const_reference instead of const value_type&
const_reference front () const {
return c.front ();
}
// lwg issue 307: return reference instead of value_type&
reference back () {
return c.back ();
}
// lwg issue 307: return const_reference instead of const value_type&
const_reference back () const {
return c.back ();
}
void push (const value_type &__x) {
c.push_back (__x);
}
void pop () {
c.pop_front ();
}
};
template <class _TypeT, class _Container>
inline bool operator== (const queue<_TypeT, _Container> &__x,
const queue<_TypeT, _Container> &__y)
{
return __x.c == __y.c;
}
template <class _TypeT, class _Container>
inline bool operator< (const queue<_TypeT, _Container> &__x,
const queue<_TypeT, _Container> &__y)
{
return __x.c < __y.c;
}
template <class _TypeT, class _Container>
inline bool operator!= (const queue<_TypeT, _Container> &__x,
const queue<_TypeT, _Container> &__y)
{
return !(__x == __y);
}
template <class _TypeT, class _Container>
inline bool operator> (const queue<_TypeT, _Container> &__x,
const queue<_TypeT, _Container> &__y)
{
return __y < __x;
}
template <class _TypeT, class _Container>
inline bool operator>= (const queue<_TypeT, _Container> &__x,
const queue<_TypeT, _Container> &__y)
{
return !(__x < __y);
}
template <class _TypeT, class _Container>
inline bool operator<= (const queue<_TypeT, _Container> &__x,
const queue<_TypeT, _Container> &__y)
{
return !(__y < __x);
}
template<class _TypeT,
class _Container = vector<_TypeT>,
class _Compare = less<typename _Container::value_type> >
class priority_queue
{
public:
typedef _Container container_type;
typedef typename container_type::value_type value_type;
typedef typename container_type::size_type size_type;
// lwg issue 307: additional typedefs
typedef typename container_type::reference reference;
typedef typename container_type::const_reference const_reference;
protected:
container_type c;
_Compare comp;
public:
explicit
priority_queue (const _Compare &__cmp = _Compare (),
const container_type &__c = container_type ())
: c (__c), comp (__cmp) {
_STD::make_heap (c.begin (), c.end (), comp);
}
template <class _InputIter>
priority_queue (_InputIter __first, _InputIter __last,
const _Compare &__cmp = _Compare (),
const _Container &__c = container_type ())
: c (__c), comp (__cmp) {
c.insert (c.end (), __first, __last);
_STD::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) {
c.push_back (__x);
_STD::push_heap (c.begin (), c.end (), comp);
}
void pop () {
_STD::pop_heap (c.begin (), c.end (), comp);
c.pop_back ();
}
};
} // namespace std
#endif // _RWSTD_QUEUE_INCLUDED