2
\$\begingroup\$

Introduction

I have this semi-dynamic range minimum query (RMQ) tree in Java. It is called semi-dynamic due to the fact that it cannot be modified after it is constructed. However, the values associated with the keys may be updated.

An RMQ tree maintains a set of (distinct) keys and associates a value with each key. The tree in question provides two important operations:

  • update(key, value) - if value associated with the key key is smaller than the current value of key (current_value), sets the value of the key to value overwriting the current_value,
  • getRangeMinimum(leftKey, rightKey) - in the range R = [leftKey ... rightKey] returns the minimum value stored somewhere in R.

Both above operations run in exact \$\Theta(\log n)\$ time where \$n\$ is the number of keys in the tree. Building the tree runs in \$\mathcal{O}(n \log n)\$ time.

Also note that all keys are associated with only leaf nodes of the tree and if we traverse the leaves from left to right, the keys will come out in strictly increasing order, that is, the keys are stored in sorted order.

Code

com.github.coderodde.util.AbstractRMQTreeNode.java:

package com.github.coderodde.util;

public abstract class AbstractRMQTreeNode<V> {
    
    protected V value;
    protected AbstractRMQTreeNode<V> parent;

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public AbstractRMQTreeNode<V> getParent() {
        return parent;
    }

    public void setParent(AbstractRMQTreeNode<V> parent) {
        this.parent = parent;
    }
}

com.github.coderodde.util.InternalRMQTreeNode.java:

package com.github.coderodde.util;

import java.util.Objects;

public final class InternalRMQTreeNode<V> extends AbstractRMQTreeNode<V> {
    
    private AbstractRMQTreeNode<V> leftChild;
    private AbstractRMQTreeNode<V> rightChild;

    public AbstractRMQTreeNode<V> getLeftChild() {
        return leftChild;
    }

    public AbstractRMQTreeNode<V> getRightChild() {
        return rightChild;
    }

    public void setLeftChild(AbstractRMQTreeNode<V> leftChild) {
        this.leftChild = leftChild;
    }

    public void setRightChild(AbstractRMQTreeNode<V> rightChild) {
        this.rightChild = rightChild;
    }
    
    @Override
    public String toString() {
        return String.format("[INTERNAL: value = \"%s\"]", 
                             Objects.toString(value));
    }
}

com.github.coderodde.util.LeafRMQTreeNode.java:

package com.github.coderodde.util;

import java.util.Objects;

public final class LeafRMQTreeNode<V> extends AbstractRMQTreeNode<V> {
    
    @Override
    public String toString() {
        return String.format("[LEAF: value = \"%s\"]",
                             Objects.toString(getValue()));
    }
}

com.github.coderodde.util.KeyValuePair.java:

package com.github.coderodde.util;

import java.util.Objects;

public final class KeyValuePair<K extends Comparable<? super K>, V>
        
