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

#ifndef List_h
#define List_h

#include <iostream.h>
#include <stddef.h>
#include <LINK/basic/Container.h>

class Vertex;
class Edge;
template <class Item> class List;
template <class Item> class SortedList;

//template <class Item> class CollectionWrapper;
//template <class Item> class ListWrapper;

#ifdef STK_LISTS

#include <stk.h>
#include <iostream.h>
#include <LINK/stkWrapper/LINK_STk.h>
#include <LINK/stkWrapper/Wrapper.h>

template <class Item> class CollectionWrapper;
template <class Item> class ListWrapper;

//***********************************************************************
// class ListNode
//		this class header contains source code in order to
//		relieve users of the responsibility of instantiating
//		ListNode templates in addition to List templates when
//		the STk interface is used.  If the compiler instantiates
//		templates automatically, the code in this header could
//		be moved to List.cc	
//***********************************************************************
template <class Item>
class ListNode : public obj {
public:
    friend class List<Item>;
    friend class SortedList<Item>;
    friend class ListWrapper<Item>;
    void*               operator new(size_t size)
			{
			 //cout << "operator new (ListNode):";
        		 //SCM *list_node = new SCM;
        		 //NEWCELL( (*list_node), tc_cons);
			 //cout << "operator new (ListNode): protecting:" <<*list_node << endl;
			 //STk_gc_protect(list_node);
        		 //CAR( (*list_node) ) = CDR( (*list_node) ) = NIL;
			 //cout << "the new cell is: " << *list_node << endl;
			 //cout << "cdr set to: " << NIL << endl;
			 //return *list_node;
        		 SCM list_node;
        		 NEWCELL(list_node, tc_cons);
        		 CAR(list_node) = CDR(list_node) = NIL;
			 return (void*) list_node;
			}

    void                operator delete(void *p, size_t size) 
			{
			 //STk_gc_unprotect((SCM) p);	//frees list_node
			}

    void*               info() const    
			{ 
				//cout << "at least ListNode::info" <<endl; 
				return EXTDATA(VAL(CAR( (SCM) this))); 
			} 
protected:
    ListNode(Item e)
    {
	//cout << "ListNode(): " << this << endl;
        type = tc_cons;
	int  &member_type =  Wrapper<Item>::type;
	char *member_name =  Wrapper<Item>::name;
	SCM ptr_node;
	//cout << "Wrapper<Item>::type: " << Wrapper<Item>::type << endl;
	ptr_node = STk_make_CXXwrapper(member_type, member_name,
					(void *) new Item(e), LINK_DYNAMIC);
        CAR( (SCM) this) = ptr_node;
	//cout << "LISTNODE: element type is: " << TYPE(ptr_node) << endl;
	//cout << "LISTNODE: type is: " << TYPE(this) << endl;
	//cout << "LISTNODE: element address is: " << ptr_node << endl;
	//cout<<"LISTNODE: element address thru CAR is: "<<CAR((SCM)this)<<endl;
	//cout << "LISTNODE: element type is: " << TYPE(ptr_node) << endl;
	//cout << "LISTNODE: address is:        " << this << endl;
	//cout << "LISTNODE: address as SCM is: " << (SCM) this << endl;
	//cout << "LISTNODE: sizeof(*this): " << sizeof(*this) << endl;
	//cout << "LISTNODE: sizeof(ListNode<Item>): "<< sizeof(ListNode<Item>) << endl;
	//cout << "LISTNODE: size as SCM is: " << sizeof(*((SCM) this)) << endl;
    }

    ListNode*           next() const    { return (ListNode<Item>*)
						CDR( (SCM) this);	    
					}
    Item		getItem() const	{ 
				return *(Item *) EXTDATA(VAL(CAR((SCM)this)));
					}
    void           	setNext(ListNode* y)
					{ CDR( (SCM) this) = (SCM) y; }
};

#else

