// **********************************************************************
//
// Copyright (c) 2002
// IONA Technologies, Inc.
// Waltham, MA, USA
//
// All Rights Reserved
//
// **********************************************************************

//
// Implementation of core std::list functionality.
// This will be extended to provide the missing std::list methods and
// template parameters as the need arises.
// The primary goal is to move away from using arbitrary propriety
// list/sequence interfaces, to ease the eventual transition to the STL.
//

#ifndef OB_LIST_H
#define OB_LIST_H

#include <OB/STLConfig.h>

#include <OB/allocator.h>
#include <OB/algorithms.h>
#include <OB/iterator.h>
#include <assert.h>


namespace OB
{


namespace stl
{


template<class T> class list;


//
// A template for implementing bidirectional iterators.
// Used to create both const and non-const iterators over a list.
//
// Ref is a reference to T
// NodePtr is a pointer to a list node
// ListPtr is a pointer to list<T>
// 
template<class T, class Ref, class NodePtr, class ListPtr>
class iterator_template
{
    ListPtr list_;
    NodePtr current_node_;
    
    friend class list<T>;
    
    //
    // Create an iterator over the given list, starting at
    // the node specified by position
    //
    iterator_template(ListPtr list, NodePtr position) :
        list_(list), current_node_(position)
    {
    }
    
public:
    typedef T value_type;
    
    //
    // Default constructor.
    // After construction it cannot be used as it points nowhere,
    // except to be assigned the value of another iterator.
    //
    iterator_template() : list_(0), current_node_(0)
    {
    }

    //
    // Create an iterator that points to the same list location
    // as another iterator
    //
    iterator_template(const iterator_template& other_iterator) :
        list_(other_iterator.list_),
        current_node_(other_iterator.current_node_)
    {
    }

    //
    // Destructor
    //
    ~iterator_template()
    {
    }

    //
    // Equality operator.
    // Determine if this iterator is pointing at the same list location
    // as another iterator.
    //
    bool operator==(const iterator_template& other_iterator) const
    {
        return other_iterator.current_node_ == current_node_;
    }

    //
    // Inequality operator.
    // Determine if this iterator is not pointing at the same list location
    // as another iterator.
    //
    bool operator!=(const iterator_template& other_iterator) const
    {
        return !(*this == other_iterator);
    }

    //
    // Assignment operator.
    // Make the iterator point to the same location in the list as
    // another iterator
    //
    const iterator_template& operator=(const iterator_template& other_iterator)
    {
        list_ = other_iterator.list_;
        current_node_ = other_iterator.current_node_;
        return *this;
    }

    //
    // Return the item at the current position of the iterator
    //
    Ref operator*() const
    {
        assert(current_node_ != 0);
        assert(current_node_ != list_ -> head_);
        assert(current_node_ != list_ -> tail_);

        return current_node_->item();
    }

    //
    // Move the iterator to the next position in the list
    //
    iterator_template& operator++()
    {
        assert(current_node_ != 0);
        assert(current_node_ != list_ -> tail_);

        current_node_ = current_node_->next();
        return *this;
    }

    //
    // Move the iterator to the next position in the list
    // (postfix)
    //
    iterator_template operator++(int)
    {
        iterator_template previous_state = *this;
        ++(*this);
        return previous_state;
    }

    //
    // Move the iterator to the previous position in the list
    //
    iterator_template& operator--()
    {
        assert(current_node_ != 0);
        assert(current_node_ != list_ -> head_);

        current_node_ = current_node_->prev();
        return *this;
    }

    //
    // Move the iterator to the previous position in the list
    // (postfix)
    //
    iterator_template operator--(int)
    {
        iterator_template previous_state = *this;
        --(*this);
        return previous_state;
    }
}; // End iterator_template


//
// A template for implementing bidirectional reverse iterators.
// Used to create both const and non-const iterators that work
// backwards (from the last element to the first) over a list
//
// Ref is a reference to T
// Iterator is an iterator over the list
// ListPtr is a pointer to list<T>
// 
template<class T, class Ref, class Iterator, class ListPtr>
class reverse_iterator_template
{
private:
    friend class list<T>;
            
