(K key)
| 4082 | } |
| 4083 | |
| 4084 | TreeMap.Entry<K, V> findLowerEntry(K key) { |
| 4085 | if (root == null) { |
| 4086 | return null; |
| 4087 | } |
| 4088 | java.lang.Comparable<K> object = comparator == null ? toComparable((K) key) |
| 4089 | : null; |
| 4090 | K keyK = (K) key; |
| 4091 | Node<K, V> node = root; |
| 4092 | Node<K, V> foundNode = null; |
| 4093 | int foundIndex = 0; |
| 4094 | while (node != null) { |
| 4095 | K[] keys = node.keys; |
| 4096 | int left_idx = node.left_idx; |
| 4097 | int result = cmp(object, keyK, keys[left_idx]); |
| 4098 | if (result <= 0) { |
| 4099 | node = node.left; |
| 4100 | } else { |
| 4101 | foundNode = node; |
| 4102 | foundIndex = left_idx; |
| 4103 | int right_idx = node.right_idx; |
| 4104 | if (left_idx != right_idx) { |
| 4105 | result = cmp(object, key, keys[right_idx]); |
| 4106 | } |
| 4107 | if (result > 0) { |
| 4108 | foundNode = node; |
| 4109 | foundIndex = right_idx; |
| 4110 | node = node.right; |
| 4111 | } else { /* search in node */ |
| 4112 | int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| 4113 | while (low <= high) { |
| 4114 | mid = (low + high) >> 1; |
| 4115 | result = cmp(object, key, keys[mid]); |
| 4116 | if (result > 0) { |
| 4117 | foundNode = node; |
| 4118 | foundIndex = mid; |
| 4119 | low = mid + 1; |
| 4120 | } else { |
| 4121 | high = mid; |
| 4122 | } |
| 4123 | if (low == high && high == mid){ |
| 4124 | break; |
| 4125 | } |
| 4126 | } |
| 4127 | break; |
| 4128 | } |
| 4129 | } |
| 4130 | } |
| 4131 | if (foundNode != null |
| 4132 | && cmp(object,keyK, foundNode.keys[foundIndex]) <= 0) { |
| 4133 | foundNode = null; |
| 4134 | } |
| 4135 | if (foundNode != null){ |
| 4136 | return createEntry(foundNode, foundIndex); |
| 4137 | } |
| 4138 | return null; |
| 4139 | } |
| 4140 | |
| 4141 | TreeMap.Entry<K, V> findHigherEntry(K key) { |
no test coverage detected