template <class Item>
class ListNode : public ContainerNode {
public:
    friend class List<Item>;
    friend class SortedList<Item>;
    void*               info() const         	{return (void *) &item; }  
    ListNode*           next() const    	{return nxt;  		}
    ListNode*           setNext(ListNode* y)	{return nxt = y;  	}
protected:
    ListNode(Item passed_item) : nxt(0), item(passed_item) {}

    Item		getItem() const	{ return item;	    }
    Item		item;
    ListNode*		nxt;
};

#endif // STK_LISTS

template <class Item>
class ListContainerNode : public ContainerNode {
public:
    friend class List<Item>;
    ListContainerNode() {}
    void*               info() const    	   { return _node->info(); }
    ListNode<Item>*     getNode() const 	   { return _node; 	   }
    void		setNode(ListNode<Item>* n) { _node = n;		   }
protected:
    ListNode<Item>*	_node;
};


template <class Item>
class List : public SimpleContainer<Item> {

public:

    List();
    List(const List<Item>& c);
    List(const Container<Item>& c);
    virtual ~List();

    Item		info(const ContainerNode *cn) const;
    List<Item>&         operator=(const List<Item>& copy_list);
    //List<Item>&	copy(List<Item>& copy_list) 
    //				{*this = copy_list; return *this; }

    int			size() const;	
    Bool		emptyQ() const	{ return listEnd(_first);	}
    Bool		fullQ() const	{ return FALSE; 		}
    Bool            	sortedQ() const { return FALSE; 		}
    DataType            type() const    { return LIST; 			}

    ContainerNode*      prepend(Item i);
    ContainerNode*      append(Item i);

    ContainerNode*      insert(Item i);
    ContainerNode*      insertBefore(Item i, ContainerNode * n);
    ContainerNode*      insertAfter(Item i, ContainerNode * n);

    Item                get();          
 
    Bool		memberQ(const Item& i) const;
    ContainerNode*      search(const Item& item) const;
    void		sort(int (*)(const Item&, const Item&));

    Item		first() const;
    Item		last() const;

    void		remove(Item i);
    void                clear();

    ContainerNode*      predecessor(const ContainerNode * n) const;
    ContainerNode*      successor(const ContainerNode * n) const;

    int                 rank(Item& item) const;


    ostream&            display(ostream& os) const;
   // List<Item>&       scramble()
#ifdef STK_LISTS
    PRIMITIVE			retrieveHeader();
    PRIMITIVE			unprotectHeader();
#endif
    //friend class ListWrapper<Item>;
    //friend class CollectionWrapper<Item>;

protected:
    ListNode<Item>*		_first; 
    ListContainerNode<Item>*	_current_node;
    int 			listEnd(const ListNode<Item>* n) const;
    int 			listEnd(const ListContainerNode<Item>* n) const;
    ListNode<Item>*		cn2ListNode(const ContainerNode *n) const;
    ListNode<Item>*		firstNode() const;
    ContainerNode*		ListNode2cn(ListNode<Item> *n) const;
    int                 	iterate(Iterator<Item>& iter, Item& item) const;
#ifdef STK_LISTS
    void			createProtectedHeader();
#endif
};

template <class Item>
class SortedList: public List<Item> {
public:
    SortedList() {}
    SortedList(const Container<Item>& l); 
    SortedList(const SortedList<Item>& l); 
    SortedList<Item>&     	operator=(const SortedList<Item>& copy_list);
    ContainerNode*		prepend(Item i);
    ContainerNode*      	append(Item i);
    ContainerNode*      	insert(Item i);
    ContainerNode*      	insertBefore(Item i, ContainerNode * n);
    ContainerNode*      	insertAfter(Item i, ContainerNode * n);
    Bool                	memberQ(const Item& i) const;
    Bool                	sortedQ() const { return TRUE;    }
    Item                	min() const 	{ return first(); }
    ContainerNode*      	search(const Item& item) const;
}; 

#ifdef DEFINE_TEMPLATE
#include <LINK/basic/List.cc>
#endif


#endif