#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#	Makefile
#	Graphs.c
#	Graphs.h
#	splaylib.c
#	splaylib.h
#	testgraph.c
#	graph1
# This archive created: Wed Mar  5 11:43:20 1997
export PATH; PATH=/bin:/usr/bin:$PATH
if test -f 'Makefile'
then
	echo shar: "will not over-write existing file 'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
CC=c89
CFLAGS=-g -I.
LFLAGS=-g -lm
SRC=Graphs.c splaylib.c
OBJS=Graphs.o splaylib.o testgraph.o

all: Graphs.o splaylib.o testgraph

testgraph: $(OBJS)
	$(CC) $(OBJS) -o $@ $(LFLAGS)

testgraph.o: testgraph.c

splaylib.o: splaylib.c

splaylib.c: splaylib.h

Graphs.o: Graphs.c

Graphs.c: Graphs.h

SHAR_EOF
fi
if test -f 'Graphs.c'
then
	echo shar: "will not over-write existing file 'Graphs.c'"
else
cat << \SHAR_EOF > 'Graphs.c'
/*
 **     Copyright (C) 1997  Rick Romero [rickr+@cmu.edu]
 **
 **     This program is free software; you can redistribute it and/or modify
 **     it under the terms of the GNU General Public License as published by
 **     the Free Software Foundation; either version 1, or (at your option)
 **     any later version.
 **     
 **     This program is distributed in the hope that it will be useful,
 **     but WITHOUT ANY WARRANTY; without even the implied warranty of
 **     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 **     GNU General Public License for more details.
 **     
 **     You should have received a copy of the GNU General Public License
 **     along with this program; if not, write to the Free Software
 **     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include "splaylib.h"
#include "Graphs.h"

#ifdef DEBUG
#define dprintf(x) printf x
#else
#define dprintf(x) 
#endif



typedef struct NullList_st {
  void *obj;
  struct NullList_st *next, *prev;
} NullList_t, *NullList_p;



PermSet_p GetTheta(ComboGraph_p g) {
  if (g)
    return g->Theta;
  else
    return NULL;
}

PermSet_p GetThetaStar(ComboGraph_p g) {
  if (g)
    return (MakeThetaStar(g));
  else
    return NULL;
}


int CompareEdges(void *o1, void *o2) {
  Node_p n11, n12, n21, n22;

  n11 = ((Edge_p) o1)->n1;
  n12 = ((Edge_p) o1)->n2;
  n21 = ((Edge_p) o2)->n1;
  n22 = ((Edge_p) o2)->n2;
  return ((n11 < n21) ? -1 :
	  ((n11 > n21) ? 1 :
	   ((n12 < n22) ? -1 : (n12 > n22))));

}

int CompareID(void *o1, void *o2) {
  int n1, n2;
  n1 = ((Node_p) o1)->ID;
  n2 = ((Node_p) o2)->ID;

  return (n1 < n2 ? -1 : (n2 < n1 ? 1 : 0));
}

NullList_p CopyList(NullList_p l) {
  NullList_p head, current, next;
  
  if (l) {
    head = (NullList_p) malloc(sizeof(NullList_t));
    head->obj = l->obj;
    head->prev = NULL;
    current = head;
    while (l->next) {
      l = l->next;
      current->next = (NullList_p) malloc(sizeof(NullList_t));
      current->next->prev = current;
      current = current->next;
      current->obj = l->obj;
    }
    current->next = NULL;
    return head;
  } else {
    return NULL;
  }
}





ComboGraph_p MakeComboGraph(void) {
  ComboGraph_p g;

  g = (ComboGraph_p) malloc(sizeof(ComboGraph_t));
/*
  g->E = (PermList_p) malloc(sizeof(PermList_t));
  g->E->next = g->E->prev = NULL;
  g->E->edge = NULL;
  g->Theta = (PermSet_p) malloc(sizeof(PermSet_p));
  g->Inv   = (PermSet_p) malloc(sizeof(PermSet_p));
  g->Theta->next = g->Theta->prev = NULL;
  g->Theta->list = NULL;
  g->Inv->next = g->Inv->prev = NULL;
  g->Inv->list = NULL;
*/
  g->E     = NULL;
  g->Theta = NULL;
  g->Inv   = NULL;
  g->Es    = CreateSplay(CompareEdges);
  g->Vs    = CreateSplay(CompareID);
  g->nodes = g->edges = 0;
  g->components = -1;
  g->cstale = g->tstale = 1;

  return g;

}


Node_p MakeNode(ComboGraph_p g, Point_t p) {
  Node_p n;

  n = (Node_p) malloc(sizeof(Node_t));
  n->ID =  (g->nodes)++;
  n->p = p;
  SplayInsert(g->Vs, n);
  n->cycle = NULL;
  return n;

}


PermList_p NewThetaPermList(ComboGraph_p g) {
  PermSet_p set;
  PermList_p list;

  list = (PermList_p) malloc(sizeof(PermList_t));
  set   = (PermSet_p)  malloc(sizeof(PermSet_t));
  list->next = list->prev = list;
  set->list = list;
  set->next = g->Theta;
  set->prev = NULL;
  if (g->Theta)
    g->Theta->prev = set;
  g->Theta = set;
  return list;

}


PermList_p NewInvPermList(ComboGraph_p g) {
  PermSet_p set;
  PermList_p list;

  list = (PermList_p) malloc(sizeof(PermList_t));
  set   = (PermSet_p)  malloc(sizeof(PermSet_t));
  list->next = list->prev = list;
  set->list = list;
  set->next = g->Inv;
  set->prev = NULL;
  if (g->Inv)
    g->Inv->prev = set;
  g->Inv = set;
  return list;

}

