// This may look like C code, but it is really -*- C++ -*-
/* 
Copyright (C) 1991 Free Software Foundation

This file is part of the GNU C++ Library.  This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.  This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.  See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifdef __GNUG__
#pragma implementation
#endif

#include <stream.h>
#include <time.h>
#include "<T>.<C>.SkipMap.h"

/*
 * Bags implemented via William Pugh SkipList algorithms.
 * CACM, June 1990, p 668-676.
 *
 */

MLCG* <T><C>SkipMap::gen = 0;
int <T><C>SkipMapinit::count = 0;

static int countbits(long bits)
{
  int n = 0;
  while(bits>>=1) n++;
  return n;
}

<T><C>SkipMap::<T><C>SkipMap(<C&> dflt, long size)
: <T><C>Map(dflt),
  level(0),
  header(new <T><C>SkipMapNode (countbits(size)+1)),
  max_levels (countbits(size)+1),
  random_bits(gen->asLong()),
  randoms_left(BITS_IN_RANDOM / 2)
{
  <T><C>SkipMapNodePtr *buffer_start = header->forward;
  <T><C>SkipMapNodePtr *trav = &header->forward[max_levels];
  
  count = 0;
  while (trav > buffer_start)
    *--trav = (<T><C>SkipMapNodePtr) header;
}

<T><C>SkipMap::<T><C>SkipMap(<T><C>SkipMap& b)
: <T><C>Map(b.def),
  level (0),
  header (new <T><C>SkipMapNode (b.max_levels)),
  max_levels (b.max_levels),
  random_bits (gen->asLong()),
  randoms_left (BITS_IN_RANDOM / 2)
{
  <T><C>SkipMapNodePtr *buffer_start = header->forward;
  <T><C>SkipMapNodePtr *trav = &header->forward[max_levels];
  
  count = 0;
  
   while (trav > buffer_start)
     *--trav = (<T><C>SkipMapNodePtr)header;
  
  for (<T><C>SkipMapNodePtr t = b.leftmost(); t; t = b.succ(t))
    (*this)[t->item] = t->cont;
}

<C>& <T><C>SkipMap::operator [] (<T&> item)
{
  <T><C>SkipMapNodePtr *update = new <T><C>SkipMapNodePtr[max_levels+1];
  <T><C>SkipMapNodePtr curr =
    (<T><C>SkipMapNodePtr) this->header;
  int   l = level;
  <T><C>SkipMapNodePtr temp;
  
  do
  {
    while ((temp = curr->forward[l])!=header &&
	   <T>CMP(temp->item, item) < 0)
      curr = temp;
    update[l] = curr;
  } 
  while (--l >= 0);
  
  if (temp != header && <T>CMP(temp->item, item) == 0)
  {
      delete update;
      return temp->cont;
  }

  if ((l = random_level ()) > level)
  {
    l = ++level;
    update[l] = (<T><C>SkipMapNodePtr)header;
  };

  temp = new <T><C>RealSkipMapNode (item, def, l);
  <T><C>SkipMapNodePtr *temp_forward = temp->forward;
  
  do
  {
    <T><C>SkipMapNodePtr *curr_forward = update[l]->forward;
    
    temp_forward[l] = curr_forward[l];
    curr_forward[l] = temp;
  } 
  while (--l >= 0);

  count++;
  delete update;
  return temp->cont;
}

void <T><C>SkipMap::del(<T&> key)
{
  
  int   l = level;
  int   curr_level = level;
  <T><C>SkipMapNodePtr *update = new <T><C>SkipMapNodePtr[max_levels+1];
  <T><C>SkipMapNodePtr curr = (<T><C>SkipMapNodePtr)header;
  <T><C>SkipMapNodePtr temp;
  
  do
  {
    while ((temp = curr->forward[l])!=header
	   && <T>CMP(temp->item,key) < 0)
      curr = temp;
    update[l] = curr;
  } 
  while (--l >= 0);
  
  if (<T>CMP(temp->item,key)==0)
  {
    <T><C>SkipMapNodePtr *temp_forward = temp->forward;
    
    for (l = 0;
	 l <= curr_level && (curr = update[l])->forward[l] == temp;
	 l++)
      curr->forward[l] = temp_forward[l];
    
    delete temp;
    
    <T><C>SkipMapNodePtr *forward = header->forward;
    
    while (forward[curr_level]==header && curr_level > 0)
      curr_level--;
    
    level = curr_level;
    count--;
    delete update;
    return;
  }
}

