/*******************************************************************************
+
+  LEDA 3.5
+
+  _f_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.
+ 
*******************************************************************************/

#include <LEDA/impl/f_skiplist.h>
#include <assert.h>


const int BitsInRandom      = 31;
const int MaxHeight = 32;

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

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

inline int HEADER_SIZE(int l)
{ int l1 = 1;
  while (l1 < l) l1 <<= 1; 
  return int(sizeof(header_node))+(l1)*int(sizeof(f_skiplist_node*));
}
  
 
#define NEW_HEADER(p,l) p=(large_item)std_memory.allocate_bytes(HEADER_SIZE(l)); p->height=l

#define FREE_HEADER(p)  std_memory.deallocate_bytes(p,HEADER_SIZE(p->height))

f_skiplist::f_skiplist(float p) 
{ prob = p;
  randomBits = rand_int(0,MAXINT-1);
  randomsLeft = BitsInRandom;
#ifdef NOMEM   
  header = new header_node;
  header->forward = new f_skiplist_item[MaxHeight+1];
  header->height = MaxHeight;
  STOP = new f_skiplist_node;
  STOP->height = -1;
#else
  NEW_HEADER(header,MaxHeight);
  NEW_NODE(STOP,-1);
#endif
  header->true_height = 0;
  header->myseq = this;  
  STOP->backward= (f_skiplist_item) header;
  STOP->pred= (f_skiplist_item) header;
  header->forward[0] = STOP;
} 
 
f_skiplist::f_skiplist(const f_skiplist& L) 
{ prob = L.prob;
  randomBits = rand_int(0,MAXINT-1);
  randomsLeft = BitsInRandom;
#ifdef NOMEM   
  header = new header_node;
  header->forward = new f_skiplist_item[MaxHeight+1];
  header->height = MaxHeight;
  STOP = new f_skiplist_node;
  STOP->height = -1;
#else
  NEW_HEADER(header,MaxHeight);
  NEW_NODE(STOP,-1);
#endif
  header->true_height = 0;
  header->myseq = this;
  STOP->backward= (f_skiplist_item) header;
  STOP->pred= (f_skiplist_item) header;

  header->forward[0] = STOP;
 
  f_skiplist_item p = L.STOP->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;
  }
} 

 
f_skiplist& f_skiplist::operator=(const f_skiplist& L) 
{ clear();
  f_skiplist_item p = L.STOP->pred;
  while (p!= L.header) 
  { insert_at_item(header,p->key,p->inf,after);
    p = p->pred;
   }
  return *this;
 } 
 
void f_skiplist::clear() 
{ register f_skiplist_item p,q;
  p = header->forward[0];
  while(p!=STOP)
  { q = p->forward[0];
    clear_key(p->key);
    clear_inf(p->inf);
#ifdef NOMEM
    delete p->forward;
    delete p;
#else
    FREE_NODE(p);
#endif
    p = q; 
   }
 header->true_height = 0;
 header->forward[0] = STOP;
 STOP->pred= (f_skiplist_item) header;
}
 
 
 
f_skiplist::~f_skiplist() 
{ clear();
#ifdef NOMEM
  delete header->forward;
  delete header;
  delete STOP;
#else
  FREE_HEADER(header);
  FREE_NODE(STOP);
#endif
 }


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

f_skiplist_item f_skiplist::gen_search(f_skiplist_item v, 
                           int h, GenPtr key, int& l) const
{ register f_skiplist_item p = v;
  register f_skiplist_item q = p->forward[h];
  l = 0;

#ifdef CHECK_INVARIANTS
  assert(p->height == MaxHeight || cmp(key,p->key) > 0);
  assert(q->height < 0 || cmp(key,q->key) <= 0);
#endif
 
  if (q->height >= 0 && cmp(key,q->key) == 0)  return q;

  int k = h - 1;
  int c = -1;
  
  while (k >=0)
  { /* p->key < key < p->forward[k+1]->key and c = -1 */
    q = p->forward[k];
    while (k == q->height && (c = cmp(key,q->key)) > 0)
    { p = q;
      q = p->forward[k];
    }
    if (c == 0) break;
    k--;
  }
  l = k;
   

#ifdef CHECK_INVARIANTS
  p = q->pred;
  assert(p->height == MaxHeight || cmp(key,p->key) > 0);
  assert(q->height <  0 || cmp(key, q->key) <= 0);
  assert(l >= 0 && cmp(key,q->key) == 0 ||
  ( l < 0 && (q->height < 0 || cmp(key,q->key) < 0)));
#endif

  return q;
}


