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;
}