private Entry buildFromSorted()

in orderbook-core/src/main/java/com/epam/deltix/orderbook/core/impl/collections/rbt/RBTree.java [817:872]

• 33 lines of code
• 6 McCabe index (conditional complexity)

    private Entry<K, V> buildFromSorted(final int level,
                                        final int lo,
                                        final int hi,
                                        final int redLevel,
                                        final ArrayList<V> values) {
        /*
         * Strategy: The root is the middlemost element. To get to it, we
         * have to first recursively construct the entire left subtree,
         * so as to grab all of its elements. We can then proceed with right
         * subtree.
         *
         * The lo and hi arguments are the minimum and maximum
         * indices to pull out of the iterator or stream for current subtree.
         * They are not actually indexed, we just proceed sequentially,
         * ensuring that items are extracted in corresponding order.
         */

        if (hi < lo) {
            return null;
        }

        final int mid = (lo + hi) >>> 1;

        Entry<K, V> left = null;
        if (lo < mid) {
            left = buildFromSorted(level + 1, lo, mid - 1, redLevel,
                    values);
        }

        final K key = (K) values.get(currentIndex);
        final V value = values.get(currentIndex);


        final Entry<K, V> middle = pool.borrow();
        middle.set(key, value, null);

        // color nodes in non-full bottommost level red
        if (level == redLevel) {
            middle.color = RED;
        }

        if (left != null) {
            middle.left = left;
            left.parent = middle;
        }

        currentIndex++;

        if (mid < hi) {
            final Entry<K, V> right = buildFromSorted(level + 1, mid + 1, hi, redLevel, values);
            middle.right = right;
            right.parent = middle;
        }

        return middle;
    }