// This may look like C code, but it is really -*- C++ -*-
/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea (dl@rocky.oswego.edu)

This file is part of the GNU C++ Library.  This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.  This library 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 Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/


#ifndef _<T>List_h
#ifdef __GNUG__
#pragma interface
#endif
#define _<T>List_h 1

#include <Pix.h>
#include "<T>.defs.h"

#ifndef _<T>_typedefs
#define _<T>_typedefs 1
typedef void (*<T>Procedure)(<T&>);
typedef <T>  (*<T>Mapper)(<T&>);
typedef <T>  (*<T>Combiner)(<T&>, <T&>);
typedef int  (*<T>Predicate)(<T&>);
typedef int  (*<T>Comparator)(<T&>, <T&>);
#endif

struct <T>ListNode
{
  <T>ListNode*          tl;
  short                 ref;
  <T>                   hd;
};

extern <T>ListNode Nil<T>ListNode;

class <T>List
{
protected:
  <T>ListNode*          P;

                        <T>List(<T>ListNode* p);
public:
                        <T>List();
                        <T>List(<T&> head);
                        <T>List(<T&> head, <T>List& tl);
                        <T>List(<T>List& a);
                        <T>List(Pix p);
                        ~<T>List();

  <T>List&              operator = (<T>List& a);

  int                   null();
  int                   valid();
                        operator const void* ();
  int                   operator ! ();

  int                   length();
  int                   list_length();

  <T>&                  get();
  <T>&                  head();
  <T>&                  operator [] (int n);

  <T>List               nth(int n);
  <T>List               tail();
  <T>List               last();

  <T>List               find(<T&> targ);
  <T>List               find(<T>List& targ);
  int                   contains(<T&> targ);
  int                   contains(<T>List& targ);
  int                   position(<T&> targ);

  friend <T>List        copy(<T>List& a);
  friend <T>List        concat(<T>List& a, <T>List& b);
  friend <T>List        append(<T>List& a, <T>List& b);
  friend <T>List        map(<T>Mapper f, <T>List& a);
  friend <T>List        merge(<T>List& a, <T>List& b, <T>Comparator f);
  friend <T>List        combine(<T>Combiner f, <T>List& a, <T>List& b);
  friend <T>List        reverse(<T>List& a);
  friend <T>List        select(<T>Predicate f, <T>List& a);        
#undef remove
  friend <T>List        remove(<T&> targ, <T>List& a);
  friend <T>List        remove(<T>Predicate f, <T>List& a);
  friend <T>List        subst(<T&> old, <T&> repl, <T>List& a);

  void                  push(<T&> x);
  <T>                   pop();

  void                  set_tail(<T>List& p);
  void                  append(<T>List& p);
  void                  prepend(<T>List& p);
  void                  del(<T&> targ);
  void                  del(<T>Predicate f);
  void                  select(<T>Predicate f);
  void                  subst(<T&> old, <T&> repl);
  void                  reverse();
  void                  sort(<T>Comparator f);

  void                  apply(<T>Procedure f);
  <T>                   reduce(<T>Combiner f, <T&> base);

  friend int            operator == (<T>List& a, <T>List& b);
  friend int            operator != (<T>List& a, <T>List& b);

  Pix                   first();
  void                  next(Pix& p);
  Pix                   seek(<T&> item);
  <T>&                  operator () (Pix p);
  int                   owns(Pix p);

  void                  error(const char*);
  int                   OK();
};


inline void reference(<T>ListNode* p)
{
  if (p->ref >= 0) ++p->ref;
}

inline void dereference(<T>ListNode* p)
{
  while (p->ref > 0 && --p->ref == 0)
  {
    <T>ListNode* n = p->tl;
    delete(p);
    p = n;
  }
}


inline <T>ListNode* new<T>ListNode(<T&> h)
{
  <T>ListNode* p = new <T>ListNode;
  p->ref = 1;
  p->hd = h;
  return p;
}

inline <T>ListNode* new<T>ListNode(<T&> h, <T>ListNode* t)
{
  <T>ListNode* p = new <T>ListNode;
  p->ref = 1;
  p->hd = h;
  p->tl = t;
  return p;
}


inline <T>List::~<T>List()
{
  dereference(P);
}

inline <T>List::<T>List()
{
  P = &Nil<T>ListNode;
}

inline <T>List::<T>List(<T>ListNode* p)
{
  P = p;
}

inline <T>List::<T>List(<T&> head)
{
  P = new<T>ListNode(head);
  P->tl = &Nil<T>ListNode;
}

inline <T>List::<T>List(<T&> head, <T>List& tl)
{
  P = new<T>ListNode(head, tl.P);
  reference(P->tl);
}

inline <T>List::<T>List(<T>List& a)
{
  reference(a.P);
  P = a.P;
}


inline <T>& <T>List::get()
{
  return P->hd;
}

inline <T>& <T>List::head()
{
  return P->hd;
}


inline <T>List <T>List::tail()
{
  reference(P->tl);
  return <T>List(P->tl);
}



inline int <T>List::null()
{
  return P == &Nil<T>ListNode;
}

inline int <T>List::valid()
{
  return P != &Nil<T>ListNode;
}

inline <T>List::operator const void* ()
{
  return (P == &Nil<T>ListNode)? 0 : this;
}

inline int <T>List::operator ! ()
{
  return (P == &Nil<T>ListNode);
}


inline void <T>List::push(<T&> head)
{
  <T>ListNode* oldp = P;
  P = new<T>ListNode(head, oldp);
}


inline int operator != (<T>List& x, <T>List& y)
{
  return !(x == y);
}

inline Pix <T>List::first()
{
  return (P == &Nil<T>ListNode)? 0 : Pix(P);
}

inline <T>& <T>List::operator () (Pix p)
{
  return ((<T>ListNode*)p)->hd;
}

inline void <T>List::next(Pix& p)
{
  if (p != 0)
  {
    p = Pix(((<T>ListNode*)p)->tl);
    if (p == &Nil<T>ListNode) p = 0;
  }
}

inline <T>List::<T>List(Pix p)
{
  P = (<T>ListNode*)p;
  reference(P);
}

#endif