// list.h //	Data structures to manage LISP-like lists.  ////      As in LISP, a list can contain any type of data structure//	as an item on the list: thread control blocks, //	pending interrupts, etc.  That is why each item is a "void *",//	or in other words, a "pointers to anything".//// Copyright (c) 1992-1993 The Regents of the University of California.// All rights reserved.  See copyright.h for copyright notice and limitation // of liability and disclaimer of warranty provisions.#ifndef LIST_H#define LIST_H#include "copyright.h"#include "utility.h"// The following class defines a "list element" -- which is// used to keep track of one item on a list.  It is equivalent to a// LISP cell, with a "car" ("next") pointing to the next element on the list,// and a "cdr" ("item") pointing to the item on the list.//// Internal data structures kept public so that List operations can// access them directly.template< class T >class ListElement {   public:     ListElement(T itemPtr, int sortKey);	// initialize a list element     ListElement *next;		// next element on list, 				// NULL if this is the last     int key;		    	// priority, for a sorted list     T item; 	    		// item on the list};// The following class defines a "list" -- a singly linked list of// list elements, each of which points to a single item on the list.//// By using the "Sorted" functions, the list can be kept in sorted// in increasing order by "key" in ListElement.template< class T >class List {  public:    List();			// initialize the list    ~List();			// de-allocate the list    void Prepend(T item); 	// Put item at the beginning of the list    void Append(T item); 	// Put item at the end of the list    T Remove(); 	 	// Take item off the front of the list    T Peek();			// Return but don't remove front of list    void Mapcar(VoidFunctionPtr func);	// Apply "func" to every element 					// on the list    bool IsEmpty();		// is the list empty?         // Routines to put/get items on/off list in order (sorted by key)    void SortedInsert(T item, int sortKey);	// Put item into list    T SortedRemove(int *keyPtr); 	  	// Remove first item from list    T SortedPeek(int *keyPtr);			// Return first item from list    T IndexPeek(int _index);			// Return item index from list    T IndexRemove(int _index);			// Remove item index from list    void SetAllKeys(int value);			// Sets all keys in list to value   private:    ListElement< T > *first;  	// Head of the list, NULL if list is empty    ListElement< T > *last;		// Last element of list};#include "list.cpp"#endif // LIST_H