/*******************************************************************************
+
+  LEDA 3.5
+
+  _array.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/gen_array.h>

#ifdef SWAP
#undef SWAP
#endif

#define SWAP(a,b) { GenPtr help = *a; *a = *b; *b = help; }


void gen_array::read(istream& in, string s)
{ clear();
  cout << s;
  int i = 0;
  while (in && i < sz) read_el(v[i++],in);
  while (i < sz) init_entry(v[i++]);
 }

void gen_array::print(ostream& out, string s, char space) const
{ out << s;
  for (int i=0; i<sz; i++)
  { out << string("%c",space);
    print_el(v[i],out); 
   }
  out.flush();
}

void gen_array::clear() 
{ int type_id = el_type_id();
  if (type_id == INT_TYPE_ID || type_id == PTR_TYPE_ID) return;
  GenPtr* p = v + sz;
  while (p > v) clear_entry(*--p);
}

void gen_array::init() 
{ int type_id = el_type_id();
  if (type_id == INT_TYPE_ID || type_id == PTR_TYPE_ID) return;
  GenPtr* p = v + sz;
  while (p > v) init_entry(*--p);
}

void gen_array::init(GenPtr p0, GenPtr p1) 
{ v[0] = p0;
  v[1] = p1;
 }

void gen_array::init(GenPtr p0, GenPtr p1, GenPtr p2) 
{ v[0] = p0;
  v[1] = p1;
  v[2] = p2;
 }

void gen_array::init(GenPtr p0, GenPtr p1, GenPtr p2, GenPtr p3) 
{ v[0] = p0;
  v[1] = p1;
  v[2] = p2;
  v[3] = p3;
 }


gen_array::gen_array()
{ Low = 0;
  High = -1;
  sz = 0;
  v = 0;
  last = 0;
}


gen_array::gen_array(int a, int b)
{ if (a>b) error_handler(1,string("array: bad array bounds [%d..%d]",a,b));
  Low = a;
  High = b;
  sz = b-a+1;
  v = new GenPtr[sz];  
  if (v==0) error_handler(99,"array: out of memory");
  last = v+sz-1;
 }

gen_array::gen_array(int n)
{ Low = 0;
  High = n-1;
  sz = n;
  v = new GenPtr[sz];
  if (v==0) error_handler(99,"array: out of memory");
  last = v+sz-1;
}

gen_array::gen_array(const gen_array& a)
{ sz = a.sz;
  Low = a.Low;
  High = a.High;
  v = new GenPtr[sz];
  if (v==0) error_handler(99,"array: out of memory");
  last = v+sz-1;
  GenPtr* vv = v + sz;
  GenPtr* av = a.v + sz;
  while (vv > v) 
  { *--vv = *--av;
    a.copy_entry(*vv);
   }
}

gen_array& gen_array::operator=(const gen_array& a)
{ if (this == &a) return *this;

  if (sz != a.sz)
  { clear();
    sz = a.sz;       
    delete[] v;
    v = new GenPtr[sz];
    if (v==0) error_handler(99,"array: out of memory");
    last = v+sz-1;
   }

  Low = a.Low;
  High = a.High;
  GenPtr* vv = v + sz;
  GenPtr* av = a.v + sz;
  while (vv > v) 
  { *--vv = *--av;
    copy_entry(*vv);
   }

  return *this;
}

void gen_array::permute(int l, int r)
{
  if (l<Low || l>High || r<l || r>High) 
         error_handler(2,"array::permute illegal range");
 
  l -= Low;
  r -= Low;

  GenPtr* x;
  GenPtr* y;
  GenPtr* stop = v+r+1;

  for(x=v+l;x!=stop;x++) 
  { y = v + rand_int(l,r);  
    SWAP(x,y);  
   }
}

void gen_array::sort(int l, int h, int min_d, int special) 
{
  if (l >= h) return;

  if (min_d < 1) min_d = 1;

  GenPtr* left  = v+l-Low;
  GenPtr* right = v+h-Low;
  GenPtr* min_stop = left + min_d;

  if (min_stop > right) min_stop = right;

  int type_id = (special) ? el_type_id() : UNKNOWN_TYPE_ID;

  switch (type_id) {

    case INT_TYPE_ID:
            int_quick_sort(left,right,min_d);
            if (min_d > 1)
              int_insertion_sort(left,right,min_stop);
            break;

    case FLOAT_TYPE_ID:
            float_quick_sort(left,right,1);
/*
            if (min_d > 1)
              double_insertion_sort(left,right,min_stop);
*/
            break;
  
    case DOUBLE_TYPE_ID:
            double_quick_sort(left,right,min_d);
            if (min_d > 1)
              double_insertion_sort(left,right,min_stop);
            break;
  
    default:
            gen_quick_sort(left,right,min_d);
            if (min_d > 1)
              gen_insertion_sort(left,right,min_stop);
            break;
   }
}
 

