lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/fst/FSTEnum.java

   1 package org.apache.lucene.util.fst;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import org.apache.lucene.util.ArrayUtil;
  21 import org.apache.lucene.util.RamUsageEstimator;
  22
  23 import java.io.IOException;
  24
  25 /** Can next() and advance() through the terms in an FST
  26  *
  27   * @lucene.experimental
  28 */
  29
  30 abstract class FSTEnum<T> {
  31   protected final FST<T> fst;
  32
  33   @SuppressWarnings("unchecked") protected FST.Arc<T>[] arcs = new FST.Arc[10];
  34   // outputs are cumulative
  35   @SuppressWarnings("unchecked") protected T[] output = (T[]) new Object[10];
  36
  37   protected final T NO_OUTPUT;
  38   protected final FST.Arc<T> scratchArc = new FST.Arc<T>();
  39
  40   protected int upto;
  41   protected int targetLength;
  42
  43   /** doFloor controls the behavior of advance: if it's true
  44    *  doFloor is true, advance positions to the biggest
  45    *  term before target.  */
  46   protected FSTEnum(FST<T> fst) {
  47     this.fst = fst;
  48     NO_OUTPUT = fst.outputs.getNoOutput();
  49     fst.getFirstArc(getArc(0));
  50     output[0] = NO_OUTPUT;
  51   }
  52
  53   protected abstract int getTargetLabel();
  54   protected abstract int getCurrentLabel();
  55
  56   protected abstract void setCurrentLabel(int label);
  57   protected abstract void grow();
  58
  59   /** Rewinds enum state to match the shared prefix between
  60    *  current term and target term */
  61   protected final void rewindPrefix() throws IOException {
  62     if (upto == 0) {
  63       //System.out.println("  init");
  64       upto = 1;
  65       fst.readFirstTargetArc(getArc(0), getArc(1));
  66       return;
  67     }
  68     //System.out.println("  rewind upto=" + upto + " vs targetLength=" + targetLength);
  69
  70     final int currentLimit = upto;
  71     upto = 1;
  72     while (upto < currentLimit && upto <= targetLength+1) {
  73       final int cmp = getCurrentLabel() - getTargetLabel();
  74       if (cmp < 0) {
  75         // seek forward
  76         break;
  77       } else if (cmp > 0) {
  78         // seek backwards -- reset this arc to the first arc
  79         final FST.Arc<T> arc = getArc(upto);
  80         fst.readFirstTargetArc(getArc(upto-1), arc);
  81         //System.out.println("    seek first arc");
  82         break;
  83       }
  84       upto++;
  85     }
  86   }
  87
  88   protected void doNext() throws IOException {
  89     //System.out.println("FE: next upto=" + upto);
  90     if (upto == 0) {
  91       //System.out.println("  init");
  92       upto = 1;
  93       fst.readFirstTargetArc(getArc(0), getArc(1));
  94     } else {
  95       // pop
  96       //System.out.println("  check pop curArc target=" + arcs[upto].target + " label=" + arcs[upto].label + " isLast?=" + arcs[upto].isLast());
  97       while (arcs[upto].isLast()) {
  98         upto--;
  99         if (upto == 0) {
 100           //System.out.println("  eof");
 101           return;
 102         }
 103       }
 104       fst.readNextArc(arcs[upto]);
 105     }
 106
 107     pushFirst();
 108   }
 109
 110   // TODO: should we return a status here (SEEK_FOUND / SEEK_NOT_FOUND /
 111   // SEEK_END)?  saves the eq check above?
 112
 113   /** Seeks to smallest term that's >= target. */
 114   protected void doSeekCeil() throws IOException {
 115
 116     //System.out.println("    advance len=" + target.length + " curlen=" + current.length);
 117
 118     // TODO: possibly caller could/should provide common
 119     // prefix length?  ie this work may be redundant if
 120     // caller is in fact intersecting against its own
 121     // automaton
 122
 123     //System.out.println("FE.seekCeil upto=" + upto);
 124
 125     // Save time by starting at the end of the shared prefix
 126     // b/w our current term & the target:
 127     rewindPrefix();
 128     //System.out.println("  after rewind upto=" + upto);
 129
 130     FST.Arc<T> arc = getArc(upto);
 131     int targetLabel = getTargetLabel();
 132     //System.out.println("  init targetLabel=" + targetLabel);
 133
 134     // Now scan forward, matching the new suffix of the target
 135     while(true) {
 136
 137       //System.out.println("  cycle upto=" + upto + " arc.label=" + arc.label + " (" + (char) arc.label + ") vs targetLabel=" + targetLabel);
 138
 139       if (arc.bytesPerArc != 0 && arc.label != -1) {
 140
 141         // Arcs are fixed array -- use binary search to find
 142         // the target.
 143
 144         final FST<T>.BytesReader in = fst.getBytesReader(0);
 145         int low = arc.arcIdx;
 146         int high = arc.numArcs-1;
 147         int mid = 0;
 148         //System.out.println("do arc array low=" + low + " high=" + high + " targetLabel=" + targetLabel);
 149         boolean found = false;
 150         while (low <= high) {
 151           mid = (low + high) >>> 1;
 152           in.pos = arc.posArcsStart - arc.bytesPerArc*mid - 1;
 153           final int midLabel = fst.readLabel(in);
 154           final int cmp = midLabel - targetLabel;
 155           //System.out.println("  cycle low=" + low + " high=" + high + " mid=" + mid + " midLabel=" + midLabel + " cmp=" + cmp);
 156           if (cmp < 0)
 157             low = mid + 1;
 158           else if (cmp > 0)
 159             high = mid - 1;
 160           else {
 161             found = true;
 162             break;
 163           }
 164         }
 165
 166         // NOTE: this code is dup'd w/ the code below (in
 167         // the outer else clause):
 168         if (found) {
 169           // Match
 170           arc.arcIdx = mid-1;
 171           fst.readNextRealArc(arc, in);
 172           assert arc.arcIdx == mid;
 173           assert arc.label == targetLabel: "arc.label=" + arc.label + " vs targetLabel=" + targetLabel + " mid=" + mid;
 174           output[upto] = fst.outputs.add(output[upto-1], arc.output);
 175           if (targetLabel == FST.END_LABEL) {
 176             return;
 177           }
 178           setCurrentLabel(arc.label);
 179           incr();
 180           arc = fst.readFirstTargetArc(arc, getArc(upto));
 181           targetLabel = getTargetLabel();
 182           continue;
 183         } else if (low == arc.numArcs) {
 184           // Dead end
 185           arc.arcIdx = arc.numArcs-2;
 186           fst.readNextRealArc(arc, in);
 187           assert arc.isLast();
 188           // Dead end (target is after the last arc);
 189           // rollback to last fork then push
 190           upto--;
 191           while(true) {
 192             if (upto == 0) {
 193               return;
 194             }
 195             final FST.Arc<T> prevArc = getArc(upto);
 196             //System.out.println("  rollback upto=" + upto + " arc.label=" + prevArc.label + " isLast?=" + prevArc.isLast());
 197             if (!prevArc.isLast()) {
 198               fst.readNextArc(prevArc);
 199               pushFirst();
 200               return;
 201             }
 202             upto--;
 203           }
 204         } else {
 205           arc.arcIdx = (low > high ? low : high)-1;
 206           fst.readNextRealArc(arc, in);
 207           assert arc.label > targetLabel;
 208           pushFirst();
 209           return;
 210         }
 211       } else {
 212         // Arcs are not array'd -- must do linear scan:
 213         if (arc.label == targetLabel) {
 214           // recurse
 215           output[upto] = fst.outputs.add(output[upto-1], arc.output);
 216           if (targetLabel == FST.END_LABEL) {
 217             return;
 218           }
 219           setCurrentLabel(arc.label);
 220           incr();
 221           arc = fst.readFirstTargetArc(arc, getArc(upto));
 222           targetLabel = getTargetLabel();
 223         } else if (arc.label > targetLabel) {
 224           pushFirst();
 225           return;
 226         } else if (arc.isLast()) {
 227           // Dead end (target is after the last arc);
 228           // rollback to last fork then push
 229           upto--;
 230           while(true) {
 231             if (upto == 0) {
 232               return;
 233             }
 234             final FST.Arc<T> prevArc = getArc(upto);
 235             //System.out.println("  rollback upto=" + upto + " arc.label=" + prevArc.label + " isLast?=" + prevArc.isLast());
 236             if (!prevArc.isLast()) {
 237               fst.readNextArc(prevArc);
 238               pushFirst();
 239               return;
 240             }
 241             upto--;
 242           }
 243         } else {
 244           // keep scanning
 245           //System.out.println("    next scan");
 246           fst.readNextArc(arc);
 247         }
 248       }
 249     }
 250   }
 251
 252   // TODO: should we return a status here (SEEK_FOUND / SEEK_NOT_FOUND /
 253   // SEEK_END)?  saves the eq check above?
 254   /** Seeks to largest term that's <= target. */
 255   protected void doSeekFloor() throws IOException {
 256
 257     // TODO: possibly caller could/should provide common
 258     // prefix length?  ie this work may be redundant if
 259     // caller is in fact intersecting against its own
 260     // automaton
 261     //System.out.println("FE: seek floor upto=" + upto);
 262
 263     // Save CPU by starting at the end of the shared prefix
 264     // b/w our current term & the target:
 265     rewindPrefix();
 266
 267     //System.out.println("FE: after rewind upto=" + upto);
 268
 269     FST.Arc<T> arc = getArc(upto);
 270     int targetLabel = getTargetLabel();
 271
 272     //System.out.println("FE: init targetLabel=" + targetLabel);
 273
 274     // Now scan forward, matching the new suffix of the target
 275     while(true) {
 276       //System.out.println("  cycle upto=" + upto + " arc.label=" + arc.label + " (" + (char) arc.label + ") targetLabel=" + targetLabel + " isLast?=" + arc.isLast());
 277
 278       if (arc.bytesPerArc != 0 && arc.label != FST.END_LABEL) {
 279         // Arcs are fixed array -- use binary search to find
 280         // the target.
 281
 282         final FST<T>.BytesReader in = fst.getBytesReader(0);
 283         int low = arc.arcIdx;
 284         int high = arc.numArcs-1;
 285         int mid = 0;
 286         //System.out.println("do arc array low=" + low + " high=" + high + " targetLabel=" + targetLabel);
 287         boolean found = false;
 288         while (low <= high) {
 289           mid = (low + high) >>> 1;
 290           in.pos = arc.posArcsStart - arc.bytesPerArc*mid - 1;
 291           final int midLabel = fst.readLabel(in);
 292           final int cmp = midLabel - targetLabel;
 293           //System.out.println("  cycle low=" + low + " high=" + high + " mid=" + mid + " midLabel=" + midLabel + " cmp=" + cmp);
 294           if (cmp < 0)
 295             low = mid + 1;
 296           else if (cmp > 0)
 297             high = mid - 1;
 298           else {
 299             found = true;
 300             break;
 301           }
 302         }
 303
 304         // NOTE: this code is dup'd w/ the code below (in
 305         // the outer else clause):
 306         if (found) {
 307           // Match -- recurse
 308           //System.out.println("  match!  arcIdx=" + mid);
 309           arc.arcIdx = mid-1;
 310           fst.readNextRealArc(arc, in);
 311           assert arc.arcIdx == mid;
 312           assert arc.label == targetLabel: "arc.label=" + arc.label + " vs targetLabel=" + targetLabel + " mid=" + mid;
 313           output[upto] = fst.outputs.add(output[upto-1], arc.output);
 314           if (targetLabel == FST.END_LABEL) {
 315             return;
 316           }
 317           setCurrentLabel(arc.label);
 318           incr();
 319           arc = fst.readFirstTargetArc(arc, getArc(upto));
 320           targetLabel = getTargetLabel();
 321           continue;
 322         } else if (high == -1) {
 323           //System.out.println("  before first");
 324           // Very first arc is after our target
 325           // TODO: if each arc could somehow read the arc just
 326           // before, we can save this re-scan.  The ceil case
 327           // doesn't need this because it reads the next arc
 328           // instead:
 329           while(true) {
 330             // First, walk backwards until we find a first arc
 331             // that's before our target label:
 332             fst.readFirstTargetArc(getArc(upto-1), arc);
 333             if (arc.label < targetLabel) {
 334               // Then, scan forwards to the arc just before
 335               // the targetLabel:
 336               while(!arc.isLast() && fst.readNextArcLabel(arc) < targetLabel) {
 337                 fst.readNextArc(arc);
 338               }
 339               pushLast();
 340               return;
 341             }
 342             upto--;
 343             if (upto == 0) {
 344               return;
 345             }
 346             targetLabel = getTargetLabel();
 347             arc = getArc(upto);
 348           }
 349         } else {
 350           // There is a floor arc:
 351           arc.arcIdx = (low > high ? high : low)-1;
 352           //System.out.println(" hasFloor arcIdx=" + (arc.arcIdx+1));
 353           fst.readNextRealArc(arc, in);
 354           assert arc.isLast() || fst.readNextArcLabel(arc) > targetLabel;
 355           assert arc.label < targetLabel;
 356           pushLast();
 357           return;
 358         }
 359       } else {
 360
 361         if (arc.label == targetLabel) {
 362           // Match -- recurse
 363           output[upto] = fst.outputs.add(output[upto-1], arc.output);
 364           if (targetLabel == FST.END_LABEL) {
 365             return;
 366           }
 367           setCurrentLabel(arc.label);
 368           incr();
 369           arc = fst.readFirstTargetArc(arc, getArc(upto));
 370           targetLabel = getTargetLabel();
 371         } else if (arc.label > targetLabel) {
 372           // TODO: if each arc could somehow read the arc just
 373           // before, we can save this re-scan.  The ceil case
 374           // doesn't need this because it reads the next arc
 375           // instead:
 376           while(true) {
 377             // First, walk backwards until we find a first arc
 378             // that's before our target label:
 379             fst.readFirstTargetArc(getArc(upto-1), arc);
 380             if (arc.label < targetLabel) {
 381               // Then, scan forwards to the arc just before
 382               // the targetLabel:
 383               while(!arc.isLast() && fst.readNextArcLabel(arc) < targetLabel) {
 384                 fst.readNextArc(arc);
 385               }
 386               pushLast();
 387               return;
 388             }
 389             upto--;
 390             if (upto == 0) {
 391               return;
 392             }
 393             targetLabel = getTargetLabel();
 394             arc = getArc(upto);
 395           }
 396         } else if (!arc.isLast()) {
 397           //System.out.println("  check next label=" + fst.readNextArcLabel(arc) + " (" + (char) fst.readNextArcLabel(arc) + ")");
 398           if (fst.readNextArcLabel(arc) > targetLabel) {
 399             pushLast();
 400             return;
 401           } else {
 402             // keep scanning
 403             fst.readNextArc(arc);
 404           }
 405         } else {
 406           pushLast();
 407           return;
 408         }
 409       }
 410     }
 411   }
 412
 413   private void incr() {
 414     upto++;
 415     grow();
 416     if (arcs.length <= upto) {
 417       @SuppressWarnings("unchecked") final FST.Arc<T>[] newArcs =
 418         new FST.Arc[ArrayUtil.oversize(1+upto, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
 419       System.arraycopy(arcs, 0, newArcs, 0, arcs.length);
 420       arcs = newArcs;
 421     }
 422     if (output.length <= upto) {
 423       @SuppressWarnings("unchecked") final T[] newOutput =
 424         (T[]) new Object[ArrayUtil.oversize(1+upto, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
 425       System.arraycopy(output, 0, newOutput, 0, output.length);
 426       output = newOutput;
 427     }
 428   }
 429
 430   // Appends current arc, and then recurses from its target,
 431   // appending first arc all the way to the final node
 432   private void pushFirst() throws IOException {
 433
 434     FST.Arc<T> arc = arcs[upto];
 435     assert arc != null;
 436
 437     while (true) {
 438       output[upto] = fst.outputs.add(output[upto-1], arc.output);
 439       if (arc.label == FST.END_LABEL) {
 440         // Final node
 441         break;
 442       }
 443       //System.out.println("  pushFirst label=" + (char) arc.label + " upto=" + upto + " output=" + fst.outputs.outputToString(output[upto]));
 444       setCurrentLabel(arc.label);
 445       incr();
 446
 447       final FST.Arc<T> nextArc = getArc(upto);
 448       fst.readFirstTargetArc(arc, nextArc);
 449       arc = nextArc;
 450     }
 451   }
 452
 453   // Recurses from current arc, appending last arc all the
 454   // way to the first final node
 455   private void pushLast() throws IOException {
 456
 457     FST.Arc<T> arc = arcs[upto];
 458     assert arc != null;
 459
 460     while (true) {
 461       setCurrentLabel(arc.label);
 462       output[upto] = fst.outputs.add(output[upto-1], arc.output);
 463       if (arc.label == FST.END_LABEL) {
 464         // Final node
 465         break;
 466       }
 467       incr();
 468
 469       arc = fst.readLastTargetArc(arc, getArc(upto));
 470     }
 471   }
 472
 473   private FST.Arc<T> getArc(int idx) {
 474     if (arcs[idx] == null) {
 475       arcs[idx] = new FST.Arc<T>();
 476     }
 477     return arcs[idx];
 478   }
 479 }