[Commit] tess avl.5c, 1.1.1.1, 1.2 sortlist.5c, NONE, 1.1 sortlisttest.5c, NONE, 1.1

[Keith Packard]

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");
}