//
// Copyright (c) 2002-2006 by Stephen C. Dewhurst
//
// http://www.semantics.org
//
// 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 representation about the suitability of this software for any purpose.
// It is provided "as is" without express or implied warranty.
//
// flist
//
// flist is pronounced "ef list."  The "f" stands for "fickle."
//
// An early version is described in CUJ 20(6), June 2002:  "Running Circles Round You, Logically."
// A prepublication version of the above article is available at
//     http://www.semantics.org/publications/02_06_logicalcircles.pdf
//
// flist is an STL-compliant container that uses two-way pointers to implement a doubly-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.
//
// flist has all the same members as std::list (splice, sort, merge, reverse, etc.)
//
// flist has half the storage overhead of list while providing similar performance (except for reversing,
// where flist beats the pants off list).
//
// flist has the same storage overhead and similar performance to (typical, non-standard) slist (except
// for insert, erase, and reverse, where flist provides constant time, rather than linear performance)
// but provides bidirectional rather than forward iterators.  For compatibility with slist, flist also
// provides the slist insert_after, erase_after, splice_after, and previous members.
//
// The major difference between flist and list or slist is that flist is not a "node-based" container (even
// though it's implemented with nodes) because insertion, deletion, swapping, splicing, or assigning
// can invalidate iterators adjacent to the nodes directly affected by the operation.  Note, however,
// that, like std::deque, pointers and references to adjacent nodes are not affected by these operations.
//
// Due to iterator invalidation during splicing, flist's isplice operations return an flist::splice_return_type
// which contains three iterators: two give the spliced subrange in the target list, and the third gives
// the end iterator from the source list.  splice_return_type is a pair, the first element of which is a pair:
//
//     typedef std::pair<std::pair<iterator,iterator>,iterator> splice_return_type;
//
// Because a (typically) 24-byte return may be too bulky for some applications, the usual "splice" members
// have the usual void return.
//
// flist's "fickle" iterators are unusual in that they can easily change their minds about about which way
// they're traversing (that's what makes them fickle).  Note that flist also provides reverse_iterators,
// but they differ from fickle iterators, since reverse_iterators are always reversed.  Direction
// of iteration in an flist is relative anyway, since an flist can reverse itself in constant time.
// Many algorithms can be efficiently rendered by reversing an flist and its iterators at will;
// reversing an flist or flist iterator has about the same cost as incrementing an iterator.
// Changing direction with a fickle iterator is faster and simpler than the corresponding code written with
// reverse-iterators, because ++ may be marginally faster than -- for flist, and there is no irritating base()
// offset for fickle iterators as there is for a reverse_iterator; that is, when you reverse an flist iterator,
// it still refers to the same list element, it's just that the effects of ++ and -- are reversed.  (If the
// above discussion irritates you, just avoid the reverse functions, and use an flist as a lightweight list.)
//
// This implementation tries to do a fairly good job of minimizing code bloat for different instantiations
// of flist.  Nearly all the template-argument-specific code consists of compile-time-only static
// casts.
//
// Note:  This code is a heavily modified version of what appeared in the article.
// One big change: this version has "fickle bidirectional" iterators rather than "fickle forward"
// iterators.
//
// Final Note:  This code was originally intended for use as an exercise in an advanced STL course.
// (See http://www.semantics.org for more information on such courses.)  This observation may help to
// excuse the fussy or preachy tone of some of the comments in the code.
//
// Really Final Note:  Let's call this version 0.97 of flist (July, 2006).  The implementation has been
// tested a fair amount, but has not been in production use.  If there's a more recent version of flist
// available, it will be found at http://www.semantics.org/code.html.
//
// Thanks to Kevlin Henney for complaining about my use of ptrdiff_t in the original implementation
// to hold a pointer value, and to Dan Saks for informing me about C's intptr_t and uintptr_t types.

#ifndef FLIST_H
#define FLIST_H

#include <iterator>
#include <limits>

#ifndef NDEBUG
#include <iostream> // for debug code only...
#endif

