// Semantics Consulting's Tyr Library
// http://www.semantics.org
//
// Copyright (c) 2003 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 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 Running Circles Round You, Logically. C/C++ Users Journal 20, 6 (June 2002).
//
// 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.
//
/// NOTE:  This code is a modified version of what appeared in the article.  The original code incorrectly
/// used ptrdiff_t to hold the value of a pointer (That approach will often "work" but it's not
/// guaranteed to.)  Here we use a more careful (but, I believe, still not guaranteed by the standard)
/// approach.  See uintptr_t, tobits, and toptr below.
///
/// Thanks to Kevlin Henney for complaining about my use of ptrdiff_t to hold a pointer value, and
/// to Dan Saks for informing me about C's intptr_t and uinptr_t types.

#ifndef LIST_H
#define LIST_H

#include "utils.h"

namespace Tyr {

/// uintptr_t is an attempt to create a type similar to C's uintptr_t
/// that can hold or transmit the value of a void * safely.
typedef Select<
					(sizeof(void *)<=sizeof(unsigned int)),
					unsigned int,
					Select<
							(sizeof(void *)<=sizeof(unsigned long)),
							unsigned long,
							void //will cause compile error if used
					>::R
				>::R uintptr_t;

/// Simple utilities to copy pointers to and from a uintptr_t.
/// I'm being extra careful here (or I intend to be) and make sure that
/// any pointer value passes through a void * on its way to or from a
/// uintptr_t.  This probably isn't necessary, but it helps me to sleep.
///
/// The other precaution I'm taking now that I didn't before (since we're
/// on the subject of paranoia) is that two-way pointer values are always
/// stored in a uintptr_t and not in any type of pointer.  This is because
/// the value of a two-way pointer is only rarely a valid address, and
/// there may be integral values that may not be stored in a pointer object.
inline uintptr_t
tobits( void *ptr )
	{ return reinterpret_cast<uintptr_t>(ptr); }

template <typename Ptr, typename Bits>
inline Ptr
toptr( Bits bits )
	{ return static_cast<Ptr>(reinterpret_cast<void *>(bits)); }

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

struct ListElBase {
	ListElBase () : ptr(0) {}
	uintptr_t ptr; /// note that ptr is no longer a pointer, but a uint_t
};

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 ptrdiff_t difference_type;
	typedef 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 ListEl<T> *Ptr;
  	ListElBase clasp;
  	ListEl<T> *&hd, *&tl, *p1, *p2;
  	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 ) {
	Ptr newEl = new ListEl<T>( v );
	newEl->ptr = tobits(&clasp) ^ tobits(hd);
	hd->ptr = hd->ptr^tobits(newEl) ^ tobits(&clasp);
	clasp.ptr = clasp.ptr ^ tobits(newEl) ^ tobits(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 = toptr<Ptr>( hd->ptr ^ tobits(&clasp) );
	clasp.ptr = tobits(tl) ^ tobits(n);
	n->ptr = n->ptr ^ tobits(hd) ^ tobits(&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() {
    Ptr temp( p1 );
    p1 = p2;
    p2 = temp;
}

// 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, 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 typename List<T>::Ptr Ptr;
  	Ptr prev, curr;
};

template <typename T>
Iter<T> List<T>::begin()
	{ return Iter<T>(hd,static_cast<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>( static_cast<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 = toptr<Ptr>(curr->ptr ^ tobits(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 = toptr<Ptr>(curr->ptr ^ tobits(prev)); }

} // namespace Tyr

#endif