// This may look like C code, but it is really -*- C++ -*-

// <copyright>
// 
// Copyright (c) 1993-1995
// Institute for Information Processing and Computer Supported New Media (IICM),
// Graz University of Technology, Austria.
// 
// </copyright>

//<file>
//
// Name:       arrays.h
//
// Purpose:    Generic dynamic and sorted arrays of data
//
// Created:     1 Feb 92    Gerald Pani
//
// Modified:   20 Jul 93    Gerald Pani
//
//
//
// Description:
//
// Macros for creating arrays of abstract datatypes. The array is
// always sorted and dynamic in storage allocation.
//
// Macros:
// - Arraysdeclare(name_of_array_datatype,name_of_element_datatype)
//   Declaration part of new class name_of_array_datatype.
// - Arraysimplement(name_of_array_datatype,name_of_element_datatype)
//   Implementation part of class name_of_array_datatype.
//
//</file>

#ifndef hg_utils_arrays_h
#define hg_utils_arrays_h

#include <iostream.h>
#include <generic.h>
#include <stdlib.h>
#include "types.h"

//<class>
//
// Name:       Array
//
// Purpose:    Array is a dynamic and sorted array of Data created by macros
//             Arraysdeclare(Array,Data) and Arraysimplement(Array,Data).
//
// Public Interface:
//
// - Array()
//   Default constructor. Sets up an empty Array of length 0.
//
// - Array( int c, Data* i, int s = 0)
//   Constructor. Sets up an Array of length s (or default c) from
//   datafield i within c elements. The constructor sorts the array.
//   The STORAGE ALLOCATED for datafield i is NOW CONTROLLED by the ARRAY.
//
// - Array( int s)
//   Constructor. Sets up an empty Array of length s.
//
// - Array( const Array& arr)
//   Constructor. Sets up an Array as a copy of arr.
//
// - Array( const Array& arr, int beg, int count)
//   Constructor. Sets up an Array from the next count elements of arr
//   beginning at position beg.
//
// - ~Array()
//   Destructor. Deletes ALL storage used by the array itself and
//   calls the destructor of all elements.
//
// - void init( int c, Data* i, int s = 0)
//   Frees old data and reinitializes the array controlling the sort order.
//   The STORAGE ALLOCATED for datafield i is NOW CONTROLLED by the ARRAY.
//
// - void free()
//   Deletes ALL storage used by the array itself and
//   calls the destructor of all elements.
//
// - boolean insert( const Data& data)
//   Inserts data into the array. If data is already inserted, the
//   function does nothing and return false.
//
// - void append( const Data& data)
//   Appends data to the end of array. NOTE: The array may not be sorted
//   or could have duplicate elements after this operation (see 'sort' operation).
//
// - void sort()
//   Sorts the array and removes duplicate elements. Invoke this method only
//   after a number of append operations.
//
// - int count() const
//   Returns the number of elements.
//
// - const Data* data() const
//   Returns a pointer to the internal data array.
//
// - const Data& operator []( int i) const
//   Returns a reference to the i-th element.
//
// - Array& operator =( const Array& arr)
//   Frees any old data (unless arr and *this are equal) and copies the data of arr.
//   The function returns a reference to the result (*this).
//
// - Array& operator +=( const Array& a)
//   Sets *this to the union of (the sets) *this and a returning *this.
//
// - Array& operator *=( const Array& a)
//   Sets *this to the intersection of (the sets) *this and a returning *this.
//
// - Array& operator -=( const Array& a)
//   Removes all elements from *this which are members of a.returning *this.
//
// - boolean operator ==( const Array& a)
//   Returns true, if both arrays are equal.
//
// - boolean remove( const Data& data)
//   Removes data from *this returning true, if data was to remove.
//
// - boolean element( const Data& data) const
//   Returns true, if data is an element of *this.
//
// - boolean position( const Data& data, int& i) const
//   Returns true (i holding the array index of data), if data is an element of *this.
//
// - Array& getpart( const Array& arr, int beg, int c)
//   Sets *this to the subset of arr consisting of the next c consecutive
//   elements beginning at position beg. *this is returned.
//
// - friend ostream& operator <<( ostream& s, const Array& arr)
//   Writes the array arr to the ostream s by calling the operator <<
//   for each element. Elements are separated by space and after the
//   last item a newline is printed.
// 
// Protected Interface:
//
// - void enlarge()
//   Enlarges (double) the allocated storage.
//
// - void remove_( int i)
//   Removes the element at position i.
//
// - void init( const Array& arr, int begin, int count)
//   Reinitializes the array with count elements of arr beginning at begin.
//
//
// Description:
//
// The key of each array element is unique. Insert and sort garantee
// this. The array is always sorted. Binary search is used to find an
// element. 
//
// To create an array of class Data use Arraysdeclare(ArrayName, Data)
// in your header file and Arraysimplement(ArrayName, Data) in your
// corresponding C++-file.
//
// The class Data must have:
// * a default constructor
// * a destructor
// * an operator =
// * an operator ==
// * an operator <
// * an operator !=
// * an operator <<
// 
//</class>


