/*
 * Copyright Derek Park 2001
 * All rights reserved
 */
import java.util.NoSuchElementException;

/**
 *BucketSort provides a quick, memory intensive sort for int arrays
 */

public class BucketSort {

   /**
    *Sorts an int array passed by client
    */
   public static void bucketSort(int [] inputArray) {
      /*
       *instantiate BucketSets to use for sorting
       */
      BucketSet currentBucketSet = new BucketSet(inputArray.length);
      BucketSet prevBucketSet = new BucketSet(inputArray.length);
      BucketSet tempBucketSet;
      
      // stores the current digit to sort (ie: 1, 10, 100, 1000, etc.)
      int currentDigit = 1;
   
      // loop until through array
      for (int i = 0; i < inputArray.length; i++) {
         
         // use Bucket's add method to
         currentBucketSet.add((inputArray[i] / currentDigit) % 10,
                             inputArray[i], currentDigit);
      }

      // Add from one BucketSet to the next until sorted
      while (currentBucketSet.notSorted()) {
         // set prev to current and vice versa
         tempBucketSet = prevBucketSet;
         prevBucketSet = currentBucketSet;
         currentBucketSet = tempBucketSet;
         
         currentBucketSet.setNotSorted(false);  // reset the BucketSet
         currentDigit *= 10;  // move digit to next power

         while (!(prevBucketSet.isEmpty())) {
            // get next element from previous BucketSet
            int element = prevBucketSet.getNext();
            
            // add element to the current BucketSet
            currentBucketSet.add((element / currentDigit) % 10, 
                                element, currentDigit);
         }
      }
      
      // copy from last BucketSet used to the original array
      for (int i = 0; i < inputArray.length; i++) {
         inputArray[i] = currentBucketSet.getNext();      
      }
      
   }
   
   /* BucketSet is a supporting class for BucketSort, 
    * used to hold Buckets
    */
   private static class BucketSet {

      int [][] bucket;                       // array to hold Buckets
      int [] bucketDepth = {-1,-1,-1,-1,-1,
                            -1,-1,-1,-1,-1}; // depth of each bucket
      int totalInBuckets = 0;                // total number in all buckets
      boolean notSorted = false;
      
      public BucketSet(int inputCols) {
         bucket = new int [10][inputCols];   // create buckets based on input
      }
   
      public boolean notSorted() {
         return notSorted;
      }
      
      public void setNotSorted(boolean inputNotSorted){  // reset Bucket
         notSorted = inputNotSorted;
      }
   
      public boolean isEmpty() {
         return (totalInBuckets == 0);
      }
      

      /*      
       * Adds to one bucket in the BucketSet
       * place is the bucket (0 - 9) to store the value in
       * inputValue is the value to be stored
       * currentDigit is the power to opertate on (1, 10, 100)
       */
      public void add(int place, int inputValue, int currentDigit) {
         bucketDepth[place]++;
         bucket[place][bucketDepth[place]] = inputValue;  // add to bucket
         totalInBuckets++;
         if (inputValue > currentDigit) { // if further sorting is needed
            notSorted = true;             // set variables accordingly
         }
      }

      // Returns a value from a bucket, starting with the zero bucket
      public int getNext() {
         for (int i = 0; i < 10; i++) { // loop until non-empty bucket found
            if (bucketDepth[i] >= 0 ) { // if current bucket is not empty
               int returnValue = bucket[i][0]; // save the element to be returned
               
               //take from the top of the bucket and move the rest up
               for (int j = 1; j <= bucketDepth[i]; j++){
                  bucket[i][j - 1] = bucket[i][j];
               }
               bucketDepth[i]--;          // bucket has one less
               totalInBuckets--;          // total has one less
               return returnValue;        // return the one saved as temp
            }
         }
         /*
          * This won't be reached unless the user failed to check isEmpty()
          * Hopefully the user will at least catch the exception
          */
         throw new NoSuchElementException("Element below zero");
      }
   
   }

}