// lib/prec_stl/deque

#pragma ifndef PREC_STL_DEQUE
#pragma define PREC_STL_DEQUE
#pragma link off global PREC_STL_DEQUE;
#pragma link C++ nestedtypedef;
#pragma link C++ nestedclass;
#if defined(G__HP_aCC) || defined(G__SUNPRO_C)
#pragma mask_newdelete 0x1c;
#else
#pragma mask_newdelete 0x10;
#endif

// Imported from ANSI/ISO C++ 1997/Nov draft 
// Got some ideas from Scott Snyder, Fermi-lab
// Modified by Masaharu Goto
// SGI KCC porting by Philippe Canal, Fermi-lab

#include <iterator>
#include <memory>

#if defined(G__ANSIISOLIB)
template<class T,class Allocator=allocator<T> >
#elif defined(G__GNUC) && !defined(G__KCC)
template<class T,class Allocator=alloc>
#elif defined(G__HPUX)
template<class T,class Allocator=allocator>
#else
template<class T,class Allocator=allocator<T> >
#endif
class deque {
 public:
  typedef T value_type;
  typedef Allocator                                 allocator_type;
#if (defined(G__GNUC) && !defined (G__KCC)) || defined(G__HPUX)
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
#else
  typedef typename Allocator::reference             reference;
  typedef typename Allocator::const_reference       const_reference;
  typedef typename Allocator::size_type             size_type;
  typedef typename Allocator::difference_type       difference_type;
  typedef typename Allocator::pointer               pointer;
  typedef typename Allocator::const_pointer         const_pointer;
#endif

  class iterator 
#if defined(G__VISUAL)
	: public _Ranit<T,difference_type>
#elif !defined(G__SUNPRO_C)
  	: public random_access_iterator<T,difference_type>
#endif
	{
   public:
    iterator() ;
    iterator(const iterator& x) ;
#if !defined(G__BORLAND) && !defined(G__KCC)
    iterator& operator=(const iterator& x) ;
#endif
    T& operator*() const ;
    iterator& operator++();
    iterator operator++(int a);
    iterator& operator--();
    iterator operator--(int a);
    bool operator==(const iterator& x) ;
#ifndef G__HPUX
    bool operator!=(const iterator& x) ;
#endif
    iterator operator+(long n);
    iterator operator-(long n);
    iterator& operator+=(long n);
    iterator& operator-=(long n);
    T& operator[](long n) ;
  };
#ifdef G__HPUX
  friend bool operator!=(const deque::iterator& x
                        ,const deque::iterator& y) const;
#endif

  class reverse_iterator 
#if defined(G__VISUAL)
	: public _Ranit<T,difference_type>
#elif !defined(G__SUNPRO_C)
	: public random_access_iterator<T,difference_type>
#endif
	{
   public:
    reverse_iterator(const reverse_iterator& x);
#if !defined(G__BORLAND) && !defined(G__KCC)
    reverse_iterator& operator=(const reverse_iterator& x) ;
#endif
#ifdef G__HPUX
    T& operator*() ;
#else
    T& operator*() const ;
#endif
    reverse_iterator& operator++();
    reverse_iterator operator++(int a);
    reverse_iterator& operator--();
    reverse_iterator operator--(int a);
    reverse_iterator operator+(long n);
    reverse_iterator operator-(long n);
    reverse_iterator& operator+=(long n);
    reverse_iterator& operator-=(long n);
    T& operator[](long n) ;
   private:
  };
  friend bool operator==(const deque::reverse_iterator& x
                        ,const deque::reverse_iterator& y) const;
  friend bool operator!=(const deque::reverse_iterator& x
                        ,const deque::reverse_iterator& y) const;

  typedef const iterator const_iterator;
  typedef const reverse_iterator const_reverse_iterator;

  deque();
  deque(size_type n, const T& value = T());
#if 0
  template <class InputIterator>
    deque(InputIterator first, InputIterator last,
         const Allocator& = Allocator());
#else
#if (defined(G__GNUC) && !defined (G__KCC))
  deque(const T* first,const T* last) ;
#endif
  deque(const_iterator first, const_iterator last);
#endif
  deque(const deque& x);
  ~deque();
  deque& operator=(const deque& x);
#if defined(G__KCC)
  template <class InputIterator>
   void assign(InputIterator first, InputIterator last);
#endif
#if !defined(G__GNUC) || defined(G__KCC)
  void assign(size_type n, const T& t);
#endif
  //allocator_type get_allocator() const;
  // iterators:
  iterator               begin();
  iterator               end();
  reverse_iterator       rbegin();
  reverse_iterator       rend();
#ifdef G__CONSTNESSFLAG
  const_iterator begin(void) const;
  const_iterator end(void) const;
  const_reverse_iterator rbegin(void) const;
  const_reverse_iterator rend(void) const;
#endif
  // _lib.deque.capacity_ capacity:
  size_type size() const;
  size_type max_size() const;
  void      resize(size_type sz, T c = T());
  bool      empty() const;