implements Comparable<KeyValuePair<K, V>> {
    
    private final K key;
    private final V value;
    
    public KeyValuePair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public int compareTo(KeyValuePair<K, V> o) {
        return key.compareTo(o.key);
    }
    
    @Override
    public String toString() {
        return String.format("[KeyValuePair: key = \"%s\", value = \"%s\"]",
                             Objects.toString(key),
                             Objects.toString(value));
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
}

com.github.coderodde.util.SemiDynamicRMQTree.java:

package com.github.coderodde.util;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import com.github.coderodde.util.SemiDynamicRMQTreeBuilder.RMQTreeBuilderResult;
import static com.github.coderodde.util.Utils.min;

/**
 * This class implements a semi-dynamic RMQ (range minimum query) tree. While
 * it does not support modification of the tree, it supports update of leaf node
 * values. The operation 
 * {@link #update(java.lang.Comparable, java.lang.Comparable)} runs in exact
 * logarithmic time; so does the 
 * {@link #getRangeMinimum(java.lang.Comparable, java.lang.Comparable) }.
 * 
 * @param <K> the key type.
 * @param <V> the value type.
 */
public final class SemiDynamicRMQTree<K extends Comparable<? super K>,
                                      V extends Comparable<? super V>> {
    
    private final AbstractRMQTreeNode<V> root;
    private final Map<K, LeafRMQTreeNode<V>> leafMap;
    
    public SemiDynamicRMQTree(Set<KeyValuePair<K, V>> keyValuePairSet) {
        RMQTreeBuilderResult<K, V> result = 
                SemiDynamicRMQTreeBuilder.buildRMQTree(keyValuePairSet);
        
        root = result.getRoot();
        leafMap = result.getLeafMap();
    }
    
    /**
     * Returns the root node of this tree. Is package-private in order to be
     * accessible from the unit tests.
     * 
     * @return the root node of this tree. 
     */
    AbstractRMQTreeNode<V> getRoot() {
        return root;
    }
    
    /**
     * Returns the string representation of this tree.
     * 
     * @return the string representation of this tree.
     */
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        toStringImpl(stringBuilder);
        return stringBuilder.toString();
    }
    
    /**
     * Associates the value {@code newValue} with the key {@code key}. Runs in
     * exact logarithmic time.
     * 
     * @param key      the target key.
     * @param newValue the new value for the target key.
     */
    public void update(K key, V newValue) {
        AbstractRMQTreeNode<V> node = leafMap.get(key);
        
        while (node != null) {
            node.setValue(min(node.getValue(), newValue));
            node = node.getParent();
        }
    }
    
    /**
     * Given the range {@code R = [leftKey ... rightKey]}, return the minimum
     * value in {@code R}. Runs in exact logarithmic time.
     * 
     * @param leftKey  the leftmost key of the range.
     * @param rightKey the rightmost key of the range.
     * @return the minimum value in {@code R}.
     */
    public V getRangeMinimum(K leftKey, K rightKey) {
        
        AbstractRMQTreeNode<V> leftLeaf  = leafMap.get(leftKey);
        
        Objects.requireNonNull(
                leftLeaf,
                String.format(
                        "The left key [%s] is not in this tree.",
                        leftKey));
        
        AbstractRMQTreeNode<V> rightLeaf = leafMap.get(rightKey);
        
        Objects.requireNonNull(
                rightLeaf,
                String.format(
                        "The right key [%s] is not in this tree.",
                        rightKey));
        
        if (leftKey.compareTo(rightKey) > 0) {
            String exceptionMessage = 
                    String.format(
                            "The specified range [%s, %s] is descending.", 
                            leftKey, 
                            rightKey);
            
            throw new IllegalArgumentException(exceptionMessage);
        }
        
        AbstractRMQTreeNode<V> splitNode =
                computeSplitNode(leftLeaf,
                                 rightLeaf);
        
        List<AbstractRMQTreeNode<V>> leftPath = getPath(splitNode,
                                                              leftLeaf);
        
        List<AbstractRMQTreeNode<V>> rightPath = getPath(splitNode,
                                                               rightLeaf);
        
        List<AbstractRMQTreeNode<V>> leftPathV = 
                computeLeftPathV(leftPath);
        
        List<AbstractRMQTreeNode<V>> rightPathV = 
                computeRightPartV(rightPath);
        
        V vl = computeMinimum(leftPathV);
        V vr = computeMinimum(rightPathV);
        
        if (vl == null) {
            vl = leftLeaf.getValue();
        }
        
        if (vr == null) {
            vr = rightLeaf.getValue();
        }
        
        vl = min(vl, leftLeaf.getValue());
        vr = min(vr, rightLeaf.getValue());
        
        return min(vl, vr);
    }
    
    /**
     * Computes the minimum value in {@code nodes}.
     * 
     * @param <V>   the value type.
     * @param nodes the list of values.
     * @return the minimum value or {@code null} if the input list is empty.
     */
    private <V extends Comparable<? super V>>   
        V computeMinimum(List<AbstractRMQTreeNode<V>> nodes) {
        
        if (nodes.isEmpty()) {
            return null;
        }
            
        V minValue = nodes.get(0).getValue();
        
        for (int i = 1; i < nodes.size(); i++) {
            AbstractRMQTreeNode<V> node = nodes.get(i);
            
            minValue = min(minValue, node.getValue());
        }
        
        return minValue;
    }
    
    /**
     * Computes the so called {@code V'}.
     * 
     * @param path the target path.
     * @return the {@code V'} set.
     */
    private List<AbstractRMQTreeNode<V>> 
        computeLeftPathV(List<AbstractRMQTreeNode<V>> path) {
            
        Set<AbstractRMQTreeNode<V>> pathSet   = new HashSet<>(path);
        List<AbstractRMQTreeNode<V>> nodeList = new ArrayList<>();
        
        for (int i = 0; i < path.size(); i++) {
            InternalRMQTreeNode<V> parent = 
                    (InternalRMQTreeNode<V>) path.get(i);
            
            AbstractRMQTreeNode<V> leftChild  = parent.getLeftChild();
            AbstractRMQTreeNode<V> rightChild = parent.getRightChild();
            
            if (pathSet.contains(leftChild)) {
                nodeList.add(rightChild);
            }
        }
        
        return nodeList;
    }
        
    /**
     * Computes the so called {@code V''}.
     * 
     * @param path the target path.
     * @return the {@code V''} set.
     */
    private List<AbstractRMQTreeNode<V>>
        computeRightPartV(List<AbstractRMQTreeNode<V>> path) {
        Set<AbstractRMQTreeNode<V>> pathSet   = new HashSet<>(path);
        List<AbstractRMQTreeNode<V>> nodeList = new ArrayList<>();
        
        for (int i = 0; i < path.size() - 1; i++) {
            InternalRMQTreeNode<V> parent = 
                    (InternalRMQTreeNode<V>) path.get(i);
            
            AbstractRMQTreeNode<V> leftChild  = parent.getLeftChild();
            AbstractRMQTreeNode<V> rightChild = parent.getRightChild();
            
            if (pathSet.contains(rightChild)) {
                nodeList.add(leftChild);
            }
        }
        
        return nodeList;
    }
    
    /**
     * Gets the path from {@code splitNode} to the {@code leaf}. The returned
     * path will, however, exclude {@code splitNode} and {@code leaf}.
     *
     * @param splitNode the starting path node.
     * @param leafNode  the target node.
     * @return the path from {@code splitNode} to {@code leaf};
     */
    private List<AbstractRMQTreeNode<V>> 
        getPath(AbstractRMQTreeNode<V> splitNode, 
                AbstractRMQTreeNode<V> leafNode) {
        
        List<AbstractRMQTreeNode<V>> path = new ArrayList<>();
        
        AbstractRMQTreeNode<V> node = leafNode.getParent();
        
        while (node != null && !node.equals(splitNode)) {
            path.add(node);
            node = node.getParent();
        }
        
        Collections.reverse(path);
        return path;
    }
    
    /**
     * Computes the node at which the path from the root splits towards 
     * {@code leftLeaf} and {@code rightLeaf}.
     * 
     * @param leftLeaf  the left leaf.
     * @param rightLeaf the right leaf.
     * @return the split node.
     */
    private AbstractRMQTreeNode<V> 
        computeSplitNode(AbstractRMQTreeNode<V> leftLeaf,
                         AbstractRMQTreeNode<V> rightLeaf) {
            
        Set<AbstractRMQTreeNode<V>> leftPathSet = new HashSet<>();
        
        AbstractRMQTreeNode<V> node = leftLeaf;
        
        while (node != null) {
            leftPathSet.add(node);
            node = node.getParent();
        }
        
        node = rightLeaf;
        
        while (node != null) {
            if (leftPathSet.contains(node)) {
                return node;
            }
            
            node = node.getParent();
        }
        
        throw new IllegalStateException("Should not get here.");
    }
        
    /**
     * Implements the actual conversion from the tree to the string.
     * 
     * @param stringBuilder the string builder to which dump the string data.
     */
    private void toStringImpl(StringBuilder stringBuilder) {
        
        Deque<AbstractRMQTreeNode<V>> queue = 
                new ArrayDeque<>();
        
        queue.addLast(root);
        
        AbstractRMQTreeNode<V> levelEnd = root;
        
        while (!queue.isEmpty()) {
            AbstractRMQTreeNode<V> currentNode = queue.removeFirst();
            stringBuilder.append(String.format("%s ", currentNode));
            
            if (currentNode instanceof InternalRMQTreeNode) {
                
                AbstractRMQTreeNode<V> leftChild =
                        ((InternalRMQTreeNode<V>) currentNode)
                                .getLeftChild();
                
                AbstractRMQTreeNode<V> rightChild = 
                        ((InternalRMQTreeNode<V>) currentNode)
                                .getRightChild();
                
                queue.addLast(leftChild);
                queue.addLast(rightChild);
            } 
            
            if (currentNode.equals(levelEnd)) {
                if (!queue.isEmpty()) {
                    levelEnd = queue.getLast();
                }
                    
                stringBuilder.append("\n");
            }
        }
    }
}

