// File:       list.c++
// Version:    1.01
// Author:     (c) Miles Sabin, 1996
// Purpose:    approximation to ANSI C++ list template

// Change log:
//  28/12/96   v. 1.00
//   2/01/97   Added unique(), merge() and sort() comparator fn variants.
//  13/01/97   v. 1.01
//             Factored out non-generic code into list_base.
//             Added remove_if().
//  16/01/97   Hoist helper is now a local static to avoid static init
//               problems.
//  23/01/97   Hoist helper is now a singleton.
//  23/02/97   Adapted to HoistHelper/HoistComparator split.
//  31/03/97   Added list(size_t) constructor.
//  04/04/97   Replaced HoistComparators with HoistBinaryPredicate and HoistUnaryPredicates.

#include "list.h"

#include "functional.h"
#include "hoistbp.h"
#include "hoistctdt.h"
#include "hoistup.h"
#include "tpltutil.h"


// Implementation of list<T>

#define reference              T&
#define const_reference        T const&
#define iterator               list_iterator<T>
#define const_iterator         list_const_iterator<T>
#define rev_iterator           reverse_bidirectional_iterator<list_iterator<T>, T, reference>
#define const_rev_iterator     reverse_bidirectional_iterator<list_const_iterator<T>, T, const_reference>
#define size_type              size_t
#define difference_type        ptrdiff_t
#define value_type             T

#ifndef INSTANTIATE_LIST_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_IF_ONLY
#ifndef INSTANTIATE_LIST_EXTERNAL_COMPARATORS_ONLY

template<class T>
list<T>::list()
  : list_base(get_hoist_constructor_destructor((T*)0))
  {}

#ifndef INSTANTIATE_LIST_NO_DEFAULT_CTOR

template<class T>
list<T>::list(size_type n)
  : list_base(get_hoist_constructor_destructor((T*)0))
  {
    T value;
    list_base::assign(n, &value);
  }

#endif

template<class T>
list<T>::list(size_type n, T const& value)
  : list_base(get_hoist_constructor_destructor((T*)0), n, &value)
  {}

template<class T>
list<T>::list(iterator const& first, iterator const& last)
  : list_base(get_hoist_constructor_destructor((T*)0), first.node_, last.node_)
  {}

template<class T>
list<T>::list(T const* first, T const* last)
  : list_base(get_hoist_constructor_destructor((T*)0), first, last)
  {}

template<class T>
list<T>::list(list<T> const& rhs)
  : list_base(rhs)
  {}

template<class T>
list<T>::~list()
  {}

template<class T>
const_iterator list<T>::begin() const
  { return const_iterator(list_base::begin()); }

template<class T>
const_iterator list<T>::end() const
  { return const_iterator(list_base::end()); }

template<class T>
const_rev_iterator list<T>::rbegin() const
  { return const_rev_iterator(end()); }

template<class T>
const_rev_iterator list<T>::rend() const
  { return const_rev_iterator(begin()); }

template<class T>
const_reference list<T>::front() const
  { return *reinterpret_cast(T*, list_base::front()); }

template<class T>
const_reference list<T>::back() const
  { return *reinterpret_cast(T*, list_base::back()); }

template<class T>
bool list<T>::empty() const
  { return list_base::empty(); }

template<class T>
size_type list<T>::size() const
  { return list_base::size(); }

template<class T>
size_type list<T>::max_size() const
  { return list_base::max_size(); }

template<class T>
list<T>& list<T>::operator=(list<T> const& rhs)
  {
    list_base::operator=(rhs);
    return *this;
  }

template<class T>
void list<T>::assign(iterator const& first, iterator const& last)
  { list_base::assign(first.node_, last.node_); }

template<class T>
void list<T>::assign(T const* first, T const* last)
  { list_base::assign(first, last); }

template<class T>
void list<T>::assign(size_type n, T const& t)
  { list_base::assign(n, &t); }

template<class T>
iterator list<T>::begin()
  { return iterator(list_base::begin()); }

template<class T>
iterator list<T>::end()
  { return iterator(list_base::end()); }

template<class T>
rev_iterator list<T>::rbegin()
  { return rev_iterator(end()); }

template<class T>
rev_iterator list<T>::rend()
  { return rev_iterator(begin()); }

template<class T>
reference list<T>::front()
  { return *reinterpret_cast(T*, list_base::front()); }

template<class T>
reference list<T>::back()
  { return *reinterpret_cast(T*, list_base::back()); }

template<class T>
void list<T>::push_front(T const& x)
  { list_base::push_front(&x); }

template<class T>
void list<T>::push_back(T const& x)
  { list_base::push_back(&x); }

template<class T>
void list<T>::pop_front()
  { list_base::pop_front(); }

template<class T>
void list<T>::pop_back()
  { list_base::pop_back(); }