  // element access:
  T&       operator[](size_type n);
  //const_reference operator[](size_type n) const;
#if !defined(G__GNUC) || defined(G__KCC)
  T& at(size_type n);
#endif
  //const_reference at(size_type n) const;
  T& front();
  //const_reference front() const;
  T& back();
  //const_reference back() const;
  // _lib.deque.modifiers_ modifiers:
  void push_front(const T& x);
  void push_back(const T& x);
  iterator insert(iterator position, const T& x);
  void     insert(iterator position, size_type n, const T& x);
#if 0
  template <class InputIterator>
   void insert (iterator position,
                InputIterator first, InputIterator last);
#endif
  void pop_front();
  void pop_back();
  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);
  void     swap(deque<T,Allocator>&);
  void     clear();

  friend bool operator==(const deque& x, const deque& y);
  friend bool operator< (const deque& x, const deque& y);
  friend bool operator!=(const deque& x, const deque& y);
  friend bool operator> (const deque& x, const deque& y);
  friend bool operator>=(const deque& x, const deque& y);
  friend bool operator<=(const deque& x, const deque& y);
  // specialized algorithms:
#ifndef G__GNUC
  // doesn't work on egcs nor VC++5.0
  //friend void swap(deque& x, deque& y);
#endif

#ifndef G__NOALGORITHM
  // Generic algorithm
#if defined(G__GNUC) || defined(G__BORLAND) || defined (G__KCC)

  // input iter
  friend deque::iterator 
    find(deque::iterator first,deque::iterator last,const T& value);
  // forward iter
  friend deque::iterator 
    find_end(deque::iterator first1,deque::iterator last1,
	     deque::iterator first2,deque::iterator last2);
  friend deque::iterator 
    find_first_of(deque::iterator first1,deque::iterator last1,
	          deque::iterator first2,deque::iterator last2);
  friend deque::iterator 
    adjacent_find(deque::iterator first,deque::iterator last);
  // input iter
#if !defined(G__BORLAND)
  friend deque::difference_type
    count(deque::iterator first,deque::iterator last,const T& value);
#endif
#if 0
  friend pair<deque::iterator,deque::iterator>
    mismatch(deque::iterator first1,deque::iterator last1,
             deque::iterator first2);
#endif
  friend bool
    equal(deque::iterator first1,deque::iterator last1,
          deque::iterator first2);
  // forward iter
  friend deque::iterator
    search(deque::iterator first1,deque::iterator last1,
           deque::iterator first2,deque::iterator last2);
  friend deque::iterator
    search_n(deque::iterator first,deque::iterator last
             ,deque::size_type count,const T& value);
  // input and output iter -> forward iter
  friend deque::iterator
    copy(deque::iterator first,deque::iterator last,
         deque::iterator result);
  // bidirectional iter
  friend deque::iterator
    copy_backward(deque::iterator first,deque::iterator last,
                  deque::iterator result);
  // just value_type
  friend void swap(T& a,T& b);
  // forward iter
  friend deque::iterator
    swap_ranges(deque::iterator first1,deque::iterator last1,
                deque::iterator first2);
  friend void iter_swap(deque::iterator a,deque::iterator b);
  friend void replace(deque::iterator first,deque::iterator last,
                      const T& old_value,const T& new_value);
  // input, output iter -> forward iter
  friend deque::iterator 
    replace_copy(deque::iterator first,deque::iterator last,
                 deque::iterator result,
                 const T& old_value,const T& new_value);
  // forward iter
  friend void
    fill(deque::iterator first,deque::iterator last,const T& value);
#if (G__GNUC>=3) || defined(G__KCC)
  friend void
    fill_n(deque::iterator first,deque::size_type n,const T& value);
