#ifndef cathlibcpp_dequebase_H
#define cathlibcpp_dequebase_H

// File:       dequebase.h
// Author:     (c) Miles Sabin, 1997
// Purpose:    private header for deque<T> non-template hoist base class


#ifndef included_stddef_H
#define included_stddef_H
#include <stddef.h>              // for ptrdiff_t, size_t
#endif

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

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

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


class HoistBinaryPredicateProtocol;
class HoistConstructorDestructorProtocol;


class deque_base
{
  friend bool operator==(deque_base const& lhs, deque_base const& rhs);
  friend bool operator< (deque_base const& lhs, deque_base const& rhs);

  public:

#   define size_type             size_t
#   define difference_type       ptrdiff_t

    // constructors
    deque_base(HoistConstructorDestructorProtocol const& hoist_ctdt);
    deque_base(HoistConstructorDestructorProtocol const& hoist_ctdt, size_type n, void const* value);
    deque_base(HoistConstructorDestructorProtocol const& hoist_ctdt, void const* first, void const* last);
    deque_base(deque_base const& rhs);
    ~deque_base();

    // accessors
    void const* begin() const
      { return begin_; }
    void const* end() const
      { return end_; }

    size_type size() const
      { return size_; }
    size_type max_size() const;
    size_type capacity() const
      { return (end_of_storage_-begin_of_storage_)/elem_size_; }

    bool empty() const
      { return begin_ == end_; }

    void const* operator[](size_type n) const
      { return begin_+(n*elem_size_); }
    void const* at(size_type n) const
      { return begin_+(n*elem_size_); }

    void const* front() const
      { return begin_; }
    void const* back() const
      { return end_-elem_size_; }

    // mutators
    deque_base& operator=(deque_base const& rhs);
    void assign(void const* first, void const* last);
    void assign(size_type n, void const* t);

    void* begin()
      { return begin_; }
    void* end()
      { return end_; }

    void resize(size_type sz, void const* c);

    void* operator[](size_type n)
      { return begin_+(n*elem_size_); }
    void* at(size_type n)
      { return begin_+(n*elem_size_); }

    void* front()
      { return begin_; }
    void* back()
      { return end_-elem_size_; }

    void push_front(void const* x);
    void pop_front();

    void push_back(void const* x);
    void pop_back();

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

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

    void swap(deque_base& x);

    void clear();

    bool is_equal(HoistBinaryPredicateProtocol const& hoist_comparator, deque_base const& rhs) const;
    bool is_less_than(HoistBinaryPredicateProtocol const& hoist_comparator, deque_base const& rhs) const;

  private:

    void init();

    void move(void* first, void* last, void* result);
    void move_backward(void* first, void* last, void* result);
    void resize_and_insert(void* position, size_type n);
    void* insert_aux(void* position, size_type n);

    char* begin_;
    char* end_;
    char* begin_of_storage_;
    char* end_of_storage_;
    size_type size_;
    HoistConstructorDestructorProtocol const& hoist_ctdt_;
    size_type elem_size_;

#   undef size_type
#   undef difference_type
};

#endif