com.github.coderodde.util.SemiDynamicRMQTreeBuilder.java:

package com.github.coderodde.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import static com.github.coderodde.util.Utils.min;

public final class SemiDynamicRMQTreeBuilder<K extends Comparable<? super K>,
                                             V extends Comparable<? super V>> {

    /**
     * Implements the actual tree building.'
     * 
     * @param <K> the key type.
     * @param <V> the value type.
     * @param keyValuePairSet the set of key/value pairs.
     * @return the tree data.
     */
    static <K extends Comparable<? super K>,
            V extends Comparable<? super V>>
                    
    RMQTreeBuilderResult<K, V> 
        buildRMQTree(Set<KeyValuePair<K, V>> keyValuePairSet) {
        
        Map<K, LeafRMQTreeNode<V>> leafMap = new HashMap<>();
        
        loadLeafMap(leafMap, keyValuePairSet);
        
        Objects.requireNonNull(
                keyValuePairSet,
                "The input KeyValuePair set is null.");
        
        if (keyValuePairSet.isEmpty()) {
            throw new IllegalArgumentException(
                    "No key/value pairs to process.");
        }
        
        List<KeyValuePair<K, V>> keyValuePairList = 
                new ArrayList<>(keyValuePairSet);
        
        Collections.sort(keyValuePairList);
        
        Map<K, LeafRMQTreeNode<V>> mapKeyToLeafNode = new HashMap<>();
        RMQTreeBuilderResult<K, V> result = new RMQTreeBuilderResult();
        AbstractRMQTreeNode<V> root = 
                buildRMQTreeImpl(keyValuePairList, 
                                 mapKeyToLeafNode);
        
        result.setLeafMap(mapKeyToLeafNode);
        result.setRoot(root);
        
        return result;
    }
 
    /**
     * Implements the actual, recursive building routine.
     * <p>
     * This algorithm seems much like in Task9, yet it differs: this one does 
     * not stored actual keys to the internal nodes, except to the leaf nodes,
     * unlike the algorithm in Task9.java.
     * 
     * @param <K>               the key type.
     * @param <V>               the value type.
     * @param keyValuePairs     the set of key/value pairs.
     * @param mapKeyToLeafNodes the map mapping keys to leaf nodes.
     * @return local root of the tree constructed.
     */
    private static <K extends Comparable<? super K>,
                    V extends Comparable<? super V>>
                    
    AbstractRMQTreeNode<V> 
        buildRMQTreeImpl(List<KeyValuePair<K, V>> keyValuePairs, 
                         Map<K, LeafRMQTreeNode<V>> mapKeyToLeafNodes) {
            
        if (keyValuePairs.size() == 1) {
            KeyValuePair<K, V> keyValuePair = keyValuePairs.get(0);
            LeafRMQTreeNode<V> leaf = new LeafRMQTreeNode<>();
            leaf.setValue(keyValuePair.getValue());
            mapKeyToLeafNodes.put(keyValuePair.getKey(), leaf);
            return leaf;
        }
        
        // middleIndex goes to the right:
        int middleIndex = keyValuePairs.size() / 2;

        AbstractRMQTreeNode<V> leftSubTreeRoot
                = buildRMQTreeImpl(
                        keyValuePairs.subList(0, middleIndex),
                        mapKeyToLeafNodes);

        AbstractRMQTreeNode<V> rightSubTreeRoot
                = buildRMQTreeImpl(
                        keyValuePairs.subList(
                                middleIndex,
                                keyValuePairs.size()),
                        mapKeyToLeafNodes);

        InternalRMQTreeNode<V> localRoot = new InternalRMQTreeNode<>();
        
        // Link the children and their parent:
        localRoot.setLeftChild(leftSubTreeRoot);
        localRoot.setRightChild(rightSubTreeRoot);
        
        leftSubTreeRoot.setParent(localRoot);
        rightSubTreeRoot.setParent(localRoot);
        
        localRoot.setValue(min(leftSubTreeRoot.getValue(), // Important step!
                               rightSubTreeRoot.getValue()));

        return localRoot;
    }
        
    /**
     * Loads the map mapping keys to leaf nodes.
     * '
     * @param <K>             the key type.
     * @param <V>             the value type.
     * @param leafMap         the map to populate.
     * @param keyValuePairSet the key/value pair set.
     */
    private static <K extends Comparable<? super K>,
                    V extends Comparable<? super V>>
                
    void loadLeafMap(Map<K, LeafRMQTreeNode<V>> leafMap, 
                         Set<KeyValuePair<K, V>> keyValuePairSet) {
        
        for (KeyValuePair<K, V> keyValuePair : keyValuePairSet) {
            LeafRMQTreeNode<V> leaf = new LeafRMQTreeNode<>();
            leaf.setValue(keyValuePair.getValue());
            leafMap.put(keyValuePair.getKey(), leaf);
        }
    }
    
    static final 
            class RMQTreeBuilderResult<K extends Comparable<? super K>,
                                       V extends Comparable<? super V>> {
        
        private Map<K, LeafRMQTreeNode<V>> leafMap;
        private AbstractRMQTreeNode<V> root;

        public void setLeafMap(Map<K, LeafRMQTreeNode<V>> leafMap) {
            this.leafMap = leafMap;
        }

        public void setRoot(AbstractRMQTreeNode<V> root) {
            this.root = root;
        }
        
        Map<K, LeafRMQTreeNode<V>> getLeafMap() {
            return leafMap;
        }
        
        AbstractRMQTreeNode<V> getRoot() {
            return root;
        }
    }
}

