/*
 * List.h
 *
 * Copyright (C) 1999 Stephen F. White
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (see the file "COPYING" for details); if 
 * not, write to the Free Software Foundation, Inc., 675 Mass Ave, 
 * Cambridge, MA 02139, USA.
 */

#ifndef _LIST_H
#define _LIST_H

#ifndef NULL
#define NULL 0L
#endif

template<class T> 
class List {
public:
    class Iterator {
	friend class List<T>;
    public:
			Iterator(const T &t) : _value(t)
			    { _prev = _next = NULL; }

	Iterator       *prev()		{ return _prev; }
	const Iterator *prev() const	{ return _prev; }
	Iterator       *next()		{ return _next; }
	const Iterator *next() const	{ return _next; }

	const T	       &item() const	{ return _value; }
	T	        item()		{ return _value; }
	void	        setItem(const T &t)	
                                        { _value = t; }

    private:
	Iterator	       *_prev;
	Iterator	       *_next;
	T			_value;
    };

    void Init(void)
    {
	_head = _tail = NULL; _length = 0;
    }

			List()
    {
	_head = _tail = NULL; _length = 0;
    }

			List(const List<T> &l)
    {
	_head = _tail = NULL; _length = 0;
	for (Iterator *i = l.first(); i != NULL; i = i->next())
	    append(i->item());
    }

		       ~List()
    { 
	removeAll();
    }
    


    void		append(const T &t)
    {
	Iterator   *i = new Iterator(t);
	i->_prev = _tail;
	if (_tail) {
	    _tail->_next = i;
	} else {
	    _head = i;
	}
	_tail = i;
	_length++;
    }

    void		insert(const T &t)
    {
	Iterator   *i = new Iterator(t);
	i->_next = _head;
	if (_head) {
	    _head->_prev = i;
	} else {
	    _tail = i;
	}
	_head = i;
	_length++;
    }

    void		remove(Iterator *i)
    {
	if (i->_prev) {
	    i->_prev->_next = i->_next;
	} else {
	    _head = i->_next;
	}
	if (i->_next) {
	    i->_next->_prev = i->_prev;
	} else {
	    _tail = i->_prev;
	}
	delete i;
	_length--;
    }

    Iterator	       *find(const T &t) const
    {
	for (Iterator *i = _head; i != NULL; i = i->next()) {
	    if (i->item() == t) return i;
	}
	return NULL;
    }

    Iterator	       *get(int index) const
    {
	Iterator *i;
	for (i = _head; i != NULL && index > 0; i = i->next())
	    index--;
	return i;
    }

    void		removeAll()
    {
	Iterator		*i, *j;

	for (i = _head; i != NULL; i = j) {
	    j = i->next();
	    delete i;
	}
        Init();
    }

    void		appendList(List<T> *list)
    {
	for (Iterator *i = list->first(); i != NULL;
	     i = i->next()) {
	    append(i->item());
	}
    }

    void		insertList(List<T> *list)
    {
	for (Iterator *i = list->last(); i != NULL;
	     i = i->prev()) {
	    insert(i->item());
	}
    }

    Iterator	       *first() const { return _head; }
    Iterator	       *last() const { return _tail; }
    int			size() const { return _length; }

    int			operator==(const List<T> &list)
    {
	Iterator	*i, *j;

	for(i = list.first(), j = _head; i != NULL && j != NULL;
	    i = i->next(), j = j->next())
	{
	    if (i->item() != j->item()) return 0;
	}
	return i != NULL && j != NULL;
    }
private:
    Iterator	       *_head;
    Iterator	       *_tail;
    int			_length;
};
#endif // _LIST_H