#define ARRAY_QS_RAND(d) (d/2)
 

void gen_array::gen_quick_sort(GenPtr* l, GenPtr* r, int min_d)
{ int d = r-l;

  if (d <= 2)
  { if (cmp(*l,*r) > 0) SWAP(l,r);
    if (d == 2) 
    { GenPtr* m = l+1;
      if (cmp(*m,*l) < 0) SWAP(m,l)
      else if (cmp(*m,*r) > 0) SWAP(m,r)
     }
    return;
   }

  GenPtr* j = l+ARRAY_QS_RAND(d);
  if (cmp(*j,*r) > 0) SWAP(j,r);
  SWAP(l,j);
  GenPtr s = *l;
  GenPtr* i = l;
  GenPtr* k = r;
  for(;;)
  { while (cmp(*(++i),s)<0);
    while (cmp(*(--k),s)>0);
    if (i<k) SWAP(i,k) else break;
   }
  SWAP(l,k);
  if (k > l+min_d) gen_quick_sort(l,k-1,min_d);
  if (r > k+min_d) gen_quick_sort(k+1,r,min_d);
}



#define ARRAY_QS_BODY(type,func)                                     \
  int d = r-l;                                                       \
  if (d <= 2)                                                        \
  { if (LEDA_ACCESS(type,*l) > LEDA_ACCESS(type,*r)) SWAP(l,r);      \
    if (d == 1) return;                                              \
    GenPtr* m = l+1;                                                 \
    if (LEDA_ACCESS(type,*m) < LEDA_ACCESS(type,*l)) SWAP(m,l)       \
    else if (LEDA_ACCESS(type,*m) > LEDA_ACCESS(type,*r)) SWAP(m,r)  \
    return;                                                          \
   }                                                                 \
  GenPtr* j = l+ARRAY_QS_RAND(d);                                    \
  if (LEDA_ACCESS(type,*j) > LEDA_ACCESS(type,*r)) SWAP(j,r);        \
  SWAP(l,j);                                                         \
  type s = LEDA_ACCESS(type,*l);                                     \
  GenPtr* i = l;                                                     \
  GenPtr* k = r;                                                     \
  for(;;)                                                            \
  { while (LEDA_ACCESS(type,*(++i)) < s);                            \
    while (LEDA_ACCESS(type,*(--k)) > s);                            \
    if (i<k) SWAP(i,k) else break;                                   \
   }                                                                 \
  SWAP(l,k);                                                         \
  if (k > l+min_d) func(l,k-1,min_d);                                \
  if (r > k+min_d) func(k+1,r,min_d);                                \


void gen_array::int_quick_sort(GenPtr* l, GenPtr* r, int min_d)
{ ARRAY_QS_BODY(int,int_quick_sort) }

void gen_array::float_quick_sort(GenPtr* l, GenPtr* r, int min_d)
{ ARRAY_QS_BODY(float,float_quick_sort) }

void gen_array::double_quick_sort(GenPtr* l, GenPtr* r, int min_d)
{ ARRAY_QS_BODY(double,double_quick_sort) }




