import java.io.*;
import java.util.*;
 
public class PalindromeState
{
  // this version does not init
  public PalindromeState(boolean noinit)
  {
  }

  public PalindromeState()
       throws FileNotFoundException
  {
    Init("dict", 80282, false);
    int w = rnd.nextInt();
    w =  w % wt.length();
    sb.addWord(wt.getWord(w), sb.MAX / 2);
  }

  public PalindromeState(String s)
       throws FileNotFoundException
  {
    Init("dict", 80282, false);
    sb.addWord(s, sb.MAX / 2);
  }

  public void Init(String wtName, int size, boolean trace)
       throws FileNotFoundException
  {
    this.trace = trace;

    wt = new WordTable(wtName, size);
    wtReverse = new WordTable(wtName + ".reverse", size);

    sb = new SandBox();
    rnd = new RandomRange();
  }

  public void print()
  {
    sb.print();
  }

  public boolean GoalTest()
  {
    return (sb.Complete() || sb.CompleteReverse());
  }

  public Vector Expand()
  {
    return Expand(MAX_BRANCHES);
  }

  //  ALGORITHM:
  //
  //  if there is an island, must fill
  //  when do island, call largest-suffix or largest-prefix
  //      if subsequent failure, call largest on a smaller part...
  //
  //  when do a prefix or suffix on edge, check if is-complete-word
  //
  public Vector Expand(int branchFactor)
  {
    Vacancy v;    // part that has to be filled with real word(s)
    Vector succ = new Vector();  // successors

    // 6 conditions: island, right edge, left edges; reverses thereof

    if (trace)
      sb.print();

    // if (sb.numwords() > 5) {
    //  return succ;
    // }
    // else 

    if ((v = sb.Island()).length() > 0) {
      for (int i=v.length(); i > 0; i--) {
	String segment = v.content().substring(0,i);
	String toadd = wt.LargestPrefix(segment);
	if (toadd.length() > 0) {
	  PalindromeState newP = copy();
	  newP.getSB().addWord(toadd, v.loc());
	  succ.addElement(newP);

	}
	i = toadd.length();//next,look at islandpart one smaller than curr pref
      }
      return succ;
    }
    else if ((v = sb.IslandReverse()).length() > 0) {
      for (int i=v.length(); i > 0; i--) {
	String segment = v.content().substring(0,i);
	String toadd = wt.LargestPrefix(segment);
	if (toadd.length() > 0) {
	  PalindromeState newP = copy();
	  newP.getSB().addWordReverse(toadd, v.loc());
	  succ.addElement(newP);

	}
	i = toadd.length();//next,look at islandpart one smaller than curr pref
      }
      return succ;
    }

    // Future: randomize order of the following 4 options?
    //   also, randomize order of prefix lengths?

    else {

    if ((v = sb.RightEdge()).length() > 0) {

      if (v.length() > 1) {  // test edgelet (ie edge witout last letter)
	  String edgelet = v.content().substring(0, v.length()-1);
	  if (wt.isWord(edgelet)) {
	      // the edgelet is an entire word -- try that one first
	      PalindromeState newP = copy();
	      newP.getSB().addWord(edgelet, v.loc());
	      succ.addElement(newP);

	  }
      }
      
      // String toadd1 = wt.LargestPrefix(v.content())
      // if (v.content()
      for (int i=0; i < v.length(); i++) {
	String segment = v.content().substring(i);
	Range r = wt.SearchPrefix(segment);
	if (!r.empty()) {
	  if (i == 0 && wt.getWord(r.begin()).length() == v.length()) {
	      // the edge is an entire word -- try that one first
	      PalindromeState newP = copy();
	      newP.getSB().addWord(segment, v.loc());
	      succ.addElement(newP);

	      r.shrinkFront();  // eliminate that option in the following loop
	  }
	  // for (int j=0; j < ((r.size() / 20) + 1); j++) {
	  for (int j=0; j < branchFactor && j < r.size(); j++) {
	    String toadd = wt.getWord(rnd.range(r));

	    PalindromeState newP = copy();
	    newP.getSB().addWord(toadd, v.loc()+i);
	    succ.addElement(newP);

	  }
	}
      }
    }
    else if ((v = sb.LeftEdge()).length() > 0) {

      if (v.length() > 1) {  // test edgelet (ie edge without first letter)
	  String edgelet = v.content().substring(1);
	  if (wt.isWord(edgelet)) {
	      // the edgelet is an entire word -- try that one first

	      PalindromeState newP = copy();
	      newP.getSB().addWord(edgelet, v.loc() - edgelet.length() + 1);
	      succ.addElement(newP);

	  }
      }
      
      for (int i=0; i < v.length(); i++) {
	String segment = new String(new StringBuffer(v.content()).reverse());
	segment = segment.substring(i);
	Range r = wtReverse.SearchPrefix(segment);
	if (!r.empty()) {
	  if (i == 0 && wtReverse.getWord(r.begin()).length() == v.length()) {
	      // the edge is an entire word -- try that one first

	      PalindromeState newP = copy();
	      newP.getSB().addWord(v.content(), v.loc() - v.length() + 1);
	      succ.addElement(newP);

	      r.shrinkFront();  // eliminate that option in the following loop
	  }
	  for (int j=0; j < branchFactor && j < r.size(); j++) {
	    String toadd = wtReverse.getWord(rnd.range(r));
	    toadd = new String(new StringBuffer(toadd).reverse());

	    PalindromeState newP = copy();
	    newP.getSB().addWord(toadd, v.loc() - i - toadd.length() + 1);
	    succ.addElement(newP);

	  }
	}
      }
    }
    // this is actually going left, backwards, but on the right if you 
    // turn it upside down :>
    else if ((v = sb.RightEdgeReverse()).length() > 0) {

      if (v.length() > 1) {  // test edgelet (ie edge without first letter)
	  String edgelet = v.content().substring(0,v.length()-1);
	  if (wt.isWord(edgelet)) {
	      // the edgelet is an entire word -- try that one first
	      PalindromeState newP = copy();
	      newP.getSB().addWordReverse(edgelet, v.loc());
	      succ.addElement(newP);

	  }
      }
      
      for (int i=0; i < v.length(); i++) {
	String segment = v.content().substring(i);
	Range r = wt.SearchPrefix(segment);
	if (!r.empty()) {
	  if (i == 0 && wt.getWord(r.begin()).length() == v.length()) {
	      // the edge is an entire word -- try that one first

	      PalindromeState newP = copy();
	      newP.getSB().addWordReverse(segment, v.loc());
	      succ.addElement(newP);

	      r.shrinkFront();  // eliminate that option in the following loop
	  }
	  for (int j=0; j < branchFactor && j < r.size(); j++) {
	    String toadd = wt.getWord(rnd.range(r));

	    PalindromeState newP = copy();
	    newP.getSB().addWordReverse(toadd, v.loc() - i);
	    succ.addElement(newP);

	  }
	}
      }
    }
    else if ((v = sb.LeftEdgeReverse()).length() > 0) {

      if (v.length() > 1) {  // test edgelet (ie edge without first letter)
	  String edgelet = v.content().substring(1);
	  if (wt.isWord(edgelet)) {
	      // the edgelet is an entire word -- try that one first

	      PalindromeState newP = copy();
	      newP.getSB().addWordReverse(edgelet, v.loc() + edgelet.length() - 1);
	      succ.addElement(newP);

	  }
      }
      
      for (int i=0; i < v.length(); i++) {
	String segment = new String(new StringBuffer(v.content()).reverse());
	segment = segment.substring(i);
	Range r = wtReverse.SearchPrefix(segment);
	if (!r.empty()) {
	  if (i == 0 && wtReverse.getWord(r.begin()).length() == v.length()) {
	      // the edge is an entire word -- try that one first

	      PalindromeState newP = copy();
	      newP.getSB().addWordReverse(v.content(), v.loc() + v.length() - 1);
	      succ.addElement(newP);

	      r.shrinkFront();  // eliminate that option in the following loop
	  }
	  for (int j=0; j < branchFactor && j < r.size(); j++) {
	    String toadd = wtReverse.getWord(rnd.range(r));
	    toadd = new String(new StringBuffer(toadd).reverse());

	    PalindromeState newP = copy();
	    newP.getSB().addWordReverse(toadd, v.loc() + i + toadd.length() - 1);
	    succ.addElement(newP);

	  }
	}
      }
    }
    }

    return succ;
  }

