//
// See copyright.h for copyright notice and limitation of liability
// and disclaimer of warranty provisions.
//
#include "copyright.h"

#ifndef TREE_H
#define TREE_H
///////////////////////////////////////////////////////////////////////////
//
// file: tree.h
//
// This file defines the basic class of tree node and list
//
///////////////////////////////////////////////////////////////////////////

#include "utils.h"
#include <iostream>

/////////////////////////////////////////////////////////////////////
//
//  tree_node
//
//   All APS nodes are derived from tree_node.  There is a
//   protected field:
//       int line_number     line in the source file from which this node came;
//                           this is read from a global variable when the
//                           node is created.
//
//
//
//   The public methods are:
//       tree_node()
//         builds a new tree_node.  The type field is NULL, the
//         line_number is set to the value of the global yylineno.
//
//       void dump(std::ostream& s,int n);
//         dump is a pretty printer for tree nodes.  The std::ostream argument
//         is the output stream on which the node is to be printed; n is
//         the number of spaces to indent the output.
//
//       int get_line_number();  return the line number
//       Symbol get_type();      return the type
//
//       tree_node *set(tree_node *t)
//           sets the line number and type of "this" to the values in
//           the argument tree_node.  Returns "this".
//
//
////////////////////////////////////////////////////////////////////////////
class tree_node {
protected:
  int line_number; // stash the line number when node is made
public:
  tree_node();
  virtual tree_node *copy() = 0;
  virtual void dump(std::ostream &stream, int n) = 0;
  int get_line_number();
  tree_node *set(tree_node *);
  virtual ~tree_node() {}
};

///////////////////////////////////////////////////////////////////
//
//  Lists of APS objects are implemented by the "list_node"
//  template.  List elements have type Elem.  The interface is:
//
//     tree_node *copy()
//     list_node<Elem> *copy_list()
//
//     These functions have identical behavior; they return a deep
//     copy of the list (i.e., all elements of the list are copied).
//     When possible, the second function should be used, as it
//     has a more accurate result type.  The "copy" function is for
//     copying an entire APS tree of which a list is just one component
//     (see the definition of copy() in class tree_node).
//
//     Elem nth(int n);
//     returns the nth element of a list.  If the list has fewer than n
//     elements, an error is generated.
//
//     int first();
//     int next(int n);
//     int more(int n);
//       These three functions define a simple iterator for stepping through
//     list elements in order.  If l is a list, a typical use would be:
//
//     for(int i = l->first(); l->more(i); i = l->next(i))
//         ... operate on l->nth(i) ...
//
//
//     int len()
//     returns the length of the list
//
//     nth_length(int n, int &len);
//     Returns the nth element of the list or NULL if there are not n elements.
//     "len" is set to the length of the list.  This method is used internally
//     by the APS package to efficiently traverse the list representation.
//
//     static list_node<Elem> *nil();
//     static list_node<Elem> *single(Elem);
//     static list_node<Elem> *append(list_node<Elem> *, list_node<Elem> *);
//
//     These three functions construct an empty list, a list of one element,
//     and append two lists, respectively.  Note that the functions are static;
//     there is no "this" parameter.  Example uses:
//
//     list_node<Elem>::nil();
//     list_node<Elem>::single(e);     where "e" has type Elem
//     list_node<Elem>::append(l1,l2);
//
//////////////////////////////////////////////////////////////////////////////

template <class Elem> class list_node;

template <class Elem> class list_node_iterator {
  list_node<Elem> *list;
  int index;

public:
  list_node_iterator(list_node<Elem> *list_) : list(list_), index(0) {}
  list_node_iterator(list_node<Elem> *list_, int index_)
      : list(list_), index(index_) {}

  list_node_iterator<Elem> &operator++() {
    ++index;
    return *this;
  }
  Elem operator*() const { return list->nth(index); }
  bool operator!=(const list_node_iterator<Elem> &rhs) const {
    return index != rhs.index;
  }
};

template <class Elem> class list_node : public tree_node {
public:
  tree_node *copy() { return copy_list(); }
  Elem nth(int n);
  //
  // The next three define a simple iterator.
  //
  int first() { return 0; }
  int next(int n) { return n + 1; }
  int more(int n) { return (n < len()); }

  virtual list_node<Elem> *copy_list() = 0;
  virtual int len() = 0;
  virtual Elem nth_length(int n, int &len) = 0;

  static list_node<Elem> *nil();
  static list_node<Elem> *single(Elem);
  static list_node<Elem> *append(list_node<Elem> *l1, list_node<Elem> *l2);
};
template <class Elem> list_node_iterator<Elem> begin(list_node<Elem> &list) {
  return list_node_iterator<Elem>(&list);
}

template <class Elem> list_node_iterator<Elem> end(list_node<Elem> &list) {
  return list_node_iterator<Elem>(&list, list.len());
}

template <class Elem> list_node_iterator<Elem> begin(list_node<Elem> *list) {
  return list_node_iterator<Elem>(list);
}

template <class Elem> list_node_iterator<Elem> end(list_node<Elem> *list) {
  return list_node_iterator<Elem>(list, list->len());
}

template <class Elem> class nil_node : public list_node<Elem> {
public:
  list_node<Elem> *copy_list();
  int len();
  Elem nth_length(int n, int &len);
  void dump(std::ostream &stream, int n);
};

