/*
 * StringWordOrganizer.java
 *
 * Created on October 15, 2005, 1:37 PM
 */

package Current.search;

import java.lang.String;
import java.lang.StringBuffer;
import java.util.Comparator;
import java.util.TreeSet;

/**
 * This class holds a set of string and orders them canonically.
 * In particular, it will not hold duplicates.
 *<br><br>
 * This class is essentially a wrapper for a TreeSet for handling strings.
 * I have used naming conventions from the SortedSet class.
 *<br><br>
 * It also comes with some utility function for organizing Strings canonically.
 *
 * @see java.lang.String
 * @see java.lang.TreeSet
 * @see java.lang.SortedSet
 * @author  pat
 */
public class StringWordOrganizer implements Comparator {
    TreeSet ts;
    /** Creates a new instance of StringWordOrganizer */
    public StringWordOrganizer() {
        ts=new TreeSet(this);
    }
    
    /** Compare two strings first by length and second lexigraphically.
     * @return -1 if the first is less than the second, 0 if they are equal
     * and 1 if the  first is greater
     **/
    public int compare(Object obj, Object obj1) {
        if ( ((String)obj).length()<((String)obj1).length())
            return -1;
        if ( ((String)obj).length()>((String)obj1).length())
            return 1;
        return ((String)obj).compareTo((String)obj1);
    }
    
    /** Returns a canonical version of the string. Returns null if the
     * string is a power of an even word. */
    public static String canonicalize(String str) {
        int l=str.length();
        StringBuffer ret=new StringBuffer(l);
        int i,j;
        
        /* find the least lexigraphical forward ordered word */
        int best=0;
        for (i=1; i<l; i++) {
            for (j=0;(j<l)&&(str.charAt((best+j)%l)==str.charAt((i+j)%l));
            j++) {}
            if ( (j!=l) && (str.charAt((i+j)%l)<str.charAt((best+j)%l)) ) {
                best=i;
            }
            if (j==l) {
                // there are two equal words.
                if ((i-best)%2==0) {
                    // two equal even words--- it must be a power of an even word
                    return null;
                }
            }
        }
        str=str.substring(best)+str.substring(0,best);
        best=0;
        
        /* find the least lexigraphical backward ordered word */
        int best2=0;
        for (i=1; i<l; i++) {
            for (j=l;(j>0)&&(str.charAt((best2+j)%l)==str.charAt((i+j)%l));
            j--) {}
            if ( (j!=l) && (str.charAt((i+j)%l)<str.charAt((best2+j)%l)) ) {
                best2=i;
            }
        }
        
        /* copare the two */
        for (j=0; (j<l)&&(str.charAt((best+j)%l)==str.charAt((best2+l-j)%l));
        j++) {
            ret.append(str.charAt((best+j)%l));
        }
        if (j==l) {
            // we have a palindrome !
            // these are the possible starting locations:
            ret.delete(0, ret.length());
            int p1=((best+best2)/2)%l,p2=(p1+l/2)%l;
            for (j=0;(j<l)&&(str.charAt((best+j)%l)==str.charAt((i+j)%l));
            j++) {
                ret.append(str.charAt((p1+j)%l));
            }
            if (j!=l) {
                // Otherwise Odd Square Palindrome!
                if (str.charAt((best+j)%l)<str.charAt((i+j)%l)) {
                    while (j<l) {
                        ret.append(str.charAt((p1+j)%l));
                        j++;
                    }
                } else {
                    while (j<l) {
                        ret.append(str.charAt((p2+j)%l));
                        j++;
                    }
                }
            }
        } else if (str.charAt((best+j)%l)<str.charAt((best2+l-j)%l)) {
            // forward is the best
            while (j<l) {
                ret.append(str.charAt((best+j)%l));
                j++;
            }
        } else {
            // backward is the best
            while (j<l) {
                ret.append(str.charAt((best2+l-j)%l));
                j++;
            }
        }
        return ret.toString();
    }
    
    /** Add a string to the set. If not in canonical order, it will be
     * canonicalized before being placed in the set.
     * @see java.util.SortedSet#add */
    public boolean add(String str) {
        String temp=canonicalize(str);
        if (temp!=null)
            return ts.add(temp);
        return false;             
    }
    
    /** */
    public void clear() {
        ts.clear();
    }
    
    /** Returns true iff str is in the set */
    public boolean contains(String str) {
        return ts.contains(str);
    }
    
    /** return the first string  in the list */
    public String first() {
        return (String)ts.first();
    }
    
    /* return true if empty */
    public boolean isEmpty() {
        return ts.isEmpty();
    }
    
    
    /** The last String */
    public String last() {
        return (String)ts.last();
    }
    
    /** Remove a string */
    public boolean remove(String str) {
        return ts.remove(str);
    }
    
    /** Number of strings held */
    public int size() {
        return ts.size();
    }
    
    /** return an array with all the elements stored in the set
     * @see java.util.SortedSet#toArray()
     */
    public String[] toArray(){
        return toArray(new String[ts.size()]);
    }
    
    /** return an array with all the elements stored in the set
     * @see java.util.SortedSet#toArray(Object[])
     */
    public String[] toArray(String[] a){
        ts.toArray(a);
        return a;
    }
}