E find(const Key& k) const
{
    SkipNode<Key,E> *x = head;		//dummy head node    
    for (int i=level; i>=0;i--)
	while ((x->forward[i] != NULL)&&(k>x->forward[i]->k))
	    x = x->forward[i];
    x = x->forward[0];
    if ((x!=NULL)&&(k==x->k)) return x->it;
    return NULL;
}

void insert(const Key& k, const E& it)
{
    int i;
    SkipNode<Key,E> *x = head;
    int newLevel = randomLevel();
    if (newLevel > level)	//new node is deapest in list
    {
	AdjustHead(newLevel);	//add null pointer to header
	level = newLevel;
    }
    SkipNode<Key,E>* update[level+1];
    for (i=level; i>=0; i--)	//search for insert position
    {
	while ((x->forward[i] != NULL)&& (x->forward[i]->k <k))
	    x = x->forward[i];
	update[i] =x;
    }
    x = new SkipNode<Key,E>(k,it,newLevel);
    for (i=0; i<=newLevel; i++)
    {
	x->forward[i] = update[i]->forward[i];
	update[i]->forward[i] = x;
    }
}

//pick a level using an exponential distribution
int randomLevel(void)
{
    int level = 0;
    while (Random(2)==0) level++;
    return level;
}