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;

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

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

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

        if (child.childrend.length == 1) {
          final subchild = child.childrend.first;
          child.prefix = child.prefix + subchild.prefix;
          child.value = subchild.value;
          child.childrend.clear();
        }

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

    i += 1;
  }

  return result;
}