| 4958 | } |
| 4959 | |
| 4960 | K removeMiddleElement(Node<K, V> node, int index) { |
| 4961 | // this function is called iff index if some middle element; |
| 4962 | // so node.left_idx < index < node.right_idx |
| 4963 | // condition above assume that node.size > 1 |
| 4964 | K ret = null; |
| 4965 | if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| 4966 | // move all to prev node and kill it |
| 4967 | Node<K, V> prev = node.prev; |
| 4968 | int left_idx = node.left_idx; |
| 4969 | int size = index - left_idx; |
| 4970 | System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); |
| 4971 | System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); |
| 4972 | prev.right_idx += size; |
| 4973 | size = node.right_idx - index; |
| 4974 | System.arraycopy(node.keys, index + 1, prev.keys, prev.right_idx + 1, size); |
| 4975 | System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size); |
| 4976 | ret = prev.keys[prev.right_idx + 1]; |
| 4977 | prev.right_idx += size; |
| 4978 | prev.size += (node.size - 1); |
| 4979 | deleteNode(node); |
| 4980 | } else if (node.next != null && (node.next.left_idx) > node.size) { |
| 4981 | // move all to next node and kill it |
| 4982 | Node<K, V> next = node.next; |
| 4983 | int left_idx = node.left_idx; |
| 4984 | int next_new_left = next.left_idx - node.size + 1; |
| 4985 | next.left_idx = next_new_left; |
| 4986 | int size = index - left_idx; |
| 4987 | System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); |
| 4988 | System.arraycopy(node.values, left_idx, next.values, next_new_left, size); |
| 4989 | next_new_left += size; |
| 4990 | size = node.right_idx - index; |
| 4991 | System.arraycopy(node.keys, index + 1, next.keys, next_new_left, size); |
| 4992 | System.arraycopy(node.values, index + 1, next.values, next_new_left, size); |
| 4993 | ret = next.keys[next_new_left]; |
| 4994 | next.size += (node.size - 1); |
| 4995 | deleteNode(node); |
| 4996 | } else { |
| 4997 | int moveFromRight = node.right_idx - index; |
| 4998 | int left_idx = node.left_idx; |
| 4999 | int moveFromLeft = index - left_idx ; |
| 5000 | if (moveFromRight <= moveFromLeft) { |
| 5001 | System.arraycopy(node.keys, index + 1, node.keys, index, moveFromRight); |
| 5002 | System.arraycopy(node.values, index + 1, node.values, index, moveFromRight); |
| 5003 | Node<K, V> next = node.next; |
| 5004 | if (next != null && next.size == 1) { |
| 5005 | node.keys [node.right_idx] = next.keys [next.left_idx]; |
| 5006 | node.values[node.right_idx] = next.values[next.left_idx]; |
| 5007 | ret = node.keys[index]; |
| 5008 | deleteNode(next); |
| 5009 | } else { |
| 5010 | node.keys [node.right_idx] = null; |
| 5011 | node.values[node.right_idx] = null; |
| 5012 | node.right_idx--; |
| 5013 | node.size--; |
| 5014 | } |
| 5015 | } else { |
| 5016 | System.arraycopy(node.keys, left_idx , node.keys, left_idx + 1, moveFromLeft); |
| 5017 | System.arraycopy(node.values, left_idx , node.values, left_idx + 1, moveFromLeft); |