// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Patricia K. Fasel (Los Alamos Nat. Lab.), Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 


#define List_CC
#include <iostream.h>


#ifdef STK_LISTS

template <class Item>
void
List<Item>::createProtectedHeader()
{
	Tcl_HashEntry *p;
	int not_found;
	SCM *z = new SCM (STk_make_CXXwrapper(Wrapper<List<Item> >::type, 
	                            Wrapper<List<Item> >::name, 
				    (void *) this, LINK_DYNAMIC));
	STk_gc_protect(z);
        p = Tcl_CreateHashEntry(&listTable, (char*) this, &not_found);
	Tcl_SetHashValue(p, (ClientData) *z);
}

template <class Item>
PRIMITIVE
List<Item>::retrieveHeader()
{
        SCM z;
        Tcl_HashEntry *entry;
        entry = Tcl_FindHashEntry(&listTable, (char*)this);
        if (entry) {
        	z = (SCM) Tcl_GetHashValue(entry);
        	return z;
	}
	return NIL;
}

template <class Item>
PRIMITIVE
List<Item>::unprotectHeader()
{
        SCM z;
        Tcl_HashEntry *entry;
        entry = Tcl_FindHashEntry(&listTable, (char*)this);
        if (entry) {
        	z = (SCM) Tcl_GetHashValue(entry);
        	STk_gc_unprotect(z);
		Tcl_DeleteHashEntry(entry);
        	return z;
	}
	return NIL;
}

template <class Item>
int
List<Item>::listEnd(const ListNode<Item>* n) const 
{
	return ((n==0) || (TYPEP((SCM)n,tc_nil)));
}

template <class Item>
int
List<Item>::listEnd(const ListContainerNode<Item>* n) const 
{
	return ((n==0) || (TYPEP((SCM)n->getNode(),tc_nil)));
}

//
// constructor(implicit)
//
template <class Item>
List<Item>::List() : _first( (ListNode<Item> *)NIL), 	// NIL: see stk.h
		     _current_node(new ListContainerNode<Item>())
{
	//cout << "STk List()" << endl;
	createProtectedHeader();
}

template <class Item>
List<Item>::List(const List<Item>& copy_list) :
                        _first( (ListNode<Item> *)NIL),
		        _current_node(new ListContainerNode<Item>())
{
    //cout << "STk List(List)" << endl;
    Iterator<Item> get_item(&copy_list);
    Item item;
    while (get_item(item))
        append(item);
    createProtectedHeader();
}

template <class Item>
List<Item>::List(const Container<Item>& c) :
                        _first( (ListNode<Item> *) NIL),
		        _current_node(new ListContainerNode<Item>())
{
    //cout << "STk List(Container)" << endl;
    Iterator<Item> get_item(&c);
    Item item;
    while (get_item(item))
        append(item);
    createProtectedHeader();
}

template <class Item>
void
List<Item>::clear()
{
    //extern SCM my_examine_tree(SCM);
    //ListNode<Item>* node = _first;
    //cout << "clear(): " << endl;
    //my_examine_tree( (SCM) node);
    //while (!listEnd(node)) {
    //    ListNode<Item>* next_node = node->next();
    //    delete node;
    //    node = next_node;
    //}

    SCM inst = unprotectHeader();
    if (inst != NIL) {
	SCM wrap = STk_slot_ref(inst, val_scm);
	my_STk_release_cell(wrap);
	my_STk_release_cell(inst);
    }
    _first = (ListNode<Item> *) NIL;
}

#else

template <class Item>
int
List<Item>::listEnd(const ListNode<Item>* n) const 
{
	return n==0;
}

template <class Item>
int
List<Item>::listEnd(const ListContainerNode<Item>* n) const 
{
	return (n==0) || (n->getNode()==0);
}

//
// constructor(implicit)
//
template <class Item>
List<Item>::List() : _first(0),
		     _current_node(new ListContainerNode<Item>())
{
	//cout << "standard List()" << endl;
}


//
// copy constructor
//
template <class Item>
List<Item>::List(const List<Item>& copy_list) :
                        _first(0),
		        _current_node(new ListContainerNode<Item>())
{
    //cout << "standard List(List)" << endl;
    Iterator<Item> get_item(&copy_list);
    Item item;
    while (get_item(item))
        append(item);
}