#define Arraysdeclare(Array, Data)					      \
class Array {								      \
  public:								      \
     Array();								      \
     Array( int c, Data* i, int s = 0);					      \
     Array( int s);							      \
     Array( const Array&);						      \
     Array( const Array&, int, int);					      \
     ~Array();								      \
     void init( int c, Data* i, int s = 0);				      \
     void free();							      \
     boolean insert( const Data&);					      \
     void append( const Data&);						      \
     int count() const;							      \
     const Data* data() const;						      \
     const Data& operator []( int) const;				      \
     Array& operator =( const Array&);    				      \
     Array& operator +=( const Array&);				       	      \
     Array& operator *=( const Array&);				  	      \
     Array& operator -=( const Array&);		 			      \
     boolean operator ==( const Array&);				      \
     boolean remove( const Data&);					      \
     boolean element( const Data&) const;				      \
     boolean position( const Data& , int& ) const;			      \
     Array& getpart( const Array&, int, int);				      \
     void sort();							      \
									      \
     friend ostream& operator <<( ostream&, const Array&);		      \
									      \
  protected:								      \
     void enlarge();							      \
     void remove_( int);						      \
     void init( const Array&, int, int);				      \
     static int merge( Data* f, int c);					      \
									      \
     int count_;							      \
     Data* data_;							      \
     int size_;								      \
									      \
  public:								      \
     static int version_1_0;						      \
									      \
};									      \
									      \
static int name2(Array,_version) = Array::version_1_0;			      \
									      \
inline const Data& Array::operator []( int i) const {			      \
     return data_[i];							      \
}									      \
									      \
inline int Array::count() const { 					      \
     return count_;							      \
}									      \
									      \
inline const Data* Array::data() const { 				      \
     return data_;							      \
}									      \
									      \
inline Array::Array() : count_( 0), data_( nil), size_( 0) {		      \
}									      \
									      \
inline Array::Array( const Array& arr) : count_( 0), data_( nil), size_( 0) { \
     operator=( arr);							      \
}									      \
									      \
inline Array::Array( int c, Data* i, int s) : count_( c), data_( i) {	      \
     if (s <= c)							      \
	  size_ = count_;						      \
     else								      \
	  size_ = s;							      \
     sort();								      \
}									      \
									      \
inline Array::Array( int s) : count_( 0), size_( s) {			      \
     data_ = s ? new Data[s] : nil;					      \
}

#define Arraysimplement(Array, Data)					      \
int Array::version_1_0;							      \
									      \
boolean Array::insert( const Data& data) {				      \
     int pos;								      \
     if (!position( data, pos)) {					      \
	  if (count_ == size_)						      \
	       enlarge();						      \
	  for (int i = count_; i > pos;i--)				      \
	       data_[i] = data_[i-1];					      \
	  data_[pos] = data;						      \
	  count_++;							      \
	  return true;							      \
     }									      \
     return false;							      \
}									      \
									      \
void Array::append( const Data& data) {					      \
     if (count_ == size_)						      \
	  enlarge();							      \
     data_[count_++] = data;						      \
}									      \
									      \
boolean Array::remove( const Data& data) {				      \
     int pos;								      \
     if (position( data, pos)) {					      \
	  remove_( pos);						      \
	  return true;							      \
     }									      \
     return false;							      \
}									      \
									      \