f_skiplist_item f_skiplist::int_search(f_skiplist_item v, 
                           int h, GenPtr key, int& l) const
{ register f_skiplist_item p = v;
  register f_skiplist_item q = p->forward[h];
  l = 0;
  int ki = LEDA_ACCESS(int,key);

#ifdef CHECK_INVARIANTS
  assert(p->height == MaxHeight || ki > LEDA_ACCESS(int,p->key));
  assert(q->height < 0 || ki <= LEDA_ACCESS(int,q->key));
#endif
  //if (q->height >= 0 && ki == LEDA_ACCESS(int,q->key)) return q;

  int k = h - 1;
  STOP->key = key;
  
  while (k >= 0)
  { /* p->key < key <= p->forward[k+1]->key */
#ifdef CHECK_INVARIANTS
  assert(p->height == MaxHeight || ki > LEDA_ACCESS(int,p->key));
  assert(q->height < 0 || ki < LEDA_ACCESS(int,q->key));
#endif

    q = p->forward[k];
    while ( ki > LEDA_ACCESS(int,q->key) )
    { p = q;
      q = p->forward[k];
    }
    if ( ki == LEDA_ACCESS(int,q->key) && q != STOP ) break;
    k--;
  }
  l = k;
   

#ifdef CHECK_INVARIANTS
  p = q->pred;
  assert(p->height == MaxHeight || ki > LEDA_ACCESS(int,p->key));
  assert(q->height <  0 || ki <= LEDA_ACCESS(int,q->key));
  assert(l >= 0 && ki == LEDA_ACCESS(int,q->key) ||
  ( l < 0 && (q->height < 0 || ki < LEDA_ACCESS(int,q->key))));
#endif

  return q;
}


f_skiplist_item f_skiplist::double_search(f_skiplist_item v, 
                           int h, GenPtr key, int& l) const
{ register f_skiplist_item p = v;
  register f_skiplist_item q = p->forward[h];
  l = 0;
  double ki = LEDA_ACCESS(double,key);

#ifdef CHECK_INVARIANTS
  assert(p->height == MaxHeight || ki > LEDA_ACCESS(double,p->key));
  assert(q->height < 0 || ki <= LEDA_ACCESS(double,q->key));
#endif
 
  //if (q->height >= 0 && ki == LEDA_ACCESS(double,q->key)) return q;

  int k = h - 1;
  STOP->key = key;
  
  while (k >= 0)
  { /* p->key < key <= p->forward[k+1]->key */
#ifdef CHECK_INVARIANTS
  assert(p->height == MaxHeight || ki > LEDA_ACCESS(double,p->key));
  assert(q->height < 0 || ki < LEDA_ACCESS(double,q->key));
#endif

    q = p->forward[k];
    while ( ki > LEDA_ACCESS(double,q->key) )
    { p = q;
      q = p->forward[k];
    }
    if ( ki == LEDA_ACCESS(double,q->key) && q != STOP ) break;
    k--;
  }
  l = k;
   

#ifdef CHECK_INVARIANTS
  p = q->pred;
  assert(p->height == MaxHeight || ki > LEDA_ACCESS(double,p->key));
  assert(q->height <  0 || ki <= LEDA_ACCESS(double,q->key));
  assert(l >= 0 && ki == LEDA_ACCESS(double,q->key) ||
  ( l < 0 && (q->height < 0 || ki < LEDA_ACCESS(double,q->key))));
#endif

  return q;
}







f_skiplist_item f_skiplist::locate_succ(GenPtr key) const
{ int l;
  f_skiplist_item q = search(header,header->true_height,key,l);
  
  return (q == STOP) ? 0 : q;
 }

f_skiplist_item f_skiplist::locate(GenPtr key) const 
{ 
  return locate_succ(key); 
 }


f_skiplist_item f_skiplist::locate_pred(GenPtr key) const
{ int l;
  f_skiplist_item q = search(header,header->true_height,key,l);
  if (l < 0) q = q->pred;
  return (q == header) ? 0 : q;
 }

 

 
f_skiplist_item f_skiplist::lookup(GenPtr key) const
{ int k;
  f_skiplist_item q = search(header,header->true_height,key,k);
  return (k < 0) ? 0 : q;
 }



f_skiplist_item f_skiplist::finger_search(GenPtr key, int& l) const
{ switch (key_type_id()) {
  case INT_TYPE_ID:    return int_finger_search(key,l);
  case DOUBLE_TYPE_ID: return double_finger_search(key,l);
  default:             return gen_finger_search(key,l);
  }

}

