[Commit] tess ChangeLog, 1.13, 1.14 skiplist.5c, NONE, 1.1 skiplisttest.5c, NONE, 1.1

[Keith Packard]

Committed by: keithp

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

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

	* skiplist.5c:
	* skiplisttest.5c:
	Add skip list implementation.  This isn't used yet, but it
	sure looks good.  Supports insert, delete, swap and search.
	Traversal is trivial, but there isn't a function to do it.


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/tess/ChangeLog,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- ChangeLog	9 Jul 2004 19:19:15 -0000	1.13
+++ ChangeLog	10 Jul 2004 07:52:22 -0000	1.14
@@ -1,3 +1,11 @@
+2004-07-10  Keith Packard  <keithp at keithp.com>
+
+	* skiplist.5c:
+	* skiplisttest.5c:
+	Add skip list implementation.  This isn't used yet, but it
+	sure looks good.  Supports insert, delete, swap and search.
+	Traversal is trivial, but there isn't a function to do it.
+
 2004-07-09  Carl Worth  <cworth at isi.edu>
 
 	* sortlist.5c (delete): Reset prev/next to List.nil to catch bugs

--- NEW FILE: skiplist.5c ---
(This appears to be a binary file; contents omitted.)

--- NEW FILE: skiplisttest.5c ---
autoimport Skiplist;

typedef IntElement;

typedef union {
    *IntElement	element;
    void	nil;
} IntElementPtr;

typedef struct {
    ElementPtr[*]   forward;
    int	    i;
} IntElement;

bool int_gt (IntElementPtr a, IntElementPtr b) = a.element->i > b.element->i;

public int[*] rand_array (int n)
{
    int[n] a = { [i] = i };
    PRNG::shuffle (&a);
    return a;
}

public void insert_int (List l, int i) {
    insert (l, (IntElementPtr.element) &(IntElement) { i = i }, int_gt);
}

public void insert_ints (List l, int[*] i) {
    for (int j = 0; j < dim(i); j++)
	insert_int (l, i[j]);
}

public List rand_ints (int n)
{
    List    l = new ();
    insert_ints (l, rand_array(n));
    return l;
}

public int search_len (List l, int i)
{
    int	len = 0;
    
    bool gt (IntElementPtr a, IntElementPtr b)
    {
	len++;
	return a.element->i > b.element->i;
    }

    search (l, (IntElementPtr.element) &(IntElement) {i = i}, gt);
    return len;
}

public void dump (List l)
{
    for (IntElementPtr e = l->header.forward[0]; 
	 e != IntElementPtr.nil;
	 e = e.element->forward[0])
    {
	printf ("%4d ", e.element->i);
	for (int i = 0; i < dim(e.element->forward); i++)
	     printf (" |");
	printf ("\n");
    }
}

public void histogram (real[*] l)
{
    int	largest = 0;
    for (int i = 0; i < dim (l); i++)
	if (l[i] > largest)
	    largest = l[i];

    int width = 80 - 17;
    real scale = width / largest;

    for (int i = 0; i < dim (l); i++)
    {
	printf ("%5d %10g ", i, l[i]);
	int lim = floor (l[i] * scale + 0.5);
	for (int j = 0; j < lim; j++)
	    printf ("*");
	printf ("\n");
    }
}

public void analyse (List l)
{
    int[l->level]   levels = { 0 ... };
    int[...]	    slens = {};
    
    void incslens(int i) {
	while (dim(slens) <= i)
	    slens[dim(slens)] = 0;
	slens[i]++;
    }

    for (IntElementPtr e = l->header.forward[0]; 
	 e != IntElementPtr.nil;
	 e = e.element->forward[0])
    {
	int slen = search_len (l, e.element->i);
	incslens(slen);
	levels[dim(e.element->forward) - 1]++;
    }

    printf ("len distribution\n");
    histogram (levels);
    
    printf ("search distribution\n");
    histogram (slens);
}