// queue standard header
#pragma once
#ifndef _QUEUE_
#define _QUEUE_
#ifndef RC_INVOKED
#include <algorithm>
#include <deque>
#include <xfunctional>
#include <vector>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)
_STD_BEGIN
		// TEMPLATE CLASS queue
template<class _Ty,
	class _Container = deque<_Ty> >
	class queue
	{	// FIFO queue implemented with a container
public:
	typedef queue<_Ty, _Container> _Myt;
	typedef _Container container_type;
	typedef typename _Container::value_type value_type;
	typedef typename _Container::size_type size_type;
	typedef typename _Container::reference reference;
	typedef typename _Container::const_reference const_reference;

	queue()
		: c()
		{	// construct with empty container
		}

	queue(const _Myt& _Right)
		: c(_Right.c)
		{	// construct by copying _Right container
		}

	explicit queue(const _Container& _Cont)
		: c(_Cont)
		{	// construct by copying specified container
		}

	_Myt& operator=(const _Myt& _Right)
		{	// assign by copying _Right
		c = _Right.c;
		return (*this);
		}

	queue(_Myt&& _Right)
		: c(_STD move(_Right.c))
		{	// construct by moving _Right
		}

	explicit queue(_Container&& _Cont)
		: c(_STD move(_Cont))
		{	// construct by moving specified container
		}

	_Myt& operator=(_Myt&& _Right)
		{	// assign by moving _Right
		c = _STD move(_Right.c);
		return (*this);
		}

	void push(value_type&& _Val)
		{	// insert element at beginning
		c.push_back(_STD move(_Val));
		}

	template<class _Valty>
		void emplace(_Valty&& _Val)
		{	// insert element at beginning
		c.emplace_back(_STD forward<_Valty>(_Val));
		}

	void swap(_Myt&& _Right)
		{	// exchange contents with movable _Right
		c.swap(_STD move(_Right.c));
		}

	bool empty() const
		{	// test if queue is empty
		return (c.empty());
		}

	size_type size() const
		{	// return length of queue
		return (c.size());
		}

	reference front()
		{	// return first element of mutable queue
		return (c.front());
		}

	const_reference front() const
		{	// return first element of nonmutable queue
		return (c.front());
		}

	reference back()
		{	// return last element of mutable queue
		return (c.back());
		}

	const_reference back() const
		{	// return last element of nonmutable queue
		return (c.back());
		}

	void push(const value_type& _Val)
		{	// insert element at beginning
		c.push_back(_Val);
		}

	void pop()
		{	// erase element at end
		c.pop_front();
		}

	const _Container& _Get_container() const
		{	// get reference to container
		return (c);
		}

	void swap(_Myt& _Right)
		{	// exchange contents with _Right
		c.swap(_Right.c);
		}

protected:
	_Container c;	// the underlying container
	};

		// queue TEMPLATE FUNCTIONS
template<class _Ty,
	class _Container> inline
	void swap(queue<_Ty, _Container>& _Left,
		queue<_Ty, _Container>& _Right)
	{	// swap _Left and _Right queues
	_Left.swap(_Right);
	}

template<class _Ty,
	class _Container> inline
	void swap(queue<_Ty, _Container>& _Left,
		queue<_Ty, _Container>&& _Right)
	{	// swap _Left and _Right queues
	typedef queue<_Ty, _Container> _Myt;
	_Left.swap(_STD forward<_Myt>(_Right));
	}

template<class _Ty,
	class _Container> inline
	void swap(queue<_Ty, _Container>&& _Left,
		queue<_Ty, _Container>& _Right)
	{	// swap _Left and _Right queues
	typedef queue<_Ty, _Container> _Myt;
	_Right.swap(_STD forward<_Myt>(_Left));
	}

template<class _Ty,
	class _Container> inline
	bool operator==(const queue<_Ty, _Container>& _Left,
		const queue<_Ty, _Container>& _Right)
	{	// test for queue equality
	return (_Left._Get_container() == _Right._Get_container());
	}

template<class _Ty,
	class _Container> inline
	bool operator!=(const queue<_Ty, _Container>& _Left,
		const queue<_Ty, _Container>& _Right)
	{	// test for queue inequality
	return (!(_Left == _Right));
	}

template<class _Ty,
	class _Container> inline
	bool operator<(const queue<_Ty, _Container>& _Left,
		const queue<_Ty, _Container>& _Right)
	{	// test if _Left < _Right for queues
	return (_Left._Get_container() < _Right._Get_container());
	}

template<class _Ty,
	class _Container> inline
	bool operator>(const queue<_Ty, _Container>& _Left,
		const queue<_Ty, _Container>& _Right)
	{	// test if _Left > _Right for queues
	return (_Right < _Left);
	}

template<class _Ty,
	class _Container> inline
	bool operator<=(const queue<_Ty, _Container>& _Left,
		const queue<_Ty, _Container>& _Right)
	{	// test if _Left <= _Right for queues
	return (!(_Right < _Left));
	}

template<class _Ty,
	class _Container> inline
	bool operator>=(const queue<_Ty, _Container>& _Left,
		const queue<_Ty, _Container>& _Right)
	{	// test if _Left >= _Right for queues
	return (!(_Left < _Right));
	}

		// TEMPLATE CLASS priority_queue