com.github.coderodde.util.SemiDynamicRMQTreeDemo.java:

package com.github.coderodde.util;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public final class SemiDynamicRMQTreeDemo {
    
    private static final int INITIAL_TREE_SIZE = 4;
             
    private static SemiDynamicRMQTree<Integer, Long> tree = 
            constructREPLTree(INITIAL_TREE_SIZE);
    
    public static void main(String[] args) {
        replInterface();
    }
             
    private static SemiDynamicRMQTree<Integer, Long> 
        constructREPLTree(int size) {
            
        long start = System.nanoTime();
        Set<KeyValuePair<Integer, Long>> keyValuePairSet = new HashSet<>(size);
        
        for (int i = 0; i < size; i++) {
            Integer key = i + 1;
            Long value = Long.valueOf(i + 1);
            KeyValuePair<Integer, Long> keyValuePair = new KeyValuePair<>(key, value);
            keyValuePairSet.add(keyValuePair);
        }
        
        long end = System.nanoTime();
        long total = end - start;
        
        System.out.printf(
                "Built the key/value pairs in %,d nanoseconds.\n",
                total);
        
        start = System.nanoTime();
        
        SemiDynamicRMQTree<Integer, Long> tree =
                new SemiDynamicRMQTree<>(keyValuePairSet);

        end = System.nanoTime();
        
        System.out.printf("Built the RMQ tree in %,d nanoseconds.\n", 
                          end - start);
        
        total += end - start;
        
        System.out.printf(
                "Total time building the RMQ tree: %,d nanoseconds.\n",
                total);
        
        return tree;
    }
             
    private static void replInterface() {
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            System.out.print("> ");
            
            String commandLine = scanner.nextLine().trim();
            
            try {
                String[] commandLineParts = commandLine.split(" ");
                String command = commandLineParts[0].trim();

                switch (command) {
                    case "update":
                        runUpdate(commandLineParts[1],
                                  commandLineParts[2]);
                        break;

                    case "rmq":
                        Long value = runRMQ(commandLineParts[1],
                                            commandLineParts[2]);

                        System.out.println(value);
                        break;

                    case "print":
                        System.out.println(tree);
                        break;

                    case "new":
                        int size = Integer.parseInt(commandLineParts[1]);
                        tree = constructREPLTree(size);
                        break;

                    case "help":
                        printHelp();
                        break;

                    case "quit":
                    case "exit":
                        System.out.println("Bye!");
                        return;
                }
            } catch (Exception ex) {
                System.out.printf(
                        "ERROR: Could not parse command \"%s\".\n",
                        commandLine);
            }
        }
    }
    
    private static void printHelp() {
        final String help = "update KEY VALUE\n" + 
                            "rmq KEY1 KEY2\n" + 
                            "print\n" +
                            "new TREE_SIZE\n" +
                            "help";
        
        System.out.println(help);
    }
    
    private static void runUpdate(String keyString, String newValueString) {
        Integer key = Integer.valueOf(keyString);
        Long value = Long.valueOf(newValueString);
        
        long start = System.nanoTime();
        tree.update(key, value);
        long end = System.nanoTime();
        
        System.out.printf("update in %,d nanoseconds.\n", end - start);
    }
    
    private static Long runRMQ(String leftKeyString, String rightKeyString) {
        Integer leftKey = Integer.valueOf(leftKeyString);
        Integer rightKey = Integer.valueOf(rightKeyString);
        
        long start = System.nanoTime();
        Long returnValue = tree.getRangeMinimum(leftKey, rightKey);
        long end = System.nanoTime();
        
        System.out.printf("rmq in %,d nanoseconds.\n", end - start);
        
        return returnValue;
    }
}

