

/*!
  @author d金魚
  @since 2003/8/21
	@note
	licence:BSD Licence
*/


#ifndef _dkutil_stack_or_queue
#define _dkutil_stack_or_queue


#include "../s34/list_sort.h"

namespace dkutil{

///d金魚って馬鹿なＷｒａｐｐｅｒばっかりつくるなぁ
/*!
<b>stack_or_queueの有用性：</b><br>
<ul>
	<li>iteratorが使える。(爆）
	<li>ぶっちゃけ　push と pop　で　各機能をラップしただけ･･･
</ul>
*/
///std::stackかもしれないしstd::queueかもしれないクラス
template<class T ,class CONTAINER=std::deque<T> >
class stack_or_queue : public CONTAINER
{
public:
	typedef CONTAINER CONTAINER_TYPE;
	typedef CONTAINER BASE_TYPE;
	enum{
		enuSTACK = false,
		enuQUEUE = true,
	};
	stack_or_queue(bool flag=enuSTACK){m_flag=flag;}
	/// データの追加
	void push(const T& x){	
		BASE_TYPE::push_back(x);
	}
	/// データの削除
	void pop()
	{
		if(m_flag==enuSTACK){
			BASE_TYPE::pop_back();
		}else{
			BASE_TYPE::pop_front();
		}
	}
	void set_type(bool flag){
		m_flag=flag;
	}

	T &top(){ return BASE_TYPE::back(); }
	const T &top()const{return BASE_TYPE::back();}

#ifndef BOOST_NO_PRIVATE_IN_AGGREGATE //なぜか boost 対応･･･
protected:
#endif
	bool m_flag;
};


template <class T, class Container = std::list<T>,
          class Compare = std::less<Container::value_type> >
class stable_priority_queue_ex : public Container {
public:
  typedef Container::value_type value_type;
  typedef Container::size_type  size_type;
  typedef Container             container_type;
	typedef Container							base_type;
	typedef stable_priority_queue_ex<T,Container,Compare> self_type;

	typedef base_type::iterator iterator;
	typedef base_type::const_iterator const_iterator;
	typedef base_type::reverse_iterator reverse_iterator;
	typedef base_type::const_reverse_iterator const_reverse_iterator;
	typedef base_type::reference reference;
	typedef base_type::const_reference const_reference;
protected:
  Compare comp;

private:
  template<class InputIterator>
    void push(InputIterator first, InputIterator last)
      { for ( ; first != last; ++first ) push(*first); }
	void push_back(){}
	void pop_back(){}
	void push_front(){}
	void pop_front(){}
	reference       front(){};
	const_reference front() const{};


	reference       back(){};
	const_reference back() const{}

	template <class InputIterator>
		void assign(InputIterator first, InputIterator last);
	void assign(size_type n, const T& t){}

	void splice(iterator position, base_type &x){}
	
	void splice(iterator position, base_type& x, iterator i){}
	
	void splice(iterator position, base_type& x,
		iterator first, iterator last){}

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

  template <class InputIterator>
    stable_priority_queue_ex(InputIterator first, InputIterator last,
                          const Compare& pp = Compare())
    : comp(pp) { push(first,last); }

  ///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) {
		base_type::insert(std::lower_bound(begin(), end(), x, comp), x);
  }
	///pushのWrapper
	void insert(const value_type& x){
		push(x);
	}
	///探す
	iterator find(const value_type &x){
		return std::find(begin(),end(),x);
	}
	///探す（const版
	const_iterator find(const value_type& x)const{
		return std::find(begin(),end(),x);
	}
	///削除する。
	bool erase(const value_type& x){
		iterator it = find(x);
		if(end()==it) return false;
		base_type::erase(it);	
		return true;
	}
	/*/Containerのclear()
	void clear(){
		clear();
	}*/
	///swapする。
	void swap(self_type &x){
		std::swap(*this,x);
	}
	template<class Compare__>
	void sort(Compare__ &x){
		stx::comb_sort(begin(),end(),x);
	}
	/*
	iterator begin(){return base_type::begin();}
	const_iterator begin()const{return base_type::begin();}
	reverse_iterator rbegin(){return base_type::rbegin();}
	const_reverse_iterator rbegin()const{return baes_type::rbegin();}
	*/
	/*
	///Containerのemptyと同じ
  bool              empty() const { return c.empty(); }
  ///Containerのsize
	size_type         size()  const { return c.size(); }
	*/
};

}//end of dkutil namepsace

#endif //end of include once