template<class _Ty,
	class _Container = vector<_Ty>,
	class _Pr = less<typename _Container::value_type> >
	class priority_queue
	{	// priority queue implemented with a _Container
public:
	typedef priority_queue<_Ty, _Container, _Pr> _Myt;
	typedef _Container container_type;
	typedef typename _Container::value_type value_type;
	typedef typename _Container::size_type size_type;
	typedef typename _Container::reference reference;
	typedef typename _Container::const_reference const_reference;

	priority_queue()
		: c(), comp()
		{	// construct with empty container, default comparator
		}

	priority_queue(const _Myt& _Right)
		: c(_Right.c), comp(_Right.comp)
		{	// construct by copying _Right
		}

	explicit priority_queue(const _Pr& _Pred)
		: c(), comp(_Pred)
		{	// construct with empty container, specified comparator
		}

	priority_queue(const _Pr& _Pred, const _Container& _Cont)
		: c(_Cont), comp(_Pred)
		{	// construct by copying specified container, comparator
		make_heap(c.begin(), c.end(), comp);
		}

	template<class _Iter>
		priority_queue(_Iter _First, _Iter _Last)
		: c(_First, _Last), comp()
		{	// construct by copying [_First, _Last), default comparator
		make_heap(c.begin(), c.end(), comp);
		}

	template<class _Iter>
		priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred)
		: c(_First, _Last), comp(_Pred)
		{	// construct by copying [_First, _Last), specified comparator
		make_heap(c.begin(), c.end(), comp);
		}

	template<class _Iter>
		priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred,
			const _Container& _Cont)
		: c(_Cont), comp(_Pred)
		{	// construct by copying [_First, _Last), container, and comparator
		c.insert(c.end(), _First, _Last);
		make_heap(c.begin(), c.end(), comp);
		}

	_Myt& operator=(const _Myt& _Right)
		{	// assign by copying _Right
		c = _Right.c;
		comp = _Right.comp;
		return (*this);
		}

	priority_queue(_Myt&& _Right)
		: c(_STD move(_Right.c)), comp(_STD move(_Right.comp))
		{	// construct by moving _Right
		}

	priority_queue(const _Pr& _Pred, _Container&& _Cont)
		: c(_STD move(_Cont)), comp(_Pred)
		{	// construct by moving specified container, comparator
		make_heap(c.begin(), c.end(), comp);
		}

	template<class _Iter>
		priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred,
			_Container&& _Cont)
		: c(_STD move(_Cont)), comp(_Pred)
		{	// construct by copying [_First, _Last), moving container
		c.insert(c.end(), _First, _Last);
		make_heap(c.begin(), c.end(), comp);
		}

	_Myt& operator=(_Myt&& _Right)
		{	// assign by moving _Right
		c = _STD move(_Right.c);
		comp = _Right.comp;
		return (*this);
		}

	void push(value_type&& _Val)
		{	// insert element at beginning
		c.push_back(_STD move(_Val));
		push_heap(c.begin(), c.end(), comp);
		}

	template<class _Valty>
		void emplace(_Valty&& _Val)
		{	// insert element at beginning
		c.emplace_back(_STD forward<_Valty>(_Val));
		push_heap(c.begin(), c.end(), comp);
		}

	void swap(_Myt&& _Right)
		{	// exchange contents with movable _Right
		c.swap(_STD move(_Right.c));
		_Swap_adl(comp, _Right.comp);
		}

	bool empty() const
		{	// test if queue is empty
		return (c.empty());
		}

	size_type size() const
		{	// return length of queue
		return (c.size());
		}

	const_reference top() const
		{	// return highest-priority element
		return (c.front());
		}

	reference top()
		{	// return mutable highest-priority element (retained)
		return (c.front());
		}

	void push(const value_type& _Val)
		{	// insert value in priority order
		c.push_back(_Val);
		push_heap(c.begin(), c.end(), comp);
		}

	void pop()
		{	// erase highest-priority element
		pop_heap(c.begin(), c.end(), comp);
		c.pop_back();
		}

	void swap(_Myt& _Right)
		{	// exchange contents with _Right
		c.swap(_Right.c);
		_Swap_adl(comp, _Right.comp);
		}

protected:
	_Container c;	// the underlying container
	_Pr comp;	// the comparator functor
	};

		// priority_queue TEMPLATE FUNCTIONS
template<class _Ty,
	class _Container,
	class _Pr> inline
	void swap(priority_queue<_Ty, _Container, _Pr>& _Left,
		priority_queue<_Ty, _Container, _Pr>& _Right)
	{	// swap _Left and _Right queues
	_Left.swap(_Right);
	}

template<class _Ty,
	class _Container,
	class _Pr> inline
	void swap(priority_queue<_Ty, _Container, _Pr>& _Left,
		priority_queue<_Ty, _Container, _Pr>&& _Right)
	{	// swap _Left and _Right queues
	_Left.swap(_Right);
	}

template<class _Ty,
	class _Container,
	class _Pr> inline
	void swap(priority_queue<_Ty, _Container, _Pr>&& _Left,
		priority_queue<_Ty, _Container, _Pr>& _Right)
	{	// swap _Left and _Right queues
	_Right.swap(_Left);
	}
_STD_END
 #pragma warning(pop)
 #pragma pack(pop)

#endif /* RC_INVOKED */
#endif /* _QUEUE_ */

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

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.20:0009 */