template <class Item>
List<Item>::List(const Container<Item>& c) :
                        _first(0),
		        _current_node(new ListContainerNode<Item>())
{
    //cout << "standard List(Container)" << endl;
    Iterator<Item> get_item(&c);
    Item item;
    while (get_item(item))
        append(item);
}

template <class Item>
void
List<Item>::clear()
{
    ListNode<Item>* node = _first;
    while (!listEnd(node)) {
        ListNode<Item>* next_node = node->next();
        delete node; 
        node = next_node;
    }
    _first = 0;
}

#endif


template <class Item>
ListNode<Item>*
List<Item>::cn2ListNode(const ContainerNode* n) const
{
	return ((ListContainerNode<Item>*)n)->getNode();
}

template <class Item>
ContainerNode*
List<Item>::ListNode2cn(ListNode<Item>* n) const
{
	_current_node->_node = n;
	return _current_node;
}


//
// destructor
//
template <class Item>
List<Item>::~List()
{
    clear();
}

template <class Item>
Item
List<Item>::info(const ContainerNode *node) const
{
	ListContainerNode<Item>* cn = (ListContainerNode<Item>*) node;
        if (!listEnd(cn))
                return  * (Item *) cn->info();
	static Item i;
        return i;
}


//
// copy one list to another
//
template <class Item>
List<Item>&
List<Item>::operator=(const List<Item>& copy_list)
{
    if (this != &copy_list) {
        clear();
        Iterator<Item> get_list(&copy_list);
        Item item;
        while (get_list(item))
            append(item);
    }
    return(*this);
}

//
// find the length of the list - note: a count is *not* kept 
// to make the list more scheme-like  STk can do list surgery
//
template <class Item>
int
List<Item>::size() const
{
    Iterator<Item> get_next(this);
    Item i;
    int count = 0;
    while (get_next(i))
	count++;
    return count;
}

//
// return last item   (no tail pointer to save space;  also more scheme-like)
//
template <class Item>
Item
List<Item>::last() const
{
    if (listEnd(_first)) {
	warning("no last on empty list");
        static Item it;
	return it;  // empty_data;
    }
    ListNode<Item>* node;
    for (node=_first; !listEnd(node->next());node=node->next());
    return node->getItem();
}

//
// insert item into beginning of list
//
template <class Item>
ContainerNode*
List<Item>::prepend(Item passed_item)
{
    ListNode<Item>* node = new ListNode<Item>(passed_item);
    node->setNext(_first);
    _first = node;

    return ListNode2cn(node);
}

//
// append item to back of list
//
template <class Item>
ContainerNode*
List<Item>::append(Item passed_item)
{
    ListNode<Item>* newNode = new ListNode<Item>(passed_item);
    if (listEnd(_first)) {
        newNode->setNext(_first);	// _first is an object with STk
        _first = newNode;
    } else {
	ListNode<Item> *node;
	for (node = _first; !listEnd(node->next()); node = node->next());
	newNode->setNext(node->next());
	node->setNext(newNode);
	if (!listEnd(newNode->next()))
		error("List::append: error with listEnd");
    }
    return ListNode2cn(newNode);
}

//
// insert item into beginning of list 
//
template <class Item>
ContainerNode*
List<Item>::insert(Item passed_item)
{
    return prepend(passed_item);
}

//
// insert item before the node
//
template <class Item>
ContainerNode*
List<Item>::insertBefore(Item passed_item, ContainerNode * in_node)
{
    ListNode<Item>* passed_node = cn2ListNode(in_node);
    if (listEnd(passed_node))
    {
	warning("List::insertBefore(): can't insert before null pointer");
        return ListNode2cn(passed_node);
    }

    ListNode<Item>* before_node = (ListNode<Item>*) passed_node;
    ListNode<Item>* node = new ListNode<Item>(passed_item);
   
    if ((_first == before_node) || (listEnd(_first)))  {
      if (listEnd(_first))   
		warning("List<Item>::insertBefore() called on empty list");
      if (listEnd(before_node)) {
		warning("List<Item>::insertBefore(it,NULL), returning ");
    		return ListNode2cn(before_node);
      }
      node->setNext(_first);
      _first = node; 
      return ListNode2cn(node);
    }
    ListNode<Item> *n;
    for (n = _first; !listEnd(n->next()); n = n->next()) 
	if (n->next() == before_node)
	    break;
    node->setNext(n->next());
    n->setNext(node);
    return ListNode2cn(node);
}


