HW4 Solutions Page

Return to homework page.

// cs146sec6hw4file1.java - sorting algorithm tester


import java.util.*;
import java.io.*;

/** 

   This class does not have any non-static methods. It 
   groups together various array sorting algorithms under one
   class. Using static methods makes the sorting algortihms
   work slightly faster.

   This class can be run from the command line using:

   java cs146sec6hw4file1 x filename

   where x is one of the sort types mentioned in HW description
   and filename is the name of a file with int's on each distinct row.

   @author  Chris Pollett
   @version 1.0			
*/
public class cs146sec6hw4file1
{
   /**
      Sorts array passed to it according to one of the sorting
      algorithms available in this class.

      @param sortType - type of sorting algorithm to use
      @param array - array to be sorted.
   */
   public static void sort(String sortType, Comparable[] array)
   {
       if(sortType.equals("insertion")) insertionSort(array);
       else if(sortType.equals("3heap")) threeHeapSort(array);
       else if(sortType.equals("skew")) skewHeapSort(array);
       else if(sortType.equals("binomial")) binomialHeapSort(array);
       else System.err.println("Invalid sort type array not sorted.");
   }

   /**
      Sorts the array using a skew heap
      @param array - what is to be sorted.
   */
   public static void insertionSort(Comparable[] array)
   {
      int j;

      for( int p = 1; p < array.length; p++)
      {
          Comparable tmp = array[ p ];
          
          for( j = p; j > 0 && tmp.compareTo( array[ j - 1 ] ) < 0; j--)
             array[ j ] = array[ j - 1];
       
          array[j] = tmp;
      }
   }

   /**
      Sorts the array using a 3-heap heap.
      Since this is the simplest kind of heap based sorting
      in this homework. We didn't use a separate class to implement
      the 3-heaps auxiliary methods and instead having them as non-public
      functions.

      @param array - what is to be sorted.
   */
   public static void threeHeapSort(Comparable[] array)
   {
      for( int i = array.length/3 ; i >= 0; i--)
         percolateDown(array, i, array.length);

      for( int i = array.length - 1; i > 0; i--)
      {
         swap(array, 0, i);
         percolateDown(array, 0 , i);
      }
   }

   /**
      Sorts the array using a skew heap
      @param array - what is to be sorted.
   */
   public static void skewHeapSort(Comparable[] array)
   {
       heapSort("skew", array);
   }

   /**
      Sorts the array using a binomial heap
      @param array - what is to be sorted.
   */
   public static void binomialHeapSort(Comparable[] array)
   {
       heapSort("binomial", array);
   }

   /*
      Main entry point
   */
   public static void main(String[] args) 
   {
      if( args.length < 2 )
      {
         System.err.println("You need two command line arguments:"); 
         System.err.println("sort_type filename"); 
         System.exit(1);
      }
		
      Comparable[] array;

      array = readArray(args[1]);
      if(array == null) 
      {
         System.err.println("Sort array empty so bailing.");
         System.exit(1);
      }

      sort(args[0], array);
      printArray("",array);
     
   }

   /*
      Used to do any of the more complicated sorting
      algorithms we'll consider based on Heap.
      This function uses the insert() and deleteMin()
      methods of any class that implements Heap whose
      name we've entered to do the sorting.

      s - is the name of the kind of Heap we'll use.
      array - is the array to be sorted.
   */
   static void heapSort(String s, Comparable[] array)
   {
       Heap heap = new SkewHeap();

       if(s.equals("binomial"))
          heap = new BinomialQueue();
       else if(!s.equals("skew"))
       {
          System.err.println("Bad sort type");
          return;
       }

       int i;
       for(i = 0; i < array.length; i++)
       {
          try
          {
             heap.insert(array[i]);
          }
          catch(Overflow o)
          {
              System.err.println("Overflow exception"+o.toString());
              System.exit(1);
          }
       }

       for(i = 0; i < array.length; i++)
          array[i] = heap.deleteMin();
   }