template <class Elem> class single_list_node : public list_node<Elem> {
  Elem elem;

public:
  single_list_node(Elem t) { elem = t; }
  list_node<Elem> *copy_list();
  int len();
  Elem nth_length(int n, int &len);
  void dump(std::ostream &stream, int n);
};

template <class Elem> class append_node : public list_node<Elem> {
private:
  list_node<Elem> *some, *rest;

public:
  append_node(list_node<Elem> *l1, list_node<Elem> *l2) {
    some = l1;
    rest = l2;
  }
  list_node<Elem> *copy_list();
  int len();
  Elem nth_length(int n, int &len);
  void dump(std::ostream &stream, int n);
};

template <class Elem> single_list_node<Elem> *list(Elem x);
template <class Elem> append_node<Elem> *cons(Elem x, list_node<Elem> *l);
template <class Elem> append_node<Elem> *xcons(list_node<Elem> *l, Elem x);

template <class Elem> list_node<Elem> *list_node<Elem>::nil() {
  return new nil_node<Elem>();
}
template <class Elem> list_node<Elem> *list_node<Elem>::single(Elem e) {
  return new single_list_node<Elem>(e);
}
template <class Elem>
list_node<Elem> *list_node<Elem>::append(list_node<Elem> *l1,
                                         list_node<Elem> *l2) {
  return new append_node<Elem>(l1, l2);
}

///////////////////////////////////////////////////////////////////////////
//
// list_node::nth
//
// function to find the nth element of the list
//
///////////////////////////////////////////////////////////////////////////

template <class Elem> Elem list_node<Elem>::nth(int n) {
  int len;
  Elem tmp = nth_length(n, len);

  if (tmp) {
    return tmp;
  }
  throw std::runtime_error("nth: outside the range of the list");
}

///////////////////////////////////////////////////////////////////////////
//
// nil_node::copy_list
//
// return the deep copy of the nil_node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> list_node<Elem> *nil_node<Elem>::copy_list() {
  return new nil_node<Elem>();
}

///////////////////////////////////////////////////////////////////////////
//
// nil_node::len
//
// return the length of the nil_node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> int nil_node<Elem>::len() { return 0; }

///////////////////////////////////////////////////////////////////////////
//
// nil_node::nth_length
//
// return the nth element on the list
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> Elem nil_node<Elem>::nth_length(int, int &len) {
  len = 0;
  return NULL;
}

///////////////////////////////////////////////////////////////////////////
//
// nil_node::dump
//
// dump for list node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> void nil_node<Elem>::dump(std::ostream &stream, int n) {
  stream << pad(n) << "(nil)\n";
}

///////////////////////////////////////////////////////////////////////////
//
// single_list_node::copy_list
//
// return the deep copy of the single_list_node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> list_node<Elem> *single_list_node<Elem>::copy_list() {
  return new single_list_node<Elem>((Elem)elem->copy());
}

///////////////////////////////////////////////////////////////////////////
//
// single_list_node::len
//
// return the length of the single_list_node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> int single_list_node<Elem>::len() { return 1; }

///////////////////////////////////////////////////////////////////////////
//
// single_list_node::nth_length
//
// return the nth element on the list
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> Elem single_list_node<Elem>::nth_length(int n, int &len) {
  len = 1;
  if (n)
    return NULL;
  else
    return elem;
}

///////////////////////////////////////////////////////////////////////////
//
// single_list_node::dump
//
// dump for list node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem>
void single_list_node<Elem>::dump(std::ostream &stream, int n) {
  elem->dump(stream, n);
}

///////////////////////////////////////////////////////////////////////////
//
// append_node::copy_list
//
// return the deep copy of the append_node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> list_node<Elem> *append_node<Elem>::copy_list() {
  return new append_node<Elem>(some->copy_list(), rest->copy_list());
}

///////////////////////////////////////////////////////////////////////////
//
// append_node::len
//
// return the length of the append_node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> int append_node<Elem>::len() {
  return some->len() + rest->len();
}

///////////////////////////////////////////////////////////////////////////
//
// append_node::nth_length
//
// return the nth element on the list
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> Elem append_node<Elem>::nth_length(int n, int &len) {
  int rlen;
  Elem tmp = some->nth_length(n, len);

  if (!tmp) {
    tmp = rest->nth_length(n - len, rlen);
    len += rlen;
  }
  return tmp;
}

///////////////////////////////////////////////////////////////////////////
//
// append_node::dump
//
// dump for list node
//
///////////////////////////////////////////////////////////////////////////
template <class Elem>
void append_node<Elem>::dump(std::ostream &stream, int n) {
  int i, size;

  size = len();
  stream << pad(n) << "list\n";
  for (i = 0; i < size; i++)
    this->nth(i)->dump(stream, n + 2);
  stream << pad(n) << "(end_of_list)\n";
}

///////////////////////////////////////////////////////////////////////////
//
// list
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> single_list_node<Elem> *list(Elem x) {
  return new single_list_node<Elem>(x);
}

///////////////////////////////////////////////////////////////////////////
//
// cons
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> append_node<Elem> *cons(Elem x, list_node<Elem> *l) {
  return new append_node<Elem>(list(x), l);
}

///////////////////////////////////////////////////////////////////////////
//
// xcons
//
///////////////////////////////////////////////////////////////////////////
template <class Elem> append_node<Elem> *xcons(list_node<Elem> *l, Elem x) {
  return new append_node<Elem>(l, list(x));
}

#endif /* TREE_H */