public static Automaton makeBinaryInterval()

in lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java [276:478]
157 lines of code
50 McCabe index (conditional complexity)

  public static Automaton makeBinaryInterval(
      BytesRef min, boolean minInclusive, BytesRef max, boolean maxInclusive) {

    if (min == null && minInclusive == false) {
      throw new IllegalArgumentException("minInclusive must be true when min is null (open ended)");
    }

    if (max == null && maxInclusive == false) {
      throw new IllegalArgumentException("maxInclusive must be true when max is null (open ended)");
    }

    if (min == null) {
      min = new BytesRef();
      minInclusive = true;
    }

    int cmp;
    if (max != null) {
      cmp = min.compareTo(max);
    } else {
      cmp = -1;
      if (min.length == 0) {
        if (minInclusive) {
          return makeAnyBinary();
        } else {
          return makeNonEmptyBinary();
        }
      }
    }

    if (cmp == 0) {
      if (minInclusive == false || maxInclusive == false) {
        return makeEmpty();
      } else {
        return makeBinary(min);
      }
    } else if (cmp > 0) {
      // max < min
      return makeEmpty();
    }

    if (max != null && StringHelper.startsWith(max, min) && suffixIsZeros(max, min.length)) {

      // Finite case: no sink state!

      int maxLength = max.length;

      // the == case was handled above
      assert maxLength > min.length;

      //  bar -> bar\0+
      if (maxInclusive == false) {
        maxLength--;
      }

      if (maxLength == min.length) {
        if (minInclusive == false) {
          return makeEmpty();
        } else {
          return makeBinary(min);
        }
      }

      Automaton a = new Automaton();
      int lastState = a.createState();
      for (int i = 0; i < min.length; i++) {
        int state = a.createState();
        int label = min.bytes[min.offset + i] & 0xff;
        a.addTransition(lastState, state, label);
        lastState = state;
      }

      if (minInclusive) {
        a.setAccept(lastState, true);
      }

      for (int i = min.length; i < maxLength; i++) {
        int state = a.createState();
        a.addTransition(lastState, state, 0);
        a.setAccept(state, true);
        lastState = state;
      }
      a.finishState();
      return a;
    }

    Automaton a = new Automaton();
    int startState = a.createState();

    int sinkState = a.createState();
    a.setAccept(sinkState, true);

    // This state accepts all suffixes:
    a.addTransition(sinkState, sinkState, 0, 255);

    boolean equalPrefix = true;
    int lastState = startState;
    int firstMaxState = -1;
    int sharedPrefixLength = 0;
    for (int i = 0; i < min.length; i++) {
      int minLabel = min.bytes[min.offset + i] & 0xff;

      int maxLabel;
      if (max != null && equalPrefix && i < max.length) {
        maxLabel = max.bytes[max.offset + i] & 0xff;
      } else {
        maxLabel = -1;
      }

      int nextState;
      if (minInclusive && i == min.length - 1 && (equalPrefix == false || minLabel != maxLabel)) {
        nextState = sinkState;
      } else {
        nextState = a.createState();
      }

      if (equalPrefix) {

        if (minLabel == maxLabel) {
          // Still in shared prefix
          a.addTransition(lastState, nextState, minLabel);
        } else if (max == null) {
          equalPrefix = false;
          sharedPrefixLength = 0;
          a.addTransition(lastState, sinkState, minLabel + 1, 0xff);
          a.addTransition(lastState, nextState, minLabel);
        } else {
          // This is the first point where min & max diverge:
          assert maxLabel > minLabel;

          a.addTransition(lastState, nextState, minLabel);

          if (maxLabel > minLabel + 1) {
            a.addTransition(lastState, sinkState, minLabel + 1, maxLabel - 1);
          }

          // Now fork off path for max:
          if (maxInclusive || i < max.length - 1) {
            firstMaxState = a.createState();
            if (i < max.length - 1) {
              a.setAccept(firstMaxState, true);
            }
            a.addTransition(lastState, firstMaxState, maxLabel);
          }
          equalPrefix = false;
          sharedPrefixLength = i;
        }
      } else {
        // OK, already diverged:
        a.addTransition(lastState, nextState, minLabel);
        if (minLabel < 255) {
          a.addTransition(lastState, sinkState, minLabel + 1, 255);
        }
      }
      lastState = nextState;
    }

    // Accept any suffix appended to the min term:
    if (equalPrefix == false && lastState != sinkState && lastState != startState) {
      a.addTransition(lastState, sinkState, 0, 255);
    }

    if (minInclusive) {
      // Accept exactly the min term:
      a.setAccept(lastState, true);
    }

    if (max != null) {

      // Now do max:
      if (firstMaxState == -1) {
        // Min was a full prefix of max
        sharedPrefixLength = min.length;
      } else {
        lastState = firstMaxState;
        sharedPrefixLength++;
      }
      for (int i = sharedPrefixLength; i < max.length; i++) {
        int maxLabel = max.bytes[max.offset + i] & 0xff;
        if (maxLabel > 0) {
          a.addTransition(lastState, sinkState, 0, maxLabel - 1);
        }
        if (maxInclusive || i < max.length - 1) {
          int nextState = a.createState();
          if (i < max.length - 1) {
            a.setAccept(nextState, true);
          }
          a.addTransition(lastState, nextState, maxLabel);
          lastState = nextState;
        }
      }

      if (maxInclusive) {
        a.setAccept(lastState, true);
      }
    }

    a.finishState();

    assert a.isDeterministic() : a.toDot();

    return a;
  }