int AddEdgeToCycle(ComboGraph_p g, Edge_p e, PermList_p p) {
  double theta, theta1, theta2;
  PermList_p next, current;


  if (p->edge) {
    current = (PermList_p) malloc(sizeof(PermList_t));
    if (current == NULL)
      return -1;

    current->edge = e;
    e->cycle = current;

    next = p->next;

    /* Get the fixed theta and theta1 */
    theta1 = atan2(p->edge->n1->p.y - p->edge->n2->p.y,
		   p->edge->n1->p.x - p->edge->n2->p.x);
    theta = atan2(p->edge->n1->p.y - e->n2->p.y,
		  p->edge->n1->p.x - e->n2->p.x) - theta1;
    /* Scale to 0-2PI if necessary */
    if (theta < 0.0)
      theta += 2 * M_PI;

    while(next != p) {
      theta2 = atan2(p->edge->n1->p.y - next->edge->n2->p.y,
		     p->edge->n1->p.x - next->edge->n2->p.x) - theta1;
      if (theta2 < 0.0)
	theta2 += 2 * M_PI;

      /* Check if theta is "between" theta1 and theta2 in the
       * counter-clockwise direction.
       */
      if (theta < theta2) {
	break;
      } 
      next = next->next;
    }
    /* OK, insert here */
    current->next = next;
    current->prev = next->prev;
    current->prev->next = current;
    next->prev = current;
    

  } else {
    /* oh, shit, there wasn't anything to check against, just throw it in. */
    p->edge = e;
    p->next = p->prev = p;
    e->cycle = p;
  }

  return 0;
}


void AddEdgeToList(ComboGraph_p g, Edge_p e) {
  PermList_p current;
  
  current = (PermList_p) malloc(sizeof(PermList_t));
  current->edge = e;
  current->next = g->E;
  if (g->E)
    g->E->prev = current;
  current->prev = NULL;
  g->E = current;

}

void RemoveEdgeFromList(ComboGraph_p g, Edge_p e) {
  PermList_p current;

  if (e == g->E->edge) {
    current = g->E;
    g->E = g->E->next;
    current->next->prev = NULL;
  } else {
    current = g->E;
    while (current->edge != e) {
      current = current->next;
    }
    if (current->prev)
      current->prev->next = current->next;
    if (current->next)
      current->next->prev = current->prev;
  }
  free(current);

}





int AddEdge(ComboGraph_p g, Node_p n1, Node_p n2) {
  Edge_p e, e2, tmp_e;
  Node_p ln1, ln2;
  PermList_p cycle;
  PermSet_p  set;

  /* Is this a valid Node? */
  ln1 = (Node_p) SplayAccess(g->Vs, n1);
  if ((ln1 == NULL) || (CompareID(ln1, n1) != 0)) {
    return -1;
  }

  ln2 = (Node_p) SplayAccess(g->Vs, n2);
  if ((ln2 == NULL) || (CompareID(ln2, n2) != 0)) {
    return -1;
  }

  if (ln1 == ln2) {
    /* Shit, we have an edge from a node to the same node... don't allow
     * that */
    return 0;
  }

  g->cstale = 1;
  g->tstale = 1;
  e = (Edge_p) malloc(sizeof(Edge_t));
  e->ID = (g->edges)++;
  e->n1 = n1;
  e->n2 = n2;
  tmp_e = SplayAccess(g->Es, e);
  if (tmp_e && CompareEdges(tmp_e, e) == 0) {
    /* This is a duplicate, chuck it. */
    free(e);
    (g->edges)--;
    return 0;
  }
  /* Make the reverse edge, don't bother with putting it in the tree */
  e2 = (Edge_p) malloc(sizeof(Edge_t));
  e2->ID = -(e->ID);
  e2->n1 = n2;
  e2->n2 = n1;
  tmp_e = SplayAccess(g->Es, e2); 
  if (tmp_e && CompareEdges(tmp_e, e2) == 0) {
    /* Duplicate, dammit */
    free(e);
    free(e2);
    (g->edges)--;
    return 0;
  }


  SplayInsert(g->Es, e);
  
  /* Yeah, have a link from e to e_bar, and vice-versa */
  /* This way, I don't really need to keep track of Theta_Star */
  e->bar = e2;
  e2->bar = e;

  /* Also put them in a linear linked list */
  AddEdgeToList(g, e);
  AddEdgeToList(g, e2);

  /* Check if this edge adds a link between two permutation cycles */
  if (ln1->cycle == NULL) {
    if (ln2->cycle == NULL) {
      /* Hmm, not in any permutation cycle, better make one */
      /* For Theta, the edge goes from Node 1 to Node 2     */
      cycle = NewThetaPermList(g);
      cycle->edge = e;
      e->cycle = cycle;
      ln1->cycle = cycle;

      if (ln1 != ln2) {
	cycle = NewThetaPermList(g);
	cycle->edge = e2;
	e2->cycle = cycle;
	ln2->cycle = cycle;
      } else {
	cycle->next = (PermList_p) malloc(sizeof(PermList_t));
	cycle->next->next = cycle;
	cycle->next->prev = cycle->next;
	cycle->prev = cycle->next;
	cycle->next->edge = e2;
	e2->cycle = cycle->next;
      }
    } else {
      /* OK, Node 1 is not in a cycle, Node 2 is... */
      /* Swap the nodes and edges, just handle as a single case below */
      Node_p tmp_n;
      Edge_p tmp_e;
      tmp_n = ln1;
      ln1 = ln2;
      ln2 = tmp_n;
      tmp_e = e;
      e = e2;
      e2 = tmp_e;
      
      /* hee-hee, I love goto statements, reminds me of the good
       * old days of Basic & assembler coding on my Apple //e */
      goto HandleSymmetric;
    }
  } else {
    /* OK, Node 1 is in a cycle... */
    if (ln2->cycle == NULL) {
      /* Node 2 is not */
    HandleSymmetric:
      /* We have a new edge coming in to node 1, but nothing is coming out
       * from node 2: Need to put node 2 in a cycle for the n2->n1 edge,
       * and update theta for node 1, since we have a new edge n1->n2.
       */
      if (AddEdgeToCycle(g, e, ln1->cycle)) {
	/* Got some error, that's no good. */
	return -1;
      }
      cycle = NewThetaPermList(g);
      cycle->edge = e2;
      e2->cycle = cycle;
      ln2->cycle = cycle;
    } else {
      /* and Node 2 is in a cycle... Just update both cycle maps. 
       * Can they be in the same cycle? seems like that might be an
       * error, since that would be an edge from node x to node x.
       * I'm gonna throw away duplicate edges here...
       */
      

      if (AddEdgeToCycle(g, e, ln1->cycle)) {
	return -1;
      }
      if (AddEdgeToCycle(g, e2, ln2->cycle)) {
	return -1;
      }
    }
  }
  return 0;

}




