[Commit] tess ChangeLog, 1.15, 1.16 kbentley.5c, 1.1, 1.2 skiplist.5c, 1.2, 1.3 skiplisttest.5c, 1.2, 1.3 slist.5c, 1.1, 1.2

[Keith Packard]

Committed by: keithp

Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv6630

Modified Files:
	ChangeLog kbentley.5c skiplist.5c skiplisttest.5c slist.5c 
Log Message:
2004-07-11  Keith Packard  <keithp at keithp.com>

	* kbentley.5c:
	Validate sweep_line before and after insert (for debugging)
	Fix up fprint_event_queue
	* skiplist.5c:
	Ammend validation code to check for correct ordering
	* skiplisttest.5c:
	Use validation code
	* slist.5c:
	Add validation code to check for correct ordering


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
--- ChangeLog	11 Jul 2004 05:53:18 -0000	1.15
+++ ChangeLog	11 Jul 2004 07:18:43 -0000	1.16
@@ -1,3 +1,15 @@
+2004-07-11  Keith Packard  <keithp at keithp.com>
+
+	* kbentley.5c:
+	Validate sweep_line before and after insert (for debugging)
+	Fix up fprint_event_queue
+	* skiplist.5c:
+	Ammend validation code to check for correct ordering
+	* skiplisttest.5c:
+	Use validation code
+	* slist.5c:
+	Add validation code to check for correct ordering
+
 2004-07-10  Keith Packard  <keithp at keithp.com>
 
 	* kbentley.5c:

Index: kbentley.5c
===================================================================
RCS file: /local/src/CVS/tess/kbentley.5c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- kbentley.5c	11 Jul 2004 05:53:18 -0000	1.1
+++ kbentley.5c	11 Jul 2004 07:18:43 -0000	1.2
@@ -1,6 +1,9 @@
 #!/usr/bin/env nickle
 
 autoload Skiplist;
+
+prefix="skip/";
+
 autoload Sort;
 
 import File;
