// File:       dequebase.c++
// Version:    1.00
// Author:     (c) Miles Sabin, 1997
// Purpose:    private implementation of deque<T> non-template hoist base class

// Change log:
//  14/01/97   v. 1.00
//             Built from deque<T> 1.00.
//  22/01/97   Bug fix: forgot self-assignment check in operator=().
//             Reimplemented clear().
//  23/02/97   Adapted to HoistHelper/HoistComparator split.
//  04/04/97   Replaced HoistComparators with HoistBinaryPredicates.

#include "dequebase.h"

#include "algorithm.h"
#include "hoistalgo.h"
#include "hoistbpp.h"
#include "hoistctdtp.h"
#include "memory.h"
#include "newcasts.h"


// Implementation of deque_base

#define size_type             size_t
#define difference_type       ptrdiff_t

deque_base::deque_base(HoistConstructorDestructorProtocol const& hoist_ctdt)
  : hoist_ctdt_(hoist_ctdt)
  { init(); }

deque_base::deque_base(HoistConstructorDestructorProtocol const& hoist_ctdt, size_type n, void const* value)
  : hoist_ctdt_(hoist_ctdt)
  {
    init();
    insert(begin_, n, value);
  }

deque_base::deque_base(HoistConstructorDestructorProtocol const& hoist_ctdt, void const* first, void const* last)
  : hoist_ctdt_(hoist_ctdt)
  {
    init();
    insert(begin_, first, last);
  }

deque_base::deque_base(deque_base const& rhs)
  : hoist_ctdt_(rhs.hoist_ctdt_)
  {
    init();
    insert(begin_, rhs.begin_, rhs.end_);
  }

deque_base::~deque_base()
  {
    HoistAlgorithm::destroy(hoist_ctdt_, begin_, end_);
    ::operator delete(begin_of_storage_);
  }

size_type deque_base::max_size() const
  { return 1<<24; }

deque_base& deque_base::operator=(deque_base const& rhs)
  {
    if(this == &rhs)
      return *this;

    clear();
    insert(begin_, rhs.begin_, rhs.end_);

    return *this;
  }

void deque_base::assign(void const* first, void const* last)
  {
    clear();
    insert(begin_, first, last);
  }

void deque_base::assign(size_type n, void const* t)
  {
    clear();
    insert(begin_, n, t);
  }

void deque_base::resize(size_type sz, void const* c)
  {
    int change = sz-size();

    if(change > 0)
      insert(end_, change, c);
    else if(change < 0)
      erase(begin_+(sz*elem_size_), end_);
  }

void deque_base::push_front(void const* x)
  { insert(begin_, x); }

void deque_base::pop_front()
  { erase(begin_); }

void deque_base::push_back(void const* x)
  { insert(end_, x); }

void deque_base::pop_back()
  { erase(end_-elem_size_); }

void* deque_base::insert(void* position, void const* x)
  {
    int offset = reinterpret_cast(char*, position)-begin_;
    insert(position, 1, x);
    return begin_+offset;
  }

void deque_base::insert(void* position, size_type n, void const* x)
  {
    if(n == 0)
      return;

    position = insert_aux(position, n);
    HoistAlgorithm::uninitialized_fill(hoist_ctdt_, position, n, x);
  }

void deque_base::insert(void* position, void const* first, void const* last)
  {
    if(first == last)
      return;

    position = insert_aux(position, (reinterpret_cast(char*, last)-reinterpret_cast(char*, first))/elem_size_);
    HoistAlgorithm::uninitialized_copy(hoist_ctdt_, first, last, position);
  }

void deque_base::erase(void* position)
  { erase(position, reinterpret_cast(char*, position)+elem_size_); }

void deque_base::erase(void* first, void* last)
  {
    if(first == last)
      return;

    int erase_size = (reinterpret_cast(char*, last)-reinterpret_cast(char*, first))/elem_size_;
    int new_size = size()-erase_size;

    if(reinterpret_cast(char*, first)-begin_ < end_-reinterpret_cast(char*, last))
    {
      HoistAlgorithm::copy_backward(hoist_ctdt_, begin_, first, last);
      HoistAlgorithm::destroy(hoist_ctdt_, begin_, begin_+(erase_size*elem_size_));
      begin_ = end_-(new_size*elem_size_);
    }
    else
    {
      HoistAlgorithm::copy(hoist_ctdt_, last, end_, first);
      HoistAlgorithm::destroy(hoist_ctdt_, end_-(erase_size*elem_size_), end_);
      end_ = begin_+(new_size*elem_size_);
    }

    size_ -= erase_size;
  }

void deque_base::swap(deque_base& x)
  {
    ::swap(begin_, x.begin_);
    ::swap(end_, x.end_);
    ::swap(begin_of_storage_, x.begin_of_storage_);
    ::swap(end_of_storage_, x.end_of_storage_);
    ::swap(size_, x.size_);
  }

void deque_base::clear()
  {
    HoistAlgorithm::destroy(hoist_ctdt_, begin_, end_);
    begin_ = begin_of_storage_+((capacity()*elem_size_)/2);
    end_ = begin_;
    size_ = 0;
  }

void deque_base::init()
  {
    begin_ = 0;
    end_ = 0;
    begin_of_storage_ = 0;
    end_of_storage_ = 0;
    size_ = 0;
    elem_size_ = hoist_ctdt_.size();
  }