namespace Tyr {

//
//	An implementation of comparison operators with CRTP
//	for use below.
//
//	Note use of EBO chaining to reduce storage overhead.
//
struct EndOfChain {};

template <class T, class Next = EndOfChain>
struct CompOps : public Next {
	bool operator !=( const T &b )
		{ return !(*static_cast<const T *>(this) == b); }
	bool operator >( const T &b )const
		{ return b < *static_cast<const T *>(this); }
	bool operator >=( const T &b ) const
		{ return !(*static_cast<const T *>(this) < b); }
	bool operator <=( const T &b ) const
		{ return !(b < *static_cast<const T *>(this)); }
};

//
//	This is (similar to) Alexandrescu's Select.
//
template <bool, typename, typename B>
struct Select
    { typedef B R; };

template <typename A, typename B>
struct Select<true,A,B>
    { typedef A R; };

// 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 (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 PtrType, typename Bits>
inline PtrType toptr( Bits bits )
	{ return static_cast<PtrType>(reinterpret_cast<void *>(bits)); }

//
//	The major entities that make up the list implementation are:
//		flist: the user interface
//		ListImpl: an implementation base class for flist
//		ListImplBase: factoring base class for ListImpl
//		ListImpl::ListEl: what the implementation holds: list nodes
//		ListElBase, a factoring base for ListEl
//		ListIter, ConstListIter: iterators
//		IterImpl: factoring base class for iterators
//
template <typename T, class A> class flist;
template <typename T, class A> class ListImpl;
template <class ListHandle> class ConstListIter;
template <class ListHandle> class ListIter;

//
// We use a base class for the "clasp" so as to avoid expense
// or restrictions (e.g. a requirement for a default ctor) on the
// element type of the list.
//
// The term "clasp": As the original article states, "The curious clasp
// identifier comes from my visualizing this structure as a bead necklace,
// which is held together by a clasp that differs in structure from the beads."
//
// The ptr_ member is a 2-way pointer that contains an encoding of
// the next and previous node addrs: next ^ previous.
// Note that next ^ previous ^ next == previous and that
// next ^ previous ^ previous == next.
struct ListElBase {
	ListElBase () : ptr_(0) {}
	uintptr_t ptr_;
};

//
// Factoring for ListImpl, since much of the code is
// independent of element type and allocator.
//
// Note that all the members of ListImplBase are nothrow.
//
class ListImplBase {
  public:
  	typedef ListElBase *NodePtr;
	NodePtr tail() const;
	NodePtr claspAddr() const; // safe, avoids mutable on clasp_
	ListImplBase();
	bool empty() const;
	void insertImpl( ListElBase *newNode, ListElBase *curr, ListElBase *prev );
	NodePtr eraseImpl( ListElBase *curr, ListElBase *prev );
	void spliceImpl(ListElBase *b_prev, ListElBase *b_curr,
		ListElBase *e_prev, ListElBase *e_curr,
		ListElBase *at_prev, ListElBase *at_curr,
		ListElBase *&from_hd );
	void reverse();
	ListElBase clasp_; // root of circular list
  	ListElBase *hd_; // head of the path around circle that leads indirectly to clasp_
};

inline ListImplBase::NodePtr ListImplBase::tail() const
	{ return toptr<NodePtr>(clasp_.ptr_ ^ tobits(hd_)); }

inline ListImplBase::NodePtr ListImplBase::claspAddr() const
	{ return const_cast<NodePtr>(&clasp_); }

inline ListImplBase::ListImplBase()
	: hd_(&clasp_) { clasp_.ptr_ = 0; }

inline bool ListImplBase::empty() const
	{ return hd_ == &clasp_; }

void ListImplBase::insertImpl( NodePtr newEl, NodePtr curr, NodePtr prev ) {
	if( curr == hd_ )
		hd_ = newEl;
	curr->ptr_ ^= tobits(newEl) ^ tobits(prev);
	newEl->ptr_ = tobits(prev) ^ tobits(curr);
	prev->ptr_ ^= tobits(curr) ^ tobits(newEl);
}

ListImplBase::NodePtr ListImplBase::eraseImpl( ListElBase *curr, ListElBase *prev ) {
	NodePtr next = toptr<NodePtr>(curr->ptr_ ^ tobits(prev));
	if( hd_ == curr )
		hd_ = next;
	next->ptr_ ^= tobits(curr) ^ tobits(prev);
	prev->ptr_ ^= tobits(curr) ^ tobits(next);
	return next;
}

void ListImplBase::spliceImpl(
		ListElBase *b_prev, ListElBase *b_curr,
		ListElBase *e_prev, ListElBase *e_curr,
		ListElBase *at_prev, ListElBase *at_curr,
		ListElBase *&from_hd ) {
	// Detach [b,e) from source list.
	b_prev->ptr_ ^= tobits(b_curr) ^ tobits(e_curr);
	e_curr->ptr_ ^= tobits(e_prev) ^ tobits(b_prev);
	if( from_hd == b_curr )
		from_hd = e_curr;
	
	// Attach [b,e) to target list.
	at_prev->ptr_ ^= tobits(at_curr) ^ tobits(b_curr);
	b_curr->ptr_ ^= tobits(b_prev) ^ tobits(at_prev);
	e_prev->ptr_ ^= tobits(e_curr) ^ tobits(at_curr);
	at_curr->ptr_ ^= tobits(at_prev) ^ tobits(e_prev);
	if( hd_ == at_curr )
		hd_ = b_curr;
}

inline void ListImplBase::reverse()
	{ hd_ = tail(); }

//
//	flist implementation
//
// Note that all ListImpl members are strongly exception safe.
//
template <typename T, class A>
class ListImpl : public A, public ListImplBase {
  public:
	// get the types from the allocator
	typedef A allocator_type;
	typedef typename allocator_type::value_type value_type;
	typedef typename allocator_type::difference_type difference_type;
	typedef typename allocator_type::size_type size_type;
	typedef typename allocator_type::pointer pointer;
	typedef typename allocator_type::const_pointer const_pointer;
	typedef typename allocator_type::reference reference;
	typedef typename allocator_type::const_reference const_reference;
	
	typedef ListIter< ListImpl<T,A> > iterator;
	typedef ConstListIter< ListImpl<T,A> > const_iterator;
	typedef std::reverse_iterator<iterator> reverse_iterator;
	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
		