void gen_array::gen_insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop)
{
  GenPtr* min=l;
  GenPtr* run;
  GenPtr* p;
  GenPtr* q;

  for (run = l+1; run <= min_stop; run++)
      if (cmp(*run,*min) < 0) min = run;

  SWAP(min,l);

  if (r == l+1) return;

  for(run=l+2; run <= r; run++)
  { for (min = run-1; cmp(*run,*min) < 0; min--);
    min++;
    if (run != min) 
    { GenPtr save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}



void gen_array::int_insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop)
{
  GenPtr* min=l;
  GenPtr* run;
  GenPtr* p;
  GenPtr* q;

  int d_min = LEDA_ACCESS(int,*min);
  for (run = l+1; run <= min_stop; run++)
  { int d_run = LEDA_ACCESS(int,*run);
    if (d_run <  d_min) 
    { min = run;
      d_min = d_run;
     }
   }

  SWAP(min,l);

  if (r == l+1) return;

  for(run=l+2; run <= r; run++)
  { int d_run = LEDA_ACCESS(int,*run);
    min = run-1; 
    while (d_run < LEDA_ACCESS(int,*min)) min--;
    min++;
    if (run != min) 
    { GenPtr save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}


void gen_array::double_insertion_sort(GenPtr* l, GenPtr* r, GenPtr* min_stop)
{
  GenPtr* min=l;
  GenPtr* run;
  GenPtr* p;
  GenPtr* q;

  double d_min = LEDA_ACCESS(double,*min);
  for (run = l+1; run <= min_stop; run++)
  { double d_run = LEDA_ACCESS(double,*run);
    if (d_run <  d_min) 
    { min = run;
      d_min = d_run;
     }
   }

  SWAP(min,l);

  if (r == l+1) return;

  for(run=l+2; run <= r; run++)
  { double d_run = LEDA_ACCESS(double,*run);
    min = run-1; 
    while (d_run < LEDA_ACCESS(double,*min)) min--;
    min++;
    if (run != min) 
    { GenPtr save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}


int gen_array::binary_search(GenPtr x, int special)
{ int type_id = (special) ? el_type_id() : UNKNOWN_TYPE_ID;
  switch (type_id) {
    case INT_TYPE_ID:      return int_binary_search(x);
    case DOUBLE_TYPE_ID:   return double_binary_search(x);
    default:               return gen_binary_search(x);
   }
}



int gen_array::gen_binary_search(GenPtr x)
{ int l = 0;
  int r = sz-1;

  while (l <= r)
  { int m = (l+r)/2;
    int c = cmp(x,v[m]);
    if (c == 0) return m+Low;
    if (c > 0)
       l = m+1;
    else
       r = m-1;
   }

  return  Low-1;
}



int gen_array::int_binary_search(GenPtr x)
{ int l = 0;
  int r = sz-1;

  int x_i = LEDA_ACCESS(int,x);

  while (l <= r)
  { int m = (l+r)/2;
    int m_i = LEDA_ACCESS(int,v[m]);
    if (x_i == m_i) return m+Low;
    if (x_i > m_i)  
       l = m+1;
    else
       r = m-1;
   }

  return  Low-1;
}


int gen_array::double_binary_search(GenPtr x)
{ int l = 0;
  int r = sz-1;

  double x_i = LEDA_ACCESS(double,x);

  while (l <= r)
  { int m = (l+r)/2;
    double m_i = LEDA_ACCESS(double,v[m]);
    if (x_i == m_i) return m+Low;
    if (x_i > m_i)  
       l = m+1;
    else
       r = m-1;
   }

  return  Low-1;
}



void gen_array2::init(int a, int b, int c, int d)
{ int i,j;
  for (i=a;i<=b;i++) 
      for (j=c; j<=d; j++) init_entry(row(i)->entry(j));
}

gen_array2::gen_array2(int a, int b, int c, int d) : A(a,b) 
{ Low1  = a;
  High1 = b;
  Low2  = c;
  High2 = d;
  while (b>=a) A.entry(b--) = (GenPtr) new gen_array(c,d); 
}

gen_array2::gen_array2(int a, int b) : A(a) 
{ Low1  = 0;
  High1 = a-1;
  Low2  = 0;
  High2 = b-1;
  while (a>0) A.entry(--a) = (GenPtr) new gen_array(b); 
}

void gen_array2::clear()
{ int i,j;
  for (i=Low1;i<=High1;i++) 
  for (j=Low2;j<=High2;j++) 
  clear_entry(row(i)->entry(j));
}

gen_array2::~gen_array2()
{ for (int i=Low1;i<=High1;i++) delete (gen_array*)A.entry(i); }



void gen_array2::copy_row(gen_array* from, gen_array* to) const
{ GenPtr* p = to->v + to->sz;
  GenPtr* q = from->v + from->sz;
  while (q > from->v) 
  { *--p = *--q;
    copy_entry(*p);
   }
}


gen_array2::gen_array2(const gen_array2& a) : A(a.Low1,a.High1)
{ 
  Low1 = a.Low1;
  High1 = a.High1;
  Low2 = a.Low2;
  High2 = a.High2;

  for(int i=Low1; i<=High1; i++)
  { gen_array* p =  new gen_array(Low2,High2); 
    if (p==0) error_handler(99,"array2: out of memory");
    a.copy_row((gen_array*)a.A.inf(i),p);
    A.entry(i) = p;
   }
}

gen_array2& gen_array2::operator=(const gen_array2& a)
{ 
  clear();

  Low1 = a.Low1;
  High1 = a.High1;
  Low2 = a.Low2;
  High2 = a.High2;

  for(int i=Low1; i<=High1; i++)
  { gen_array* p =  new gen_array(Low2,High2); 
    if (p==0) error_handler(99,"array2: out of memory");
    a.copy_row((gen_array*)a.A.inf(i),p);
    A.entry(i) = p;
   }

  return *this;
}