void PrintGraph(ComboGraph_p g) {
  PermSet_p theta;
  PermList_p cycle, start;

  printf("Nodes:  %d\nEdges: %d\n", g->nodes, g->edges);
  printf("Connected Components: %d\n", ComputeConnectedComponents(g));
  printf("Genus: %d\n\n", GetGenus(g));
  printf("Theta:\n");
  theta = g->Theta;
  while (theta) {
    printf("(");
    cycle = start = theta->list;
    printf("(%d, %d)", cycle->edge->n1->ID, cycle->edge->n2->ID);
    while (cycle->next != start) {
      cycle = cycle->next;
      printf(", (%d, %d)", cycle->edge->n1->ID, cycle->edge->n2->ID);
    }
    printf(")\n");
    theta = theta->next;
  }

  theta = MakeThetaStar(g);
  printf("\nThetaStar:\n");
  while (theta) {
    printf("(");
    cycle = start = theta->list;
    printf("(%d, %d)", cycle->edge->n1->ID, cycle->edge->n2->ID);
    while (cycle->next != start) {
      cycle = cycle->next;
      printf(", (%d, %d)", cycle->edge->n1->ID, cycle->edge->n2->ID);
    }
    printf(")\n");
    theta = theta->next;
  }

}


PermList_p FindInSet(PermSet_p sets, Edge_p e) {
  PermList_p s, l;

  if (sets == NULL) return NULL;

  while(sets) {
    s = l = sets->list;
    do {
      if (e == l->edge)
	return l;
      l = l->next;
    } while(s != l);
    sets = sets->next;
  }

  return NULL;

}


      
void FreePermSet(PermSet_p s) {
  PermList_p list, next;
  PermSet_p next_set;

  while (s) {
    list = s->list;
    if (list)
      list->prev->next = NULL;
    while (list) {
      next = list->next;
      free(list);
      list = next;
    }
    next_set = s->next;
    free(s);
    s = next_set;
  }
}


void RemoveFromList(PermList_p *l_p, Edge_p e) {
  PermList_p c;

  c = *l_p;
  while (e != c->edge) {
    c = c->next;
  }

  if (c->next == c->prev) {
    free(c);
    *l_p = NULL;
  } else if ((*l_p) == c) {
    if (c->prev)
      c->prev->next = c->next;
    if (c->next)
      c->next->prev = c->prev;
    *l_p = c->next;
    free(c);
  } else {
    if (c->prev)
      c->prev->next = c->next;
    if (c->next)
      c->next->prev = c->prev;
    free(c);
  }
}



PermSet_p MakeThetaStar(ComboGraph_p g) {
  PermList_p edges, cycle, next;
  Edge_p ebar, e, start, theta;

  if (g->tstale == 0)
    return g->Inv;

  edges = (PermList_p) CopyList((NullList_p) (g->E));

  FreePermSet(g->Inv);

  while (edges) {
    start = e = edges->edge;
    RemoveFromList(&edges, e);
    cycle = NewInvPermList(g);
    cycle->edge = e;
    ebar = e->bar;
    theta = ebar->cycle->next->edge;      
    while (theta != start) {
      next = (PermList_p) malloc(sizeof(PermList_t));
      next->prev = cycle;
      next->next = cycle->next;
      next->next->prev = next;
      cycle->next = next;
      cycle = next;
      next->edge = theta;
      RemoveFromList(&edges, theta);
      e = theta;
      ebar = e->bar;
      theta = ebar->cycle->next->edge;
    }
  }

  g->tstale = 0;

  return g->Inv;

}


void EdgeDFS(PermList_p e) {
  PermList_p cycle, start;

  if (e->edge->visited && e->edge->bar->visited)
    return;

  e->edge->visited = 1;
  start = e->edge->cycle;
  cycle = start->next;
  /* For every edge going out from this node, follow the back pointer */
  while (cycle != start) {
    dprintf(("At edge %d: ", cycle->edge->ID));
    if (cycle->edge->visited == 0) {
      /* Follow the edge pointing into this node */
      dprintf(("Recurse on edge %d\n", cycle->edge->bar->ID));
      cycle->edge->visited = 1;
      EdgeDFS(cycle->edge->bar->cycle);
    } else {
      dprintf(("\n"));
    }
    cycle = cycle->next;
  }

  e->edge->bar->visited = 1;
  start = e->edge->bar->cycle;
  cycle = start->next;
  /* Apply the inverse operator, track through that cycle. */
  while (cycle != start) {
    dprintf(("At edge %d: ", cycle->edge->ID));
    if (cycle->edge->visited == 0) {
      /* Follow the edge pointing into this node */
      dprintf(("Recurse on edge %d\n", cycle->edge->bar->ID));
      cycle->edge->visited = 1;
      EdgeDFS(cycle->edge->bar->cycle);
    } else {
      dprintf(("\n"));
    }
    cycle = cycle->next;
  }
}


/* Returns the number of connected components, not counting the nodes
 * added to the graph but not connected to anything.
 * Don't need to worry about these since we're counting nodes
 * and faces based on cycles in edges.
 */