com.github.coderodde.util.Utils.java:

package com.github.coderodde.util;

public final class Utils {
    
    /**
     * Returns the smaller of the two given values.
     * 
     * @param <E>    the value of type. Must be {@link java.lang.Comparable}.
     * @param value1 the first value.
     * @param value2 the second value.
     * @return the smaller of the two input values.
     */
    public static <E extends Comparable<? super E>> E min(E value1, E value2) {
        return value1.compareTo(value2) < 0 ? value1 : value2;
    }
}

com.github.coderodde.util.SemiDynamicRMQTreeTest.java:

package com.github.coderodde.util;

import java.util.HashSet;
import java.util.Set;
import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class SemiDynamicRMQTreeTest {
    
    @Test
    public void passesOnTreeWith4Nodes() {
        Set<KeyValuePair<Integer, Long>> keyValuePairSet = new HashSet<>(4);
        
        keyValuePairSet.add(new KeyValuePair<>(2, 2L));
        keyValuePairSet.add(new KeyValuePair<>(4, 4L));
        keyValuePairSet.add(new KeyValuePair<>(1, 1L));
        keyValuePairSet.add(new KeyValuePair<>(3, 3L));
        
        SemiDynamicRMQTree<Integer, Long> tree = 
                new SemiDynamicRMQTree<>(keyValuePairSet);
        
        InternalRMQTreeNode<Long> root = 
                (InternalRMQTreeNode<Long>) tree.getRoot();
        
        InternalRMQTreeNode<Long> leftMiddleNode  = 
                (InternalRMQTreeNode<Long>) root.getLeftChild();
        
        InternalRMQTreeNode<Long> rightMiddleNode = 
                (InternalRMQTreeNode<Long>) root.getRightChild();
        
        LeafRMQTreeNode<Long> leaf1 = (LeafRMQTreeNode<Long>) leftMiddleNode.getLeftChild();
        LeafRMQTreeNode<Long> leaf2 = (LeafRMQTreeNode<Long>) leftMiddleNode.getRightChild();
        LeafRMQTreeNode<Long> leaf3 = (LeafRMQTreeNode<Long>) rightMiddleNode.getLeftChild();
        LeafRMQTreeNode<Long> leaf4 = (LeafRMQTreeNode<Long>) rightMiddleNode.getRightChild();
        
        assertEquals(Long.valueOf(1L), root.getValue());
        
        assertEquals(Long.valueOf(1L), leftMiddleNode.getValue());
        
        assertEquals(Long.valueOf(3L), rightMiddleNode.getValue());
        
        assertEquals(Long.valueOf(1L), leaf1.getValue());
        assertEquals(Long.valueOf(2L), leaf2.getValue());
        assertEquals(Long.valueOf(3L), leaf3.getValue());
        assertEquals(Long.valueOf(4L), leaf4.getValue());
        
        assertEquals(Long.valueOf(1L), 
                     tree.getRangeMinimum(Integer.valueOf(1),
                                          Integer.valueOf(2)));
        
        assertEquals(Long.valueOf(3L),
                     tree.getRangeMinimum(Integer.valueOf(3), 
                                          Integer.valueOf(4)));
        
        assertEquals(Long.valueOf(2L),
                     tree.getRangeMinimum(Integer.valueOf(2), 
                                          Integer.valueOf(4)));
        
        assertEquals(Long.valueOf(1L),
                     tree.getRangeMinimum(Integer.valueOf(1), 
                                          Integer.valueOf(4)));
        tree.update(4, -1L);
        
        assertEquals(Long.valueOf(-1L), leaf4.getValue());
        assertEquals(Long.valueOf(-1L), rightMiddleNode.getValue());
        assertEquals(Long.valueOf(-1L), root.getValue());
    }
    
    @Test
    public void passesOnTreeWith3Nodes() {
        Set<KeyValuePair<Integer, Long>> keyValuePairSet = new HashSet<>(4);
        
        keyValuePairSet.add(new KeyValuePair<>(2, 2L));
        keyValuePairSet.add(new KeyValuePair<>(1, 1L));
        keyValuePairSet.add(new KeyValuePair<>(3, 3L));
        
        SemiDynamicRMQTree<Integer, Long> tree = 
                new SemiDynamicRMQTree<>(keyValuePairSet);
        
        InternalRMQTreeNode<Long> root =
                (InternalRMQTreeNode<Long>) tree.getRoot();
        
        assertEquals(Long.valueOf(1L), root.getValue());
        
        InternalRMQTreeNode<Long> middleInternalNode = 
                (InternalRMQTreeNode<Long>) root.getRightChild();
        
        assertEquals(Long.valueOf(2L), middleInternalNode.getValue());
        
        LeafRMQTreeNode<Long> leaf1 = (LeafRMQTreeNode<Long>) root.getLeftChild();
        LeafRMQTreeNode<Long> leaf2 = (LeafRMQTreeNode<Long>) middleInternalNode.getLeftChild();
        LeafRMQTreeNode<Long> leaf3 = (LeafRMQTreeNode<Long>) middleInternalNode.getRightChild();
        
        assertEquals(Long.valueOf(1L), leaf1.getValue());
        assertEquals(Long.valueOf(2L), leaf2.getValue());
        assertEquals(Long.valueOf(3L), leaf3.getValue());
    }
}

