/* List.H */

#ifndef _XRML_LIST_H_
#define _XRML_LIST_H_

#include "memory.H"

namespace xrml {

template<class T>
class list: public PooledObj {
public:
  T data;
  class list *next;	// pointer to next element

  inline operator T() const { return data; }
  inline operator T*() { return &data; }

  inline list() { next = 0; }

  inline list(const T& data)
  {
    list::data = data;
    list::next = 0;
  }

  // Insert new element after 'this', returns pointer to new list element:
  // if inserting after the tail of the list, the new tail of the list if
  // returned.
  inline list* append(class list *l)
  {
    l->next = next;
    next = l;
    return l;
  }

  // Insert new element after 'this', returns pointer to new list element
  // (=new tial of the list if inserting after the tail).
  inline list *append(const T& data)
  {
    return append(new list(data));
  }

  // Adds new elements in front of the list. Returns the new head of the list
  // (which is 'l').
  inline list *prepend(class list *l)
  {
    l->next = this;
    return l;
  }

  // Adds 'data' to the head of the list. Returns the new list head.
  inline list* prepend(const T& data)
  {
    list* l = new list(data);
    return prepend(l);
  }

  // Returns pointer to first list element starting from 'this', with
  // data equal to 'data' (tested with '=='). If 'chasing' is not null,
  // a pointer to the list element before the returned element is filled
  // in (chasing pointer). The chasing pointer is null if 'this' is the
  // matching element in the list. The chasing pointer points to the last
  // element in the list if no match is found.
  inline list* find(const T& data, class list** chasing =0)
  {
    list *l, *p=0;
    for (l=this; l; p=l, l=l->next)
      if (data == l->data)
	break;
    if (chasing) *chasing = p;
    return l;
  }

  // Removes 'this', 'prev' = preceeding element, returns pointer to the 
  // first element of the list past the deleted element 'this'.
  // 'prev' is null is 'this' is the head of the list. In that case, the
  // new head of the list is returned.
  inline list *remove(class list *prev)
  {
    if (prev) prev->next = next;
    return next;
  }

  // Removes the first occurence of 'data' in the list, starting from 'this'.
  // returns the first element after the deleted element. If 'data' is not
  // found in the list, nothing is removed and 'this' is returned.
  inline list* remove(const T& data)
  {
    list *p=0, *l = find(data, &p), *n = this;
    if (l) {
      n = remove(p);
      delete l;
    }
    return n;
  }

  // Counts the number of elements in the list starting from 'this'.
  inline int count(void) const
  {
    int count=0;
    for (list* l=this; l; l++)
      count++;
    return count;
  }

  // duplicates the list, starting from 'this'
  inline list* clone(void)
  {
    list *newlist = 0, *tail = 0;
    for (list *l=this; l; l=l->next) {
      list *clone = new list(l->data);
      tail = tail ? tail->append(clone) : (newlist = clone);
    }
    return newlist;
  }
};

} // namespace xrml

#endif /* _XRML_LIST_H_ */
