/*******************************************************************************
+
+  LEDA 3.5
+
+  _skiplist.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

//------------------------------------------------------------------------------
//
//  skip lists 
//
//  doubly linked
//
//  S. Naeher (1992-96)
//
//------------------------------------------------------------------------------

 
#include <LEDA/impl/skiplist.h>

inline int NODE_SIZE(int l)
{ int l1 = 1;
  while (l1 < l) l1 <<= 1; 
  return int(sizeof(skiplist_node))+(l1)*int(sizeof(skiplist_node*));
}
  
 
#define NEW_NODE(p,l) p=(skiplist_item)std_memory.allocate_bytes(NODE_SIZE(l)); p->level=l;

#define FREE_NODE(p)  std_memory.deallocate_bytes(p,NODE_SIZE(p->level))



leda_mutex skiplist_node::mutex_id_count;

unsigned long skiplist_node::id_count = 0;
 
const int BitsInRandom      = 31;
const int MaxNumberOfLevels = 32;
 
skiplist::skiplist(float p) 
{ prob = p;
  randomBits = ran.get();
  randomsLeft = BitsInRandom;
  level = 0;
  count = 0;

  //NEW_NODE(header,MaxNumberOfLevels-1);
  header = (skiplist_node*)malloc(NODE_SIZE(MaxNumberOfLevels));
  header->level = MaxNumberOfLevels-1;

  NEW_NODE(stopper,-1);
  stopper->backward = header;
  stopper->pred = header;

  for(int i=0;i<MaxNumberOfLevels;i++) header->forward[i] = stopper;
  header->backward = 0;
  header->pred = 0;

 } 
 
skiplist::skiplist(const skiplist& L) 
{ prob = L.prob;
  randomBits = ran.get();
  randomsLeft = BitsInRandom;
  level = 0;
  count = 0;

  //NEW_NODE(header,MaxNumberOfLevels-1);
  header = (skiplist_node*)malloc(NODE_SIZE(MaxNumberOfLevels));
  header->level = MaxNumberOfLevels-1;

  NEW_NODE(stopper,-1);
  stopper->backward = header;
  stopper->pred = header;

  for(int i=0;i<MaxNumberOfLevels;i++) header->forward[i] = stopper;
  header->backward = 0;
  header->pred = 0;

 
  skiplist_item p = L.stopper->pred;
  while (p!= L.header) 
  { insert_at_item(header,p->key,p->inf);
    L.copy_key(p->key);
    L.copy_inf(p->inf);
    p = p->pred;
   }
 } 
 
 
skiplist& skiplist::operator=(const skiplist& L) 
{ clear();
  skiplist_item p = L.stopper->pred;
  while (p!= L.header) 
  { insert_at_item(header,p->key,p->inf);
    p = p->pred;
   }
  return *this;
 } 
 
void skiplist::clear() 
{ skiplist_item p,q;
  p = header->forward[0];
  while(p!=stopper)
  { q = p->forward[0];
    clear_key(p->key);
    clear_inf(p->inf);
    FREE_NODE(p);
    p = q; 
   }
 level = 0;
 for(int i=0;i<MaxNumberOfLevels;i++) header->forward[i] = stopper;
 stopper->pred = header;
 count = 0;
}
 
 
 
skiplist::~skiplist() 
{ clear();
  free((char*)header);
  FREE_NODE(stopper);
 }
 
 
int skiplist::randomLevel()
{ int lev = 0;
  unsigned long b = 0;

   while (b==0)
   { b = randomBits&3;    // read next two random bits
     randomBits >>= 2;
     randomsLeft -= 2;
     if (b==0) lev++;   // increase level with prob 0.25
     if (randomsLeft < 2) 
     { randomBits = ran.get();
       randomsLeft = BitsInRandom;
      }
    }
/*
    // user defined probability "prob"
    { float r;
      ran >> r;
      while (r < prob)
      { lev++;
        ran >> r;
       }
     }
*/
    
   return lev;
 }
 

skiplist_item skiplist::search(GenPtr key, int& l) const
{ switch (key_type_id()) {
  case INT_TYPE_ID:    return int_search(key,l);
  case DOUBLE_TYPE_ID: return double_search(key,l);
  default:             return gen_search(key,l);
  }
}


skiplist_item skiplist::gen_search(GenPtr key, int& l) const
{ skiplist_item p = header;
  skiplist_item q = 0;
  int k;
  int c=1;
 
  for(k = level; k>=0; k--)
  { q = p->forward[k];
    while (k==q->level && (c=cmp(key,q->key)) > 0)
    { p = q;
      q = p->forward[k];
#if defined(MULTI_THREAD)
      if (q == stopper) break;
#endif
     }
    if(c==0) break;
   }

  l = k;
  return q;
 }
 

 
 
skiplist_item skiplist::int_search(GenPtr key, int& l) const
{ skiplist_item p = header;
  skiplist_item q = 0;
  int ki = LEDA_ACCESS(int,key);
  int k;
 
  stopper->key = key;
  for(k = level; k>=0; k--)
  { q = p->forward[k];
    while (ki > LEDA_ACCESS(int,q->key)) 
    { p = q;
      q = p->forward[k];
#if defined(MULTI_THREAD)
      if (q == stopper) break;
#endif
     }
    if(ki==LEDA_ACCESS(int,q->key) && q != stopper) break;
   }

  l = k;
  return q;
 }
 

