TokenSet.fromFuzzyString constructor

TokenSet.fromFuzzyString(String str, int editDistance)

Implementation

factory TokenSet.fromFuzzyString(String str, int editDistance) {
  var root = TokenSet();

  Stack stack = [Frame(node: root, editsRemaining: editDistance, str: str)];

  while (stack.isNotEmpty) {
    Frame frame = stack.removeLast();

    // no edit
    if (frame.str.isNotEmpty) {
      String char = frame.str[0];
      TokenSet noEditNode;

      if (frame.node.edges.containsKey(char)) {
        noEditNode = frame.node.edges[char]!;
      } else {
        noEditNode = TokenSet();
        frame.node.edges[char] = noEditNode;
      }

      if (frame.str.length == 1) {
        noEditNode.isFinal = true;
      }

      stack.add(Frame(
          node: noEditNode,
          editsRemaining: frame.editsRemaining,
          str: frame.str.substring(1)));
    }

    if (frame.editsRemaining == 0) {
      continue;
    }

    TokenSet insertionNode;
    // insertion
    if (frame.node.edges.containsKey('*')) {
      insertionNode = frame.node.edges["*"]!;
    } else {
      insertionNode = TokenSet();
      frame.node.edges["*"] = insertionNode;
    }

    if (frame.str.isEmpty) {
      insertionNode.isFinal = true;
    }

    stack.add(Frame(
        node: insertionNode,
        editsRemaining: frame.editsRemaining - 1,
        str: frame.str));

    // deletion
    // can only do a deletion if we have enough edits remaining
    // and if there are characters left to delete in the string
    if (frame.str.length > 1) {
      stack.add(Frame(
          node: frame.node,
          editsRemaining: frame.editsRemaining - 1,
          str: frame.str.substring(1)));
    }

    // deletion
    // just removing the last character from the str
    if (frame.str.length == 1) {
      frame.node.isFinal = true;
    }

    // substitution
    // can only do a substitution if we have enough edits remaining
    // and if there are characters left to substitute
    TokenSet substitutionNode;
    if (frame.str.isNotEmpty) {
      if (frame.node.edges.containsKey("*")) {
        substitutionNode = frame.node.edges["*"]!;
      } else {
        substitutionNode = TokenSet();
        frame.node.edges["*"] = substitutionNode;
      }

      if (frame.str.length == 1) {
        substitutionNode.isFinal = true;
      }

      stack.add(Frame(
          node: substitutionNode,
          editsRemaining: frame.editsRemaining - 1,
          str: frame.str.substring(1)));
    }

    // transposition
    // can only do a transposition if there are edits remaining
    // and there are enough characters to transpose
    if (frame.str.length > 1) {
      var charA = frame.str[0], charB = frame.str[1];
      TokenSet transposeNode;

      if (frame.node.edges.containsKey(charB)) {
        transposeNode = frame.node.edges[charB]!;
      } else {
        transposeNode = TokenSet();
        frame.node.edges[charB] = transposeNode;
      }

      if (frame.str.length == 1) {
        transposeNode.isFinal = true;
      }

      stack.add(Frame(
          node: transposeNode,
          editsRemaining: frame.editsRemaining - 1,
          str: charA + frame.str.substring(2)));
    }
  }

  return root;
}