f_skiplist_item f_skiplist::gen_finger_search(GenPtr key, int& l) const
{ f_skiplist_item q = STOP->pred; 
  if ( q == header || cmp(key, q->key) > 0) 
  {  l = -1; 
     return STOP; 
  } 

  /* we have header->key  < key <= q->key */

  header->key = key;  STOP->key = key;
  l = 0; 
  int k = 0;
  int c1,c2;

  while (((c1 = cmp(key,header->forward[k]->key)) > 0) &&
         ((c2 = cmp(key, q->key)) <= 0) )
  { /* q is the righmost tower of height at least k; it is 
       proper since k = true_height implies header->forward[k] = STOP 
       and the loop body would not have been entered. */

    k++;

    if (c2 == 0)  return q;

    while (k > q->height)  q = q->backward;

  }

  if (c1 == 0 && STOP != header->forward[k])
  return header->forward[k];

  if (c1 <= 0) 
  {
#ifdef CHECK_INVARIANTS
    f_skiplist_item r = header->forward[k];
    assert(r == STOP || cmp(key, r->key) < 0);
#endif
    return search(header,k,key,l);
  }
#ifdef CHECK_INVARIANTS
  f_skiplist_item r = q->forward[k];
  assert(q == header || cmp(key,q->key) > 0);
  assert(r == STOP   || cmp(key,r->key) < 0 );
#endif
  return search(q,k,key,l);
}






f_skiplist_item f_skiplist::int_finger_search(GenPtr key, int& l) const
{ f_skiplist_item q = STOP->pred; 
  int ki = LEDA_ACCESS(int,key);

  if ( q == header || ki > LEDA_ACCESS(int,q->key))
  {  l = -1; 
     return STOP; 
  } 

  /* we have header->key  < key <= q->key */

  header->key = key;  STOP->key = key;
  l = 0; 
  int k = 0;


  while ( ki > LEDA_ACCESS(int,header->forward[k]->key) &&
          ki <= LEDA_ACCESS(int,q->key) ) 
  { /* q is the righmost tower of height at least k; it is 
       proper since k = true_height implies header->forward[k] = STOP 
       and the loop body would not have been entered. */

    k++;

    if ( ki == LEDA_ACCESS(int,q->key) )  return q;

    while (k > q->height)  q = q->backward;

  }

  if ( ki == LEDA_ACCESS(int,header->forward[k]->key)
                        && STOP != header->forward[k])
  return header->forward[k];

  if (ki <= LEDA_ACCESS(int,header->forward[k]->key)) 
  {
#ifdef CHECK_INVARIANTS
    f_skiplist_item r = header->forward[k];
    assert(r == STOP || ki < LEDA_ACCESS(int,r->key));
#endif
    return search(header,k,key,l);
  }
#ifdef CHECK_INVARIANTS
  f_skiplist_item r = q->forward[k];
  assert(q == header || ki > LEDA_ACCESS(int,q->key));
  assert(r == STOP   || ki < LEDA_ACCESS(int,r->key));
#endif
  return search(q,k,key,l);
}


f_skiplist_item f_skiplist::double_finger_search(GenPtr key, int& l) const
{ f_skiplist_item q = STOP->pred; 
  double ki = LEDA_ACCESS(double,key);

  if ( q == header || ki > LEDA_ACCESS(double,q->key))
  {  l = -1; 
     return STOP; 
  } 

  /* we have header->key  < key <= q->key */

  header->key = key;  STOP->key = key;
  l = 0; 
  int k = 0;

  while ( ki > LEDA_ACCESS(double,header->forward[k]->key) &&
          ki <= LEDA_ACCESS(double,q->key) )
  { /* q is the righmost tower of height at least k; it is 
       proper since k = height implies header->forward[k] = STOP 
       and the loop body would not have been entered. */

    k++;

    if ( ki == LEDA_ACCESS(double,q->key) )  return q;

    while (k > q->height)  q = q->backward;

  }

  if ( ki == LEDA_ACCESS(double,header->forward[k]->key)
                        && STOP != header->forward[k])
  return header->forward[k];

  if (ki <= LEDA_ACCESS(double,header->forward[k]->key)) 
  {
#ifdef CHECK_INVARIANTS
    f_skiplist_item r = header->forward[k];
    assert(r == STOP || ki < LEDA_ACCESS(double,r->key));
#endif
    return search(header,k,key,l);
  }
#ifdef CHECK_INVARIANTS
  f_skiplist_item r = q->forward[k];
  assert(q == header || ki > LEDA_ACCESS(double,q->key));
  assert(r == STOP   || ki < LEDA_ACCESS(double,r->key));
#endif
  return search(q,k,key,l);
}


f_skiplist_item f_skiplist::finger_search(f_skiplist_item v, 
                                  GenPtr key, int& l) const
{ switch (key_type_id()) {
  case INT_TYPE_ID:    return int_finger_search(v,key,l);
  case DOUBLE_TYPE_ID: return double_finger_search(v,key,l);
  default:             return gen_finger_search(v,key,l);
  }
}


