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


template <class Item>
DList<Item>::DList() :
			_first(0),
			_last(0),
			_count(0)
{}


template <class Item>
DList<Item>::~DList()
{
    clear();
}

template <class Item>
DList<Item>::DList(const DList<Item>& c) :
			_first(0),
			_last(0),
			_count(0)
{
    Iterator<Item> get_item(&c);
    Item item;
    while (get_item(item))
	append(item);
}

template <class Item>
DList<Item>::DList(const Container<Item>& c) :
			_first(0),
			_last(0),
			_count(0)
{
    Iterator<Item> get_item(&c);
    Item item;
    while (get_item(item))
	append(item);
}

template <class Item>
Item
DList<Item>::info(const ContainerNode *node) const
{
	if (node != 0) 
		return *(Item*) node->info();
	static Item i;
	return i;
}

template <class Item>
DList<Item>&
DList<Item>::operator=(const DList<Item>& copy_list)
{
    if (this != &copy_list) {
        clear();
        Iterator<Item> get_list(&copy_list);
        Item item;
        while (get_list(item))
            append(item);
    }
    return(*this);
}



//
// prepend an item to the head of a list
//
template <class Item>
ContainerNode*
DList<Item>::prepend(Item passed_item)
{
    DListNode<Item>* node = new DListNode<Item>(passed_item);
    node->succ = _first;
    if (_first)
    	_first->pred = node;
    _first = node;
    if (_last == 0)
	_last = node;
    _count++;
    return (ContainerNode*) node;
}


template <class Item>
ContainerNode*
DList<Item>::successor(const ContainerNode  *cn) const
{
    if (!cn) return NULL;
    DListNode<Item>* node = (DListNode<Item>*) cn;
    return node->succ;
}

//
// insert an item before the passed item
//
template <class Item>
ContainerNode*
DList<Item>::insertBefore(Item passed_item, Item before_item)
{
    DListNode<Item>* temp_node = _first;
    while (temp_node) {
        if (ElementOps<Item>::compareItems(temp_node->item, before_item)==0) {
            DListNode<Item>* node = new DListNode<Item>(passed_item);
            node->pred = temp_node->pred;
            node->succ = temp_node;
            if (_first == temp_node)
                _first = node;
            else
                node->pred->succ = node;
            temp_node->pred = node;
            _count++;
	    return (ContainerNode*) node;
        } else
            temp_node = temp_node->succ;
    }
    return (ContainerNode*) 0;
}


template <class Item>
ContainerNode*
DList<Item>::insertBefore(Item passed_item, ContainerNode  * passed_node)
{
    if (!passed_node)
    {
        warning("DList::insertBefore(): can't insert before null pointer");
        return passed_node; 
    }


    DListNode<Item>* before_node = (DListNode<Item>*) passed_node;
    DListNode<Item>* node = new DListNode<Item>(passed_item);

    node->succ = before_node;
    if (before_node->pred)
        before_node->pred->succ = node;
    else
        _first = node;
    node->pred = before_node->pred;
    before_node->pred = node;
    _count++;
    return (ContainerNode*) node;
}


//
// insert an item after the passed item
//
template <class Item>
ContainerNode*
DList<Item>::insertAfter(Item passed_item, Item after_item)
{
    DListNode<Item>* temp_node = _first;
    while (temp_node) {
        if (ElementOps<Item>::compareItems(temp_node->item,after_item)==0) {
            DListNode<Item>* node = new DListNode<Item>(passed_item);
            node->pred = temp_node;
            node->succ = temp_node->succ;
            if (_last == temp_node)
                _last = node;
            else
                temp_node->succ->pred = node;
            temp_node->succ = node;
            _count++;
            return (ContainerNode*) node;
        } else
            temp_node = temp_node->succ;
    }
    return (ContainerNode*) 0;
}


template <class Item>
ContainerNode*
DList<Item>::insertAfter(Item passed_item, ContainerNode  * passed_node)
{
    if (!passed_node)
	return(append(passed_item));
    DListNode<Item>* after_node = (DListNode<Item>*) passed_node;
    DListNode<Item>* node = new DListNode<Item>(passed_item);

    node->pred = after_node;
    if (after_node->succ)
        after_node->succ->pred = node;
    node->succ = after_node->succ;
    after_node->succ = node;
    _count++;
    return (ContainerNode*) node;
}


//
// append an item to the tail of a list
//
template <class Item>
ContainerNode*
DList<Item>::append(Item passed_item)
{
    DListNode<Item>* node = new DListNode<Item>(passed_item);
    if (_last == 0)
	_first = node;
    else
        _last->succ = node;
    node->pred = _last;
    node->succ = 0;
    _last = node;
    _count++;
    return (ContainerNode*) node;
}

template <class Item>
ContainerNode*
DList<Item>::insert(ContainerNode    *cn)
{
    DListNode<Item>* node = (DListNode<Item>*) cn;

    if (_last == 0)
	_first = node;
    else
        _last->succ = node;
    node->pred = _last;
    node->succ = 0;
    _last = node;
    _count++;
    return (ContainerNode*) node;
}

