/*******************************************************************************
+
+  LEDA 3.5
+
+  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_ARRAY_H
#define LEDA_ARRAY_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350010
#include <LEDA/REDEFINE_NAMES.h>
#endif

//------------------------------------------------------------------------------
// array
//------------------------------------------------------------------------------

#include <LEDA/impl/gen_array.h>


/*{\Manpage {array} {E} {One Dimensional Arrays} }*/


template<class E> 

class array : public gen_array {

/*{\Mdefinition
    An instance $A$ of the parameterized data type |\Mname| is a mapping from 
    an interval $I =[a..b]$ of integers, the index set of $A$, to the set of 
    variables of data type $E$, the element type of $A$. $A(i)$ is called the 
    element at position $i$. }*/


#if !defined(LEDA_COMPARE_TEMPLATE)
decl_compare_func<E> cmp_func;
#endif

int (*cmp_ptr)(const E&, const E&);   // user supplied cmp function

// define virtual functions for element type E

int cmp(GenPtr x, GenPtr y) const 
{ return (*cmp_ptr)(LEDA_ACCESS(E,x),LEDA_ACCESS(E,y)); }


int el_type_id() const { return LEDA_TYPE_ID(E); }

void print_el(GenPtr& x,ostream& out) const { LEDA_PRINT(E,x,out);}
void read_el(GenPtr& x,istream& in)   const { LEDA_READ(E,x,in); }
void clear_entry(GenPtr& x)           const { LEDA_CLEAR(E,x); }
void copy_entry(GenPtr& x)            const { LEDA_COPY(E,x); }
void init_entry(GenPtr& x)            const { LEDA_CREATE(E,x); }


public:

typedef E value_type;

/*{\Mcreation A}*/

array(int a, int b) : gen_array(a,b) { init(); }
/*{\Mcreate  creates an instance |\Mvar| of type |\Mname| with index set $[a..b]$. }*/


array(int n) : gen_array(n)   { init(); }
/*{\Mcreate  creates an instance |\Mvar| of type |\Mname| with index set $[0..n-1]$. }*/ 

array()  {}
/*{\Mcreate  creates an instance |\Mvar| of type |\Mname| with empty index set.}*/


/*{\Mtext
{\bf Special Constructors} }*/

array(int low, const E& x, const E& y) : gen_array(low,low+1) 
{ init(leda_copy(x),leda_copy(y)); }
/*{\Mcreate  creates an instance |\Mvar| of type |\Mname| with index set 
            $[low, low+1]$ initialized to $[x,y]$. }*/ 

array(int low, const E& x, const E& y, const E& w) : gen_array(low,low+2) 
{ init(leda_copy(x),leda_copy(y),leda_copy(w)); }
/*{\Mcreate  creates an instance |\Mvar| of type |\Mname| with index set 
            $[low, low+2]$ initialized to $[x,y,w]$. }*/ 

array(int low, const E& x, const E& y, const E& z, const E& w) 
: gen_array(low,low+3) 
{ init(leda_copy(x),leda_copy(y),leda_copy(z),leda_copy(w)); }
/*{\Mcreate  creates an instance |\Mvar| of type |\Mname| with index set 
            $[low, low+3]$ initialized to $[x,y,z,w]$. }*/ 


// copy constructor, destructor, operator=

 array(const array<E>& A) : gen_array(A) {}

~array()  { clear(); }