f_skiplist_item f_skiplist::gen_finger_search(f_skiplist_item v, GenPtr key, int& l) const
{ l = 0;
f_skiplist_item p = v;

if ( p->height < 0 ) p = p->backward;
if ( p->height == MaxHeight ) 
  return ((large_item) p)->myseq->finger_search(key,l);

int dir = cmp(key, v->key);
if  ( dir == 0 ) return v;

int k = 0;
int c;
        
if (dir > 0)
{ while ( p->height < MaxHeight && 
          p->forward[k]->height  >= 0 && 
          (c = cmp(key,p->forward[k]->key )) >= 0 )
  { if (c == 0) return p->forward[k];
    k++;
    while (k > p->height) p = p->backward;
  }
  if (p->height == MaxHeight) 
     return  ((large_item) p)->myseq->finger_search(key,l);
}
else 
{ while ( p->height  < MaxHeight && 
          p->forward[k]->height >= 0 && 
          (c = cmp(key, p->key)) <= 0 )
  { if (c == 0)  return p;
    k = p->height;
    p = p->backward;
  }
  if (p->forward[k]->height  < 0 ) 
  { p = p->forward[k]->backward;
    return ((large_item) p)->myseq->finger_search(key,l);
  }
}

#ifdef CHECK_INVARIANTS
assert(p->height == MaxHeight || cmp(key, p->key) > 0);
assert(p->forward[k]->height < 0 || cmp(key, p->forward[k]->key) <0);
#endif

return search(p,k,key,l);
}



f_skiplist_item f_skiplist::int_finger_search(f_skiplist_item v, 
GenPtr key, int& l) const
{ l = 0;
f_skiplist_item p = v;
int ki = LEDA_ACCESS(int,key);

if ( p->height < 0 ) p = p->backward;
if ( p->height == MaxHeight ) 
  return ((large_item) p)->myseq->finger_search(key,l);

if  ( ki == LEDA_ACCESS(int,v->key) ) return v;

int k = 0;
        
if ( ki >  LEDA_ACCESS(int,v->key) )
{ while ( p->height < MaxHeight && 
          p->forward[k]->height  >= 0 && 
          ( ki >= LEDA_ACCESS(int,p->forward[k]->key)) )
  { if ( ki == LEDA_ACCESS(int,p->forward[k]->key)) return p->forward[k];
    k++;
    while (k > p->height) p = p->backward;
  }
  if (p->height == MaxHeight) 
     return  ((large_item) p)->myseq->finger_search(key,l);
}
else 
{ while ( p->height  < MaxHeight && 
          p->forward[k]->height >= 0 && 
          ( ki <= LEDA_ACCESS(int,p->key)) )
  { if ( ki == LEDA_ACCESS(int,p->key) )  return p;
    k = p->height;
    p = p->backward;
  }
  if (p->forward[k]->height  < 0 ) 
  { p = p->forward[k]->backward;
    return ((large_item) p)->myseq->finger_search(key,l);
  }
}

#ifdef CHECK_INVARIANTS
assert(p->height == MaxHeight || ki > LEDA_ACCESS(int,p->key));
assert(p->forward[k]->height < 0 || ki < LEDA_ACCESS(int,p->forward[k]->key));
#endif

return search(p,k,key,l);
}


f_skiplist_item f_skiplist::double_finger_search(f_skiplist_item v, 
GenPtr key, int& l) const
{ l = 0;
f_skiplist_item p = v;
double ki = LEDA_ACCESS(double,key);

if ( p->height < 0 ) p = p->backward;
if ( p->height == MaxHeight ) 
  return ((large_item) p)->myseq->finger_search(key,l);

if  ( ki == LEDA_ACCESS(double,v->key) ) return v;

int k = 0;
        
if ( ki >  LEDA_ACCESS(double,v->key) )
{ while ( p->height < MaxHeight && 
          p->forward[k]->height  >= 0 && 
          ( ki >= LEDA_ACCESS(double,p->forward[k]->key)) )
  { if ( ki == LEDA_ACCESS(double,p->forward[k]->key)) return p->forward[k];
    k++;
    while (k > p->height) p = p->backward;
  }
  if (p->height == MaxHeight) 
     return  ((large_item) p)->myseq->finger_search(key,l);
}
else 
{ while ( p->height  < MaxHeight && 
          p->forward[k]->height >= 0 && 
          ( ki <= LEDA_ACCESS(double,p->key)) )
  { if ( ki == LEDA_ACCESS(double,p->key) )  return p;
    k = p->height;
    p = p->backward;
  }
  if (p->forward[k]->height  < 0 ) 
  { p = p->forward[k]->backward;
    return ((large_item) p)->myseq->finger_search(key,l);
  }
}

#ifdef CHECK_INVARIANTS
assert(p->height == MaxHeight || ki > LEDA_ACCESS(double,p->key));
assert(p->forward[k]->height < 0 || ki < LEDA_ACCESS(double,p->forward[k]->key));
#endif

return search(p,k,key,l);
}


        
        


