/* $Header$ */

/*
 * Copyright © 2004 Keith Packard and Bart Massey.
 * All Rights Reserved.  See the file COPYING in this directory
 * for licensing information.
 */

autoload PRNG;

namespace Skiplist {
    public typedef *struct {
    } List;

    public typedef bool (poly a, poly b) Greater;

    public typedef void (poly a) Visit;
    
    public exception not_found (poly missing);
    
    /*
     * Private representation of an element
     */
    typedef Element;

    typedef union {
	*Element	element;
	void		nil;
    } ElementPtr;

    const MaxLevel = 16;

    typedef struct {
	poly		value;
	ElementPtr[*]	forward;
    } Element;

    typedef struct {
	int		level;
	Greater		greater;
	Element		header;
    } SkipRec;

    typedef *SkipRec Skip;

    int random_level ()
	/*
	 * This uses a fixed probability of 1/4 for each level
	 */
    {
	int bits = PRNG::randbits(MaxLevel * 2);
	int level = 0;
	
	while (++level < MaxLevel)
	{
	    if ((bits & 3) != 0)
		break;
	    bits >>= 2;
	}
	return level;
    }
    
    public List new (Greater greater)
	/*
	 * Allocate a new list with 'greater' as the ordering function
	 */
    {
	return &(SkipRec) {
	    .level = 0,
	    .greater = greater,
	    .header = { 
		.forward = (ElementPtr[MaxLevel]) { [i] = ElementPtr.nil },
		.value = <> 
	    }
	};
    }

    public poly search (Skip list, poly value)
	/*
	 * Search 'list' for 'value', returning a
	 * matching value in the list else Raise 'not_found'.
	 */
    {
	ElementPtr x = (ElementPtr.element) &list->header;

	for (int i = list->level; --i >= 0; )
	{
	    while (x.element->forward[i] != ElementPtr.nil &&
		   list->greater (value, 
				  x.element->forward[i].element->value))
		x = x.element->forward[i];
	}
	x = x.element->forward[0];
	if (x == ElementPtr.nil || list->greater (x.element->value, value))
	    raise not_found (value);
	return x.element->value;
    }

    public void insert (Skip list, poly value)
	/*
	 * Insert 'value' into 'list'
	 */
    {
	ElementPtr[MaxLevel] update = {};
	ElementPtr x = (ElementPtr.element) &list->header;

	for (int i = list->level; --i >= 0;)
	{
	    while (x.element->forward[i] != ElementPtr.nil && 
		   list->greater (value, 
				  x.element->forward[i].element->value))
		x = x.element->forward[i];
	    update[i] = x;
	}
	x = x.element->forward[0];
	int level = random_level ();
	if (level > list->level)
	{
	    level = list->level + 1;
	    list->level = level;
	    update[level-1] = (ElementPtr.element) &list->header;
	}

	/*
	 * Allocate new list entry
	 */
	ElementPtr new = (ElementPtr.element) &(Element) {
	    .value = value,
	    .forward = (ElementPtr[level]) {}
	};
	
	for (int i = 0; i < level; i++)
	{
	    new.element->forward[i] = update[i].element->forward[i];
	    update[i].element->forward[i] = new;
	}
    }

    public void delete (Skip list, poly value)
	 /*
	  * delete entry matching 'value' from 'list', else
	  * raise not_found.
	  */
    {
	ElementPtr[MaxLevel] update = {};
	ElementPtr x = (ElementPtr.element) &list->header;

	for (int i = list->level; --i >= 0;)
	{
	    while (x.element->forward[i] != ElementPtr.nil && 
		   list->greater (value, 
				  x.element->forward[i].element->value))
		x = x.element->forward[i];
	    update[i] = x;
	}
	x = x.element->forward[0];
	if (x == ElementPtr.nil || list->greater (x.element->value, value))
	    raise not_found (value);

	for (int i = 0; 
	     i < list->level && update[i].element->forward[i] == x; 
	     i++)
	{
	    update[i].element->forward[i] = x.element->forward[i];
	}
	
	while (list->level > 0 &&
	       list->header.forward[list->level-1] == ElementPtr.nil)
	    list->level--;
    }

    public void walk (Skip list, Visit visit)
	/*
	 * Invoke 'visit' for each element of 'list'.
	 * Operations on 
	 */
    {
	for (ElementPtr e = list->header.forward[0];
	     e != ElementPtr.nil;
	     e = (ElementPtr next))
	 {
	    next = e.element->forward[0];
	    visit (e.element->value);
	 }
    }

    public bool (&poly) iterate (Skip list)
    {
	ElementPtr  e = list->header.forward[0];

	bool next (&poly value) {
	    if (e == ElementPtr.nil)
		return false;
	    value = e.element->value;
	    e = e.element->forward[0];
	    return true;
	}

	return next;
    }

    public int storage (Skip list, poly value)
    {
	ElementPtr x = (ElementPtr.element) &list->header;

	for (int i = list->level; --i >= 0;)
	{
	    while (x.element->forward[i] != ElementPtr.nil && 
		   list->greater (value, 
				  x.element->forward[i].element->value))
		x = x.element->forward[i];
	}
	x = x.element->forward[0];
	if (x == ElementPtr.nil || list->greater (x.element->value, value))
	    raise not_found (value);
	return dim (x.element->forward);
    }
}

namespace Sortlist {
    public import Skiplist;
}