   /*
      Reads an array of Integers from a file.
      Each Integer is assumed to be on its own line. 
      Lines not in this format are ignored.
   */
   static Comparable[] readArray(String file)
   {
      String line;
      ArrayList arr = new ArrayList();

      try
      {
         BufferedReader buf= new BufferedReader(new FileReader( file));

         while((line = buf.readLine()) != null)
         {
            try
            {
               arr.add(Integer.valueOf(line));
            }
            catch(NumberFormatException ne) {} //ignore bad line
         }
         buf.close();
      }
      catch(FileNotFoundException fe)
      {
         System.err.println("File not found");
         System.exit(1);
      }
      catch(IOException ie)
      {
         System.err.println("An I/O Exception occurred:"+ie.toString());
         System.exit(1);
      } 
 
      Comparable[] array = new Comparable[arr.size()];

      /* bogus was to convert ArrayList to an array of Comparable's.
         can't do toArray() and cast */

      for(int i = 0 ; i < arr.size(); i++) 
         array[i] = (Comparable)arr.get(i);

     return array;
   }

   /*
     Prints a title followed by the lement of array each on its own line
   */
   static void printArray(String title, Comparable[] array)
   {
      System.out.println(title);

      for(int i = 0; i < array.length; i++ )
         System.out.println(array[i].toString());
           
   }

   /*
      Used to restore the heap property beneath i in array when the
      3-heap ends at n. Used by threeHeapSort.
   */
   static void percolateDown(Comparable[] array, int i, int n)
   {
      int child;
      Comparable tmp = array[i];

      while((child = leftChild(i)) < n)
      {
         int index = child + 1;

         if( index < n   && array[child].compareTo(array[index]) < 0)
           child = index;
         if( ++index < n && array[child].compareTo(array[index]) < 0)
           child = index;

         if( tmp.compareTo( array[child]) < 0)
           array[ i ] = array[ child];       
         else
            break;         
         
         i  = child;
      }
      array[ i ] = tmp;
   }

   /*
      Computes the left child of node i in the 3-heap.
      Used by threeHeapSort.
   */
   static int leftChild(int i)
   {
      return 3*i + 1;
   }

   /*
      Swaps value at index i in array with value at index j.
      Used by threeHeapSort. 
   */
   static void swap(Comparable[] array, int i, int j)
   {
      Comparable tmp = array[i];
      array[i] = array[j];
      array[j] = tmp; 
   }
} //end cs146sec6hw2file1.java

/*
   Interface of common function to the various type of heaps.
   (In particular Skew and Binomial Heaps)
*/
interface Heap
{
   public void insert( Comparable x ) throws Overflow;
   public Comparable deleteMin();
}

/* 
  Basic node stored in skew heaps
*/
class SkewHeapNode
{
   // Constructors
   SkewHeapNode( Comparable theElement )
   {
      this( theElement, null, null );
   }

   SkewHeapNode( Comparable theElement, SkewHeapNode lt, SkewHeapNode rt )
   {
      element = theElement;
      left    = lt;
      right   = rt;
   }

   Comparable   element;      // The data in the node
   SkewHeapNode left;         // Left child
   SkewHeapNode right;        // Right child
}


/*
 Implements a skew heap.
 modified from code in Mark Allen Weiss' book
*/

class SkewHeap implements Heap
{
  /*
    Construct the skew heap.
  */
  SkewHeap( )
  {
     root = null;
  }

  /*
     Merge rhs into the priority queue.
     rhs becomes empty. rhs must be different from this.
     rhs the other leftist heap.
  */
  void merge( SkewHeap rhs )
  {
     if( this == rhs )    // Avoid aliasing problems
        return;
    
     root = merge( root, rhs.root );
     rhs.root = null;
  }