skiplist_item skiplist::double_search(GenPtr key, int& l) const
{ skiplist_item p = header;
  skiplist_item q = 0;
  double kd = LEDA_ACCESS(double,key);
  int k;
 
  stopper->key = key;
  for(k = level; k>=0; k--)
  { q = p->forward[k];
    while (kd > LEDA_ACCESS(double,q->key)) 
    { p = q;
      q = p->forward[k];
#if defined(MULTI_THREAD)
      if (q == stopper) break;
#endif
     }
    if(kd==LEDA_ACCESS(double,q->key) && q != stopper) break;
   }

  l = k;
  return q;
 }
 
 


skiplist_item skiplist::locate(GenPtr key) const { return locate_succ(key); }


skiplist_item skiplist::locate_succ(GenPtr key) const
{ int k;
  skiplist_item q = search(key,k);
  return (q==stopper) ? 0 : q;
 }

skiplist_item skiplist::locate_pred(GenPtr key) const
{ int k;
  skiplist_item q = search(key,k);
  if (q==stopper) return max();
  if (cmp(key,q->key)!=0) q = q->pred;
  return (q==header) ? 0 : q;
 }


 
skiplist_item skiplist::lookup(GenPtr key) const
{ int k;
  skiplist_item q = search(key,k);
  return (k<0) ? 0 : q;
 }


void skiplist::insert_item_at_item(skiplist_item q, skiplist_item p)
{ 
  // insert item q immediately after item p

  skiplist_item x;
  int k;
  q->pred = p;
  p->forward[0]->pred = q;
  for(k=0; k<=q->level; k++)
  { while (k > p->level) p = p->backward;
    x = p->forward[k];
    q->forward[k] = x;
    p->forward[k] = q;
    if (x->level == k) x->backward = q;
   }
   q->backward = p;
 }
 

skiplist_item skiplist::insert_at_item(skiplist_item p, GenPtr key, GenPtr inf)
{ skiplist_item q;
  int k;

  if (p != header)
  { int c = cmp(key,p->key);

    if (c == 0)
    { clear_inf(p->inf);
      copy_inf(inf);
      p->inf = inf;
      return p;
     }

    if (c<0) p = p->pred;

/*
     if (p!=min() && cmp(key,p->pred->key) <= 0)
     {  cout << "wrong position for "; print_key(key);
        newline;
        cout << " pos = "; print_key(p->key);
        newline;
        cout << " pred = "; print_key(p->pred->key);
        newline;
        error_handler(1,"skiplist::insert_at : wrong position "); 
      }
*/
   }
 
   k = randomLevel();
   if (k>level) k = ++level;
 
   NEW_NODE(q,k);
   copy_key(key);
   copy_inf(inf);
   q->key = key;
   q->inf = inf;
   skiplist_node::mutex_id_count.lock();
   q->id = skiplist_node::id_count++;
   skiplist_node::mutex_id_count.unlock();
   count++;

   insert_item_at_item(q,p);
 
   return q;
 }


void skiplist::remove_item(skiplist_item q)
{ int k;
  skiplist_item p = q->backward;
  skiplist_item x = 0;

  for(k=q->level; k>=0; k--)
  { while (p->forward[k] != q) p = p->forward[k];
    x = q->forward[k];
    p->forward[k] = x;
    if (x->level==k) x->backward = p;
   }
  x->pred = p;
}
 
 
void skiplist::del_item(skiplist_item q)
{ remove_item(q);
  clear_key(q->key);
  clear_inf(q->inf);
  FREE_NODE(q);
  while(header->forward[level] == stopper && level > 0 ) level--;
  count --;
}

skiplist_item skiplist::insert(GenPtr key, GenPtr inf)
{ int k;
  skiplist_item p = search(key,k);
  if (p==stopper) p = p->pred;
  return insert_at_item(p,key,inf);
 }

void skiplist::del(GenPtr key)
{ int k;
  skiplist_item q = search(key,k);
  if (k>=0) del_item(q);
 }


void skiplist::reverse_items(skiplist_item p, skiplist_item q)
{ skiplist_item r;
  while (p!=q)
  { r = p;
    p = p->forward[0];
    remove_item(r);
    insert_item_at_item(r,q);
   }
 }

void skiplist::conc(skiplist&)
{ error_handler(1,"sorry, not implemented: skiplist::conc(skiplist)\n"); }

void skiplist::split_at_item(skiplist_item,skiplist&,skiplist&)
{ error_handler(1,"sorry, not implemented: skiplist::split_at_item\n"); }


void skiplist::print()
{ skiplist_item p = header;
  cout << "Level = " << level << "\n"; 
  for(;;)
  { cout << string("<%d>  ",p);
    if (p != header && p != stopper)
    { cout << "key = ";
      print_key(p->key);
     }
    newline;
    for(int k=p->level;k>=0;k--)
       cout << string("forward[%d] = %8d\n", k,p->forward[k]);
    cout << string("backward = %8d   pred = %8d\n",p->backward, p->pred);
    if (p==stopper) break;
    p = p->forward[0];
    newline;
   }
}

