Method findHigherEntry

Ports/CLDC11/src/java/util/TreeMap.java:4148–4205

(K key)

    }

    TreeMap.Entry<K, V> findHigherEntry(K key) {
        if (root == null) {
            return null;
        }
        java.lang.Comparable<K> object = comparator == null ? toComparable((K) key)
                : null;
        K keyK = (K) key;
        Node<K, V> node = root;
        Node<K, V> foundNode = null;
        int foundIndex = 0;
        while (node != null) {
            K[] keys = node.keys;
            int right_idx = node.right_idx;
            int result = cmp(object, keyK, keys[right_idx]);
            if (result >= 0) {
                node = node.right;
            } else {
                foundNode = node;
                foundIndex = right_idx;
                int left_idx = node.left_idx;
                if (left_idx != right_idx) {
                    result = cmp(object, key, keys[left_idx]);
                }
                if (result < 0) {
                    foundNode = node;
                    foundIndex = left_idx;
                    node = node.left;
                } else { /* search in node */
                    foundNode = node;
                    foundIndex = right_idx;
                    int low = left_idx + 1, mid = 0, high = right_idx - 1;
                    while (low <= high) {
                        mid = (low + high) >> 1;
                        result = cmp(object, key, keys[mid]);
                        if (result < 0) {
                            foundNode = node;
                            foundIndex = mid;
                            high = mid - 1;     
                        }else {
                            low = mid + 1;            
                        }
                        if (low == high && high == mid){
                            break;
                        }
                    }
                    break;
                }
            }
        }
        if (foundNode != null
                && cmp(object,keyK, foundNode.keys[foundIndex]) >= 0) {
            foundNode = null;
        }
        if (foundNode != null){
            return createEntry(foundNode, foundIndex);
        }
        return null;
    }