boolean seekTo()

in accord-core/src/main/java/accord/utils/btree/TreeCursor.java [98:171]


    boolean seekTo(K key, boolean forwards, boolean skipOne)
    {
        NodeCursor<K> cur = this.cur;

        /**
         * decide if we will "try one" value by itself, as a sequential access;
         * we actually *require* that we try the "current key" for any node before we call seekInNode on it.
         *
         * if we are already on a value, we just check it irregardless of if it is a leaf or not;
         * if we are not, we have already excluded it (as we have consumed it), so:
         *    if we are on a branch we consider that good enough;
         *    otherwise, we move onwards one, and we try the new value
         *
         */
        boolean tryOne = !skipOne;
        if ((!tryOne & cur.isLeaf()) && !(tryOne = (cur.advanceLeafNode(forwards) || (cur = moveOutOfLeaf(forwards, cur, null)) != null)))
        {
            // we moved out of the tree; return out-of-bounds
            this.cur = root();
            return false;
        }

        if (tryOne)
        {
            // we're presently on a value we can (and *must*) cheaply test
            K test = cur.value();

            int cmp;
            if (key == test) cmp = 0; // check object identity first, since we utilise that in some places and it's very cheap
            else cmp = comparator.compare(test, key); // order of provision matters for asymmetric comparators
            if (forwards ? cmp >= 0 : cmp <= 0)
            {
                // we've either matched, or excluded the value from being present
                this.cur = cur;
                return cmp == 0;
            }
        }

        // if we failed to match with the cheap test, first look to see if we're even in the correct sub-tree
        while (cur != root())
        {
            NodeCursor<K> bound = cur.boundIterator(forwards);
            if (bound == null)
                break; // we're all that's left

            int cmpbound = comparator.compare(bound.bound(forwards), key); // order of provision matters for asymmetric comparators
            if (forwards ? cmpbound > 0 : cmpbound < 0)
                break; //  already in correct sub-tree

            // bound is on-or-before target, so ascend to that bound and continue looking upwards
            cur = bound;
            cur.safeAdvanceIntoBranchFromChild(forwards);
            if (cmpbound == 0) // it was an exact match, so terminate here
            {
                this.cur = cur;
                return true;
            }
        }

        // we must now be able to find our target in the sub-tree rooted at cur
        boolean match;
        while (!(match = cur.seekInNode(key, forwards)) && !cur.isLeaf())
        {
            cur = cur.descend();
            cur.position = forwards ? -1 : getKeyEnd(cur.node);
        }

        if (!match)
            cur = ensureValidLocation(forwards, cur);

        this.cur = cur;
        assert !cur.inChild;
        return match;
    }