int ComputeConnectedComponents(ComboGraph_p g) {
  PermList_p edges;
  int i=0;

  
  if (g->cstale == 0)
    return g->components;

  edges = g->E;
  while(edges) {
    edges->edge->visited = 0;
    edges = edges->next;
  }

  edges = g->E;
  while (edges) {
    i++;
    EdgeDFS(edges);
    edges = edges->next;
    while (edges && edges->edge->visited)
      edges = edges->next;
  }

  g->cstale = 0;
  g->components = i;
  return i;
}

int GetGenus(ComboGraph_p g)  {
  int i;
  PermSet_p s;

  MakeThetaStar(g);

  i = g->edges;
  s = g->Theta;
  while (s) {
    i--;
    s = s->next;
  }
  s = g->Inv;
  while (s) {
    i--;
    s = s->next;
  }
  i += (2 * ComputeConnectedComponents(g));
  return i;

}
SHAR_EOF
fi
if test -f 'Graphs.h'
then
	echo shar: "will not over-write existing file 'Graphs.h'"
else
cat << \SHAR_EOF > 'Graphs.h'
/*
 * Some code for handling graphs in the combinatorial fashion:
 *
 * This isn't C++ or Java, but the design is done using what I consider
 * to be a good data structures format. If you wanted to port this to C++
 * (which I personally think gains me nothing,) then it wouldn't be hard
 * to wrap some object defs around what I already have here and enforce
 * data hiding/abstraction. The splay tree code was written long long ago,
 * and has been robust for me for a while.
 *
 * Structures to know:
 *   Point_t, Node_p, Edge_p, PermList_p, PermSet_p, ComboGraph_p
 *
 * Functions to use:
 *   MakeComboGraph, MakeNode, AddEdge, GetGenus, PrintGraph,
 *   ComputeConnectedComponents, GetTheta, GetThetaStar
 *
 * Details:
 *   My take on the assignment was to generate an embedding into the
 *   combinatorial form, given an arbitrary graph in the plane.
 *   In this sense, it can be used as a dynamic library (although deletion
 *   of edges is not done, it could be,) that always keeps track of the
 *   nodes in the graph and the correct mapping of Theta.
 *   Calling sequences would look something like:
 *      
 *      g = MakeComboGraph();
 *      while(notdone) { p = getpoint(); MakeNode(g,p); notdone = dowork(); }
 *      ...
 *      while(notdone) { p1 = edgestart(); p2 = edgeend(); AddEdge(g, p1, p2);
 *                       notdone = domorework(); }
 *      ...
 *      c = ComputeConnectedComponents(g);
 *      ...
 *      g = GetGenus(g);
 *      ...
 *      PrintGraph(g);
 *      ...
 *
 *   If you want to work directly with the theta mapping, then it may be
 *   worth noting what it is, exactly. I've implented data structures in
 *   the following manner:
 *     
 *     Theta: A set of circular permutation lists (circular linked lists)
 *     
 *     Permutation Lists: A list of edges, possibly circularly linked
 *       and possibly not, such that going from the current to the
 *       element of the list is equivalent to applying theta.
 *
 *     Edges: Edges contain the mapping from e to ebar via a pointer to
 *       another edge. They also contain a mapping from e to e's location
 *       within a cycle of the permutation map theta. In other words,
 *       they have a pointer back into the permuation list (which is circular)
 *       so that you can apply theta to an edge given just the edge pointer.
 *       Oh, plus they also have two pointers to nodes which the edge connects.
 *     
 *     Nodes: Nodes are just points in 2D Euclidean space, but they have an
 *       ID field, and they have a pointer to the cycle in theta which they
 *       are equivalent to.
 *     
 *   Right, so what's a graph... A graph contains:
 *     A linked list of edges in insertion order
 *     A mapping Theta
 *     A mapping Inv (the Theta* mapping)
 *     An ordered tree of edges (ordering based on node equivalence)
 *     An ordered tree of nodes (based on node ID)
 *     The number of edges, vertices and connected components
 *   I use splay trees to maintain the ordered trees of edges and nodes.
 *   I keep that around so I can quickly check to see if an edge is a duplicate
 *   of some previous edge, and if the nodes are "valid" nodes, as in they
 *   were created via MakeNode, and everything was set up right.
 *
 *
 */

/*
 **     Copyright (C) 1997  Rick Romero [rickr+@cmu.edu]
 **
 **     This program is free software; you can redistribute it and/or modify
 **     it under the terms of the GNU General Public License as published by
 **     the Free Software Foundation; either version 1, or (at your option)
 **     any later version.
 **     
 **     This program is distributed in the hope that it will be useful,
 **     but WITHOUT ANY WARRANTY; without even the implied warranty of
 **     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 **     GNU General Public License for more details.
 **     
 **     You should have received a copy of the GNU General Public License
 **     along with this program; if not, write to the Free Software
 **     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#ifndef _Graphs_H_
#define _Graphs_H_

#include "splaylib.h"

typedef struct Point_st {
  int x, y;
} Point_t, *Point_p;


typedef struct Node_st {
  int   ID;
  Point_t p;
  struct PermutationList_st *cycle;
} Node_t, *Node_p;


typedef struct Edge_st {
  int    ID;
  Node_p n1, n2;
  struct PermutationList_st *cycle;
  struct Edge_st *bar;
  int    visited;
} Edge_t, *Edge_p;


typedef struct PermutationList_st {
  Edge_p edge;
  struct PermutationList_st *next, *prev;
} PermList_t, *PermList_p;

typedef struct PermutationSet_st {
  PermList_p list;
  struct PermutationSet_st *next, *prev;
} PermSet_t, *PermSet_p;


typedef struct ComboGraph_st {
  PermList_p  E;              /* Bunch of edges  */
  PermSet_p   Theta;          /* Cycles          */
  PermSet_p   Inv;            /* Theta*          */
  SplayTree_p Es;             /* Ordered Edges   */
  SplayTree_p Vs;             /* Ordered Nodes   */
  int         nodes;          /* Num nodes       */
  int         edges;          /* Num edges       */
  int         components;     /* Connected comps */ 
  int         tstale;         /* Stale Theta     */
  int         cstale;         /* Stale components*/
  
} ComboGraph_t, *ComboGraph_p;