  /*
     Internal static method to merge two roots.
     Deals with deviant cases and calls recursive merge1.
  */
  static SkewHeapNode merge( SkewHeapNode h1, SkewHeapNode h2 )
  {
     if( h1 == null )
        return h2;
     if( h2 == null )
        return h1;
     if( h1.element.compareTo( h2.element ) < 0 )
        return merge1( h1, h2 );
     else
        return merge1( h2, h1 );
  }

  /*
    Internal static method to merge two roots.
    Assumes trees are not empty, and h1's root contains smallest item.
  */
  static SkewHeapNode merge1( SkewHeapNode h1, SkewHeapNode h2 )
  {
     if( h1.left == null )   // Single node
        h1.left = h2;       // Other fields in h1 already accurate
     else
     {
        h1.right = merge( h1.right, h2 );
        swapChildren( h1 );
     }
     return h1;
  }

  /*
     Swaps t's two children.
  */
  static void swapChildren( SkewHeapNode t )
  {
     SkewHeapNode tmp = t.left;
     t.left = t.right;
     t.right = tmp;
  }

  /*
     Insert into the priority queue, maintaining heap order.
  */
  public void insert( Comparable x )
  {
     root = merge( new SkewHeapNode( x ), root );
  }

  /*
    Find the smallest item in the priority queue.
  */
  Comparable findMin( )
  {
    if( isEmpty( ) )
       return null;
    return root.element;
  }

  /*
    Remove the smallest item from the priority queue.
  */
  public Comparable deleteMin( )
  {
     if( isEmpty( ) )
        return null;
 
     Comparable minItem = root.element;
     root = merge( root.left, root.right );

     return minItem;
  }

  /*
    Test if the priority queue is logically empty.
  */ 
  boolean isEmpty( )
  {
     return root == null;
  }

  SkewHeapNode root;    // root

}

class BinomialNode
{
  // Constructors
  BinomialNode( Comparable theElement )
  {
     this( theElement, null, null );
  }

  BinomialNode( Comparable theElement, BinomialNode lt, BinomialNode nt )
  {
     element     = theElement;
     leftChild   = lt;
     nextSibling = nt;
  }

  Comparable   element;     // The data in the node
  BinomialNode leftChild;   // Left child
  BinomialNode nextSibling; // Right child
}

/*
  Implements a binomial queue.
  Essentially from Mark Allen Weiss book
  Mark Allen Weiss
*/
class BinomialQueue implements Heap
{
  /*
     Construct the binomial queue.
  */
  BinomialQueue( )
  {
     theTrees = new BinomialNode[ MAX_TREES ];
     makeEmpty( );
  }

  /*
     Merge rhs into the priority queue.
     rhs becomes empty. rhs must be different from this.
     rhs the other binomial queue.
     Overflow if result exceeds capacity.
  */
  void merge( BinomialQueue rhs ) throws Overflow
  {
     if( this == rhs )    // Avoid aliasing problems
        return;

     if( currentSize + rhs.currentSize > capacity( ) )
        throw new Overflow( );

     currentSize += rhs.currentSize;

     BinomialNode carry = null;
     for( int i = 0, j = 1; j <= currentSize; i++, j *= 2 )
     {
        BinomialNode t1 = theTrees[ i ];
        BinomialNode t2 = rhs.theTrees[ i ];

        int whichCase = t1 == null ? 0 : 1;
        whichCase += t2 == null ? 0 : 2;
        whichCase += carry == null ? 0 : 4;

        switch( whichCase )
        {
           case 0: /* No trees */
           case 1: /* Only this */
              break;
           case 2: /* Only rhs */
              theTrees[ i ] = t2;
              rhs.theTrees[ i ] = null;
              break;
           case 4: /* Only carry */
              theTrees[ i ] = carry;
              carry = null;
              break;
           case 3: /* this and rhs */
              carry = combineTrees( t1, t2 );
              theTrees[ i ] = rhs.theTrees[ i ] = null;
              break;
           case 5: /* this and carry */
              carry = combineTrees( t1, carry );
              theTrees[ i ] = null;
              break;
           case 6: /* rhs and carry */
              carry = combineTrees( t2, carry );
              rhs.theTrees[ i ] = null;
              break;
           case 7: /* All three */
              theTrees[ i ] = carry;
              carry = combineTrees( t1, t2 );
              rhs.theTrees[ i ] = null;
              break;
           }
     }

      for( int k = 0; k < rhs.theTrees.length; k++ )
         rhs.theTrees[ k ] = null;
      rhs.currentSize = 0;
  }        