 array<E>& operator=(const array<E>& A) 
 { gen_array::operator=(A); return *this; }




/*{\Moperations 1.2 5 }*/

/*{\Moptions nextwarning=no}*/
#if defined(LEDA_CHECKING_OFF)
const E& operator[](int x) const { return LEDA_CONST_ACCESS(E,v[x-Low]); }
E&       operator[](int x)       { return LEDA_ACCESS(E,v[x-Low]); }
#else
const E& operator[](int x) const { return LEDA_CONST_ACCESS(E,entry(x)); }
E&       operator[](int x)       { return LEDA_ACCESS(E,entry(x)); }
#endif
/*{\Marrop     returns $A(x)$.\\
               \precond $a\le x\le b$.  }*/


int low()  const { return gen_array::low();}
/*{\Mop        returns the minimal index $a$ of |\Mvar|. }*/


int high() const { return gen_array::high();}
/*{\Mop        returns the maximal index $b$ of |\Mvar|. }*/

int size() const { return gen_array::size();}
/*{\Mop        returns the size ($b-a+1$) of |\Mvar|. }*/

bool C_style() const { return gen_array::low()==0;}
/*{\Mop        returns |true| if the array has ``C-style'', i.e.,
               the index set is $[0..size-1]$. }*/



/*{\Moptions nextwarning=no}*/
void sort(int (*cmp)(const E&, const E&), int d) 
{ cmp_ptr = cmp; gen_array::sort(low(),high(),d,0); }

void sort(int (*cmp)(const E&, const E&)) 
{ cmp_ptr = cmp; gen_array::sort(low(),high(),1,0); }
/*{\Mopl       sorts the elements of |\Mvar|, using function $cmp$
	      to compare two elements, i.e., if $(in_a,\dots,in_b)$
	      and $(out_a,\dots,out_b)$ denote the values of the
	      variables $(A(a),\dots,A(b))$ before and after the
	      call of sort, then $cmp(out_i,out_j) \le 0$ for $i\le j$
	      and there is a permutation $\pi$ of $[a..b]$ such that
	      $out_i=in_{\pi(i)}$ for $a \le i \le b$.}*/


/*{\Moptions nextwarning=no}*/
void sort(int d)
{ cmp_ptr = compare; gen_array::sort(low(),high(),d,1); }

void sort()
{ cmp_ptr = compare; gen_array::sort(low(),high(),1,1); }
/*{\Mop       sorts the elements of |\Mvar| according to the linear order
              of the element type $E$.\\
	      \precond A linear order on $E$
              must have been defined by $compare(const E\&, const E\&)$. }*/



void sort(int (*cmp)(const E&, const E&), int l, int h)
{ cmp_ptr = cmp; gen_array::sort(l,h,1,0); }
/*{\Mopl       sorts sub-array \Mvar$[l..h]$ using compare function $cmp$.}*/



void sort(int l, int h)
{ cmp_ptr = compare; gen_array::sort(l,h,1,1); }
/*{\Mop        sorts sub-array \Mvar$[l..h]$ using the linear order on $E$.}*/



void permute() { gen_array::permute(); }
/*{\Mop        the elemens of |\Mvar| are randomly permuted.}*/



void permute(int l, int h) { gen_array::permute(l,h); }
/*{\Mop        the elements of \Mvar$[l..h]$ are randomly permuted.}*/



int binary_search(int (*cmp)(const E&,const E&), const E& x)
{ cmp_ptr = cmp; return gen_array::binary_search(leda_cast(x),0);}
/*{\Mopl      performs a binary search for $x$. Returns $i$
	      with $A[i] = x$ if $x$ in $A$, $A$.low$()-1$
	      otherwise. Function $cmp$ is used to compare
	      two elements.\\
	      \precond $A$ must be sorted
	      according to $cmp$.}*/



int binary_search(const E& x)
{ cmp_ptr = compare; 
  return gen_array::binary_search(leda_cast(x),1);
}
/*{\Mop       performs a binary search for $x$ using the default
              linear order on $E$.\\
	      \precond $A$ must be sorted.}*/


void read(istream& I) {gen_array::read(I);}

/*{\Mop       reads $b-a+1$ objects of type $E$ from the
	      input stream $I$ into the array $A$ using the
	      |operator>>(istream&,E&)|.}*/


void read() {gen_array::read();}
/*{\Mop       calls $A$.read($cin$) to read $A$ from the
	      standard input stream $cin$.}*/



void read(string s) {gen_array::read(s);}
/*{\Mop        As above, uses string $s$ as prompt.}*/



void print(ostream& O, char space = ' ') const { gen_array::print(O,space);}
/*{\Mopl      prints the contents of array $A$ to the output
	      stream $O$ using |operator<<(ostream&,const E&)|
	      to print each element. The elements are separated by 
              character $space$.}*/


void print(char space = ' ') const {gen_array::print(space);}
/*{\Mop       calls $A$.print($cout$, $space$) to print $A$ on 
	      the standard output stream $cout$.}*/



void print(string s, char space = ' ') const {gen_array::print(s,space);}
/*{\Mopl        As above, uses string $s$ as header.}*/


// Iteration

GenPtr forall_loop_test(GenPtr it, E& x) const
{ if (it) x = LEDA_ACCESS(E,*(GenPtr*)it); 
  return it;
 }


friend ostream& operator<<(ostream& out, const array<E>& A) 
{ A.print(out); return out;}

friend istream& operator>>(istream& in,  array<E>& A)
{ A.read(in); return in;}



#if defined(__GNUC__) || (!defined(hpux) && !defined(__DECCXX) && !defined(__xlC__))

#define LEDA_STL_ARRAY

E&       operator[](GenPtr it)       { return LEDA_ACCESS(E,*(GenPtr*)it); } 
const E& operator[](GenPtr it) const { return LEDA_ACCESS(E,*(GenPtr*)it); }

STL_ITERATORS(array<E>,GenPtr,E)

#endif


};


/*{\Mimplementation
Arrays are implemented by \CC vectors. The access operation takes time
$O(1)$, the sorting is realized by quicksort (time $O(n \log n)$) and
the binary\_search operation takes time $O(\log n)$, where $n = b-a+1$.
The space requirement is $O(|I|* sizeof(E))$.}*/


#if LEDA_ROOT_INCL_ID == 350010
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif
#endif