//
// get the previous item before the passed item
//
//template <class Item>
//Item
//DList<Item>::pred(const Item& passed_item) const
//{
//    DListNode<Item>* node = _first;
//    while (node) {
//        if ((ElementOps<Item>::compareItems(node->item, passed_item)==0) && 
//	      node->pred)
//            return node->pred->item;
//        node = node->succ;
//    }
//    static Item i;
//    return i;
//}

template <class Item>
ContainerNode*
DList<Item>::predecessor(const ContainerNode *cn) const
{
    if (!cn) return NULL;
    DListNode<Item>* node = (DListNode<Item>*) cn;
    return node->pred;
}


//
// return the first item from the list and remove it from the list
//
template <class Item>
Item
DList<Item>::get()
{
    if (_first) {
        DListNode<Item>* node = _first;
        Item pop_item = node->item;
        _first = node->succ;
        if (node->succ)
            node->succ->pred = node->pred;
        delete node;
	_count--;
	if (_count == 0) {
	    _first = 0;
	    _last = 0;
	}
        return pop_item;
    }
    static Item i;
    return i;
}


//
// return the item at the head of the list
//
template <class Item>
Item
DList<Item>::first() const
{
    if (_first)
	return _first->item;
    else {
	static Item i;
	return i;
    }
}


//
// return the item at the tail of the list
//
template <class Item>
Item
DList<Item>::last() const
{
    if (_last) 
	return _last->item;
    else {
	static Item i;
	return i;
    }
}

template <class Item>
ContainerNode *
DList<Item>::unlink(ContainerNode   *cn)
{
    if (cn == NULL) return NULL;

    DListNode<Item>* node = (DListNode<Item>*) cn;
    DListNode<Item>* prev_node = (DListNode<Item>*) node->pred;
    DListNode<Item>* next_node = (DListNode<Item>*) node->succ;
    if (prev_node == 0) {
	_first = next_node;
	if (next_node)
	    next_node->pred = 0;
    } else {
	prev_node->succ = next_node;
	if (next_node)
	    next_node->pred = prev_node;
    }
    if (_last == node)
	_last = node->pred;
   _count--;
    if (_count == 0) {
	_first = 0;
	_last = 0;
    }
    return cn;
}


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

    while (node) {
	if (ElementOps<Item>::compareItems(node->item, passed_item)==0) {
	    DListNode<Item>* next_node = (DListNode<Item>*) node->succ;
	    if (prev_node == 0) {
		_first = next_node;
		if (next_node)
		    next_node->pred = 0;
	    } else {
		prev_node->succ = next_node;
		if (next_node)
		    next_node->pred = prev_node;
	    }
	    if (_last == node)
		_last = node->pred;
	    delete node;
	    node = next_node;
	    _count--;
	    if (_count == 0) {
		_first = 0;
		_last = 0;
	    }
	    return;
	} else {
	    prev_node = node;
	    node = node->succ;
	}
    }
}


//
// is the passed object a member of this list
//
template <class Item>
Bool
DList<Item>::memberQ(const Item& passed_item) const
{
    for (DListNode<Item>* node = _first; node; node = node->succ) 
	if (ElementOps<Item>::compareItems(passed_item, node->item)==0)
	    return TRUE;
    return FALSE;
}


//
// remove all items from a list
//
template <class Item>
void
DList<Item>::clear()
{
    DListNode<Item>* node = _first;
    while (node) {
	DListNode<Item>* next_node = node->succ;
	delete node;
	node = next_node;
    }
    _first = 0;
    _last = 0;
    _count = 0;
}


template<class Item>
int
DList<Item>::iterate(Iterator<Item>& iterator, Item& item) const
{
    if (iterator._index == 0) {
	// first time through iteration, return first point at next
        if (_count == 0)
            return 0;
        else {
            item = _first->item;
            iterator._node = _first->succ;
            iterator._index = 1;
            return 1;
        }
    } else
        if (iterator._node == 0)
	    // end of iteration
            return 0;
        else {
	    // middle of iteration
            DListNode<Item>* node = (DListNode<Item>*)iterator._node;
            item = node->item;
            iterator._node = (ContainerNode*) node->succ;
            iterator._index++;
            return 1;
        }
}

template <class Item>
int
DList<Item>::rank(const Item& passed_item) const
{
    int r=1;
    DListNode<Item>* temp_node = _first;
    while (temp_node) {
        if (ElementOps<Item>::compareItems(temp_node->item, passed_item)==0) 
		return r;
	temp_node = temp_node->succ;
	r++;
    }
    return 0;
}

template <class Item>
ContainerNode*
DList<Item>::search(const Item& passed_item) const
{
    DListNode<Item>* temp_node = _first;
    while (temp_node) {
        if (ElementOps<Item>::compareItems(temp_node->item, passed_item)==0) 
		return temp_node;
	temp_node = temp_node->succ;
    }
    return 0;
}

template <class Item>
ostream&
DList<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;
}