#ifndef cathlibcpp_deque_H
#define cathlibcpp_deque_H

// File:       deque.h
// Author:     (c) Miles Sabin, 1996
// Purpose:    approximation to ANSI C++ deque template


#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_dequebase_H
#include "dequebase.h"
#endif

#ifndef cathlibcpp_iterator_H
#include "iterator.h"
#endif

#ifndef cathlibcpp_utility_H
#include "utility.h"
#endif


template<class T>
class deque : public deque_base
{
  public:

#   define reference             T&
#   define const_reference       T const&
#   define iterator              T*
#   define const_iterator        T const*
#   define size_type             size_t
#   define difference_type       ptrdiff_t
#   define value_type            T
#   define rev_iterator          reverse_iterator<iterator, value_type, reference>
#   define const_rev_iterator    reverse_iterator<const_iterator, value_type, const_reference>

    // constructors
    deque();
    deque(size_type n);
    deque(size_type n, T const& value);
    deque(T const* first, T const* last);
    deque(deque<T> const& rhs);
    ~deque();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    const_rev_iterator rbegin() const;
    const_rev_iterator rend() const;

    size_type size() const;
    size_type max_size() const;
    size_type capacity() const;

    bool empty() const;

    const_reference operator[](size_type n) const;
    const_reference at(size_type n) const;

    const_reference front() const;
    const_reference back() const;

    // mutators
    deque<T>& operator=(deque<T> const& rhs);
    void assign(T const* first, T const* last);
    void assign(size_type n, T const& t);

    iterator begin();
    iterator end();

    rev_iterator rbegin();
    rev_iterator rend();

    void resize(size_type sz, T const& c);

    reference operator[](size_type n);
    reference at(size_type n);

    reference front();
    reference back();

    void push_front(T const& x);
    void pop_front();

    void push_back(T const& x);
    void pop_back();

    iterator insert(iterator position, T const& x);
    void insert(iterator position, size_type n, T const& x);
    void insert(iterator position, T const* first, T const* last);

    void erase(iterator position);
    void erase(iterator first, iterator last);

    void swap(deque<T>& x);

    void clear();

#   undef reference
#   undef const_reference
#   undef iterator
#   undef const_iterator
#   undef size_type
#   undef difference_type
#   undef value_type
#   undef rev_iterator
#   undef const_rev_iterator
};

template<class T>
bool operator==(deque<T> const& lhs, deque<T> const& rhs);

template<class T>
bool operator<(deque<T> const& lhs, deque<T> const& rhs);

#endif
