svn commit: r910818 - in /lucene/java/branches/flex_1458/src: java/org/apache/lucene/util/automaton/BasicOperations.java test/org/apache/lucene/util/automaton/ test/org/apache/lucene/util/automaton/TestBasicOperations.java

[rm...@apache.org]

Author: rmuir
Date: Wed Feb 17 04:13:19 2010
New Revision: 910818

URL: http://svn.apache.org/viewvc?rev=910818&view=rev
Log:
LUCENE-2089: avoid useless NFA-DFA conversion for singleton-DFA concat

Added:
    lucene/java/branches/flex_1458/src/test/org/apache/lucene/util/automaton/
    lucene/java/branches/flex_1458/src/test/org/apache/lucene/util/automaton/TestBasicOperations.java   (with props)
Modified:
    lucene/java/branches/flex_1458/src/java/org/apache/lucene/util/automaton/BasicOperations.java

Modified: lucene/java/branches/flex_1458/src/java/org/apache/lucene/util/automaton/BasicOperations.java
URL: http://svn.apache.org/viewvc/lucene/java/branches/flex_1458/src/java/org/apache/lucene/util/automaton/BasicOperations.java?rev=910818&r1=910817&r2=910818&view=diff
==============================================================================
--- lucene/java/branches/flex_1458/src/java/org/apache/lucene/util/automaton/BasicOperations.java (original)
+++ lucene/java/branches/flex_1458/src/java/org/apache/lucene/util/automaton/BasicOperations.java Wed Feb 17 04:13:19 2010
@@ -57,6 +57,10 @@
   static public Automaton concatenate(Automaton a1, Automaton a2) {
     if (a1.isSingleton() && a2.isSingleton()) return BasicAutomata
         .makeString(a1.singleton + a2.singleton);
+    // adding epsilon transitions with the NFA concatenation algorithm
+    // in this case always produces a resulting DFA, preventing expensive
+    // redundant determinize() calls for this common case.
+    boolean deterministic = a1.isSingleton() && a2.isDeterministic();
     if (a1 == a2) {
       a1 = a1.cloneExpanded();
       a2 = a2.cloneExpanded();
@@ -68,7 +72,7 @@
       s.accept = false;
       s.addEpsilon(a2.initial);
     }
-    a1.deterministic = false;
+    a1.deterministic = deterministic;
     a1.clearHashCode();
     a1.checkMinimizeAlways();
     return a1;

Added: lucene/java/branches/flex_1458/src/test/org/apache/lucene/util/automaton/TestBasicOperations.java
URL: http://svn.apache.org/viewvc/lucene/java/branches/flex_1458/src/test/org/apache/lucene/util/automaton/TestBasicOperations.java?rev=910818&view=auto
==============================================================================
--- lucene/java/branches/flex_1458/src/test/org/apache/lucene/util/automaton/TestBasicOperations.java (added)
+++ lucene/java/branches/flex_1458/src/test/org/apache/lucene/util/automaton/TestBasicOperations.java Wed Feb 17 04:13:19 2010
@@ -0,0 +1,71 @@
+package org.apache.lucene.util.automaton;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+import org.apache.lucene.util.LuceneTestCase;
+
+public class TestBasicOperations extends LuceneTestCase { 
+  /** Test optimization to concatenate() */
+  public void testSingletonConcatenate() {
+    Automaton singleton = BasicAutomata.makeString("prefix");
+    Automaton expandedSingleton = singleton.cloneExpanded();
+    Automaton other = BasicAutomata.makeMaxInteger("57");
+    Automaton concat = BasicOperations.concatenate(singleton, other);
+    assertTrue(concat.isDeterministic());
+    assertEquals(BasicOperations.concatenate(expandedSingleton, other), concat);
+  }
+  
+  /** Test optimization to concatenate() to an NFA */
+  public void testSingletonNFAConcatenate() {
+    Automaton singleton = BasicAutomata.makeString("prefix");
+    Automaton expandedSingleton = singleton.cloneExpanded();
+    // an NFA (two transitions for 't' from initial state)
+    Automaton nfa = BasicOperations.union(BasicAutomata.makeString("this"),
+        BasicAutomata.makeString("three"));
+    Automaton concat = BasicOperations.concatenate(singleton, nfa);
+    assertFalse(concat.isDeterministic());
+    assertEquals(BasicOperations.concatenate(expandedSingleton, nfa), concat);
+  }
+  
+  /** Test optimization to concatenate() with empty String */
+  public void testEmptySingletonConcatenate() {
+    Automaton singleton = BasicAutomata.makeString("");
+    Automaton expandedSingleton = singleton.cloneExpanded();
+    Automaton other = BasicAutomata.makeMaxInteger("57");
+    Automaton concat1 = BasicOperations.concatenate(expandedSingleton, other);
+    Automaton concat2 = BasicOperations.concatenate(singleton, other);
+    assertTrue(concat2.isDeterministic());
+    assertEquals(concat1, concat2);
+    assertEquals(other, concat1);
+    assertEquals(other, concat2);
+  }
+  
+  /** Test optimization to concatenate() with empty String to an NFA */
+  public void testEmptySingletonNFAConcatenate() {
+    Automaton singleton = BasicAutomata.makeString("");
+    Automaton expandedSingleton = singleton.cloneExpanded();
+    // an NFA (two transitions for 't' from initial state)
+    Automaton nfa = BasicOperations.union(BasicAutomata.makeString("this"),
+        BasicAutomata.makeString("three"));
+    Automaton concat1 = BasicOperations.concatenate(expandedSingleton, nfa);
+    Automaton concat2 = BasicOperations.concatenate(singleton, nfa);
+    assertFalse(concat2.isDeterministic());
+    assertEquals(concat1, concat2);
+    assertEquals(nfa, concat1);
+    assertEquals(nfa, concat2);
+  }
+}

Propchange: lucene/java/branches/flex_1458/src/test/org/apache/lucene/util/automaton/TestBasicOperations.java
------------------------------------------------------------------------------
    svn:eol-style = native