#endif
  friend deque::iterator
    remove(deque::iterator first,deque::iterator last,const T& value);
  // input,output iter -> forward iter
  friend deque::iterator
    remove_copy(deque::iterator first,deque::iterator last,
                deque::iterator result,const T& value);
  friend deque::iterator
    unique(deque::iterator first,deque::iterator last);
  friend deque::iterator 
    unique_copy(deque::iterator first,deque::iterator last,
                deque::iterator result);
  friend void reverse(deque::iterator first,deque::iterator last);
  friend deque::iterator
     reverse_copy(deque::iterator first,deque::iterator last,
                  deque::iterator result);
  // forward iter
  friend void rotate(deque::iterator first,deque::iterator mid,
                     deque::iterator last);
  // forward iter
  friend deque::iterator 
    rotate_copy(deque::iterator first,deque::iterator mid,
                deque::iterator last,deque::iterator result);
  // randomaccess iter
  friend void random_shuffle(deque::iterator first,deque::iterator last);
  // randomaccess iter
  friend void sort(deque::iterator first,deque::iterator last);
  friend void stable_sort(deque::iterator first,deque::iterator last);
  friend void partial_sort(deque::iterator first,deque::iterator mid,
                           deque::iterator last);
  friend deque::iterator
    partial_sort_copy(deque::iterator first,deque::iterator last,
                      deque::iterator result_first,
                      deque::iterator result_last);
  friend void nth_element(deque::iterator first,deque::iterator nth,
                          deque::iterator last);
  // forward iter
  friend deque::iterator 
    lower_bound(deque::iterator first,deque::iterator last,const T& value);
  friend deque::iterator 
    upper_bound(deque::iterator first,deque::iterator last,const T& value);
#if 0
  friend pair<deque::iterator,deque::iterator>
    equal_range(deque::iterator first,deque::iterator last,const T& value);
#endif
  friend bool binary_search(deque::iterator first,deque::iterator last,
                            const T& value);
  friend deque::iterator merge(deque::iterator first1,deque::iterator last1,
                                deque::iterator first2,deque::iterator last2,
                                deque::iterator result);
  friend void inplace_merge(deque::iterator first,deque::iterator middle,
                            deque::iterator last);
  friend bool includes(deque::iterator first1,deque::iterator last1,
                       deque::iterator first2,deque::iterator last2);
  friend deque::iterator 
    set_union(deque::iterator first1,deque::iterator last1,
              deque::iterator first2,deque::iterator last2,
              deque::iterator result);
  friend deque::iterator 
    set_intersection(deque::iterator first1,deque::iterator last1,
                     deque::iterator first2,deque::iterator last2,
                     deque::iterator result);
  friend deque::iterator 
    set_difference(deque::iterator first1,deque::iterator last1,
                   deque::iterator first2,deque::iterator last2,
                   deque::iterator result);
  friend deque::iterator 
    set_symmetric_difference(deque::iterator first1,deque::iterator last1,
                             deque::iterator first2,deque::iterator last2,
                             deque::iterator result);
  // random access
  friend void push_heap(deque::iterator first,deque::iterator last);
  friend void pop_heap(deque::iterator first,deque::iterator last);
  friend void make_heap(deque::iterator first,deque::iterator last);
  friend void sort_heap(deque::iterator first,deque::iterator last);
  // min,max, just value_type
  friend const T& min(const T& a,const T& b);
  friend const T& max(const T& a,const T& b);
  // forward iter
  friend deque::iterator 
    min_element(deque::iterator first,deque::iterator last);
  friend deque::iterator 
    max_element(deque::iterator first,deque::iterator last);
  // input iter
  friend bool
    lexicographical_compare(deque::iterator first1,deque::iterator last1,
                            deque::iterator first2,deque::iterator last2);
  // bidirectional iter
  friend bool next_permutation(deque::iterator first,deque::iterator last);
  friend bool prev_permutation(deque::iterator first,deque::iterator last);

#elif defined(G__VISUAL)

  friend void reverse(deque::iterator first,deque::iterator last);
  friend void sort(deque::iterator first,deque::iterator last);

  friend deque::iterator 
    find(deque::iterator first,deque::iterator last,const T& value);
  friend deque::iterator
    search(deque::iterator first1,deque::iterator last1,
           deque::iterator first2,deque::iterator last2);
  friend deque::iterator
    copy(deque::iterator first,deque::iterator last,
         deque::iterator result);
  friend void
    fill(deque::iterator first,deque::iterator last,const T& value);
#if 0
  friend deque::iterator
    remove(deque::iterator first,deque::iterator last,const T& value);
  friend deque::iterator
    unique(deque::iterator first,deque::iterator last);
#endif

#endif // G__GNUC || G__BORLAND

#endif // G__NOALGORITHM

  // Generic algorithm
  //friend void reverse(deque::iterator first,deque::iterator last);
  //friend void reverse(deque::reverse_iterator first,deque::reverse_itetator last);

  // iterator_category resolution
  //friend random_access_iterator_tag iterator_category(deque::iterator x);
};

#pragma endif