You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2010/05/04 01:23:58 UTC

svn commit: r940671 [2/3] - in /lucene/dev/trunk: lucene/ lucene/src/java/org/apache/lucene/search/ lucene/src/java/org/apache/lucene/util/ lucene/src/java/org/apache/lucene/util/automaton/ lucene/src/test/org/apache/lucene/search/ lucene/src/test/org/...

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/BasicOperations.java Mon May  3 23:23:57 2010
@@ -29,15 +29,22 @@
 
 package org.apache.lucene.util.automaton;
 
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.UnicodeUtil;
+import org.apache.lucene.util.RamUsageEstimator;
+
 import java.util.ArrayList;
 import java.util.BitSet;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.IdentityHashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.Random;
 
 /**
  * Basic automata operations.
@@ -73,7 +80,8 @@ final public class BasicOperations {
       s.addEpsilon(a2.initial);
     }
     a1.deterministic = deterministic;
-    a1.clearHashCode();
+    //a1.clearHashCode();
+    a1.clearNumberedStates();
     a1.checkMinimizeAlways();
     return a1;
   }
@@ -125,7 +133,8 @@ final public class BasicOperations {
           ac = ns;
         }
       b.deterministic = false;
-      b.clearHashCode();
+      //b.clearHashCode();
+      b.clearNumberedStates();
       b.checkMinimizeAlways();
       return b;
     }
@@ -144,7 +153,8 @@ final public class BasicOperations {
     s.accept = true;
     a.initial = s;
     a.deterministic = false;
-    a.clearHashCode();
+    //a.clearHashCode();
+    a.clearNumberedStates();
     a.checkMinimizeAlways();
     return a;
   }
@@ -165,7 +175,8 @@ final public class BasicOperations {
       p.addEpsilon(s);
     a.initial = s;
     a.deterministic = false;
-    a.clearHashCode();
+    //a.clearHashCode();
+    a.clearNumberedStates();
     a.checkMinimizeAlways();
     return a;
   }
@@ -217,7 +228,8 @@ final public class BasicOperations {
       for (State p : b.getAcceptStates())
         p.addEpsilon(d.initial);
       b.deterministic = false;
-      b.clearHashCode();
+      //b.clearHashCode();
+      b.clearNumberedStates();
       b.checkMinimizeAlways();
     }
     return b;
@@ -233,7 +245,7 @@ final public class BasicOperations {
     a = a.cloneExpandedIfRequired();
     a.determinize();
     a.totalize();
-    for (State p : a.getStates())
+    for (State p : a.getNumberedStates())
       p.accept = !p.accept;
     a.removeDeadTransitions();
     return a;
@@ -274,10 +286,8 @@ final public class BasicOperations {
       else return BasicAutomata.makeEmpty();
     }
     if (a1 == a2) return a1.cloneIfRequired();
-    Transition[][] transitions1 = Automaton
-        .getSortedTransitions(a1.getStates());
-    Transition[][] transitions2 = Automaton
-        .getSortedTransitions(a2.getStates());
+    Transition[][] transitions1 = a1.getSortedTransitions();
+    Transition[][] transitions2 = a2.getSortedTransitions();
     Automaton c = new Automaton();
     LinkedList<StatePair> worklist = new LinkedList<StatePair>();
     HashMap<StatePair,StatePair> newstates = new HashMap<StatePair,StatePair>();
@@ -302,9 +312,9 @@ final public class BasicOperations {
               newstates.put(q, q);
               r = q;
             }
-            char min = t1[n1].min > t2[n2].min ? t1[n1].min : t2[n2].min;
-            char max = t1[n1].max < t2[n2].max ? t1[n1].max : t2[n2].max;
-            p.s.transitions.add(new Transition(min, max, r.s));
+            int min = t1[n1].min > t2[n2].min ? t1[n1].min : t2[n2].min;
+            int max = t1[n1].max < t2[n2].max ? t1[n1].max : t2[n2].max;
+            p.s.addTransition(new Transition(min, max, r.s));
           }
       }
     }
@@ -313,6 +323,24 @@ final public class BasicOperations {
     c.checkMinimizeAlways();
     return c;
   }
+
+  /** Returns true if these two auotomata accept exactly the
+   *  same language.  This is a costly computation!  Note
+   *  also that a1 and a2 will be determinized as a side
+   *  effect. */
+  public static boolean sameLanguage(Automaton a1, Automaton a2) {
+    if (a1 == a2) {
+      return true;
+    }
+    if (a1.isSingleton() && a2.isSingleton()) {
+      return a1.singleton.equals(a2.singleton);
+    } else if (a1.isSingleton()) {
+      // subsetOf is faster if the first automaton is a singleton
+      return subsetOf(a1, a2) && subsetOf(a2, a1);
+    } else {
+      return subsetOf(a2, a1) && subsetOf(a1, a2);
+    }
+  }
   
   /**
    * Returns true if the language of <code>a1</code> is a subset of the language
@@ -328,10 +356,8 @@ final public class BasicOperations {
       return BasicOperations.run(a2, a1.singleton);
     }
     a2.determinize();
-    Transition[][] transitions1 = Automaton
-        .getSortedTransitions(a1.getStates());
-    Transition[][] transitions2 = Automaton
-        .getSortedTransitions(a2.getStates());
+    Transition[][] transitions1 = a1.getSortedTransitions();
+    Transition[][] transitions2 = a2.getSortedTransitions();
     LinkedList<StatePair> worklist = new LinkedList<StatePair>();
     HashSet<StatePair> visited = new HashSet<StatePair>();
     StatePair p = new StatePair(a1.initial, a2.initial);
@@ -339,19 +365,24 @@ final public class BasicOperations {
     visited.add(p);
     while (worklist.size() > 0) {
       p = worklist.removeFirst();
-      if (p.s1.accept && !p.s2.accept) return false;
+      if (p.s1.accept && !p.s2.accept) {
+        return false;
+      }
       Transition[] t1 = transitions1[p.s1.number];
       Transition[] t2 = transitions2[p.s2.number];
       for (int n1 = 0, b2 = 0; n1 < t1.length; n1++) {
         while (b2 < t2.length && t2[b2].max < t1[n1].min)
           b2++;
         int min1 = t1[n1].min, max1 = t1[n1].max;
+
         for (int n2 = b2; n2 < t2.length && t1[n1].max >= t2[n2].min; n2++) {
-          if (t2[n2].min > min1) return false;
-          if (t2[n2].max < Character.MAX_VALUE) min1 = t2[n2].max + 1;
+          if (t2[n2].min > min1) {
+            return false;
+          }
+          if (t2[n2].max < Character.MAX_CODE_POINT) min1 = t2[n2].max + 1;
           else {
-            min1 = Character.MAX_VALUE;
-            max1 = Character.MIN_VALUE;
+            min1 = Character.MAX_CODE_POINT;
+            max1 = Character.MIN_CODE_POINT;
           }
           StatePair q = new StatePair(t1[n1].to, t2[n2].to);
           if (!visited.contains(q)) {
@@ -359,7 +390,9 @@ final public class BasicOperations {
             visited.add(q);
           }
         }
-        if (min1 <= max1) return false;
+        if (min1 <= max1) {
+          return false;
+        }
       }
     }
     return true;
@@ -387,7 +420,8 @@ final public class BasicOperations {
     s.addEpsilon(a2.initial);
     a1.initial = s;
     a1.deterministic = false;
-    a1.clearHashCode();
+    //a1.clearHashCode();
+    a1.clearNumberedStates();
     a1.checkMinimizeAlways();
     return a1;
   }
@@ -414,64 +448,257 @@ final public class BasicOperations {
     Automaton a = new Automaton();
     a.initial = s;
     a.deterministic = false;
-    a.clearHashCode();
+    //a.clearHashCode();
+    a.clearNumberedStates();
     a.checkMinimizeAlways();
     return a;
   }
-  
+
+  // Simple custom ArrayList<Transition>
+  private final static class TransitionList {
+    Transition[] transitions = new Transition[2];
+    int count;
+
+    public void add(Transition t) {
+      if (transitions.length == count) {
+        Transition[] newArray = new Transition[ArrayUtil.oversize(1+count, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+        System.arraycopy(transitions, 0, newArray, 0, count);
+        transitions = newArray;
+      }
+      transitions[count++] = t;
+    }
+  }
+
+  // Holds all transitions that start on this int point, or
+  // end at this point-1
+  private final static class PointTransitions implements Comparable<PointTransitions> {
+    int point;
+    final TransitionList ends = new TransitionList();
+    final TransitionList starts = new TransitionList();
+    public int compareTo(PointTransitions other) {
+      return point - other.point;
+    }
+
+    public void reset(int point) {
+      this.point = point;
+      ends.count = 0;
+      starts.count = 0;
+    }
+
+    public boolean equals(Object other) {
+      return ((PointTransitions) other).point == point;
+    }
+
+    public int hashCode() {
+      return point;
+    }
+  }
+
+  private final static class PointTransitionSet {
+    int count;
+    PointTransitions[] points = new PointTransitions[5];
+
+    private final static int HASHMAP_CUTOVER = 30;
+    private final HashMap<Integer,PointTransitions> map = new HashMap<Integer,PointTransitions>();
+    private boolean useHash = false;
+
+    private PointTransitions next(int point) {
+      // 1st time we are seeing this point
+      if (count == points.length) {
+        final PointTransitions[] newArray = new PointTransitions[ArrayUtil.oversize(1+count, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+        System.arraycopy(points, 0, newArray, 0, count);
+        points = newArray;
+      }
+      PointTransitions points0 = points[count];
+      if (points0 == null) {
+        points0 = points[count] = new PointTransitions();
+      }
+      points0.reset(point);
+      count++;
+      return points0;
+    }
+
+    private PointTransitions find(int point) {
+      if (useHash) {
+        final Integer pi = point;
+        PointTransitions p = map.get(pi);
+        if (p == null) {
+          p = next(point);
+          map.put(pi, p);
+        }
+        return p;
+      } else {
+        for(int i=0;i<count;i++) {
+          if (points[i].point == point) {
+            return points[i];
+          }
+        }
+
+        final PointTransitions p = next(point);
+        if (count == HASHMAP_CUTOVER) {
+          // switch to HashMap on the fly
+          assert map.size() == 0;
+          for(int i=0;i<count;i++) {
+            map.put(points[i].point, points[i]);
+          }
+          useHash = true;
+        }
+        return p;
+      }
+    }
+
+    public void reset() {
+      if (useHash) {
+        map.clear();
+        useHash = false;
+      }
+      count = 0;
+    }
+
+    public void sort() {
+      if (count > 1) {
+        Arrays.sort(points, 0, count);
+      }
+    }
+
+    public void add(Transition t) {
+      find(t.min).starts.add(t);
+      find(1+t.max).ends.add(t);
+    }
+
+    public String toString() {
+      StringBuilder s = new StringBuilder();
+      for(int i=0;i<count;i++) {
+        if (i > 0) {
+          s.append(' ');
+        }
+        s.append(points[i].point).append(':').append(points[i].starts.count).append(',').append(points[i].ends.count);
+      }
+      return s.toString();
+    }
+  }
+
   /**
    * Determinizes the given automaton.
    * <p>
-   * Complexity: exponential in number of states.
+   * Worst case complexity: exponential in number of states.
    */