f_skiplist_item f_skiplist::finger_locate_succ(f_skiplist_item v, GenPtr key) const
{ int l;
  f_skiplist_item q = finger_search(v,key,l);
  
  return (q->height < 0) ? 0 : q;
 }

f_skiplist_item f_skiplist::finger_locate_succ(GenPtr key) const
{  int l;
  f_skiplist_item q = finger_search(key,l);
  
  return (q==STOP) ? 0 : q;
 }


f_skiplist_item f_skiplist::finger_locate_pred(f_skiplist_item v, GenPtr key) const
{ int l;
  f_skiplist_item q = finger_search(v,key,l);
  if (l < 0) q = q->pred;
  return (q->height == MaxHeight) ? 0 : q;
 }

 
f_skiplist_item f_skiplist::finger_locate_pred(GenPtr key) const
{  int l;
  f_skiplist_item q = finger_search(key,l);
  if (l < 0) q = q->pred;
  return (q==header) ? 0 : q;
 }

 
f_skiplist_item f_skiplist::finger_lookup(f_skiplist_item v, GenPtr key) const
{  int l;
  f_skiplist_item q = finger_search(v,key,l);
  return (l<0) ? 0 : q;
 }

f_skiplist_item f_skiplist::finger_lookup(GenPtr key) const
{  int l;
  f_skiplist_item q = finger_search(key,l);
  return (l<0) ? 0 : q;
 }


void f_skiplist::insert_item_at_item(f_skiplist_item q, f_skiplist_item p, int dir)
{ int k = q->height;
  if (dir == before) p = p->pred;

  /* insert item |q| immediately after item |p| */

  register f_skiplist_item x;
  q->pred = p;
  p->forward[0]->pred = q;
  for (k = 0; k<=q->height; k++ )
  { while (k > p->height) p = p->backward;
    x = p->forward[k];
    if (p->height == MaxHeight && x->height < 0)
    {/* we have reached header and STOP and need to 
           increase true_height */
     ((large_item) p)->true_height = k + 1;
     p->forward[k+1] = x;
     
    }
    q->forward[k] = x;
    p->forward[k] = q;
    if (x->height == k) x->backward = q;
   }
   q->backward = p;
}





f_skiplist_item f_skiplist::insert_at_item(f_skiplist_item p, GenPtr key, GenPtr inf)
{ register f_skiplist_item q;
  if (p->height < 0) p = p->pred;
  else
  { if (p->height < MaxHeight )
    { 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;
    }
  }
 
  int k = randomLevel();
  if ( k >= MaxHeight ) k = MaxHeight - 1;
 
#ifdef NOMEM
  q = new f_skiplist_node;
  q->forward = new f_skiplist_item[k+1];
  q->height = k;
#else
  NEW_NODE(q,k);
#endif
  copy_key(key);
  copy_inf(inf);
  q->key = key;
  q->inf = inf;

  insert_item_at_item(q,p,after);
 
  return q;
}
 
int f_skiplist::randomLevel()
{ int height = 0;
  int b = 0;

  if ( prob == 0.25 )  
  { while ( b == 0 )
    { b = randomBits&3;    // read next two random bits
      randomBits >>= 2;
      randomsLeft -= 2;
      if ( b == 0 ) height++;   // increase height with prob 0.25
      if (randomsLeft < 2) 
      { randomBits = rand_int(0,MAXINT-1);
        randomsLeft = BitsInRandom;
      }
    }
  }
  else            // user defined prob.
  { double p;
    rand_int >> p;
    while ( p < prob ) 
    { height++;
      rand_int >> p;
    }
  }
  return height;
}


f_skiplist_item f_skiplist::insert_at_item(f_skiplist_item p, GenPtr key, GenPtr inf,
int dir)
{ register f_skiplist_item q;
  register int k = randomLevel();
#ifdef NOMEM
  q = new f_skiplist_node;
  q->forward = new f_skiplist_item[k+1];
  q->height = k;
#else
  NEW_NODE(q,k);
#endif
  copy_key(key);
  copy_inf(inf);
  q->key = key;
  q->inf = inf;

  insert_item_at_item(q,p,dir);
 
  return q;
}
 


void f_skiplist::remove_item(f_skiplist_item q)
{ 
  if (q->height == MaxHeight || q->height < 0)
   error_handler(1,"cannot remove improper item");

  register int k;
  register f_skiplist_item p = q->backward;
  register f_skiplist_item x;

  for(k=q->height; k>=0; k--)
  { while (p->forward[k] != q) p = p->forward[k];
    x = q->forward[k];
    p->forward[k] = x;
    if (x->height==k) x->backward = p;
   }
  x->pred = p;
}
 
 
void f_skiplist::del_item(f_skiplist_item q)
{ 
  if (q->height == MaxHeight || q->height < 0)
   error_handler(1,"cannot delete improper item");
  remove_item(q);
  clear_key(q->key);
  clear_inf(q->inf);
  f_skiplist_item p = q->forward[q->height];
#ifdef NOMEM
  delete q->forward;
  delete q;
#else
  FREE_NODE(q);
#endif
  if (p->height < 0)
   { large_item r = (large_item) p->backward;     
    int& h = r->true_height;
    while( h > 0 && r->forward[h - 1] == p) h--;
   }
}