void Array::remove_( int pos) {						      \
     count_--;								      \
     for (int i = pos; i < count_; i++) {				      \
	  data_[i] = data_[i+1];					      \
     }									      \
     Data d;                                                                  \
     data_[count_] = d;                                                       \
}									      \
									      \
boolean Array::position( const Data& data, int& pos) const {		      \
     int low = 0, high = count_;					      \
     for (;;) {								      \
	  if (low == high) {						      \
	       pos = low;						      \
	       return false;						      \
	  }								      \
	  int mid = (low + high)/2;					      \
	  if (data == data_[mid]) {					      \
	       pos = mid;						      \
	       return true;						      \
	  }								      \
	  if (data < data_[mid])					      \
	       high = mid;						      \
	  else								      \
	       low = mid + 1;						      \
     }									      \
}									      \
									      \
void Array::free() {							      \
     count_ = size_ = 0;						      \
     if (!data_)							      \
	  return;							      \
     delete [] data_;							      \
     data_ = nil;							      \
}									      \
									      \
void Array::init( int c, Data* i, int s) {				      \
     free();								      \
     count_ = c;							      \
     if (s < count_)							      \
	  size_ = count_;						      \
     else 								      \
	  size_ = s;							      \
     data_ = size_ ? i : nil;						      \
     sort();								      \
}									      \
									      \
Array::~Array() { 							      \
     free();								      \
}									      \
									      \
boolean Array::element( const Data& data) const {			      \
     int pos;								      \
     if (position( data, pos))						      \
	  return true;							      \
     return false;							      \
}									      \
									      \
void Array::enlarge() {							      \
     Data* olddata = data_;						      \
     if (size_ == 0)							      \
	  size_ = 1;							      \
     else								      \
	  size_ *= 2;							      \
     data_ = new Data [size_];						      \
     if (!data_) \
        abort() ; \
     Data* p = olddata, * q = data_;					      \
     for(int i = count_; i; i--)					      \
	  *q++ = *p++;							      \
     delete [] olddata;							      \
}									      \
									      \
Array& Array::operator =( const Array& arr) {				      \
     if (data_ == arr.data_)						      \
          return *this;							      \
     free();								      \
     if (!arr.count())							      \
	  return *this;							      \
     data_ = new Data [arr.count()];					      \
     if (!data_)							      \
	  return *this;							      \
     count_ = size_ = arr.count();					      \
     for (int i = 0; i < count_; i++ ) {				      \
	  data_[i] = arr[i];						      \
     }									      \
     return *this;							      \
}									      \
									      \
Array& Array::getpart( const Array& arr, int begin, int count) {	      \
     free();								      \
     init( arr, begin, count);						      \
     return *this;							      \
}									      \
									      \
Array::Array( const Array& arr, int begin, int count) : count_( 0), data_( nil), size_( 0) { \
     init( arr, begin, count);						      \
}									      \
									      \
void Array::init( const Array& arr, int begin, int count) {		      \
     if (begin < 0)							      \
	  begin = 0;							      \
     if (begin >= arr.count())						      \
	  return;							      \
     if (count <= 0)							      \
	  return;							      \
     if (begin + count > arr.count())					      \
	  count = arr.count() - begin;					      \
     data_ = new Data[count];						      \
     size_ = count_ = count;						      \
     for (int i = 0; i < count_; i++) {					      \
	  data_[i] = arr[begin + i];					      \
     }									      \
}									      \
									      \
Array& Array::operator +=( const Array& arr) {				      \
     int count = count_ + arr.count();					      \
     if (!count)	 						      \
	  return *this;							      \
     if (!count_)	   						      \
	  return operator=( arr);					      \
									      \
     Data* ndata = new Data [count];					      \
     int i, j, k;							      \
     for (i = 0, j = 0, k = 0; i < count_ && j < arr.count(); ) {	      \
	  if (data_[i] == arr[j]) {					      \
	       ndata[k++] = data_[i++];					      \
	       j++;							      \
	  }								      \
	  else if (data_[i] < arr[j]) {					      \
	       ndata[k++] = data_[i++];					      \
	  }								      \
	  else {							      \
	       ndata[k++] = arr[j++];					      \
	  }								      \
     }									      \
     if (i == count_) {							      \
	  for ( ; j < arr.count(); ) 					      \
	       ndata[k++] = arr[j++];					      \
     }									      \
     else {								      \
	  for ( ; i < count_; ) 					      \
	       ndata[k++] = data_[i++];					      \
     }									      \
     init(k, ndata, count);						      \
     return *this;							      \
}									      \
									      \
