#include <stdio.h>#include "mystdlib.h"#include "nat.h"#include "commonInter.h"#include "plist.h"#include "property.h"#include "linkedList.h"#include "error.h"#include "counter.h"#include "dot.h"#include "tree.h"struct tree{  linkedList vs;  str treeName;};struct vertex{  tyVft vft;  poly info;  linkedList edges;  plist plist;};struct edge{  tyVft vft;  struct vertex *from;  struct vertex *to;  plist plist;};typedef struct vertex *vertex;typedef struct edge *edge;static struct tyVft vertexVft;static struct tyVft edgeVft;static int vertexFlag = 1;static int edgeFlag = 1;static int vertexEquals (poly v1, poly v2);static plist vertexGetPlist (poly data);static int vertexHashCode (poly data);static str vertexToString (poly data);static int edgeEquals (poly v1, poly v2);static plist edgeGetPlist (poly data);static int edgeHashCode (poly data);static str edgeToString (poly data);static vertex searchVertex (tree t, poly data);tree newTree (str treeName){  tree t = checkedMalloc (sizeof (*t));  t->vs = newLinkedList ();  t->treeName = treeName;    return t;}str treeName (tree t){  return t->treeName;}static vertex newVertex (poly data){  vertex v = checkedMalloc (sizeof (*v));  if (vertexFlag)  {    vertexFlag--;    vertexVft.equals = vertexEquals;    vertexVft.getPlist = vertexGetPlist;    vertexVft.hashCode = vertexHashCode;    vertexVft.toString = vertexToString;  }  v->vft = &vertexVft;  v->info = data;  v->edges = newLinkedList ();  v->plist = newPlist ();    return v;}static vertex searchVertex (tree t, poly data){  linkedList p = linkedListGetFirst (t->vs);    tyEquals eq = getVft (data)->equals;  while (p)  {    if (eq (data, (((vertex)(p->data))->info)))    {      return p->data;    }    else    {      p = p->next;    }  }  error ("no this data: tree.c\n");  return NULL;}static int vertexEquals (poly v1, poly v2){  return plistEquals (((vertex)v1)->plist, ((vertex)v2)->plist);}static plist vertexGetPlist (poly data){  return ((vertex)(data))->plist;}static int vertexHashCode (poly data){  // a trivial but correct one  return 0;}static str vertexToString (poly data){  exception ("not implemented yet\n");  return NULL;}/*static edge newEdge (tree t, poly from, poly to){  edge e = checkedMalloc (sizeof (*e));  if (edgeFlag)  {    edgeFlag--;    edgeVft.equals = edgeEquals;    edgeVft.getPlist = edgeGetPlist;    edgeVft.hashCode = edgeHashCode;    edgeVft.toString = edgeToString;  }  e->vft = &edgeVft;  vertex fromVertex = searchVertex (t, from);  vertex toVertex = searchVertex (t, to);    e->from = fromVertex;  e->to = toVertex;  e->plist = newPlist ();    return e;}*/static edge newEdge2 (vertex fromVertex, vertex toVertex){  edge e = checkedMalloc (sizeof (*e));  if (edgeFlag)  {    edgeFlag--;    edgeVft.equals = edgeEquals;    edgeVft.getPlist = edgeGetPlist;    edgeVft.hashCode = edgeHashCode;    edgeVft.toString = edgeToString;  }  e->vft = &edgeVft;  e->from = fromVertex;  e->to = toVertex;  e->plist = newPlist ();    return e;}static int edgeEquals (poly v1, poly v2){  return plistEquals (((edge)v1)->plist, ((edge)v2)->plist);  }static plist edgeGetPlist (poly data){  return ((edge)data)->plist;}static int edgeHashCode (poly data){  // a trivial but correct one  return 0;}static str edgeToString (poly data){  exception ("not implemented yet: tree.c\n");  return NULL;}void treeInsertVertex (tree g, poly x){  vertex v = newVertex (x);  linkedListInsertHead (g->vs, v);  return;}void treeInsertEdge (tree t, poly from, poly to){    vertex fromVertex = searchVertex (t, from);  vertex toVertex = searchVertex (t, to);  edge e = newEdge2 (fromVertex, toVertex);  linkedListInsertHead (fromVertex->edges, e);    return;}void treeListAllVertex (tree t, tyVisit visit){  linkedList l = linkedListGetFirst (t->vs);    while (l)  {    visit (((vertex)(l->data))->info);    l = l->next;  }  return;}void treeToJpg (tree t, str fname){  dot d = newDot ();    str emptyStr = newStr ("");  str name = strConcat (t->treeName, fname);    linkedList l = linkedListGetFirst (t->vs);    while (l)  {    vertex v = (vertex)(l->data);    str sFrom = getVft (v->info)->toString (v->info);    linkedList es = linkedListGetFirst (v->edges);    while (es)    {      edge e = (edge)(es->data);      str sTo = getVft (e->to->info) ->toString (e->to->info);      dotInsert (sFrom, sTo, emptyStr, d);      es = es->next;    }    l = l->next;  }    dotToJpg (d, strToCharStar (name));}void treePreOrderDoit (vertex v, property visited, tyVisit visit){  if (visit)  {    printf ("\nnow visiting vertex: ");    visit (v->info);  }  propertyAdd (visited, v, newNat (1));  linkedList edges = linkedListGetFirst (v->edges);    while (edges)  {    edge e = edges->data;    vertex to = e->to;    poly value = propertyPeek (visited, to);    if (!value)      treePreOrderDoit (to, visited,visit);    edges = edges->next;  }  return;}void treePreOrder (tree t, poly start, tyVisit visit){  linkedList vs = linkedListGetFirst (t->vs);  vertex stv = searchVertex (t, start);  property visited = newProperty ();    if (!stv)    treePreOrderDoit (stv, visited, visit);      while (vs)  {    vertex current = vs->data;    poly value = propertyPeek (visited, current);    if (!value)      treePreOrderDoit (current, visited, visit);    vs = vs->next;  }    propertyDestroy (visited);  return;}