/*******************************************************************************
+
+  LEDA 3.5
+
+  gen_array.h
+
+  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.
+ 
*******************************************************************************/
#ifndef LEDA_GEN_ARRAY_H
#define LEDA_GEN_ARRAY_H

//------------------------------------------------------------------------------
// arrays
//------------------------------------------------------------------------------

#include <LEDA/basic.h>


class gen_array {

friend class gen_array2;

protected:
	GenPtr* v;
	GenPtr* last;
	int sz;	
        int Low;
        int High;

virtual int  el_type_id() const { return UNKNOWN_TYPE_ID; }

virtual int  cmp(GenPtr, GenPtr)  const { return 0; }
virtual void print_el(GenPtr&,ostream&) const {}
virtual void read_el(GenPtr& ,istream&) const {}
virtual void clear_entry(GenPtr&) const {}
virtual void copy_entry(GenPtr&)  const {}
virtual void init_entry(GenPtr&)  const {}

  void gen_quick_sort(GenPtr*,GenPtr*,int);
  void int_quick_sort(GenPtr*,GenPtr*,int);
  void float_quick_sort(GenPtr*,GenPtr*,int);
  void double_quick_sort(GenPtr*,GenPtr*,int);

  void gen_insertion_sort(GenPtr*,GenPtr*,GenPtr*);
  void int_insertion_sort(GenPtr*,GenPtr*,GenPtr*);
  void double_insertion_sort(GenPtr*,GenPtr*,GenPtr*);

  int  gen_binary_search(GenPtr);
  int  int_binary_search(GenPtr);
  int  double_binary_search(GenPtr);

protected:

  void sort(int l ,int h, int d,int spec); 
  int  binary_search(GenPtr,int spec);

  void init();
  void init(GenPtr,GenPtr);
  void init(GenPtr,GenPtr,GenPtr);
  void init(GenPtr,GenPtr,GenPtr,GenPtr);

  void clear();

public:
         gen_array();
         gen_array(int);
         gen_array(int, int);
         gen_array(const gen_array&);
virtual ~gen_array() { if (v) delete[] v; }

   gen_array& operator=(const gen_array&);

   int     size() const     { return sz; }
   int     low()  const     { return Low; }
   int     high() const     { return High; }

   GenPtr& elem(int i)       { return v[i]; }
   GenPtr  elem(int i) const { return v[i]; }

   GenPtr& entry(int i) const
   { if (i<Low || i>High)
     error_handler(2,"array::entry index out of range");
     return v[i-Low];
    }

   GenPtr  inf(int i) const
   { if (i<Low || i>High)
     error_handler(2,"array::inf index out of range");
     return v[i-Low];
    }

   void permute(int,int);
   void permute()  { permute(Low,High); }

   void print(ostream&,string, char space) const;    
   void print(ostream& out,char space=' ') const { print(out,"",space);  }
   void print(string s, char space=' ')    const { print(cout,s,space);  }
   void print(char space=' ')              const { print(cout,"",space); }   

   void read(istream&,string);  
   void read(istream& in)      { read(in,"");  }
   void read(string s )        { read(cin,s);  }   
   void read()                 { read(cin,""); }   

// Iteration

   GenPtr first_item() const { return v; }
   GenPtr last_item()  const { return last; }
   GenPtr next_item(GenPtr it) const { return (GenPtr*)it+1;   }
   GenPtr pred_item(GenPtr it) const { return (GenPtr*)it-1;   }

   void loop_to_succ(GenPtr& p) { p = (p == last) ? 0 : (GenPtr*)p + 1;}
   void loop_to_pred(GenPtr& p) { p = (p == v)    ? 0 : (GenPtr*)p - 1;}

};


/*------------------------------------------------------------------------*/
/* 2 dimensional arrays                                                   */
/*------------------------------------------------------------------------*/


class gen_array2 {
gen_array A;
int Low1, Low2, High1, High2;
virtual void clear_entry(GenPtr& x) const { x = 0; }
virtual void copy_entry(GenPtr& x)  const { x = 0; }
virtual void init_entry(GenPtr& x)  const { x = 0; }

protected:
void clear();
gen_array* row(int i) const { return (gen_array*)A.inf(i); }

void copy_row(gen_array*, gen_array*) const;

public:
void init(int,int,int,int);
int low1()  const { return Low1; }
int low2()  const { return Low2; }
int high1() const { return High1; }
int high2() const { return High2; }
gen_array2(int,int,int,int);
gen_array2(int,int);
virtual ~gen_array2();

gen_array2(const gen_array2& a);

gen_array2& operator=(const gen_array2& a);

};

#endif