template <class Item>
ContainerNode*
List<Item>::insertAfter(Item passed_item, ContainerNode * in_node)
{
    ListNode<Item>* passed_node = cn2ListNode(in_node);
    if (listEnd(passed_node)) 
    {
	warning("can't insert after a null pointer");
        return ListNode2cn(passed_node);
    }

    ListNode<Item>* after_node = (ListNode<Item>*) passed_node;
    ListNode<Item>* node = new ListNode<Item>(passed_item);

    if (listEnd(after_node)) {
		warning("List<Item>::insertAfter(it,NULL), returning ");
    		return ListNode2cn(after_node);
    }
    node->setNext(after_node->next());
    after_node->setNext(node);
    return ListNode2cn(node);
}


//
// return head of list and remove it
//
template <class Item>
Item
List<Item>::get()
{
    if (!listEnd(_first)) {
        ListNode<Item>* node = _first;
        Item pop_item = node->getItem();
        _first = node->next();
        delete node;
        return pop_item;
    }
    else
    {
	warning("can't get anything from empty list");
        static Item it;
        return it; // empty_data; 
    }
}

//
// return whether item is in list or not
//
template <class Item>
Bool
List<Item>::memberQ(const Item& passed_item) const
{
    if (listEnd(_first)) return FALSE;
    for (ListNode<Item>* node = _first; !listEnd(node); node = node->next())
        if (ElementOps<Item>::compareItems(passed_item, node->getItem())==0)
            return TRUE;
    return FALSE;
}

template <class Item>
ContainerNode* 
List<Item>::search(const Item& item) const
{
    ListNode<Item>* node;
    for (node = _first; !listEnd(node); node = node->next())
        if (ElementOps<Item>::compareItems(item, node->getItem()) ==0) 
            return ListNode2cn(node);
    return ListNode2cn(node);
} 

template <class Item>
void
List<Item>::sort(int (*compare)(const Item&, const Item&)=0) 
{
    if (listEnd(_first) || listEnd(_first->next()))
	return;

    if (!compare)
	compare = ElementOps<Item>::compareItems;

    static Item t;
    ListNode<Item> *dummy = new ListNode<Item>(t), *p, *c, *p2, *c2;
    dummy->setNext(_first);
    p=_first; 
    c=_first->next(); 
    while (!listEnd(c)) {
    	for (p2=dummy, c2=dummy->next(); 
		!listEnd(c2) && (compare(c2->getItem(), c->getItem()) <0); 
		p2=c2, c2=c2->next());
	if (compare(c->getItem(), c2->getItem()) < 0) {
		p->setNext(c->next());
		c->setNext(c2);
		p2->setNext(c);
		c = p->next();
	} else {
		p = c;
		c = c->next();
	}
    }
    _first = dummy->next();
    delete dummy;
}

template <class Item>
Item
List<Item>::first() const
{
    if (!listEnd(_first))
	return _first->getItem();
    else {
	warning("no first on empty list");
        static Item it;
	return it; // empty_data;
    }
}

template <class Item>
ListNode<Item>*
List<Item>::firstNode() const
{
    return _first;
}

//
// remove an item from the list
//
template <class Item>
void
List<Item>::remove(Item passed_item)
{
    ListNode<Item>* node = _first;
    ListNode<Item>* prev_node = 0;

    if (listEnd(_first))
    {
	warning("can't remove from empty list");
	return;
    }
    //if (memberQ(passed_item) == 0)
    //{
    //warning("can't remove things which don't exist");
    //    return;
    //}	
    while (!listEnd(node)) { 
	if (ElementOps<Item>::compareItems(node->getItem(), passed_item) == 0) {
	    ListNode<Item>* next_node = (ListNode<Item>*) node->next();
	    if (listEnd(prev_node))
		_first = next_node;
	    else
		prev_node->setNext(next_node);
	    delete node;
	    return;
	} 
        else {
	    prev_node = node;
	    node = node->next();
	}
    }
    //warning("list::remove(): element is not a member of the list");
    return;
}


           
/**************************************************************
    Considered, but didn't do:
    Removed predecessor and successor to force programmers to use the 
    Iterator.  Using successor is potentially confusing since the 
    end of list marking will not be NULL, but an object of type tc_nil
    if stk is being used.  I don't want to give the applications 
    programmer access to  this.		JWB  7/8/95
***/