ComboGraph_p MakeComboGraph(void);

Node_p    MakeNode(ComboGraph_p g, Point_t p);
int       AddEdge(ComboGraph_p g, Node_p p1, Node_p p2);
int       GetGenus(ComboGraph_p g);
void      PrintGraph(ComboGraph_p g);
int       ComputeConnectComponents(ComboGraph_p g);
PermSet_p GetTheta(ComboGraph_p g);
PermSet_p GetThetaStar(ComboGraph_p g);
PermSet_p MakeThetaStar(ComboGraph_p g);

#endif

SHAR_EOF
fi
if test -f 'splaylib.c'
then
	echo shar: "will not over-write existing file 'splaylib.c'"
else
cat << \SHAR_EOF > 'splaylib.c'
/*
 **     Copyright (C) 1995  Rick Romero
 **
 **     This program is free software; you can redistribute it and/or modify
 **     it under the terms of the GNU General Public License as published by
 **     the Free Software Foundation; either version 1, or (at your option)
 **     any later version.
 **     
 **     This program is distributed in the hope that it will be useful,
 **     but WITHOUT ANY WARRANTY; without even the implied warranty of
 **     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 **     GNU General Public License for more details.
 **     
 **     You should have received a copy of the GNU General Public License
 **     along with this program; if not, write to the Free Software
 **     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct SplayNode {
  struct SplayNode *left, *right, *parent, *leftmin;
  void *obj;
} SNode;

typedef struct SplayTree {
  int (*compare)(void *, void *);
  SNode *root;
} STree;

STree *CreateSplay(int (*compare)());
SNode *SplayCreateNode();
void SplayDelete(STree *, void *);
void SplayInsert(STree *, void *);
void SplayJoin(STree *, STree *);
void SplaySplit(STree *, STree *, void *);
void *SplayAccess(STree *, void *);
void SplayNode(STree *, SNode *);
void S_splayr(STree *, SNode *);
void S_splayl(STree *, SNode *);
void S_splayrl(STree *, SNode *);
void S_splayrr(STree *, SNode *);
void S_splayll(STree *, SNode *);
void S_splaylr(STree *, SNode *);
STree *SplayCopyTree(STree *, void (*CopyNode)(SNode *, SNode *));
void SplayTraverse(STree *, void (*function)(void *));
SNode *SplayMinOfSubTree(SNode *);
void SplayCopySubTree(SNode *, SNode *, void (*CopyNode)(SNode *, SNode *));
void SplayInOrderTraverse(SNode *sn, void (*function)(void *));
void SplayDeleteTree(STree *);
void SplayDeleteSubTree(SNode *);
void SplayDestroyTree(STree *);
void SplayDestroySubTree(SNode *);
void SplayFreeNode(SNode *);



#define SNODE_MALLOC_SIZE 100


static SNode *SplayNodeFreeList = NULL;


void SplayFreeNode(SNode *sn) {
  if (sn) {
    sn->right = SplayNodeFreeList;
#ifdef DEBUG
    sn->left = NULL;
    sn->parent = NULL;
    sn->obj = NULL;
    sn->leftmin = NULL;
#endif
    SplayNodeFreeList = sn;
  }
}



STree *CreateSplay(int (*compare)(void *, void *)) {
  STree *stree;
  stree = (STree *) malloc(sizeof(STree));
  stree->compare = compare;
  stree->root = NULL;
  return stree;
}

SNode *SplayCreateNode() {
  SNode *tmp;

  if (SplayNodeFreeList) {
    tmp = SplayNodeFreeList;
    SplayNodeFreeList = tmp->right;
  } else {
    int i;
    tmp = (SNode *) malloc(sizeof(SNode) * SNODE_MALLOC_SIZE);
    tmp += (SNODE_MALLOC_SIZE-1);
    tmp->right = SplayNodeFreeList;
    tmp--;
    for (i=SNODE_MALLOC_SIZE-2; i; i--, tmp--)
      tmp->right = (tmp+1);
    SplayNodeFreeList = tmp+1;
  }
  tmp->leftmin = tmp;
  tmp->obj = tmp->left = tmp->right = tmp->parent = NULL;
  return tmp;

}

void *SplayAccess(STree *stree, void *obj) {
  SNode *snode;
  int res, done = 0;
  int (*compare)(void *, void *);


  compare = stree->compare;
  snode = stree->root;
  if(snode == NULL) return NULL;
  if((compare)(obj, snode->obj) == 0) return snode->obj;

/*  if(snode->left == NULL && snode->right == NULL) return NULL;*/
  if (snode->left == NULL && snode->right == NULL) return snode->obj;

  while(!done) {
    res = (compare)(obj, snode->obj);
    if (res == 0)
      done = 2;
    else
      if(res > 0)
	if(snode->right != NULL) {
	  snode = snode->right;
	}
	else
	  done = 1;
      else
	if(snode->left != NULL) {
	  snode = snode->left;
	}
	else
	  done = 1;
  }
  SplayNode(stree, snode);
  if (done == 2)
    return snode->obj;
  else
    /*  return NULL; */
    return snode->obj;

}

