#ifndef __S34_STABLE_PRIORITY_QUEUE_H_
#define __S34_STABLE_PRIORITY_QUEUE_H_


namespace stx{
	
template <class T, class Container = std::list<T>,
          class Compare = std::less<Container::value_type> >
class stable_priority_queue {
public:
  typedef Container::value_type value_type;
  typedef Container::size_type  size_type;
  typedef Container             container_type;

protected:
  Container c;
  Compare comp;

private:
  template<class InputIterator>
    void push(InputIterator first, InputIterator last)
      { for ( ; first != last; ++first ) push(*first); }

public:
  explicit stable_priority_queue(const Compare& pp = Compare(),
                                 const Container& cc = Container())
    : comp(pp) { push(cc.begin(), cc.end()); }

  template <class InputIterator>
    stable_priority_queue(InputIterator first, InputIterator last,
                          const Compare& pp = Compare())
    : comp(pp) { push(first,last); }
	///Containerのemptyと同じ
  bool              empty() const { return c.empty(); }
  ///Containerのsize
	size_type         size()  const { return c.size(); }
  ///Containerのback
	const value_type& top() const   { return c.back(); }
  ///Containerのpop_back
	void              pop()         { c.pop_back(); }
	//Containerにぶち込む
  void push(const value_type& x) {
    c.insert(std::lower_bound(c.begin(), c.end(), x, comp), x);
  }
	///Containerのclear()
	void clear(){
		c.clear();
	}
	
};


}//end of stx namespace

#endif