//
// Return node before the passed node
//
template <class Item>
ContainerNode* 
List<Item>::predecessor(const ContainerNode * in_node) const
{
    ListNode<Item>* n = cn2ListNode(in_node);
    ListNode<Item>* node = _first;
    ListNode<Item>* prev_node = 0;
   
    if (listEnd(n)) 
    {
	warning("no predecessor for null pointer");
	return NULL;
    }
    while (!listEnd(node)) {
       if (node == (ListNode<Item>*) n) {
          if (listEnd(prev_node))
              return NULL;
          else 
              return (ContainerNode*) prev_node;
       }
       prev_node = node;
       node = node->next();
    }
    return NULL;
}
  
//
// Return node after the passed node
//
template <class Item>
ContainerNode* 
List<Item>::successor(const ContainerNode * n) const
{
    if (n == NULL)
    {
        warning("no successor for null pointer");
        return NULL;
    } 
    return (ContainerNode*)  ((ListNode<Item>*) n)->next();
}

//
// return the position of the item in the list
//
template <class Item>
int 
List<Item>::rank(Item& item) const
{
    int position = 1;
    ListNode<Item>* node = _first;

    while (!listEnd(node)) {
        if (ElementOps<Item>::compareItems(item, node->getItem()) == 0)
            return position;
        else {
            position++;
            node = node->next();
        }
    }
    warning("this item is not in the list, return 0");
    return 0;
}

template<class Item>
int
List<Item>::iterate(Iterator<Item>& iterator, Item& item) const
{
    //cout << "iterate::::: iterator._node: " << iterator._node << endl;
    if (iterator._index == 0) {
        // first time through iteration, return first, point at next
        if (listEnd(_first))
            return 0;
        else {
	    //cout << "iterate::: first time thru" << endl;
            item = _first->getItem();
            //*****iterator._node = ListNode2cn(_first->next());
            iterator._node = (ContainerNode*) _first->next();
            iterator._index = 1;
	    //cout << "iterate::: after next,_current_node:"<<_current_node<<endl;
	    //cout << "iterate::: after next,_current_node->_node:"<<_current_node->_node<<endl;
            return 1;
        }
    } else {
	//cout << "iterate::: another time thru" << endl;
        //cout << "iterate::::: iterator._node: " << iterator._node << endl;
        //****ListNode<Item>* node = cn2ListNode(iterator._node);
        ListNode<Item>* node = (ListNode<Item>*) iterator._node;
	//cout << "iterate::: node:"<<node<<endl;
	//cout << "iterate::: _current_node:"<<_current_node<<endl;
	//cout << "iterate::: _current_node->_node:"<<_current_node->_node<<endl;
        if (listEnd(node))
            // end of the iteration
            return 0;
        else {
            // middle of the iteration
            item = node->getItem();
            //********iterator._node = ListNode2cn(node->next());
            iterator._node = (ContainerNode*) node->next();
            iterator._index++;
	    //cout << "iterate::: after next: _current_node:"<<_current_node<<endl;
	    //cout << "iterate::: after next :_current_node->_node:"<<_current_node->_node<<endl;
            return 1;
        }
    }
}

template <class Item>
ostream&
List<Item>::display(ostream& os) const
{
    Iterator<Item> get_next(this);
    Item i;
    Bool start = FALSE;
    os << "(";
    while (get_next(i))
        if (!start) {
                ElementOps<Item>::displayItem(os, i);
                start = TRUE;
        } else {
                os << " ";
                ElementOps<Item>::displayItem(os, i);
	}
    os << ")";
    return os;
}

