[Commit] tess avl.5c, 1.1.1.1, 1.2 sortlist.5c, NONE,
1.1 sortlisttest.5c, NONE, 1.1
Keith Packard
commit at keithp.com
Thu Jul 1 23:53:37 PDT 2004
Committed by: keithp
Update of /local/src/CVS/tess
In directory home.keithp.com:/tmp/cvs-serv30613
Modified Files:
avl.5c
Added Files:
sortlist.5c sortlisttest.5c
Log Message:
Add sorted list functions
Index: avl.5c
===================================================================
RCS file: /local/src/CVS/tess/avl.5c,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- avl.5c 2 Jul 2004 02:03:31 -0000 1.1.1.1
+++ avl.5c 2 Jul 2004 06:53:34 -0000 1.2
@@ -84,7 +84,7 @@
public void valid_node (*Node n, bool check_range)
{
- printf ("valid_node\n");
+# printf ("valid_node\n");
if (n != &nil)
{
if (check_range)
@@ -451,6 +451,62 @@
}
}
+ public poly prev (Tree tree, poly key)
+ {
+ *Node n = tree->root;
+ *Node right = &nil;
+
+ while (n != &nil)
+ {
+ int c = tree->order (n->key, key);
+ if (c == 0)
+ {
+ if (n->left == &nil)
+ return right->key;
+ n = n->left;
+ while (n->right != &nil)
+ n = n->right;
+ return n->key;
+ }
+ if (c < 0)
+ n = n->left;
+ else
+ {
+ right = n;
+ n = n->right;
+ }
+ }
+ raise not_found (key);
+ }
+
+ public poly next (Tree tree, poly key)
+ {
+ *Node n = tree->root;
+ *Node left = &nil;
+
+ while (n != &nil)
+ {
+ int c = tree->order (n->key, key);
+ if (c == 0)
+ {
+ if (n->right == &nil)
+ return left->key;
+ n = n->right;
+ while (n->left != &nil)
+ n = n->left;
+ return n->key;
+ }
+ if (c < 0)
+ {
+ left = n;
+ n = n->left;
+ }
+ else
+ n = n->right;
+ }
+ raise not_found (key);
+ }
+
public bool(*poly) iterate (Tree tree)
/*
* Return a function which will walk the tree
@@ -544,6 +600,15 @@
int[*] a = rand_array (n);
insert_array (t, a);
validate (t);
+ walk (t, void func (poly a) {
+ static p = &nil;
+ if (p != &nil)
+ {
+ assert (prev(t, a) == p,
+ "bad prev %v != %v\n", prev(t,a), p);
+ }
+ p = a;
+ });
PRNG::shuffle (&a);
delete_array (t, a);
validate (t);
--- NEW FILE: sortlist.5c ---
#
# Doublely linked sorted lists
#
namespace Sortlist {
public typedef ListElt;
public typedef union {
*ListElt elt;
void nil;
} List;
typedef struct {
List prev, next;
} ListElt;
typedef bool (List a, List b) Greater;
public void validate_elt (List a)
{
if (a == List.nil)
return;
assert (a.elt->prev == List.nil || a.elt->prev.elt->next == a,
"bad prev");
assert (a.elt->next == List.nil || a.elt->next.elt->prev == a,
"bad next");
}
public void validate (List a)
{
assert (a == List.nil || a.elt->prev == List.nil,
"bad head");
while (a != List.nil)
{
validate_elt (a);
a = a.elt->next;
}
}
List add (List head, List before, List new)
{
List after;
if (before == List.nil)
{
after = head;
head = new;
}
else
after = before.elt->next;
new.elt->prev = before;
new.elt->next = after;
if (before != List.nil)
before.elt->next = new;
if (after != List.nil)
after.elt->prev = new;
validate (head);
return head;
}
public List insert (List head, List new, Greater gt)
{
if (head == List.nil)
{
new.elt->next = List.nil;
new.elt->prev = List.nil;
return new;
}
List l = head;
List p = l.elt->prev;
while (l != List.nil && gt (new, l))
{
p = l;
l = l.elt->next;
}
return add (head, p, new);
}
public List delete (List head, List old)
{
if (old.elt->prev != List.nil)
old.elt->prev.elt->next = old.elt->next;
else
head = old.elt->next;
if (old.elt->next != List.nil)
old.elt->next.elt->prev = old.elt->prev;
validate (head);
return head;
}
public List swap (List head, List a)
{
List b = a.elt->next;
/* remove a */
head = delete (head, a);
/* add a after b */
return add (head, b, a);
}
}
--- NEW FILE: sortlisttest.5c ---
autoimport Sortlist;
typedef IntListElt;
typedef union {
*IntListElt elt;
void nil;
} IntList;
typedef struct {
List prev, next;
int i;
} IntListElt;
IntList l = (IntList.elt) &(IntListElt) { i = 7 };
bool int_gt (IntList a, IntList b) = a.elt->i > b.elt->i;
public int[*] rand_array (int n)
{
int[n] a = { [i] = i };
PRNG::shuffle (&a);
return a;
}
public IntList insert_int (IntList head, int i) {
return insert (head, (IntList.elt) &(IntListElt) { i = i }, int_gt);
}
public IntList insert_ints (IntList head, int[*] i) {
for (int j = 0; j < dim(i); j++)
head = insert_int (head, i[j]);
return head;
}
public IntList rand_ints (int n)
{
IntList head = IntList.nil;
return insert_ints (head, rand_array(n));
}
public void dump_ints (IntList l)
{
while (l != IntList.nil)
{
printf ("%d ", l.elt->i);
l = l.elt->next;
}
printf ("\n");
}
More information about the Commit
mailing list