putValue<T> static method

void putValue<T>(RadixTreeNode<T> node, String key, T? value)

Put the value with the given key from the subtree rooted at the given node.

Implementation

static void putValue<T>(RadixTreeNode<T> node, String key, T? value) {
  final largestPrefix = largestPrefixLength(key, node.prefix);

  if (largestPrefix == node.prefix.length && largestPrefix == key.length) {
    // Exact match, update the value here.
    node.value = value;
  } else if (largestPrefix == 0 ||
      (largestPrefix < key.length && largestPrefix == node.prefix.length)) {
    // Key we're looking for shares no common prefix (e.g. at the root), OR
    // Key we're looking for subsumes this node's string.
    final leftOverKey = key.substring(largestPrefix);
    var found = false;

    // Try to find a child node that continues matching the remainder.
    for (final child in node) {
      if (child.prefix[0] == leftOverKey[0]) {
        found = true;
        putValue<T>(child, leftOverKey, value);
        break;
      }
    }
    // Otherwise add the remainder as a child of this node.
    if (!found) {
      final newNode = RadixTreeNode<T>(leftOverKey, value);
      node.childrend.add(newNode);
    }
  } else {
    // case largestPrefix < node.prefix.length:
    // Key we're looking for shares a non-empty subset of this node's string.
    final leftOverPrefix = node.prefix.substring(largestPrefix);
    final newNode = RadixTreeNode<T>(leftOverPrefix, node.value);
    newNode.childrend.addAll(node.childrend);

    node.prefix = node.prefix.substring(0, largestPrefix);
    node.childrend.clear();
    node.childrend.add(newNode);

    if (largestPrefix == key.length) {
      node.value = value;
    } else {
      final leftOverKey = key.substring(largestPrefix);
      final keyNode = RadixTreeNode<T>(leftOverKey, value);
      node.childrend.add(keyNode);
      node.value = null;
    }
  }
}