| 4866 | } |
| 4867 | |
| 4868 | K removeLeftmost(Node<K, V> node) { |
| 4869 | int index = node.left_idx; |
| 4870 | // record next key and record if the node is removed |
| 4871 | K key = (index + 1 <= node.right_idx) ? node.keys[index + 1] : null; |
| 4872 | if (node.size == 1) { |
| 4873 | deleteNode(node); |
| 4874 | } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| 4875 | // move all to prev node and kill it |
| 4876 | Node<K, V> prev = node.prev; |
| 4877 | int size = node.right_idx - index; |
| 4878 | System.arraycopy(node.keys, index + 1, prev.keys, prev.right_idx + 1, size); |
| 4879 | System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size); |
| 4880 | prev.right_idx += size; |
| 4881 | prev.size += size; |
| 4882 | deleteNode(node); |
| 4883 | } else if (node.next != null && (node.next.left_idx) > node.size) { |
| 4884 | // move all to next node and kill it |
| 4885 | Node<K, V> next = node.next; |
| 4886 | int size = node.right_idx - index; |
| 4887 | int next_new_left = next.left_idx - size; |
| 4888 | next.left_idx = next_new_left; |
| 4889 | System.arraycopy(node.keys, index + 1, next.keys, next_new_left, size); |
| 4890 | System.arraycopy(node.values, index + 1, next.values, next_new_left, size); |
| 4891 | next.size += size; |
| 4892 | deleteNode(node); |
| 4893 | } else { |
| 4894 | node.keys[index] = null; |
| 4895 | node.values[index] = null; |
| 4896 | node.left_idx++; |
| 4897 | node.size--; |
| 4898 | Node<K, V> prev = node.prev; |
| 4899 | key = null; |
| 4900 | if (prev != null && prev.size == 1) { |
| 4901 | node.size++; |
| 4902 | node.left_idx--; |
| 4903 | node.keys [node.left_idx] = prev.keys [prev.left_idx]; |
| 4904 | node.values[node.left_idx] = prev.values[prev.left_idx]; |
| 4905 | deleteNode(prev); |
| 4906 | } |
| 4907 | } |
| 4908 | modCount++; |
| 4909 | size--; |
| 4910 | return key; |
| 4911 | } |
| 4912 | |
| 4913 | K removeRightmost(Node<K, V> node) { |
| 4914 | int index = node.right_idx; |