/**
 * CS151 Fall 2007 Lab 13 Solution.<BR>
 * Exercises from the textbook for practicing recursion, specifically "tail" recursion.
 * 
 * @author Scott Russell 
 * @version 12/05/2007
 */
public class Sentence
{
    // the text of the sentence
    private String phrase;
    
    /**
     * Simple constructor that makes a Sentence object from the given string.
     * @param text the text of the sentence
     */
    public Sentence(String text)
    {
        phrase = text;
    }
    
    /**
     * Returns a String representation of this object.
     */
    public String toString()
    {
        return phrase;
    }
    
    /**
     * Exercise P13.1: Reverses the contents of the this sentence.
     */
    public void reverse()
    {
        if (phrase != null && phrase.length() > 0)
        {
            // make a new sentence with all but first character of this sentence object
            // recall that substring with a single position parameter gives the substring from that 
            // position to the end of the string
            Sentence tail = new Sentence(this.toString().substring(1));
            
            // reverse the new sentence just created;
            tail.reverse();
            
            //change this sentence to be the reversed tail followed by this sentence's first letter
            phrase = tail.toString() + this.toString().substring(0,1);
        }
    }
    
    /**
     * Exercise P13.2: Reverses the contents of the this sentence.  
     * Note that this version requires less 
     * extra space for storing parts of the original Sentence.  At any one time there is only a single 
     * Sentence object.  When working with objects that require a lot of memory this can be an important
     * consideration.
     */
    public void reverse2()
    {
        // use the recursive helper method of same name on the entire sentence
        reverse2(0);
    }
    
    // recursive helper method for implementing reverse without creating new sentences
    // sorts the substring of the sentence from position start to end (inclusive)
    private void reverse2(int start)
    {
        // Check to see that the indexes are correct an then make the problem a little simpler
        // by sorting a substring with the first character removed
        if (phrase != null && phrase.length() > start)
        {
            // reverse the smaller substring
            this.reverse2(start+1);
            
            /*
             * leave everything before start unchanged while swaping character in position start and 
             * the substring just sorted substring beginning at position start+1
             */
            phrase = phrase.substring(0,start) + phrase.substring(start+1, phrase.length()) + phrase.charAt(start);
      }
    }
    
    /**
     * Checks whether the sentence contains the exact specified text, i.e. it's case sensitive.
     * @param text what to search the sentence for
     * @return true if text is found in the sentence and false otherwise
     */
    public boolean find(String text)
    {
        if (phrase != null)
            // call the recurisive helper method on the entire sentence
            return find(text, 0);
        else
            return false;
    }
    
    // this is a recursive helper method for find that takes the String to find, and also the position in the 
    // sentence to begin looking
    private boolean find(String text, int start)
    {
        /* 
         * Note that the first two options are base or bottom cases necessary for the recursion to stop
         * In this case we probably would get an ArrayIndexOutOfBounds exception before a stack overflow
         */
             
        // is the substring of sentence long enough to contain text?
        if (phrase == null || text == null || phrase.length() - start < text.length())
            return false;
            
        // if long enough, does the substring start with the text to find?
        else if (phrase.substring(start, start + text.length()).equals(text))
            return true;
            
        else
            // if not, try to find text in the substring starting one position to the right (from start+1)
            return find(text, start + 1);
    }
  
    /**
     * Finds the position of the first occurence of the exact specified text in this sentence.
     * @param text what to search the sentence for
     * @return the position of first occurrence of text found or -1 if not found
     */
    public int indexOf(String text)
    {
        if (phrase != null)
            return indexOf(text, 0);
        else
            return -1;
    }
    
    // this is a recursive helper method for find that takes the String to find, and also the start which
    // tells how far from the beginning of the sentence the current substring is
    private int indexOf(String text, int start)
    {
        /* 
         * Note that the first two options are base cases to stop the recursion.
         * In this case we probably would get an ArrayIndexOutOfBounds exception before a stack overflow
         */
             
        // is the substring from start to the end of the sentence long enough to contain text?
        if (phrase == null || text == null || phrase.length() - start < text.length())
            return -1;

        // if long enough, does the substring start with the text to find?
        else if (phrase.substring(start, start + text.length()).equals(text))
            return start;
            
        else
            // if not, try to find text in the substring starting one position to the right (from start+1)
            return indexOf(text, start + 1);  
    }
}