  SandBox getSB()
  {
    return sb;
  }

  PalindromeState copy()
  {
    PalindromeState dup = new PalindromeState(true);

    dup.sb = sb.copy();
    dup.wt = wt;
    dup.wtReverse = wtReverse;
    dup.rnd = rnd;
    dup.trace = trace;

    return dup;
  }

  // The following 4 functions for making a heuristic operate
  // over the entire palindrome, not just the sandbox's half-string

  int length()
  {
    return 2 * sb.length();
  }

  int nWords()
  {
    return sb.numwords();
  }

  char getLetter(int i)
  {
    int l = sb.length();
    if (i >= l) {
      i = i-l;
      return sb.getLetter(l - i - 1);
    }
    else
      return sb.getLetter(i);
  }

  boolean used(int i)
  {
    int l = sb.length();
    if (i >= l) {
      i = i-l;
      return sb.usedReverse(l - i - 1);
    }
    else {
      return sb.used(i);
    }
  }

  public static void main(String[] args) throws FileNotFoundException
  {
    PalindromeState p;
    boolean trace = false;

    p = new PalindromeState();
    Vector v = p.Expand();
    System.out.println("size " + v.size());
    for (int i=0; i < v.size(); i++) {
      PalindromeState pp = (PalindromeState) v.elementAt(i);
      pp.print();
    }
    
    PalindromeState p1 = (PalindromeState) v.firstElement();
    System.out.println(p1.nWords() + " words " + p1.length() + " letters");
    p1.print();
    for (int i=0; i < p1.length(); i++) {
      System.out.print(p1.getLetter(i));
    }
    System.out.println("");
    for (int i=0; i < p1.length(); i++) {
      if (p1.used(i))
	System.out.print("Y");
      else
	System.out.print(" ");
    }
    System.out.println("");
  }

  private SandBox sb;
  private WordTable wt;
  private WordTable wtReverse;
  private RandomRange rnd;
  private boolean trace;

  final static int MAX_BRANCHES = 5;
}