  /*
     Return the result of merging equal-sized t1 and t2.
  */
  static BinomialNode combineTrees( BinomialNode t1,
                                                  BinomialNode t2 )
  {
     if( t1.element.compareTo( t2.element ) > 0 )
        return combineTrees( t2, t1 );
     t2.nextSibling = t1.leftChild;
     t1.leftChild = t2;
     return t1;
  }

  /**
     Insert into the priority queue, maintaining heap order.
     This implementation is not optimized for O(1) performance.
     @param x the item to insert.
     @exception Overflow if capacity exceeded.
  */
  public void insert( Comparable x ) throws Overflow
  {
     BinomialQueue oneItem = new BinomialQueue( );
     oneItem.currentSize = 1;
     oneItem.theTrees[ 0 ] = new BinomialNode( x );

     merge( oneItem );
  }

  /*
     Find the smallest item in the priority queue.
  */
  Comparable findMin( )
  {
     if( isEmpty( ) )
        return null;

     return theTrees[ findMinIndex( ) ].element;
  }

    
  /*
     Find index of tree containing the smallest item in the priority queue.
     The priority queue must not be empty.    
  */
  int findMinIndex( )
  {
     int i;
     int minIndex;

     for( i = 0; theTrees[ i ] == null; i++ )
        ;

     for( minIndex = i; i < theTrees.length; i++ )
        if( theTrees[ i ] != null &&
           theTrees[ i ].element.compareTo( theTrees[ minIndex ].element ) < 0 )
              minIndex = i;
     return minIndex;
  }

  /*
     Remove the smallest item from the priority queue.
  */
  public Comparable deleteMin( )
  {
     if( isEmpty( ) )
        return null;

     int minIndex = findMinIndex( );
     Comparable minItem = theTrees[ minIndex ].element;

     BinomialNode deletedTree = theTrees[ minIndex ].leftChild;

     BinomialQueue deletedQueue = new BinomialQueue( );
     deletedQueue.currentSize = ( 1 << minIndex ) - 1;
     for( int j = minIndex - 1; j >= 0; j-- )
     {
         deletedQueue.theTrees[ j ] = deletedTree;
         deletedTree = deletedTree.nextSibling;
         deletedQueue.theTrees[ j ].nextSibling = null;
     }

     theTrees[ minIndex ] = null;
     currentSize -= deletedQueue.currentSize + 1;

     try
     { merge( deletedQueue ); }
     catch( Overflow e ) { }
     return minItem;
   }

   /*
     Test if the priority queue is logically empty.
   */
   public boolean isEmpty( )
   {
      return currentSize == 0;
   }

   /*
      Test if the priority queue is logically full.
   */
   public boolean isFull( )
   {
      return currentSize == capacity( );
   }

   /*
     Make the priority queue logically empty.
   */
   public void makeEmpty( )
   {
      currentSize = 0;
      for( int i = 0; i < theTrees.length; i++ )
         theTrees[ i ] = null;
   }


   static final int MAX_TREES = 14;

   int currentSize;            // # items in priority queue
   BinomialNode [ ] theTrees;  // An array of tree roots
    

   /*
      Return the capacity.
   */
   int capacity( )
   {
      return ( 1 << theTrees.length ) - 1;
   }

}

/*
  Exception class for access in full containers
  such as stacks, queues, and priority queues.
*/
class Overflow extends Exception
{
}