tree.c

压缩包里面的都是精致的基本C语言小程序

#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;
}