template <class Item>
SortedList<Item>::SortedList(const Container<Item>& l) 
{
    Iterator<Item> getnext(&l);
    Item item;

    while (getnext(item))
	insert(item);
}

template <class Item>
SortedList<Item>::SortedList(const SortedList<Item>& l) 
{
    Iterator<Item> getnext(&l);
    Item item;
    ContainerNode* cn;;

    if (!l.emptyQ()) {
	getnext(item);
	cn = insert(item);
    }
    while (getnext(item)) 
	cn = List<Item>::insertAfter(item, cn);
}

template <class Item>
SortedList<Item>&
SortedList<Item>::operator=(const SortedList<Item>& copy_list)
{
    ContainerNode *cn = ListNode2cn(_first);

    if (this != &copy_list) {
        clear();
        Iterator<Item> get_list(&copy_list);
        Item item;
    	if (!copy_list.emptyQ()) {
		get_list(item);
		cn = insert(item);
    	}
    	while (get_list(item)) 
		cn = List<Item>::insertAfter(item, cn);
    }
    return(*this);
}

template <class Item>
ContainerNode*
SortedList<Item>::prepend(Item i)
{
    if (!listEnd(_first) && (ElementOps<Item>::compareItems(_first->getItem(),
								 i)<0)) 
    {
	warning("Larger than the first element can't prepend");
	return NULL;
    }
    ListNode<Item>* node = new ListNode<Item>(i);
    node->setNext(_first);
    _first = node;

    return ListNode2cn(node);
}

//
// append() - insert at end if sorted order is maintained, else call insert()
//
template <class Item>
ContainerNode*
SortedList<Item>::append(Item passed_item)
{

    if (listEnd(_first)) {
        ListNode<Item>* node = new ListNode<Item>(passed_item);
	node->setNext(_first);
	_first = node;
        return ListNode2cn(node);
    }
    ListNode<Item>* n;
    for (n = _first; !listEnd(n->next()); n = n->next());
    if (ElementOps<Item>::compareItems(n->getItem(), passed_item) > 0) 
    {
	return insert(passed_item);
    }
    ListNode<Item>* node = new ListNode<Item>(passed_item);
    node->setNext(n->next());
    n->setNext(node);

    return ListNode2cn(node);
}

//
//
//
template <class Item>
ContainerNode*
SortedList<Item>::insert(Item passed_item)
{
    ListNode<Item>* node = new ListNode<Item>(passed_item);
    ListNode<Item>*prev, *n;
    int f;

    if (listEnd(_first))
    {
	node->setNext(_first);
	_first = node;
    } else if (((f=ElementOps<Item>::compareItems(passed_item, 
					_first->getItem()))==0) || (f<0)){
	node->setNext(_first);
	_first = node;
    } else {
       for (prev=_first,n=prev->next(); !listEnd(prev); 
					prev=prev->next(),n=n->next()) {
    	   if (!listEnd(n)) {
	      if (ElementOps<Item>::compareItems(n->getItem(),passed_item)>0) {
	       		node->setNext(n);
	       		prev->setNext(node);
	       		break;
	      }
	   } else {
	       node->setNext(n);
	       prev->setNext(node);
	       break;
	   }
       }
    }
    return ListNode2cn(node);
}

//template <class Item>
//ContainerNode*
//SortedList<Item>::remove(Item passed_item)
//{
//    ListNode<Item>*prev, *n;
//    int f;
//
//    if (listEnd(_first))
//    {
//	warning("can't remove from empty list");
//    } else if (((f=ElementOps<Item>::compareItems(passed_item, _first->getItem()))==0) || (f<0)){
//	warning("can't remove from empty list");
//    } else {
//       for (prev=_first,n=prev->next(); !listEnd(prev); 
//					prev=prev->next(),n=n->next()) {
//    	   if (!listEnd(n)) {
//		if (ElementOps<Item>::compareItems(n->getItem(), passed_item)==0) {
//	       		prev->setNext(n->next());
//			delete n;
//	       		break;
//		}
//	   }
//       }
//    }
//    return (ContainerNode*) node;
//}

