/*
************************************************************************
*
*   element.C -
*
*   Copyright (c) 1995
*
*   ETH Zuerich
*   Institut fuer Molekularbiologie und Biophysik
*   ETH-Hoenggerberg
*   CH-8093 Zuerich
*
*   All Rights Reserved
*
*   Date of last modification : 95/09/15
*   Pathname of SCCS file     : /export/home3/cb/garant-1.0/src/SCCS/s.element.C
*   SCCS identification       : 1.2
*
************************************************************************
*/
/**************************************************************************/
/*                            element.cc                                  */
/*                                                                        */
/* general class to define elements of a ordered list                     */
/**************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "log.h"			/* general log file               */
#include "global.h"			/* global constants               */
#include "element.h"

Element::Element() {t=NONE; }

void Element::print(int off)
{
   Log log;
   char str[MAXLINE];

   sprintf(str,"%*sgeneral Element\n",off,"");
   log.w(str);
}

Index::Index(int m)
{
   max = m;
   l = new Element*[max];
   n = 0;
   cur = 0;
}

Index::~Index()
{
   delete l;
}

Element *Index::start()
{
   cur = 0;
   return(next());
}

void Index::init(Iterator &i)
{
   i.cur = 0;
}

Element *Index::start(Iterator &i)
{
   i.cur = 0;
   return(next(i));
}

Element *Index::startPars(Iterator &i, char *t)
{
   i.cur = 0;
   return(nextPars(i,t));
}

Element *Index::getCyc(Iterator &i,int offset)
{
   int getel;

   getel=i.cur-1+offset;
   while(getel < 0) getel += n;
   while(getel >=n) getel -= n;
   return l[getel];
}


//Element *Index::next()
//
//   if(cur<n) {cur++; return(l[cur-1]); }
//   else return(0);
//

//Element *Index::next(Iterator &i)
//{
//   if(i.cur<n) {i.cur++; return(l[i.cur-1]); }
//   else return(0);
//}

//Element *Index::nextCyc(Iterator &i)
//{
//   if(i.cur>=n) i.cur -= n;
//   i.cur++;
//  return(l[i.cur-1]);
//}

//Element *Index::prevCyc(Iterator &i)
//
//   i.cur--;
//   if(i.cur < 0) i.cur = n-1;
//   if(i.cur == 0) return l[n-1];
//   else return l[i.cur-1];
//}

//Element *Index::get(Iterator i)
//{
//   if(i.cur-1 > 0 && i.cur-1 < n) return l[i.cur-1];
//   else return 0;
//}

Element *Index::nextPars(Iterator &i, char *t)
{
   while(i.cur<n && !l[i.cur]->match(t)) i.cur++;

   i.cur++;
   if(i.cur<=n) { return l[i.cur-1]; }
   else return 0;
}

int Index::insert(Element *e)
{
   int res;
   Element **newl;

   if(find(*e)!=0) res=0;
   else {
      if(n==max) {
         newl = new Element *[2*max];
         for(int j=0;j<max;j++) newl[j]=l[j];
         delete l;
         l=newl;
         max *= 2;
      }
      for(int j=n;j>cur;j--) l[j] = l[j-1];
      l[cur] = e;
      n++;
      res = 1;
   }
   return(res);
}

int Index::add(Element *e)
{
   int res;
   Element **newl;

   if(n==max) {
      newl = new Element *[2*max];
      for(int j=0;j<max;j++) newl[j]=l[j];
      delete l;
      l=newl;
      max *= 2;
   }
   l[n] = e;
   n++;
   res = 1;
   return res;
}

void Index::remove()
{
   n=0; cur=0;
}

void Index::del()
{
   int i;
   for(i=0;i<n;i++) delete l[i];
   n=0; cur=0;
}

int Index::compare(const Element *e1, const Element *e2)
{
   return(e2->t - e1->t);
}

Element *Index::find(const Element &e)	// cur = gefundenes element oder 
{					// eins groesser als das gefundene
   int i,j,res;				// element

   if(n==0) return(0);

   i=0;
   j=n-1;
   cur=0;
   res=1;
   while(i<=j && res !=0) {
      cur = (i+j)/2;
      res=compare(&e,l[cur]);
      if(res < 0) i=cur+1;
      else j=cur-1;
   }
   if(res==0) return(l[cur]);
   else if(res<0) {cur++; return(0); }
   else return(0);
}

void Index::list(int off, char *t)
{
   Element *E;
   Iterator i;

   E = startPars(i,t);
   while(E != 0) {
      E->print(off+3);
      E = nextPars(i,t);
   }
}

