// Sorter.java
// $Id: Sorter.java,v 1.2 1997/01/08 17:38:22 abaird Exp $
// (c) COPYRIGHT MIT and INRIA, 1996.
// Please first read the full copyright statement in file COPYRIGHT.html

package w3c.tools.sorter ;

import java.util.* ;

/**
 * This class implements a bunch of different ways of sorting things.
 */

public class Sorter {

    /**
     * Insert a String into a vector, maintaing the order.
     * @param key The string to insert.
     * @param into The target sorted vector.
     */

    static void orderedStringInsert(String key, Vector into) {
	int lo  = 0 ;
	int hi  = into.size() - 1 ;
	int idx = -1 ;
	String item = null ;
	int cmp = 0 ;

	if ( hi >= lo ) {
	    while ((hi - lo) > 1) {
		idx  = (hi-lo) / 2 + lo ;
		item = (String) into.elementAt(idx) ;
		cmp  = item.compareTo(key) ;
		if ( cmp == 0 ) {
		    return ;
		} else if ( cmp < 0 ) {
		    lo = idx ;
		} else if ( cmp > 0 ) {
		    hi = idx ;
		}
	    }
	    switch (hi-lo) {
	      case 0:
		item = (String) into.elementAt(hi) ;
		if (item.equals(key))
		    return ;
		idx = (item.compareTo(key) < 0) ? hi + 1 : hi ;
		break ;
	      case 1:
		String loitem = (String) into.elementAt(lo) ;
		String hiitem = (String) into.elementAt(hi) ;
		if ( loitem.equals(key) )
		    return ;
		if ( hiitem.equals(key) )
		    return ;
		if ( key.compareTo(loitem) < 0 ) {
		    idx = lo ;
		} else if ( key.compareTo(hiitem) < 0 ) {
		    idx = hi ;
		} else {
		    idx = hi + 1 ;
		}
		break ;
	      default:
		throw new RuntimeException ("implementation bug.") ;
	    }
	}
	// Add this key to the vector:
	if ( idx < 0 ) 
	    idx = 0 ;
	into.insertElementAt(key, idx) ;
	return ;
    }

    /**
     * Quick sort the given chunk of the array in place.
     * @param array The array to sort.
     * @param lo0 The low bound of the chunk of the array to sort.
     * @param hi0 The high bound of the array to sort.
     */

    static void quickSortStringArray(String array[], int lo0, int hi0) {
	int lo = lo0 ;
	int hi = hi0 ;
	String mid = null ;

	if ( hi0 > lo0 ) {
	    mid = array[(lo0+hi0)/2] ;
	    while (lo <= hi) {
		while ((lo < hi0) && (array[lo].compareTo(mid) < 0)) 
		    ++lo ;
		while ((hi > lo0) && (array[hi].compareTo(mid) > 0))
		    --hi ;
		if ( lo <= hi ) {
		    String tmp = array[lo] ;
		    array[lo]  = array[hi] ;
		    array[hi]  = tmp ;
		    ++lo ;
		    --hi ;
		}
	    }
	    if ( lo0 < hi )
		quickSortStringArray(array, lo0, hi) ;
	    if ( lo < hi0 )
		quickSortStringArray(array, lo, hi0) ;
	}
    }
     
    /**
     * Get the keys of this hashtable, sorted.
     * @param h The hashtable whose String keys are wanted.
     */

    public static Vector sortStringKeys(Hashtable h) {
	return sortStringEnumeration(h.keys()) ;
    }

    /**
     * Sort the given String enumeration.
     * @return A sorted vector of String.
     */

    public static Vector sortStringEnumeration(Enumeration enum) {
	Vector sorted = new Vector() ;
	while ( enum.hasMoreElements() ) 
	    orderedStringInsert((String) enum.nextElement(), sorted) ;
	sorted.trimToSize();
	return sorted ;
    }


    /**
     * Get the keys of this hashtable, sorted.
     * @param h The hashtable whose keys.toString() are wanted.
     */

    public static Vector sortObjectKeys(Hashtable h) {
	return sortObjectEnumeration(h.keys()) ;
    }

    /**
     * Sort the given enumeration whose elements have .toString() method.
     * @return A sorted vector of the original objects.
     */

    public static Vector sortObjectEnumeration(Enumeration enum) {
      Vector sorted = new Vector() ;
      Hashtable mapper = new Hashtable();
      while ( enum.hasMoreElements() ) {
	Object next = enum.nextElement();
	mapper.put(next.toString(), next);
	orderedStringInsert(next.toString(), sorted) ;
      }
      sorted.trimToSize();
      Vector tmp = new Vector();
      for (int i=0; i<sorted.size(); i++) 
	tmp.addElement(mapper.get(sorted.elementAt(i)));
      return tmp ;
    }

    /**
     * Sort the given String array in place.
     * @param array The array of String to sort.
     * @param inplace Sort the array in place if <strong>true</strong>, 
     *    allocate a fresh array for the result otherwise.
     * @return The same array, with string sorted.
     */

    public static String[] sortStringArray(String array[], boolean inplace) {
	String tosort[] = array ;
	if ( ! inplace ) {
	    tosort = new String[array.length] ;
	    System.arraycopy(array, 0, tosort, 0, array.length) ;
	}
	quickSortStringArray(tosort, 0, tosort.length-1) ;
	return tosort ;
    }

}