Array& Array::operator *=( const Array& arr) {				      \
     if (!count_)							      \
	  return *this;							      \
     int i, j, k;							      \
     for (i = 0, j = 0, k = 0; i < count_ && j < arr.count(); ) {	      \
	  if (data_[i] == arr[j]) {					      \
	       data_[k++] = data_[i++];					      \
	       j++;							      \
	  }								      \
	  else if (data_[i] < arr[j]) {					      \
	       i++;							      \
	  }								      \
	  else {							      \
	       j++;							      \
	  }								      \
     }									      \
     for (i = k; i < count_; i++) {                                           \
          Data d;                                                             \
          data_[i] = d;                                                       \
     }                                                                        \
     count_ = k;							      \
     return *this;							      \
}									      \
									      \
Array& Array::operator -=( const Array& arr) {				      \
     if (!count_)							      \
	  return *this;							      \
     int i, j, k;							      \
     for (i = 0, j = 0, k = 0; i < count_ && j < arr.count(); ) {	      \
	  if (data_[i] == arr[j]) {					      \
	       i++;							      \
	       j++;							      \
	  }								      \
	  else if (data_[i] < arr[j]) {					      \
	       data_[k++] = data_[i++];					      \
	  }								      \
	  else {							      \
	       j++;							      \
	  }								      \
     }									      \
     if (j == arr.count()) {						      \
	  for ( ; i < count_; ) 					      \
	       data_[k++] = data_[i++];					      \
     }									      \
     for (i = k; i < count_; i++) {                                           \
          Data d;                                                             \
          data_[i] = d;                                                       \
     }                                                                        \
     count_ = k;							      \
     return *this;							      \
}									      \
									      \
boolean Array::operator ==( const Array& data) {			      \
     if (count() != data.count())					      \
	  return false;							      \
     for (int i = 0; i < count(); i++) {				      \
	  if (data_[i] != data[i])					      \
	       return false;						      \
     }									      \
     return true;							      \
}									      \
									      \
int Array::merge( Data* f, int c) {			\
     if (c <= 0)					\
	  return 0;					\
     if (c == 1)					\
	  return 1;					\
     if (c == 2) {					\
	  if (f[0] == f[1]) {				\
	       Data d;					\
	       f[1] = d;				\
	       return 1;				\
	  }						\
	  else if (f[1] < f[0]) {			\
	       Data d = f[1];				\
	       f[1] = f[0];				\
	       f[0] = d;				\
	  }						\
	  return 2;					\
     }							\
     Data* fh = new Data[c];				\
     int i = 0;						\
     for (i = 0; i < c; i++)				\
	  fh[i] = f[i];					\
     int h = (c+1)/2;					\
     int a = merge( fh, h);				\
     int b = merge( &fh[h], c-h);			\
     int j = 0;						\
     int k = h;						\
     for (i = 0, j = 0, k = h; j < a && k < h + b; ) {	\
	  if (fh[j] == fh[k])				\
	       j++;					\
	  else if (fh[j] < fh[k])			\
	       f[i++] = fh[j++];			\
	  else						\
	       f[i++] = fh[k++];			\
     }							\
     for ( ; j < a; )					\
	  f[i++] = fh[j++];				\
     for ( ; k < h + b; ) 				\
	  f[i++] = fh[k++];				\
							\
     h = i;						\
     Data d;						\
     for ( ; i < c; )					\
	  f[i++] = d;					\
     delete [] fh;					\
     return h;						\
}							\
							\
void Array::sort() {				\
     boolean ok = true;				\
     int i;					\
     for (i = count() - 1; i > 0; i--)		\
	  if (!(data_[i-1] < data_[i])) {	\
	       ok = false;			\
	       break;				\
	  }					\
     if (ok) 					\
	  return;				\
     count_ = merge( data_, count_);		\
     return;					\
}						\
						\
									      \
ostream& operator << ( ostream& s, const Array& arr) {			      \
     for (int i = 0; i < arr.count(); i++)				      \
	  s << arr[i] << ' ';						      \
     s << endl;								      \
     return s;								      \
}

#endif