// list.cc 

//

//     	Routines to manage a singly-linked list of "things".

//

// 	A "ListElement" is allocated for each item to be put on the

//	list; it is de-allocated when the item is removed. This means

//      we don't need to keep a "next" pointer in every object we

//      want to put on a list.

// 

//     	NOTE: Mutual exclusion must be provided by the caller.

//  	If you want a synchronized list, you must use the routines 

//	in synchlist.cc.

//

// 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.

#include "list.h"

//----------------------------------------------------------------------

// ListElement::ListElement

// 	Initialize a list element, so it can be added somewhere on a list.

//

//	"itemPtr" is the item to be put on the list.  It can be a pointer

//		to anything.

//	"sortKey" is the priority of the item, if any.

//----------------------------------------------------------------------

ListElement::ListElement(void *itemPtr, int sortKey)

{

     item = itemPtr;

     key = sortKey;

     next = NULL;	// assume we'll put it at the end of the list 

     previous = NULL;

}

//----------------------------------------------------------------------

// List::List

//	Initialize a list, empty to start with.

//	Elements can now be added to the list.

//----------------------------------------------------------------------

List::List()

{ 

    first = last = NULL;

    length = 0;

}

//----------------------------------------------------------------------

// List::~List

//	Prepare a list for deallocation.  If the list still contains any 

//	ListElements, de-allocate them.  However, note that we do *not*

//	de-allocate the "items" on the list -- this module allocates

//	and de-allocates the ListElements to keep track of each item,

//	but a given item may be on multiple lists, so we can't

//	de-allocate them here.

//----------------------------------------------------------------------

List::~List()

{ 

    while (Remove() != NULL)

	;	 // delete all the list elements

}

//----------------------------------------------------------------------

// List::Append

//      Append an "item" to the end of the list.

//      

//	Allocate a ListElement to keep track of the item.

//      If the list is empty, then this will be the only element.

//	Otherwise, put it at the end.

//

//	"item" is the thing to put on the list, it can be a pointer to 

//		anything.

//----------------------------------------------------------------------

void

List::Append(void *item)

{

    ListElement *element = new ListElement(item, 0);

    if (IsEmpty()) {		// list is empty

	first = element;

	last = element;

    } else {			// else put it after last

	last->next = element;

	element->previous = last;

	last = element;

    }

    length++;

}

//----------------------------------------------------------------------

// List::Prepend

//      Put an "item" on the front of the list.

//      

//	Allocate a ListElement to keep track of the item.

//      If the list is empty, then this will be the only element.

//	Otherwise, put it at the beginning.

//

//	"item" is the thing to put on the list, it can be a pointer to 

//		anything.

//----------------------------------------------------------------------

void

List::Prepend(void *item)

{

    ListElement *element = new ListElement(item, 0);

    if (IsEmpty()) {		// list is empty

	first = element;

	last = element;

    } else {			// else put it before first

	element->next = first;

	first->previous = element;

	first = element;

    }

    length++;

}

//----------------------------------------------------------------------

// List::Remove

//      Remove the first "item" from the front of the list.

// 

// Returns:

//	Pointer to removed item, NULL if nothing on the list.

//----------------------------------------------------------------------

void *

List::Remove()

{

    return SortedRemove(NULL);  // Same as SortedRemove, but ignore the key

    length--;

}

//----------------------------------------------------------------------

// List::Mapcar

//	Apply a function to each item on the list, by walking through  

//	the list, one element at a time.

//

//	Unlike LISP, this mapcar does not return anything!

//

//	"func" is the procedure to apply to each element of the list.

//----------------------------------------------------------------------

void

List::Mapcar(VoidFunctionPtr func)

{

    for (ListElement *ptr = first; ptr != NULL; ptr = ptr->next) {

       (*func)((int)ptr->item);

    }

}

//----------------------------------------------------------------------

// List::IsEmpty

//      Returns TRUE if the list is empty (has no items).

//----------------------------------------------------------------------

bool

List::IsEmpty() 

{ 

    if (first == NULL)

        return TRUE;

    else

	return FALSE; 

}

//----------------------------------------------------------------------

// List::SortedInsert

//      Insert an "item" into a list, so that the list elements are

//	sorted in increasing order by "sortKey".

//      

//	Allocate a ListElement to keep track of the item.

//      If the list is empty, then this will be the only element.

//	Otherwise, walk through the list, one element at a time,

//	to find where the new item should be placed.

//

//	"item" is the thing to put on the list, it can be a pointer to 

//		anything.

//	"sortKey" is the priority of the item.

//----------------------------------------------------------------------

void

List::SortedInsert(void *item, int sortKey)

{

    ListElement *element = new ListElement(item, sortKey);

    ListElement *ptr;		// keep track

    if (IsEmpty()) {	// if list is empty, put

        first = element;

        last = element;

    } else if (sortKey < first->key) {	

		// item goes on front of list

	element->next = first;

	first->previous = element;

	first = element;

    } else {		// look for first elt in list bigger than item

        for (ptr = first; ptr->next != NULL; ptr = ptr->next) {

            if (sortKey < ptr->next->key) {

		element->next = ptr->next;

		element->previous = ptr;

		ptr->next->previous = element;

	        ptr->next = element;

		return;

	    }

	}

	last->next = element;		// item goes at end of list

	element->previous = last;

	last = element;

    }

    length++;

}

//----------------------------------------------------------------------

// List::SortedRemove

//      Remove the first "item" from the front of a sorted list.

// 

// Returns:

//	Pointer to removed item, NULL if nothing on the list.

//	Sets *keyPtr to the priority value of the removed item

//	(this is needed by interrupt.cc, for instance).

//

//	"keyPtr" is a pointer to the location in which to store the 

//  priority of the removed item.

//----------------------------------------------------------------------

void *

List::SortedRemove(int *keyPtr)

{

    ListElement *element = first;

    void *thing;

    if (IsEmpty()) 

	return NULL;

    thing = first->item;

    if (first == last) {	// list had one item, now has none 

        first = NULL;

	last = NULL;

    } else {

        first = element->next;

	if (first != NULL)

	  first->previous = NULL;

    }

    if (keyPtr != NULL)

        *keyPtr = element->key;

    delete element;

    length--;

    return thing;

}

void List::insertAfter(ListElement * listEl, void *item)   

 // insert a new item after this one

{

    ListElement *newElement = new ListElement(item, 0);

    newElement->next = listEl->next;

    newElement->previous = listEl;

    listEl->next = newElement;

    if (last == listEl)

      last = newElement;

    length++;

}

void List::insertBefore(ListElement * listEl, void *item)   

 // insert a new item before this one

{

    ListElement *newElement = new ListElement(item, 0);

    newElement->next = listEl;

    newElement->previous = listEl->previous;

    listEl->previous = newElement;

    if (first == listEl)

      first = newElement;

    length++;

}

void List::removeAt(ListElement * listEl)   

     // removes listEl from the list. Do not delete it from memory

{

    if(first != listEl)

      (listEl->previous)->next = listEl->next;

    else 

      first = listEl->next;

    if(last != listEl)

      (listEl->next)->previous = listEl->previous;

    else 

      last = listEl->previous;

//    delete listEl;

    length --;

}