void SplayNode(STree *stree, SNode *snode) {
  SNode *par, *gpar, *ll, *lr, *l, *r, *rr, *rl;




  while((par = snode->parent) != NULL) {
    if(par->parent != NULL) {
      gpar = par->parent;
      ll = lr = rr = rl = NULL;
      l = gpar->left;
      r = gpar->right;
      if(l != NULL) {
	ll = l->left;
	lr = l->right;
      }
      if(r != NULL) {
	rl = r->left;
	rr = r->right;
      }
      if(snode == ll)
	S_splayll(stree, snode);
      else if(snode == lr)
	S_splaylr(stree, snode);
      else if(snode == rr)
	S_splayrr(stree, snode);
      else if(snode == rl)
	S_splayrl(stree, snode);
    } else {
      l = par->left;
      r = par->right;
      if(snode == l)
	S_splayl(stree, snode);
      else if(snode == r)
	S_splayr(stree, snode);
      else fprintf(stderr, "really fucked. go home and die.\n");
    }
  }

}
	  
void S_splayl(STree *stree, SNode *snode) {
  stree->root->left = snode->right;
  stree->root->parent = snode;
  if(snode->right != NULL) {
    stree->root->leftmin = snode->right->leftmin;
    snode->right->parent = stree->root;
  } else {
    stree->root->leftmin = stree->root;
  }
  snode->right = stree->root;
  stree->root = snode;
  snode->parent = NULL;

}

void S_splayr(STree *stree, SNode *snode) {
  stree->root->right = snode->left;
  stree->root->parent = snode;
  if(snode->left != NULL)
    snode->left->parent = stree->root;
  snode->left = stree->root;
  stree->root = snode;
  snode->parent = NULL;
  snode->leftmin = snode->left->leftmin;
}

void S_splayll(STree *stree, SNode *snode) {
  SNode *ggpar, *gpar, *par;

  par = snode->parent;
  gpar = par->parent;

  /* Do the min left operations */
  if(par->right != NULL)
    gpar->leftmin = par->right->leftmin;
  else
    gpar->leftmin = gpar;
  if(snode->right != NULL)
    par->leftmin = snode->right->leftmin;
  else
    par->leftmin = par;

  /* Do the splay rotations */
  ggpar = gpar->parent;
  gpar->left = par->right;
  if(gpar->left != NULL)
    gpar->left->parent = gpar;
  gpar->parent = par;
  par->right = gpar;
  par->left = snode->right;
  if(par->left != NULL)
    par->left->parent = par;
  par->parent = snode;
  snode->right = par;
  snode->parent = ggpar;
  if(ggpar != NULL) {
    if(ggpar->right == gpar)
      ggpar->right = snode;
    else
      ggpar->left = snode;
  } else {
    stree->root = snode;
  }
}


void S_splayrr(STree *stree, SNode *snode) {
  SNode *ggpar, *gpar, *par;

  par = snode->parent;
  gpar = par->parent;
  ggpar = gpar->parent;
  /* This min tracking is easy--gpar has min of all x, y, z */
  par->leftmin = snode->leftmin = gpar->leftmin;

  /* Do rotations */
  gpar->right = par->left;
  if(gpar->right != NULL)
    gpar->right->parent = gpar;
  gpar->parent = par;
  par->left = gpar;
  par->right = snode->left;
  if(par->right != NULL)
    par->right->parent = par;
  par->parent = snode;
  snode->left = par;
  snode->parent = ggpar;
  if(ggpar != NULL) {
    if(ggpar->right == gpar)
      ggpar->right = snode;
    else
      ggpar->left = snode;
  } else {
    stree->root = snode;
  }
}


void S_splaylr(STree *stree, SNode *snode) {
  SNode *ggpar, *gpar, *par;

  par = snode->parent;
  gpar = par->parent;

  /* Do the min calcs */
  if(snode->right != NULL)
    gpar->leftmin = snode->right->leftmin;
  else
    gpar->leftmin = gpar;
  snode->leftmin = par->leftmin;

  /* Do the rotations */
  ggpar = gpar->parent;
  par->right = snode->left;
  if(par->right != NULL)
    par->right->parent = par;
  par->parent = snode;
  gpar->left = snode->right;
  if(gpar->left != NULL)
    gpar->left->parent = gpar;
  gpar->parent = snode;
  snode->left = par;
  snode->right = gpar;
  snode->parent = ggpar;
  if(ggpar != NULL) {
    if(ggpar->right == gpar)
      ggpar->right = snode;
    else
      ggpar->left = snode;
  } else {
    stree->root = snode;
  }
}
  
void S_splayrl(STree *stree, SNode *snode) {
  SNode *ggpar, *gpar, *par;

  par = snode->parent;
  gpar = par->parent;

  /* Do the min swaps */
  snode->leftmin = gpar->leftmin;
  if(snode->right != NULL)
    par->leftmin = snode->right->leftmin;
  else
    par->leftmin = par;

  /* do the rotations */
  ggpar = gpar->parent;
  gpar->right = snode->left;
  if(gpar->right != NULL)
    gpar->right->parent = gpar;
  gpar->parent = snode;
  par->left = snode->right;
  if(par->left != NULL)
    par->left->parent = par;
  par->parent = snode;
  snode->left = gpar;
  snode->right = par;
  snode->parent = ggpar;
  if(ggpar != NULL)
    if(ggpar->right == gpar)
      ggpar->right = snode;
    else
      ggpar->left = snode;
  else
    stree->root = snode;
}


void SplaySplit(STree *stree, STree *stree2, void *obj) {
  SplayAccess(stree, obj);
  if ((stree->compare)(stree->root->obj, obj) > 0) {
    stree2->root = stree->root;
    stree->root = stree->root->left;
    if (stree->root) {
      stree->root->parent = NULL;
    }
  } else {
    stree2->root = stree->root->right;
    if(stree2->root != NULL) {
      stree2->root->parent = NULL;
    }
    stree->root->right = NULL;
  }
}

void SplayJoin(STree *stree1, STree *stree2) {
  SplayNode(stree2, stree2->root->leftmin);
  stree2->root->left = stree1->root;
  stree1->root->parent = stree2->root;
  stree1->root = stree2->root;
  stree1->root->leftmin = stree1->root->left->leftmin;
  free(stree2);
}

