| 4911 | } |
| 4912 | |
| 4913 | K removeRightmost(Node<K, V> node) { |
| 4914 | int index = node.right_idx; |
| 4915 | // store the next key, return if the node is deleted |
| 4916 | K key = (node != null && node.next != null) ? node.next.keys[node.next.left_idx] : null; |
| 4917 | if (node.size == 1) { |
| 4918 | deleteNode(node); |
| 4919 | } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| 4920 | // move all to prev node and kill it |
| 4921 | Node<K, V> prev = node.prev; |
| 4922 | int left_idx = node.left_idx; |
| 4923 | int size = index - left_idx; |
| 4924 | System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); |
| 4925 | System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); |
| 4926 | prev.right_idx += size; |
| 4927 | prev.size += size; |
| 4928 | deleteNode(node); |
| 4929 | } else if (node.next != null && (node.next.left_idx) > node.size) { |
| 4930 | // move all to next node and kill it |
| 4931 | Node<K, V> next = node.next; |
| 4932 | int left_idx = node.left_idx; |
| 4933 | int size = index - left_idx; |
| 4934 | int next_new_left = next.left_idx - size; |
| 4935 | next.left_idx = next_new_left; |
| 4936 | System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); |
| 4937 | System.arraycopy(node.values, left_idx, next.values, next_new_left, size); |
| 4938 | next.size += size; |
| 4939 | deleteNode(node); |
| 4940 | } else { |
| 4941 | node.keys[index] = null; |
| 4942 | node.values[index] = null; |
| 4943 | node.right_idx--; |
| 4944 | node.size--; |
| 4945 | Node<K, V> next = node.next; |
| 4946 | key = null; |
| 4947 | if (next != null && next.size == 1) { |
| 4948 | node.size++; |
| 4949 | node.right_idx++; |
| 4950 | node.keys[node.right_idx] = next.keys[next.left_idx]; |
| 4951 | node.values[node.right_idx] = next.values[next.left_idx]; |
| 4952 | deleteNode(next); |
| 4953 | } |
| 4954 | } |
| 4955 | modCount++; |
| 4956 | size--; |
| 4957 | return key; |
| 4958 | } |
| 4959 | |
| 4960 | K removeMiddleElement(Node<K, V> node, int index) { |
| 4961 | // this function is called iff index if some middle element; |