<T><C>SkipMapNodePtr <T><C>SkipMap::rightmost()
{
  <T><C>SkipMapNodePtr temp;
  <T><C>SkipMapNode*   curr = header;
  int l = level;
  
  do
    while ((temp = curr->forward[l])!=header)
      curr = temp;
  while (--l >= 0);
  
  return temp==header ? 0 : temp;
}

<T><C>SkipMapNodePtr <T><C>SkipMap::pred(<T><C>SkipMapNodePtr t)
{
  <T><C>SkipMapNodePtr temp, curr = (<T><C>SkipMapNodePtr) header;
  int l = level;
  
  do
    while ((temp = curr->forward[l])!=t)
      curr = temp;
  while (--l >= 0);
  
  return curr == header ? 0 : curr;
}

void <T><C>SkipMap::_kill()
{
  <T><C>SkipMapNode *p = this->header->forward[0];
  
  while (p != header)
  {
    <T><C>SkipMapNodePtr q = p->forward[0];
    delete p;
    p = q;
  }
}

void <T><C>SkipMap::clear()
{
  <T><C>SkipMapNodePtr *buffer_start = header->forward;
  <T><C>SkipMapNodePtr *trav = &header->forward[level+1];
  _kill();
  count = 0;
    
  while (trav > buffer_start)
    *--trav = (<T><C>SkipMapNodePtr)header;
}

Pix <T><C>SkipMap::seek(<T&> key)
{
  <T><C>SkipMapNodePtr temp;
  <T><C>SkipMapNode *curr  = header;
  int   l = level;
    
  do
  {
    while ((temp = curr->forward[l])!=header &&
	   <T>CMP(temp->item, key) < 0)
      curr = temp;
  }
  while (--l >= 0);
  
  if (<T>CMP(temp->item, key) != 0)
    return 0;
  else
  {
    return Pix(temp);
  }
}

/*
 * random function for probabilistic balancing
 *
 * Hardwired for p = .25.  Not too flexible,
 * but fast.  Changing this would require a constructor
 * that would accept a different value for p, etc.
 * Perhaps someone else would like to implement this?
 *
 */
int <T><C>SkipMap::random_level (void)
{
  int rlevel = 0;
  int b;
  
  do
  {
    b = random_bits & 3L;
    if (!b)
      rlevel++;
    random_bits >>= 2;
    if (--randoms_left == 0)
    {
      random_bits = gen->asLong();
      randoms_left = BITS_IN_RANDOM / 2;
    };
  } 
  while (!b);
  
  return rlevel > max_levels ? max_levels : rlevel;
}

int <T><C>SkipMap::OK()
{
  int v = 1;
  if (header == 0) 
    v = 0;
  else
  {
    int n = 0;
    <T><C>SkipMapNodePtr trail = leftmost();
    <T><C>SkipMapNodePtr t = 0;
    if (trail) t = succ(trail);
    if (t) n++;
    while (t != 0)
    {
      ++n;
      v &= <T>CMP(trail->item, t->item) < 0;
      trail = t;
      t = succ(t);
    }
    v &= n == count;
  }
  if (!v) error("invariant failure");
  return v;
}

<T><C>SkipMapinit::<T><C>SkipMapinit()
{
    if (!count)
	<T><C>SkipMap::gen = new MLCG(time(0));
    count++;
}

<T><C>SkipMapinit::~<T><C>SkipMapinit()
{
    count--;
    if (!count)
	delete <T><C>SkipMap::gen;
}