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

// Change log:
//  13/12/96   v. 1.00
//             Built from list<T> 1.00.
//             Added special case for sort().
//             Added special case for reverse().
//             Added remove_if().
//  21/01/97   Bug fix: swap() was broken.
//  22/01/97   Bug fix: forgot self-assignment check in operator=().
//             Control node now allocated from heap.
//             Factored unique(), merge() and sort() variants.
//  23/02/97   Adapted to HoistHelper/HoistComparator split.
//  04/04/97   Replaced HoistComparators with HoistBinaryPredicate and HoistUnaryPredicates.
//             Swapped order of merge() arguments.

#include "listbase.h"

#include "algorithm.h"
#include "hoistalgo.h"
#include "hoistbpp.h"
#include "hoistctdtp.h"
#include "hoistupp.h"
#include "new.h"
#include "newcasts.h"


// Implementation of list_base

#define size_type              size_t
#define difference_type        ptrdiff_t

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

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

list_base::list_base(HoistConstructorDestructorProtocol const& hoist_ctdt, list_base_node const* first, list_base_node const* last)
  : hoist_ctdt_(hoist_ctdt)
  {
    init();
    insert(begin(), first, last);
  }

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

list_base::list_base(list_base const& rhs)
  : hoist_ctdt_(rhs.hoist_ctdt_)
  {
    init();
    insert(begin(), rhs.begin(), rhs.end());
  }

list_base::~list_base()
  {
    clear();
    delete control_node_;
  }

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

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

    assign(rhs.begin(), rhs.end());
    return *this;
  }

void list_base::assign(list_base_node const* first, list_base_node const* last)
  {
    clear();
    insert(begin(), first, last);
  }

void list_base::assign(void const* first, void const* last)
  {
    clear();
    insert(begin(), first, last);
  }

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

void list_base::push_front(void const* x)
  { insert(begin(), x); }

void list_base::push_back(void const* x)
  { insert(end(), x); }

void list_base::pop_front()
  { erase(begin()); }

void list_base::pop_back()
  { erase(end()->prev_); }

list_base_node* list_base::insert(list_base_node* position, void const* x)
  {
    list_base_node* prev = position->prev_;

    list_base_node* new_node = reinterpret_cast(list_base_node*, ::operator new(sizeof(list_base_node)+hoist_ctdt_.size()));
    new(new_node) list_base_node(prev, position);
    hoist_ctdt_.construct(new_node+1, x);

    prev->next_ = new_node;
    position->prev_ = new_node;

    ++size_;

    return new_node;
  }

void list_base::insert(list_base_node* position, size_type n, void const* x)
  {
    while(n-- > 0)
      insert(position, x);
  }

void list_base::insert(list_base_node* position, list_base_node const* first, list_base_node const* last)
  {
    while(first != last)
    {
      insert(position, first+1);
      first = first->next_;
    }
  }

void list_base::insert(list_base_node* position, void const* first, void const* last)
  {
    while(first != last)
    {
      insert(position, first);
      first += hoist_ctdt_.size();
    }
  }

void list_base::erase(list_base_node* position)
  {
    list_base_node* prev = position->prev_;
    list_base_node* next = position->next_;

    prev->next_ = next;
    next->prev_ = prev;

    --size_;

    hoist_ctdt_.destroy(position+1);

    ::operator delete(position);
  }

void list_base::erase(list_base_node* first, list_base_node* last)
  {
    while(first != last)
    {
      list_base_node* prev = first;
      first = first->next_;
      erase(prev);
    }
  }

void list_base::swap(list_base& x)
  {
    ::swap(control_node_, x.control_node_);
    ::swap(size_, x.size_);
  }

void list_base::clear()
  { erase(begin(), end()); }

void list_base::splice(list_base_node* position, list_base& x)
  {
    if(x.empty())
      return;

    transfer(position, x.begin(), x.end());
    size_ += x.size_;
    x.size_ = 0;
  }

void list_base::splice(list_base_node* position, list_base& x, list_base_node* i)
  {
    if(position == i || position == i->next_)
      return;

    transfer(position, i, i->next_);
    ++size_;
    --x.size_;
  }

void list_base::splice(list_base_node* position, list_base& x, list_base_node* first, list_base_node* last)
  {
    if(first == last)
      return;

    if(&x != this)
    {
      difference_type n = 1;
      for(list_base_node* i = first->next_; i != last; ++n, i = i->next_);

      x.size_ -= n;
      size_ += n;
    }

    transfer(position, first, last);
  }