-  public static void determinize(Automaton a) {
-    if (a.deterministic || a.isSingleton()) return;
-    Set<State> initialset = new HashSet<State>();
-    initialset.add(a.initial);
-    determinize(a, initialset);
-  }
-  
-  /**
-   * Determinizes the given automaton using the given set of initial states.
-   */
-  static void determinize(Automaton a, Set<State> initialset) {
-    char[] points = a.getStartPoints();
+  static void determinize(Automaton a) {
+    if (a.deterministic || a.isSingleton()) {
+      return;
+    }
+
+    final State[] allStates = a.getNumberedStates();
+
     // subset construction
-    Map<Set<State>,Set<State>> sets = new HashMap<Set<State>,Set<State>>();
-    LinkedList<Set<State>> worklist = new LinkedList<Set<State>>();
-    Map<Set<State>,State> newstate = new HashMap<Set<State>,State>();
-    sets.put(initialset, initialset);
-    worklist.add(initialset);
+    final boolean initAccept = a.initial.accept;
+    final int initNumber = a.initial.number;
     a.initial = new State();
+    SortedIntSet.FrozenIntSet initialset = new SortedIntSet.FrozenIntSet(initNumber, a.initial);
+
+    LinkedList<SortedIntSet.FrozenIntSet> worklist = new LinkedList<SortedIntSet.FrozenIntSet>();
+    Map<SortedIntSet.FrozenIntSet,State> newstate = new HashMap<SortedIntSet.FrozenIntSet,State>();
+
+    worklist.add(initialset);
+
+    a.initial.accept = initAccept;
     newstate.put(initialset, a.initial);
+
+    int newStateUpto = 0;
+    State[] newStatesArray = new State[5];
+    newStatesArray[newStateUpto] = a.initial;
+    a.initial.number = newStateUpto;
+    newStateUpto++;
+
+    // like Set<Integer,PointTransitions>
+    final PointTransitionSet points = new PointTransitionSet();
+
+    // like SortedMap<Integer,Integer>
+    final SortedIntSet statesSet = new SortedIntSet(5);
+
     while (worklist.size() > 0) {
-      Set<State> s = worklist.removeFirst();
-      State r = newstate.get(s);
-      for (State q : s)
-        if (q.accept) {
-          r.accept = true;
-          break;
-        }
-      for (int n = 0; n < points.length; n++) {
-        Set<State> p = new HashSet<State>();
-        for (State q : s)
-          for (Transition t : q.transitions)
-            if (t.min <= points[n] && points[n] <= t.max) p.add(t.to);
-        if (!sets.containsKey(p)) {
-          sets.put(p, p);
-          worklist.add(p);
-          newstate.put(p, new State());
-        }
-        State q = newstate.get(p);
-        char min = points[n];
-        char max;
-        if (n + 1 < points.length) max = (char) (points[n + 1] - 1);
-        else max = Character.MAX_VALUE;
-        r.transitions.add(new Transition(min, max, q));
+      SortedIntSet.FrozenIntSet s = worklist.removeFirst();
+
+      // Collate all outgoing transitions by min/1+max:
+      for(int i=0;i<s.values.length;i++) {
+        final State s0 = allStates[s.values[i]];
+        for(int j=0;j<s0.numTransitions;j++) {
+          points.add(s0.transitionsArray[j]);
+        }
+      }
+
+      if (points.count == 0) {
+        // No outgoing transitions -- skip it
+        continue;
+      }
+
+      points.sort();
+
+      int lastPoint = -1;
+      int accCount = 0;
+
+      final State r = s.state;
+      for(int i=0;i<points.count;i++) {
+
+        final int point = points.points[i].point;
+
+        if (statesSet.upto > 0) {
+          assert lastPoint != -1;
+
+          statesSet.computeHash();
+          
+          State q = newstate.get(statesSet);
+          if (q == null) {
+            q = new State();
+            final SortedIntSet.FrozenIntSet p = statesSet.freeze(q);
+            worklist.add(p);
+            if (newStateUpto == newStatesArray.length) {
+              final State[] newArray = new State[ArrayUtil.oversize(1+newStateUpto, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+              System.arraycopy(newStatesArray, 0, newArray, 0, newStateUpto);
+              newStatesArray = newArray;
+            }
+            newStatesArray[newStateUpto] = q;
+            q.number = newStateUpto;
+            newStateUpto++;
+            q.accept = accCount > 0;
+            newstate.put(p, q);
+          } else {
+            assert (accCount > 0 ? true:false) == q.accept: "accCount=" + accCount + " vs existing accept=" + q.accept + " states=" + statesSet;
+          }
+
+          r.addTransition(new Transition(lastPoint, point-1, q));
+        }
+
+        // process transitions that end on this point
+        // (closes an overlapping interval)
+        Transition[] transitions = points.points[i].ends.transitions;
+        int limit = points.points[i].ends.count;
+        for(int j=0;j<limit;j++) {
+          final Transition t = transitions[j];
+          final Integer num = t.to.number;
+          statesSet.decr(num);
+          accCount -= t.to.accept ? 1:0;
+        }
+        points.points[i].ends.count = 0;
+
+        // process transitions that start on this point
+        // (opens a new interval)
+        transitions = points.points[i].starts.transitions;
+        limit = points.points[i].starts.count;
+        for(int j=0;j<limit;j++) {
+          final Transition t = transitions[j];
+          final Integer num = t.to.number;
+          statesSet.incr(num);
+          accCount += t.to.accept ? 1:0;
+        }
+        lastPoint = point;
+        points.points[i].starts.count = 0;
       }
+      points.reset();
+      assert statesSet.upto == 0: "upto=" + statesSet.upto;
     }
     a.deterministic = true;
-    a.removeDeadTransitions();
+    a.setNumberedStates(newStatesArray, newStateUpto);
   }
   
   /**
@@ -535,7 +762,8 @@ final public class BasicOperations {
     for (StatePair p : pairs)
       p.s1.addEpsilon(p.s2);
     a.deterministic = false;
-    a.clearHashCode();
+    //a.clearHashCode();
+    a.clearNumberedStates();
     a.checkMinimizeAlways();
   }
   
@@ -545,7 +773,7 @@ final public class BasicOperations {
    */
   public static boolean isEmptyString(Automaton a) {
     if (a.isSingleton()) return a.singleton.length() == 0;
-    else return a.initial.accept && a.initial.transitions.isEmpty();
+    else return a.initial.accept && a.initial.numTransitions() == 0;
   }
   
   /**
@@ -553,7 +781,7 @@ final public class BasicOperations {
    */
   public static boolean isEmpty(Automaton a) {
     if (a.isSingleton()) return false;
-    return !a.initial.accept && a.initial.transitions.isEmpty();
+    return !a.initial.accept && a.initial.numTransitions() == 0;
   }
   
   /**
@@ -561,10 +789,10 @@ final public class BasicOperations {
    */
   public static boolean isTotal(Automaton a) {
     if (a.isSingleton()) return false;
-    if (a.initial.accept && a.initial.transitions.size() == 1) {
-      Transition t = a.initial.transitions.iterator().next();
-      return t.to == a.initial && t.min == Character.MIN_VALUE
-          && t.max == Character.MAX_VALUE;
+    if (a.initial.accept && a.initial.numTransitions() == 1) {
+      Transition t = a.initial.getTransitions().iterator().next();
+      return t.to == a.initial && t.min == Character.MIN_CODE_POINT
+          && t.max == Character.MAX_CODE_POINT;
     }
     return false;
   }
@@ -580,24 +808,23 @@ final public class BasicOperations {
     if (a.isSingleton()) return s.equals(a.singleton);
     if (a.deterministic) {
       State p = a.initial;
-      for (int i = 0; i < s.length(); i++) {
-        State q = p.step(s.charAt(i));
+      for (int i = 0, cp = 0; i < s.length(); i += Character.charCount(cp)) {
+        State q = p.step(cp = s.codePointAt(i));
         if (q == null) return false;
         p = q;
       }
       return p.accept;
     } else {
-      Set<State> states = a.getStates();
-      Automaton.setStateNumbers(states);
+      State[] states = a.getNumberedStates();
       LinkedList<State> pp = new LinkedList<State>();
       LinkedList<State> pp_other = new LinkedList<State>();
-      BitSet bb = new BitSet(states.size());
-      BitSet bb_other = new BitSet(states.size());
+      BitSet bb = new BitSet(states.length);
+      BitSet bb_other = new BitSet(states.length);
       pp.add(a.initial);
       ArrayList<State> dest = new ArrayList<State>();
       boolean accept = a.initial.accept;
-      for (int i = 0; i < s.length(); i++) {
-        char c = s.charAt(i);
+      for (int i = 0, c = 0; i < s.length(); i += Character.charCount(c)) {
+        c = s.codePointAt(i);
         accept = false;
         pp_other.clear();
         bb_other.clear();
@@ -622,4 +849,149 @@ final public class BasicOperations {
       return accept;
     }
   }
+
+  // picks a random int code point that this transition
+  // accepts, avoiding the surrogates range since they are
+  // "defined" in UTF32.  Don't call this on a transition
+  // that only accepts UTF16 surrogate values!!
+  private static int getRandomCodePoint(final Random r, final Transition t) {
+    while(true) {
+      final int v = t.min+r.nextInt(t.max-t.min+1);
+      if (v < UnicodeUtil.UNI_SUR_HIGH_START ||
+          v > UnicodeUtil.UNI_SUR_LOW_END) {
+        return v;
+      }
+    }
+  }
+
+  public static class RandomAcceptedStrings {
+
+    private final Map<Transition,Boolean> leadsToAccept;
+    private final Automaton a;
+
+    private static class ArrivingTransition {
+      final State from;
+      final Transition t;
+      public ArrivingTransition(State from, Transition t) {
+        this.from = from;
+        this.t = t;
+      }
+    }
+
+    public RandomAcceptedStrings(Automaton a) {
+      this.a = a;
+      if (a.isSingleton()) {
+        leadsToAccept = null;
+        return;
+      }
+
+      // must use IdentityHashmap because two Transitions w/
+      // different start nodes can be considered the same
+      leadsToAccept = new IdentityHashMap<Transition,Boolean>();
+      final Map<State,List<ArrivingTransition>> allArriving = new HashMap<State,List<ArrivingTransition>>();
+
+      final LinkedList<State> q = new LinkedList<State>();
+      final Set<State> seen = new HashSet<State>();
+
+      // reverse map the transitions, so we can quickly look
+      // up all arriving transitions to a given state
+      for(State s: a.getNumberedStates()) {
+        for(int i=0;i<s.numTransitions;i++) {
+          final Transition t = s.transitionsArray[i];
+          List<ArrivingTransition> tl = allArriving.get(t.to);
+          if (tl == null) {
+            tl = new ArrayList<ArrivingTransition>();
+            allArriving.put(t.to, tl);
+          }
+          tl.add(new ArrivingTransition(s, t));
+        }
+        if (s.accept) {
+          q.add(s);
+          seen.add(s);
+        }
+      }
+
+      // Breadth-first search, from accept states,
+      // backwards:
+      while(!q.isEmpty()) {
+        final State s = q.pop();
+        List<ArrivingTransition> arriving = allArriving.get(s);
+        if (arriving != null) {
+          for(ArrivingTransition at : arriving) {
+            final State from = at.from;
+            if (!seen.contains(from)) {
+              q.add(from);
+              seen.add(from);
+              leadsToAccept.put(at.t, Boolean.TRUE);
+            }
+          }
+        }
+      }
+    }
+
+    public int[] getRandomAcceptedString(Random r) {
+
+      final List<Integer> soFar = new ArrayList<Integer>();
+      if (a.isSingleton()) {
+        // accepts only one
+        final String s = a.singleton;
+      
+        int charUpto = 0;
+        while(charUpto < s.length()) {
+          final int cp = s.codePointAt(charUpto);
+          charUpto += Character.charCount(cp);
+          soFar.add(cp);
+        }
+      } else {
+
+        State s = a.initial;
+
+        while(true) {
+      
+          if (s.accept) {
+            if (s.numTransitions == 0) {
+              // stop now
+              break;
+            } else {
+              if (r.nextBoolean()) {
+                break;
+              }
+            }
+          }
+
+          if (s.numTransitions == 0) {
+            throw new RuntimeException("this automaton has dead states");
+          }
+
+          boolean cheat = r.nextBoolean();
+
+          final Transition t;
+          if (cheat) {
+            // pick a transition that we know is the fastest
+            // path to an accept state
+            List<Transition> toAccept = new ArrayList<Transition>();
+            for(int i=0;i<s.numTransitions;i++) {
+              final Transition t0 = s.transitionsArray[i];
+              if (leadsToAccept.containsKey(t0)) {
+                toAccept.add(t0);
+              }
+            }
+            if (toAccept.size() == 0) {
+              // this is OK -- it means we jumped into a cycle
+              t = s.transitionsArray[r.nextInt(s.numTransitions)];
+            } else {
+              t = toAccept.get(r.nextInt(toAccept.size()));
+            }
+          } else {
+            t = s.transitionsArray[r.nextInt(s.numTransitions)];
+          }
+          
+          soFar.add(getRandomCodePoint(r, t));
+          s = t.to;
+        }
+      }
+
+      return ArrayUtil.toIntArray(soFar);
+    }
+  }
 }

Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java Mon May  3 23:23:57 2010
@@ -0,0 +1,38 @@
+package org.apache.lucene.util.automaton;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class ByteRunAutomaton extends RunAutomaton {
+  
+  public ByteRunAutomaton(Automaton a) {
+    super(new UTF32ToUTF8().convert(a), 256, true);
+  }
+
+  /**
+   * Returns true if the given byte array is accepted by this automaton
+   */
+  public boolean run(byte[] s, int offset, int length) {
+    int p = initial;
+    int l = offset + length;
+    for (int i = offset; i < l; i++) {
+      p = step(p, s[i] & 0xFF);
+      if (p == -1) return false;
+    }
+    return accept[p];
+  }
+}

Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ByteRunAutomaton.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java Mon May  3 23:23:57 2010
@@ -0,0 +1,51 @@
+package org.apache.lucene.util.automaton;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class CharacterRunAutomaton extends RunAutomaton {
+
+  public CharacterRunAutomaton(Automaton a) {
+    super(a, Character.MAX_CODE_POINT, false);
+  }
+
+  /**
+   * Returns true if the given string is accepted by this automaton.
+   */
+  public boolean run(String s) {
+    int p = initial;
+    int l = s.length();
+    for (int i = 0, cp = 0; i < l; i += Character.charCount(cp)) {
+      p = step(p, cp = s.codePointAt(i));
+      if (p == -1) return false;
+    }
+    return accept[p];
+  }
+  
+  /**
+   * Returns true if the given string is accepted by this automaton
+   */
+  public boolean run(char[] s, int offset, int length) {
+    int p = initial;
+    int l = offset + length;
+    for (int i = offset, cp = 0; i < l; i += Character.charCount(cp)) {
+      p = step(p, cp = Character.codePointAt(s, i, l));
+      if (p == -1) return false;
+    }
+    return accept[p];
+  }
+}

Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/CharacterRunAutomaton.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java Mon May  3 23:23:57 2010
@@ -21,11 +21,6 @@ import java.util.Iterator;
 import java.util.SortedSet;
 import java.util.TreeSet;
 
-import org.apache.lucene.util.automaton.Automaton;
-import org.apache.lucene.util.automaton.BasicAutomata;
-import org.apache.lucene.util.automaton.State;
-import org.apache.lucene.util.automaton.Transition;
-
 /**
  * Class to construct DFAs that match a word within some edit distance.
  * <p>
@@ -39,13 +34,13 @@ public class LevenshteinAutomata {
   public static final int MAXIMUM_SUPPORTED_DISTANCE = 2;
   /* input word */
   final String input;
-  final char word[];
+  final int word[];
   /* the automata alphabet. */
-  final char alphabet[];
+  final int alphabet[];
 
   /* the unicode ranges outside of alphabet */
-  final char rangeLower[];
-  final char rangeUpper[];
+  final int rangeLower[];
+  final int rangeUpper[];
   int numRanges = 0;
   
   ParametricDescription descriptions[]; 
@@ -55,42 +50,46 @@ public class LevenshteinAutomata {
    */
   public LevenshteinAutomata(String input) {
     this.input = input;
-    this.word = input.toCharArray();
+    int length = Character.codePointCount(input, 0, input.length());
+    word = new int[length];
+    for (int i = 0, j = 0, cp = 0; i < input.length(); i += Character.charCount(cp)) {
+      word[j++] = cp = input.codePointAt(i);
+    }
     
     // calculate the alphabet
-    SortedSet<Character> set = new TreeSet<Character>();
+    SortedSet<Integer> set = new TreeSet<Integer>();
     for (int i = 0; i < word.length; i++)
       set.add(word[i]);
-    alphabet = new char[set.size()];
-    Iterator<Character> iterator = set.iterator();
+    alphabet = new int[set.size()];
+    Iterator<Integer> iterator = set.iterator();
     for (int i = 0; i < alphabet.length; i++)
       alphabet[i] = iterator.next();
       
-    rangeLower = new char[alphabet.length + 2];
-    rangeUpper = new char[alphabet.length + 2];
+    rangeLower = new int[alphabet.length + 2];
+    rangeUpper = new int[alphabet.length + 2];
     // calculate the unicode range intervals that exclude the alphabet
     // these are the ranges for all unicode characters not in the alphabet
     int lower = 0;
     for (int i = 0; i < alphabet.length; i++) {
-      char higher = alphabet[i];
+      int higher = alphabet[i];
       if (higher > lower) {
-        rangeLower[numRanges] = (char) lower;
-        rangeUpper[numRanges] = (char) (higher - 1);
+        rangeLower[numRanges] = lower;
+        rangeUpper[numRanges] = higher - 1;
         numRanges++;
       }
       lower = higher + 1;
     }
     /* add the final endpoint */
-    if (lower <= 0xFFFF) {
-      rangeLower[numRanges] = (char) lower;
-      rangeUpper[numRanges] = '\uFFFF';
+    if (lower <= Character.MAX_CODE_POINT) {
+      rangeLower[numRanges] = lower;
+      rangeUpper[numRanges] = Character.MAX_CODE_POINT;
       numRanges++;
     }
 
     descriptions = new ParametricDescription[] {
         null, /* for n=0, we do not need to go through the trouble */
-        new Lev1ParametricDescription(input.length()),
-        new Lev2ParametricDescription(input.length()),
+        new Lev1ParametricDescription(word.length),
+        new Lev2ParametricDescription(word.length),
     };
   }
   
@@ -119,6 +118,7 @@ public class LevenshteinAutomata {
     // create all states, and mark as accept states if appropriate
     for (int i = 0; i < states.length; i++) {
       states[i] = new State();
+      states[i].number = i;
       states[i].setAccept(description.isAccept(i));
     }
     // create transitions from state to state
@@ -129,7 +129,7 @@ public class LevenshteinAutomata {
       final int end = xpos + Math.min(word.length - xpos, range);
       
       for (int x = 0; x < alphabet.length; x++) {
-        final char ch = alphabet[x];
+        final int ch = alphabet[x];
         // get the characteristic vector at this position wrt ch
         final int cvec = getVector(ch, xpos, end);
         int dest = description.transition(k, xpos, cvec);
@@ -143,13 +143,15 @@ public class LevenshteinAutomata {
       if (dest >= 0)
         for (int r = 0; r < numRanges; r++)
           states[k].addTransition(new Transition(rangeLower[r], rangeUpper[r], states[dest]));      
+      // reduce the state: this doesn't appear to help anything
+      //states[k].reduce();
     }
 
-    Automaton a = new Automaton();
-    a.setInitialState(states[0]);
+    Automaton a = new Automaton(states[0]);
     a.setDeterministic(true);
+    a.setNumberedStates(states);
     // we need not trim transitions to dead states, as they are not created.
-    // a.restoreInvariant();
+    //a.restoreInvariant();
     return a;
   }
   
@@ -157,7 +159,7 @@ public class LevenshteinAutomata {
    * Get the characteristic vector <code>X(x, V)</code> 
    * where V is <code>substring(pos, end)</code>
    */
-  int getVector(char x, int pos, int end) {
+  int getVector(int x, int pos, int end) {
     int vector = 0;
     for (int i = pos; i < end; i++) {
       vector <<= 1;

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java Mon May  3 23:23:57 2010
@@ -31,7 +31,6 @@ package org.apache.lucene.util.automaton
 
 import java.util.ArrayList;
 import java.util.LinkedList;
-import java.util.Set;
 
 /**
  * Operations for minimizing automata.
@@ -41,7 +40,7 @@ import java.util.Set;
 final public class MinimizationOperations {
   
   private MinimizationOperations() {}
-  
+
   /**
    * Minimizes (and determinizes if not already deterministic) the given
    * automaton.
@@ -53,8 +52,8 @@ final public class MinimizationOperation
       minimizeHopcroft(a);
     }
     // recompute hash code
-    a.hash_code = a.getNumberOfStates() * 3 + a.getNumberOfTransitions() * 2;
-    if (a.hash_code == 0) a.hash_code = 1;
+    //a.hash_code = 1a.getNumberOfStates() * 3 + a.getNumberOfTransitions() * 2;
+    //if (a.hash_code == 0) a.hash_code = 1;
   }
   
   private static <T> void initialize(ArrayList<T> list, int size) {
@@ -67,24 +66,18 @@ final public class MinimizationOperation
    */
   public static void minimizeHopcroft(Automaton a) {
     a.determinize();
-    Set<Transition> tr = a.initial.getTransitions();
-    if (tr.size() == 1) {
-      Transition t = tr.iterator().next();
-      if (t.to == a.initial && t.min == Character.MIN_VALUE
-          && t.max == Character.MAX_VALUE) return;
+    if (a.initial.numTransitions == 1) {
+      Transition t = a.initial.transitionsArray[0];
+      if (t.to == a.initial && t.min == Character.MIN_CODE_POINT
+          && t.max == Character.MAX_CODE_POINT) return;
     }
     a.totalize();
-    // make arrays for numbered states and effective alphabet
-    Set<State> ss = a.getStates();
-    State[] states = new State[ss.size()];
-    int number = 0;
-    for (State q : ss) {
-      states[number] = q;
-      q.number = number++;
-    }
-    char[] sigma = a.getStartPoints();
+
+    int[] sigma = a.getStartPoints();
     // initialize data structures
     ArrayList<ArrayList<LinkedList<State>>> reverse = new ArrayList<ArrayList<LinkedList<State>>>();
+    final State[] states = a.getNumberedStates();
+
     for (int q = 0; q < states.length; q++) {
       ArrayList<LinkedList<State>> v = new ArrayList<LinkedList<State>>();
       initialize(v, sigma.length);
@@ -121,7 +114,7 @@ final public class MinimizationOperation
       partition.get(j).add(qq);
       block[qq.number] = j;
       for (int x = 0; x < sigma.length; x++) {
-        char y = sigma[x];
+        int y = sigma[x];
         State p = qq.step(y);
         reverse.get(p.number).get(x).add(qq);
         reverse_nonempty[p.number][x] = true;
@@ -218,9 +211,10 @@ final public class MinimizationOperation
     for (int n = 0; n < newstates.length; n++) {
       State s = newstates[n];
       s.accept = states[s.number].accept;
-      for (Transition t : states[s.number].transitions)
-        s.transitions.add(new Transition(t.min, t.max, newstates[t.to.number]));
+      for (Transition t : states[s.number].getTransitions())
+        s.addTransition(new Transition(t.min, t.max, newstates[t.to.number]));
     }
+    a.clearNumberedStates();
     a.removeDeadTransitions();
   }
   

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RegExp.java Mon May  3 23:23:57 2010
@@ -366,9 +366,9 @@ public class RegExp {
   Kind kind;
   RegExp exp1, exp2;
   String s;
-  char c;
+  int c;
   int min, max, digits;
-  char from, to;
+  int from, to;
   
   String b;
   int flags;
@@ -625,10 +625,10 @@ public class RegExp {
         b.append(")");
         break;
       case REGEXP_CHAR:
-        b.append("\\").append(c);
+        b.append("\\").appendCodePoint(c);
         break;
       case REGEXP_CHAR_RANGE:
-        b.append("[\\").append(from).append("-\\").append(to).append("]");
+        b.append("[\\").appendCodePoint(from).append("-\\").appendCodePoint(to).append("]");
         break;
       case REGEXP_ANYCHAR:
         b.append(".");
@@ -725,9 +725,9 @@ public class RegExp {
   static private RegExp makeString(RegExp exp1, RegExp exp2) {
     StringBuilder b = new StringBuilder();
     if (exp1.kind == Kind.REGEXP_STRING) b.append(exp1.s);
-    else b.append(exp1.c);
+    else b.appendCodePoint(exp1.c);
     if (exp2.kind == Kind.REGEXP_STRING) b.append(exp2.s);
-    else b.append(exp2.c);
+    else b.appendCodePoint(exp2.c);
     return makeString(b.toString());
   }
   
@@ -777,14 +777,14 @@ public class RegExp {
     return r;
   }
   
-  static RegExp makeChar(char c) {
+  static RegExp makeChar(int c) {
     RegExp r = new RegExp();
     r.kind = Kind.REGEXP_CHAR;
     r.c = c;
     return r;
   }
   
-  static RegExp makeCharRange(char from, char to) {
+  static RegExp makeCharRange(int from, int to) {
     RegExp r = new RegExp();
     r.kind = Kind.REGEXP_CHAR_RANGE;
     r.from = from;
@@ -834,13 +834,13 @@ public class RegExp {
   }
   
   private boolean peek(String s) {
-    return more() && s.indexOf(b.charAt(pos)) != -1;
+    return more() && s.indexOf(b.codePointAt(pos)) != -1;
   }
   
-  private boolean match(char c) {
+  private boolean match(int c) {
     if (pos >= b.length()) return false;
-    if (b.charAt(pos) == c) {
-      pos++;
+    if (b.codePointAt(pos) == c) {
+      pos += Character.charCount(c);
       return true;
     }
     return false;
@@ -850,9 +850,11 @@ public class RegExp {
     return pos < b.length();
   }
   
-  private char next() throws IllegalArgumentException {
+  private int next() throws IllegalArgumentException {
     if (!more()) throw new IllegalArgumentException("unexpected end-of-string");
-    return b.charAt(pos++);
+    int ch = b.codePointAt(pos);
+    pos += Character.charCount(ch);
+    return ch;
   }
   
   private boolean check(int flag) {
@@ -933,7 +935,7 @@ public class RegExp {
   }
   
   final RegExp parseCharClass() throws IllegalArgumentException {
-    char c = parseCharExp();
+    int c = parseCharExp();
     if (match('-')) return makeCharRange(c, parseCharExp());
     else return makeChar(c);
   }
@@ -993,7 +995,7 @@ public class RegExp {
     } else return makeChar(parseCharExp());
   }
   
-  final char parseCharExp() throws IllegalArgumentException {
+  final int parseCharExp() throws IllegalArgumentException {
     match('\\');
     return next();
   }

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/RunAutomaton.java Mon May  3 23:23:57 2010
@@ -30,22 +30,22 @@
 package org.apache.lucene.util.automaton;
 
 import java.io.Serializable;
-import java.util.Set;
 
 /**
  * Finite-state automaton with fast run operation.
  * 
  * @lucene.experimental
  */
-public final class RunAutomaton implements Serializable {
-  
+public abstract class RunAutomaton implements Serializable {
+  final int maxInterval;
   final int size;
   final boolean[] accept;
   final int initial;
   final int[] transitions; // delta(state,c) = transitions[state*points.length +
                      // getCharClass(c)]
-  final char[] points; // char interval start points
+  final int[] points; // char interval start points
   final int[] classmap; // map from char number to class class
+  final Automaton automaton;
   
   /**
    * Returns a string representation of this automaton.
@@ -61,10 +61,10 @@ public final class RunAutomaton implemen
       for (int j = 0; j < points.length; j++) {
         int k = transitions[i * points.length + j];
         if (k != -1) {
-          char min = points[j];
-          char max;
-          if (j + 1 < points.length) max = (char) (points[j + 1] - 1);
-          else max = Character.MAX_VALUE;
+          int min = points[j];
+          int max;
+          if (j + 1 < points.length) max = (points[j + 1] - 1);
+          else max = maxInterval;
           b.append(" ");
           Transition.appendCharString(min, b);
           if (min != max) {
@@ -81,52 +81,59 @@ public final class RunAutomaton implemen
   /**
    * Returns number of states in automaton.
    */
-  public int getSize() {
+  public final int getSize() {
     return size;
   }
   
   /**
    * Returns acceptance status for given state.
    */
-  public boolean isAccept(int state) {
+  public final boolean isAccept(int state) {
     return accept[state];
   }
   
   /**
    * Returns initial state.
    */
-  public int getInitialState() {
+  public final int getInitialState() {
     return initial;
   }
   
   /**
-   * Returns array of character class interval start points. The array should
+   * Returns array of codepoint class interval start points. The array should
    * not be modified by the caller.
    */
-  public char[] getCharIntervals() {
+  public final int[] getCharIntervals() {
     return points.clone();
   }
   
   /**
-   * Gets character class of given char.
+   * Gets character class of given codepoint
    */
-  int getCharClass(char c) {
+  final int getCharClass(int c) {
     return SpecialOperations.findIndex(c, points);
   }
   
   /**
+   * @return the automaton
+   */
+  public Automaton getAutomaton() {
+    return automaton;
+  }
+
+  /**
    * Constructs a new <code>RunAutomaton</code> from a deterministic
    * <code>Automaton</code>.
    * 
    * @param a an automaton
    */
-  public RunAutomaton(Automaton a) {
+  public RunAutomaton(Automaton a, int maxInterval, boolean tableize) {
+    this.maxInterval = maxInterval;
     a.determinize();
     points = a.getStartPoints();
-    Set<State> states = a.getStates();
-    Automaton.setStateNumbers(states);
     initial = a.initial.number;
-    size = states.size();
+    final State[] states = a.getNumberedStates();
+    size = states.length;
     accept = new boolean[size];
     transitions = new int[size * points.length];
     for (int n = 0; n < size * points.length; n++)
@@ -142,12 +149,18 @@ public final class RunAutomaton implemen
     /*
      * Set alphabet table for optimal run performance.
      */
-    classmap = new int[Character.MAX_VALUE + 1];
-    int i = 0;
-    for (int j = 0; j <= Character.MAX_VALUE; j++) {
-      if (i + 1 < points.length && j == points[i + 1]) i++;
-      classmap[j] = i;
+    if (tableize) {
+      classmap = new int[maxInterval + 1];
+      int i = 0;
+      for (int j = 0; j <= maxInterval; j++) {
+        if (i + 1 < points.length && j == points[i + 1])
+          i++;
+        classmap[j] = i;
+      }
+    } else {
+      classmap = null;
     }
+    this.automaton = a;
   }
   
   /**
@@ -157,54 +170,10 @@ public final class RunAutomaton implemen
    * if a dead state is entered in an equivalent automaton with a total
    * transition function.)
    */
-  public int step(int state, char c) {
-    return transitions[state * points.length + classmap[c]];
-  }
-  
-  /**
-   * Returns true if the given string is accepted by this automaton.
-   */
-  public boolean run(String s) {
-    int p = initial;
-    int l = s.length();
-    for (int i = 0; i < l; i++) {
-      p = step(p, s.charAt(i));
-      if (p == -1) return false;
-    }
-    return accept[p];
-  }
-  
-  /**
-   * Returns true if the given string is accepted by this automaton
-   */
-  public boolean run(char[] s, int offset, int length) {
-    int p = initial;
-    int l = offset + length;
-    for (int i = offset; i < l; i++) {
-      p = step(p, s[i]);
-      if (p == -1) return false;
-    }
-    return accept[p];
-  }
-  
-  /**
-   * Returns the length of the longest accepted run of the given string starting
-   * at the given offset.
-   * 
-   * @param s the string
-   * @param offset offset into <code>s</code> where the run starts
-   * @return length of the longest accepted run, -1 if no run is accepted
-   */
-  public int run(String s, int offset) {
-    int p = initial;
-    int l = s.length();
-    int max = -1;
-    for (int r = 0; offset <= l; offset++, r++) {
-      if (accept[p]) max = r;
-      if (offset == l) break;
-      p = step(p, s.charAt(offset));
-      if (p == -1) break;
-    }
-    return max;
+  public final int step(int state, int c) {
+    if (classmap == null)
+      return transitions[state * points.length + getCharClass(c)];
+    else
+      return transitions[state * points.length + classmap[c]];
   }
 }

Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java Mon May  3 23:23:57 2010
@@ -0,0 +1,272 @@
+package org.apache.lucene.util.automaton;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.util.TreeMap;
+import java.util.Map;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.RamUsageEstimator;
+
+// Just holds a set of int[] states, plus a corresponding
+// int[] count per state.  Used by
+// BasicOperations.determinize
+final class SortedIntSet {
+  int[] values;
+  int[] counts;
+  int upto;
+  private int hashCode;
+
+  // If we hold more than this many states, we switch from
+  // O(N^2) linear ops to O(N log(N)) TreeMap
+  private final static int TREE_MAP_CUTOVER = 30;
+
+  private final Map<Integer,Integer> map = new TreeMap<Integer,Integer>();
+
+  private boolean useTreeMap;
+
+  State state;
+
+  public SortedIntSet(int capacity) {
+    values = new int[capacity];
+    counts = new int[capacity];
+  }
+
+  // Adds this state to the set
+  public void incr(int num) {
+    if (useTreeMap) {
+      final Integer key = num;
+      Integer val = map.get(key);
+      if (val == null) {
+        map.put(key, 1);
+      } else {
+        map.put(key, 1+val);
+      }
+      return;
+    }
+
+    if (upto == values.length) {
+      values = ArrayUtil.grow(values, 1+upto);
+      counts = ArrayUtil.grow(counts, 1+upto);
+    }
+
+    for(int i=0;i<upto;i++) {
+      if (values[i] == num) {
+        counts[i]++;
+        return;
+      } else if (num < values[i]) {
+        // insert here
+        int j = upto-1;
+        while (j >= i) {
+          values[1+j] = values[j];
+          counts[1+j] = counts[j];
+          j--;
+        }
+        values[i] = num;
+        counts[i] = 1;
+        upto++;
+        return;
+      }
+    }
+
+    // append
+    values[upto] = num;
+    counts[upto] = 1;
+    upto++;
+
+    if (upto == TREE_MAP_CUTOVER) {
+      useTreeMap = true;
+      for(int i=0;i<upto;i++) {
+        map.put(values[i], counts[i]);
+      }
+    }
+  }
+
+  // Removes this state from the set, if count decrs to 0
+  public void decr(int num) {
+
+    if (useTreeMap) {
+      final int count = map.get(num);
+      if (count == 1) {
+        map.remove(num);
+      } else {
+        map.put(num, count-1);
+      }
+      // Fall back to simple arrays once we touch zero again
+      if (map.size() == 0) {
+        useTreeMap = false;
+        upto = 0;
+      }
+      return;
+    }
+
+    for(int i=0;i<upto;i++) {
+      if (values[i] == num) {
+        counts[i]--;
+        if (counts[i] == 0) {
+          final int limit = upto-1;
+          while(i < limit) {
+            values[i] = values[i+1];
+            counts[i] = counts[i+1];
+            i++;
+          }
+          upto = limit;
+        }
+        return;
+      }
+    }
+    assert false;
+  }
+
+  public void computeHash() {
+    if (useTreeMap) {
+      if (map.size() > values.length) {
+        final int size = ArrayUtil.oversize(map.size(), RamUsageEstimator.NUM_BYTES_INT);
+        values = new int[size];
+        counts = new int[size];
+      }
+      hashCode = map.size();
+      upto = 0;
+      for(int state : map.keySet()) {
+        hashCode = 683*hashCode + state;
+        values[upto++] = state;
+      }
+    } else {
+      hashCode = upto;
+      for(int i=0;i<upto;i++) {
+        hashCode = 683*hashCode + values[i];
+      }
+    }
+  }
+
+  public FrozenIntSet freeze(State state) {
+    final int[] c = new int[upto];
+    System.arraycopy(values, 0, c, 0, upto);
+    return new FrozenIntSet(c, hashCode, state);
+  }
+
+  public int hashCode() {
+    return hashCode;
+  }
+
+  public boolean equals(Object _other) {
+    if (_other == null) {
+      return false;
+    }
+    if (!(_other instanceof FrozenIntSet)) {
+      return false;
+    }
+    FrozenIntSet other = (FrozenIntSet) _other;
+    if (hashCode != other.hashCode) {
+      return false;
+    }
+    if (other.values.length != upto) {
+      return false;
+    }
+    for(int i=0;i<upto;i++) {
+      if (other.values[i] != values[i]) {
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  public String toString() {
+    StringBuilder sb = new StringBuilder().append('[');
+    for(int i=0;i<upto;i++) {
+      if (i > 0) {
+        sb.append(' ');
+      }
+      sb.append(values[i]).append(':').append(counts[i]);
+    }
+    sb.append(']');
+    return sb.toString();
+  }
+  
+  public final static class FrozenIntSet {
+    final int[] values;
+    final int hashCode;
+    final State state;
+
+    public FrozenIntSet(int[] values, int hashCode, State state) {
+      this.values = values;
+      this.hashCode = hashCode;
+      this.state = state;
+    }
+
+    public FrozenIntSet(int num, State state) {
+      this.values = new int[] {num};
+      this.state = state;
+      this.hashCode = 683+num;
+    }
+
+    public int hashCode() {
+      return hashCode;
+    }
+
+    public boolean equals(Object _other) {
+      if (_other == null) {
+        return false;
+      }
+      if (_other instanceof FrozenIntSet) {
+        FrozenIntSet other = (FrozenIntSet) _other;
+        if (hashCode != other.hashCode) {
+          return false;
+        }
+        if (other.values.length != values.length) {
+          return false;
+        }
+        for(int i=0;i<values.length;i++) {
+          if (other.values[i] != values[i]) {
+            return false;
+          }
+        }
+        return true;
+      } else if (_other instanceof SortedIntSet) {
+        SortedIntSet other = (SortedIntSet) _other;
+        if (hashCode != other.hashCode) {
+          return false;
+        }
+        if (other.values.length != values.length) {
+          return false;
+        }
+        for(int i=0;i<values.length;i++) {
+          if (other.values[i] != values[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+      return false;
+    }
+
+    public String toString() {
+      StringBuilder sb = new StringBuilder().append('[');
+      for(int i=0;i<values.length;i++) {
+        if (i > 0) {
+          sb.append(' ');
+        }
+        sb.append(values[i]);
+      }
+      sb.append(']');
+      return sb.toString();
+    }
+  }
+}
+  

Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SortedIntSet.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/SpecialOperations.java Mon May  3 23:23:57 2010
@@ -33,6 +33,8 @@ import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Set;
 
+import org.apache.lucene.util.BytesRef;
+
 /**
  * Special automata operations.
  * 
@@ -46,7 +48,7 @@ final public class SpecialOperations {
    * Finds the largest entry whose value is less than or equal to c, or 0 if
    * there is no such entry.
    */
-  static int findIndex(char c, char[] points) {
+  static int findIndex(int c, int[] points) {
     int a = 0;
     int b = points.length;
     while (b - a > 1) {
@@ -70,9 +72,11 @@ final public class SpecialOperations {
    * Checks whether there is a loop containing s. (This is sufficient since
    * there are never transitions to dead states.)
    */
+  // TODO: not great that this is recursive... in theory a
+  // large automata could exceed java's stack
   private static boolean isFinite(State s, HashSet<State> path) {
     path.add(s);
-    for (Transition t : s.transitions)
+    for (Transition t : s.getTransitions())
       if (path.contains(t.to) || !isFinite(t.to, path)) return false;
     path.remove(s);
     return true;
@@ -93,10 +97,10 @@ final public class SpecialOperations {
     do {
       done = true;
       visited.add(s);
-      if (!s.accept && s.transitions.size() == 1) {
-        Transition t = s.transitions.iterator().next();
+      if (!s.accept && s.numTransitions() == 1) {
+        Transition t = s.getTransitions().iterator().next();
         if (t.min == t.max && !visited.contains(t.to)) {
-          b.append(t.min);
+          b.appendCodePoint(t.min);
           s = t.to;
           done = false;
         }
@@ -105,6 +109,31 @@ final public class SpecialOperations {
     return b.toString();
   }
   
+  // TODO: this currently requites a determinized machine,
+  // but it need not -- we can speed it up by walking the
+  // NFA instead.  it'd still be fail fast.
+  public static BytesRef getCommonPrefixBytesRef(Automaton a) {
+    if (a.isSingleton()) return new BytesRef(a.singleton);
+    BytesRef ref = new BytesRef(10);
+    HashSet<State> visited = new HashSet<State>();
+    State s = a.initial;
+    boolean done;
+    do {
+      done = true;
+      visited.add(s);
+      if (!s.accept && s.numTransitions() == 1) {
+        Transition t = s.getTransitions().iterator().next();
+        if (t.min == t.max && !visited.contains(t.to)) {
+          ref.grow(++ref.length);
+          ref.bytes[ref.length - 1] = (byte)t.min;
+          s = t.to;
+          done = false;
+        }
+      }
+    } while (!done);
+    return ref;
+  }
+  
   /**
    * Returns the longest string that is a suffix of all accepted strings and
    * visits each state at most once.
@@ -119,7 +148,30 @@ final public class SpecialOperations {
     Automaton r = a.clone();
     reverse(r);
     r.determinize();
-    return reverseUnicode3(SpecialOperations.getCommonPrefix(r));
+    return new StringBuilder(SpecialOperations.getCommonPrefix(r)).reverse().toString();
+  }
+  
+  public static BytesRef getCommonSuffixBytesRef(Automaton a) {
+    if (a.isSingleton()) // if singleton, the suffix is the string itself.
+      return new BytesRef(a.singleton);
+    
+    // reverse the language of the automaton, then reverse its common prefix.
+    Automaton r = a.clone();
+    reverse(r);
+    r.determinize();
+    BytesRef ref = SpecialOperations.getCommonPrefixBytesRef(r);
+    reverseBytes(ref);
+    return ref;
+  }
+  
+  private static void reverseBytes(BytesRef ref) {
+    if (ref.length <= 1) return;
+    int num = ref.length >> 1;
+    for (int i = ref.offset; i < ( ref.offset + num ); i++) {
+      byte b = ref.bytes[i];
+      ref.bytes[i] = ref.bytes[ref.offset * 2 + ref.length - i - 1];
+      ref.bytes[ref.offset * 2 + ref.length - i - 1] = b;
+    }
   }
   
   /**
@@ -130,8 +182,11 @@ final public class SpecialOperations {
     a.expandSingleton();
     // reverse all edges
     HashMap<State, HashSet<Transition>> m = new HashMap<State, HashSet<Transition>>();
-    Set<State> states = a.getStates();
-    Set<State> accept = a.getAcceptStates();
+    State[] states = a.getNumberedStates();
+    Set<State> accept = new HashSet<State>();
+    for (State s : states)
+      if (s.isAccept())
+        accept.add(s);
     for (State r : states) {
       m.put(r, new HashSet<Transition>());
       r.accept = false;
@@ -139,41 +194,17 @@ final public class SpecialOperations {
     for (State r : states)
       for (Transition t : r.getTransitions())
         m.get(t.to).add(new Transition(t.min, t.max, r));
-    for (State r : states)
-      r.transitions = m.get(r);
+    for (State r : states) {
+      Set<Transition> tr = m.get(r);
+      r.setTransitions(tr.toArray(new Transition[tr.size()]));
+    }
     // make new initial+final states
     a.initial.accept = true;
     a.initial = new State();
     for (State r : accept)
       a.initial.addEpsilon(r); // ensures that all initial states are reachable
     a.deterministic = false;
+    a.clearNumberedStates();
     return accept;
   }
-  
-  /**
-   * Intentionally use a unicode 3 reverse.
-   * This is because we are only going to reverse it again...
-   */
-  private static String reverseUnicode3( final String input ){
-    char[] charInput = input.toCharArray();
-    reverseUnicode3(charInput, 0, charInput.length);
-    return new String(charInput);
-  }
-  
-  /**
-   * Intentionally use a unicode 3 reverse.
-   * This is because it is only used by getCommonSuffix(),
-   * which will reverse the entire FSM using code unit reversal,
-   * so we must then reverse its common prefix back using the 
-   * same code unit reversal.
-   */
-  private static void reverseUnicode3(char[] buffer, int start, int len){
-    if (len <= 1) return;
-    int num = len>>1;
-    for (int i = start; i < ( start + num ); i++) {
-      char c = buffer[i];
-      buffer[i] = buffer[start * 2 + len - i - 1];
-      buffer[start * 2 + len - i - 1] = c;
-    }
-  }
 }

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/State.java Mon May  3 23:23:57 2010
@@ -28,13 +28,14 @@
  */
 
 package org.apache.lucene.util.automaton;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.RamUsageEstimator;
 
 import java.io.Serializable;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Set;
+import java.util.Comparator;
+import java.util.Iterator;
 
 /**
  * <tt>Automaton</tt> state.
@@ -44,7 +45,8 @@ import java.util.Set;
 public class State implements Serializable, Comparable<State> {
   
   boolean accept;
-  Set<Transition> transitions;
+  public Transition[] transitionsArray;
+  public int numTransitions;
   
   int number;
 
@@ -63,7 +65,25 @@ public class State implements Serializab
    * Resets transition set.
    */
   final void resetTransitions() {
-    transitions = new HashSet<Transition>();
+    transitionsArray = new Transition[0];
+    numTransitions = 0;
+  }
+
+  private class TransitionsIterable implements Iterable<Transition> {
+    public Iterator<Transition> iterator() {
+      return new Iterator<Transition>() {
+        int upto;
+        public boolean hasNext() {
+          return upto < numTransitions;
+        }
+        public Transition next() {
+          return transitionsArray[upto++];
+        }
+        public void remove() {
+          throw new UnsupportedOperationException();
+        }
+      };
+    }
   }
   
   /**
@@ -72,8 +92,17 @@ public class State implements Serializab
    * 
    * @return transition set
    */
-  public Set<Transition> getTransitions() {
-    return transitions;
+  public Iterable<Transition> getTransitions() {
+    return new TransitionsIterable();
+  }
+
+  public int numTransitions() {
+    return numTransitions;
+  }
+
+  public void setTransitions(Transition[] transitions) {
+    this.numTransitions = transitions.length;
+    this.transitionsArray = transitions;
   }
   
   /**
@@ -82,7 +111,12 @@ public class State implements Serializab
    * @param t transition
    */
   public void addTransition(Transition t) {
-    transitions.add(t);
+    if (numTransitions == transitionsArray.length) {
+      final Transition[] newArray = new Transition[ArrayUtil.oversize(1+numTransitions, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+      System.arraycopy(transitionsArray, 0, newArray, 0, numTransitions);
+      transitionsArray = newArray;
+    }
+    transitionsArray[numTransitions++] = t;
   }
   
   /**
@@ -106,44 +140,88 @@ public class State implements Serializab
   /**
    * Performs lookup in transitions, assuming determinism.
    * 
-   * @param c character to look up
+   * @param c codepoint to look up
    * @return destination state, null if no matching outgoing transition
-   * @see #step(char, Collection)
+   * @see #step(int, Collection)
    */
-  public State step(char c) {
-    for (Transition t : transitions)
+  public State step(int c) {
+    assert c >= 0;
+    for (int i=0;i<numTransitions;i++) {
+      final Transition t = transitionsArray[i];
       if (t.min <= c && c <= t.max) return t.to;
+    }
     return null;
   }
   
   /**
    * Performs lookup in transitions, allowing nondeterminism.
    * 
-   * @param c character to look up
+   * @param c codepoint to look up
    * @param dest collection where destination states are stored
-   * @see #step(char)
+   * @see #step(int)
    */
-  public void step(char c, Collection<State> dest) {
-    for (Transition t : transitions)
+  public void step(int c, Collection<State> dest) {
+    for (int i=0;i<numTransitions;i++) {
+      final Transition t = transitionsArray[i];
       if (t.min <= c && c <= t.max) dest.add(t.to);
+    }
   }
   
   void addEpsilon(State to) {
     if (to.accept) accept = true;
-    for (Transition t : to.transitions)
-      transitions.add(t);
+    for (Transition t : to.getTransitions())
+      addTransition(t);
+  }
+
+  /** Downsizes transitionArray to numTransitions */
+  public void trimTransitionsArray() {
+    if (numTransitions < transitionsArray.length) {
+      final Transition[] newArray = new Transition[numTransitions];
+      System.arraycopy(transitionsArray, 0, newArray, 0, numTransitions);
+      transitionsArray = newArray;
+    }
   }
   
   /**
-   * Returns transitions sorted by (min, reverse max, to) or (to, min, reverse
-   * max)
-   */
-  public Transition[] getSortedTransitionArray(boolean to_first) {
-    Transition[] e = transitions.toArray(new Transition[transitions.size()]);
-    Arrays.sort(e, new TransitionComparator(to_first));
-    return e;
+   * Reduces this state. A state is "reduced" by combining overlapping
+   * and adjacent edge intervals with same destination.
+   */
+  public void reduce() {
+    if (numTransitions <= 1) {
+      return;
+    }
+    sortTransitions(Transition.CompareByDestThenMinMax);
+    State p = null;
+    int min = -1, max = -1;
+    int upto = 0;
+    for (int i=0;i<numTransitions;i++) {
+      final Transition t = transitionsArray[i];
+      if (p == t.to) {
+        if (t.min <= max + 1) {
+          if (t.max > max) max = t.max;
+        } else {
+          if (p != null) {
+            transitionsArray[upto++] = new Transition(min, max, p);
+          }
+          min = t.min;
+          max = t.max;
+        }
+      } else {
+        if (p != null) {
+          transitionsArray[upto++] = new Transition(min, max, p);
+        }
+        p = t.to;
+        min = t.min;
+        max = t.max;
+      }
+    }
+
+    if (p != null) {
+      transitionsArray[upto++] = new Transition(min, max, p);
+    }
+    numTransitions = upto;
   }
-  
+
   /**
    * Returns sorted list of outgoing transitions.
    * 
@@ -151,10 +229,11 @@ public class State implements Serializab
    *          reverse max, to)
    * @return transition list
    */
-  public List<Transition> getSortedTransitions(boolean to_first) {
-    return Arrays.asList(getSortedTransitionArray(to_first));
-  }
   
+  /** Sorts transitions array in-place. */
+  public void sortTransitions(Comparator<Transition> comparator) {
+    Arrays.sort(transitionsArray, 0, numTransitions, comparator);
+  }
   
   /**
    * Return this state's number. 
@@ -178,7 +257,7 @@ public class State implements Serializab
     if (accept) b.append(" [accept]");
     else b.append(" [reject]");
     b.append(":\n");
-    for (Transition t : transitions)
+    for (Transition t : getTransitions())
       b.append("  ").append(t.toString()).append("\n");
     return b.toString();
   }
@@ -190,20 +269,4 @@ public class State implements Serializab
   public int compareTo(State s) {
     return s.id - id;
   }
-  
-  /**
-   * See {@link java.lang.Object#equals(java.lang.Object)}.
-   */
-  @Override
-  public boolean equals(Object obj) {
-    return super.equals(obj);
-  }
-  
-  /**
-   * See {@link java.lang.Object#hashCode()}.
-   */
-  @Override
-  public int hashCode() {
-    return super.hashCode();
-  }
 }

Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java?rev=940671&r1=940670&r2=940671&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Transition.java Mon May  3 23:23:57 2010
@@ -30,12 +30,13 @@
 package org.apache.lucene.util.automaton;
 
 import java.io.Serializable;
+import java.util.Comparator;
 
 /**
  * <tt>Automaton</tt> transition.
  * <p>
  * A transition, which belongs to a source state, consists of a Unicode
- * character interval and a destination state.
+ * codepoint interval and a destination state.
  * 
  * @lucene.experimental
  */
@@ -45,18 +46,18 @@ public class Transition implements Seria
    * CLASS INVARIANT: min<=max
    */
 
-  char min;
-  char max;
-  
-  State to;
+  final int min;
+  final int max;
+  final State to;
   
   /**
    * Constructs a new singleton interval transition.
    * 
-   * @param c transition character
+   * @param c transition codepoint
    * @param to destination state
    */
-  public Transition(char c, State to) {
+  public Transition(int c, State to) {
+    assert c >= 0;
     min = max = c;
     this.to = to;
   }
@@ -68,9 +69,11 @@ public class Transition implements Seria
    * @param max transition interval maximum
    * @param to destination state
    */
-  public Transition(char min, char max, State to) {
+  public Transition(int min, int max, State to) {
+    assert min >= 0;
+    assert max >= 0;
     if (max < min) {
-      char t = max;
+      int t = max;
       max = min;
       min = t;
     }
@@ -80,12 +83,12 @@ public class Transition implements Seria
   }
   
   /** Returns minimum of this transition interval. */
-  public char getMin() {
+  public int getMin() {
     return min;
   }
   
   /** Returns maximum of this transition interval. */
-  public char getMax() {
+  public int getMax() {
     return max;
   }
   
@@ -134,14 +137,18 @@ public class Transition implements Seria
     }
   }
   
-  static void appendCharString(char c, StringBuilder b) {
-    if (c >= 0x21 && c <= 0x7e && c != '\\' && c != '"') b.append(c);
+  static void appendCharString(int c, StringBuilder b) {
+    if (c >= 0x21 && c <= 0x7e && c != '\\' && c != '"') b.appendCodePoint(c);
     else {
-      b.append("\\u");
+      b.append("\\\\U");
       String s = Integer.toHexString(c);
-      if (c < 0x10) b.append("000").append(s);
-      else if (c < 0x100) b.append("00").append(s);
-      else if (c < 0x1000) b.append("0").append(s);
+      if (c < 0x10) b.append("0000000").append(s);
+      else if (c < 0x100) b.append("000000").append(s);
+      else if (c < 0x1000) b.append("00000").append(s);
+      else if (c < 0x10000) b.append("0000").append(s);
+      else if (c < 0x100000) b.append("000").append(s);
+      else if (c < 0x1000000) b.append("00").append(s);
+      else if (c < 0x10000000) b.append("0").append(s);
       else b.append(s);
     }
   }
@@ -171,4 +178,96 @@ public class Transition implements Seria
     }
     b.append("\"]\n");
   }
+
+  private static final class CompareByDestThenMinMaxSingle implements Comparator<Transition> {
+    public int compare(Transition t1, Transition t2) {
+      if (t1.to != t2.to) {
+        if (t1.to.number < t2.to.number) return -1;
+        else if (t1.to.number > t2.to.number) return 1;
+      }
+      if (t1.min < t2.min) return -1;
+      if (t1.min > t2.min) return 1;
+      if (t1.max > t2.max) return -1;
+      if (t1.max < t2.max) return 1;
+      return 0;
+    }
+  }
+
+  public static final Comparator<Transition> CompareByDestThenMinMax = new CompareByDestThenMinMaxSingle();
+
+  private static final class CompareByMinMaxThenDestSingle implements Comparator<Transition> {
+    public int compare(Transition t1, Transition t2) {
+      if (t1.min < t2.min) return -1;
+      if (t1.min > t2.min) return 1;
+      if (t1.max > t2.max) return -1;
+      if (t1.max < t2.max) return 1;
+      if (t1.to != t2.to) {
+        if (t1.to.number < t2.to.number) return -1;
+        if (t1.to.number > t2.to.number) return 1;
+      }
+      return 0;
+    }
+  }
+
+  public static final Comparator<Transition> CompareByMinMaxThenDest = new CompareByMinMaxThenDestSingle();
+
+  private static class UTF8InUTF16Order {
+    protected int compareCodePoint(int aByte, int bByte) {
+      if (aByte != bByte) {
+        // See http://icu-project.org/docs/papers/utf16_code_point_order.html#utf-8-in-utf-16-order
+
+        // We know the terms are not equal, but, we may
+        // have to carefully fixup the bytes at the
+        // difference to match UTF16's sort order:
+        if (aByte >= 0xee && bByte >= 0xee) {
+          if ((aByte & 0xfe) == 0xee) {
+            aByte += 0x10;
+          }
+          if ((bByte&0xfe) == 0xee) {
+            bByte += 0x10;
+          }
+        }
+        return aByte - bByte;
+      }
+      return 0;
+    }
+  }
+
+  private static final class CompareByDestThenMinMaxUTF8InUTF16OrderSingle extends UTF8InUTF16Order implements Comparator<Transition> {
+    public int compare(Transition t1, Transition t2) {
+      if (t1.to != t2.to) {
+        if (t1.to == null) return -1;
+        else if (t2.to == null) return 1;
+        else if (t1.to.number < t2.to.number) return -1;
+        else if (t1.to.number > t2.to.number) return 1;
+      }
+      int minComp = compareCodePoint(t1.min, t2.min);
+      if (minComp != 0) return minComp;
+      int maxComp = compareCodePoint(t1.max, t2.max);
+      if (maxComp != 0) return maxComp;
+      return 0;
+    }
+  }
+
+  public static final Comparator<Transition> CompareByDestThenMinMaxUTF8InUTF16Order = new CompareByDestThenMinMaxUTF8InUTF16OrderSingle();
+
+  private static final class CompareByMinMaxThenDestUTF8InUTF16OrderSingle extends UTF8InUTF16Order implements Comparator<Transition> {
+    public int compare(Transition t1, Transition t2) {
+      int minComp = compareCodePoint(t1.min, t2.min);
+      if (minComp != 0) return minComp;
+      int maxComp = compareCodePoint(t1.max, t2.max);
+      if (maxComp != 0) return maxComp;
+      if (t1.to != t2.to) {
+        if (t1.to == null) return -1;
+        else if (t2.to == null) return 1;
+        else if (t1.to.number < t2.to.number) return -1;
+        else if (t1.to.number > t2.to.number) return 1;
+      }
+      return 0;
+    }
+  }
+
+  public static final Comparator<Transition> CompareByMinMaxThenDestUTF8InUTF16Order = new CompareByMinMaxThenDestUTF8InUTF16OrderSingle();
+
+
 }

Added: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java?rev=940671&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java (added)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java Mon May  3 23:23:57 2010
@@ -0,0 +1,324 @@
+package org.apache.lucene.util.automaton;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import org.apache.lucene.util.RamUsageEstimator;
+import org.apache.lucene.util.ArrayUtil;
+
+import java.util.List;
+import java.util.ArrayList;
+
+// TODO
+//   - do we really need the .bits...?  if not we can make util in UnicodeUtil to convert 1 char into a BytesRef
+
+final class UTF32ToUTF8 {
+
+  // Unicode boundaries for UTF8 bytes 1,2,3,4
+  private static final int[] startCodes = new int[] {0, 128, 2048, 65536};
+  private static final int[] endCodes = new int[] {127, 2047, 65535, 1114111};
+
+  static int[] MASKS = new int[32];
+  static {
+    int v = 2;
+    for(int i=0;i<32;i++) {
+      MASKS[i] = v-1;
+      v *= 2;
+    }
+  }
+
+  // Represents one of the N utf8 bytes that (in sequence)
+  // define a code point.  value is the byte value; bits is
+  // how many bits are "used" by utf8 at that byte
+  private static class UTF8Byte {
+    int value;                                    // TODO: change to byte
+    byte bits;
+  }
+
+  // Holds a single code point, as a sequence of 1-4 utf8 bytes:
+  // TODO: maybe move to UnicodeUtil?
+  private static class UTF8Sequence {
+    private final UTF8Byte[] bytes;
+    private int len;
+
+    public UTF8Sequence() {
+      bytes = new UTF8Byte[4];
+      for(int i=0;i<4;i++) {
+        bytes[i] = new UTF8Byte();
+      }
+    }
+
+    public int byteAt(int idx) {
+      return bytes[idx].value;
+    }
+
+    public int numBits(int idx) {
+      return bytes[idx].bits;
+    }
+
+    private void set(int code) {
+      if (code < 128) {
+        // 0xxxxxxx
+        bytes[0].value = code;
+        bytes[0].bits = 7;
+        len = 1;
+      } else if (code < 2048) {
+        // 110yyyxx 10xxxxxx
+        bytes[0].value = (6 << 5) | (code >> 6);
+        bytes[0].bits = 5;
+        setRest(code, 1);
+        len = 2;
+      } else if (code < 65536) {
+        // 1110yyyy 10yyyyxx 10xxxxxx
+        bytes[0].value = (14 << 4) | (code >> 12);
+        bytes[0].bits = 4;
+        setRest(code, 2);
+        len = 3;
+      } else {
+        // 11110zzz 10zzyyyy 10yyyyxx 10xxxxxx
+        bytes[0].value = (30 << 3) | (code >> 18);
+        bytes[0].bits = 3;
+        setRest(code, 3);
+        len = 4;
+      }
+    }
+
+    private void setRest(int code, int numBytes) {
+      for(int i=0;i<numBytes;i++) {
+        bytes[numBytes-i].value = 128 | (code & MASKS[5]);
+        bytes[numBytes-i].bits = 6;
+        code = code >> 6;
+      }
+    }
+
+    public String toString() {
+      StringBuilder b = new StringBuilder();
+      for(int i=0;i<len;i++) {
+        if (i > 0) {
+          b.append(' ');
+        }
+        b.append(Integer.toBinaryString(bytes[i].value));
+      }
+      return b.toString();
+    }
+  }
+
+  private final UTF8Sequence startUTF8 = new UTF8Sequence();
+  private final UTF8Sequence endUTF8 = new UTF8Sequence();
+
+  private final UTF8Sequence tmpUTF8a = new UTF8Sequence();
+  private final UTF8Sequence tmpUTF8b = new UTF8Sequence();
+
+  // Builds necessary utf8 edges between start & end
+  void convertOneEdge(State start, State end, int startCodePoint, int endCodePoint) {
+    startUTF8.set(startCodePoint);
+    endUTF8.set(endCodePoint);
+    //System.out.println("start = " + startUTF8);
+    //System.out.println("  end = " + endUTF8);
+    build(start, end, startUTF8, endUTF8, 0);
+  }
+
+  private void build(State start, State end, UTF8Sequence startUTF8, UTF8Sequence endUTF8, int upto) {
+
+    // Break into start, middle, end:
+    if (startUTF8.byteAt(upto) == endUTF8.byteAt(upto)) {
+      // Degen case: lead with the same byte:
+      if (upto == startUTF8.len-1 && upto == endUTF8.len-1) {
+        // Super degen: just single edge, one UTF8 byte:
+        start.addTransition(new Transition(startUTF8.byteAt(upto), endUTF8.byteAt(upto), end));
+        return;
+      } else {
+        assert startUTF8.len > upto+1;
+        assert endUTF8.len > upto+1;
+        State n = newUTF8State();
+
+        // Single value leading edge
+        start.addTransition(new Transition(startUTF8.byteAt(upto), n));  // type=single
+
+        // Recurse for the rest
+        build(n, end, startUTF8, endUTF8, 1+upto);
+      }
+    } else if (startUTF8.len == endUTF8.len) {
+      if (upto == startUTF8.len-1) {
+        start.addTransition(new Transition(startUTF8.byteAt(upto), endUTF8.byteAt(upto), end));        // type=startend
+      } else {
+        start(start, end, startUTF8, upto, false);
+        if (endUTF8.byteAt(upto) - startUTF8.byteAt(upto) > 1) {
+          // There is a middle
+          all(start, end, startUTF8.byteAt(upto)+1, endUTF8.byteAt(upto)-1, startUTF8.len-upto-1);
+        }
+        end(start, end, endUTF8, upto, false);
+      }
+    } else {
+
+      // start
+      start(start, end, startUTF8, upto, true);
+
+      // possibly middle, spanning multiple num bytes
+      int byteCount = 1+startUTF8.len-upto;
+      final int limit = endUTF8.len-upto;
+      while (byteCount < limit) {
+        // wasteful: we only need first byte, and, we should
+        // statically encode this first byte:
+        tmpUTF8a.set(startCodes[byteCount-1]);
+        tmpUTF8b.set(endCodes[byteCount-1]);
+        all(start, end,
+            tmpUTF8a.byteAt(0),
+            tmpUTF8b.byteAt(0),
+            tmpUTF8a.len - 1);
+        byteCount++;
+      }
+
+      // end
+      end(start, end, endUTF8, upto, true);
+    }
+  }
+
+  private void start(State start, State end, UTF8Sequence utf8, int upto, boolean doAll) {
+    if (upto == utf8.len-1) {
+      // Done recursing
+      start.addTransition(new Transition(utf8.byteAt(upto), utf8.byteAt(upto) | MASKS[utf8.numBits(upto)-1], end));  // type=start
+    } else {
+      State n = newUTF8State();
+      start.addTransition(new Transition(utf8.byteAt(upto), n));  // type=start
+      start(n, end, utf8, 1+upto, true);
+      int endCode = utf8.byteAt(upto) | MASKS[utf8.numBits(upto)-1];
+      if (doAll && utf8.byteAt(upto) != endCode) {
+        all(start, end, utf8.byteAt(upto)+1, endCode, utf8.len-upto-1);
+      }
+    }
+  }
+
+  private void end(State start, State end, UTF8Sequence utf8, int upto, boolean doAll) {
+    if (upto == utf8.len-1) {
+      // Done recursing
+      start.addTransition(new Transition(utf8.byteAt(upto) & (~MASKS[utf8.numBits(upto)-1]), utf8.byteAt(upto), end));   // type=end
+    } else {
+      final int startCode;
+      if (utf8.numBits(upto) == 5) {
+        // special case -- avoid created unused edges (utf8
+        // doesn't accept certain byte sequences) -- there
+        // are other cases we could optimize too:
+        startCode = 194;
+      } else {
+        startCode = utf8.byteAt(upto) & (~MASKS[utf8.numBits(upto)-1]);
+      }
+      if (doAll && utf8.byteAt(upto) != startCode) {
+        all(start, end, startCode, utf8.byteAt(upto)-1, utf8.len-upto-1);
+      }
+      State n = newUTF8State();
+      start.addTransition(new Transition(utf8.byteAt(upto), n));  // type=end
+      end(n, end, utf8, 1+upto, true);
+    }
+  }
+
+  private void all(State start, State end, int startCode, int endCode, int left) {
+    if (left == 0) {
+      start.addTransition(new Transition(startCode, endCode, end));  // type=all
+    } else {
+      State lastN = newUTF8State();
+      start.addTransition(new Transition(startCode, endCode, lastN));  // type=all
+      while (left > 1) {
+        State n = newUTF8State();
+        lastN.addTransition(new Transition(128, 191, n));  // type=all*
+        left--;
+        lastN = n;
+      }
+      lastN.addTransition(new Transition(128, 191, end)); // type = all*
+    }
+  }
+
+  private State[] utf8States;
+  private int utf8StateCount;
+
+  /** Converts an incoming utf32 automaton to an equivalent
+   *  utf8 one.  The incoming automaton need not be
+   *  deterministic.  Note that the returned automaton will
+   *  not in general be deterministic, so you must
+   *  determinize it if that's needed. */
+  public Automaton convert(Automaton utf32) {
+    if (utf32.isSingleton()) {
+      utf32 = utf32.cloneExpanded();
+    }
+
+    State[] map = new State[utf32.getNumberedStates().length];
+    List<State> pending = new ArrayList<State>();
+    State utf32State = utf32.getInitialState();
+    pending.add(utf32State);
+    Automaton utf8 = new Automaton();
+    utf8.setDeterministic(false);
+
+    State utf8State = utf8.getInitialState();
+
+    utf8States = new State[5];
+    utf8StateCount = 0;
+    utf8State.number = utf8StateCount;
+    utf8States[utf8StateCount] = utf8State;
+    utf8StateCount++;
+
+    utf8State.setAccept(utf32State.isAccept());
+
+    map[utf32State.number] = utf8State;
+    
+    while(pending.size() != 0) {
+      utf32State = pending.remove(pending.size()-1);
+      utf8State = map[utf32State.number];
+      for(int i=0;i<utf32State.numTransitions;i++) {
+        final Transition t = utf32State.transitionsArray[i];
+        final State destUTF32 = t.to;
+        State destUTF8 = map[destUTF32.number];
+        if (destUTF8 == null) {
+          destUTF8 = newUTF8State();
+          destUTF8.accept = destUTF32.accept;
+          map[destUTF32.number] = destUTF8;
+          pending.add(destUTF32);
+        }
+        convertOneEdge(utf8State, destUTF8, t.min, t.max);
+      }
+    }
+
+    utf8.setNumberedStates(utf8States, utf8StateCount);
+
+    return utf8;
+  }
+
+  private State newUTF8State() {
+    State s = new State();
+    if (utf8StateCount == utf8States.length) {
+      final State[] newArray = new State[ArrayUtil.oversize(1+utf8StateCount, RamUsageEstimator.NUM_BYTES_OBJ_REF)];
+      System.arraycopy(utf8States, 0, newArray, 0, utf8StateCount);
+      utf8States = newArray;
+    }
+    utf8States[utf8StateCount] = s;
+    s.number = utf8StateCount;
+    utf8StateCount++;
+    return s;
+  }
+
+  public static void main(String[] args) {
+    final int startCode = Integer.parseInt(args[0]);
+    final int endCode = Integer.parseInt(args[1]);
+
+    Automaton a = new Automaton();
+    State start = a.getInitialState();
+    State end = new State();
+    end.setAccept(true);
+    
+    UTF32ToUTF8 converter = new UTF32ToUTF8();
+    converter.convertOneEdge(start, end, startCode, endCode);
+  }
+}

Propchange: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java
------------------------------------------------------------------------------
    svn:eol-style = native