(Node<K, V> node, int index)
| 1977 | } |
| 1978 | |
| 1979 | void removeMiddleElement(Node<K, V> node, int index) { |
| 1980 | // this function is called iff index if some middle element; |
| 1981 | // so node.left_idx < index < node.right_idx |
| 1982 | // condition above assume that node.size > 1 |
| 1983 | if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) { |
| 1984 | // move all to prev node and kill it |
| 1985 | Node<K, V> prev = node.prev; |
| 1986 | int left_idx = node.left_idx; |
| 1987 | int size = index - left_idx; |
| 1988 | System.arraycopy(node.keys, left_idx, prev.keys, prev.right_idx + 1, size); |
| 1989 | System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size); |
| 1990 | prev.right_idx += size; |
| 1991 | size = node.right_idx - index; |
| 1992 | System.arraycopy(node.keys, index + 1, prev.keys, prev.right_idx + 1, size); |
| 1993 | System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size); |
| 1994 | prev.right_idx += size; |
| 1995 | prev.size += (node.size - 1); |
| 1996 | deleteNode(node); |
| 1997 | } else if (node.next != null && (node.next.left_idx) > node.size) { |
| 1998 | // move all to next node and kill it |
| 1999 | Node<K, V> next = node.next; |
| 2000 | int left_idx = node.left_idx; |
| 2001 | int next_new_left = next.left_idx - node.size + 1; |
| 2002 | next.left_idx = next_new_left; |
| 2003 | int size = index - left_idx; |
| 2004 | System.arraycopy(node.keys, left_idx, next.keys, next_new_left, size); |
| 2005 | System.arraycopy(node.values, left_idx, next.values, next_new_left, size); |
| 2006 | next_new_left += size; |
| 2007 | size = node.right_idx - index; |
| 2008 | System.arraycopy(node.keys, index + 1, next.keys, next_new_left, size); |
| 2009 | System.arraycopy(node.values, index + 1, next.values, next_new_left, size); |
| 2010 | next.size += (node.size - 1); |
| 2011 | deleteNode(node); |
| 2012 | } else { |
| 2013 | int moveFromRight = node.right_idx - index; |
| 2014 | int left_idx = node.left_idx; |
| 2015 | int moveFromLeft = index - left_idx ; |
| 2016 | if (moveFromRight <= moveFromLeft) { |
| 2017 | System.arraycopy(node.keys, index + 1, node.keys, index, moveFromRight); |
| 2018 | System.arraycopy(node.values, index + 1, node.values, index, moveFromRight); |
| 2019 | Node<K, V> next = node.next; |
| 2020 | if (next != null && next.size == 1) { |
| 2021 | node.keys [node.right_idx] = next.keys [next.left_idx]; |
| 2022 | node.values[node.right_idx] = next.values[next.left_idx]; |
| 2023 | deleteNode(next); |
| 2024 | } else { |
| 2025 | node.keys [node.right_idx] = null; |
| 2026 | node.values[node.right_idx] = null; |
| 2027 | node.right_idx--; |
| 2028 | node.size--; |
| 2029 | } |
| 2030 | } else { |
| 2031 | System.arraycopy(node.keys, left_idx , node.keys, left_idx + 1, moveFromLeft); |
| 2032 | System.arraycopy(node.values, left_idx , node.values, left_idx + 1, moveFromLeft); |
| 2033 | Node<K, V> prev = node.prev; |
| 2034 | if (prev != null && prev.size == 1) { |
| 2035 | node.keys [left_idx ] = prev.keys [prev.left_idx]; |
| 2036 | node.values[left_idx ] = prev.values[prev.left_idx]; |
no test coverage detected