	// Iterator invalidation is a problem when splicing, so we provide information
	// in the return: the [begin,end) of the newly sliced section in the destination
	// list, and the location following the spliced elements in the source list (basically
	// the old end node).
	typedef std::pair<std::pair<iterator,iterator>,iterator> splice_return_type;
	
	ListImpl();
	~ListImpl();
	
	allocator_type get_allocator() const;
	difference_type size() const;
	size_type max_size() const;
	void push_back( const T &v );
	void push_front( const T &v );
	void pop_front();
	void pop_back();
	iterator insert( iterator, const value_type & );
	iterator erase( iterator );
	splice_return_type ispliceImpl( iterator at, ListImpl &, iterator b, iterator e );
	void spliceImpl( iterator at, ListImpl &, iterator b, iterator e );
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;
	
	struct ListEl : public ListElBase {
		T el_; // the list element's value
	};
	typedef ListEl *DerivedNodePtr;
	typedef typename allocator_type::template rebind<ListEl>::other NA;
	NA nodeAlloc_; // Node allocator; allocates "ListEl"s.
		// Note use of "compressed_pair" would be more trouble than it's worth in this context.
	NA &get_node_allocator() const { return nodeAlloc_; }
	NodePtr newNode( const value_type & );
	void deleteNode( DerivedNodePtr );
	
  	void print( const char * ) const; // just for debugging
  private:
  	// disallow copying
	ListImpl( const ListImpl & );
	ListImpl &operator =( const ListImpl & );
};

template <typename T, class A>
inline typename ListImpl<T,A>::NodePtr ListImpl<T,A>::newNode( const value_type &v ) {
	// Note that this is the only use of a try block in the entire
	// implementation of flist.  Correctly-written exception safe code
	// generally employs few try-blocks.
	DerivedNodePtr n = nodeAlloc_.allocate( 1 );
	try {
		this->construct( &n->el_, v );
	}
	catch( ... ) {
		nodeAlloc_.deallocate( n, 1 );
		throw;
	}
	return n;
}

template <typename T, class A>
inline void ListImpl<T,A>::deleteNode( DerivedNodePtr p ) {
	this->destroy( &p->el_ );
	nodeAlloc_.deallocate( p, 1 );
}

template <typename T, class A>
inline ListImpl<T,A>::ListImpl() : ListImplBase()
	{}

template <typename T, class A>
ListImpl<T,A>::~ListImpl() {
	while( !empty() )
		pop_front();
}

template <typename T, class A>
typename ListImpl<T,A>::allocator_type ListImpl<T,A>::get_allocator() const {
	// Slicing isn't always bad, but it should always be well-hidden
	// and intentional.  Here we slice off a copy of the allocator.
	// See also the implementation of iterator to const_iterator conversion.
	// By the way, we derive from the allocator because allocators often
	// are "empty," and we can thereby pick up the empty base class optimization.
	// The allocator is in no way a polymorphic base class.
	return *this;
}

template <typename T, class A>
typename ListImpl<T,A>::difference_type ListImpl<T,A>::size() const {
	// Note: linear time so isplice can be constant time.
	size_type len( 0 );
	for( const_iterator i( begin() ); i != end(); ++i )
		++len;
	return len;
}

template <typename T, class A>
inline typename ListImpl<T,A>::size_type ListImpl<T,A>::max_size() const
    { return std::numeric_limits<size_type>::max(); }

template <typename T, class A>
void ListImpl<T,A>::push_front( const T &v ) {
	// Note ordering of operations for exception safety.
	NodePtr newEl = newNode( v );
	iterator at = begin();
	ListImplBase::insertImpl( newEl, at.curr_, at.prev_ );
}

template <typename T, class A>
void ListImpl<T,A>::push_back( const T &v ) {
	// Note ordering of operations for exception safety.
	NodePtr newEl = newNode( v );
	iterator at = end();
	ListImplBase::insertImpl( newEl, at.curr_, at.prev_ );
}

template <typename T, class A>
void ListImpl<T,A>::pop_front() {
	iterator at = begin();
	ListImplBase::eraseImpl( at.curr_, at.prev_ );
	deleteNode( static_cast<DerivedNodePtr>( at.curr_ ) );
}

template <typename T, class A>
inline void ListImpl<T,A>::pop_back() {
	reverse();
	pop_front();
	reverse();
}

template <typename T, typename A>
typename ListImpl<T,A>::iterator ListImpl<T,A>::insert( iterator i, const value_type &v ) {
	NodePtr newEl = newNode( v );
	ListImplBase::insertImpl( newEl, i.curr_, i.prev_ );
	return iterator( newEl, i.prev_ );
}

template <typename T, typename A>
typename ListImpl<T,A>::iterator ListImpl<T,A>::erase( iterator i ) {
	NodePtr next = ListImplBase::eraseImpl( i.curr_, i.prev_ );
	deleteNode( static_cast<DerivedNodePtr>(i.curr_) );
	return iterator( next, i.prev_ );
}

template <typename T, typename A>
typename ListImpl<T,A>::splice_return_type ListImpl<T,A>::ispliceImpl( iterator at, ListImpl &from, iterator b, iterator e ) {
	splice_return_type nrv; // Note encouragement of the "named return value optimization."
	if( b == e ) {
		nrv.first.first = at;
		nrv.first.second = at;
		nrv.second = e;
	}
	else {
		nrv.first.first = iterator(b.curr_,at.prev_); // begin of spliced section (now in target list)
		nrv.first.second = iterator(at.curr_,e.prev_); // end of spliced section (now in target list)
		nrv.second = iterator(e.curr_,b.prev_); // element following spliced section (in source list)
		ListImplBase::spliceImpl( b.prev_, b.curr_, e.prev_, e.curr_, at.prev_, at.curr_, from.hd_ );
	}
	return nrv;
}

// spliceImpl is intended for use "behind the scenes," in those cases where
// the return value is not needed and you don't want to pay for a 24-byte return (NRV or not).
template <typename T, typename A>
inline void ListImpl<T,A>::spliceImpl( iterator at, ListImpl &from, iterator b, iterator e ) {
	if( b != e )
		ListImplBase::spliceImpl( b.prev_, b.curr_, e.prev_, e.curr_, at.prev_, at.curr_, from.hd_ );
}

template <typename T, class A>
inline typename ListImpl<T,A>::iterator ListImpl<T,A>::begin()
	{ return typename ListImpl<T,A>::iterator( hd_, claspAddr() ); }

template <typename T, class A>
inline typename ListImpl<T,A>::iterator ListImpl<T,A>::end()
	{ return typename ListImpl<T,A>::iterator( claspAddr(), tail() ); }

template <typename T, class A>
inline typename ListImpl<T,A>::const_iterator ListImpl<T,A>::begin() const
	{ return typename ListImpl<T,A>::const_iterator( hd_, claspAddr() ); }

template <typename T, class A>
inline typename ListImpl<T,A>::const_iterator ListImpl<T,A>::end() const
	{ return typename ListImpl<T,A>::const_iterator( claspAddr(), tail() ); } 

//
//	flist, the user interface
//
template < typename T, class A = std::allocator<T> >
class flist : public CompOps< flist<T,A>, ListImpl<T,A> > {
  public:
	typedef ListImpl<T,A> Impl;
	