template<class T>
iterator list<T>::insert(iterator const& position, T const& x)
  { return iterator(list_base::insert(position.node_, &x)); }

template<class T>
void list<T>::insert(iterator const& position, size_type n, T const& x)
  { list_base::insert(position.node_, n, &x); }

template<class T>
void list<T>::insert(iterator const& position, iterator const& first, iterator const& last)
  { list_base::insert(position.node_, first.node_, last.node_); }

template<class T>
void list<T>::insert(iterator const& position, T const* first, T const* last)
  { list_base::insert(position.node_, first, last); }

template<class T>
void list<T>::erase(iterator const& position)
  { list_base::erase(position.node_); }

template<class T>
void list<T>::erase(iterator const& first, iterator const& last)
  { list_base::erase(first.node_, last.node_); }

template<class T>
void list<T>::swap(list<T>& x)
  { list_base::swap(x); }

template<class T>
void list<T>::clear()
  { list_base::clear(); }

template<class T>
void list<T>::splice(iterator const& position, list<T>& x)
  { list_base::splice(position.node_, x); }

template<class T>
void list<T>::splice(iterator const& position, list<T>& x, iterator const& i)
  { list_base::splice(position.node_, x, i.node_); }

template<class T>
void list<T>::splice(iterator const& position, list<T>& x, iterator const& first, iterator const& last)
  { list_base::splice(position.node_, x, first.node_, last.node_); }

template<class T>
void list<T>::reverse()
  { list_base::reverse(); }

template<class T>
void list<T>::resize(size_type sz, T const& c)
  { list_base::resize(sz, &c); }

#endif
#endif
#endif
#endif

#ifndef INSTANTIATE_LIST_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_IF_ONLY
#ifndef INSTANTIATE_LIST_EXTERNAL_COMPARATORS_ONLY

// using equal_to<> and binder1st<> would be nicer, but
// triggers long names problems with even relatively short
// class names.

template<class T>
struct equal_to_value
{
  public:

    equal_to_value(const T& value)
      : value_(value)
      {}

    bool operator()(const T& value) const
      { return value == value_; }

  private:

    T const& value_;
};

template<class T>
void list<T>::remove(T const& value)
  { list_base::remove_if(make_hoist_unary_predicate(equal_to_value<T>(value), (T*)0)); }

#endif
#endif
#endif
#endif

#ifndef INSTANTIATE_LIST_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_ONLY
#ifndef INSTANTIATE_LIST_EXTERNAL_COMPARATORS_ONLY

template<class T>
void list<T>::remove_if(bool (*pred)(T const&))
  { list_base::remove_if(make_hoist_unary_predicate(pred, (T*)0)); }

#endif
#endif
#endif
#endif

#ifndef INSTANTIATE_LIST_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_IF_ONLY

template<class T>
void list<T>::unique(bool (*pred)(T const&, T const&))
  { list_base::unique(make_hoist_binary_predicate(pred, (T*)0)); }

template<class T>
void list<T>::merge(list<T>& x, bool (*comp)(T const&, T const&))
  { list_base::merge(x, make_hoist_binary_predicate(comp, (T*)0)); }

template<class T>
void list<T>::sort(bool (*comp)(T const&, T const&))
  { list_base::sort(make_hoist_binary_predicate(comp, (T*)0)); }

#endif
#endif
#endif
#endif

#ifndef INSTANTIATE_LIST_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_IF_ONLY
#ifndef INSTANTIATE_LIST_EXTERNAL_COMPARATORS_ONLY

template<class T>
void list<T>::unique()
  { list_base::unique(get_hoist_equal_to_comparator((T*)0)); }

template<class T>
void list<T>::merge(list<T>& x)
  { list_base::merge(x, get_hoist_less_comparator((T*)0)); }

template<class T>
void list<T>::sort()
  { list_base::sort(get_hoist_less_comparator((T*)0)); }

#endif
#endif
#endif
#endif

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


// Implementation of list<T> free fns


#ifndef INSTANTIATE_LIST_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_ONLY
#ifndef INSTANTIATE_LIST_REMOVE_IF_ONLY
#ifndef INSTANTIATE_LIST_EXTERNAL_COMPARATORS_ONLY

template<class T>
bool operator==(list<T> const& lhs, list<T> const& rhs)
{
  return REF_reinterpret_cast(list_base, lhs).is_equal(get_hoist_equal_to_comparator((T*)0), REF_reinterpret_cast(list_base, rhs));
}

template<class T>
bool operator< (list<T> const& lhs, list<T> const& rhs)
{
  return REF_reinterpret_cast(list_base, lhs).is_less_than(get_hoist_less_comparator((T*)0), REF_reinterpret_cast(list_base, rhs));
}

#endif
#endif
#endif
#endif
