--- /dev/null
+package org.apache.lucene.util.fst;
+
+/**
+ * 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.ArrayUtil;
+import org.apache.lucene.util.RamUsageEstimator;
+
+import java.io.IOException;
+
+/** Can next() and advance() through the terms in an FST
+ *
+ * @lucene.experimental
+*/
+
+abstract class FSTEnum<T> {
+ protected final FST<T> fst;
+
+ @SuppressWarnings("unchecked") protected FST.Arc<T>[] arcs = new FST.Arc[10];
+ // outputs are cumulative
+ @SuppressWarnings("unchecked") protected T[] output = (T[]) new Object[10];
+
+ protected final T NO_OUTPUT;
+ protected final FST.Arc<T> scratchArc = new FST.Arc<T>();
+
+ protected int upto;
+ protected int targetLength;
+
+ /** doFloor controls the behavior of advance: if it's true
+ * doFloor is true, advance positions to the biggest
+ * term before target. */
+ protected FSTEnum(FST<T> fst) {
+ this.fst = fst;
+ NO_OUTPUT = fst.outputs.getNoOutput();
+ fst.getFirstArc(getArc(0));
+ output[0] = NO_OUTPUT;
+ }
+
+ protected abstract int getTargetLabel();
+ protected abstract int getCurrentLabel();
+
+ protected abstract void setCurrentLabel(int label);
+ protected abstract void grow();
+
+ /** Rewinds enum state to match the shared prefix between
+ * current term and target term */
+ protected final void rewindPrefix() throws IOException {
+ if (upto == 0) {
+ //System.out.println(" init");
+ upto = 1;
+ fst.readFirstTargetArc(getArc(0), getArc(1));
+ return;
+ }
+ //System.out.println(" rewind upto=" + upto + " vs targetLength=" + targetLength);
+
+ final int currentLimit = upto;
+ upto = 1;
+ while (upto < currentLimit && upto <= targetLength+1) {
+ final int cmp = getCurrentLabel() - getTargetLabel();
+ if (cmp < 0) {
+ // seek forward
+ break;
+ } else if (cmp > 0) {
+ // seek backwards -- reset this arc to the first arc
+ final FST.Arc<T> arc = getArc(upto);
+ fst.readFirstTargetArc(getArc(upto-1), arc);
+ //System.out.println(" seek first arc");
+ break;
+ }
+ upto++;
+ }
+ }
+
+ protected void doNext() throws IOException {
+ //System.out.println("FE: next upto=" + upto);
+ if (upto == 0) {
+ //System.out.println(" init");
+ upto = 1;
+ fst.readFirstTargetArc(getArc(0), getArc(1));
+ } else {
+ // pop
+ //System.out.println(" check pop curArc target=" + arcs[upto].target + " label=" + arcs[upto].label + " isLast?=" + arcs[upto].isLast());
+ while (arcs[upto].isLast()) {
+ upto--;
+ if (upto == 0) {
+ //System.out.println(" eof");
+ return;
+ }
+ }
+ fst.readNextArc(arcs[upto]);
+ }
+
+ pushFirst();
+ }
+
+ // TODO: should we return a status here (SEEK_FOUND / SEEK_NOT_FOUND /
+ // SEEK_END)? saves the eq check above?
+
+ /** Seeks to smallest term that's >= target. */
+ protected void doSeekCeil() throws IOException {
+
+ //System.out.println(" advance len=" + target.length + " curlen=" + current.length);
+
+ // TODO: possibly caller could/should provide common
+ // prefix length? ie this work may be redundant if
+ // caller is in fact intersecting against its own
+ // automaton
+
+ //System.out.println("FE.seekCeil upto=" + upto);
+
+ // Save time by starting at the end of the shared prefix
+ // b/w our current term & the target:
+ rewindPrefix();
+ //System.out.println(" after rewind upto=" + upto);
+
+ FST.Arc<T> arc = getArc(upto);
+ int targetLabel = getTargetLabel();
+ //System.out.println(" init targetLabel=" + targetLabel);
+
+ // Now scan forward, matching the new suffix of the target
+ while(true) {
+
+ //System.out.println(" cycle upto=" + upto + " arc.label=" + arc.label + " (" + (char) arc.label + ") vs targetLabel=" + targetLabel);
+
+ if (arc.bytesPerArc != 0 && arc.label != -1) {
+
+ // Arcs are fixed array -- use binary search to find
+ // the target.
+
+ final FST<T>.BytesReader in = fst.getBytesReader(0);
+ int low = arc.arcIdx;
+ int high = arc.numArcs-1;
+ int mid = 0;
+ //System.out.println("do arc array low=" + low + " high=" + high + " targetLabel=" + targetLabel);
+ boolean found = false;
+ while (low <= high) {
+ mid = (low + high) >>> 1;
+ in.pos = arc.posArcsStart - arc.bytesPerArc*mid - 1;
+ final int midLabel = fst.readLabel(in);
+ final int cmp = midLabel - targetLabel;
+ //System.out.println(" cycle low=" + low + " high=" + high + " mid=" + mid + " midLabel=" + midLabel + " cmp=" + cmp);
+ if (cmp < 0)
+ low = mid + 1;
+ else if (cmp > 0)
+ high = mid - 1;
+ else {
+ found = true;
+ break;
+ }
+ }
+
+ // NOTE: this code is dup'd w/ the code below (in
+ // the outer else clause):
+ if (found) {
+ // Match
+ arc.arcIdx = mid-1;
+ fst.readNextRealArc(arc, in);
+ assert arc.arcIdx == mid;
+ assert arc.label == targetLabel: "arc.label=" + arc.label + " vs targetLabel=" + targetLabel + " mid=" + mid;
+ output[upto] = fst.outputs.add(output[upto-1], arc.output);
+ if (targetLabel == FST.END_LABEL) {
+ return;
+ }
+ setCurrentLabel(arc.label);
+ incr();
+ arc = fst.readFirstTargetArc(arc, getArc(upto));
+ targetLabel = getTargetLabel();
+ continue;
+ } else if (low == arc.numArcs) {
+ // Dead end
+ arc.arcIdx = arc.numArcs-2;
+ fst.readNextRealArc(arc, in);
+ assert arc.isLast();
+ // Dead end (target is after the last arc);
+ // rollback to last fork then push
+ upto--;
+ while(true) {
+ if (upto == 0) {
+ return;
+ }
+ final FST.Arc<T> prevArc = getArc(upto);
+ //System.out.println(" rollback upto=" + upto + " arc.label=" + prevArc.label + " isLast?=" + prevArc.isLast());
+ if (!prevArc.isLast()) {
+ fst.readNextArc(prevArc);
+ pushFirst();
+ return;
+ }
+ upto--;
+ }
+ } else {
+ arc.arcIdx = (low > high ? low : high)-1;
+ fst.readNextRealArc(arc, in);
+ assert arc.label > targetLabel;
+ pushFirst();
+ return;
+ }
+ } else {
+ // Arcs are not array'd -- must do linear scan:
+ if (arc.label == targetLabel) {
+ // recurse
+ output[upto] = fst.outputs.add(output[upto-1], arc.output);
+ if (targetLabel == FST.END_LABEL) {
+ return;
+ }
+ setCurrentLabel(arc.label);
+ incr();
+ arc = fst.readFirstTargetArc(arc, getArc(upto));
+ targetLabel = getTargetLabel();
+ } else if (arc.label > targetLabel) {
+ pushFirst();
+ return;
+ } else if (arc.isLast()) {
+ // Dead end (target is after the last arc);
+ // rollback to last fork then push
+ upto--;
+ while(true) {
+ if (upto == 0) {
+ return;
+ }
+ final FST.Arc<T> prevArc = getArc(upto);
+ //System.out.println(" rollback upto=" + upto + " arc.label=" + prevArc.label + " isLast?=" + prevArc.isLast());
+ if (!prevArc.isLast()) {
+ fst.readNextArc(prevArc);
+ pushFirst();
+ return;
+ }
+ upto--;
+ }
+ } else {
+ // keep scanning
+ //System.out.println(" next scan");
+ fst.readNextArc(arc);
+ }
+ }
+ }
+ }
+
+ // TODO: should we return a status here (SEEK_FOUND / SEEK_NOT_FOUND /
+ // SEEK_END)? saves the eq check above?
+ /** Seeks to largest term that's <= target. */
+ protected void doSeekFloor() throws IOException {
+
+ // TODO: possibly caller could/should provide common
+ // prefix length? ie this work may be redundant if
+ // caller is in fact intersecting against its own
+ // automaton
+ //System.out.println("FE: seek floor upto=" + upto);
+
+ // Save CPU by starting at the end of the shared prefix
+ // b/w our current term & the target:
+ rewindPrefix();
+
+ //System.out.println("FE: after rewind upto=" + upto);
+
+ FST.Arc<T> arc = getArc(upto);
+ int targetLabel = getTargetLabel();
+
+ //System.out.println("FE: init targetLabel=" + targetLabel);
+
+ // Now scan forward, matching the new suffix of the target
+ while(true) {
+ //System.out.println(" cycle upto=" + upto + " arc.label=" + arc.label + " (" + (char) arc.label + ") targetLabel=" + targetLabel + " isLast?=" + arc.isLast());
+
+ if (arc.bytesPerArc != 0 && arc.label != FST.END_LABEL) {
+ // Arcs are fixed array -- use binary search to find
+ // the target.
+
+ final FST<T>.BytesReader in = fst.getBytesReader(0);
+ int low = arc.arcIdx;
+ int high = arc.numArcs-1;
+ int mid = 0;
+ //System.out.println("do arc array low=" + low + " high=" + high + " targetLabel=" + targetLabel);
+ boolean found = false;
+ while (low <= high) {
+ mid = (low + high) >>> 1;
+ in.pos = arc.posArcsStart - arc.bytesPerArc*mid - 1;
+ final int midLabel = fst.readLabel(in);
+ final int cmp = midLabel - targetLabel;
+ //System.out.println(" cycle low=" + low + " high=" + high + " mid=" + mid + " midLabel=" + midLabel + " cmp=" + cmp);
+ if (cmp < 0)
+ low = mid + 1;
+ else if (cmp > 0)
+ high = mid - 1;
+ else {
+ found = true;
+ break;
+ }
+ }
+
+ // NOTE: this code is dup'd w/ the code below (in
+ // the outer else clause):
+ if (found) {
+ // Match -- recurse
+ //System.out.println(" match! arcIdx=" + mid);
+ arc.arcIdx = mid-1;
+ fst.readNextRealArc(arc, in);
+ assert arc.arcIdx == mid;
+ assert arc.label == targetLabel: "arc.label=" + arc.label + " vs targetLabel=" + targetLabel + " mid=" + mid;
+ output[upto] = fst.outputs.add(output[upto-1], arc.output);
+ if (targetLabel == FST.END_LABEL) {
+ return;
+ }
+ setCurrentLabel(arc.label);
+ incr();
+ arc = fst.readFirstTargetArc(arc, getArc(upto));
+ targetLabel = getTargetLabel();
+ continue;
+ } else if (high == -1) {
+ //System.out.println(" before first");
+ // Very first arc is after our target
+ // TODO: if each arc could somehow read the arc just
+ // before, we can save this re-scan. The ceil case
+ // doesn't need this because it reads the next arc
+ // instead:
+ while(true) {
+ // First, walk backwards until we find a first arc
+ // that's before our target label:
+ fst.readFirstTargetArc(getArc(upto-1), arc);
+ if (arc.label < targetLabel) {
+ // Then, scan forwards to the arc just before
+ // the targetLabel:
+ while(!arc.isLast() && fst.readNextArcLabel(arc) < targetLabel) {
+ fst.readNextArc(arc);
+ }
+ pushLast();
+ return;
+ }
+ upto--;
+ if (upto == 0) {
+ return;
+ }
+ targetLabel = getTargetLabel();
+ arc = getArc(upto);
+ }
+ } else {
+ // There is a floor arc:
+ arc.arcIdx = (low > high ? high : low)-1;
+ //System.out.println(" hasFloor arcIdx=" + (arc.arcIdx+1));
+ fst.readNextRealArc(arc, in);
+ assert arc.isLast() || fst.readNextArcLabel(arc) > targetLabel;
+ assert arc.label < targetLabel;
+ pushLast();
+ return;
+ }
+ } else {
+
+ if (arc.label == targetLabel) {
+ // Match -- recurse
+ output[upto] = fst.outputs.add(output[upto-1], arc.output);
+ if (targetLabel == FST.END_LABEL) {
+ return;
+ }
+ setCurrentLabel(arc.label);
+ incr();
+ arc = fst.readFirstTargetArc(arc, getArc(upto));
+ targetLabel = getTargetLabel();
+ } else if (arc.label > targetLabel) {
+ // TODO: if each arc could somehow read the arc just
+ // before, we can save this re-scan. The ceil case
+ // doesn't need this because it reads the next arc
+ // instead:
+ while(true) {
+ // First, walk backwards until we find a first arc
+ // that's before our target label:
+ fst.readFirstTargetArc(getArc(upto-1), arc);
+ if (arc.label < targetLabel) {
+ // Then, scan forwards to the arc just before
+ // the targetLabel:
+ while(!arc.isLast() && fst.readNextArcLabel(arc) < targetLabel) {
+ fst.readNextArc(arc);
+ }
+ pushLast();
+ return;
+ }
+ upto--;
+ if (upto == 0) {
+ return;
+ }
+ targetLabel = getTargetLabel();
+ arc = getArc(upto);
+ }
+ } else if (!arc.isLast()) {
+ //System.out.println(" check next label=" + fst.readNextArcLabel(arc) + " (" + (char) fst.readNextArcLabel(arc) + ")");
+ if (fst.readNextArcLabel(arc) > targetLabel) {
+ pushLast();
+ return;
+ } else {
+ // keep scanning
+ fst.readNextArc(arc);
+ }
+ } else {
+ pushLast();
+ return;
+ }
+ }
+ }
+ }
+
+ private void incr() {
+ upto++;
+ grow();
+ if (arcs.length <= upto) {
+ @SuppressWarnings("unchecked") final FST.Arc<T>[] newArcs =
+ new FST.Arc[ArrayUtil.oversize(1+upto, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
+ System.arraycopy(arcs, 0, newArcs, 0, arcs.length);
+ arcs = newArcs;
+ }
+ if (output.length <= upto) {
+ @SuppressWarnings("unchecked") final T[] newOutput =
+ (T[]) new Object[ArrayUtil.oversize(1+upto, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
+ System.arraycopy(output, 0, newOutput, 0, output.length);
+ output = newOutput;
+ }
+ }
+
+ // Appends current arc, and then recurses from its target,
+ // appending first arc all the way to the final node
+ private void pushFirst() throws IOException {
+
+ FST.Arc<T> arc = arcs[upto];
+ assert arc != null;
+
+ while (true) {
+ output[upto] = fst.outputs.add(output[upto-1], arc.output);
+ if (arc.label == FST.END_LABEL) {
+ // Final node
+ break;
+ }
+ //System.out.println(" pushFirst label=" + (char) arc.label + " upto=" + upto + " output=" + fst.outputs.outputToString(output[upto]));
+ setCurrentLabel(arc.label);
+ incr();
+
+ final FST.Arc<T> nextArc = getArc(upto);
+ fst.readFirstTargetArc(arc, nextArc);
+ arc = nextArc;
+ }
+ }
+
+ // Recurses from current arc, appending last arc all the
+ // way to the first final node
+ private void pushLast() throws IOException {
+
+ FST.Arc<T> arc = arcs[upto];
+ assert arc != null;
+
+ while (true) {
+ setCurrentLabel(arc.label);
+ output[upto] = fst.outputs.add(output[upto-1], arc.output);
+ if (arc.label == FST.END_LABEL) {
+ // Final node
+ break;
+ }
+ incr();
+
+ arc = fst.readLastTargetArc(arc, getArc(upto));
+ }
+ }
+
+ private FST.Arc<T> getArc(int idx) {
+ if (arcs[idx] == null) {
+ arcs[idx] = new FST.Arc<T>();
+ }
+ return arcs[idx];
+ }
+}
fnp / pylucene.git / blobdiff