void Index::print(int off)
{
   Element *E;

   E = start();
   while(E != 0) {
      E->print(off+3);
      E = next();
   }
}

void Index::sort(int dir)
{
   if(n > 0) {
      if(dir == 1)
         quicksort(0,n-1);
      else
         revquicksort(0,n-1);
   }
}

void Index::quicksort(int von, int bis)
{
   int i,j;
   Element *x;
   Element *w;

   i=von; j=bis;
   x=l[(i+j)/2];
   do {
      while(compare(l[i],x)<0) {i++; }
      while(compare(l[j],x)>0) {j--; }
      if(i<=j) {
         w=l[i]; l[i]=l[j]; l[j]=w;
         i++; j--;
      }
   } while(i<=j);

   if(von < j) {quicksort(von,j); }
   if(i < bis) {quicksort(i,bis); }
}

void Index::revquicksort(int von, int bis)
{
   int i,j;
   Element *x;
   Element *w;

   i=von; j=bis;
   x=l[(i+j)/2];
   do {
      while(compare(l[i],x)>0) {i++; }
      while(compare(l[j],x)<0) {j--; }
      if(i<=j) {
         w=l[i]; l[i]=l[j]; l[j]=w;
         i++; j--;
      }
   } while(i<=j);

   if(von < j) {revquicksort(von,j); }
   if(i < bis) {revquicksort(i,bis); }
}

Element *Index::select(float ratio)
{
   float randomnr;
   int index;

   if(getn() == 0) return 0;

   sort();

   randomnr = drand48();
   if(randomnr > 0.0)
      index = (int)floor(exp(log(randomnr) * ratio) * getn());
   else 
      index = 0;

   return l[index];
}

Cycle::Cycle(int m)
{
   max = m;
   l = new Element*[max];
   v=0; b=0;
}

Cycle::~Cycle()
{
   delete l;
}

void Cycle::reset()
{
   v=0;b=0;
}

void Cycle::add(Element *e)
{
   Element **newlist;
   int i;

   if(b-v == max) {
      newlist = new Element*[max*2];
      for(i=v;i<b;i++) {
         if(i<max) newlist[i-v] = l[i];
         else      newlist[i-v] = l[i-max];
      }
      delete l;
      l = newlist;
      v = 0;
      b = max;
      max *= 2;
   }
   if(b<max) l[b] = e;
   else l[b-max] = e;
   b++;
}

void Cycle::addfront(Element *e)
{
   Element **newlist;
   int i;

   if(b-v == max) {
      newlist = new Element*[max*2];
      for(i=v;i<b;i++) {
         if(i<max) newlist[i-v] = l[i];
         else      newlist[i-v] = l[i-max];
      }
      delete l;
      l = newlist;
      v = 0;
      b = max;
      max *= 2;
   }
   v--;
   if(v<0) {v+=max; b+=max; }
   if(v<max) l[v] = e;
   else l[v-max] = e;
}

void Cycle::addrandom(Element *e)
{
   int randpos;
   int newpos;

   add(e);
   randpos = (int)(rand() % (b-v) + v);
   if(randpos>=max) randpos -= max;
   newpos = b - 1;
   if(newpos>=max) newpos -= max;

   l[newpos] = l[randpos];
   l[randpos] = e;
}

void Cycle::addrandom(Element *e,int pos)
{
   int randpos;
   int newpos;

   add(e);
   if(pos>1) {
      if(pos>b-v) pos=b-v;
      randpos = (int)(b - rand() % pos - 1);
      if(randpos>=max) randpos -= max;
      newpos = b - 1;
      if(newpos>=max) newpos -= max;

      l[newpos] = l[randpos];
      l[randpos] = e;
   }
}

void Cycle::addrandomfront(Element *e,int pos)
{
   int randpos;
   int newpos;

   addfront(e);
   if(pos>1) {
      randpos = (int)(v + rand() % pos);
      if(randpos>=max) randpos -= max;
      newpos = v;
      if(newpos>=max) newpos -= max;

      l[newpos] = l[randpos];
      l[randpos] = e;
   }
}

Element *Cycle::get()
{
   Element *e;
   if(v==b) e = 0;
   else {
      if(v<max) e=l[v];
      else e=l[v-max];

      v++;
      if(v==max) {
         v -= max;
         b -= max;
      }
   }

   return e;
}

Element *Cycle::getrandom()
{
   Element *e;
   e = get();
   while(drand48() > 0.2) {
      add(e);
      e=get();
   }
   return e;
}