removeValue<T> static method

T? removeValue<T>(RadixTreeNode<T> node, String key)

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

Implementation

static T? removeValue<T>(RadixTreeNode<T> node, String key) {
  T? result;

  var childrend = node.children.toList();
  var i = 0;

  while (i < childrend.length) {
    var child = childrend[i];
    var largestPrefix = largestPrefixLength(key, child.prefix);

    if (largestPrefix == child.prefix.length && largestPrefix == key.length) {
      if (child.children.isEmpty) {
        result = child.value;
        node.children.remove(child);
      } else if (child.hasValue) {
        result = child.value;
        child.value = null;

        if (child.children.length == 1) {
          var subchild = child.children.first;

          child
            ..prefix = child.prefix + subchild.prefix
            ..value = subchild.value
            ..children.clear();
        }

        break;
      }
    } else if (largestPrefix > 0 && largestPrefix < key.length) {
      var leftoverKey = key.substring(largestPrefix);
      result = removeValue<T>(child, leftoverKey);
      break;
    }

    i += 1;
  }

  return result;
}