1 files changed, 136 insertions, 0 deletions
diff --git a/src/fortune/edgelist.c b/src/fortune/edgelist.c
new file mode 100644
index 0000000..dfd85a7
--- /dev/null
+++ b/src/fortune/edgelist.c
@@ -0,0 +1,136 @@
+#
+#include "defs.h"
+int nedges;
+struct Freelist efl;
+struct Freelist hfl;
+struct Halfedge *ELleftend, *ELrightend;
+int ELhashsize;
+struct Halfedge **ELhash;
+
+int ntry, totalsearch;
+
+void ELinitialize() {
+	int i;
+	freeinit(&hfl, sizeof **ELhash);
+	ELhashsize = 2 * sqrt_nsites;
+	ELhash = (struct Halfedge **)myalloc(sizeof *ELhash * ELhashsize);
+	for (i = 0; i < ELhashsize; i += 1)
+		ELhash[i] = (struct Halfedge *)NULL;
+	ELleftend = HEcreate((struct Edge *)NULL, 0);
+	ELrightend = HEcreate((struct Edge *)NULL, 0);
+	ELleftend->ELleft = (struct Halfedge *)NULL;
+	ELleftend->ELright = ELrightend;
+	ELrightend->ELleft = ELleftend;
+	ELrightend->ELright = (struct Halfedge *)NULL;
+	ELhash[0] = ELleftend;
+	ELhash[ELhashsize - 1] = ELrightend;
+}
+
+struct Halfedge *HEcreate(e, pm) struct Edge *e;
+int pm;
+{
+	struct Halfedge *answer;
+	answer = (struct Halfedge *)getfree(&hfl);
+	answer->ELedge = e;
+	answer->ELpm = pm;
+	answer->PQnext = (struct Halfedge *)NULL;
+	answer->vertex = (struct Site *)NULL;
+	answer->ELrefcnt = 0;
+	return (answer);
+}
+
+void ELinsert(struct Halfedge *lb, struct Halfedge *new) {
+	new->ELleft = lb;
+	new->ELright = lb->ELright;
+	(lb->ELright)->ELleft = new;
+	lb->ELright = new;
+}
+
+/* Get entry from hash table, pruning any deleted nodes */
+struct Halfedge *ELgethash(b) int b;
+{
+	struct Halfedge *he;
+
+	if (b < 0 || b >= ELhashsize)
+		return ((struct Halfedge *)NULL);
+	he = ELhash[b];
+	if (he == (struct Halfedge *)NULL || he->ELedge != (struct Edge *)DELETED)
+		return (he);
+
+	/* Hash table points to deleted half edge.  Patch as necessary. */
+	ELhash[b] = (struct Halfedge *)NULL;
+	if ((he->ELrefcnt -= 1) == 0)
+		makefree((struct Freenode *)he, &hfl);
+	return ((struct Halfedge *)NULL);
+}
+
+struct Halfedge *ELleftbnd(p) struct Point *p;
+{
+	int i, bucket;
+	struct Halfedge *he;
+
+	/* Use hash table to get close to desired halfedge */
+	bucket = (p->x - xmin) / deltax * ELhashsize;
+	if (bucket < 0)
+		bucket = 0;
+	if (bucket >= ELhashsize)
+		bucket = ELhashsize - 1;
+	he = ELgethash(bucket);
+	if (he == (struct Halfedge *)NULL) {
+		for (i = 1; 1; i += 1) {
+			if ((he = ELgethash(bucket - i)) != (struct Halfedge *)NULL)
+				break;
+			if ((he = ELgethash(bucket + i)) != (struct Halfedge *)NULL)
+				break;
+		};
+		totalsearch += i;
+	};
+	ntry += 1;
+	/* Now search linear list of halfedges for the corect one */
+	if (he == ELleftend || (he != ELrightend && right_of(he, p))) {
+		do {
+			he = he->ELright;
+		} while (he != ELrightend && right_of(he, p));
+		he = he->ELleft;
+	} else
+		do {
+			he = he->ELleft;
+		} while (he != ELleftend && !right_of(he, p));
+
+	/* Update hash table and reference counts */
+	if (bucket > 0 && bucket < ELhashsize - 1) {
+		if (ELhash[bucket] != (struct Halfedge *)NULL)
+			ELhash[bucket]->ELrefcnt -= 1;
+		ELhash[bucket] = he;
+		ELhash[bucket]->ELrefcnt += 1;
+	};
+	return (he);
+}
+
+/* This delete routine can't reclaim node, since pointers from hash
+	 table may be present.   */
+void ELdelete(struct Halfedge *he) {
+	(he->ELleft)->ELright = he->ELright;
+	(he->ELright)->ELleft = he->ELleft;
+	he->ELedge = (struct Edge *)DELETED;
+}
+
+struct Halfedge *ELright(he) struct Halfedge *he;
+{ return (he->ELright); }
+
+struct Halfedge *ELleft(he) struct Halfedge *he;
+{ return (he->ELleft); }
+
+struct Site *leftreg(he) struct Halfedge *he;
+{
+	if (he->ELedge == (struct Edge *)NULL)
+		return (bottomsite);
+	return (he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
+}
+
+struct Site *rightreg(he) struct Halfedge *he;
+{
+	if (he->ELedge == (struct Edge *)NULL)
+		return (bottomsite);
+	return (he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
+}