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