f_skiplist_item f_skiplist::insert(GenPtr key, GenPtr inf)
{ int k;
  f_skiplist_item p = search(header,header->true_height,key,k);
  if ( k >= 0 )
  { clear_inf(p->inf);
    copy_inf(inf);
    p->inf  = inf;
    return p;
  }
  p = insert_at_item(p,key,inf,before);
  return p;
}

void f_skiplist::del(GenPtr key)
{ int k;
  f_skiplist_item q = search(header,header->true_height,key,k);
  if ( k>=0 ) del_item(q);
}


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


template<class E> inline void swap(E& x, E& y)
{ E z = x;
  x = y;
  y = z;
}

void f_skiplist::conc(f_skiplist& S1, int dir)
{
if (header->true_height < S1.header->true_height)
 {
  swap(header->myseq,S1.header->myseq);
  swap(header,S1.header);
  swap(STOP,S1.STOP);
 
 dir = ((dir == after) ? before : after);
 }

if (S1.STOP->pred == S1.header)  return;


/* S1 is non-empty and since height >= S1.height thi| is
also non-empty */

if (dir == after)
{ f_skiplist_item p = STOP->pred;
  f_skiplist_item q = S1.STOP->pred;
 
  assert(cmp(p->key, S1.header->forward[0]->key) < 0);
   
  STOP->pred = q;
  S1.header->forward[0]->pred = p;

  for (int k = 0; k < S1.header->true_height; k++)
  { /* p and q are the rightmost items of height at 
       least k in this and S1, respectively */
    f_skiplist_item r = S1.header->forward[k];
    p->forward[k] = r; 
    if (r->height == k) r->backward = p;
    q->forward[k] = STOP;
    while (p->height == k) p = p->backward;
    while (q->height == k) q = q->backward;
  }
}
else
{  f_skiplist_item q = S1.STOP->pred;

  assert(cmp(q->key, header->forward[0]->key) < 0);

  S1.header->forward[0]->pred= (f_skiplist_item) header;
  header->forward[0]->pred = q;

  for (int k = 0; k < S1.header->true_height; k++)
  { /* q is the rightmost item of height at least k in S1 */   
    f_skiplist_item r = header->forward[k];
    q->forward[k] = r;
    if (r->height == k) r->backward = q;
    r = S1.header->forward[k];
    header->forward[k] = r; 
    if (r->height == k) r->backward= (f_skiplist_item) header;
    while (q->height == k) q = q->backward;
  }
}

S1.header->true_height = 0;
S1.STOP->pred = (f_skiplist_item) S1.header;
S1.header->forward[0] = S1.STOP;

#ifdef CHECK_INVARIANTS
this->check_data_structure("this in conc");
/* in delete_subsequence we call conc with an argument S1 that 
does not know the type of keys and infs. here it is important 
that the implicite argument of the next instruction is this. */
check_data_structure(S1,"S1 in conc");
#endif

}