Typical output

Built the key/value pairs in 1 628 500 nanoseconds.
Built the RMQ tree in 8 127 200 nanoseconds.
Total time building the RMQ tree: 9 755 700 nanoseconds.
> new 10000000
Built the key/value pairs in 5 512 051 500 nanoseconds.
Built the RMQ tree in 25 338 403 700 nanoseconds.
Total time building the RMQ tree: 30 850 455 200 nanoseconds.
> rmq 1 10000000
rmq in 1 012 800 nanoseconds.
1
> update 26 -1
update in 55 300 nanoseconds.
> rmq 1 10000000
rmq in 278 200 nanoseconds.
-1
> 

Critique request

Please tell me anything that comes to mind.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Context

RMQ is not as a well known problem as say sorting, so I personally had to search the web first to even know what this is exactly about. I had a quick look at the Wikipedia article, where one of the solutions is to use a Cartesian tree, but I wasn't even sure if your tree is a Cartesian tree or something else because there's zero explanation.
I also have had a quick look at Google results for "range minimum query tree" and the first result was something called Segment Tree and again I didn't know it it was the type of tree you implemented or something else.
At this point I gave up on trying to understand what exactly your tree is and I have a feeling, that this lack of context is one of the reasons this question got so little attention.
Thus the rest of the review will focus solely on code organization and skip the question whether the algorithm/data structure you implemented could be somehow optimized/improved.

