/** -*- C++ -*-
 **
 **  KAI C++ Compiler
 **
 **  Copyright (C) 1996-2001 Intel Corp. All rights reserved.
 **/
/**
 **  Lib++  : The Modena C++ Standard Library,
 **           Version 2.4, October 1997
 **
 **  Copyright (c) 1995-1997 Modena Software Inc.
 **/
#ifndef __KAI_QUEUE
#define __KAI_QUEUE

#include <mcompile.h>
#include <heap>
#include <functional>
#include <deque>
#include <vector>

namespace std {

// Subclause 23.2.3.1 -- clause queue
template <class T, class Container = deque<T> >
class queue {
    template <class T2, class Container2>
    friend bool operator==(const queue<T2, Container2>& x, const queue<T2, Container2>& y);
    template <class T2, class Container2>
    friend bool operator<(const queue<T2, Container2>& x, const queue<T2, Container2>& y);
    template <class T2, class Container2>
    friend bool operator!=(const queue<T2, Container2>& x, const queue<T2, Container2>& y);
    template <class T2, class Container2>
    friend bool operator>(const queue<T2, Container2>& x, const queue<T2, Container2>& y);
    template <class T2, class Container2>
    friend bool operator>=(const queue<T2, Container2>& x, const queue<T2, Container2>& y);
    template <class T2, class Container2>
    friend bool operator<=(const queue<T2, Container2>& x, const queue<T2, Container2>& y);

public:
    typedef typename Container::value_type       value_type;
    typedef typename Container::size_type        size_type;
    typedef Container                            container_type;

protected:
    Container c;

public:
    explicit queue(const Container& cont = Container()) : c(cont) {}

    bool               empty()             const { return c.empty(); }
    size_type          size()              const { return c.size();  }
    value_type&        front()                   { return c.front(); }
    const value_type&  front()             const { return c.front(); }
    value_type&        back()                    { return c.back();  }
    const value_type&  back()              const { return c.back();  }
    void               push(const value_type& x) { c.push_back(x);   }
    void               pop()                     { c.pop_front();    }
};

template <class T2, class Container2 >
bool operator==(const queue<T2, Container2>& x, const queue<T2, Container2>& y) { return x.c == y.c; }
template <class T2, class Container2 >
bool operator<(const queue<T2, Container2>& x, const queue<T2, Container2>& y) { return x.c < y.c; }
template <class T2, class Container2 >
bool operator!=(const queue<T2, Container2>& x, const queue<T2, Container2>& y) { return x.c != y.c; }
template <class T2, class Container2 >
bool operator>(const queue<T2, Container2>& x, const queue<T2, Container2>& y) { return x.c > y.c; }
template <class T2, class Container2 >
bool operator>=(const queue<T2, Container2>& x, const queue<T2, Container2>& y) { return x.c >= y.c; }
template <class T2, class Container2 >
bool operator<=(const queue<T2, Container2>& x, const queue<T2, Container2>& y) { return x.c <= y.c; }


// Subclause 23.2.3.2 -- clause priority_queue
template <class T, class Container = vector<T>,
    class Compare = less<typename Container::value_type> >
class priority_queue
{
public:
    typedef typename Container::value_type	value_type;
    typedef typename Container::size_type	size_type;
    typedef Container				container_type;

    explicit priority_queue(const Compare& x = Compare(), const Container& cont = Container()) : c(cont), comp(x) {}

    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last,
		   const Compare& x = Compare(), const Container& cont = Container())
	: c(cont), 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 value_type& top() const { return c.front(); }

    void push(const value_type& x);
    void pop();

protected:
    Container c;
    Compare comp;

};
template <class T, class Container, class Compare>
void priority_queue<T,Container, Compare>::push (const value_type& x)
{
    MSIPL_TRY {     
	c.push_back(x); 
	push_heap(c.begin(), c.end(), comp);
    }
    MSIPL_CATCH {
	c.clear();
	MSIPL_RETHROW;
    }
}
template <class T, class Container, class Compare>
void priority_queue<T,Container, Compare>::pop()
{
    MSIPL_TRY {
	pop_heap(c.begin(), c.end(), comp);
	c.pop_back(); 
    }
    MSIPL_CATCH {
	c.clear();
	MSIPL_RETHROW;
    }
}

} // namespace std

#endif /* __KAI_QUEUE */