void SplayInsert(STree *stree, void *obj) {
  int (*compare)(void *, void *);
  SNode *snode;

  snode = SplayCreateNode();
  snode->obj = obj;

  compare = stree->compare;
  if(stree->root == NULL) {
    stree->root = snode;
    return;
  }
  SplayAccess(stree, obj);
  if((compare)(stree->root->obj, obj) < 0) {
    snode->left = stree->root;
    if(snode->left != NULL) {
      snode->leftmin = snode->left->leftmin;
      snode->left->parent = snode;
    } else {
      snode->leftmin = snode;
    }
    snode->right = stree->root->right;
    if(snode->right != NULL)
      snode->right->parent = snode;
    stree->root->right = NULL;
    stree->root = snode;
    snode->parent = NULL;
  } else {
    snode->right = stree->root;
    if(snode->right != NULL) {
      snode->right->parent = snode;
      snode->right->leftmin = snode->right;
    }
    snode->left = stree->root->left;
    if(snode->left != NULL) {
      snode->leftmin = snode->left->leftmin;
      snode->left->parent = snode;
    } else {
      snode->leftmin = snode;
    }
    stree->root->left = NULL;
    stree->root = snode;
    snode->parent = NULL;
  }
}


void SplayDelete(STree *stree, void *obj) {
  STree stree2;
  SNode *tmp;

  if (stree) {
    if (stree->root == NULL)
      return;
  } else {
    return;
  }

  if ((stree->compare)(SplayAccess(stree, obj),obj))
    return;

  if (stree->root->right) {
    stree2.root = stree->root->right;
    stree2.root->parent = NULL;
    stree2.compare = stree->compare;
    SplayNode(&stree2, stree2.root->leftmin);
    stree2.root->left = stree->root->left;
    if (stree->root->left) {
      stree->root->left->parent = stree2.root;
      stree2.root->leftmin = stree->root->leftmin;
    } else {
      stree2.root->leftmin = stree2.root;
    }
    tmp = stree->root;
    stree->root = stree2.root;
  } else {
    tmp = stree->root;
    stree->root = stree->root->left;
    if (stree->root)
      stree->root->parent = NULL;
  }

  SplayFreeNode(tmp);

}

void CopySubTree(SNode *snode, SNode *snode2, void (*CopyNode)(SNode *, SNode *)) {
  SNode *snew;
  
  CopyNode(snode, snode2);
  if(snode->left != NULL) {
    snode2->left = snew = SplayCreateNode();
    snew->parent = snode2;
    CopySubTree(snode->left, snew, CopyNode);
    snode2->leftmin = snode2->left->leftmin;
  } else {
    snode2->leftmin = snode;
  }
  
  if(snode->right != NULL) {
    snode2->right = snew = SplayCreateNode();
    snew->parent = snode2;
    CopySubTree(snode->right, snew, CopyNode);
  }
}


STree *SplayCopyTree(STree *st, void (*CopyNode)(SNode *, SNode *)) {
  STree *st2;
  
  st2 = CreateSplay(st->compare);
  if(st->root != NULL) {
    st2->root = SplayCreateNode();
    CopySubTree(st->root, st2->root, CopyNode);
  }
  return st2;
}



void SplayTraverse(STree *st, void (*function)(void *)) {
  if(st->root != NULL)
    SplayInOrderTraverse(st->root, function);
}

void SplayInOrderTraverse(SNode *sn, void (*function)(void *)) {
  if(sn->left != NULL)
    SplayInOrderTraverse(sn->left, function);
  (function)(sn->obj);
  if(sn->right != NULL)
    SplayInOrderTraverse(sn->right, function);
}

SNode *MinOfSubTree(SNode *sn) {
  return sn->leftmin;
}

SNode *MinOfTree(STree *st) {
  return st->root->leftmin;
}


void SplayDeleteTree(STree *st) {
  SNode *sn;
  
  if((sn = st->root) != NULL)
    SplayDeleteSubTree(sn);
  free(st);

}

void SplayDeleteSubTree(SNode *sn) {
  
  if(sn->right != NULL)
    SplayDeleteSubTree(sn->right);
  if(sn->left != NULL)
    SplayDeleteSubTree(sn->left);
  SplayFreeNode(sn);

}

void SplayDestroyTree(STree *st) {
  SNode *sn;
  
  if((sn = st->root) != NULL)
    SplayDestroySubTree(sn);
  free(st);

}

void SplayDestroySubTree(SNode *sn) {
  
  if(sn->right != NULL)
    SplayDestroySubTree(sn->right);
  if(sn->left != NULL)
    SplayDestroySubTree(sn->left);
  free(sn->obj);
  SplayFreeNode(sn);

}

SHAR_EOF
fi
if test -f 'splaylib.h'
then
	echo shar: "will not over-write existing file 'splaylib.h'"