Overblown class hierarchy

You have THREE classes for your tree nodes (abstract base, internal, leaf), the only method that is ever overridden is toString() (having almost exactly the same behaviour, differing only with constant used) and internal nodes do not enforce non-null on at least 1 of their children. In the rest of the code, there's only 1 place that differentiates between a leaf and an internal node by doing instanceof: this is often a very strong indicator, that something is wrong with your class hierarchy.
Furthermore, if you joined these 3 classes into 1, it would save you lots of casting that you currently need all around the code...
It is possible, that these classes were extracted from some bigger code base where there were some additional methods, that would justify having 3 separate classes, but for the purpose of this review it would be much better to have just 1 RMQTreeNode class with additional boolean isLeaf field. This would make the code much quicker to comprehend. I'm guessing that this is the 2nd reason why this question got so little attention: honestly when I first saw it I was like "oh boy, so many classes: this is BIIIG, it will require a LOT of undivided time to review!" and gave up until now...

Now on top of the above there's KeyValuePair, that can be replaced by AbstractMap.SimpleEntry and Utils with a single 1-line static helper method that could be moved for example to SemiDynamicRMQTree...

As pointed before, even if in some broader context there's a reason for having these 3 *RMQTreeNode classes, I think it would be cleaner to have isLeaf() method in the abstract base and use it instead of instanceof.

Code style

Everyone is usually quite opinionated regarding code style guidelines and I'm usually fine with that, but I strongly believe that 99% of Java devs in the world would agree that blank lines in the middle of method headers are misleading. I literally spent like 30 seconds staring before I finally realized what I was looking at ;-)

Unnecessary boilerplate

Java has a bad reputation for requiring a lot of boilerplate. This is to some degree caused by developers perpetuating overly strict (IMO) coding style guidelines, like that every class, even dumb DTOs like RMQTreeBuilderResult must have all fields private accompanied by accessor methods. However from the point of view of access control, making a field private final and providing a getter brings absolutely zero value comparing to making it public final and no getter is necessary then.
Furthermore, I've noticed on github that language level is set to 20, in which case the whole RMQTreeBuilderResult can be converted into a 2 line record.

Similarly with fields in *RMQTreeNode classes: they are all private and then both getters and setters are provided: this is totally unnecessary IMO: if you provide both a getter and a setter it's equivalent to just making the field public and no boilerplate methods are necessary then.

Unused code

SemiDynamicRMQTreeBuilder has only static methods: it does not need type params

toString() methods of *RMQTreeNode classes have unnecessary calls to Objects.toString(...)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.