/*
 * @(#)RadixSortAlgorithm.java      1.0 2000/02/15 Kenji YOKOYAMA 
 *
 * Copyright (c) 2000 Science University of Tokyo
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies. Please refer to the file "copyright.html"
 * for further important copyright and licensing information.
 *
 * SUT MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. UBC SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 */

/**
 * A radix sort demonstration algorithm
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author Kenji YOKOYAMA
 * @version     1.0, 15 Feb 2000
 *
 */


public class RadixSortAlgorithm extends SortAlgorithm
{
    private boolean pauseTrue(int lo, int hi) throws Exception {
	super.pause(lo, hi);
	return true;
    }
    
   void RadixSort(int a[], int lo0, int hi0, int b) throws Exception
   {
      int t, lo, hi;

      if(hi0>lo0 && b>=0)
        {
        lo = lo0;
        hi = hi0;
        while(lo != hi)
          {
            while(bits(a[lo], b, 1) == 0 && pauseTrue(lo0, hi0) && lo<hi) lo++;
            while(bits(a[hi], b, 1) != 0 && pauseTrue(lo0, hi0) && hi>lo) hi--;
            swap(a, lo, hi);
          }

        if(bits(a[hi0], b, 1) == 0) hi++;
          RadixSort(a, lo0, hi-1, b-1);
          RadixSort(a, hi, hi0, b-1);
      }

   }



   private void swap(int a[], int i, int j)
   {
      int T;
      T = a[i];
      a[i] = a[j];
      a[j] = T;

   }

   public void sort(int a[]) throws Exception
   {
      RadixSort(a, 0, a.length-1, 6);
   }

   public int bits(int x, int k, int j)
   {
      return (x >> k) & ~(~0 << j);
   }

}