	// get the types from the implementation
	typedef typename Impl::value_type value_type;
	typedef typename Impl::difference_type difference_type;
	typedef typename Impl::size_type size_type;
	typedef typename Impl::pointer pointer;
	typedef typename Impl::const_pointer const_pointer;
	typedef typename Impl::reference reference;
	typedef typename Impl::const_reference const_reference;
	
	typedef typename Impl::iterator iterator;
	typedef typename Impl::const_iterator const_iterator;
	typedef typename Impl::reverse_iterator reverse_iterator;
	typedef typename Impl::const_reverse_iterator const_reverse_iterator;
	
	typedef typename Impl::allocator_type allocator_type;
	typedef typename Impl::splice_return_type splice_return_type;
	
	flist();
	explicit flist( const allocator_type & );
	allocator_type get_allocator() const { return Impl::get_allocator(); }
	~flist();
	flist( const flist & );
	explicit flist( size_type );
	flist( size_type, const value_type & );
	template <typename In> flist( In, In );
	flist &operator =( const flist & );
	
	bool operator ==( const flist &rhs ) const;
	bool operator <( const flist &rhs ) const;
	bool empty() const;
	size_type size() const;
	size_type max_size() const;
	void swap( flist & );
	
	// stack and queue operations
	reference front();
	const_reference front() const;
	reference back();
	const_reference back() const;
	void push_back( const T &v );
	void push_front( const T &v );
	void pop_front();
	void pop_back();
	
	// resizing
	void assign( size_type, const T & );
	template <typename In> void assign( In, In );
	void clear();
	void resize( size_type );
	void resize( size_type, const value_type & );
	
	// inserting and erasing
	iterator insert( iterator, const value_type & );
	void insert( iterator, size_type, const value_type & );
	template <typename In> void insert( iterator, In b, In e );
	iterator erase( iterator );
	iterator erase( iterator, iterator );
	
	//splicing
	void splice( iterator, flist &, iterator, iterator );
	void splice( iterator, flist & );
	void splice( iterator, flist &, iterator );
	
	// flist-specific value-returning splices
	splice_return_type splice_before( iterator, flist &, iterator, iterator );
	splice_return_type splice_before( iterator, flist &, iterator );
	
	// iterators
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;
	reverse_iterator rbegin();
	reverse_iterator rend();
	const_reverse_iterator rbegin() const;
	const_reverse_iterator rend() const;
	
	// member algorithms
	void reverse();
	void remove( const T & );
	template <typename Pred> void remove_if( Pred );
	void unique();
	template <typename BinaryPred> void unique( BinaryPred );
	void merge( flist & );
	template <typename Comp> void merge( flist &, Comp );
	void sort();
	template <typename Comp> void sort( Comp );
	
	// flist versions of operations provided by slist
	iterator insert_after( iterator, const value_type & );
	void insert_after( iterator, size_type, const value_type & );
	template <typename In> void insert_after( iterator, In b, In e );
	iterator erase_after( iterator );
	iterator erase_after( iterator, iterator );
	splice_return_type splice_after( iterator, flist &, iterator, iterator );
	splice_return_type splice_after( iterator, flist &, iterator );
	splice_return_type splice_after( iterator, flist & );
	iterator previous( iterator );
	const_iterator previous( const_iterator ) const;
	
