//
// Copyright (c) 2002 by Stephen C. Dewhurst
// Permission to use, copy, modify, distribute and sell this software for any purpose is
// hereby granted without fee, provided that the above copyright notice appears in all copies
// and that both that copyright notice and this permission notice appear in supporting documentation.
// The author or makes no representations about the suitability of this software for any purpose.
// It is provided "as is" without express or implied warranty.
//

// List
//
// Described in CUJ 20(6), June 2002:  "Running Circles Round You, Logically" 
// List (great name, huh?) is an STL-like container that uses two-way pointers to implement a
// singly-linked list that can change its mind as to which way it's organized.  Its iterators are
// similarly confused, and this makes for some interesting complexity results. 

#ifndef LIST_H
#define LIST_H

namespace org_semantics {

template <typename T> class List;
template <typename T> class Iter;
template <typename T> class ListEl;

struct ListElBase {
	ListElBase () : ptr(0) {}
	ListElBase *ptr;
	typedef std::ptrdiff_t Bits;
};

template <typename T>
class ListEl : public ListElBase {
	ListEl( const T &v ) : el( v ) {}
	T el;
	friend class List<T>;
	friend class Iter<T>;
};

template <typename T>
class List {
  public:
	typedef Iter<T> iterator;
	typedef T value_type;
	typedef std::ptrdiff_t difference_type;
	typedef std::size_t size_type;
	typedef value_type *pointer;
	typedef const value_type *const_pointer;
	typedef value_type &reference;
	typedef const value_type const_reference;
	List();
	~List();
	//List( const List & );
	//List &operator =( const List & );
	bool empty() const;
	// size, max_size, swap omitted for space
	void push_back( const T &v );
	void push_front( const T &v );
	void pop_front();
	void pop_back();
	iterator begin();
	iterator end();
	// const versions omitted for space
	void reverse();
  private:
  	typedef ListElBase::Bits Bits;
  	typedef ListEl<T> *Ptr;
  	ListElBase clasp;
  	ListEl<T> *&hd, *&tl, *p1, *p2; // should be ListEl<T> **: can't assign or swap
  	void push( const T &value, Ptr &head, Ptr &tail );
  	void pop( Ptr &head, Ptr &tail );
	friend class Iter<T>;
};

template <typename T>
List<T>::~List()
	{}

template <typename T>
List<T>::List()
	: hd(p1), tl(p2), p1( Ptr(&clasp) ), p2( Ptr(&clasp) ) {}

template <typename T>
bool List<T>::empty() const
	{ return hd == &clasp; }

template <typename T>
void List<T>::push( const T &v, Ptr &hd, Ptr &tl ) {
	ListEl<T> *newEl = new ListEl<T>( v );
	newEl->ptr = Ptr( Bits(&clasp)^Bits(hd) );
	hd->ptr = Ptr( Bits(hd->ptr)^Bits(newEl)^Bits(&clasp) );
	clasp.ptr = Ptr( Bits(clasp.ptr)^Bits(newEl)^Bits(hd) );
	if( empty() )
		tl = newEl;
	hd = newEl;
}

template <typename T>
void List<T>::push_front( const T &v )
	{ push( v, hd, tl ); }

template <typename T>
void List<T>::push_back( const T &v )
	{ push( v, tl, hd ); }

template <typename T>
void List<T>::pop( Ptr &hd, Ptr &tl ) {
	Ptr n = Ptr( Bits(hd->ptr)^Bits(&clasp) );
	clasp.ptr = Ptr( Bits(tl)^Bits(n) );
	n->ptr = Ptr( Bits(n->ptr)^Bits(hd)^Bits(&clasp) );
	if( tl == hd )
		tl = n;
	delete hd;
	hd = n;
}

template <class T>
void List<T>::pop_front()
	{ pop( hd, tl ); }

template <class T>
void List<T>::pop_back()
	{ pop( tl, hd ); }

template <typename T>
void List<T>::reverse() {
	// We should use std::swap, but...
	(Bits &)p1 ^= (Bits &)p2;
    (Bits &)p2 ^= (Bits &)p1;
    (Bits &)p1 ^= (Bits &)p2;
}

// Not quite an STL "node-based" container, since an inserted or deleted
// node affects iterators to adjacent nodes.
template <class T>
class Iter : public std::iterator<std::forward_iterator_tag, T, std::ptrdiff_t> {
  public:
	Iter( ListEl<T> *start, ListEl<T> *previous );
	Iter() {}
	Iter &operator ++();
	Iter operator ++(int);
	T &operator *();
	T *operator ->();
	bool operator ==( const Iter &that ) const;
	bool operator !=( const Iter &that ) const;
	void reverse();
  private:
  	typedef ListEl<T>::Bits Bits;
  	typedef List<T>::Ptr Ptr;
  	ListEl<T> *prev, *curr;
};

template <typename T>
Iter<T> List<T>::begin()
	{ return Iter<T>(hd,Ptr(&clasp)); }

template <typename T>
Iter<T> List<T>::end()
	// There are really two different end values, like +0 and -0
	//{ return Iter<T>( &clasp, &clasp ); } // this end value does not "reverse"
	{ return Iter<T>( Ptr(&clasp), tl ); } // even end has a direction
										// both end values compare equal, but behave differently when reversed

template <typename T>
Iter<T>::Iter( ListEl<T> *start, ListEl<T> *previous )
	: prev(previous), curr(start) {}
	
template <typename T>
Iter<T> &Iter<T>::operator ++() {
	ListEl<T> *tmp = curr;
	curr = (ListEl<T> *)(Bits(curr->ptr) ^ Bits(prev));
	prev = tmp;
	return *this;
}

template <typename T>
Iter<T> Iter<T>::operator ++(int) {
	Iter tmp( *this );
	++*this;
	return tmp;
}

template <typename T>
T &Iter<T>::operator *()
	{ return curr->el; }

template <typename T>
T *Iter<T>::operator ->()
	{ return &curr->el; }

template <typename T>
bool Iter<T>::operator ==( const Iter &that ) const
	// equality is a question about the current node we refer to,
	// not what direction we're heading
	{ return curr == that.curr; }

template <typename T>
bool Iter<T>::operator !=( const Iter &that ) const
	{ return !(*this == that); }

template <typename T>
void Iter<T>::reverse()
	// reversing is just changing your mind about what the previous node is.
	{ prev = Ptr(Bits(curr->ptr) ^ Bits(prev)); }

} // org_semantics

#endif