    //
    // We implement the reverse iterator be simply reversing the
    // operations applied a forward iterator
    //
    Iterator current_;

    //
    // Create a reverse iterator from a forward iterator
    //
    reverse_iterator_template(const Iterator& current)
        : current_(current)
    {
    }

public:
    typedef T value_type;

    //
    // Default constructor.
    // After construction it cannot be used as it points nowhere,
    // except to be assigned the value of another iterator.
    //
    reverse_iterator_template()
    {
    }

    //
    // Create an iterator that points to the same list location
    // as another iterator
    //
    reverse_iterator_template(
        const reverse_iterator_template& other_iterator)
        : current_(other_iterator.current_)
    {
    }

    //
    // Destructor
    //
    ~reverse_iterator_template()
    {
    }

    //
    // Equality operator.
    // Determine if this iterator is pointing at the same list location
    // as another iterator.
    //
    bool operator==(
        const reverse_iterator_template& other_iterator) const
    {
        return other_iterator.current_ == current_;
    }

    //
    // Inequality operator.
    // Determine if this iterator is not pointing at the same list location
    // as another iterator.
    //
    bool operator!=(
        const reverse_iterator_template& other_iterator) const
    {
        return !(*this == other_iterator);
    }

    //
    // Assignment operator.
    // Make the iterator point to the same location in the list as
    // another iterator
    //
    const reverse_iterator_template& operator=(
        const reverse_iterator_template& other_iterator)
    {
        current_ = other_iterator.current_;
        return *this;
    }

    //
    // Return the item at the current position of the iterator
    //
    Ref operator*() const
    {
        return *current_;
    }

    //
    // Move the iterator to the next position in the list
    //
    reverse_iterator_template& operator++()
    {
        --current_;
        return *this;
    }

    //
    // Move the iterator to the next position in the list
    // (postfix)
    //
    reverse_iterator_template operator++(int)
    {
        reverse_iterator_template previous_state = *this;
        current_--;
        return previous_state;
    }

    //
    // Move the iterator to the previous position in the list
    //
    reverse_iterator_template& operator--()
    {
        ++current_;
        return *this;
    }

    //
    // Move the iterator to the previous position in the list
    // (postfix)
    //
    reverse_iterator_template operator--(int)
    {
        reverse_iterator_template previous_state = *this;
        current_++;
        return previous_state;
    }
}; // End reverse_iterator_template

//
// list implementation
//
// The list is implemented as a doubley linked list.
// Each item placed in the list is stored in a "list node".
// This list node contains the item, a pointer to the next node, and a
// pointer to the previous node.
//
// To support the full STL bidirectional iterator functionality, each list
// has two distinct nodes, "head" and "tail".
// These are required to allow iteration to move past the last node in
// the list (to the "end") position, and then move back to the last node.
// The same applies with the start of the list and a reverse iterator.
// If the start and end of the list were represented with 0 pointers from
// the actual first and last nodes in the list, then the expression:
//
// list.end()--
//
// ... will fail, as list.end() would return the 0 pointer.
// This problem also occurs at the beginning of the list when using a reverse
// iterator to traverse from the end to the beginning of the list.
// Again list.rend() cannot return 0, as the expression list.rend() would
// fail.
// The cost of the extra two nodes per list is not considered significant.
//
// List nodes are allocated from a STL-like "allocator" template class.
// We have not supplied the allocator as a template parameter in this
// first version to simplify porting to platforms with less than perfect
// support for templates.
// The allocator used is a simple pool of list nodes, which allocates
// memory for the node objects in chunks of N objects.
//
template <class T>
class ListNodeT
{
    T item_;
    ListNodeT *next_;
    ListNodeT *prev_;

public:
    ListNodeT() : next_(0), prev_(0)
    {
    }
	
    ListNodeT(const T& item, ListNodeT *next, ListNodeT *prev)
	: item_(item), next_(next), prev_(prev)
    {
    }

    ~ListNodeT()
    {
    }

    T& item()
    {
	return item_;
    }

    const T& item() const
    {
	return item_;
    }

    ListNodeT* next()
    {
	return next_;
    }

    const ListNodeT* next() const
    {
	return next_;
    }

