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 2014/06/17 00:23:13 UTC
svn commit: r1603012 [2/4] - in /lucene/dev/branches/lucene5752:
lucene/analysis/common/src/java/org/apache/lucene/analysis/hunspell/
lucene/analysis/common/src/test/org/apache/lucene/analysis/core/
lucene/codecs/src/java/org/apache/lucene/codecs/memor...
Added: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java?rev=1603012&view=auto
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java (added)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java Mon Jun 16 22:23:11 2014
@@ -0,0 +1,1285 @@
+/*
+ * dk.brics.automaton
+ *
+ * Copyright (c) 2001-2009 Anders Moeller
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.apache.lucene.util.automaton;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.RamUsageEstimator;
+
+/**
+ * Automata operations.
+ *
+ * @lucene.experimental
+ */
+final public class Operations {
+
+ private Operations() {}
+
+ /**
+ * Returns an automaton that accepts the concatenation of the languages of the
+ * given automata.
+ * <p>
+ * Complexity: linear in total number of states.
+ */
+ static public Automaton concatenate(Automaton a1, Automaton a2) {
+ return concatenate(Arrays.asList(a1, a2));
+ }
+
+ /**
+ * Returns an automaton that accepts the concatenation of the languages of the
+ * given automata.
+ * <p>
+ * Complexity: linear in total number of states.
+ */
+ static public Automaton concatenate(List<Automaton> l) {
+ Automaton result = new Automaton();
+
+ // First pass: create all states
+ for(Automaton a : l) {
+ if (a.getNumStates() == 0) {
+ result.finishState();
+ return result;
+ }
+ int numStates = a.getNumStates();
+ for(int s=0;s<numStates;s++) {
+ result.createState();
+ }
+ }
+
+ // Second pass: add transitions, carefully linking accept
+ // states of A to init state of next A:
+ int stateOffset = 0;
+ Transition t = new Transition();
+ for(int i=0;i<l.size();i++) {
+ Automaton a = l.get(i);
+ int numStates = a.getNumStates();
+
+ Automaton nextA = (i == l.size()-1) ? null : l.get(i+1);
+
+ for(int s=0;s<numStates;s++) {
+ int numTransitions = a.initTransition(s, t);
+ for(int j=0;j<numTransitions;j++) {
+ a.getNextTransition(t);
+ result.addTransition(stateOffset + s, stateOffset + t.dest, t.min, t.max);
+ }
+
+ if (a.isAccept(s)) {
+ Automaton followA = nextA;
+ int followOffset = stateOffset;
+ int upto = i+1;
+ while (true) {
+ if (followA != null) {
+ // Adds a "virtual" epsilon transition:
+ numTransitions = followA.initTransition(0, t);
+ for(int j=0;j<numTransitions;j++) {
+ followA.getNextTransition(t);
+ result.addTransition(stateOffset + s, followOffset + numStates + t.dest, t.min, t.max);
+ }
+ if (followA.isAccept(0)) {
+ // Keep chaining if followA accepts empty string
+ followOffset += followA.getNumStates();
+ followA = (upto == l.size()-1) ? null : l.get(upto+1);
+ upto++;
+ } else {
+ break;
+ }
+ } else {
+ result.setAccept(stateOffset + s, true);
+ break;
+ }
+ }
+ }
+ }
+
+ stateOffset += numStates;
+ }
+
+ if (result.getNumStates() == 0) {
+ result.createState();
+ }
+
+ result.finishState();
+
+ return result;
+ }
+
+ /**
+ * Returns an automaton that accepts the union of the empty string and the
+ * language of the given automaton.
+ * <p>
+ * Complexity: linear in number of states.
+ */
+ static public Automaton optional(Automaton a) {
+ Automaton result = new Automaton();
+ result.createState();
+ result.setAccept(0, true);
+ if (a.getNumStates() > 0) {
+ result.copy(a);
+ result.addEpsilon(0, 1);
+ }
+ result.finishState();
+ return result;
+ }
+
+ /**
+ * Returns an automaton that accepts the Kleene star (zero or more
+ * concatenated repetitions) of the language of the given automaton. Never
+ * modifies the input automaton language.
+ * <p>
+ * Complexity: linear in number of states.
+ */
+ static public Automaton repeat(Automaton a) {
+ Automaton.Builder builder = new Automaton.Builder();
+ builder.createState();
+ builder.setAccept(0, true);
+ builder.copy(a);
+
+ Transition t = new Transition();
+ int count = a.initTransition(0, t);
+ for(int i=0;i<count;i++) {
+ a.getNextTransition(t);
+ builder.addTransition(0, t.dest+1, t.min, t.max);
+ }
+
+ int numStates = a.getNumStates();
+ for(int s=0;s<numStates;s++) {
+ if (a.isAccept(s)) {
+ count = a.initTransition(0, t);
+ for(int i=0;i<count;i++) {
+ a.getNextTransition(t);
+ builder.addTransition(s+1, t.dest+1, t.min, t.max);
+ }
+ }
+ }
+
+ return builder.finish();
+ }
+
+ /**
+ * Returns an automaton that accepts <code>min</code> or more concatenated
+ * repetitions of the language of the given automaton.
+ * <p>
+ * Complexity: linear in number of states and in <code>min</code>.
+ */
+ static public Automaton repeat(Automaton a, int min) {
+ if (min == 0) {
+ return repeat(a);
+ }
+ List<Automaton> as = new ArrayList<>();
+ while (min-- > 0) {
+ as.add(a);
+ }
+ as.add(repeat(a));
+ return concatenate(as);
+ }
+
+ /**
+ * Returns an automaton that accepts between <code>min</code> and
+ * <code>max</code> (including both) concatenated repetitions of the language
+ * of the given automaton.
+ * <p>
+ * Complexity: linear in number of states and in <code>min</code> and
+ * <code>max</code>.
+ */
+ static public Automaton repeat(Automaton a, int min, int max) {
+ if (min > max) {
+ return Automata.makeEmpty();
+ }
+
+ Automaton b;
+ if (min == 0) {
+ b = Automata.makeEmptyString();
+ } else if (min == 1) {
+ b = new Automaton();
+ b.copy(a);
+ } else {
+ List<Automaton> as = new ArrayList<>();
+ for(int i=0;i<min;i++) {
+ as.add(a);
+ }
+ b = concatenate(as);
+ }
+
+ Set<Integer> prevAcceptStates = new HashSet<>(b.getAcceptStates());
+
+ for(int i=min;i<max;i++) {
+ int numStates = b.getNumStates();
+ b.copy(a);
+ for(int s : prevAcceptStates) {
+ b.addEpsilon(s, numStates);
+ }
+ prevAcceptStates.clear();
+ for(int s : a.getAcceptStates()) {
+ prevAcceptStates.add(numStates+s);
+ }
+ }
+
+ b.finishState();
+
+ return b;
+ }
+
+ /**
+ * Returns a (deterministic) automaton that accepts the complement of the
+ * language of the given automaton.
+ * <p>
+ * Complexity: linear in number of states (if already deterministic).
+ */
+ static public Automaton complement(Automaton a) {
+ a = determinize(a).totalize();
+ int numStates = a.getNumStates();
+ for (int p=0;p<numStates;p++) {
+ a.setAccept(p, !a.isAccept(p));
+ }
+ return removeDeadStates(a);
+ }
+
+ /**
+ * Returns a (deterministic) automaton that accepts the intersection of the
+ * language of <code>a1</code> and the complement of the language of
+ * <code>a2</code>. As a side-effect, the automata may be determinized, if not
+ * already deterministic.
+ * <p>
+ * Complexity: quadratic in number of states (if already deterministic).
+ */
+ static public Automaton minus(Automaton a1, Automaton a2) {
+ if (Operations.isEmpty(a1) || a1 == a2) {
+ return Automata.makeEmpty();
+ }
+ if (Operations.isEmpty(a2)) {
+ return a1;
+ }
+ return intersection(a1, complement(a2));
+ }
+
+ /**
+ * Returns an automaton that accepts the intersection of the languages of the
+ * given automata. Never modifies the input automata languages.
+ * <p>
+ * Complexity: quadratic in number of states.
+ */
+ static public Automaton intersection(Automaton a1, Automaton a2) {
+ if (a1 == a2) {
+ return a1;
+ }
+ if (a1.getNumStates() == 0) {
+ return a1;
+ }
+ if (a2.getNumStates() == 0) {
+ return a2;
+ }
+ Transition[][] transitions1 = a1.getSortedTransitions();
+ Transition[][] transitions2 = a2.getSortedTransitions();
+ Automaton c = new Automaton();
+ c.createState();
+ LinkedList<StatePair> worklist = new LinkedList<>();
+ HashMap<StatePair,StatePair> newstates = new HashMap<>();
+ StatePair p = new StatePair(0, 0, 0);
+ worklist.add(p);
+ newstates.put(p, p);
+ while (worklist.size() > 0) {
+ p = worklist.removeFirst();
+ c.setAccept(p.s, a1.isAccept(p.s1) && a2.isAccept(p.s2));
+ Transition[] t1 = transitions1[p.s1];
+ Transition[] t2 = transitions2[p.s2];
+ for (int n1 = 0, b2 = 0; n1 < t1.length; n1++) {
+ while (b2 < t2.length && t2[b2].max < t1[n1].min)
+ b2++;
+ for (int n2 = b2; n2 < t2.length && t1[n1].max >= t2[n2].min; n2++)
+ if (t2[n2].max >= t1[n1].min) {
+ StatePair q = new StatePair(t1[n1].dest, t2[n2].dest);
+ StatePair r = newstates.get(q);
+ if (r == null) {
+ q.s = c.createState();
+ worklist.add(q);
+ newstates.put(q, q);
+ r = q;
+ }
+ 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;
+ c.addTransition(p.s, r.s, min, max);
+ }
+ }
+ }
+ c.finishState();
+
+ return removeDeadStates(c);
+ }
+
+ /** Returns true if these two automata accept exactly the
+ * same language. This is a costly computation! Note
+ * also that a1 and a2 will be determinized as a side
+ * effect. Both automata must be determinized and have
+ * no dead states! */
+ public static boolean sameLanguage(Automaton a1, Automaton a2) {
+ if (a1 == a2) {
+ return true;
+ }
+ return subsetOf(a2, a1) && subsetOf(a1, a2);
+ }
+
+ // TODO: move to test-framework?
+ /** Returns true if this automaton has any states that cannot
+ * be reached from the initial state or cannot reach an accept state.
+ * Cost is O(numTransitions+numStates). */
+ public static boolean hasDeadStates(Automaton a) {
+ BitSet liveStates = getLiveStates(a);
+ int numLive = liveStates.cardinality();
+ int numStates = a.getNumStates();
+ assert numLive <= numStates: "numLive=" + numLive + " numStates=" + numStates + " " + liveStates;
+ return numLive < numStates;
+ }
+
+ // TODO: move to test-framework?
+ /** Returns true if there are dead states reachable from an initial state. */
+ public static boolean hasDeadStatesFromInitial(Automaton a) {
+ BitSet reachableFromInitial = getLiveStatesFromInitial(a);
+ BitSet reachableFromAccept = getLiveStatesToAccept(a);
+ reachableFromInitial.andNot(reachableFromAccept);
+ return reachableFromInitial.isEmpty() == false;
+ }
+
+ // TODO: move to test-framework?
+ /** Returns true if there are dead states that reach an accept state. */
+ public static boolean hasDeadStatesToAccept(Automaton a) {
+ BitSet reachableFromInitial = getLiveStatesFromInitial(a);
+ BitSet reachableFromAccept = getLiveStatesToAccept(a);
+ reachableFromAccept.andNot(reachableFromInitial);
+ return reachableFromAccept.isEmpty() == false;
+ }
+
+ /**
+ * Returns true if the language of <code>a1</code> is a subset of the language
+ * of <code>a2</code>. Both automata must be determinized and must have no dead
+ * states.
+ * <p>
+ * Complexity: quadratic in number of states.
+ */
+ public static boolean subsetOf(Automaton a1, Automaton a2) {
+ if (a1.isDeterministic() == false) {
+ throw new IllegalArgumentException("a1 must be deterministic");
+ }
+ if (a2.isDeterministic() == false) {
+ throw new IllegalArgumentException("a2 must be deterministic");
+ }
+ assert hasDeadStatesFromInitial(a1) == false;
+ assert hasDeadStatesFromInitial(a2) == false;
+ if (a1.getNumStates() == 0) {
+ // Empty language is alwyas a subset of any other language
+ return true;
+ } else if (a2.getNumStates() == 0) {
+ return isEmpty(a1);
+ }
+
+ // TODO: cutover to iterators instead
+ Transition[][] transitions1 = a1.getSortedTransitions();
+ Transition[][] transitions2 = a2.getSortedTransitions();
+ LinkedList<StatePair> worklist = new LinkedList<>();
+ HashSet<StatePair> visited = new HashSet<>();
+ StatePair p = new StatePair(0, 0);
+ worklist.add(p);
+ visited.add(p);
+ while (worklist.size() > 0) {
+ p = worklist.removeFirst();
+ if (a1.isAccept(p.s1) && a2.isAccept(p.s2) == false) {
+ return false;
+ }
+ Transition[] t1 = transitions1[p.s1];
+ Transition[] t2 = transitions2[p.s2];
+ 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_CODE_POINT) {
+ min1 = t2[n2].max + 1;
+ } else {
+ min1 = Character.MAX_CODE_POINT;
+ max1 = Character.MIN_CODE_POINT;
+ }
+ StatePair q = new StatePair(t1[n1].dest, t2[n2].dest);
+ if (!visited.contains(q)) {
+ worklist.add(q);
+ visited.add(q);
+ }
+ }
+ if (min1 <= max1) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Returns an automaton that accepts the union of the languages of the given
+ * automata.
+ * <p>
+ * Complexity: linear in number of states.
+ */
+ public static Automaton union(Automaton a1, Automaton a2) {
+ return union(Arrays.asList(a1, a2));
+ }
+
+ public static Automaton union(Collection<Automaton> l) {
+ Automaton result = new Automaton();
+
+ // Create initial state:
+ result.createState();
+
+ // Copy over all automata
+ Transition t = new Transition();
+ for(Automaton a : l) {
+ result.copy(a);
+ }
+
+ // Add epsilon transition from new initial state
+ int stateOffset = 1;
+ for(Automaton a : l) {
+ if (a.getNumStates() == 0) {
+ continue;
+ }
+ result.addEpsilon(0, stateOffset);
+ stateOffset += a.getNumStates();
+ }
+
+ result.finishState();
+
+ return result;
+ }
+
+ // Simple custom ArrayList<Transition>
+ private final static class TransitionList {
+ // dest, min, max
+ int[] transitions = new int[3];
+ int next;
+
+ public void add(Transition t) {
+ if (transitions.length < next+3) {
+ transitions = ArrayUtil.grow(transitions, next+3);
+ }
+ transitions[next] = t.dest;
+ transitions[next+1] = t.min;
+ transitions[next+2] = t.max;
+ next += 3;
+ }
+ }
+
+ // 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();
+
+ @Override
+ public int compareTo(PointTransitions other) {
+ return point - other.point;
+ }
+
+ public void reset(int point) {
+ this.point = point;
+ ends.next = 0;
+ starts.next = 0;
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ return ((PointTransitions) other).point == point;
+ }
+
+ @Override
+ 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<>();
+ 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_OBJECT_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() {
+ // Tim sort performs well on already sorted arrays:
+ if (count > 1) ArrayUtil.timSort(points, 0, count);
+ }
+
+ public void add(Transition t) {
+ find(t.min).starts.add(t);
+ find(1+t.max).ends.add(t);
+ }
+
+ @Override
+ 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.next/3).append(',').append(points[i].ends.next/3);
+ }
+ return s.toString();
+ }
+ }
+
+ /**
+ * Determinizes the given automaton.
+ * <p>
+ * Worst case complexity: exponential in number of states.
+ */
+ public static Automaton determinize(Automaton a) {
+ if (a.isDeterministic()) {
+ // Already determinized
+ return a;
+ }
+ if (a.getNumStates() <= 1) {
+ // Already determinized
+ return a;
+ }
+
+ // subset construction
+ Automaton.Builder b = new Automaton.Builder();
+
+ //System.out.println("DET:");
+ //a.writeDot("/l/la/lucene/core/detin.dot");
+
+ SortedIntSet.FrozenIntSet initialset = new SortedIntSet.FrozenIntSet(0, 0);
+
+ // Create state 0:
+ b.createState();
+
+ LinkedList<SortedIntSet.FrozenIntSet> worklist = new LinkedList<>();
+ Map<SortedIntSet.FrozenIntSet,Integer> newstate = new HashMap<>();
+
+ worklist.add(initialset);
+
+ b.setAccept(0, a.isAccept(0));
+ newstate.put(initialset, 0);
+
+ int newStateUpto = 0;
+ int[] newStatesArray = new int[5];
+ newStatesArray[newStateUpto] = 0;
+ newStateUpto++;
+
+ // like Set<Integer,PointTransitions>
+ final PointTransitionSet points = new PointTransitionSet();
+
+ // like SortedMap<Integer,Integer>
+ final SortedIntSet statesSet = new SortedIntSet(5);
+
+ Transition t = new Transition();
+
+ while (worklist.size() > 0) {
+ SortedIntSet.FrozenIntSet s = worklist.removeFirst();
+ //System.out.println("det: pop set=" + s);
+
+ // Collate all outgoing transitions by min/1+max:
+ for(int i=0;i<s.values.length;i++) {
+ final int s0 = s.values[i];
+ int numTransitions = a.getNumTransitions(s0);
+ a.initTransition(s0, t);
+ for(int j=0;j<numTransitions;j++) {
+ a.getNextTransition(t);
+ points.add(t);
+ }
+ }
+
+ if (points.count == 0) {
+ // No outgoing transitions -- skip it
+ continue;
+ }
+
+ points.sort();
+
+ int lastPoint = -1;
+ int accCount = 0;
+
+ final int 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();
+
+ Integer q = newstate.get(statesSet);
+ if (q == null) {
+ q = b.createState();
+ final SortedIntSet.FrozenIntSet p = statesSet.freeze(q);
+ //System.out.println(" make new state=" + q + " -> " + p + " accCount=" + accCount);
+ worklist.add(p);
+ b.setAccept(q, accCount > 0);
+ newstate.put(p, q);
+ } else {
+ assert (accCount > 0 ? true:false) == b.isAccept(q): "accCount=" + accCount + " vs existing accept=" +
+ b.isAccept(q) + " states=" + statesSet;
+ }
+
+ // System.out.println(" add trans src=" + r + " dest=" + q + " min=" + lastPoint + " max=" + (point-1));
+
+ b.addTransition(r, q, lastPoint, point-1);
+ }
+
+ // process transitions that end on this point
+ // (closes an overlapping interval)
+ int[] transitions = points.points[i].ends.transitions;
+ int limit = points.points[i].ends.next;
+ for(int j=0;j<limit;j+=3) {
+ int dest = transitions[j];
+ statesSet.decr(dest);
+ accCount -= a.isAccept(dest) ? 1:0;
+ }
+ points.points[i].ends.next = 0;
+
+ // process transitions that start on this point
+ // (opens a new interval)
+ transitions = points.points[i].starts.transitions;
+ limit = points.points[i].starts.next;
+ for(int j=0;j<limit;j+=3) {
+ int dest = transitions[j];
+ statesSet.incr(dest);
+ accCount += a.isAccept(dest) ? 1:0;
+ }
+ lastPoint = point;
+ points.points[i].starts.next = 0;
+ }
+ points.reset();
+ assert statesSet.upto == 0: "upto=" + statesSet.upto;
+ }
+
+ Automaton result = b.finish();
+ assert result.isDeterministic();
+ return result;
+ }
+
+ /**
+ * Returns true if the given automaton accepts no strings.
+ */
+ public static boolean isEmpty(Automaton a) {
+ if (a.getNumStates() == 0) {
+ // Common case: no states
+ return true;
+ }
+ if (a.isAccept(0) == false && a.getNumTransitions(0) == 0) {
+ // Common case: just one initial state
+ return true;
+ }
+ if (a.isAccept(0) == true) {
+ // Apparently common case: it accepts the damned empty string
+ return false;
+ }
+
+ LinkedList<Integer> workList = new LinkedList<>();
+ BitSet seen = new BitSet(a.getNumStates());
+ workList.add(0);
+ seen.set(0);
+
+ Transition t = new Transition();
+ while (workList.isEmpty() == false) {
+ int state = workList.removeFirst();
+ if (a.isAccept(state)) {
+ return false;
+ }
+ int count = a.initTransition(state, t);
+ for(int i=0;i<count;i++) {
+ a.getNextTransition(t);
+ if (seen.get(t.dest) == false) {
+ workList.add(t.dest);
+ seen.set(t.dest);
+ }
+ }
+ }
+
+ return true;
+ }
+
+ /**
+ * Returns true if the given automaton accepts all strings. The automaton must be minimized.
+ */
+ public static boolean isTotal(Automaton a) {
+ if (a.isAccept(0) && a.getNumTransitions(0) == 1) {
+ Transition t = new Transition();
+ a.getTransition(0, 0, t);
+ return t.dest == 0 && t.min == Character.MIN_CODE_POINT
+ && t.max == Character.MAX_CODE_POINT;
+ }
+ return false;
+ }
+
+ /**
+ * Returns true if the given string is accepted by the automaton. The input must be deterministic.
+ * <p>
+ * Complexity: linear in the length of the string.
+ * <p>
+ * <b>Note:</b> for full performance, use the {@link RunAutomaton} class.
+ */
+ public static boolean run(Automaton a, String s) {
+ assert a.isDeterministic();
+ int state = 0;
+ for (int i = 0, cp = 0; i < s.length(); i += Character.charCount(cp)) {
+ int nextState = a.step(state, cp = s.codePointAt(i));
+ if (nextState == -1) {
+ return false;
+ }
+ state = nextState;
+ }
+ return a.isAccept(state);
+ }
+
+ /**
+ * Returns true if the given string (expressed as unicode codepoints) is accepted by the automaton. The input must be deterministic.
+ * <p>
+ * Complexity: linear in the length of the string.
+ * <p>
+ * <b>Note:</b> for full performance, use the {@link RunAutomaton} class.
+ */
+ public static boolean run(Automaton a, IntsRef s) {
+ assert a.isDeterministic();
+ int state = 0;
+ for (int i=0;i<s.length;i++) {
+ int nextState = a.step(state, s.ints[s.offset+i]);
+ if (nextState == -1) {
+ return false;
+ }
+ state = nextState;
+ }
+ return a.isAccept(state);
+ }
+
+ /**
+ * Returns the set of live states. A state is "live" if an accept state is
+ * reachable from it and if it is reachable from the initial state.
+ */
+ private static BitSet getLiveStates(Automaton a) {
+ BitSet live = getLiveStatesFromInitial(a);
+ live.and(getLiveStatesToAccept(a));
+ return live;
+ }
+
+ /** Returns bitset marking states reachable from the initial state. */
+ private static BitSet getLiveStatesFromInitial(Automaton a) {
+ int numStates = a.getNumStates();
+ BitSet live = new BitSet(numStates);
+ if (numStates == 0) {
+ return live;
+ }
+ LinkedList<Integer> workList = new LinkedList<>();
+ live.set(0);
+ workList.add(0);
+
+ Transition t = new Transition();
+ while (workList.isEmpty() == false) {
+ int s = workList.removeFirst();
+ int count = a.initTransition(s, t);
+ for(int i=0;i<count;i++) {
+ a.getNextTransition(t);
+ if (live.get(t.dest) == false) {
+ live.set(t.dest);
+ workList.add(t.dest);
+ }
+ }
+ }
+
+ return live;
+ }
+
+ /** Returns bitset marking states that can reach an accept state. */
+ private static BitSet getLiveStatesToAccept(Automaton a) {
+ Automaton.Builder builder = new Automaton.Builder();
+
+ // NOTE: not quite the same thing as what SpecialOperations.reverse does:
+ Transition t = new Transition();
+ int numStates = a.getNumStates();
+ for(int s=0;s<numStates;s++) {
+ builder.createState();
+ }
+ for(int s=0;s<numStates;s++) {
+ int count = a.initTransition(s, t);
+ for(int i=0;i<count;i++) {
+ a.getNextTransition(t);
+ builder.addTransition(t.dest, s, t.min, t.max);
+ }
+ }
+ Automaton a2 = builder.finish();
+
+ LinkedList<Integer> workList = new LinkedList<>();
+ BitSet live = new BitSet(numStates);
+ for (int s : a.getAcceptStates()) {
+ live.set(s);
+ workList.add(s);
+ }
+
+ while (workList.isEmpty() == false) {
+ int s = workList.removeFirst();
+ int count = a2.initTransition(s, t);
+ for(int i=0;i<count;i++) {
+ a2.getNextTransition(t);
+ if (live.get(t.dest) == false) {
+ live.set(t.dest);
+ workList.add(t.dest);
+ }
+ }
+ }
+
+ return live;
+ }
+
+ /**
+ * Removes transitions to dead states (a state is "dead" if it is not
+ * reachable from the initial state or no accept state is reachable from it.)
+ */
+ public static Automaton removeDeadStates(Automaton a) {
+ int numStates = a.getNumStates();
+ BitSet liveSet = getLiveStates(a);
+
+ int[] map = new int[numStates];
+
+ Automaton result = new Automaton();
+ //System.out.println("liveSet: " + liveSet + " numStates=" + numStates);
+ for(int i=0;i<numStates;i++) {
+ if (liveSet.get(i)) {
+ map[i] = result.createState();
+ result.setAccept(map[i], a.isAccept(i));
+ }
+ }
+
+ Transition t = new Transition();
+
+ for (int i=0;i<numStates;i++) {
+ if (liveSet.get(i)) {
+ int numTransitions = a.initTransition(i, t);
+ // filter out transitions to dead states:
+ for(int j=0;j<numTransitions;j++) {
+ a.getNextTransition(t);
+ if (liveSet.get(t.dest)) {
+ result.addTransition(map[i], map[t.dest], t.min, t.max);
+ }
+ }
+ }
+ }
+
+ result.finishState();
+ assert hasDeadStates(result) == false;
+ return result;
+ }
+ /**
+ * Finds the largest entry whose value is less than or equal to c, or 0 if
+ * there is no such entry.
+ */
+ static int findIndex(int c, int[] points) {
+ int a = 0;
+ int b = points.length;
+ while (b - a > 1) {
+ int d = (a + b) >>> 1;
+ if (points[d] > c) b = d;
+ else if (points[d] < c) a = d;
+ else return d;
+ }
+ return a;
+ }
+
+ /**
+ * Returns true if the language of this automaton is finite.
+ */
+ public static boolean isFinite(Automaton a) {
+ if (a.getNumStates() == 0) {
+ return true;
+ }
+ return isFinite(new Transition(), a, 0, new BitSet(a.getNumStates()), new BitSet(a.getNumStates()));
+ }
+
+ /**
+ * 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(Transition scratch, Automaton a, int state, BitSet path, BitSet visited) {
+ path.set(state);
+ int numTransitions = a.initTransition(state, scratch);
+ for(int t=0;t<numTransitions;t++) {
+ a.getTransition(state, t, scratch);
+ if (path.get(scratch.dest) || (!visited.get(scratch.dest) && !isFinite(scratch, a, scratch.dest, path, visited))) {
+ return false;
+ }
+ }
+ path.clear(state);
+ visited.set(state);
+ return true;
+ }
+
+ /**
+ * Returns the longest string that is a prefix of all accepted strings and
+ * visits each state at most once. The automaton must be deterministic.
+ *
+ * @return common prefix
+ */
+ public static String getCommonPrefix(Automaton a) {
+ if (a.isDeterministic() == false) {
+ throw new IllegalArgumentException("input automaton must be deterministic");
+ }
+ StringBuilder b = new StringBuilder();
+ HashSet<Integer> visited = new HashSet<>();
+ int s = 0;
+ boolean done;
+ Transition t = new Transition();
+ do {
+ done = true;
+ visited.add(s);
+ if (a.isAccept(s) == false && a.getNumTransitions(s) == 1) {
+ a.getTransition(s, 0, t);
+ if (t.min == t.max && !visited.contains(t.dest)) {
+ b.appendCodePoint(t.min);
+ s = t.dest;
+ done = false;
+ }
+ }
+ } while (!done);
+
+ return b.toString();
+ }
+
+ public static BytesRef getCommonPrefixBytesRef(Automaton a) {
+ BytesRef ref = new BytesRef(10);
+ HashSet<Integer> visited = new HashSet<>();
+ int s = 0;
+ boolean done;
+ Transition t = new Transition();
+ do {
+ done = true;
+ visited.add(s);
+ if (a.isAccept(s) == false && a.getNumTransitions(s) == 1) {
+ a.getTransition(s, 0, t);
+ if (t.min == t.max && !visited.contains(t.dest)) {
+ ref.grow(++ref.length);
+ ref.bytes[ref.length - 1] = (byte) t.min;
+ s = t.dest;
+ done = false;
+ }
+ }
+ } while (!done);
+
+ return ref;
+ }
+
+ public static BytesRef getCommonSuffixBytesRef(Automaton a) {
+ // reverse the language of the automaton, then reverse its common prefix.
+ Automaton r = Operations.determinize(reverse(a));
+ BytesRef ref = 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;
+ }
+ }
+
+ public static Automaton reverse(Automaton a) {
+ return reverse(a, null);
+ }
+
+ public static Automaton reverse(Automaton a, Set<Integer> initialStates) {
+
+ if (Operations.isEmpty(a)) {
+ return new Automaton();
+ }
+
+ int numStates = a.getNumStates();
+
+ // Build a new automaton with all edges reversed
+ Automaton.Builder builder = new Automaton.Builder();
+
+ // Initial node; we'll add epsilon transitions in the end:
+ builder.createState();
+
+ for(int s=0;s<numStates;s++) {
+ builder.createState();
+ }
+
+ // Old initial state becomes new accept state:
+ builder.setAccept(1, true);
+
+ Transition t = new Transition();
+ for (int s=0;s<numStates;s++) {
+ int numTransitions = a.getNumTransitions(s);
+ a.initTransition(s, t);
+ for(int i=0;i<numTransitions;i++) {
+ a.getNextTransition(t);
+ builder.addTransition(t.dest+1, s+1, t.min, t.max);
+ }
+ }
+
+ Automaton result = builder.finish();
+
+ for(int s : a.getAcceptStates()) {
+ assert s < numStates;
+ result.addEpsilon(0, s+1);
+ if (initialStates != null) {
+ initialStates.add(s+1);
+ }
+ }
+
+ result.finishState();
+
+ return result;
+ }
+
+ private static class PathNode {
+
+ /** Which state the path node ends on, whose
+ * transitions we are enumerating. */
+ public int state;
+
+ /** Which state the current transition leads to. */
+ public int to;
+
+ /** Which transition we are on. */
+ public int transition;
+
+ /** Which label we are on, in the min-max range of the
+ * current Transition */
+ public int label;
+
+ private final Transition t = new Transition();
+
+ public void resetState(Automaton a, int state) {
+ assert a.getNumTransitions(state) != 0;
+ this.state = state;
+ transition = 0;
+ a.getTransition(state, 0, t);
+ label = t.min;
+ to = t.dest;
+ }
+
+ /** Returns next label of current transition, or
+ * advances to next transition and returns its first
+ * label, if current one is exhausted. If there are
+ * no more transitions, returns -1. */
+ public int nextLabel(Automaton a) {
+ if (label > t.max) {
+ // We've exhaused the current transition's labels;
+ // move to next transitions:
+ transition++;
+ if (transition >= a.getNumTransitions(state)) {
+ // We're done iterating transitions leaving this state
+ return -1;
+ }
+ a.getTransition(state, transition, t);
+ label = t.min;
+ to = t.dest;
+ }
+ return label++;
+ }
+ }
+
+ private static PathNode getNode(PathNode[] nodes, int index) {
+ assert index < nodes.length;
+ if (nodes[index] == null) {
+ nodes[index] = new PathNode();
+ }
+ return nodes[index];
+ }
+
+ // TODO: this is a dangerous method ... Automaton could be
+ // huge ... and it's better in general for caller to
+ // enumerate & process in a single walk:
+
+ /** Returns the set of accepted strings, up to at most
+ * <code>limit</code> strings. If more than <code>limit</code>
+ * strings are accepted, the first limit strings found are returned. If <code>limit</code> == -1, then
+ * the limit is infinite. If the {@link Automaton} has
+ * cycles then this method might throw {@code
+ * IllegalArgumentException} but that is not guaranteed
+ * when the limit is set. */
+ public static Set<IntsRef> getFiniteStrings(Automaton a, int limit) {
+ Set<IntsRef> results = new HashSet<>();
+
+ if (limit == -1 || limit > 0) {
+ // OK
+ } else {
+ throw new IllegalArgumentException("limit must be -1 (which means no limit), or > 0; got: " + limit);
+ }
+
+ if (a.isAccept(0)) {
+ // Special case the empty string, as usual:
+ results.add(new IntsRef());
+ }
+
+ if (a.getNumTransitions(0) > 0 && (limit == -1 || results.size() < limit)) {
+
+ int numStates = a.getNumStates();
+
+ // Tracks which states are in the current path, for
+ // cycle detection:
+ BitSet pathStates = new BitSet(numStates);
+
+ // Stack to hold our current state in the
+ // recursion/iteration:
+ PathNode[] nodes = new PathNode[4];
+
+ pathStates.set(0);
+ PathNode root = getNode(nodes, 0);
+ root.resetState(a, 0);
+
+ IntsRef string = new IntsRef(1);
+ string.length = 1;
+
+ while (string.length > 0) {
+
+ PathNode node = nodes[string.length-1];
+
+ // Get next label leaving the current node:
+ int label = node.nextLabel(a);
+
+ if (label != -1) {
+ string.ints[string.length-1] = label;
+
+ if (a.isAccept(node.to)) {
+ // This transition leads to an accept state,
+ // so we save the current string:
+ results.add(IntsRef.deepCopyOf(string));
+ if (results.size() == limit) {
+ break;
+ }
+ }
+
+ if (a.getNumTransitions(node.to) != 0) {
+ // Now recurse: the destination of this transition has
+ // outgoing transitions:
+ if (pathStates.get(node.to)) {
+ throw new IllegalArgumentException("automaton has cycles");
+ }
+ pathStates.set(node.to);
+
+ // Push node onto stack:
+ if (nodes.length == string.length) {
+ PathNode[] newNodes = new PathNode[ArrayUtil.oversize(nodes.length+1, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
+ System.arraycopy(nodes, 0, newNodes, 0, nodes.length);
+ nodes = newNodes;
+ }
+ getNode(nodes, string.length).resetState(a, node.to);
+ string.length++;
+ string.grow(string.length);
+ }
+ } else {
+ // No more transitions leaving this state,
+ // pop/return back to previous state:
+ assert pathStates.get(node.state);
+ pathStates.clear(node.state);
+ string.length--;
+ }
+ }
+ }
+
+ return results;
+ }
+}
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RegExp.java Mon Jun 16 22:23:11 2014
@@ -422,12 +422,12 @@ public class RegExp {
* Constructs new <code>Automaton</code> from this <code>RegExp</code>. Same
* as <code>toAutomaton(null)</code> (empty automaton map).
*/
- public LightAutomaton toLightAutomaton() {
- return toLightAutomaton(null, null);
+ public Automaton toAutomaton() {
+ return toAutomaton(null, null);
}
/**
- * Constructs new <code>LightAutomaton</code> from this <code>RegExp</code>. The
+ * Constructs new <code>Automaton</code> from this <code>RegExp</code>. The
* constructed automaton is minimal and deterministic and has no transitions
* to dead states.
*
@@ -435,9 +435,9 @@ public class RegExp {
* @exception IllegalArgumentException if this regular expression uses a named
* identifier that is not available from the automaton provider
*/
- public LightAutomaton toLightAutomaton(LightAutomatonProvider automaton_provider)
+ public Automaton toAutomaton(AutomatonProvider automaton_provider)
throws IllegalArgumentException {
- return toLightAutomaton(null, automaton_provider);
+ return toAutomaton(null, automaton_provider);
}
/**
@@ -446,26 +446,26 @@ public class RegExp {
* to dead states.
*
* @param automata a map from automaton identifiers to automata (of type
- * <code>LightAutomaton</code>).
+ * <code>Automaton</code>).
* @exception IllegalArgumentException if this regular expression uses a named
* identifier that does not occur in the automaton map
*/
- public LightAutomaton toLightAutomaton(Map<String,LightAutomaton> automata)
+ public Automaton toAutomaton(Map<String,Automaton> automata)
throws IllegalArgumentException {
- return toLightAutomaton(automata, null);
+ return toAutomaton(automata, null);
}
- private LightAutomaton toLightAutomaton(Map<String,LightAutomaton> automata,
- LightAutomatonProvider automaton_provider) throws IllegalArgumentException {
- List<LightAutomaton> list;
- LightAutomaton a = null;
+ private Automaton toAutomaton(Map<String,Automaton> automata,
+ AutomatonProvider automaton_provider) throws IllegalArgumentException {
+ List<Automaton> list;
+ Automaton a = null;
switch (kind) {
case REGEXP_UNION:
list = new ArrayList<>();
findLeaves(exp1, Kind.REGEXP_UNION, list, automata, automaton_provider);
findLeaves(exp2, Kind.REGEXP_UNION, list, automata, automaton_provider);
- a = BasicOperations.unionLight(list);
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.union(list);
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_CONCATENATION:
list = new ArrayList<>();
@@ -473,55 +473,55 @@ public class RegExp {
automaton_provider);
findLeaves(exp2, Kind.REGEXP_CONCATENATION, list, automata,
automaton_provider);
- a = BasicOperations.concatenateLight(list);
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.concatenate(list);
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_INTERSECTION:
- a = BasicOperations.intersectionLight(
- exp1.toLightAutomaton(automata, automaton_provider),
- exp2.toLightAutomaton(automata, automaton_provider));
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.intersection(
+ exp1.toAutomaton(automata, automaton_provider),
+ exp2.toAutomaton(automata, automaton_provider));
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_OPTIONAL:
- a = BasicOperations.optionalLight(exp1.toLightAutomaton(automata, automaton_provider));
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.optional(exp1.toAutomaton(automata, automaton_provider));
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_REPEAT:
- a = BasicOperations.repeatLight(exp1.toLightAutomaton(automata, automaton_provider));
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.repeat(exp1.toAutomaton(automata, automaton_provider));
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_REPEAT_MIN:
- a = BasicOperations.repeatLight(exp1.toLightAutomaton(automata, automaton_provider), min);
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.repeat(exp1.toAutomaton(automata, automaton_provider), min);
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_REPEAT_MINMAX:
- a = BasicOperations.repeatLight(exp1.toLightAutomaton(automata, automaton_provider), min, max);
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.repeat(exp1.toAutomaton(automata, automaton_provider), min, max);
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_COMPLEMENT:
- a = BasicOperations.complementLight(exp1.toLightAutomaton(automata, automaton_provider));
- a = MinimizationOperationsLight.minimize(a);
+ a = Operations.complement(exp1.toAutomaton(automata, automaton_provider));
+ a = MinimizationOperations.minimize(a);
break;
case REGEXP_CHAR:
- a = BasicAutomata.makeCharLight(c);
+ a = Automata.makeChar(c);
break;
case REGEXP_CHAR_RANGE:
- a = BasicAutomata.makeCharRangeLight(from, to);
+ a = Automata.makeCharRange(from, to);
break;
case REGEXP_ANYCHAR:
- a = BasicAutomata.makeAnyCharLight();
+ a = Automata.makeAnyChar();
break;
case REGEXP_EMPTY:
- a = BasicAutomata.makeEmptyLight();
+ a = Automata.makeEmpty();
break;
case REGEXP_STRING:
- a = BasicAutomata.makeStringLight(s);
+ a = Automata.makeString(s);
break;
case REGEXP_ANYSTRING:
- a = BasicAutomata.makeAnyStringLight();
+ a = Automata.makeAnyString();
break;
case REGEXP_AUTOMATON:
- LightAutomaton aa = null;
+ Automaton aa = null;
if (automata != null) {
aa = automata.get(s);
}
@@ -538,19 +538,19 @@ public class RegExp {
a = aa;
break;
case REGEXP_INTERVAL:
- a = BasicAutomata.makeIntervalLight(min, max, digits);
+ a = Automata.makeInterval(min, max, digits);
break;
}
return a;
}
- private void findLeaves(RegExp exp, Kind kind, List<LightAutomaton> list,
- Map<String,LightAutomaton> automata, LightAutomatonProvider automaton_provider) {
+ private void findLeaves(RegExp exp, Kind kind, List<Automaton> list,
+ Map<String,Automaton> automata, AutomatonProvider automaton_provider) {
if (exp.kind == kind) {
findLeaves(exp.exp1, kind, list, automata, automaton_provider);
findLeaves(exp.exp2, kind, list, automata, automaton_provider);
} else {
- list.add(exp.toLightAutomaton(automata, automaton_provider));
+ list.add(exp.toAutomaton(automata, automaton_provider));
}
}
Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java Mon Jun 16 22:23:11 2014
@@ -37,7 +37,7 @@ import java.util.Arrays;
* @lucene.experimental
*/
public abstract class RunAutomaton {
- final LightAutomaton automaton;
+ final Automaton automaton;
final int maxInterval;
final int size;
final boolean[] accept;
@@ -66,10 +66,10 @@ public abstract class RunAutomaton {
if (j + 1 < points.length) max = (points[j + 1] - 1);
else max = maxInterval;
b.append(" ");
- LightAutomaton.appendCharString(min, b);
+ Automaton.appendCharString(min, b);
if (min != max) {
b.append("-");
- LightAutomaton.appendCharString(max, b);
+ Automaton.appendCharString(max, b);
}
b.append(" -> ").append(k).append("\n");
}
@@ -111,7 +111,7 @@ public abstract class RunAutomaton {
* Gets character class of given codepoint
*/
final int getCharClass(int c) {
- return SpecialOperations.findIndex(c, points);
+ return Operations.findIndex(c, points);
}
/**
@@ -120,10 +120,10 @@ public abstract class RunAutomaton {
*
* @param a an automaton
*/
- public RunAutomaton(LightAutomaton a, int maxInterval, boolean tableize) {
+ public RunAutomaton(Automaton a, int maxInterval, boolean tableize) {
this.maxInterval = maxInterval;
//System.out.println("before det a=" + a.getNumStates());
- a = BasicOperations.determinize(a);
+ a = Operations.determinize(a);
this.automaton = a;
//System.out.println("AFTER DET tableize= " + tableize + ": ");
//System.out.println(a.toDot());
Copied: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/SortedIntSet.java (from r1602966, lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/SortedIntSetLight.java)
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/SortedIntSet.java?p2=lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/SortedIntSet.java&p1=lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/SortedIntSetLight.java&r1=1602966&r2=1603012&rev=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/SortedIntSetLight.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/SortedIntSet.java Mon Jun 16 22:23:11 2014
@@ -25,7 +25,7 @@ import org.apache.lucene.util.RamUsageEs
// Just holds a set of int[] states, plus a corresponding
// int[] count per state. Used by
// BasicOperations.determinize
-final class SortedIntSetLight {
+final class SortedIntSet {
int[] values;
int[] counts;
int upto;
@@ -41,7 +41,7 @@ final class SortedIntSetLight {
int state;
- public SortedIntSetLight(int capacity) {
+ public SortedIntSet(int capacity) {
values = new int[capacity];
counts = new int[capacity];
}
@@ -153,10 +153,10 @@ final class SortedIntSetLight {
}
}
- public FrozenIntSetLight freeze(int state) {
+ public FrozenIntSet freeze(int state) {
final int[] c = new int[upto];
System.arraycopy(values, 0, c, 0, upto);
- return new FrozenIntSetLight(c, hashCode, state);
+ return new FrozenIntSet(c, hashCode, state);
}
@Override
@@ -169,10 +169,10 @@ final class SortedIntSetLight {
if (_other == null) {
return false;
}
- if (!(_other instanceof FrozenIntSetLight)) {
+ if (!(_other instanceof FrozenIntSet)) {
return false;
}
- FrozenIntSetLight other = (FrozenIntSetLight) _other;
+ FrozenIntSet other = (FrozenIntSet) _other;
if (hashCode != other.hashCode) {
return false;
}
@@ -201,18 +201,18 @@ final class SortedIntSetLight {
return sb.toString();
}
- public final static class FrozenIntSetLight {
+ public final static class FrozenIntSet {
final int[] values;
final int hashCode;
final int state;
- public FrozenIntSetLight(int[] values, int hashCode, int state) {
+ public FrozenIntSet(int[] values, int hashCode, int state) {
this.values = values;
this.hashCode = hashCode;
this.state = state;
}
- public FrozenIntSetLight(int num, int state) {
+ public FrozenIntSet(int num, int state) {
this.values = new int[] {num};
this.state = state;
this.hashCode = 683+num;
@@ -228,8 +228,8 @@ final class SortedIntSetLight {
if (_other == null) {
return false;
}
- if (_other instanceof FrozenIntSetLight) {
- FrozenIntSetLight other = (FrozenIntSetLight) _other;
+ if (_other instanceof FrozenIntSet) {
+ FrozenIntSet other = (FrozenIntSet) _other;
if (hashCode != other.hashCode) {
return false;
}
@@ -242,8 +242,8 @@ final class SortedIntSetLight {
}
}
return true;
- } else if (_other instanceof SortedIntSetLight) {
- SortedIntSetLight other = (SortedIntSetLight) _other;
+ } else if (_other instanceof SortedIntSet) {
+ SortedIntSet other = (SortedIntSet) _other;
if (hashCode != other.hashCode) {
return false;
}
Copied: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/StatePair.java (from r1602966, lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightStatePair.java)
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/StatePair.java?p2=lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/StatePair.java&p1=lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightStatePair.java&r1=1602966&r2=1603012&rev=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/LightStatePair.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/StatePair.java Mon Jun 16 22:23:11 2014
@@ -34,12 +34,12 @@ package org.apache.lucene.util.automaton
*
* @lucene.experimental
*/
-public class LightStatePair {
+public class StatePair {
int s;
int s1;
int s2;
- LightStatePair(int s, int s1, int s2) {
+ StatePair(int s, int s1, int s2) {
this.s = s;
this.s1 = s1;
this.s2 = s2;
@@ -51,7 +51,7 @@ public class LightStatePair {
* @param s1 first state
* @param s2 second state
*/
- public LightStatePair(int s1, int s2) {
+ public StatePair(int s1, int s2) {
this.s1 = s1;
this.s2 = s2;
this.s = -1;
@@ -66,8 +66,8 @@ public class LightStatePair {
*/
@Override
public boolean equals(Object obj) {
- if (obj instanceof LightStatePair) {
- LightStatePair p = (LightStatePair) obj;
+ if (obj instanceof StatePair) {
+ StatePair p = (StatePair) obj;
return p.s1 == s1 && p.s2 == s2;
} else return false;
}
@@ -84,6 +84,6 @@ public class LightStatePair {
@Override
public String toString() {
- return "LightStatePair(s1=" + s1 + " s2=" + s2 + ")";
+ return "StatePair(s1=" + s1 + " s2=" + s2 + ")";
}
}
Copied: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java (from r1602966, lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8Light.java)
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java?p2=lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java&p1=lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8Light.java&r1=1602966&r2=1603012&rev=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8Light.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/UTF32ToUTF8.java Mon Jun 16 22:23:11 2014
@@ -28,7 +28,7 @@ import java.util.List;
* Converts UTF-32 automata to the equivalent UTF-8 representation.
* @lucene.internal
*/
-public final class UTF32ToUTF8Light {
+public final class UTF32ToUTF8 {
// Unicode boundaries for UTF8 bytes 1,2,3,4
private static final int[] startCodes = new int[] {0, 128, 2048, 65536};
@@ -255,14 +255,14 @@ public final class UTF32ToUTF8Light {
}
}
- LightAutomaton.Builder utf8;
+ Automaton.Builder utf8;
/** 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 LightAutomaton convert(LightAutomaton utf32) {
+ public Automaton convert(Automaton utf32) {
if (utf32.getNumStates() == 0) {
return utf32;
}
@@ -273,7 +273,7 @@ public final class UTF32ToUTF8Light {
List<Integer> pending = new ArrayList<>();
int utf32State = 0;
pending.add(utf32State);
- utf8 = new LightAutomaton.Builder();
+ utf8 = new Automaton.Builder();
int utf8State = utf8.createState();
Modified: lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java Mon Jun 16 22:23:11 2014
@@ -29,9 +29,9 @@ import org.apache.lucene.analysis.tokena
import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
import org.apache.lucene.analysis.tokenattributes.PositionLengthAttribute;
-import org.apache.lucene.util.automaton.BasicAutomata;
-import org.apache.lucene.util.automaton.BasicOperations;
-import org.apache.lucene.util.automaton.LightAutomaton;
+import org.apache.lucene.util.automaton.Automata;
+import org.apache.lucene.util.automaton.Operations;
+import org.apache.lucene.util.automaton.Automaton;
public class TestGraphTokenizers extends BaseTokenStreamTestCase {
@@ -409,10 +409,10 @@ public class TestGraphTokenizers extends
new Token[] {
token("abc", 1, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton expected = s2a("abc");
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton expected = s2a("abc");
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testMultipleHoles() throws Exception {
@@ -421,10 +421,10 @@ public class TestGraphTokenizers extends
token("a", 1, 1),
token("b", 3, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton expected = join(s2a("a"), SEP_A, HOLE_A, SEP_A, HOLE_A, SEP_A, s2a("b"));
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton expected = join(s2a("a"), SEP_A, HOLE_A, SEP_A, HOLE_A, SEP_A, s2a("b"));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testSynOverMultipleHoles() throws Exception {
@@ -434,12 +434,12 @@ public class TestGraphTokenizers extends
token("x", 0, 3),
token("b", 3, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton a1 = join(s2a("a"), SEP_A, HOLE_A, SEP_A, HOLE_A, SEP_A, s2a("b"));
- final LightAutomaton a2 = join(s2a("x"), SEP_A, s2a("b"));
- final LightAutomaton expected = BasicOperations.unionLight(a1, a2);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton a1 = join(s2a("a"), SEP_A, HOLE_A, SEP_A, HOLE_A, SEP_A, s2a("b"));
+ final Automaton a2 = join(s2a("x"), SEP_A, s2a("b"));
+ final Automaton expected = Operations.union(a1, a2);
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
// for debugging!
@@ -453,25 +453,25 @@ public class TestGraphTokenizers extends
}
*/
- private static final LightAutomaton SEP_A = BasicAutomata.makeCharLight(TokenStreamToAutomaton.POS_SEP);
- private static final LightAutomaton HOLE_A = BasicAutomata.makeCharLight(TokenStreamToAutomaton.HOLE);
+ private static final Automaton SEP_A = Automata.makeChar(TokenStreamToAutomaton.POS_SEP);
+ private static final Automaton HOLE_A = Automata.makeChar(TokenStreamToAutomaton.HOLE);
- private LightAutomaton join(String ... strings) {
- List<LightAutomaton> as = new ArrayList<>();
+ private Automaton join(String ... strings) {
+ List<Automaton> as = new ArrayList<>();
for(String s : strings) {
as.add(s2a(s));
as.add(SEP_A);
}
as.remove(as.size()-1);
- return BasicOperations.concatenateLight(as);
+ return Operations.concatenate(as);
}
- private LightAutomaton join(LightAutomaton ... as) {
- return BasicOperations.concatenateLight(Arrays.asList(as));
+ private Automaton join(Automaton ... as) {
+ return Operations.concatenate(Arrays.asList(as));
}
- private LightAutomaton s2a(String s) {
- return BasicAutomata.makeStringLight(s);
+ private Automaton s2a(String s) {
+ return Automata.makeString(s);
}
public void testTwoTokens() throws Exception {
@@ -481,12 +481,12 @@ public class TestGraphTokenizers extends
token("abc", 1, 1),
token("def", 1, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton expected = join("abc", "def");
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton expected = join("abc", "def");
//toDot(actual);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testHole() throws Exception {
@@ -496,13 +496,13 @@ public class TestGraphTokenizers extends
token("abc", 1, 1),
token("def", 2, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton expected = join(s2a("abc"), SEP_A, HOLE_A, SEP_A, s2a("def"));
+ final Automaton expected = join(s2a("abc"), SEP_A, HOLE_A, SEP_A, s2a("def"));
//toDot(actual);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testOverlappedTokensSausage() throws Exception {
@@ -513,12 +513,12 @@ public class TestGraphTokenizers extends
token("abc", 1, 1),
token("xyz", 0, 1)
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton a1 = s2a("abc");
- final LightAutomaton a2 = s2a("xyz");
- final LightAutomaton expected = BasicOperations.unionLight(a1, a2);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton a1 = s2a("abc");
+ final Automaton a2 = s2a("xyz");
+ final Automaton expected = Operations.union(a1, a2);
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testOverlappedTokensLattice() throws Exception {
@@ -529,14 +529,14 @@ public class TestGraphTokenizers extends
token("xyz", 0, 2),
token("def", 1, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton a1 = s2a("xyz");
- final LightAutomaton a2 = join("abc", "def");
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton a1 = s2a("xyz");
+ final Automaton a2 = join("abc", "def");
- final LightAutomaton expected = BasicOperations.unionLight(a1, a2);
+ final Automaton expected = Operations.union(a1, a2);
//toDot(actual);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testSynOverHole() throws Exception {
@@ -547,15 +547,15 @@ public class TestGraphTokenizers extends
token("X", 0, 2),
token("b", 2, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton a1 = BasicOperations.unionLight(
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton a1 = Operations.union(
join(s2a("a"), SEP_A, HOLE_A),
s2a("X"));
- final LightAutomaton expected = BasicOperations.concatenateLight(a1,
+ final Automaton expected = Operations.concatenate(a1,
join(SEP_A, s2a("b")));
//toDot(actual);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testSynOverHole2() throws Exception {
@@ -566,12 +566,12 @@ public class TestGraphTokenizers extends
token("abc", 0, 3),
token("def", 2, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton expected = BasicOperations.unionLight(
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton expected = Operations.union(
join(s2a("xyz"), SEP_A, HOLE_A, SEP_A, s2a("def")),
s2a("abc"));
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testOverlappedTokensLattice2() throws Exception {
@@ -583,13 +583,13 @@ public class TestGraphTokenizers extends
token("def", 1, 1),
token("ghi", 1, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton a1 = s2a("xyz");
- final LightAutomaton a2 = join("abc", "def", "ghi");
- final LightAutomaton expected = BasicOperations.unionLight(a1, a2);
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton a1 = s2a("xyz");
+ final Automaton a2 = join("abc", "def", "ghi");
+ final Automaton expected = Operations.union(a1, a2);
//toDot(actual);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
public void testToDot() throws Exception {
@@ -604,11 +604,11 @@ public class TestGraphTokenizers extends
new Token[] {
token("abc", 2, 1),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton expected = join(HOLE_A, SEP_A, s2a("abc"));
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton expected = join(HOLE_A, SEP_A, s2a("abc"));
//toDot(actual);
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
// TODO: testEndsWithHole... but we need posInc to set in TS.end()
@@ -619,10 +619,10 @@ public class TestGraphTokenizers extends
token("a", 1, 1),
token("X", 0, 10),
});
- final LightAutomaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
- final LightAutomaton expected = BasicOperations.unionLight(s2a("a"),
+ final Automaton actual = (new TokenStreamToAutomaton()).toAutomaton(ts);
+ final Automaton expected = Operations.union(s2a("a"),
s2a("X"));
- assertTrue(BasicOperations.sameLanguage(BasicOperations.determinize(BasicOperations.removeDeadStates(expected)),
- BasicOperations.determinize(BasicOperations.removeDeadStates(actual))));
+ assertTrue(Operations.sameLanguage(Operations.determinize(Operations.removeDeadStates(expected)),
+ Operations.determinize(Operations.removeDeadStates(actual))));
}
}
Modified: lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestMockAnalyzer.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestMockAnalyzer.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestMockAnalyzer.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/analysis/TestMockAnalyzer.java Mon Jun 16 22:23:11 2014
@@ -35,8 +35,8 @@ import org.apache.lucene.index.TermsEnum
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.TestUtil;
import org.apache.lucene.util.automaton.AutomatonTestUtil;
-import org.apache.lucene.util.automaton.BasicAutomata;
-import org.apache.lucene.util.automaton.BasicOperations;
+import org.apache.lucene.util.automaton.Automata;
+import org.apache.lucene.util.automaton.Operations;
import org.apache.lucene.util.automaton.CharacterRunAutomaton;
import org.apache.lucene.util.automaton.RegExp;
@@ -82,7 +82,7 @@ public class TestMockAnalyzer extends Ba
/** Test a configuration where each character is a term */
public void testSingleChar() throws Exception {
CharacterRunAutomaton single =
- new CharacterRunAutomaton(new RegExp(".").toLightAutomaton());
+ new CharacterRunAutomaton(new RegExp(".").toAutomaton());
Analyzer a = new MockAnalyzer(random(), single, false);
assertAnalyzesTo(a, "foobar",
new String[] { "f", "o", "o", "b", "a", "r" },
@@ -95,7 +95,7 @@ public class TestMockAnalyzer extends Ba
/** Test a configuration where two characters makes a term */
public void testTwoChars() throws Exception {
CharacterRunAutomaton single =
- new CharacterRunAutomaton(new RegExp("..").toLightAutomaton());
+ new CharacterRunAutomaton(new RegExp("..").toAutomaton());
Analyzer a = new MockAnalyzer(random(), single, false);
assertAnalyzesTo(a, "foobar",
new String[] { "fo", "ob", "ar"},
@@ -116,7 +116,7 @@ public class TestMockAnalyzer extends Ba
/** Test a configuration where three characters makes a term */
public void testThreeChars() throws Exception {
CharacterRunAutomaton single =
- new CharacterRunAutomaton(new RegExp("...").toLightAutomaton());
+ new CharacterRunAutomaton(new RegExp("...").toAutomaton());
Analyzer a = new MockAnalyzer(random(), single, false);
assertAnalyzesTo(a, "foobar",
new String[] { "foo", "bar"},
@@ -137,7 +137,7 @@ public class TestMockAnalyzer extends Ba
/** Test a configuration where word starts with one uppercase */
public void testUppercase() throws Exception {
CharacterRunAutomaton single =
- new CharacterRunAutomaton(new RegExp("[A-Z][a-z]*").toLightAutomaton());
+ new CharacterRunAutomaton(new RegExp("[A-Z][a-z]*").toAutomaton());
Analyzer a = new MockAnalyzer(random(), single, false);
assertAnalyzesTo(a, "FooBarBAZ",
new String[] { "Foo", "Bar", "B", "A", "Z"},
@@ -164,9 +164,9 @@ public class TestMockAnalyzer extends Ba
public void testKeep() throws Exception {
CharacterRunAutomaton keepWords =
new CharacterRunAutomaton(
- BasicOperations.complementLight(
- BasicOperations.unionLight(
- Arrays.asList(BasicAutomata.makeStringLight("foo"), BasicAutomata.makeStringLight("bar")))));
+ Operations.complement(
+ Operations.union(
+ Arrays.asList(Automata.makeString("foo"), Automata.makeString("bar")))));
Analyzer a = new MockAnalyzer(random(), MockTokenizer.SIMPLE, true, keepWords);
assertAnalyzesTo(a, "quick foo brown bar bar fox foo",
new String[] { "foo", "bar", "bar", "foo" },
@@ -175,7 +175,7 @@ public class TestMockAnalyzer extends Ba
/** Test a configuration that behaves a lot like LengthFilter */
public void testLength() throws Exception {
- CharacterRunAutomaton length5 = new CharacterRunAutomaton(new RegExp(".{5,}").toLightAutomaton());
+ CharacterRunAutomaton length5 = new CharacterRunAutomaton(new RegExp(".{5,}").toAutomaton());
Analyzer a = new MockAnalyzer(random(), MockTokenizer.WHITESPACE, true, length5);
assertAnalyzesTo(a, "ok toolong fine notfine",
new String[] { "ok", "fine" },
Modified: lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/codecs/lucene41/TestBlockPostingsFormat3.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/codecs/lucene41/TestBlockPostingsFormat3.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/codecs/lucene41/TestBlockPostingsFormat3.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/codecs/lucene41/TestBlockPostingsFormat3.java Mon Jun 16 22:23:11 2014
@@ -183,7 +183,7 @@ public class TestBlockPostingsFormat3 ex
int numIntersections = atLeast(3);
for (int i = 0; i < numIntersections; i++) {
String re = AutomatonTestUtil.randomRegexp(random());
- CompiledAutomaton automaton = new CompiledAutomaton(new RegExp(re, RegExp.NONE).toLightAutomaton());
+ CompiledAutomaton automaton = new CompiledAutomaton(new RegExp(re, RegExp.NONE).toAutomaton());
if (automaton.type == CompiledAutomaton.AUTOMATON_TYPE.NORMAL) {
// TODO: test start term too
TermsEnum leftIntersection = leftTerms.intersect(automaton, null);
Modified: lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestIndexWriter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestIndexWriter.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestIndexWriter.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestIndexWriter.java Mon Jun 16 22:23:11 2014
@@ -84,9 +84,9 @@ import org.apache.lucene.util.SetOnce;
import org.apache.lucene.util.TestUtil;
import org.apache.lucene.util.ThreadInterruptedException;
import org.apache.lucene.util.Version;
-import org.apache.lucene.util.automaton.BasicAutomata;
+import org.apache.lucene.util.automaton.Automata;
import org.apache.lucene.util.automaton.CharacterRunAutomaton;
-import org.apache.lucene.util.automaton.LightAutomaton;
+import org.apache.lucene.util.automaton.Automaton;
import org.apache.lucene.util.packed.PackedInts;
import org.junit.Test;
@@ -2006,7 +2006,7 @@ public class TestIndexWriter extends Luc
public void testStopwordsPosIncHole2() throws Exception {
// use two stopfilters for testing here
Directory dir = newDirectory();
- final LightAutomaton secondSet = BasicAutomata.makeStringLight("foobar");
+ final Automaton secondSet = Automata.makeString("foobar");
Analyzer a = new Analyzer() {
@Override
protected TokenStreamComponents createComponents(String fieldName) {
Modified: lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum.java Mon Jun 16 22:23:11 2014
@@ -33,9 +33,9 @@ import org.apache.lucene.util.LineFileDo
import org.apache.lucene.util.LuceneTestCase.SuppressCodecs;
import org.apache.lucene.util.LuceneTestCase;
import org.apache.lucene.util.TestUtil;
-import org.apache.lucene.util.automaton.BasicAutomata;
+import org.apache.lucene.util.automaton.Automata;
import org.apache.lucene.util.automaton.CompiledAutomaton;
-import org.apache.lucene.util.automaton.LightAutomaton;
+import org.apache.lucene.util.automaton.Automaton;
import org.apache.lucene.util.automaton.RegExp;
@SuppressCodecs({ "SimpleText", "Memory", "Direct" })
@@ -239,12 +239,12 @@ public class TestTermsEnum extends Lucen
final Set<String> acceptTerms = new HashSet<>();
final TreeSet<BytesRef> sortedAcceptTerms = new TreeSet<>();
final double keepPct = random().nextDouble();
- LightAutomaton a;
+ Automaton a;
if (iter == 0) {
if (VERBOSE) {
System.out.println("\nTEST: empty automaton");
}
- a = BasicAutomata.makeEmptyLight();
+ a = Automata.makeEmpty();
} else {
if (VERBOSE) {
System.out.println("\nTEST: keepPct=" + keepPct);
@@ -259,7 +259,7 @@ public class TestTermsEnum extends Lucen
acceptTerms.add(s2);
sortedAcceptTerms.add(new BytesRef(s2));
}
- a = BasicAutomata.makeStringUnionLight(sortedAcceptTerms);
+ a = Automata.makeStringUnion(sortedAcceptTerms);
}
final CompiledAutomaton c = new CompiledAutomaton(a, true, false);
@@ -738,7 +738,7 @@ public class TestTermsEnum extends Lucen
w.shutdown();
AtomicReader sub = getOnlySegmentReader(r);
Terms terms = sub.fields().terms("field");
- LightAutomaton automaton = new RegExp(".*", RegExp.NONE).toLightAutomaton();
+ Automaton automaton = new RegExp(".*", RegExp.NONE).toAutomaton();
CompiledAutomaton ca = new CompiledAutomaton(automaton, false, false);
TermsEnum te = terms.intersect(ca, null);
assertEquals("aaa", te.next().utf8ToString());
@@ -793,7 +793,7 @@ public class TestTermsEnum extends Lucen
AtomicReader sub = getOnlySegmentReader(r);
Terms terms = sub.fields().terms("field");
- LightAutomaton automaton = new RegExp(".*d", RegExp.NONE).toLightAutomaton();
+ Automaton automaton = new RegExp(".*d", RegExp.NONE).toAutomaton();
CompiledAutomaton ca = new CompiledAutomaton(automaton, false, false);
TermsEnum te;
@@ -847,7 +847,7 @@ public class TestTermsEnum extends Lucen
AtomicReader sub = getOnlySegmentReader(r);
Terms terms = sub.fields().terms("field");
- LightAutomaton automaton = new RegExp(".*", RegExp.NONE).toLightAutomaton(); // accept ALL
+ Automaton automaton = new RegExp(".*", RegExp.NONE).toAutomaton(); // accept ALL
CompiledAutomaton ca = new CompiledAutomaton(automaton, false, false);
TermsEnum te = terms.intersect(ca, null);
Modified: lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum2.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum2.java?rev=1603012&r1=1603011&r2=1603012&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum2.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/test/org/apache/lucene/index/TestTermsEnum2.java Mon Jun 16 22:23:11 2014
@@ -44,7 +44,7 @@ public class TestTermsEnum2 extends Luce
private IndexReader reader;
private IndexSearcher searcher;
private SortedSet<BytesRef> terms; // the terms we put in the index
- private LightAutomaton termsAutomaton; // automata of the same
+ private Automaton termsAutomaton; // automata of the same
int numIterations;
@Override
@@ -69,7 +69,7 @@ public class TestTermsEnum2 extends Luce
writer.addDocument(doc);
}
- termsAutomaton = BasicAutomata.makeStringUnionLight(terms);
+ termsAutomaton = Automata.makeStringUnion(terms);
reader = writer.getReader();
searcher = newSearcher(reader);
@@ -88,15 +88,15 @@ public class TestTermsEnum2 extends Luce
for (int i = 0; i < numIterations; i++) {
String reg = AutomatonTestUtil.randomRegexp(random());
- LightAutomaton automaton = BasicOperations.determinize(new RegExp(reg, RegExp.NONE).toLightAutomaton());
+ Automaton automaton = Operations.determinize(new RegExp(reg, RegExp.NONE).toAutomaton());
final List<BytesRef> matchedTerms = new ArrayList<>();
for(BytesRef t : terms) {
- if (BasicOperations.run(automaton, t.utf8ToString())) {
+ if (Operations.run(automaton, t.utf8ToString())) {
matchedTerms.add(t);
}
}
- LightAutomaton alternate = BasicAutomata.makeStringUnionLight(matchedTerms);
+ Automaton alternate = Automata.makeStringUnion(matchedTerms);
//System.out.println("match " + matchedTerms.size() + " " + alternate.getNumberOfStates() + " states, sigma=" + alternate.getStartPoints().length);
//AutomatonTestUtil.minimizeSimple(alternate);
//System.out.println("minmize done");
@@ -113,13 +113,13 @@ public class TestTermsEnum2 extends Luce
public void testSeeking() throws Exception {
for (int i = 0; i < numIterations; i++) {
String reg = AutomatonTestUtil.randomRegexp(random());
- LightAutomaton automaton = BasicOperations.determinize(new RegExp(reg, RegExp.NONE).toLightAutomaton());
+ Automaton automaton = Operations.determinize(new RegExp(reg, RegExp.NONE).toAutomaton());
TermsEnum te = MultiFields.getTerms(reader, "field").iterator(null);
ArrayList<BytesRef> unsortedTerms = new ArrayList<>(terms);
Collections.shuffle(unsortedTerms, random());
for (BytesRef term : unsortedTerms) {
- if (BasicOperations.run(automaton, term.utf8ToString())) {
+ if (Operations.run(automaton, term.utf8ToString())) {
// term is accepted
if (random().nextBoolean()) {
// seek exact
@@ -157,17 +157,17 @@ public class TestTermsEnum2 extends Luce
public void testIntersect() throws Exception {
for (int i = 0; i < numIterations; i++) {
String reg = AutomatonTestUtil.randomRegexp(random());
- LightAutomaton automaton = new RegExp(reg, RegExp.NONE).toLightAutomaton();
- CompiledAutomaton ca = new CompiledAutomaton(automaton, SpecialOperations.isFinite(automaton), false);
+ Automaton automaton = new RegExp(reg, RegExp.NONE).toAutomaton();
+ CompiledAutomaton ca = new CompiledAutomaton(automaton, Operations.isFinite(automaton), false);
TermsEnum te = MultiFields.getTerms(reader, "field").intersect(ca, null);
- LightAutomaton expected = BasicOperations.determinize(BasicOperations.intersectionLight(termsAutomaton, automaton));
+ Automaton expected = Operations.determinize(Operations.intersection(termsAutomaton, automaton));
TreeSet<BytesRef> found = new TreeSet<>();
while (te.next() != null) {
found.add(BytesRef.deepCopyOf(te.term()));
}
- LightAutomaton actual = BasicOperations.determinize(BasicAutomata.makeStringUnionLight(found));
- assertTrue(BasicOperations.sameLanguage(expected, actual));
+ Automaton actual = Operations.determinize(Automata.makeStringUnion(found));
+ assertTrue(Operations.sameLanguage(expected, actual));
}
}
}