	// debug print only
	void print( const char * = "flist" ) const;
};

template <typename T, class A>
inline flist<T,A>::flist()
	{}

template <typename T, class A>
inline flist<T,A>::flist( const allocator_type & ) // ignore allocator argument
	{}

template <typename T, class A>
inline flist<T,A>::~flist()
	{}

template <typename T, class A>
inline flist<T,A>::flist( const flist &that ) {
	// RAII approach to exception safety.
	flist tmp;
	for( const_iterator i( that.begin() ); i != that.end(); ++i )
		tmp.push_back( *i );
	splice( begin(), tmp );
}

template <typename T, class A>
flist<T,A>::flist( size_type n ) {
	const T etmp( (T()) ); // Note: we need those extra parens!
	// The other "copy initialization" syntax is probably OK here too,
	// since T is required to have an accessible copy ctor.
	flist tmp;
	while( n-- )
		tmp.push_back( etmp );
	splice( begin(), tmp );
}

template <typename T, class A>
flist<T,A>::flist( size_type n, const value_type &v ) {
	flist tmp;
	while( n-- )
		tmp.push_back( v );
	splice( begin(), tmp );
}

template <typename T, class A>
template <typename In>
flist<T,A>::flist( In b, In e ) {
	flist tmp;
	while( b != e ) {
		tmp.push_back( *b );
		++b;
	}
	splice( begin(), tmp );
}

template <typename T, class A>
bool flist<T,A>::operator ==( const flist &rhs ) const
	{ return size() == rhs.size() && std::equal( begin(), end(), rhs.begin() ); }

template <typename T, class A>
bool flist<T,A>::operator <( const flist &rhs ) const
	{ return std::lexicographical_compare( begin(), end(), rhs.begin(), rhs.end() ); }
	
template <typename T, class A>
inline bool flist<T,A>::empty() const
	{ return Impl::empty(); }

template <typename T, class A>
typename flist<T,A>::size_type flist<T,A>::size() const
	{ return Impl::size(); }

template <typename T, class A>
inline typename flist<T,A>::size_type flist<T,A>::max_size() const
    { return Impl::max_size(); }

template <typename T, class A>
inline typename flist<T,A>::iterator flist<T,A>::begin()
	{ return Impl::begin(); }

template <typename T, class A>
inline typename flist<T,A>::const_iterator flist<T,A>::begin() const
	{ return Impl::begin(); }

template <typename T, class A>
inline typename flist<T,A>::iterator flist<T,A>::end()
	{ return Impl::end(); }

template <typename T, class A>
inline typename flist<T,A>::const_iterator flist<T,A>::end() const
	{ return Impl::end(); }

template <typename T, class A>
inline typename flist<T,A>::reverse_iterator flist<T,A>::rbegin()
	{ return reverse_iterator(end()); }

template <typename T, class A>
inline typename flist<T,A>::const_reverse_iterator flist<T,A>::rbegin() const
	{ return const_reverse_iterator(end()); }

template <typename T, class A>
inline typename flist<T,A>::reverse_iterator flist<T,A>::rend()
	{ return reverse_iterator(begin()); }

template <typename T, class A>
inline typename flist<T,A>::const_reverse_iterator flist<T,A>::rend() const
	{ return const_reverse_iterator(begin()); }

template <typename T, class A>
inline typename flist<T,A>::reference flist<T,A>::front()
	{ return *begin(); }

template <typename T, class A>
inline typename flist<T,A>::const_reference flist<T,A>::front() const
	{ return *begin(); }

template <typename T, class A>
inline typename flist<T,A>::reference flist<T,A>::back() {
	iterator tmp = end();
	return *--tmp;
}

template <typename T, class A>
inline typename flist<T,A>::const_reference flist<T,A>::back() const {
	const_iterator tmp = end();
	return *--tmp;
}

template <typename T, class A>
inline void flist<T,A>::push_front( const T &v )
	{ Impl::push_front( v ); }

template <typename T, class A>
inline void flist<T,A>::push_back( const T &v )
	{ Impl::push_back( v ); }

template <typename T, class A>
inline void flist<T,A>::pop_front()
	{ Impl::pop_front(); }

template <typename T, class A>
inline void flist<T,A>::pop_back()
	{ Impl::pop_back(); }

template <typename T, class A>
inline void flist<T,A>::clear()
	{ erase( begin(), end() ); }

template <typename T, class A>
inline typename flist<T,A>::iterator flist<T,A>::insert( iterator i, const value_type &v )
	{ return Impl::insert( i, v ); }

template <typename T, class A>
void flist<T,A>::insert( iterator i, size_type n, const value_type &v ) {
	flist tmp( n, v );
	splice( i, tmp );
}

template <typename T, class A>
template <typename In>
void flist<T,A>::insert( iterator i, In b, In e ) {
	flist tmp( b, e );
	splice( i, tmp );
}

template <typename T, class A>
inline typename flist<T,A>::iterator flist<T,A>::erase( iterator i )
	{ return Impl::erase( i ); }

template <typename T, class A>
typename flist<T,A>::iterator flist<T,A>::erase( iterator b, iterator e ) {
	flist tmp;
	return tmp.splice_before( tmp.begin(), *this, b, e ).second; // return end of deleted sequence
}

template <typename T, class A>
inline typename flist<T,A>::iterator flist<T,A>::insert_after( iterator i, const value_type &v ) {
	// Mimic some slist implementations that allow insert_after(end()) to
	// mean "insert(begin())."
	// However, note SGI documentation says i may not be end().
	return Impl::insert( (i == end()) ? begin() : ++i, v );
}

template <typename T, class A>
void flist<T,A>::insert_after( iterator i, size_type n, const value_type &v ) {
	flist tmp( n, v );
	splice( (i == end()) ? begin() : ++i, tmp );
}

template <typename T, class A>
template <typename In>
void flist<T,A>::insert_after( iterator i, In b, In e ) {
	flist tmp( b, e );
	splice( (i == end()) ? begin() : ++i, tmp );
}

template <typename T, class A>
inline typename flist<T,A>::iterator flist<T,A>::erase_after( iterator i ) {
	// Return for erase_afters is a new iterator that points to what i pointed to,
	// since i is invalidated after the erase.
	// Like some slist implementations, erase_after(end()) erases element at begin().
	// My guess is that it's a runtime error to erase_after the last (as
	// opposed to end()) element, but I can't find this documented anywhere.
	iterator next = Impl::erase( (i == end()) ? begin() : ++i );
	return (next == begin()) ? end() : --next;
}

template <typename T, class A>
typename flist<T,A>::iterator flist<T,A>::erase_after( iterator b, iterator e ) {
	flist tmp;
	iterator next = tmp.isplice( tmp.begin(), *this, (b == end()) ? begin() : ++b, e ).second;
	return (next == begin()) ? end() : --next;
}

template <typename T, class A>
inline typename flist<T,A>::splice_return_type flist<T,A>::splice_before( iterator at, flist &from, iterator b, iterator e )
	{ return Impl::ispliceImpl( at, from, b, e ); }

template <typename T, class A>
inline typename flist<T,A>::splice_return_type flist<T,A>::splice_before( iterator at, flist &from, iterator i ) {
	splice_return_type r;
	iterator tmp = i;  ++tmp;
	if( i == at || tmp == at ) { // 23.2.2.4:7
		r.first.first = at;
		r.first.second = tmp;
		r.second = tmp;
	}
	else
		r = Impl::ispliceImpl( at, from, i, tmp );
	return r;
}

template <typename T, class A>
inline void flist<T,A>::splice( iterator at, flist &from, iterator b, iterator e )
	{ Impl::spliceImpl( at, from, b, e ); }

template <typename T, class A>
inline void flist<T,A>::splice( iterator at, flist &from )
	{ Impl::spliceImpl( at, from, from.begin(), from.end() ); }

template <typename T, class A>
inline void flist<T,A>::splice( iterator at, flist &from, iterator i ) {
	iterator tmp = i;  ++tmp;
	if( i == at || tmp == at ) return; // 23.2.2.4:7
	Impl::spliceImpl( at, from, i, tmp );
}

template <typename T, class A>
inline typename flist<T,A>::splice_return_type flist<T,A>::splice_after( iterator at, flist &from, iterator b, iterator e )
	{ return Impl::ispliceImpl( (at == end()) ? begin() : ++at, from, b, e ); }

template <typename T, class A>
inline typename flist<T,A>::splice_return_type flist<T,A>::splice_after( iterator at, flist &from )
	{ return Impl::ispliceImpl( (at == end()) ? begin() : ++at, from, from.begin(), from.end() ); }

template <typename T, class A>
inline typename flist<T,A>::splice_return_type flist<T,A>::splice_after( iterator at, flist &from, iterator i ) {
	splice_return_type r;
	iterator tmp = i;  ++tmp;
	if( i == at || tmp == at ) { //XXXXX Check this!!! 23.2.2.4:7
		r.first.first = at;
		r.first.second = tmp;
		r.second = tmp;
	}
	else
		r = Impl::ispliceImpl( (at == end()) ? begin() : ++at, from, i, tmp );
	return r;
}

template <typename T, class A>
inline typename flist<T,A>::iterator flist<T,A>::previous( iterator i )
	{ return --i; }

template <typename T, class A>
inline typename flist<T,A>::const_iterator flist<T,A>::previous( const_iterator i ) const
	{ return --i; }

template <typename T, class A>
inline void flist<T,A>::reverse()
	{ Impl::reverse(); }

template <typename T, class A>
void flist<T,A>::swap( flist &that ) {
	flist tmp;
	tmp.splice( tmp.begin(), *this );
	splice( begin(), that );
	that.splice( that.begin(), tmp );
	// We don't bother swapping allocators.  If it mattered,
	// we couldn't splice in the first place.
}

template <typename T, class A>
void swap( flist<T,A> &a, flist<T,A> &b )
	{ a.swap( b ); }

template <typename T, class A>
flist<T,A> &flist<T,A>::operator =( const flist &that ) {
    flist temp( that );
    swap( temp );
    return *this;
}

template <typename T, class A>
void flist<T,A>::assign( size_type n, const T &v ) {
	iterator i = begin();
	while( n ) {
		if( i == end() )
			break;
		else {
			*i = v;
			++i;
			--n;
		}
	}
	if( i != end() )
		erase( i, end() );
	else {
		while( n-- )
			push_back( v );
	}
}

template <typename T, class A>
template <typename In>
void flist<T,A>::assign( In b, In e ) {
	iterator i = begin();
	while( b != e ) {
		if( i == end() )
			break;
		else {
			*i = *b;
			++i;
			++b;
		}
	}
	if( i != end() )
		erase( i, end() );
	else {
		while( b != e ) {
			push_back( *b );
			++b;
		}
	}
}

template <typename T, class A>
inline void flist<T,A>::resize( size_type n )
	{ resize( n, T() ); }

template <typename T, class A>
void flist<T,A>::resize( size_type n, const value_type &v ) {
	size_type s( size() );
	if( s < n ) {
		flist temp( n-s, v );
		splice( end(), temp );
	}
	else if( s > n ) {
		iterator e( end() );
		e.reverse();
		std::advance( e, s-n );
		e.reverse();
		erase( e, end() );
	}
}

//
// The implementations of the algorithms below are particularly instructive
// about the effects of iterator invalidation on the structure of an implementation.
// Note in particular the use of return values from operations that invalidate
// iterators, and what may appear to be failure to cache the values returned by
// begin() and end().
//

template <typename T, class A>
inline void flist<T,A>::remove( const T &v )
	{ remove_if( std::bind2nd( std::equal_to<value_type>(), v ) ); }

template <typename T, class A>
template <typename Pred>
void flist<T,A>::remove_if( Pred pred ) {
	iterator first = begin();
	while( first != end() ) {
		if( pred( *first ) )
			first = erase( first );
		else
			++first;
	}
}

template <typename T, class A>
inline void flist<T,A>::unique()
	{ unique( std::equal_to<value_type>() ); }

template <typename T, class A>
template <typename BinaryPred>
void flist<T,A>::unique( BinaryPred eq ) {
	iterator first = begin();
	iterator last = end();
	if( first == last )
		return;
	iterator next = first; ++next;
	while( next != last ) {
		if( eq( *first, *next ) ) {
			first = next = erase( next );
			--first;
		}
		else {
			first = next;
			++next;
		}
	}
}

template <typename T, class A>
inline void flist<T,A>::merge( flist &that )
	{ merge( that, std::less<value_type>() ); }

template <typename T, class A>
template <typename Comp>
void flist<T,A>::merge( flist &that, Comp comp ) {
	if( this == &that )
		return;
	iterator first1 = begin();
	iterator first2 = that.begin();
	while( first1 != end() && first2 != that.end() ) {
		if( comp( *first2, *first1 ) ) {
			iterator i = first2;
			while( ++i != that.end() && comp( *i, *first1 ) ) {}
			splice_return_type r = splice_before( first1, that, first2, i );
			first1 = r.first.second;
			first2 = r.second;
		}
		else
			++first1;
	}
	if( first2 != that.end() )
		splice( end(), that, first2, that.end() );
}

template <typename T, class A>
inline void flist<T,A>::sort()
	{ sort( std::less<value_type>() ); }

template <typename T, class A>
template <typename Comp>
void flist<T,A>::sort( Comp comp ) {
	// This implementation of sort comes from the SGI list::sort, with
	// only small changes.  We can probably do better.
	// Copyright (c) 1994 Hewlett-Packard Company
	// Copyright (c) 1996,1997 Silicon Graphics Computer Systems, Inc.
	if( empty() )
		return;
	iterator tmp = begin();
	if( ++tmp == end() )
		return;
	
	// Otherwise, sort!
	flist carry;
	flist counter[64]; // I have no idea why we're using 64...
	int fill = 0;
	while( !empty() ) {
		carry.splice( carry.begin(), *this, begin() );
		int i = 0;
		while( i < fill && !counter[i].empty() ) {
			counter[i].merge( carry, comp );
			carry.swap( counter[i++] );
		}
		carry.swap( counter[i] );         
		if( i == fill ) ++fill;
	} 

	for( int i = 1; i < fill; ++i ) 
		counter[i].merge( counter[i-1], comp );
	swap( counter[fill-1] );
}

//
//	Iterators over the list
//
// Note that this is not an STL "node-based" container, since an inserted or deleted
// node affects iterators to adjacent nodes.  (Note the caution exercised in the
// implementations of the algorithms above.)
//
// Note also that swapping and assignment may also invalidate iterators.
//
// The container is deque-like in that pointers and references to adjacent nodes remain
// unaffected even though iterators are invalidated.
//
// Conversion from iterator to const_iterator is accomplished by lossless slicing.
//
// Iterator operations are nothrow.
//

//
// Implementation class for code factoring.
//
class IterImpl {
  public:
	typedef ListImplBase::NodePtr NodePtr;
	IterImpl( NodePtr c, NodePtr p );
	IterImpl();
	IterImpl &operator ++();
	IterImpl operator ++(int);
	IterImpl &operator --();
	IterImpl operator --(int);
	IterImpl &reverse();
	// We'll let the compiler write these operations for us:
	// IterImpl &IterImpl( const IterImpl & );
	// IterImpl &operator =( const IterImpl & );
	// ~IterImpl();
	NodePtr curr_;
  	NodePtr prev_;
};

inline IterImpl::IterImpl( NodePtr c, NodePtr p )
	: curr_(c), prev_(p) {}

inline IterImpl::IterImpl()
	// Note this ctor must be defined even though it's a no-op.
	{}

inline IterImpl &IterImpl::operator ++() {
	NodePtr tmp = curr_;
	curr_ = toptr<NodePtr>(curr_->ptr_ ^ tobits(prev_));
	prev_ = tmp;
	return *this;
}

IterImpl IterImpl::operator ++(int) {
	IterImpl tmp( *this );
	++*this;
	return tmp;
}

inline IterImpl &IterImpl::operator --() {
	// Probably not the best implementation, but too much
	// fun to pass up!
	reverse();
	++*this;
	reverse();
	return *this;
}

IterImpl IterImpl::operator --(int) {
	IterImpl tmp( *this );
	--*this;
	return tmp;
}

inline IterImpl &IterImpl::reverse() {
	// Reversing is just changing your mind about what the previous node is.  Fickle.
	prev_ = toptr<NodePtr>(curr_->ptr_ ^ tobits(prev_));
	return *this;
}

template <class ListHandle>
class ConstListIter : public IterImpl { // Note intentional avoidance of std::iterator base,
										// due to translation problems on some compilers
  public:
  	typedef typename std::bidirectional_iterator_tag iterator_category;
  	typedef typename ListHandle::value_type value_type;
  	typedef typename ListHandle::difference_type difference_type;
  	typedef typename ListHandle::const_pointer pointer;
  	typedef typename ListHandle::const_reference reference;
  	