    void next(ListNodeT* node)
    {
	next_ = node;
    }

    ListNodeT* prev()
    {
	return prev_;
    }

    const ListNodeT* prev() const
    {
	return prev_;
    }

    void prev(ListNodeT* node)
    {
	prev_ = node;
    }
};

template <class T>
class list
{
public:

    //
    // A linked list is composed of list nodes. Each list node has a link
    // pointing to the next node in the list, and to the previous node in
    // the list. A 0 value in either link implis that there is no node at
    // the end of that link, so this node is at one end of the node chain.
    // Each node also contains an item of type T, which is the item stored
    // by this node of the list.
    //

    //
    // The allocator for list nodes
    //
    // I know, it's not exactly OSI std::list, but I don't want to
    // risk breaking certain compilers by nesting templates
    // to implement "rebind" in allocator just yet
    //
    allocator< ListNodeT< T > > node_allocator;

    typedef ListNodeT<T> ListNode;

public:
    // Required std::list declarations
    typedef unsigned long size_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;

    //
    // Define iterators over the list using iterator_template
    //

    typedef iterator_template<T, T&, ListNode*, list*>
    iterator;

    typedef iterator_template<T, const T&, const ListNode*, const list*>
    const_iterator;

    //
    // Define reverse iterators over the list using
    // reverse_iterator_template
    //

    typedef reverse_iterator_template
    <T, T&, iterator, list*>
    reverse_iterator;

    typedef reverse_iterator_template
    <T, const T&, const_iterator, const list*>
    const_reverse_iterator;

private:
    // Allow iterators access to class internals

    friend class
        iterator_template<T, T&, ListNode*, list*>;

    friend class
        reverse_iterator_template<T, T&, iterator, list*>;

    friend class
        iterator_template<T, const T&, const ListNode*, const list*>;

    friend class
        reverse_iterator_template<T, const T&, const_iterator, const list*>;
    
    // Pointers to the head and tail of the list
    ListNode *head_;
    ListNode *tail_;

    // The number of items in the list
    size_type size_;

public:
    //
    // Create two linked nodes that represent the head and tail of the new
    // list.
    //
    list() :
        head_(new ListNode(T(), 0, 0)),
        tail_(new ListNode(T(), 0, 0)),
        size_(0)
    {
        head_ -> next(tail_);
        tail_ -> prev(head_);
    }

    //
    // Destructor
    //
    ~list()
    {
        erase(begin(), end());
        delete head_;
        delete tail_;
    }

    //
    // Create two linked nodes that represent the head and tail of the new
    // list, then add all the elements from the other list to this list.
    //
    list(const list& other_list) :
        head_(new ListNode(T(), 0, 0)),
        tail_(new ListNode(T(), 0, 0)),
        size_(0)
    {
        head_ -> next(tail_);
        tail_ -> prev(head_);
        OB_STL::copy(other_list.begin(), other_list.end(),
                     OB_STL::back_inserter(*this));
    }

    //
    // Assign the contents of another list to this list by erasing all
    // items in this list, and copying the items in the other list into
    // this one
    //
    const list& operator=(const list& other_list)
    {
        erase(begin(), end());
        OB_STL::copy(other_list.begin(), other_list.end(),
                     OB_STL::back_inserter(*this));
        return *this;
    }
    
    //
    // Return an iterator positioned at the start of the list
    //
    iterator begin()
    {
        return iterator(this, head_ -> next());
    }
    
    //
    // Return a const_iterator positioned at the start of the list
    //
    const_iterator begin() const
    {
        return const_iterator(this, head_ -> next());
    }
    
    //
    // Return an iterator positioned at the end of the list
    //
    iterator end()
    {
        return iterator(this, tail_);
    }

    //
    // Return a const_iterator positioned at the end of the list
    //
    const_iterator end() const
    {
        return const_iterator(this, tail_);
    }

    //
    // Return a reverse_iterator positioned at the end of the list
    //
    reverse_iterator rbegin()
    {
        return reverse_iterator(--end());
    }

    //
    // Return a const_reverse_iterator positioned at the end of the list
    //
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(--end());
    }