void f_skiplist::split_at_item(f_skiplist_item p,f_skiplist& S1 ,f_skiplist& S2,int dir)
{ if (dir == before) p = p->pred;

  f_skiplist_item p1 = p;
  f_skiplist_item p2 = p->forward[0];
  int max_level = -1;

  while ( p1->height < MaxHeight && p2->height >= 0 )
  { /* p1 and p2 are proper towers of height larger than max_level */
    max_level++;
    while (p1->height == max_level)  p1 = p1->backward;
    while (p2->height == max_level)  p2 = p2->forward[max_level];
  }

  /* we have seen proper towers of height max_level on both 
     sides of the split and either p1 or p2 is a sentinel */

  large_item pheader;

  if (p1->height == MaxHeight) 
    pheader = (large_item) p1;
  else 
    pheader = (large_item) p2->backward;
 
  f_skiplist* Pp = pheader->myseq;

  if (Pp != &S1)  S1.clear(); 
  if (Pp != &S2)  S2.clear();

  if (p1->height == MaxHeight)
  { /* we reuse pheader and pSTOP for S2 */

    if (Pp != &S2)
    { swap(Pp->header->myseq, S2.header->myseq);
      swap(Pp->header,S2.header);
      swap(Pp->STOP,S2.STOP);
 
    }
    S1.header->true_height = 1+max_level; 

    p1 = p;

    for (int k =0; k <= max_level; k++)
    { /* p1 is the rightmost item in S1 of height at least k */
 
      f_skiplist_item q = S2.header->forward[k];
      S1.header->forward[k] = q;
      if (q->height == k) q->backward = (f_skiplist_item) S1.header;
      S2.header->forward[k] = p1->forward[k];
      if (p1->forward[k]->height == k) p1->forward[k]->backward = 
                     (f_skiplist_item) S2.header;
      p1->forward[k] = S1.STOP;
      while (k == p1->height) p1 = p1->backward;
    }

    S1.header->forward[max_level + 1] = S1.STOP;
    /* the next line sets the predecessor of S1.STOP correctly if S1 is
       non-empty; if it is empty the last line corrects the mistake */
    S1.STOP->pred = p;
    S2.header->forward[0]->pred = (f_skiplist_item) S2.header;
    S1.header->forward[0]->pred = (f_skiplist_item) S1.header;
  }
  else
  { /* we want to reuse pheader and pSTOP for S1 */
    if (Pp != &S1)
    { swap(Pp->header->myseq,S1.header->myseq);
      swap(Pp->header,S1.header);
      swap(Pp->STOP,S1.STOP);
    }
    S2.header->true_height = 1 + max_level;

    p1 = p;
    p2 = S1.STOP->pred;

    for (int k =0; k <= max_level; k++)
    { /* p1 and p2 are the rightmost items in S1 and S2 
         of height at least k, respectively */ 

      f_skiplist_item q = p1->forward[k];
      S2.header->forward[k] = q;
      if (q->height == k) q->backward = (f_skiplist_item) S2.header;
      p1->forward[k] = S1.STOP;
      p2->forward[k] = S2.STOP;
      while (k == p1->height) p1 = p1->backward;
      while (k == p2->height) p2 = p2->backward;
    }

    S2.header->forward[max_level + 1] = S2.STOP;
    /* the next line sets the predecessor of S2.STOP correctly if S2 
       is non-empty; if it is empty then the next 
       line corrects the mistake */
    S2.STOP->pred = S1.STOP->pred;
    S2.header->forward[0]->pred = (f_skiplist_item) S2.header;

    S1.STOP->pred = p;
    S1.header->forward[0]->pred = (f_skiplist_item) S1.header;
  }

  if (Pp != &S1 && Pp != &S2)
  { /* P is empty if distinct from S1 and S2 */
    Pp->header->forward[0] = Pp->STOP;
    Pp->STOP->pred = Pp->STOP->backward= (f_skiplist_item) Pp->header;
    Pp->header->true_height = 0;
  }


#ifdef CHECK_INVARIANTS
this->check_data_structure("this in split");
Pp->check_data_structure("P in split");
check_data_structure(S1,"S1 in split");
check_data_structure(S2,"S2 in split");
#endif
}


void f_skiplist::merge(f_skiplist& S1)
{ f_skiplist_item p= (f_skiplist_item) header;
  f_skiplist_item q = S1.header;
  while (p->height  >= 0 && q->height >= 0)
  { p = p->forward[0];
    q = q->forward[0];
  }

  if (q->height >= 0)  
  { /* swap if this is shorter than S1 */
    swap(header->myseq,S1.header->myseq);
    swap(header,S1.header);
    swap(STOP,S1.STOP);
  }

  /* now S1 is at most as long as this */
  f_skiplist_item finger= (f_skiplist_item) header;
  p = S1.header->forward[0];

  while (p->height >= 0)
  { f_skiplist_item q = p->forward[0];
    int l;
    finger = finger_search(finger,p->key,l);
    if (l >= 0) error_handler(1,"equal keys in merge");
    insert_item_at_item(p,finger,before);
    finger = p; // put finger at newly inserted item
    p = q;
  }


  S1.header->true_height = 0;
  S1.STOP->pred = (f_skiplist_item) S1.header;
  S1.header->forward[0] = S1.STOP;
#ifdef CHECK_INVARIANTS
  check_data_structure("this in merge");
  S1.check_data_structure("S1 in merge");
#endif
}


