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/18 17:41:49 UTC

svn commit: r1603489 - in /lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton: Automaton.java Operations.java

Author: mikemccand
Date: Wed Jun 18 15:41:49 2014
New Revision: 1603489

URL: http://svn.apache.org/r1603489
Log:
LUCENE-5752: cutover to FixedBitSet to mark the accept states; improve javadocs

Modified:
    lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java
    lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java

Modified: lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java?rev=1603489&r1=1603488&r2=1603489&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java Wed Jun 18 15:41:49 2014
@@ -24,6 +24,7 @@ import java.util.HashSet;
 import java.util.Set;
 
 import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.FixedBitSet;
 import org.apache.lucene.util.InPlaceMergeSorter;
 import org.apache.lucene.util.Sorter;
 
@@ -71,7 +72,7 @@ public class Automaton {
   /** Holds toState, min, max for each transition. */
   private int[] transitions = new int[6];
 
-  private final Set<Integer> acceptStates = new HashSet<Integer>();
+  private FixedBitSet isAccept = new FixedBitSet(4);
 
   /** True if no state has two transitions leaving with the same label. */
   private boolean deterministic = true;
@@ -86,18 +87,23 @@ public class Automaton {
     int state = nextState/2;
     states[nextState] = -1;
     nextState += 2;
+    if (state >= isAccept.length()) {
+      FixedBitSet newBits = new FixedBitSet(ArrayUtil.oversize(state+1, 1));
+      newBits.or(isAccept);
+      isAccept = newBits;
+    }
     return state;
   }
 
   /** Set or clear this state as an accept state. */
-  public void setAccept(int state, boolean isAccept) {
+  public void setAccept(int state, boolean accept) {
     if (state >= getNumStates()) {
       throw new IllegalArgumentException("state=" + state + " is out of bounds (numStates=" + getNumStates() + ")");
     }
-    if (isAccept) {
-      acceptStates.add(state);
+    if (accept) {
+      isAccept.set(state);
     } else {
-      acceptStates.remove(state);
+      isAccept.clear(state);
     }
   }
 
@@ -119,14 +125,14 @@ public class Automaton {
     return transitions;
   }
 
-  /** Returns accept states. */
-  public Set<Integer> getAcceptStates() {
-    return acceptStates;
+  /** Returns accept states.  If the bit is set then that state is an accept state. */
+  FixedBitSet getAcceptStates() {
+    return isAccept;
   }
 
   /** Returns true if this state is an accept state. */
   public boolean isAccept(int state) {
-    return acceptStates.contains(state);
+    return isAccept.get(state);
   }
 
   /** Add a new transition with min = max = label. */
@@ -195,12 +201,19 @@ public class Automaton {
       if (states[nextState+i] != -1) {
         states[nextState+i] += nextTransition;
       }
-      int state = i/2;
     }
     nextState += other.nextState;
-
-    for(int s : other.getAcceptStates()) {
-      setAccept(stateOffset+s, true);
+    if (isAccept.length() < nextState/2) {
+      FixedBitSet newBits = new FixedBitSet(ArrayUtil.oversize(nextState/2, 1));
+      newBits.or(isAccept);
+      isAccept = newBits;
+    }
+    int otherNumStates = other.getNumStates();
+    FixedBitSet otherAcceptStates = other.getAcceptStates();
+    int state = 0;
+    while (state < otherNumStates && (state = otherAcceptStates.nextSetBit(state)) != -1) {
+      setAccept(stateOffset + state, true);
+      state++;
     }
 
     // Bulk copy and then fixup dest for each transition:

Modified: 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=1603489&r1=1603488&r2=1603489&view=diff
==============================================================================
--- lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java (original)
+++ lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton/Operations.java Wed Jun 18 15:41:49 2014
@@ -42,6 +42,7 @@ import java.util.Set;
 
 import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.FixedBitSet;
 import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.RamUsageEstimator;
 
@@ -239,7 +240,7 @@ final public class Operations {
       b = concatenate(as);
     }
 
-    Set<Integer> prevAcceptStates = new HashSet<>(b.getAcceptStates());
+    Set<Integer> prevAcceptStates = toSet(b, 0);
 
     for(int i=min;i<max;i++) {
       int numStates = b.getNumStates();
@@ -247,16 +248,26 @@ final public class Operations {
       for(int s : prevAcceptStates) {
         b.addEpsilon(s, numStates);
       }
-      prevAcceptStates.clear();
-      for(int s : a.getAcceptStates()) {
-        prevAcceptStates.add(numStates+s);
-      }
+      prevAcceptStates = toSet(a, numStates);
     }
 
     b.finishState();
 
     return b;
   }
+
+  private static Set<Integer> toSet(Automaton a, int offset) {
+    int numStates = a.getNumStates();
+    FixedBitSet isAccept = a.getAcceptStates();
+    Set<Integer> result = new HashSet<Integer>();
+    int upto = 0;
+    while (upto < numStates && (upto = isAccept.nextSetBit(upto)) != -1) {
+      result.add(offset+upto);
+      upto++;
+    }
+
+    return result;
+  }
   
   /**
    * Returns a (deterministic) automaton that accepts the complement of the
@@ -913,13 +924,16 @@ final public class Operations {
 
     LinkedList<Integer> workList = new LinkedList<>();
     BitSet live = new BitSet(numStates);
-    for (int s : a.getAcceptStates()) {
+    FixedBitSet acceptBits = a.getAcceptStates();
+    int s = 0;
+    while (s < numStates && (s = acceptBits.nextSetBit(s)) != -1) {
       live.set(s);
       workList.add(s);
+      s++;
     }
 
     while (workList.isEmpty() == false) {
-      int s = workList.removeFirst();
+      s = workList.removeFirst();
       int count = a2.initTransition(s, t);
       for(int i=0;i<count;i++) {
         a2.getNextTransition(t);
@@ -971,6 +985,7 @@ final public class Operations {
     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.
@@ -988,7 +1003,8 @@ final public class Operations {
   }
   
   /**
-   * Returns true if the language of this automaton is finite.
+   * Returns true if the language of this automaton is finite.  The
+   * automaton must not have any dead states.
    */
   public static boolean isFinite(Automaton a) {
     if (a.getNumStates() == 0) {
@@ -998,7 +1014,7 @@ final public class Operations {
   }
   
   /**
-   * Checks whether there is a loop containing s. (This is sufficient since
+   * Checks whether there is a loop containing state. (This is sufficient since
    * there are never transitions to dead states.)
    */
   // TODO: not great that this is recursive... in theory a
@@ -1144,12 +1160,14 @@ final public class Operations {
 
     Automaton result = builder.finish();
 
-    for(int s : a.getAcceptStates()) {
-      assert s < numStates;
+    int s = 0;
+    FixedBitSet acceptStates = a.getAcceptStates();
+    while (s < numStates && (s = acceptStates.nextSetBit(s)) != -1) {
       result.addEpsilon(0, s+1);
       if (initialStates != null) {
         initialStates.add(s+1);
       }
+      s++;
     }
 
     result.finishState();



Re: svn commit: r1603489 - in /lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton: Automaton.java Operations.java

Posted by Michael McCandless <lu...@mikemccandless.com>.
OK I'll switch to BitSet.

Mike McCandless

http://blog.mikemccandless.com


On Wed, Jun 18, 2014 at 11:44 AM, Uwe Schindler <uw...@thetaphi.de> wrote:
> Why not use java.util.BitSet here? It automatically oversizes!
>
> -----
> Uwe Schindler
> H.-H.-Meier-Allee 63, D-28213 Bremen
> http://www.thetaphi.de
> eMail: uwe@thetaphi.de
>
>
>> -----Original Message-----
>> From: mikemccand@apache.org [mailto:mikemccand@apache.org]
>> Sent: Wednesday, June 18, 2014 5:42 PM
>> To: commits@lucene.apache.org
>> Subject: svn commit: r1603489 - in
>> /lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene
>> /util/automaton: Automaton.java Operations.java
>>
>> Author: mikemccand
>> Date: Wed Jun 18 15:41:49 2014
>> New Revision: 1603489
>>
>> URL: http://svn.apache.org/r1603489
>> Log:
>> LUCENE-5752: cutover to FixedBitSet to mark the accept states; improve
>> javadocs
>>
>> Modified:
>>
>> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
>> util/automaton/Automaton.java
>>
>> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
>> util/automaton/Operations.java
>>
>> Modified:
>> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
>> util/automaton/Automaton.java
>> URL:
>> http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/cor
>> e/src/java/org/apache/lucene/util/automaton/Automaton.java?rev=160348
>> 9&r1=1603488&r2=1603489&view=diff
>> ==========================================================
>> ====================
>> ---
>> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
>> util/automaton/Automaton.java (original)
>> +++
>> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucen
>> +++ e/util/automaton/Automaton.java Wed Jun 18 15:41:49 2014
>> @@ -24,6 +24,7 @@ import java.util.HashSet;  import java.util.Set;
>>
>>  import org.apache.lucene.util.ArrayUtil;
>> +import org.apache.lucene.util.FixedBitSet;
>>  import org.apache.lucene.util.InPlaceMergeSorter;
>>  import org.apache.lucene.util.Sorter;
>>
>> @@ -71,7 +72,7 @@ public class Automaton {
>>    /** Holds toState, min, max for each transition. */
>>    private int[] transitions = new int[6];
>>
>> -  private final Set<Integer> acceptStates = new HashSet<Integer>();
>> +  private FixedBitSet isAccept = new FixedBitSet(4);
>>
>>    /** True if no state has two transitions leaving with the same label. */
>>    private boolean deterministic = true; @@ -86,18 +87,23 @@ public class
>> Automaton {
>>      int state = nextState/2;
>>      states[nextState] = -1;
>>      nextState += 2;
>> +    if (state >= isAccept.length()) {
>> +      FixedBitSet newBits = new FixedBitSet(ArrayUtil.oversize(state+1, 1));
>> +      newBits.or(isAccept);
>> +      isAccept = newBits;
>> +    }
>>      return state;
>>    }
>>
>>    /** Set or clear this state as an accept state. */
>> -  public void setAccept(int state, boolean isAccept) {
>> +  public void setAccept(int state, boolean accept) {
>>      if (state >= getNumStates()) {
>>        throw new IllegalArgumentException("state=" + state + " is out of bounds
>> (numStates=" + getNumStates() + ")");
>>      }
>> -    if (isAccept) {
>> -      acceptStates.add(state);
>> +    if (accept) {
>> +      isAccept.set(state);
>>      } else {
>> -      acceptStates.remove(state);
>> +      isAccept.clear(state);
>>      }
>>    }
>>
>> @@ -119,14 +125,14 @@ public class Automaton {
>>      return transitions;
>>    }
>>
>> -  /** Returns accept states. */
>> -  public Set<Integer> getAcceptStates() {
>> -    return acceptStates;
>> +  /** Returns accept states.  If the bit is set then that state is an
>> + accept state. */  FixedBitSet getAcceptStates() {
>> +    return isAccept;
>>    }
>>
>>    /** Returns true if this state is an accept state. */
>>    public boolean isAccept(int state) {
>> -    return acceptStates.contains(state);
>> +    return isAccept.get(state);
>>    }
>>
>>    /** Add a new transition with min = max = label. */ @@ -195,12 +201,19
>> @@ public class Automaton {
>>        if (states[nextState+i] != -1) {
>>          states[nextState+i] += nextTransition;
>>        }
>> -      int state = i/2;
>>      }
>>      nextState += other.nextState;
>> -
>> -    for(int s : other.getAcceptStates()) {
>> -      setAccept(stateOffset+s, true);
>> +    if (isAccept.length() < nextState/2) {
>> +      FixedBitSet newBits = new FixedBitSet(ArrayUtil.oversize(nextState/2,
>> 1));
>> +      newBits.or(isAccept);
>> +      isAccept = newBits;
>> +    }
>> +    int otherNumStates = other.getNumStates();
>> +    FixedBitSet otherAcceptStates = other.getAcceptStates();
>> +    int state = 0;
>> +    while (state < otherNumStates && (state =
>> otherAcceptStates.nextSetBit(state)) != -1) {
>> +      setAccept(stateOffset + state, true);
>> +      state++;
>>      }
>>
>>      // Bulk copy and then fixup dest for each transition:
>>
>> Modified:
>> 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/cor
>> e/src/java/org/apache/lucene/util/automaton/Operations.java?rev=160348
>> 9&r1=1603488&r2=1603489&view=diff
>> ==========================================================
>> ====================
>> ---
>> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
>> util/automaton/Operations.java (original)
>> +++
>> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucen
>> +++ e/util/automaton/Operations.java Wed Jun 18 15:41:49 2014
>> @@ -42,6 +42,7 @@ import java.util.Set;
>>
>>  import org.apache.lucene.util.ArrayUtil;  import
>> org.apache.lucene.util.BytesRef;
>> +import org.apache.lucene.util.FixedBitSet;
>>  import org.apache.lucene.util.IntsRef;
>>  import org.apache.lucene.util.RamUsageEstimator;
>>
>> @@ -239,7 +240,7 @@ final public class Operations {
>>        b = concatenate(as);
>>      }
>>
>> -    Set<Integer> prevAcceptStates = new HashSet<>(b.getAcceptStates());
>> +    Set<Integer> prevAcceptStates = toSet(b, 0);
>>
>>      for(int i=min;i<max;i++) {
>>        int numStates = b.getNumStates(); @@ -247,16 +248,26 @@ final public
>> class Operations {
>>        for(int s : prevAcceptStates) {
>>          b.addEpsilon(s, numStates);
>>        }
>> -      prevAcceptStates.clear();
>> -      for(int s : a.getAcceptStates()) {
>> -        prevAcceptStates.add(numStates+s);
>> -      }
>> +      prevAcceptStates = toSet(a, numStates);
>>      }
>>
>>      b.finishState();
>>
>>      return b;
>>    }
>> +
>> +  private static Set<Integer> toSet(Automaton a, int offset) {
>> +    int numStates = a.getNumStates();
>> +    FixedBitSet isAccept = a.getAcceptStates();
>> +    Set<Integer> result = new HashSet<Integer>();
>> +    int upto = 0;
>> +    while (upto < numStates && (upto = isAccept.nextSetBit(upto)) != -1) {
>> +      result.add(offset+upto);
>> +      upto++;
>> +    }
>> +
>> +    return result;
>> +  }
>>
>>    /**
>>     * Returns a (deterministic) automaton that accepts the complement of the
>> @@ -913,13 +924,16 @@ final public class Operations {
>>
>>      LinkedList<Integer> workList = new LinkedList<>();
>>      BitSet live = new BitSet(numStates);
>> -    for (int s : a.getAcceptStates()) {
>> +    FixedBitSet acceptBits = a.getAcceptStates();
>> +    int s = 0;
>> +    while (s < numStates && (s = acceptBits.nextSetBit(s)) != -1) {
>>        live.set(s);
>>        workList.add(s);
>> +      s++;
>>      }
>>
>>      while (workList.isEmpty() == false) {
>> -      int s = workList.removeFirst();
>> +      s = workList.removeFirst();
>>        int count = a2.initTransition(s, t);
>>        for(int i=0;i<count;i++) {
>>          a2.getNextTransition(t);
>> @@ -971,6 +985,7 @@ final public class Operations {
>>      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.
>> @@ -988,7 +1003,8 @@ final public class Operations {
>>    }
>>
>>    /**
>> -   * Returns true if the language of this automaton is finite.
>> +   * Returns true if the language of this automaton is finite.  The
>> +   * automaton must not have any dead states.
>>     */
>>    public static boolean isFinite(Automaton a) {
>>      if (a.getNumStates() == 0) {
>> @@ -998,7 +1014,7 @@ final public class Operations {
>>    }
>>
>>    /**
>> -   * Checks whether there is a loop containing s. (This is sufficient since
>> +   * Checks whether there is a loop containing state. (This is
>> + sufficient since
>>     * there are never transitions to dead states.)
>>     */
>>    // TODO: not great that this is recursive... in theory a @@ -1144,12 +1160,14
>> @@ final public class Operations {
>>
>>      Automaton result = builder.finish();
>>
>> -    for(int s : a.getAcceptStates()) {
>> -      assert s < numStates;
>> +    int s = 0;
>> +    FixedBitSet acceptStates = a.getAcceptStates();
>> +    while (s < numStates && (s = acceptStates.nextSetBit(s)) != -1) {
>>        result.addEpsilon(0, s+1);
>>        if (initialStates != null) {
>>          initialStates.add(s+1);
>>        }
>> +      s++;
>>      }
>>
>>      result.finishState();
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


RE: svn commit: r1603489 - in /lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/util/automaton: Automaton.java Operations.java

Posted by Uwe Schindler <uw...@thetaphi.de>.
Why not use java.util.BitSet here? It automatically oversizes!

-----
Uwe Schindler
H.-H.-Meier-Allee 63, D-28213 Bremen
http://www.thetaphi.de
eMail: uwe@thetaphi.de


> -----Original Message-----
> From: mikemccand@apache.org [mailto:mikemccand@apache.org]
> Sent: Wednesday, June 18, 2014 5:42 PM
> To: commits@lucene.apache.org
> Subject: svn commit: r1603489 - in
> /lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene
> /util/automaton: Automaton.java Operations.java
> 
> Author: mikemccand
> Date: Wed Jun 18 15:41:49 2014
> New Revision: 1603489
> 
> URL: http://svn.apache.org/r1603489
> Log:
> LUCENE-5752: cutover to FixedBitSet to mark the accept states; improve
> javadocs
> 
> Modified:
> 
> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
> util/automaton/Automaton.java
> 
> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
> util/automaton/Operations.java
> 
> Modified:
> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
> util/automaton/Automaton.java
> URL:
> http://svn.apache.org/viewvc/lucene/dev/branches/lucene5752/lucene/cor
> e/src/java/org/apache/lucene/util/automaton/Automaton.java?rev=160348
> 9&r1=1603488&r2=1603489&view=diff
> ==========================================================
> ====================
> ---
> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
> util/automaton/Automaton.java (original)
> +++
> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucen
> +++ e/util/automaton/Automaton.java Wed Jun 18 15:41:49 2014
> @@ -24,6 +24,7 @@ import java.util.HashSet;  import java.util.Set;
> 
>  import org.apache.lucene.util.ArrayUtil;
> +import org.apache.lucene.util.FixedBitSet;
>  import org.apache.lucene.util.InPlaceMergeSorter;
>  import org.apache.lucene.util.Sorter;
> 
> @@ -71,7 +72,7 @@ public class Automaton {
>    /** Holds toState, min, max for each transition. */
>    private int[] transitions = new int[6];
> 
> -  private final Set<Integer> acceptStates = new HashSet<Integer>();
> +  private FixedBitSet isAccept = new FixedBitSet(4);
> 
>    /** True if no state has two transitions leaving with the same label. */
>    private boolean deterministic = true; @@ -86,18 +87,23 @@ public class
> Automaton {
>      int state = nextState/2;
>      states[nextState] = -1;
>      nextState += 2;
> +    if (state >= isAccept.length()) {
> +      FixedBitSet newBits = new FixedBitSet(ArrayUtil.oversize(state+1, 1));
> +      newBits.or(isAccept);
> +      isAccept = newBits;
> +    }
>      return state;
>    }
> 
>    /** Set or clear this state as an accept state. */
> -  public void setAccept(int state, boolean isAccept) {
> +  public void setAccept(int state, boolean accept) {
>      if (state >= getNumStates()) {
>        throw new IllegalArgumentException("state=" + state + " is out of bounds
> (numStates=" + getNumStates() + ")");
>      }
> -    if (isAccept) {
> -      acceptStates.add(state);
> +    if (accept) {
> +      isAccept.set(state);
>      } else {
> -      acceptStates.remove(state);
> +      isAccept.clear(state);
>      }
>    }
> 
> @@ -119,14 +125,14 @@ public class Automaton {
>      return transitions;
>    }
> 
> -  /** Returns accept states. */
> -  public Set<Integer> getAcceptStates() {
> -    return acceptStates;
> +  /** Returns accept states.  If the bit is set then that state is an
> + accept state. */  FixedBitSet getAcceptStates() {
> +    return isAccept;
>    }
> 
>    /** Returns true if this state is an accept state. */
>    public boolean isAccept(int state) {
> -    return acceptStates.contains(state);
> +    return isAccept.get(state);
>    }
> 
>    /** Add a new transition with min = max = label. */ @@ -195,12 +201,19
> @@ public class Automaton {
>        if (states[nextState+i] != -1) {
>          states[nextState+i] += nextTransition;
>        }
> -      int state = i/2;
>      }
>      nextState += other.nextState;
> -
> -    for(int s : other.getAcceptStates()) {
> -      setAccept(stateOffset+s, true);
> +    if (isAccept.length() < nextState/2) {
> +      FixedBitSet newBits = new FixedBitSet(ArrayUtil.oversize(nextState/2,
> 1));
> +      newBits.or(isAccept);
> +      isAccept = newBits;
> +    }
> +    int otherNumStates = other.getNumStates();
> +    FixedBitSet otherAcceptStates = other.getAcceptStates();
> +    int state = 0;
> +    while (state < otherNumStates && (state =
> otherAcceptStates.nextSetBit(state)) != -1) {
> +      setAccept(stateOffset + state, true);
> +      state++;
>      }
> 
>      // Bulk copy and then fixup dest for each transition:
> 
> Modified:
> 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/cor
> e/src/java/org/apache/lucene/util/automaton/Operations.java?rev=160348
> 9&r1=1603488&r2=1603489&view=diff
> ==========================================================
> ====================
> ---
> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucene/
> util/automaton/Operations.java (original)
> +++
> lucene/dev/branches/lucene5752/lucene/core/src/java/org/apache/lucen
> +++ e/util/automaton/Operations.java Wed Jun 18 15:41:49 2014
> @@ -42,6 +42,7 @@ import java.util.Set;
> 
>  import org.apache.lucene.util.ArrayUtil;  import
> org.apache.lucene.util.BytesRef;
> +import org.apache.lucene.util.FixedBitSet;
>  import org.apache.lucene.util.IntsRef;
>  import org.apache.lucene.util.RamUsageEstimator;
> 
> @@ -239,7 +240,7 @@ final public class Operations {
>        b = concatenate(as);
>      }
> 
> -    Set<Integer> prevAcceptStates = new HashSet<>(b.getAcceptStates());
> +    Set<Integer> prevAcceptStates = toSet(b, 0);
> 
>      for(int i=min;i<max;i++) {
>        int numStates = b.getNumStates(); @@ -247,16 +248,26 @@ final public
> class Operations {
>        for(int s : prevAcceptStates) {
>          b.addEpsilon(s, numStates);
>        }
> -      prevAcceptStates.clear();
> -      for(int s : a.getAcceptStates()) {
> -        prevAcceptStates.add(numStates+s);
> -      }
> +      prevAcceptStates = toSet(a, numStates);
>      }
> 
>      b.finishState();
> 
>      return b;
>    }
> +
> +  private static Set<Integer> toSet(Automaton a, int offset) {
> +    int numStates = a.getNumStates();
> +    FixedBitSet isAccept = a.getAcceptStates();
> +    Set<Integer> result = new HashSet<Integer>();
> +    int upto = 0;
> +    while (upto < numStates && (upto = isAccept.nextSetBit(upto)) != -1) {
> +      result.add(offset+upto);
> +      upto++;
> +    }
> +
> +    return result;
> +  }
> 
>    /**
>     * Returns a (deterministic) automaton that accepts the complement of the
> @@ -913,13 +924,16 @@ final public class Operations {
> 
>      LinkedList<Integer> workList = new LinkedList<>();
>      BitSet live = new BitSet(numStates);
> -    for (int s : a.getAcceptStates()) {
> +    FixedBitSet acceptBits = a.getAcceptStates();
> +    int s = 0;
> +    while (s < numStates && (s = acceptBits.nextSetBit(s)) != -1) {
>        live.set(s);
>        workList.add(s);
> +      s++;
>      }
> 
>      while (workList.isEmpty() == false) {
> -      int s = workList.removeFirst();
> +      s = workList.removeFirst();
>        int count = a2.initTransition(s, t);
>        for(int i=0;i<count;i++) {
>          a2.getNextTransition(t);
> @@ -971,6 +985,7 @@ final public class Operations {
>      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.
> @@ -988,7 +1003,8 @@ final public class Operations {
>    }
> 
>    /**
> -   * Returns true if the language of this automaton is finite.
> +   * Returns true if the language of this automaton is finite.  The
> +   * automaton must not have any dead states.
>     */
>    public static boolean isFinite(Automaton a) {
>      if (a.getNumStates() == 0) {
> @@ -998,7 +1014,7 @@ final public class Operations {
>    }
> 
>    /**
> -   * Checks whether there is a loop containing s. (This is sufficient since
> +   * Checks whether there is a loop containing state. (This is
> + sufficient since
>     * there are never transitions to dead states.)
>     */
>    // TODO: not great that this is recursive... in theory a @@ -1144,12 +1160,14
> @@ final public class Operations {
> 
>      Automaton result = builder.finish();
> 
> -    for(int s : a.getAcceptStates()) {
> -      assert s < numStates;
> +    int s = 0;
> +    FixedBitSet acceptStates = a.getAcceptStates();
> +    while (s < numStates && (s = acceptStates.nextSetBit(s)) != -1) {
>        result.addEpsilon(0, s+1);
>        if (initialStates != null) {
>          initialStates.add(s+1);
>        }
> +      s++;
>      }
> 
>      result.finishState();



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org