void list_base::remove_if(HoistUnaryPredicateProtocol const& hoist_pred)
  {
    list_base_node* i = begin();

    while(i != end())
    {
      if(hoist_pred(i+1))
      {
        list_base_node* prev = i;
        i = i->next_;
        erase(prev);
      }
      else
        i = i->next_;
    }
  }

void list_base::unique(HoistBinaryPredicateProtocol const& hoist_pred)
  {
    if(size_ == 0)
      return;

    list_base_node* first = begin();
    list_base_node* last = end();

    list_base_node* next = first->next_;

    while(next != last)
    {
      if(!hoist_pred(first+1, next+1))
        first = next;
      else
      {
        erase(next);
        next = first;
      }
      next = next->next_;
    }
  }

void list_base::merge(list_base& x, HoistBinaryPredicateProtocol const& hoist_comp)
  {
    list_base_node* first1 = begin();
    list_base_node* last1 = end();
    list_base_node* first2 = x.begin();
    list_base_node* last2 = x.end();

    while(first1 != last1 && first2 != last2)
      if(!hoist_comp(first2+1, first1+1))
        first1 = first1->next_;
      else
      {
        list_base_node* next = first2->next_;
        transfer(first1, first2, next);
        first2 = next;
      }

    if(first2 != last2)
      transfer(last1, first2, last2);

    size_ += x.size_;
    x.size_ = 0;
  }

void list_base::sort(HoistBinaryPredicateProtocol const& hoist_comp)
  {
    // algorithm: merge sort

    if(size_ < 2)
      return;

    if(size_ == 2)
    {
      if(hoist_comp(control_node_->next_->next_+1, control_node_->next_+1))
        reverse();
      return;
    }

    list_base_node* split = begin();
    for(int i = size_; i > 0; i -= 2)
      split = split->next_;

    list_base partition(hoist_ctdt_);
    partition.splice(partition.begin(), *this, begin(), split);

    sort(hoist_comp);
    partition.sort(hoist_comp);

    merge(partition, hoist_comp);
  }

void list_base::reverse()
  {
    if(size_ < 2)
      return;

    if(size_ == 2)
    {
      ::swap(control_node_->prev_->prev_, control_node_->prev_->next_);
      ::swap(control_node_->next_->prev_, control_node_->next_->next_);
      ::swap(control_node_->prev_, control_node_->next_);
      return;
    }

    list_base_node* first = begin()->next_;

    while(first != end())
    {
      list_base_node* prev = first;
      first = first->next_;
      transfer(begin(), prev, first);
    }
  }

void list_base::resize(size_type sz, void const* c)
  {
    if(sz > size_)
      insert(end(), sz-size_, c);
    else if(sz < size_)
    {
      list_base_node* first = begin();
      while(sz-- > 0)
        first = first->next_;
      erase(first, end());
    }
  }

void list_base::init()
  {
    control_node_ = new list_base_node(0, 0);

    control_node_->prev_ = control_node_;
    control_node_->next_ = control_node_;
    size_ = 0;
  }

void list_base::transfer(list_base_node* position, list_base_node* first, list_base_node* last)
  {
    last = last->prev_;

    first->prev_->next_ = last->next_;
    last->next_->prev_ = first->prev_;

    first->prev_ = position->prev_;
    last->next_ = position;

    position->prev_->next_ = first;
    position->prev_ = last;
  }

bool list_base::is_equal(HoistBinaryPredicateProtocol const& hoist_comparator, list_base const& rhs) const
  {
    if(size() != rhs.size())
      return false;

    list_base_node const* first1 = begin();
    list_base_node const* last1 = end();
    list_base_node const* first2 = rhs.begin();

    while(first1 != last1 && hoist_comparator(first1+1, first2+1))
    {
      first1 = first1->next_;
      first2 = first2->next_;
    }

    return first1 == last1;
  }

bool list_base::is_less_than(HoistBinaryPredicateProtocol const& hoist_comparator, list_base const& rhs) const
  {
    list_base_node const* first1 = begin();
    list_base_node const* last1 = end();
    list_base_node const* first2 = rhs.begin();
    list_base_node const* last2 = rhs.end();

    while(first1 != last1 && first2 != last2)
    {
      if(hoist_comparator(first1+1, first2+1))
        return true;
      if(hoist_comparator(first2+1, first1+1))
        return false;
      first1 = first1->next_;
      first2 = first2->next_;
    }

    return first1 == last1 && first2 != last2;
  }

#undef size_type
#undef difference_type