  	typedef typename ListHandle::NodePtr NodePtr;
  	typedef typename ListHandle::DerivedNodePtr DerivedNodePtr;
  	typedef typename ListHandle::ListEl ListEl;
  	
  	typedef IterImpl Base;
  	
	ConstListIter( NodePtr current, NodePtr previous )
		: IterImpl( current, previous ) {}
	ConstListIter()
		{}
	ConstListIter &operator ++()
		{ return static_cast<ConstListIter &>(Base::operator ++()); }
	ConstListIter operator ++(int)
		{ Base tmp = Base::operator ++(0); return static_cast<ConstListIter &>(tmp); }
	ConstListIter &operator --()
		{ return static_cast<ConstListIter &>(Base::operator --()); }
	ConstListIter operator --(int)
		{ Base tmp = Base::operator --(0); return static_cast<ConstListIter &>(tmp); }
	ConstListIter &reverse()
		{ return static_cast<ConstListIter &>(Base::reverse()); }
	
	value_type &operator *();
	value_type *operator ->();
	
	// Note use of "making new friends" idiom to get proper argument conversions between
	// const and non-const iterators for this class template.
	friend bool operator ==( const ConstListIter &lhs, const ConstListIter &rhs )
		{ return lhs.curr_ == rhs.curr_; }
	friend bool operator !=( const ConstListIter &lhs, const ConstListIter &rhs )
		{ return !(lhs == rhs); }
};

template <class ListHandle>
inline typename ConstListIter<ListHandle>::value_type &ConstListIter<ListHandle>::operator *()
	{ return static_cast<DerivedNodePtr>(curr_)->el_; }

template <class ListHandle>
inline typename ConstListIter<ListHandle>::value_type *ConstListIter<ListHandle>::operator ->()
	{ return &operator *(); }

template <class ListHandle>
class ListIter : public ConstListIter<ListHandle> {
  public:
	typedef typename ListHandle::pointer pointer; // hide inherited typedefs
  	typedef typename ListHandle::reference reference;
  		
