[Commit] tess ChangeLog, 1.14, 1.15 kbentley.5c, NONE,
1.1 skiplist.5c, 1.1, 1.2 skiplisttest.5c, 1.1, 1.2 slist.5c,
NONE, 1.1
Keith Packard
commit at keithp.com
Sat Jul 10 22:53:20 PDT 2004
- Previous message: [Commit] tess ChangeLog, 1.13, 1.14 skiplist.5c, NONE,
1.1 skiplisttest.5c, NONE, 1.1
- Next message: [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
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Committed by: keithp
Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv5449
Modified Files:
ChangeLog skiplist.5c skiplisttest.5c
Added Files:
kbentley.5c slist.5c
Log Message:
2004-07-10 Keith Packard <keithp at keithp.com>
* kbentley.5c:
A copy of bentley.5c adapted to using skiplist.5c/slist.5c
* skiplist.5c:
* skiplisttest.5c:
Update to provide different interface that supports bentley
requirements
* slist.5c
Simple sorted list implementation to validate skiplist.5c
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -d -r1.14 -r1.15
--- ChangeLog 10 Jul 2004 07:52:22 -0000 1.14
+++ ChangeLog 11 Jul 2004 05:53:18 -0000 1.15
@@ -1,5 +1,16 @@
2004-07-10 Keith Packard <keithp at keithp.com>
+ * kbentley.5c:
+ A copy of bentley.5c adapted to using skiplist.5c/slist.5c
+ * skiplist.5c:
+ * skiplisttest.5c:
+ Update to provide different interface that supports bentley
+ requirements
+ * slist.5c
+ Simple sorted list implementation to validate skiplist.5c
+
+2004-07-10 Keith Packard <keithp at keithp.com>
+
* skiplist.5c:
* skiplisttest.5c:
Add skip list implementation. This isn't used yet, but it
--- NEW FILE: kbentley.5c ---
#!/usr/bin/env nickle
autoload Skiplist;
autoload Sort;
import File;
string TEST_NAME = "bentley";
int FRAME_COUNT;
typedef struct {
int x;
int y;
} Point;
typedef struct {
rational x;
rational y;
} RationalPoint;
bool point_greater (Point a, Point b)
{
if (a.y != b.y)
return a.y > b.y;
else
return a.x > b.x;
}
typedef Sortlist::List EdgeList;
typedef Sortlist::ElementPtr EdgePtr;
typedef struct {
Point top;
Point middle;
Point bottom;
} Edge;
typedef Sortlist::List EventQueue;
typedef Sortlist::ElementPtr EventPtr;
*Edge ElementEdge(EdgePtr e) = e.element->value;
typedef enum {
Start, Intersect, Stop
} EventType;
typedef struct {
EventType type;
EdgePtr e1;
EdgePtr e2;
Point point;
RationalPoint rational_point;
} Event;
*Event ElementEvent(EventPtr e) = e.element->value;
bool slope_greater (&Edge a, &Edge b)
{
int adx = a.bottom.x - a.top.x;
int bdx = b.bottom.x - b.top.x;
int ady = a.bottom.y - a.top.y;
int bdy = b.bottom.y - b.top.y;
return adx * bdy > ady * bdx;
}
bool slope_equal (&Edge a, &Edge b)
{
int adx = a.bottom.x - a.top.x;
int bdx = b.bottom.x - b.top.x;
int ady = a.bottom.y - a.top.y;
int bdy = b.bottom.y - b.top.y;
return adx * bdy == ady * bdx;
}
bool event_greater (&Event a, &Event b)
{
/* The major motion of the sweep line is vertical
* (top-to-bottom). */
/* Vertical discrimination begins with Y value. */
if (a.rational_point.y != b.rational_point.y)
return a.rational_point.y > b.rational_point.y;
/* XXX: We will be able to drop these when we disallow horizontal
* edges. */
bool a_horiz = ElementEdge(a.e1)->top.y == ElementEdge(a.e1)->bottom.y;
bool b_horiz = ElementEdge(b.e1)->top.y == ElementEdge(b.e1)->bottom.y;
/* Even with the same Y-value, further vertical discrimination is
* determined by the event type for non-horizontal edges. Due to
* the infinitesimal shortening rule, non-horizontal stop events
* occur before the current Y value while non-horizontal start
* events occur after the current value.
*
* So, a non-horizontal stop event is less than another event if
* that other event belongs to a horizontal edge or it is not a
* stop event. Similar logic holds for non-horizontal start
* events.
*/
if (!a_horiz && (b_horiz || b.type != a.type)) {
if (a.type == EventType.Stop)
return false;
if (a.type == EventType.Start)
return true;
}
if (!b_horiz && (a_horiz || a.type != b.type)) {
if (b.type == EventType.Stop)
return true;
if (b.type == EventType.Start)
return false;
}
/* The minor motion of the sweep line is horizontal
* (left-to-right) due to the infinitesimal tilt rule. */
/* Horizontal discrimination begins with X value. */
if (a.rational_point.x != b.rational_point.x)
return a.rational_point.x > b.rational_point.x;
/* At this point, degenerate edges cause problems, (stop events
* get scheduled before start events). I had tried adding code
* here to fix it, but decided instead to just remove those edges
* before the algorithm begine.
*/
/* Even with the same X-value, further horizontal discrimination
* is determined by the event type for horizontal edges. As
* before, due to the shortening rule, stop events occur before
* the current X value while start events occur after the current
* value.
*/
if (a.type != b.type) {
if (a.type == EventType.Stop)
return false;
if (a.type == EventType.Start)
return true;
if (b.type == EventType.Stop)
return true;
if (b.type == EventType.Start)
return false;
}
/* At this stage we are looking at two events of the same type at
* the same point. The final sort key is a slope comparison. We
* need a difference sens for start and stop events based on the
* shortening rule.
*
* NOTE: Fortunately, we get to ignore errors in the relative
* ordering of intersection events. This means we don't even have
* to look at e2 here, nor worry about which sense of the slope
* comparison test is used for intersection events.
*/
if (! slope_equal (ElementEdge(a.e1), ElementEdge(b.e1)))
if (a.type == EventType.Start)
return slope_greater (ElementEdge (a.e1), ElementEdge (b.e1));
else
return ! slope_greater (ElementEdge (a.e1), ElementEdge (b.e1));
/* As a final discrimination, look at the opposite point. This
* leaves ambiguities only for identical edges.
*
* XXX: We probably don't actually need this one, but it prevents
* my sort check from returning a false negaative.
*/
if (a.type == EventType.Start)
return point_greater (ElementEdge (b.e1)->bottom,
ElementEdge (a.e1)->bottom);
else
return point_greater (ElementEdge (a.e1)->top,
ElementEdge (b.e1)->top);
}
exception parallel (void);
exception no_intersection (void);
RationalPoint intersect_lines (&Edge a, &Edge b)
{
int det (int a, int b, int c, int d) {
return a * d - b * c;
}
int dx1 = a.top.x - a.bottom.x;
int dy1 = a.top.y - a.bottom.y;
int dx2 = b.top.x - b.bottom.x;
int dy2 = b.top.y - b.bottom.y;
int den_det = det (dx1, dy1, dx2, dy2);
if (den_det == 0)
raise parallel ();
int a_det = det (a.top.x, a.top.y,
a.bottom.x, a.bottom.y);
int b_det = det (b.top.x, b.top.y,
b.bottom.x, b.bottom.y);
return (RationalPoint) {
x = det (a_det, dx1,
b_det, dx2) / den_det,
y = det (a_det, dy1,
b_det, dy2) / den_det
};
}
/* XXX: As should be obvious, this function is a bit simpler in the
* absence of horizontal edges */
RationalPoint intersect_segments (&Edge a, &Edge b)
{
RationalPoint intersection = intersect_lines (&a, &b);
if (a.top.y == a.bottom.y) {
if (intersection.x <= a.top.x || intersection.x >= a.bottom.x)
raise no_intersection ();
} else {
if (intersection.y <= a.top.y || intersection.y >= a.bottom.y)
raise no_intersection ();
}
if (b.top.y == b.bottom.y) {
if (intersection.x <= b.top.x || intersection.x >= b.bottom.x)
raise no_intersection ();
} else {
if (intersection.y <= b.top.y || intersection.y >= b.bottom.y)
raise no_intersection ();
}
return intersection;
}
bool event_ptr_greater (EventPtr a, EventPtr b)
{
return event_greater (ElementEvent (a), ElementEvent (b));
}
void fprint_edge (file f, &Edge e)
{
fprintf (f, "(%2d, %2d)-(%2d, %2d)",
e.top.x, e.top.y,
e.bottom.x, e.bottom.y);
}
void fprint_edge_svg (file svg_file, &Edge e)
{
fprintf (svg_file, "<line x1='%d' y1='%d' x2='%d' y2='%d' />\n",
e.top.x, e.top.y,
e.bottom.x, e.bottom.y);
}
void fprint_event_queue (file f, EventQueue queue)
{
for (EventPtr e = Sortlist::first(queue);
e != EventPtr.nil;
e = Sortlist::next (queue, e))
{
union switch (e.element->value.type) {
case Start:
fprintf (f, "Start: ");
break;
case Stop:
fprintf (f, "Stop: ");
break;
case Intersect:
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, " X ");
fprint_edge (f, e.element->value.e2.element->value);
}
fprintf (f, "\n");
}
}
void fprint_event_queue_svg (file svg_file, EventQueue queue)
{
int text_y = 214;
for (EventPtr event_ptr = Sortlist::first(queue);
event_ptr != EventPtr.nil;
event_ptr = Sortlist::next (queue, event_ptr))
{
*Event event = ElementEvent (event_ptr);
fprintf (svg_file, "<text stroke='none' fill='black' x='0' y='%d'>\n", text_y);
text_y += 14;
enum switch (event->type) {
case Start:
fprintf (svg_file, "Start: ");
break;
case Stop:
fprintf (svg_file, "Stop: ");
break;
case Intersect:
fprintf (svg_file, "Intersect: ");
break;
}
fprintf (svg_file, "%g:\t", event->point);
fprint_edge (svg_file, ElementEdge (event->e1));
if (event->type == EventType.Intersect) {
fprintf (svg_file, " X ");
fprint_edge (svg_file, ElementEdge (event->e2));
}
fprintf (svg_file, "\n");
fprintf (svg_file, "</text>\n");
}
}
void fprint_sweep_line (file f, EdgeList sweep)
{
bool first = true;
for (EdgePtr e = Sortlist::first(sweep);
e != EdgePtr.nil;
e = Sortlist::next (sweep, e))
{
if (!first)
fprintf (f, ", ");
fprint_edge (f, e.element->value);
first = false;
}
fprintf (f, "\n");
}
void print_sweep_line_svg (file svg_file,
EdgeList sweep_line,
Edge[*] segments,
EventQueue event_queue,
EventPtr event_ptr,
int current_y)
{
*Event event = ElementEvent (event_ptr);
fprintf (svg_file, "<?xml version='1.0' standalone='no'?>\n");
fprintf (svg_file, "<!DOCTYPE svg PUBLIC '-//W3C//DTD SVG 20001102//EN'\n");
fprintf (svg_file, " 'http://www.w3.org/TR/2000/CR-SVG-20001102/DTD/svg-20001102.dtd'>\n");
fprintf (svg_file, "<svg transform='translate(70,70)' fill='none' stroke='black' font='mono' font-size='12'>\n");
fprintf (svg_file, "<g transform='scale(30,30)' stroke-width='.05'>\n");
for (int i=0; i < dim(segments); i++) {
fprint_edge_svg (svg_file, &segments[i]);
}
fprintf (svg_file, "</g>\n");
fprintf (svg_file, "<text stroke='none' fill='blue' x='0' y='200'>\n");
bool first = true;
for (
EdgePtr e = Sortlist::first (sweep_line);
e != EdgePtr.nil;
e = Sortlist::next (sweep_line, e))
{
if (!first)
fprintf (svg_file, ", ");
fprint_edge (svg_file, e.element->value);
first = false;
}
fprintf (svg_file, "</text>\n");
fprintf (svg_file, "<g transform='scale(30,30)' stroke='blue' stroke-width='.05'>\n");
int edge_cnt = 0;
for (EdgePtr edge_ptr = Sortlist::first (sweep_line);
edge_ptr != EdgePtr.nil;
edge_ptr = Sortlist::next (sweep_line, edge_ptr))
{
*Edge edge = ElementEdge (edge_ptr);
fprint_edge_svg (svg_file, edge);
fprintf (svg_file, "<text font-size='.4' fill='blue' stroke='none' x='%g' y='%g'>%d</text>\n",
edge->top.x + .1, edge->top.y - .1, edge_cnt++);
}
fprintf (svg_file, "<line x1='-10' y1='%d' x2='100' y2='%d' stroke-width='.05' stroke='red' />\n",
current_y, current_y);
fprintf (svg_file, "<text font-size='.4' fill='red' stroke='none' x='15' y='%g'>%d</text>\n", current_y - .1, current_y);
fprintf (svg_file, "<circle cx='%d' cy='%d' r='.15' stroke='none' fill='green'/>\n",
event->point.x, event->point.y);
fprintf (svg_file, "</g>\n");
fprint_event_queue_svg (svg_file, event_queue);
fprintf (svg_file, "</svg>\n");
}
Edge[*]
bentley_ottman (Edge[*] segments, &int intersection_count)
{
intersection_count = 0;
EventQueue event_queue = Sortlist::new (event_greater);
Edge[...] result = {};
Edge[*] remove_degenerate (Edge[*] edges) {
Edge[...] non_degenerate = {};
for (int i=0; i < dim(edges); i++)
if (edges[i].top.x != edges[i].bottom.x ||
edges[i].top.y != edges[i].bottom.y)
non_degenerate[dim(non_degenerate)] = edges[i];
return non_degenerate;
}
Edge[*] remove_horizontal (Edge[*] edges) {
Edge[...] non_horizontal = {};
for (int i=0; i < dim(edges); i++)
if (edges[i].top.y != edges[i].bottom.y)
non_horizontal[dim(non_horizontal)] = edges[i];
return non_horizontal;
}
void initialize_event_queue (Edge[*] segments) {
segments = remove_degenerate (segments);
/*
segments = remove_horizontal (segments);
*/
for (int i=0; i < dim(segments); i++) {
if (point_greater (segments[i].top, segments[i].bottom)) {
Point tmp;
tmp = segments[i].top;
segments[i].top = segments[i].bottom;
segments[i].bottom = tmp;
}
segments[i].middle = segments[i].top;
}
EdgePtr[dim(segments)] edges = { [i] = Sortlist::element (&segments[i]) };
for (int i=0; i < dim(edges); i++)
{
EventPtr start = Sortlist::element (&(Event) {
type = EventType.Start,
e1 = edges[i],
point = segments[i].top,
rational_point = segments[i].top
});
Sortlist::insert (event_queue, start);
EventPtr stop = Sortlist::element (&(Event) {
type = EventType.Stop,
e1 = edges[i],
point = segments[i].bottom,
rational_point = segments[i].bottom
});
Sortlist::insert (event_queue, stop);
}
}
initialize_event_queue (segments);
int current_y = Sortlist::first (event_queue).element->value->point.y;
bool edge_greater (*Edge a, *Edge b) {
rational edge_x_for_y (*Edge e, int y) {
int dx = e->bottom.x - e->top.x;
int dy = e->bottom.y - e->top.y;
if (dy == 0)
return e->top.x;
return e->top.x + (y - e->top.y) * dx / dy;
}
rational ax = edge_x_for_y (a, current_y);
rational bx = edge_x_for_y (b, current_y);
if (ax != bx)
return ax > bx;
/* Slope comparison */
return slope_greater (a, b);
}
/*
bool edge_greater (*Edge a, *Edge b) {
int adx = a->bottom.x - a->top.x;
int bdx = b->bottom.x - b->top.x;
int ady = a->bottom.y - a->top.y;
int bdy = b->bottom.y - b->top.y;
int ax = bdy*(adx*(current_y - a->top.y) + a->top.x * ady);
int bx = ady*(bdx*(current_y - b->top.y) + b->top.x * bdy);
return ax > bx;
}
*/
EdgeList sweep_line = Sortlist::new (edge_greater);
void insert_event_if_intersect_below_current_y (EdgePtr left, EdgePtr right) {
if (left == EdgePtr.nil || right == EdgePtr.nil)
return;
/* A slope comparison tells us if the intersection is before current_y */
if (slope_greater (ElementEdge (right), ElementEdge (left)))
return;
RationalPoint intersection;
try {
intersection = intersect_segments (ElementEdge (left),
ElementEdge (right));
} catch parallel () {
return;
} catch no_intersection () {
return;
}
EventPtr intersect = Sortlist::element ( &(Event) {
type = EventType.Intersect,
e1 = left,
e2 = right,
point = {
x = floor (intersection.x + 0.5),
y = floor (intersection.y + 0.5),
},
rational_point = intersection
});
Sortlist::insert (event_queue, intersect);
}
while ((EventPtr event_ptr = Sortlist::first (event_queue)) != EventPtr.nil)
{
*Event event = ElementEvent(event_ptr);
file svg_file;
current_y = event->point.y;
if (true)
{
string filename;
filename = sprintf ("%s_%04d.svg", 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);
}
Sortlist::delete (event_queue, event_ptr);
enum switch (event->type) {
case Start:
EdgePtr edge = event->e1;
Sortlist::insert (sweep_line, edge);
EdgePtr left = Sortlist::prev (sweep_line, edge);
EdgePtr right = Sortlist::next (sweep_line, edge);
insert_event_if_intersect_below_current_y (left, edge);
insert_event_if_intersect_below_current_y (edge, right);
break;
case Stop:
EdgePtr edge = event->e1;
result[dim(result)] = (Edge) {
top = ElementEdge(edge)->middle,
bottom = event->point
};
EdgePtr left = Sortlist::prev (sweep_line, edge);
EdgePtr right = Sortlist::next (sweep_line, edge);
Sortlist::delete (sweep_line, edge);
insert_event_if_intersect_below_current_y (left, right);
break;
case Intersect:
EdgePtr e1 = event->e1;
EdgePtr e2 = event->e2;
/* skip this intersection if its edges are not adjacent */
if (e2 != Sortlist::next (sweep_line, e1))
break;
intersection_count++;
/* Avoid inserting a degenerate edge if this edge has already
* been used for a previous intersection at exactly the
* same point. */
if (ElementEdge(e1)->middle != event->point)
result[dim(result)] = (Edge) {
top = ElementEdge(e1)->middle,
bottom = event->point
};
if (ElementEdge(e2)->middle != event->point)
result[dim(result)] = (Edge) {
top = ElementEdge(e2)->middle,
bottom = event->point
};
ElementEdge(e1)->middle = event->point;
ElementEdge(e2)->middle = event->point;
EdgePtr left = Sortlist::prev (sweep_line, e1);
EdgePtr right = Sortlist::next (sweep_line, e2);
Sortlist::swap (sweep_line, e1);
/* after the swap e2 is left of e1 */
insert_event_if_intersect_below_current_y (left, e2);
insert_event_if_intersect_below_current_y (e1, right);
break;
}
}
return result;
}
Edge[*]
bentley_ottman_iterative (Edge[*] edges, &int iterations)
{
Edge[*] old_edges;
iterations = 0;
FRAME_COUNT = 0;
int intersections;
do {
iterations++;
old_edges = edges;
edges = bentley_ottman(old_edges, &intersections);
} while (intersections > 0);
return edges;
}
bool edges_have_an_intersection_quadratic (&Edge[*] edges)
{
RationalPoint intersection;
for (int i=0; i < dim(edges); i++) {
if (point_greater (edges[i].top, edges[i].bottom)) {
Point tmp;
tmp = edges[i].top;
edges[i].top = edges[i].bottom;
edges[i].bottom = tmp;
}
}
for (int i=0; i < dim(edges); i++) {
for (int j=0; j < dim (edges); j++) {
if (i==j)
continue;
&Edge a = &edges[i];
&Edge b = &edges[j];
try {
intersection = intersect_segments (&a, &b);
} catch parallel () {
continue;
} catch no_intersection () {
continue;
}
printf ("Found intersection (%g,%g) between (%g,%g)-(%g,%g) and (%g,%g)-(%g,%g)\n",
intersection.x, intersection.y,
a.top.x, a.top.y,
a.bottom.x, a.bottom.y,
b.top.x, b.top.y,
b.bottom.x, b.bottom.y);
return true;
}
}
return false;
}
bool run_test (string name, Edge[*] edges)
{
int iterations;
TEST_NAME = name;
printf ("%s: ", name);
Edge[*] intersected_edges = bentley_ottman_iterative (edges, &iterations);
if (edges_have_an_intersection_quadratic (&intersected_edges))
printf ("*** FAIL ***");
else
printf ("PASS");
printf (" (%d iteration%s)\n", iterations, iterations == 1 ? "" : "s");
}
typedef struct {
string name;
string desc;
Edge[*] edges;
} Test;
Test[*] tests = {
{
name = "endpoint",
desc = "An intersection that occurs at the enpoint of a segments.",
edges = {
{ top = { x = 4, y = 6}, bottom = { x = 5, y = 6}},
{ top = { x = 4, y = 5}, bottom = { x = 5, y = 7}},
}
},
{
name = "overlapping",
desc = "Parallel segments that share an endpoint, with different slopes.",
edges = {
{ top = { x = 2, y = 0}, bottom = { x = 1, y = 1}},
{ top = { x = 2, y = 0}, bottom = { x = 0, y = 2}},
{ top = { x = 0, y = 3}, bottom = { x = 1, y = 3}},
{ top = { x = 0, y = 3}, bottom = { x = 2, y = 3}},
{ top = { x = 0, y = 4}, bottom = { x = 0, y = 6}},
{ top = { x = 0, y = 5}, bottom = { x = 0, y = 6}}
}
},
{
name = "hobby_stage_3",
desc = "A particularly tricky part of the 3rd stage of the 'hobby' test below.",
edges = {
{ top = { x = -1, y = -2}, bottom = { x = 4, y = 2}},
{ top = { x = 5, y = 3}, bottom = { x = 9, y = 5}},
{ top = { x = 5, y = 3}, bottom = { x = 6, y = 3}},
}
},
{
name = "hobby",
desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
edges = {
{ top = { x = 0, y = 0}, bottom = { x = 9, y = 5}},
{ top = { x = 0, y = 0}, bottom = { x = 13, y = 6}},
{ top = { x = -1, y = -2}, bottom = { x = 9, y = 5}}
}
},
{
name = "slope",
desc = "Edges with same start/stop points but different slopes",
edges = {
{ top = { x = 4, y = 1}, bottom = { x = 6, y = 3}},
{ top = { x = 4, y = 1}, bottom = { x = 2, y = 3}},
{ top = { x = 2, y = 4}, bottom = { x = 4, y = 6}},
{ top = { x = 6, y = 4}, bottom = { x = 4, y = 6}}
}
},
{
name = "horizontal",
desc = "Test of a horizontal edge",
edges = {
{ top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
{ top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
}
},
{
name = "vertical",
desc = "Test of a vertical edge",
edges = {
{ top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
{ top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
}
},
{
name = "congruent",
desc = "Two overlapping edges with the same slope",
edges = {
{ top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
{ top = { x = 5, y = 2}, bottom = { x = 5, y = 6}},
{ top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
}
},
{
name = "multi",
desc = "Several segments with a common intersection point",
edges = {
{ top = { x = 1, y = 2}, bottom = { x = 5, y = 4} },
{ top = { x = 1, y = 1}, bottom = { x = 5, y = 5} },
{ top = { x = 2, y = 1}, bottom = { x = 4, y = 5} },
{ top = { x = 4, y = 1}, bottom = { x = 2, y = 5} },
{ top = { x = 5, y = 1}, bottom = { x = 1, y = 5} },
{ top = { x = 5, y = 2}, bottom = { x = 1, y = 4} }
}
}
};
/*
for (int i=0; i < dim(tests); i++)
run_test (tests[i].name, tests[i].edges);
*/
num_random = 10;
if (dim(argv)>1)
num_random = string_to_integer (argv[1]);
printf ("%d ", num_random);
PRNG::srandom (0);
Edge[...] random_edges = {};
for (int i=0; i < num_random; i++)
{
random_edges[dim (random_edges)] = (Edge) {
top = { x = PRNG::randint (10), y = PRNG::randint (10) },
bottom = { x = PRNG::randint (10), y = PRNG::randint (10) }
};
}
run_test ("random", random_edges);
Index: skiplist.5c
===================================================================
RCS file: /local/src/CVS/tess/skiplist.5c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- skiplist.5c 10 Jul 2004 07:52:22 -0000 1.1
+++ skiplist.5c 11 Jul 2004 05:53:18 -0000 1.2
@@ -7,43 +7,69 @@
*/
namespace Skiplist {
+ /*
+ * Visible representation of an element, hides
+ * implementation details
+ */
public typedef Element;
public typedef union {
- *Element element;
- void nil;
+ *Element element;
+ void nil;
} ElementPtr;
- public const MaxLevel = 32;
-
- typedef struct {
- ElementPtr[*] forward;
+ public typedef struct {
+ poly value;
} Element;
- public typedef struct {
- int level;
- Element header;
- } ListRec;
+ public typedef *struct {
+ } List;
- public typedef *ListRec List;
+ public typedef bool (poly a, poly b) Greater;
+
+ public typedef void (poly a) Visit;
- typedef bool (ElementPtr a, ElementPtr b) Greater;
+ public exception not_found (poly missing);
+
+ /*
+ * Private representation of an element
+ */
+ typedef Elt;
- public exception not_found (ElementPtr missing);
+ typedef union {
+ *Elt element;
+ void nil;
+ } EltPtr;
+
+ const MaxLevel = 16;
+
+ typedef struct {
+ poly value;
+ EltPtr[*] forward;
+ EltPtr[*] backward;
+ } Elt;
+
+ typedef struct {
+ int level;
+ Greater greater;
+ Elt header;
+ } LstRec;
+
+ typedef *LstRec Lst;
- public void validate_element (ElementPtr a, int level)
+ void validate_element (EltPtr a, int level)
{
int l;
- if (a == ElementPtr.nil)
+ if (a == EltPtr.nil)
return;
assert (dim (a.element->forward) >= level, "Forward is too short");
- bool is_forward (ElementPtr b, int l)
+ bool is_forward (EltPtr b, int l)
{
if (a.element->forward[level] == b)
return true;
- assert (b != ElementPtr.nil, "unexpected nil");
+ assert (b != EltPtr.nil, "unexpected nil");
return is_forward (b.element->forward[l], l);
}
@@ -51,21 +77,10 @@
assert (is_forward (a, l), "not forward");
}
- public void validate (List a)
- {
- assert (a->level <= MaxLevel, "level too high");
- for (ElementPtr p = a->header.forward[0];
- p != ElementPtr.nil;
- p = p.element->forward[0])
- {
- validate_element (p, dim(p.element->forward) - 1);
- }
- }
-
/*
* This uses a fixed probability of 1/4 for each level
*/
- public int random_level ()
+ int random_level ()
{
int bits = PRNG::randbits(MaxLevel * 2);
int level = 0;
@@ -79,39 +94,76 @@
return level;
}
- public List new ()
+ public void validate (Lst a)
{
- return &(ListRec) {
+ 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,
- header = { forward = (ElementPtr[MaxLevel]) { [i] = ElementPtr.nil } }
+ greater = greater,
+ header = { forward = (EltPtr[MaxLevel]) { [i] = EltPtr.nil } }
};
}
- public ElementPtr search (List list, ElementPtr key, Greater gt)
+ public ElementPtr search (Lst list, poly value)
{
- ElementPtr x = (ElementPtr.element) &list->header;
+ EltPtr x = (EltPtr.element) &list->header;
for (int i = list->level; --i >= 0; )
{
- while (x.element->forward[i] != ElementPtr.nil &&
- gt (key, x.element->forward[i]))
+ while (x.element->forward[i] != EltPtr.nil &&
+ list->greater (value,
+ x.element->forward[i].element->value))
x = x.element->forward[i];
}
x = x.element->forward[0];
- if (gt (x, key))
+ if (x == EltPtr.nil || list->greater (x.element->value, value))
return ElementPtr.nil;
return x;
}
+
+ public ElementPtr first (Lst list)
+ {
+ return list->header.forward[0];
+ }
- public void insert (List list, ElementPtr new, Greater gt)
+ public ElementPtr next (Lst list, EltPtr x)
{
- ElementPtr[MaxLevel] update = {};
- ElementPtr x = (ElementPtr.element) &list->header;
+ return x.element->forward[0];
+ }
+
+ public ElementPtr prev (Lst list, EltPtr x)
+ {
+ EltPtr prev = x.element->backward[0];
+ if (prev == (EltPtr.element) &list->header)
+ return ElementPtr.nil;
+ return prev;
+ }
+
+ public ElementPtr element (poly value)
+ {
+ return (ElementPtr.element) &(Elt) { value = value };
+ }
+
+ public void insert (Lst list, EltPtr new)
+ {
+ EltPtr[MaxLevel] update = {};
+ EltPtr x = (EltPtr.element) &list->header;
for (int i = list->level; --i >= 0;)
{
- while (x.element->forward[i] != ElementPtr.nil &&
- gt (new, x.element->forward[i]))
+ while (x.element->forward[i] != EltPtr.nil &&
+ list->greater (new.element->value,
+ x.element->forward[i].element->value))
x = x.element->forward[i];
update[i] = x;
}
@@ -121,72 +173,108 @@
{
level = list->level + 1;
list->level = level;
- update[level-1] = (ElementPtr.element) &list->header;
+ update[level-1] = (EltPtr.element) &list->header;
}
- new.element->forward = (ElementPtr[level]) { };
+
+ new.element->forward = (EltPtr[level]) {};
+ new.element->backward = (EltPtr[level]) {};
+
for (int i = 0; i < level; i++)
{
new.element->forward[i] = update[i].element->forward[i];
+ new.element->backward[i] = update[i];
+
+ if (update[i].element->forward[i] != EltPtr.nil)
+ update[i].element->forward[i].element->backward[i] = new;
+
update[i].element->forward[i] = new;
}
}
- public void delete (List list, ElementPtr old, Greater gt)
+ public void delete (Lst list, EltPtr old)
{
- ElementPtr[MaxLevel] update = {};
- ElementPtr x = (ElementPtr.element) &list->header;
-
- for (int i = list->level; --i >= 0;)
- {
- while (x.element->forward[i] != ElementPtr.nil &&
- gt (old, x.element->forward[i]))
- x = x.element->forward[i];
- update[i] = x;
- }
- x = x.element->forward[0];
- if (gt (x, old))
- raise not_found (old);
- for (int i = 0; i < list->level; i++)
+ for (int i = 0; i < dim (old.element->forward); i++)
{
- if (update[i].element->forward[i] != x)
- break;
- update[i].element->forward[i] = x.element->forward[i];
+ EltPtr prev = old.element->backward[i];
+ EltPtr next = old.element->forward[i];
+
+ prev.element->forward[i] = next;
+ if (next != EltPtr.nil)
+ next.element->backward[i] = prev;
}
+
while (list->level > 0 &&
- list->header.forward[list->level] == ElementPtr.nil)
+ list->header.forward[list->level] == EltPtr.nil)
list->level--;
}
- public void swap (List list, ElementPtr first, Greater gt)
+ public void swap (Lst list, EltPtr x)
{
- ElementPtr[MaxLevel] update = {};
- ElementPtr x = (ElementPtr.element) &list->header;
-
- for (int i = list->level; --i >= 0;)
- {
- while (x.element->forward[i] != ElementPtr.nil &&
- gt (first, x.element->forward[i]))
- x = x.element->forward[i];
- update[i] = x;
- }
- x = x.element->forward[0];
- if (gt (x, first))
- raise not_found (first);
-
- ElementPtr y = x.element->forward[0];
+ EltPtr y = x.element->forward[0];
+ int d = min (dim (x.element->forward),
+ dim (y.element->forward));
/*
* Swap links at all levels x and y have in common
*/
- for (int i = 0; i < list->level; i++)
+ for (int i = 0; i < d; i++)
{
- if (update[i].element->forward[i] != x)
- break;
- if (x.element->forward[i] != y)
- break;
- x.element->forward[i] = y.element->forward[i];
+ EltPtr prev = x.element->backward[i];
+ EltPtr next = y.element->forward[i];
+
+ prev.element->forward[i] = y;
y.element->forward[i] = x;
- update[i].element->forward[i] = y;
+ x.element->forward[i] = next;
+
+ if (next != EltPtr.nil)
+ next.element->backward[i] = x;
+ x.element->backward[i] = y;
+ y.element->backward[i] = prev;
}
}
+
+ public void walk (Lst list, Visit visit)
+ {
+ for (EltPtr e = list->header.forward[0];
+ e != EltPtr.nil;
+ e = e.element->forward[0])
+ visit (e);
+ }
+
+ public bool (&poly) iterate (Lst list)
+ {
+ EltPtr e = list->header.forward[0];
+
+ bool next (&poly value) {
+ if (e == EltPtr.nil)
+ return false;
+ value = e.element->value;
+ e = e.element->forward[0];
+ return true;
+ }
+
+ return next;
+ }
+
+ public int storage (Lst list, poly value)
+ {
+ EltPtr x = (EltPtr.element) &list->header;
+
+ for (int i = list->level; --i >= 0; )
+ {
+ while (x.element->forward[i] != EltPtr.nil &&
+ list->greater (value,
+ x.element->forward[i].element->value))
+ x = x.element->forward[i];
+ }
+ x = x.element->forward[0];
+ if (list->greater (x.element->value, value))
+ raise not_found (value);
+ return dim (x.element->forward);
+ }
+
+}
+
+namespace Sortlist {
+ public import Skiplist;
}
Index: skiplisttest.5c
===================================================================
RCS file: /local/src/CVS/tess/skiplisttest.5c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- skiplisttest.5c 10 Jul 2004 07:52:22 -0000 1.1
+++ skiplisttest.5c 11 Jul 2004 05:53:18 -0000 1.2
@@ -1,18 +1,11 @@
-autoimport Skiplist;
-
-typedef IntElement;
-
-typedef union {
- *IntElement element;
- void nil;
-} IntElementPtr;
+autoload Skiplist;
-typedef struct {
- ElementPtr[*] forward;
- int i;
-} IntElement;
+int gt_count = 0;
-bool int_gt (IntElementPtr a, IntElementPtr b) = a.element->i > b.element->i;
+bool int_gt (int a, int b) {
+ ++gt_count;
+ return a > b;
+}
public int[*] rand_array (int n)
{
@@ -21,44 +14,43 @@
return a;
}
-public void insert_int (List l, int i) {
- insert (l, (IntElementPtr.element) &(IntElement) { i = i }, int_gt);
+public void insert_int (Sortlist::List l, int i) {
+ Sortlist::ElementPtr e = Sortlist::element (i);
+ Sortlist::insert (l, e);
}
-public void insert_ints (List l, int[*] i) {
+public void insert_ints (Sortlist::List l, int[*] i) {
for (int j = 0; j < dim(i); j++)
insert_int (l, i[j]);
}
-public List rand_ints (int n)
+public Sortlist::List rand_ints (int n)
{
- List l = new ();
+ Sortlist::List l = Sortlist::new (int_gt);
+
insert_ints (l, rand_array(n));
return l;
}
-public int search_len (List l, int i)
+public int search_len (Sortlist::List l, int i)
{
- int len = 0;
-
- bool gt (IntElementPtr a, IntElementPtr b)
- {
- len++;
- return a.element->i > b.element->i;
- }
+ int old_count = gt_count;
- search (l, (IntElementPtr.element) &(IntElement) {i = i}, gt);
- return len;
+ Sortlist::search (l, i);
+ return gt_count - old_count;
}
-public void dump (List l)
+public void dump (Sortlist::List l)
{
- for (IntElementPtr e = l->header.forward[0];
- e != IntElementPtr.nil;
- e = e.element->forward[0])
+ Sortlist::ElementPtr e;
+ for (e = Sortlist::first (l);
+ e != Sortlist::ElementPtr.nil;
+ e = Sortlist::next (l, e))
{
- printf ("%4d ", e.element->i);
- for (int i = 0; i < dim(e.element->forward); i++)
+ int value = e.element->value;
+ printf ("%4d ", value);
+ int store = Sortlist::storage (l, value);
+ for (int i = 0; i < store; i++)
printf (" |");
printf ("\n");
}
@@ -84,29 +76,26 @@
}
}
-public void analyse (List l)
+public void analyse (Sortlist::List l)
{
- int[l->level] levels = { 0 ... };
- int[...] slens = {};
+ int[...] store = {};
+ int[...] search = {};
- void incslens(int i) {
- while (dim(slens) <= i)
- slens[dim(slens)] = 0;
- slens[i]++;
+ void inc_array(&int[...] a, int i) {
+ while (dim(a) <= i)
+ a[dim(a)] = 0;
+ a[i]++;
}
- for (IntElementPtr e = l->header.forward[0];
- e != IntElementPtr.nil;
- e = e.element->forward[0])
+ for (bool (&poly) next = Sortlist::iterate (l); next (&(int value));)
{
- int slen = search_len (l, e.element->i);
- incslens(slen);
- levels[dim(e.element->forward) - 1]++;
+ inc_array (&store, Sortlist::storage (l, value));
+ inc_array (&search, search_len (l, value));
}
- printf ("len distribution\n");
- histogram (levels);
+ printf ("storage distribution\n");
+ histogram (store);
printf ("search distribution\n");
- histogram (slens);
+ histogram (search);
}
--- NEW FILE: slist.5c ---
(This appears to be a binary file; contents omitted.)
- Previous message: [Commit] tess ChangeLog, 1.13, 1.14 skiplist.5c, NONE,
1.1 skiplisttest.5c, NONE, 1.1
- Next message: [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
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the Commit
mailing list