#pragma once

#include "bits/collection.hfa"

forall( dtype T | { T *& Next ( T * ); } ) {
	struct Queue {
		inline Collection;								// Plan 9 inheritance
		T * last;										// last element, or 0 if queue is empty.
	};

	inline {
		// wrappers to make Collection have T
		T & head( Queue(T) & q ) with( q ) {
			return *(T *)head( (Collection &)q );
		} // post: empty() & head() == 0 | !empty() & head() in *q

		void ?{}( Queue(T) &, const Queue(T) & ) = void; // no copy
		Queue(T) & ?=?( const Queue(T) & ) = void;		// no assignment

		void ?{}( Queue(T) & q ) with( q ) {
			((Collection &)q){};
			last = 0p;
		} // post: empty()

		T & tail( Queue(T) & q ) with( q ) {
			return *last;
		}

		T * succ( Queue(T) & q, T * n ) with( q ) {		// pre: *n in *q
			#ifdef __CFA_DEBUG__
			if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
			#endif // __CFA_DEBUG__
			return (Next( n ) == n) ? 0p : Next( n );
		} // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q

		T & addHead( Queue(T) & q, T & n ) with( q ) {
			#ifdef __CFA_DEBUG__
			if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n );
			#endif // __CFA_DEBUG__
			if ( last ) {
				Next( &n ) = &head( q );
				q.root = &n;
			} else {
				root = last = &n;
				Next( &n ) = &n;						// last node points to itself
			}
			return n;
		}

		T & addTail( Queue(T) & q, T & n ) with( q ) {
			#ifdef __CFA_DEBUG__
			if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
			#endif // __CFA_DEBUG__
			if ( last ) Next( last ) = &n;
			else root = &n;
			last = &n;
			Next( &n ) = &n;							// last node points to itself
			return n;
		}

		T & add( Queue(T) & q, T & n ) with( q ) {
			return addTail( q, n );
		}

		T & dropHead( Queue(T) & q ) with( q ) {
			T & t = head( q );
			if ( root ) {
				root = Next( (T *)root );
				if ( &head( q ) == &t ) {
					root = last = 0p;					// only one element
				}
				Next( &t ) = 0p;
			}
			return t;
		}

		T & drop( Queue(T) & q ) with( q ) {
			return dropHead( q );
		}

		T & remove( Queue(T) & q, T & n ) with( q ) {	// O(n)
			#ifdef __CFA_DEBUG__
			if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
			#endif // __CFA_DEBUG__
			T * prev = 0p;
			T * curr = (T *)root;
			for ( ;; ) {
				if ( &n == curr ) {						// found => remove
					if ( (T *)root == &n ) {
						dropHead( q );
					} else if ( last == &n ) {
						last = prev;
						Next( last ) = last;
					} else {
						Next( prev ) = Next( curr );
					}
					Next( &n ) = 0p;
					break;
				}
				// not found => error
				#ifdef __CFA_DEBUG__
				if ( curr == last ) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n );
				#endif // __CFA_DEBUG__
				prev = curr;
				curr = Next( curr );
			}
			return n;
		} // post: ! listed( n )

		T & dropTail( Queue(T) & q ) with( q ) { // O(n)
			T & n = tail( q );
			return &n ? remove( q, n ), n : *0p;
		}

		// Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
		void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
			if ( empty( from ) ) return;				// "from" list empty ?
			if ( empty( q ) ) {							// "to" list empty ?
				root = from.root;
			} else {									// "to" list not empty
				Next( last ) = &head( from );
			}
			last = from.last;
			from.root = from.last = 0p;					// mark "from" list empty
		}

		// Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
		// Node "n" must be in the "from" list.
		void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) {
			#ifdef __CFA_DEBUG__
			if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n );
			#endif // __CFA_DEBUG__
			Queue(T) to;
			to.root = from.root;						// start of "to" list
			to.last = &n;								// end of "to" list
			from.root = Next( &n );						// start of "from" list
			if ( &n == &head( from ) ) {				// last node in list ?
				from.root = from.last = 0p;				// mark "from" list empty
			} else {
				Next( &n ) = &n;						// fix end of "to" list
			}
			transfer( q, to );
		}
	} // distribution
} // distribution

forall( dtype T | { T *& Next ( T * ); } ) {
	struct QueueIter {
		inline ColIter;									// Plan 9 inheritance
	};	

	inline {
		void ?{}( QueueIter(T) & qi ) with( qi ) {
			((ColIter &)qi){};
		} // post: curr == 0p

		// create an iterator active in Queue q
		void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
			curr = &head( q );
		} // post: curr = {e in q}

		void ?{}( QueueIter(T) & qi, T & start ) with( qi ) {
			curr = &start;
		} // post: curr = {e in q}

		// make existing iterator active in Queue q
		void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
			curr = &head( q );
		} // post: curr = {e in q}

		bool ?>>?( QueueIter(T) & qi, T && tp ) with( qi ) {
			if ( curr ) {
				&tp = Curr( qi );
				T * n = Next( Curr( qi ) );
				curr = (n == Curr( qi ) ) ? 0p : n;
			} else &tp = 0p;
			return &tp != 0p;
		}
		// post: elts == null & !operator>>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)
	} // distribution
} // distribution