    //
    // Return a reverse_iterator positioned at the start of the list
    //
    reverse_iterator rend()
    {
        return reverse_iterator(--begin());
    }

    //
    // Return a const_reverse_iterator positioned at the start of the list
    //
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(--begin());
    }

    //
    // Return the number of items in the list
    //
    size_type size() const
    {
        return size_;
    }

    //
    // Return true if the list contains no items
    //
    bool empty() const
    {
        return size_ == 0;
    }

    //
    // Return the item at the front of the list.
    // The list must not be empty.
    //
    reference front()
    {
        assert(size_ != 0); // List cannot be empty
        return *begin();
    }

    //
    // Return the item at the front of the list.
    // The list must not be empty.
    //
    const_reference front() const
    {
        assert(size_ != 0); // List cannot be empty
        return *begin();
    }

    //
    // Return the item at the end of the list.
    // The list must not be empty.
    //
    reference back()
    {
        assert(size_ != 0); // List cannot be empty
        return *(--end());
    }

    //
    // Return the item at the end of the list.
    // The list must not be empty.
    //
    const_reference back() const
    {
        assert(size_ != 0); // List cannot be empty
        return *(--end());
    }

    //
    // Add an item to the front of the list
    //
    void push_front(const T& x)
    {
        insert(begin(), x);
    }

    //
    // Add an item to the end of the list
    //
    void push_back(const T& x)
    {
        insert(end(), x);
    }

    //
    // Move all the items from x into the list at 'position'.
    // x will be empty after calling this method.
    //
    void splice(const iterator& position, list<T>& x)
    {
        splice(position, x, x.begin(), x.end());
    }

    //
    // Move the item of 'i' from x into the list at 'position'.
    // The item is removed from x.
    //
    void splice(const iterator& position, list<T>& x, iterator i)
    {
        insert(position, *i);
        x.erase(i);
    }

    //
    // Insert items from [first, last) of x into the list at
    // 'position'.
    // Remove items [first, last) from x.
    //
    void splice(const iterator& position, list<T>& x,
                iterator first, iterator last)
    {
        for (iterator x_iter = first; x_iter != last; x_iter++)
        {
            insert(position, *x_iter);
        }

        x.erase(first, last);        
    }

    //
    // Insert an item into the list at the position given.
    // All items from [position, end()) are now immediately after the
    // new item in the list.
    //
    iterator insert(const iterator& position, const T& x)
    {
        assert(position != --begin()); // Can't insert past the beginning

        ListNode* current_node = position.current_node_;

        typename allocator<ListNode>::pointer new_node =
            node_allocator.allocate(1);
        node_allocator.construct(new_node,
                                 ListNode(x,
                                          current_node,
                                          current_node->prev()));

        current_node->prev()->next(new_node);
        current_node->prev(new_node);
			      
        size_++;

        return iterator(this, new_node);
    }

    //
    // Remove the item at the front of the list.
    // The list must not be empty.
    //
    void pop_front()
    {
        assert(size_ != 0); // List cannot be empty
        erase(begin());
    }

    //
    // Remove the item at the end of the list.
    // The list must not be empty.
    //
    void pop_back()
    {
        assert(size_ != 0); // List cannot be empty
        erase(--end());
    }

    //
    // Remove the item at the given position from the list.
    //
    void erase(const iterator &position)
    {
        assert(size_ != 0); // List cannot be empty
        assert(position != end()); // Cannot erase past the end
        assert(position != --begin()); // Cannot insert past the beginning

        ListNode* current_node = position.current_node_;

        current_node->prev()->next(current_node->next());
        current_node->next()->prev(current_node->prev());

        size_--;

        node_allocator.destroy(current_node);
        node_allocator.deallocate(current_node, 1);
    }

    //
    // Remove all items in the sequence [first, last) from the list.
    //
    void erase(const iterator& first, const iterator& last)
    {
        iterator position = first;
        while(position != last)
        {
            iterator victim = position;
            position++;
            erase(victim);
        }
    }

    // Erase all the list's elements.
    void clear()
    {
        erase(begin(), end());
    }

}; // End list


} // End of namespace stl

} // End of namespace OB

#endif