void deque_base::move(void* first, void* last, void* result)
  {
    size_type n = reinterpret_cast(char*, last)-reinterpret_cast(char*, first);
    int non_overlap = reinterpret_cast(char*, first)-reinterpret_cast(char*, result);

    if(non_overlap >= n)
    {
      HoistAlgorithm::uninitialized_copy(hoist_ctdt_, first, last, result);
      HoistAlgorithm::destroy(hoist_ctdt_, first, last);
    }
    else
    {
      HoistAlgorithm::uninitialized_copy(hoist_ctdt_, first, reinterpret_cast(char*, first)+non_overlap, result);
      HoistAlgorithm::copy(hoist_ctdt_, reinterpret_cast(char*, first)+non_overlap, last, first);
      HoistAlgorithm::destroy(hoist_ctdt_, reinterpret_cast(char*, last)-non_overlap, last);
    }
  }

void deque_base::move_backward(void* first, void* last, void* result)
  {
    size_type n = reinterpret_cast(char*, last)-reinterpret_cast(char*, first);
    int non_overlap = reinterpret_cast(char*, result)-reinterpret_cast(char*, last);

    if(non_overlap >= n)
    {
      HoistAlgorithm::uninitialized_copy(hoist_ctdt_, first, last, reinterpret_cast(char*, result)-n);
      HoistAlgorithm::destroy(hoist_ctdt_, first, last);
    }
    else
    {
      HoistAlgorithm::uninitialized_copy(hoist_ctdt_, reinterpret_cast(char*, last)-non_overlap, last, reinterpret_cast(char*, result)-non_overlap);
      HoistAlgorithm::copy_backward(hoist_ctdt_, first, reinterpret_cast(char*, last)-non_overlap, last);
      HoistAlgorithm::destroy(hoist_ctdt_, first, reinterpret_cast(char*, first)+non_overlap);
    }
  }

void deque_base::resize_and_insert(void* position, size_type n)
  {
    size_type new_size = size()+n;

    if(new_size <= capacity())
    {
      // make space within existing storage

      char* first1 = begin_of_storage_+(((capacity()-new_size)/2)*elem_size_);
      char* last1 = first1+(reinterpret_cast(char*, position)-begin_);
      char* first2 = last1+(n*elem_size_);
      char* last2 = first2+(end_-reinterpret_cast(char*, position));

      if(first1 <= begin_)
      {
        if(first1 != begin_)
          move(begin_, position, first1);

        if(last2 > end_)
          move_backward(position, end_, last2);
        else if(last2 < end_)
          move(position, end_, first2);
      }
      else
      {
        move_backward(position, end_, last2);
        move_backward(begin_, position, last1);
      }

      begin_ = first1;
      end_ = last2;
    }
    else
    {
      // reallocate

      size_type new_capacity = capacity()*2;
      if(new_capacity < new_size)
        new_capacity = new_size;

      char* new_begin_of_storage = reinterpret_cast(char*, ::operator new(new_capacity*elem_size_));
      char* new_begin = new_begin_of_storage+(((new_capacity-new_size)/2)*elem_size_);

      HoistAlgorithm::uninitialized_copy(hoist_ctdt_, begin_, position, new_begin);
      HoistAlgorithm::uninitialized_copy(hoist_ctdt_, position, end_, new_begin+(reinterpret_cast(char*, position)-begin_)+(n*elem_size_));

      HoistAlgorithm::destroy(hoist_ctdt_, begin_, end_);
      ::operator delete(begin_of_storage_);

      begin_ = new_begin;
      end_ = new_begin+(new_size*elem_size_);
      begin_of_storage_ = new_begin_of_storage;
      end_of_storage_ = begin_of_storage_+(new_capacity*elem_size_);
    }
  }

void* deque_base::insert_aux(void* position, size_type n)
  {
    int offset = reinterpret_cast(char*, position)-begin_;

    if(offset < end_-reinterpret_cast(char*, position))
    {
      if(begin_-(n*elem_size_) >= begin_of_storage_)
      {
        if(reinterpret_cast(char*, position) != begin_)
          move(begin_, position, begin_-(n*elem_size_));
        begin_ -= (n*elem_size_);
      }
      else
        resize_and_insert(position, n);
    }
    else
    {
      if(end_+(n*elem_size_) <= end_of_storage_)
      {
        if(reinterpret_cast(char*, position) != end_)
          move_backward(position, end_, end_+(n*elem_size_));
        end_ += (n*elem_size_);
      }
      else
        resize_and_insert(position, n);
    }

    size_ += n;

    return begin_+offset;
  }

bool deque_base::is_equal(HoistBinaryPredicateProtocol const& hoist_comparator, deque_base const& rhs) const
  {
    return size() == rhs.size() && HoistAlgorithm::equal(hoist_ctdt_, hoist_comparator, begin_, end_, rhs.begin_);
  }

bool deque_base::is_less_than(HoistBinaryPredicateProtocol const& hoist_comparator, deque_base const& rhs) const
  {
    return HoistAlgorithm::lexicographical_compare(hoist_ctdt_, hoist_comparator, begin_, end_, rhs.begin_, rhs.end_);
  }

#undef size_type
#undef difference_type
