// Lists based on the Procedural Data
// Abstraction idea, as described in the
// paper:
/*
  Author = 	"William R. Cook",
  Title = 	"Object-Oriented Programming Versus Abstract Data Types",
  BookTitle = 	"Foundations of Object-Oriented Languages, REX
		 School/Workshop, Noordwijkerhout, The Netherlands,
		 May/June 1990",
  Publisher = 	"Springer-Verlag",
  Year = 	1991,
  Editor = 	"J. W. de Bakker and W. P. de Roever and G. Rozenberg",
  Series = 	LNCS,
  Volume = 	489,
  Pages = 	"151-178",
*/

// AUTHOR: Gary T. Leavens

#if !defined(_COOKLIST_H)
#define _COOKLIST_H

#include "boolean.h"
#include "exception.h"

// List is an abstract class
// of homogeneous lists of type T elements
template <class T>
class List {
public:
  virtual bool is_null() const = 0;
  virtual T head() const = 0;
  virtual List<T>* tail() const = 0;

  // convenience functions
  T car() const { return head(); }
  List<T>* cdr() const { return tail(); }
};

// a class of exceptions (not used)
class Empty{};

// The empty list of type T
// The two hacks below are to get around
// the C++ type checker, which doesn't
// understand that an abort never returns.
template <class T>
class Nil : public List<T> {
public:
  Nil() {}
  bool is_null() const { return true; }
  T head() const {
    throw(Empty());
    return (T)0;  // never reached
  }
  List<T>* tail() const {
    throw(Empty());
    return 0;     // never reached
  }
};

// Common code for ImmutableList and Cons
template <class T>
class NonEmptyList : public List<T> {
protected:
  T contents;
  List<T> * next_cell;
public:
  is_null() const { return false; }
  T head() const { return contents; }
  List<T>* tail() const {
    return next_cell;
  }
};

// Lists that cannot be mutated.
// The trick is in the type restrictions
// on the constructors.
template <class T>
class ImmutableList
    : public NonEmptyList<T> {
public:
  ImmutableList(T x, ImmutableList<T>* l)
    : contents(x), next_cell(l) {}
  ImmutableList(T x, Nil<T>* l)
    : contents(x), next_cell(l) {}
};

// mutable lists, with set_head
// and set_tail
template <class T>
class Cons : public NonEmptyList<T> {
public:
  Cons(T x, Cons<T>* l)
  : contents(x), next_cell(l) {}
  Cons(T x, Nil<T>* l)
  : contents(x), next_cell(l) {}

  virtual void set_head(T x) {
    contents = x;
  }
  virtual void set_tail(List<T>* l) {
    next_cell = l;
  }
};


#include <iostream.h>

template <class T>
extern
ostream& operator << (ostream & out,
		      const List<T>& lst);

template <class T>
class List_for_each {
public:
  void for_each(const List<T>& lst);
  virtual void the_proc(T) = 0;
};

template <class T, class S>
class List_map {
public:
  List<S>* map(const List<T>& lst);
  virtual S the_proc(T) = 0;
};

template <class T, class S>
class List_flat_recur {
public:
  S flat_recur(const List<T>& lst);
  virtual S seed() = 0;
  virtual S the_proc(T, S) = 0;
};

#include "CookList.C"  // hack so it works

#endif