// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Patricia K. Fasel, 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 DList_h
#define DList_h

#include <LINK/basic/Container.h>

class AnimationData;
template <class Item> class DList;


template <class Item>
class DListNode : public ContainerNode {
public:
    friend class DList<Item>;
    void	       *info() const {return (void *) &item;}

private:
    DListNode(Item passed_item) : pred(0), succ(0), item(passed_item) {}

    Item		item;
    DListNode*		pred;
    DListNode*		succ;
};


template <class Item>
class DList : public SimpleContainer<Item> {
public:
    //int		ref_count;

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

    Item                info(const ContainerNode *cn) const;
    DList<Item>&	operator=(const DList<Item>& copy_list);


    int			size() const	{ return _count;		}
    Bool		emptyQ() const	{ return _first ? FALSE : TRUE; }
    Bool		fullQ() const	{ return FALSE; 		}
    Bool		memberQ(const Item& passed_item) const;
    Bool		sortedQ() const { return FALSE; 		}
    ContainerNode*	search (const Item& passed_item) const;
    DataType		type() const	{ return DLIST; 		}

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

    ContainerNode*	insert(Item i)	{ return prepend(i); }
    ContainerNode*	insert(ContainerNode  * cn);
    ContainerNode*	insertBefore(Item i, Item before_i);
    ContainerNode*	insertAfter(Item i, Item after_i);
    ContainerNode*	insertBefore(Item i, ContainerNode  * before_node);
    ContainerNode*	insertAfter(Item i, ContainerNode  * after_node);
    ContainerNode*	prepend(Item i);
    ContainerNode*	append(Item i);
    ContainerNode*	unlink(ContainerNode   *cn);
    void		remove(Item i);
    void		clear();
    Item		get();		// return head and remove

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

    int 		rank(const Item& item) const;

    ostream&		display(ostream& os) const;

private:
    int                 iterate(Iterator<Item>& iter, Item& item) const;
    DListNode<Item>*	_first;
    DListNode<Item>*	_last;
    int			_count;
    friend class AnimationData;
};


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

#endif