else
cat << \SHAR_EOF > 'splaylib.h'
/*
 **     Copyright (C) 1995-1997  Rick Romero [rickr+@cmu.edu]
 **
 **     This program is free software; you can redistribute it and/or modify
 **     it under the terms of the GNU General Public License as published by
 **     the Free Software Foundation; either version 1, or (at your option)
 **     any later version.
 **     
 **     This program is distributed in the hope that it will be useful,
 **     but WITHOUT ANY WARRANTY; without even the implied warranty of
 **     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 **     GNU General Public License for more details.
 **     
 **     You should have received a copy of the GNU General Public License
 **     along with this program; if not, write to the Free Software
 **     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#ifndef _SPLAYTREE_H_
#define _SPLAYTREE_H_

typedef struct SplayNode {
  struct SplayNode *left, *right, *parent, *leftmin;
  void *obj;
} SplayNode_t, *SplayNode_p;

typedef struct SplayTree {
  int (*compare)(void *, void *);
  SplayNode_p root;
} SplayTree_t, *SplayTree_p;

SplayTree_p CreateSplay(int (*compare)(void *, void *));
SplayNode_p SplayCreateNode();
void SplayFreeNode(SplayNode_p);
void SplayDelete(SplayTree_p, void *);
void SplayInsert(SplayTree_p, void *);
void SplayJoin(SplayTree_p, SplayTree_p);
void SplaySplit(SplayTree_p, SplayTree_p, void *);
void *SplayAccess(SplayTree_p, void *);
void SplayNode(SplayTree_p, SplayNode_p);
void S_splayr(SplayTree_p, SplayNode_p);
void S_splayl(SplayTree_p, SplayNode_p);
void S_splayrl(SplayTree_p, SplayNode_p);
void S_splayrr(SplayTree_p, SplayNode_p);
void S_splayll(SplayTree_p, SplayNode_p);
void S_splaylr(SplayTree_p, SplayNode_p);
SplayTree_p SplayCopyTree(SplayTree_p, void (*CopyNode)());
void SplayTraverse(SplayTree_p, void (*function)());
SplayNode_p SplayMinOfSubTree(SplayNode_p);
void SplayCopySubTree(SplayNode_p, SplayNode_p, void (*CopyNode)());
void SplayInOrderTraverse(SplayNode_p, void (*function)());
void SplayDeleteTree(SplayTree_p);
void SplayDeleteSubTree(SplayNode_p);
void SplayDestroyTree(SplayTree_p);
void SplayDestroySubTree(SplayNode_p);



#endif
SHAR_EOF
fi
if test -f 'testgraph.c'
then
	echo shar: "will not over-write existing file 'testgraph.c'"
else
cat << \SHAR_EOF > 'testgraph.c'
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#include "Graphs.h"

char *pName;

int Usage() {
  fprintf(stderr, "Usage: %s [-points d] [-edges d] [file]\n\n"
	  "[-points d]\tNumber of points to randomly pick\n"
	  "[-edges d] \tNumber of edges to randomly generate\n"
	  "[file]     \tRead vertices and edges from a file instead\n",
	  pName);

}


void ReadGraph(FILE *fp, ComboGraph_p g) {
  Node_p *nodes;
  Point_t p;
  int i = 0, j;

  nodes = (Node_p *) malloc(sizeof(Node_p));

  /*  Read in the nodes as a pair of floats until you get double -1's */
  do {
    i++;
    nodes = (Node_p *) realloc(nodes, sizeof(Node_p) * i);
    if (fscanf(fp, "%d %d", &(p.x), &(p.y)) != 2) {
      fprintf(stderr, "Problem reading in the nodes\n");
      exit(-1);
    }
    nodes[i-1] = MakeNode(g, p);
  } while ((p.x != p.y) || (p.x != -1));

  /* Read in the edges as pairs of integers until you get double -1's */
  do {
    if (fscanf(fp, "%d %d", &i, &j) != 2) {
      fprintf(stderr, "EOF reached while reading edges?\n"); 
      fclose(fp);
      return;
    }
    if ((i > 0) && (j > 0))
      AddEdge(g, nodes[i-1], nodes[j-1]);
  } while ((i != j) || (i != -1));
  fclose(fp);
}


int main(int argc, char *argv[]) {
  int i, n1, n2, numPoints = 10, numEdges = 20;
  Point_t *points;
  Node_p *nodes;
  ComboGraph_p g;
  FILE *fp;
  char *fName;

  i = 1;
  pName = argv[0];

  while ((i < argc) && (argv[i][0] == '-')) {
    
    if (strcmp(argv[i]+1, "points") == 0) {
      i++;
      if (sscanf(argv[i], "%d", &numPoints) != 1) {
	Usage();
      }
      i++;
    } else if (strcmp(argv[i] + 1, "edges") == 0) {
      i++;
      if (sscanf(argv[i], "%d", &numEdges) != 1) {
	Usage();
      }
      i++;
    } else {
      Usage();
    }

  }

  g = MakeComboGraph();

  if (i < argc) {
    fName = argv[i];
    if ((fp = fopen(fName, "r")) == NULL) {
      fprintf(stderr, "Can't open %s for reading.\n", fName);
      exit(-1);
    }
    ReadGraph(fp, g);
  } else { 
    points = (Point_t *) malloc(sizeof(Point_t) * numPoints);
    nodes = (Node_p *) malloc(sizeof(Node_p) * numPoints);
    
    if (points == NULL || nodes == NULL) {
      fprintf(stderr, "Can't get memory for the points.\n");
      return -1;
    }

    srand48(time(NULL));

    printf("Points:\n");
    for (i = 0; i < numPoints; i++) {
      points[i].x = lrand48() & 127;
      points[i].y = lrand48() & 127;
      nodes[i] = MakeNode(g, points[i]);
      printf("(%3d,%3d) ", points[i].x, points[i].y);
    }
    printf("\n\nEdges:\n");
    for (i = 0; i < numEdges; i++) {
      n1 = lrand48() % numPoints;
      n2 = lrand48() % numPoints;
      if (AddEdge(g, nodes[n1], nodes[n2])) {
	fprintf(stderr, "Damn bugs!!\n");
	return -1;
      }
      printf("(%3d,%3d) ", n1, n2);
    }
  }

  printf("\n\nGraph:\n");
  PrintGraph(g);

  return 0;
  


}
SHAR_EOF
fi
if test -f 'graph1'
then
	echo shar: "will not over-write existing file 'graph1'"
else
cat << \SHAR_EOF > 'graph1'
1 8 10 10 2 3 4 3 6 4 6 8 1 9 6 2 10 8 4 7 -1 -1
5 5 3 1 7 7 2 4 3 9 2 2 6 10 1 1 2 1 6 5 -1 -1
SHAR_EOF
fi
exit 0
#	End of shell archive