/*
	File:		List.h

	Contains:	Primitive linked list class

	Written by:	Richard Rodseth

	Copyright:	c 1993 by Apple Computer, Inc., all rights reserved.

	Change History (most recent first):

		 <1>	10/24/94	jpa		first checked in
		 <5>	 9/30/94	RR		#1167950. Added RemoveCurrent, fNext and
									fPrevious to LinkedListIterator
		 <4>	  6/9/94	RR		Remove ASLM stuff
		 <2>	 5/10/94	RR		Removed ASLM_COMPATIBLE and CDECL
		 <1>	  5/5/94	CG		first checked in
		<10>	 3/15/94	MB		Changes to support SCpp/ASLM builds,
									#1150864.
		 <9>	  2/7/94	JA		Tiger Team Makeover. Added some inline
									helpers to eliminate cfront warnings in
									const methods.
		 <8>	 1/31/94	JA		Added more methods to Link and LinkedList.
									Inlined some getters/setters.
		 <7>	10/14/93	RR		Added fSeed to detect when iterator is out of sync
		 <6>	 10/6/93	PH		Make destructor virtual
		 <5>	 8/13/93	RR		Added DeleteLinks method
		 <5>	 8/13/93	RR		Added DeleteLinks method
		 <4>	  8/9/93	NP		Added class id string.
		 <3>	  4/27/93	RCR		Rename Includes
		 <2>	  4/27/93	RCR		Include ODTypes and use ODBoolean and kODNULL
		 <1>	  4/27/93	RCR		first checked in
	To Do:
*/

#ifndef _LIST_
#define _LIST_

#ifndef _ODTYPES_
#include "ODTypes.h"
#endif


//=====================================================================================
// Theory of Operation
//=====================================================================================

/*

 Note: These classes are private to the implementation. They are not available
 to part handlers.

 Note: These are primitive classes for implementing higher-level collections
 For example, to create a FrameList class, subclass Link to add a field to
 store the frame. The FrameList class would use a LinkedList in its implementation
 and would manufacture the Link objects internally.
 
 Note: SimpleLinkedList is a list without a "seed" for consistency checking.
 It cannot be iterated over.

*/

//==============================================================================
// Constants
//==============================================================================

//==============================================================================
// Scalar Types
//==============================================================================

//==============================================================================
// Classes defined in this interface
//==============================================================================

class ODExport Link;
class ODExport LinkedList;
class ODExport LinkedListIterator;

//==============================================================================
// Classes used by this interface
//==============================================================================


//==============================================================================
// Link
//==============================================================================

class  ODExport Link {
	public:
	
		Link();
		
		Link(Link* next, Link* previous);
		
		Link( const Link& );
		
		virtual ~Link();
		
		Link* GetNext() const					{return fNext;}
		
		Link* GetPrevious() const				{return fPrevious;}
	
	// The following operations are provided for efficiency, but DO NOT USE THEM
	// if there are any iterators active on a list. These operations don't bump
	// the list's fSeed and the iterators will not be able to detect that they
	// are out of sync!
		
		void  Remove( );
		
		void  AddBefore( Link *aLink );
		
		void  AddAfter( Link *aLink );
	
  //private-by-convention:
  		
		void  SetNext(Link* aLink)				{fNext = aLink;}
		
		void  SetPrevious(Link* aLink)			{fPrevious = aLink;}

	private:
	
		Link*		fNext;
		Link*		fPrevious;
};


//==============================================================================
// LinkedList
//==============================================================================


class ODExport LinkedList {

	public:
	
	  	LinkedList();
	  	
	  	~LinkedList();
	  	
	  	ODBoolean		IsEmpty( )										const;
	  	
	  	ODULong			Count()											const;
	  	
	  	ODBoolean		Includes( const Link* )							const;
	  	
	  	void			Remove(Link&);
	  	
	  	void			RemoveAll();

	  	void			DeleteAllLinks();
	  	
	  	Link*			RemoveFirst();
	  	
	  	Link*			RemoveLast();
	  	
	  	void			AddBefore(Link& existing, Link* link);
	  	
	  	void			AddAfter(Link& existing, Link* link);
	  	
	  	void			AddFirst(Link* link);
	  	
	  	void			AddLast(Link* link);
	  	
	  	void			AddLast( LinkedList &list );
	  	
	  	void			AddLastUnique( LinkedList &list );
	  	
	  	Link*			After(const Link& link)							const;
	  	
	  	Link* 			Before(const Link& link)						const;
	  	
	  	Link*			First()											const;
	  	
	  	Link* 			Last()											const;

protected:

		Link			fSentinel;	// Marks the head & tail
		ODULong			fSeed;		// Used to detect out-of-sync iterators
		
		Link*			GetSentinel( )
												{return &fSentinel;}
		const Link*		GetSentinel( )									const
												{return &fSentinel;}
		ODBoolean		IsSentinel( const Link* link )					const
												{return link==this->GetSentinel();}
		ODBoolean		NotSentinel( const Link* link )					const
												{return link!=this->GetSentinel();}

private:			  	
		friend class LinkedListIterator;
};


//=====================================================================================
// LinkedListIterator
//=====================================================================================

class ODExport  LinkedListIterator {

	public:
	
		LinkedListIterator(LinkedList*	list);
		
		~LinkedListIterator();
		
		Link*			First();
		
		Link*			Next();
		
		Link*			Last();
		
		Link*			Previous();

		Link*			Current();

		ODBoolean 		IsNotComplete();
		
		void			RemoveCurrent();
		
	private:
	
		LinkedList*		fList;
		Link*			fCurrent;
		Link*			fNext;		// Used only when deleting while iterating
		Link* 			fPrevious;	// Used only when deleting while iterating
		Link*			fSentinel;
		ODULong			fSeed;		// Used to detect out-of-sync iterators
		
};


#endif // _LIST_