@@ -255,11 +258,12 @@
 
 void fprint_event_queue (file f, EventQueue queue)
 {
-    for (EventPtr e = Sortlist::first(queue); 
-	 e != EventPtr.nil;
-	 e = Sortlist::next (queue, e))
+    for (EventPtr event_ptr = Sortlist::first(queue); 
+	 event_ptr != EventPtr.nil;
+	 event_ptr = Sortlist::next (queue, event_ptr))
     {
-	union switch (e.element->value.type) {
+	*Event	event = ElementEvent (event_ptr);
+	union switch (event->type) {
 	case Start:
 	    fprintf (f, "Start: ");
 	    break;
@@ -270,11 +274,11 @@
 	    fprintf (f, "Intersect: ");
 	    break;
 	}
-	fprintf (f, "%g:\t", e.element->value.point);
-	fprint_edge (f, e.element->value.e1);
-	if (e.element->value.type == EventType.Intersect) {
+	fprintf (f, "%g:\t", event->point);
+	fprint_edge (f, ElementEdge (event->e1));
+	if (event->type == EventType.Intersect) {
 	    fprintf (f, " X ");
-	    fprint_edge (f, e.element->value.e2.element->value);
+	    fprint_edge (f, ElementEdge (event->e2));
 	}
 	fprintf (f, "\n");
     }
@@ -457,7 +461,7 @@
 
     initialize_event_queue (segments);
 
-    int current_y = Sortlist::first (event_queue).element->value->point.y;
+    int current_y;
 
     bool edge_greater (*Edge a, *Edge b) {
 
@@ -538,17 +542,21 @@
 
 	current_y = event->point.y;
 
-
 	if (true)
 	{
 	    string filename;
-	    filename = sprintf ("%s_%04d.svg", TEST_NAME, FRAME_COUNT++);
+	    filename = sprintf ("%s%s_%04d.svg", prefix, TEST_NAME, FRAME_COUNT++);
 	    svg_file = open (filename, "w");
 	    print_sweep_line_svg (svg_file, sweep_line, segments, 
 				  event_queue, event_ptr, current_y);
 	    close (svg_file);
 	}
 
+	if (true)
+	{
+	    printf ("%3d: type %g y %g sweep: ", FRAME_COUNT-1, event->type, current_y);
+	    fprint_sweep_line (stdout, sweep_line);
+	}
     
 	Sortlist::delete (event_queue, event_ptr);
 
@@ -556,8 +564,12 @@
 	case Start:
 	    EdgePtr edge = event->e1;
 	    
+	    Sortlist::validate (sweep_line);
+
 	    Sortlist::insert (sweep_line, edge);
 	    
+	    Sortlist::validate (sweep_line);
+
 	    EdgePtr left = Sortlist::prev (sweep_line, edge);
 	    EdgePtr right = Sortlist::next (sweep_line, edge);
 	    

Index: skiplist.5c
===================================================================
RCS file: /local/src/CVS/tess/skiplist.5c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- skiplist.5c	11 Jul 2004 05:53:18 -0000	1.2
+++ skiplist.5c	11 Jul 2004 07:18:43 -0000	1.3
@@ -56,25 +56,31 @@
     } LstRec;
 
     typedef *LstRec Lst;
-    
-    void validate_element (EltPtr a, int level)
+
+    void validate_elt (Lst a, EltPtr e, int level)
     {
-	int l;
-	
-	if (a == EltPtr.nil)
-	    return;
-	assert (dim (a.element->forward) >= level, "Forward is too short");
+	EltPtr	prev = e.element->backward[level];
 
-	bool is_forward (EltPtr b, int l)
+	assert (prev.element->forward[level] == e, "pointers corrupt");
+	if (prev.element != &a->header)
+	    assert (!a->greater (prev.element->value, e.element->value),
+		    "prev misordered");
+	return <>;
+    }
+
+    public void validate (Lst a)
+    {
+	assert (a->level <= MaxLevel, "level too high");
+	
+	for (int level = 0; level < a->level; level++)
 	{
-	    if (a.element->forward[level] == b)
-		return true;
-	    assert (b != EltPtr.nil, "unexpected nil");
-	    return is_forward (b.element->forward[l], l);
+	    for (EltPtr p = a->header.forward[level]; 
+		 p != EltPtr.nil; 
+		 p = p.element->forward[level])
+	    {
+		validate_elt (a, p, level);
+	    }
 	}
-	
-	for (l = 0; l < level; l++)
-	    assert (is_forward (a, l), "not forward");
     }
 
     /*
@@ -93,24 +99,15 @@
 	}
 	return level;
     }
-
-    public void validate (Lst a)
-    {
-	assert (a->level <= MaxLevel, "level too high");
-	for (EltPtr p = a->header.forward[0]; 
-	     p != EltPtr.nil; 
-	     p = p.element->forward[0])
-	{
-	    validate_element (p, dim(p.element->forward) - 1);
-	}
-    }
-
     public List new (Greater greater)
     {
 	return &(LstRec) {
 	    level = 0,
 	    greater = greater,
-	    header = { forward = (EltPtr[MaxLevel]) { [i] = EltPtr.nil } }
+	    header = { 
+		forward = (EltPtr[MaxLevel]) { [i] = EltPtr.nil },
+		value = <> 
+	    }
 	};
     }
 
@@ -181,13 +178,16 @@
 	
 	for (int i = 0; i < level; i++)
 	{
-	    new.element->forward[i] = update[i].element->forward[i];
-	    new.element->backward[i] = update[i];
+	    EltPtr  prev = update[i];
+	    EltPtr  next = prev.element->forward[i];
 	    
-	    if (update[i].element->forward[i] != EltPtr.nil)
-		update[i].element->forward[i].element->backward[i] = new;
+	    new.element->forward[i] = next;
+	    new.element->backward[i] = prev;
 	    
-	    update[i].element->forward[i] = new;
+	    if (next != EltPtr.nil)
+		next.element->backward[i] = new;
+	    
+	    prev.element->forward[i] = new;
 	}
     }
 
@@ -204,7 +204,7 @@
 	}
 	
 	while (list->level > 0 &&
-	       list->header.forward[list->level] == EltPtr.nil)
+	       list->header.forward[list->level-1] == EltPtr.nil)
 	    list->level--;
     }
 

Index: skiplisttest.5c
===================================================================
RCS file: /local/src/CVS/tess/skiplisttest.5c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- skiplisttest.5c	11 Jul 2004 05:53:18 -0000	1.2
+++ skiplisttest.5c	11 Jul 2004 07:18:43 -0000	1.3
@@ -17,6 +17,7 @@
 public void insert_int (Sortlist::List l, int i) {
     Sortlist::ElementPtr	e = Sortlist::element (i);
     Sortlist::insert (l, e);
+    Sortlist::validate (l);
 }
 
 public void insert_ints (Sortlist::List l, int[*] i) {

Index: slist.5c
===================================================================
RCS file: /local/src/CVS/tess/slist.5c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- slist.5c	11 Jul 2004 05:53:18 -0000	1.1
+++ slist.5c	11 Jul 2004 07:18:43 -0000	1.2
@@ -60,8 +60,25 @@
 
     typedef *LstRec Lst;
     
+    void validate_elt (Lst a, EltPtr e)
+    {
+	EltPtr	prev = e.element->backward;
+
+	assert (prev.element->forward == e, "pointers corrupt");
+	if (prev.element != &a->header)
+	    assert (!a->greater (prev.element->value, e.element->value),
+		    "prev misordered");
+	return <>;
+    }
+
     public void validate (Lst a)
     {
+	for (EltPtr p = a->header.forward; 
+	     p != EltPtr.nil; 
+	     p = p.element->forward)
+	{
+	    validate_elt (a, p);
+	}
     }
 
     public List new (Greater greater)