(K key)
| 4019 | } |
| 4020 | |
| 4021 | TreeMap.Entry<K, V> findFloorEntry(K key) { |
| 4022 | if (root == null) { |
| 4023 | return null; |
| 4024 | } |
| 4025 | java.lang.Comparable<K> object = comparator == null ? toComparable((K) key) |
| 4026 | : null; |
| 4027 | K keyK = (K) key; |
| 4028 | Node<K, V> node = root; |
| 4029 | Node<K, V> foundNode = null; |
| 4030 | int foundIndex = 0; |
| 4031 | while (node != null) { |
| 4032 | K[] keys = node.keys; |
| 4033 | int left_idx = node.left_idx; |
| 4034 | int result = cmp(object, keyK, keys[left_idx]); |
| 4035 | if (result < 0) { |
| 4036 | node = node.left; |
| 4037 | } else { |
| 4038 | foundNode = node; |
| 4039 | foundIndex = left_idx; |
| 4040 | if (result == 0){ |
| 4041 | break; |
| 4042 | } |
| 4043 | int right_idx = node.right_idx; |
| 4044 | if (left_idx != right_idx) { |
| 4045 | result = cmp(object, key, keys[right_idx]); |
| 4046 | } |
| 4047 | if (result >= 0) { |
| 4048 | foundNode = node; |
| 4049 | foundIndex = right_idx; |
| 4050 | if (result == 0){ |
| 4051 | break; |
| 4052 | } |
| 4053 | node = node.right; |
| 4054 | } else { /* search in node */ |
| 4055 | int low = left_idx + 1, mid = 0, high = right_idx - 1; |
| 4056 | while (low <= high && result != 0) { |
| 4057 | mid = (low + high) >> 1; |
| 4058 | result = cmp(object, key, keys[mid]); |
| 4059 | if (result >= 0) { |
| 4060 | foundNode = node; |
| 4061 | foundIndex = mid; |
| 4062 | low = mid + 1; |
| 4063 | } else { |
| 4064 | high = mid; |
| 4065 | } |
| 4066 | if (result == 0 || (low == high && high == mid)){ |
| 4067 | break; |
| 4068 | } |
| 4069 | } |
| 4070 | break; |
| 4071 | } |
| 4072 | } |
| 4073 | } |
| 4074 | if (foundNode != null |
| 4075 | && cmp(object,keyK, foundNode.keys[foundIndex]) < 0) { |
| 4076 | foundNode = null; |
| 4077 | } |
| 4078 | if (foundNode != null){ |
no test coverage detected