  	typedef ConstListIter<ListHandle> Base;
  	typedef typename Base::NodePtr NodePtr;
  	typedef typename Base::iterator_category iterator_category;
  	typedef typename Base::value_type value_type;
  	typedef typename Base::difference_type difference_type;
  	
  	ListIter( NodePtr current, NodePtr previous )
  		: ConstListIter<ListHandle>( current, previous ) {}
	ListIter()
		{}
	ListIter &operator ++()
		{ return static_cast<ListIter &>(Base::operator ++()); }
	ListIter operator ++(int)
		{ Base tmp = Base::operator ++(0); return static_cast<ListIter &>(tmp); }
	ListIter &operator --()
		{ return static_cast<ListIter &>(Base::operator --()); }
	ListIter operator --(int)
		{ Base tmp = Base::operator ++(0); return static_cast<ListIter &>(tmp); }
	ListIter &reverse()
		{ return static_cast<ListIter &>(Base::reverse()); }
};

#ifndef NDEBUG

template <typename T, class A> // for debugging only
void ListImpl<T,A>::print( const char *title ) const {
	using namespace std;
	
	cout << title << ":\tsize = " << size() << "\telements = ";
	const_iterator i = begin();
	while( i != end() ) {
		value_type tmp = *i;
		cout << ' ' << tmp;
		++i;
	}
	if( i.curr_ != &clasp_ )
		cout << " no clasp at end!";
	else
		cout << " CLASP";
	cout << endl;
}

template <typename T, class A>
inline void flist<T,A>::print( const char *title ) const
	{ Impl::print( title ); }

#endif

} // Tyr

#endif