/*
 * It's easier to have our own list class rather than rely on the
 * C++ standard to actually work
 */

template <class T>
class node {
 public:
  node(const T & v,node<T> *n = 0) { value = v ; nptr = n ; }

  void doit(void (*f)(T)) { (*f)(value) ; }
  node<T> *next(void) { return nptr ; }

  friend ostream & operator << (ostream &,const node<T> &) ;
  ostream & deref(ostream &) const ;

  void deref_destroy(void) ;
 private:
  T value ;
  node<T> *nptr ;
} ;

template <class T>
class list {
 public:
  list(void) { first = 0 ; }
  list(const T & val) { first = new node<T>(val) ; }
  void insert(const T &val) { first = new node<T>(val,first) ; }

  friend ostream & operator << (ostream &,const list<T> &) ;
  void map (void (*f)(T))
    {
      node<T> *tmp = first ;
      while(tmp != 0)
	{
	  tmp->doit(f) ;
	  tmp = tmp->next() ;
	}
    }
  ostream & deref(ostream &) const ;

  void deref_destroy(void) ;
 private:
  node<T> *first ;
} ;

template <class T>
void node<T>::deref_destroy (void)
{
  delete value ;
}

template <class T>
ostream & node<T>::deref (ostream &out)
const
{
  out << *value ;
  return out ;
}

template <class T>
ostream & operator << (ostream &out, const node<T> & n)
{
  out << n.value ;
  return out ;
}

template <class T>
ostream & operator << (ostream &out, const list<T> & l)
{
  node<T> *tmp = l.first ;
  while(tmp != 0)
    {
      out << *tmp << ' ' ;
      tmp = tmp->next() ;
    }
  return out ;
}

template <class T>
ostream & list<T>::deref (ostream &out)
const
{
  node<T> *tmp = first ;
  while(tmp != 0)
    {
      tmp->deref(out) ;
      out << ' ' ;
      tmp = tmp->next() ;
    }
  return out ;
}

template <class T>
void list<T>::deref_destroy(void)
{
  node<T> *tmp = first ;
  node<T> *store ;
  while(tmp != 0)
    {
      store = tmp->next() ;
      tmp->deref_destroy() ;
      delete tmp ;
      tmp = store ;
    }
}