//template <class Item>
//ContainerNode*
//SortedList<Item>::insertAfter(Item passed_item, ContainerNode* passed_node)
//{
//	warning("Sorted_List<Item>::insertAfter() called - returning");
//	return 0;
//}
//
//template <class Item>
//ContainerNode*
//SortedList<Item>::insertBefore(Item passed_item, ContainerNode* passed_node)
//{
//	warning("Sorted_List<Item>::insertBefore() called - returning");
//	return 0;
//}
    
template <class Item>
ContainerNode*
SortedList<Item>::insertBefore(Item passed_item, ContainerNode * in_node)
{
    ListNode<Item>* passed_node = cn2ListNode(in_node);
    if (listEnd(passed_node)) 
    {
	warning("SortedList::insertBefore(): can't insert before null pointer");
        return ListNode2cn(passed_node);
    }

    ListNode<Item>* before_node = (ListNode<Item>*) passed_node;
    ListNode<Item>* node = new ListNode<Item>(passed_item);
   
    if ((_first == before_node) || (listEnd(_first)))  {
      if (listEnd(_first))   
		warning("SortedList<Item>::insertBefore() "
			"called on empty list");
      if (listEnd(before_node)) {
		warning("SortedList<Item>::insertBefore(it,NULL), returning ");
    		return ListNode2cn(before_node);
      }
      if (ElementOps<Item>::compareItems(passed_item, 
					 *(Item*) before_node->info()) > 0) {
		warning("SortedList<Item>::insertBefore(), request for out"
			" of order insertion - returning");
    		return ListNode2cn(before_node);
      }
      node->setNext(_first);
      _first = node; 
      return ListNode2cn(node);
    }

    ListNode<Item>* n;
    for (n = _first; !listEnd(n->next()); n = n->next()) 
	if (n->next() == before_node)
	    break;
    if (ElementOps<Item>::compareItems(passed_item, 
				       *(Item*) before_node->info()) > 0) {
	warning("SortedList<Item>::insertBefore(), request for out"
		" of order insertion - returning");
    	return ListNode2cn(before_node);
    }
    node->setNext(n->next());
    n->setNext(node);
    return ListNode2cn(node);
}
    
template <class Item>
ContainerNode*
SortedList<Item>::insertAfter(Item passed_item, ContainerNode * in_node)
{
    ListNode<Item>* passed_node = cn2ListNode(in_node);
    if (listEnd(passed_node)) 
    {
	warning("can't insert after a null pointer");
    	return ListNode2cn(passed_node);
    }

    ListNode<Item>* after_node = (ListNode<Item>*) passed_node;
    ListNode<Item>* node = new ListNode<Item>(passed_item);

    if (listEnd(after_node)) {
		warning("SortedList<Item>::insertAfter(it,NULL), returning ");
    		return ListNode2cn(after_node);
    }
    if (ElementOps<Item>::compareItems(passed_item, 
				       *(Item*) after_node->info()) < 0) {
	warning("SortedList<Item>::insertAfter(), request for out"
		" of order insertion - returning");
    	return ListNode2cn(after_node);
    }
    node->setNext(after_node->next());
    after_node->setNext(node);
    return ListNode2cn(node);
}

template <class Item>
Bool
SortedList<Item>::memberQ(const Item& passed_item) const
{
    for (ListNode<Item>* node = _first; !listEnd(node); node = node->next())
    {
        if (ElementOps<Item>::compareItems(passed_item, node->getItem())==0)
            return TRUE;
        if (ElementOps<Item>::compareItems(passed_item, node->getItem())<0)
	    return FALSE; 
    }
    return FALSE;
}

template <class Item>
ContainerNode*
SortedList<Item>::search(const Item& item) const
{
    for (ListNode<Item>* node = _first; !listEnd(node); node = node->next())
    {
        if (ElementOps<Item>::compareItems(item, node->getItem())==0) {
    	    return ListNode2cn(node);
	}
    //*************************************************************
    //** unsure about this part w.r.t. STk.  not sure if SortedList
    //** will be wrapped
    //*************************************************************
        if (ElementOps<Item>::compareItems(item, node->getItem())<0)
	    return NULL;
    }
    return NULL;
    //*************************************************************
}


// scramble is not implemented either.