/**
 * Copyright (C) 1997  William Braynen
 * Contact information can be found at www.samdurak.com
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * 
 * Written by    :  William Braynen
 * Last modified :  June 15, 1997
 * Class name    :  ArrayI
 *
 * properties:
 *    the (publicly-accessable) range of the array object = array[1..size]
 *    array[size+1] = 0 and its purpose is to tell the end of the array.
 *
 * void   Array( int size)		- public constructor, creates an array of specified size
 * void   fill()				- fills the array with random integers in the range of 0 to this.size
 * int    getItem( int position)            - returns the value of the element at specified position
 * int 	  sortedValue( int position)		- returns the value of the element at specified position in the final (sorted) array
 * int    length()				- returns the last element's index number (=the size of the array)
 * void   swap( int position1, int position2)	- swaps two elements
 * String text()				- returns a textual representation of the array
 * void   addItem( int item)	- places `element` into the most-left empty spot in the array
 * void   empty()				- empties the array, setting all its elements to 0.
 * void   setItem( int position, int value)	- array[position] = value
 * void   insertItem( int position, int value)	- side-effect:  array's size increases by one
 * ArrayI partition( int position1, int position2) - returns a subset of the array object containing elements position1 thru position2
 * ArrayI darken( int position1, int position2) - the array object's elements less than position1 and greater than position2 are set to 999.
 * int[]  cloneArray( int[] array, int size )	- *** private ***
 * int[]  cloneArray( int[] array )		- *** private ***
 * void   sort()				- *** private ***
 *
 * NOTE:  fill( 200 ) will only produce numbers divisible by 2,
 *	  fill( 300 ) will only produce numbers divisible by 3, etc.
 * BECAUSE fill( int y_max ) first uses fill( 100 ) and then multiplies every
 * 	   received value by (y_max/100).
 */

import java.lang.Object;
import java.util.Random;
import java.lang.String;
import java.awt.*;


public class ArrayI extends Object {

   private int 	   array[], sortedArray[];
   private int 	   size = 100;
   private int     InsertionSortIndex = 0;
   private boolean inplace[];


   public void init() {
	this.array  	 = new int[ this.size+2 ];		// create the array
	this.sortedArray = new int[ this.size+2 ];
	this.inplace	 = new boolean[ this.size+2 ];
	for (int index = 0; index < this.size+2; index++) {	// initialize the array
		this.array[ index ] 	  = 0;  
		this.sortedArray[ index ] = 0;
		this.inplace[ index ]	  = false;  } }



   public ArrayI( int size ) { 
	this.size = size;
	this.init(); }
   

   public void fillPerm() {
	// fill array with {1..size}
	for (int index = 1; index <= this.size; index++) {
	   this.array[index] = index;
	} // end for

	// make a copy of the array before it gets shuffled
	this.sortedArray = cloneArray( this.array );

	// shuffle
	Random randomGenerator = new Random();
	for (int index = 1; index <= this.size; index++) {
	   swap( 1, getRandomInteger( randomGenerator, this.size ) );
	   swap( getRandomInteger( randomGenerator, this.size ), getRandomInteger( randomGenerator, this.size ) );
	   swap( getRandomInteger( randomGenerator, this.size ), this.size );
	} // end for
   } // end fillPerm



   public void fillRandom() {
	  Random randomGenerator = new Random();
	  for (int index = 1; index <= this.size; index++) {
	     this.array[ index ] = getRandomInteger( randomGenerator, this.size );
	  }  // end for
	  this.sortedArray = cloneArray( this.array );	
	  this.sort();  // !! properly only works globally - locally sorts this.array!
   }  // end fillRandom



   // returns a random integer in the range from 0 to MAX
   private int getRandomInteger( Random randomGenerator, int MAX ) {
      float	randomFloat;
	  float	ONE   = 1;
	  float	f_INC = ONE / MAX;
      randomFloat = randomGenerator.nextFloat();
      boolean end = false;
      float	f   = 0;
      int	n   = 0;
      while (!end) {
        n++;
        f=f+f_INC;
        if (randomFloat < f) end=true; 
      } // end while
      return n;
    } // end getRandomInteger



   public void copyOf( ArrayI original ) {
      for (int n = 1; n < original.length()-1; n++) { // copies array1 to temp array
          setItem(n, original.getItem(n));
          sortedArray[ n ] = original.sortedValue( n );
      } // end for
   } // end copyOf


   public int  getInsertionSortIndex() {
      return InsertionSortIndex;
   } // end getInsertionSortIndex
   
   
   public void setInsertionSortIndex( int value ) {
      InsertionSortIndex = value;
   } // end setInsertionSortIndex
    