void f_skiplist::delete_subsequence(f_skiplist_item a,f_skiplist_item b,f_skiplist& S1)
{ S1.clear();
  f_skiplist_item p1 = a->pred;
  f_skiplist_item p2 = b;
  f_skiplist_item p3 = b->forward[0];
  int k = -1;

  while ( p1->height < MaxHeight && p3->height >= 0 && 
          p2->height < MaxHeight && cmp(p2->key,a->key) >= 0 )
  { k++;
    while (p1->height == k)  p1 = p1->backward;

    while ( p2->height == k)  p2 = p2->backward;

    while ( p3->height == k)  p3 = p3->forward[k];
  }

  if (p1->height == MaxHeight || p3->height  < 0)
  { if (p1->height < MaxHeight) p1 = p3->backward;
    f_skiplist* Pp = ((large_item) p1)->myseq;
    f_skiplist S2,S3;
 
    split_at_item(b,S2,S3,after);

    /* The next line is subtle. Note that a is an element of S2
       and that we split S2 into Pp and S1. So why do we use 
       this as the implicite argument for the split instead of S2.     
       The reason is that S2 is an ordinary skip list and has no 
       knowledge of the key and the inf type. In particular S2's
       virtual functions (e.g. cmp) are as defined in f_skiplist.h. 
       Thus S2 cannot properly compare two keys. It does not need 
       to in split_at_item. However, during program testing 
       split_at_item may want to call check_data_structure and 
       this procedure needs to compare keys. So it is essential 
       that we use this as the implicite argument. */

    split_at_item(a,*Pp,S1,before);  

    Pp->conc(S3,after);

    return;
  }

  /* the middle list is the lowest and we have to do some work */

  p1 = a->pred;
  p2 = b;

  /* correct predecessor pointers */

  a->pred = (f_skiplist_item) S1.header;
  S1.STOP->pred = b;
  b->forward[0]->pred = p1;

  /* height of S1 */

  S1.header->true_height = 1 + k;
  S1.header->forward[1+k] = S1.STOP;

  for (int i = 0; i <= k; i++)
  { /* p1 and p2 are the rightmost items of height at least 
       i in the first and the second part of the list respectively */

    f_skiplist_item q = p1->forward[i];
    S1.header->forward[i] = q;
    if (q->height == i) q->backward = S1.header;
    q = p2->forward[i];
    p1->forward[i] = q;
    if (q->height == i) q->backward = p1;
    p2->forward[i] = S1.STOP;

    while (i == p1->height)  p1 = p1->backward;
    while (i == p2->height)  p2 = p2->backward;
  }
}



void f_skiplist::validate_data_structure()
{
assert(header == header->myseq->header); 

int max_proper_height = -1;
f_skiplist_item p = (f_skiplist_item) header;
while (p != STOP)
{ f_skiplist_item q = p->forward[0];
  assert(p == q->pred);
  if (p != header && p->height > max_proper_height) 
                             max_proper_height = p->height;
  if (p != header && q != STOP)
                            assert(cmp(p->key,q->key) < 0);
  
  for (int i = 0; i <= Min(p->height,header->true_height); i++)
  { f_skiplist_item r = p->forward[0];
    while (r->height < i && r != STOP) r = r->forward[0];
    assert ( r == p->forward[i]);
                               
    if ( i == r->height ) assert(r->backward == p);

  }
  p = q;
}
assert(header->true_height == max_proper_height + 1);
                   
assert(STOP->backward == (f_skiplist_item) header);
}



int f_skiplist::size()
{ int count = 0;
  f_skiplist_item p;
  p= (f_skiplist_item) header;
  while ((p = p->forward[0]) != STOP)  count++;
  return count;
}

f_skiplist_item f_skiplist::pred(f_skiplist_item p) const 
{ f_skiplist_item q =  p->pred; 
  return (q->height == MaxHeight) ? 0 : q;
}


void f_skiplist::check_data_structure(const f_skiplist& S1,string s)
{ string t = "";

  if (S1.header != S1.header->myseq->header) 
    {t =t + "error in myseq";}

  int h = -1;
  f_skiplist_item p= (f_skiplist_item) S1.header;
  while (p != S1.STOP)
  { f_skiplist_item q = p->forward[0];
    if (p != q->pred)  t =t + "error in underlying list";
          
    if (p != S1.header && p->height > h) h = p->height;
    if (p != S1.header && q != S1.STOP && cmp(p->key,q->key)>=0)
            { t = t + "error in order";
      print(S1,cout,"I detected an error in the order. Here is the list",' '); 
      newline;
                 }
    if (p != S1.STOP)
    { for (int i = 0; i <= Min(p->height,S1.header->true_height); i++)
      { f_skiplist_item r = p->forward[0];
        while (r->height < i && r != S1.STOP) r = r->forward[0];
        if ( r != p->forward[i])  t =t + "error in forward";
        if ( i == r->height && r->backward != p)
                    t = t + "error in backward";
      }
    }
    p = q;
  }
  if (S1.header->true_height < h +1)  t = t + "height too small";
                   
  if (S1.header->true_height > h +1)  t =t+  "height too large";
                    
  if (S1.STOP->backward != (f_skiplist_item) S1.header)  t =t + "error in stop";
                      
  string t1 = "";
  if (t != t1) { cout << s << "   " << t; newline; cout.flush();}
}




void f_skiplist::print(const f_skiplist & S1,ostream& out,string s, char space) const
{ 
  f_skiplist_item p= ((f_skiplist_item) S1.header)->forward[0];
  out << s << "\n";
  while (p != S1.STOP)
  {  print_key(p->key);
     out << string(space);
     p = p->forward[0];
  }
  out.flush();
}

