| 4942 | } |
| 4943 | |
| 4944 | K removeRightmost(Node<K, V> node) { |
| 4945 | int index = node.right_idx; |
| 4946 | // store the next key, return if the node is deleted |
| 4947 | K key = (node != null && node.next != null) ? node.next.keys[node.next.left_idx] : null; |
| 4948 | if (node.size == 1) { |
| 4949 | deleteNode(node); |
| 4950 | } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| 4951 | // move all to prev node and kill it |
| 4952 | Node<K, V> prev = node.prev; |
| 4953 | int left_idx = node.left_idx; |
| 4954 | int size = index - left_idx; |
| 4955 | System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); |
| 4956 | System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); |
| 4957 | prev.right_idx += size; |
| 4958 | prev.size += size; |
| 4959 | deleteNode(node); |
| 4960 | } else if (node.next != null && (node.next.left_idx) > node.size) { |
| 4961 | // move all to next node and kill it |
| 4962 | Node<K, V> next = node.next; |
| 4963 | int left_idx = node.left_idx; |
| 4964 | int size = index - left_idx; |
| 4965 | int next_new_left = next.left_idx - size; |
| 4966 | next.left_idx = next_new_left; |
| 4967 | System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); |
| 4968 | System.arraycopy(node.values, left_idx, next.values, next_new_left, size); |
| 4969 | next.size += size; |
| 4970 | deleteNode(node); |
| 4971 | } else { |
| 4972 | node.keys[index] = null; |
| 4973 | node.values[index] = null; |
| 4974 | node.right_idx--; |
| 4975 | node.size--; |
| 4976 | Node<K, V> next = node.next; |
| 4977 | key = null; |
| 4978 | if (next != null && next.size == 1) { |
| 4979 | node.size++; |
| 4980 | node.right_idx++; |
| 4981 | node.keys[node.right_idx] = next.keys[next.left_idx]; |
| 4982 | node.values[node.right_idx] = next.values[next.left_idx]; |
| 4983 | deleteNode(next); |
| 4984 | } |
| 4985 | } |
| 4986 | modCount++; |
| 4987 | size--; |
| 4988 | return key; |
| 4989 | } |
| 4990 | |
| 4991 | K removeMiddleElement(Node<K, V> node, int index) { |
| 4992 | // this function is called iff index if some middle element; |