   // same as method `value`;
   // renamed `getItem` in order to follow naming convention
   public int getItem( int position ) {
        return this.array[ position ]; }
		

   public int value( int position ) {
	return this.array[ position ]; }


   public int sortedValue( int position ) {
	return this.sortedArray[ position ]; }
	

   public int last() {
	return this.size;  }

   public int length() {
	return this.size;  }



   public void swap( int position1, int position2 ) {
	int temp;
	temp = this.array[ position1 ];
	this.array[ position1 ] = this.array[ position2 ];
	this.array[ position2 ] = temp; }


   // this shit doesn't work
   public int[] insertFirst( int fromPosition ) {
	int newArray[];
	newArray = new int[ this.size + 2 ];
	newArray[ 0 ] = 0;
	newArray[ 1 ] = this.array[ fromPosition ];

	int index2 = 2;
	for (int index = 2; index <= this.size+2; index++) {
	   if (index == fromPosition) index++;
	   newArray[index2] = this.array[index];
	   index2++;
	}  // end for
	
	return newArray;
   }  // end insertFirst



   public String text() {
	String text, element, separator;
	separator = ", ";
        text      = " ";
        element   = " ";

	for (int index = 1; index < this.size+1; index++) {
	   element = String.valueOf( this.array[index] );
	   text    = text + element + separator; }
        return text; }

   public void setItem( int position, int value ) {
	this.array[ position ] = value; }


   public void insertItem( int position, int value ) {
	int newArray[];
	newArray = new int[this.size+3];
	for (int index = 0;  index < position;  index++) {
	    newArray[ index ]   = this.array[ index ];  }
	newArray[ position ]  = value;
	for (int index = position+1;  index <= this.size+2;  index++) {
	   newArray[ index ] = this.array[ index-1 ];  }
	this.size++;
	this.array = newArray; }


   // auxiliary method for `ArrayApplet.quickSort()`
   // pre-condition:	position1 <= position2
   // post-condition:	returns a subset of the array object
   //			containing elements first_pointer thru last_pointer
   public ArrayI partition( int position1, int position2 ) {
	ArrayI newArray = new ArrayI( position2 - position1 + 1 );
	int index1 = 0;
	for (int index2 = position1;  index2 <= position2;  index2++) {
	   index1++;
	   newArray.setItem( index1, this.array[ index2 ] ); }
	return newArray; }


   // auxiliary method for `ArrayApplet.quickSort()`
   // pre-condition:	position1 <= position2
   // post-condition:	the array object's elements less than position1 
   //			and greater than position2 are set to 999.
   public ArrayI darken( int position1, int position2 ) {
	ArrayI newArray = new ArrayI( this.size+1 );
	for (int index = 1;  index < position1;  index++) {
	   newArray.setItem( index, 999 ); }
	for (int index = position1;  index <= position2;  index++) {
           newArray.setItem( index, this.array[ index ] ); }
	for (int index = position2+1;  index <= this.size;  index++) {
	   newArray.setItem( index, 999 ); }
        return newArray;
	}


   private int[] cloneArray( int[] array1, int size ) {
	int[] newArray = new int[ size+2 ];
	for (int index = 0; index < size+2; index++) {
	   newArray[ index ] = array1[ index ]; }
	return newArray; }
	
   private int[] cloneArray( int[] array1 ) { return cloneArray( array1, this.size ); }


   // uses Bubble Sort globally on this.sortedArray;
   // auxiliary method for the `fill` method
   private void sort() {
	int t;
	int last = this.size;
    	for (int i = last;  i > 0;  i--) {
      	    for (int j = 2;  j < i + 1;  j++) {
        	if (this.sortedArray[j-1] > this.sortedArray[j]) {
		     t = this.sortedArray[j-1];
		     this.sortedArray[j-1] = this.sortedArray[j];
		     this.sortedArray[j] = t;
		}
            }
	}
    }



/*------------------------------------------------------------------*/

   public void addItem( int item ) {
        int index = 1;
        // get to an empty slot in the array
        while ( array[ index ] != 0 ) {
                index++; }
        // if the array is NOT completely filled
        if ( index != 11 )  array[ index ] = item; }


   public void empty() {
        for ( int index = 1;  index < 11;  index++ ) {
             array[ index ] = 0; } }


   public void bubble() {
	int t;
	for (int i = this.last();  i > 0;  i--) {
 	    for (int j = 2;  j < i + 1;  j++) {
        	if (this.value(j-1) > this.value(j)) this.swap(j-1,j); } } }

/*------------------------------------------------------------------*/

}