diff options
Diffstat (limited to 'src/datastructures/linkedlists/array-template')
| -rw-r--r-- | src/datastructures/linkedlists/array-template | 540 |
1 files changed, 0 insertions, 540 deletions
diff --git a/src/datastructures/linkedlists/array-template b/src/datastructures/linkedlists/array-template deleted file mode 100644 index 177a6cf..0000000 --- a/src/datastructures/linkedlists/array-template +++ /dev/null @@ -1,540 +0,0 @@ -/* -*- java -*- */ -/** - * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU Affero General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU Affero General Public License for more details. - * - * You should have received a copy of the GNU Affero General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -public class £{name}<T> -{ -£<EDGE=EDGE ; (( with_sentinel )) && EDGE=edge - circular=0 - if (( with_sentinel )) || (( (1 - with_head) * (1 - with_tail) )); then - circular=1 -£>fi - - - /** - * The default initial capacity - */ - private static final int DEFAULT_INITIAL_CAPACITY = 128; - -£>if (( 1 - with_sentinel )); then - /** - * Sentinel value indicating that an edge has been reached - */ - public static final int EDGE = -1; -£>fi - - /** - * Sentinel value indicating that the position is unused - */ - public static final int UNUSED = -2; - - - - /** - * Constructor - */ - public £{name}() - { - this(DEFAULT_INITIAL_CAPACITY); - } - - /** - * Constructor - * - * @param initialCapacity The initial size of the arrays - */ - @SuppressWarnings("unchecked") - public £{name}(int initialCapacity) - { - /* Most be a power of 2 */ - if ((initialCapacity & initialCapacity - 1) != 0) - { - initialCapacity |= initialCapacity >> 1; - initialCapacity |= initialCapacity >> 2; - initialCapacity |= initialCapacity >> 4; - initialCapacity |= initialCapacity >> 8; - initialCapacity |= initialCapacity >> 16; - initialCapacity++; - } - - this.capacity = initialCapacity; - this.next = new int[initialCapacity]; -£>(( with_prev )) && - this.previous = new int[initialCapacity]; - this.reusable = new int[initialCapacity]; - this.values = (T[])(new Object[initialCapacity]); - } - - - - /** - * The size of the arrays - */ - private int capacity; - - /** - * The index after the last used index in - * {@link #values} and {@link #next} - */ - public int end = 0; - - /** - * Head of the stack of reusable positions - */ - private int reuseHead = 0; - - /** - * Stack of indices than are no longer in use - */ - private int[] reusable; - -£>if (( with_sentinel )); then - /** - * The sentinel node in the list - */ - public int edge; -£>fi - -£>if (( with_head )); then - /** - * The first node in the list - */ - public int head = EDGE; -£>fi - -£>if (( with_tail )); then - /** - * The last node in the list - */ - public int tail = EDGE; -£>fi - - /** - * The value stored in each node - */ - public T[] values; - - /** - * The next node for each node, {@link #£{EDGE}} - * if the current node is the last node, and - * {@link #UNUSED} if there is no node on this - * position - */ - public int[] next; - -£>if (( with_prev )); then - /** - * The previou node for each node, {@link #£{EDGE}} - * if the current node is the first node, and - * {@link #UNUSED} if there is no node on this - * position - */ - public int[] previous; -£>fi - - - -£>if (( with_sentinel )); then - /** - * Initialiser - */ - { - this.edge = getNext(); - this.values[this.edge] = null; - this.next[this.edge] = this.edge; -£>(( with_prev )) && - this.previous[this.edge] = this.edge; - } -£>fi - - - - /** - * Pack the list so that there are no reusable - * positions, and reduce the capacity to the - * smallest capacity that can be used. Not that - * values (nodes) returned by the list's methods - * will become invalid. Additionally (to reduce - * the complexity) the list will be defragment - * so that the nodes' indices are continuous. - * This method has linear time complexity and - * linear memory complexity. - */ - public void pack() - { - int size = this.end - reuseHead; - int cap = size; - if ((cap & cap - 1) != 0) - { - cap |= cap >> 1; - cap |= cap >> 2; - cap |= cap >> 4; - cap |= cap >> 8; - cap |= cap >> 16; - cap++; - } - - @SuppressWarnings("unchecked") - T[] vals = (T[])(new Object[cap]); -£>if (( 1 - with_head )); then - int head = 0; - while ((head < this.end) && (this.next[head] == UNUSED)) - head++; - if (head < this.end) - for (int ptr = 0, node = head; (node != head) || (ptr == 0);) -£>elif (( with_sentinel )); then - for (int ptr = 0, node = this.edge; (node != this.edge) || (ptr == 0);) -£>else - for (int ptr = 0, node = this.head; node != EDGE;) -£>fi - { - vals[ptr++] = this.values[node]; - node = this.next[node]; - } - - if (cap != this.capacity) - { - this.reusable = new int[cap]; - this.next = new int[cap]; -£>(( with_prev )) && - this.previous = new int[cap]; - } - -£>LAST=EDGE ; BEGINNING=0 ; (( circular )) && { LAST=0; BEGINNING=1; } - for (int i = 0; i < size;) - this.next[i] = ++i; - this.next[size - 1] = £{LAST}; - -£>if (( with_prev )); then - for (int i = £{BEGINNING}; i < size; i++) - this.previous[i] = i - 1; -£>(( circular )) && - this.previous[0] = size - 1; -£>fi - - this.values = vals; - this.end = size; - this.reuseHead = 0; -£>(( with_head )) && - this.head = 0; -£>(( with_tail )) && - this.tail = this.end - 1; - } - - - /** - * Gets the next free position, and grow the - * arrays if necessary. This methods has constant - * amortised time complexity. - * - * @return The next free position - */ - @SuppressWarnings("unchecked") - private int getNext() - { - if (this.reuseHead > 0) - return this.reusable[--this.reuseHead]; - if (this.end == this.capacity) - { - this.capacity <<= 1; - System.arraycopy(this.values, 0, this.values = (T[])(new Object[this.capacity]), 0, this.end); - System.arraycopy(this.reusable, 0, this.reusable = new int[this.capacity], 0, this.end); - System.arraycopy(this.next, 0, this.next = new int[this.capacity], 0, this.end); -£>(( with_prev )) && - System.arraycopy(this.previous, 0, this.previous = new int[this.capacity], 0, this.end); - } - return this.end++; - } - - - /** - * Mark a position as unused - * - * @param node The position - * @return The position - */ - private int unuse(int node) - { - this.reusable[reuseHead++] = node; - this.next[node] = UNUSED; -£>(( with_prev )) && - this.previous[node] = UNUSED; - return node; - } - - -£>if (( 1 - with_sentinel )) && (( 1 - with_head )) && (( 1 - with_tail )); then - /** - * Creates the initial node in a circularly linked list - * - * @param value The value of the initial node - * @return The node that has been created and inserted - */ - public int create(T value) - { - int node = getNext(); - this.values[node] = value; -£>(( with_prev )) && - this.previous[node] = node; - return this.next[node] = node; - } -£>fi - - -£>if (( with_head )) || (( with_sentinel )); then - /** - * Insert a value in the beginning of the list. - * This methods has constant amortised time complexity. - * - * @param value The value to insert - * @return The node that has been created and inserted - */ - public int insertBeginning(T value) -£>if (( with_sentinel )); then - { - return insertAfter(value, this.edge); - } -£>else - { - int node = getNext(); - this.values[node] = value; - this.next[node] = this.head; -£>if (( with_prev )); then - if (this.next[node] != EDGE) - this.previous[this.next[node]] = node; -£>fi -£>if (( with_tail )); then - if (this.head == EDGE) - this.tail = node; -£>fi - this.head = node; - return node; - } -£>fi - - /** - * Remove the node at the beginning of the list. - * This methods has constant time complexity. - * - * @return The node that has been removed - */ - public int removeBeginning() -£>if (( with_sentinel )); then - { - return removeAfter(this.edge); - } -£>else - { - int node = this.head; - if (node != EDGE) - this.head = this.next[this.head]; -£>if (( with_prev )); then - if (this.head != EDGE) - this.previous[this.head] = EDGE; -£>fi -£>if (( with_tail )); then - if (this.tail == node) - this.tail = EDGE; -£>fi - return unuse(node); - } -£>fi -£>fi - - - /** - * Insert a value after a specified, reference, node. - * This methods has constant amortised time complexity. - * - * @param value The value to insert - * @param predecessor The reference node - * @return The node that has been created and inserted - */ - public int insertAfter(T value, int predecessor) - { - int node = getNext(); - this.values[node] = value; - this.next[node] = this.next[predecessor]; - this.next[predecessor] = node; -£>if (( with_prev )); then - this.previous[node] = predecessor; -£>(( 1 - with_sentinel )) && - if (this.next[node] != EDGE) - this.previous[this.next[node]] = node; -£>fi -£>if (( with_tail )); then - if (this.tail == predecessor) - this.tail = node; -£>fi - return node; - } - - /** - * Remove the node after a specified, reference, node. - * This methods has constant time complexity. - * - * @param predecessor The reference node - * @return The node that has been removed - */ - public int removeAfter(int predecessor) - { - int node = this.next[predecessor]; -£>(( 1 - with_sentinel )) && - if (node != EDGE) - { - this.next[predecessor] = this.next[node]; -£>if (( with_prev )); then -£>(( 1 - with_sentinel )) && - if (this.next[node] != EDGE) - this.previous[this.next[node]] = predecessor; -£>fi -£>if (( with_tail )); then - if (this.tail == node) - this.tail = predecessor; -£>fi - } - return unuse(node); - } - - -£>if (( with_prev )); then - /** - * Insert a value before a specified, reference, node. - * This methods has constant amortised time complexity. - * - * @param value The value to insert - * @param successor The reference node - * @return The node that has been created and inserted - */ - public int insertBefore(T value, int successor) - { - int node = getNext(); - this.values[node] = value; - this.previous[node] = this.previous[successor]; - this.previous[successor] = node; - this.next[node] = successor; -£>(( 1 - with_sentinel )) && - if (this.previous[node] != EDGE) - this.next[this.previous[node]] = node; -£>if (( with_head )); then - if (this.head == successor) - this.head = node; -£>fi - return node; - } - - /** - * Remove the node before a specified, reference, node. - * This methods has constant time complexity. - * - * @param successor The reference node - * @return The node that has been removed - */ - public int removeBefore(int successor) - { - int node = this.previous[successor]; -£>(( 1 - with_sentinel )) && - if (node != EDGE) - { - this.previous[successor] = this.previous[node]; -£>(( 1 - with_sentinel )) && - if (this.previous[node] != EDGE) - this.next[this.previous[node]] = successor; -£>if (( with_head )); then - if (this.head == node) - this.head = successor; -£>fi - } - return unuse(node); - } - - - /** - * Remove the node from the list. - * This methods has constant time complexity. - * - * @param node The node to remove - */ - public void remove(int node) - { -£>(( 1 - with_sentinel )) && - if (this.previous[node] != EDGE) - this.next[this.previous[node]] = this.next[node]; -£>if (( with_head )); then - else - this.head = this.next[node]; -£>fi -£>(( 1 - with_sentinel )) && - if (this.next[node] != EDGE) - this.previous[this.next[node]] = this.previous[node]; -£>if (( with_tail )); then - else - this.tail = this.previous[node]; -£>fi - unuse(node); - } -£>fi - - -£>if (( with_tail )) || (( with_sentinel * with_prev )); then - /** - * Insert a value in the end of the list. - * This methods has constant amortised time complexity. - * - * @param value The value to insert - * @return The node that has been created and inserted - */ - public int insertEnd(T value) -£>if (( with_sentinel )); then - { - return insertBefore(value, this.edge); - } -£>else - { - if (this.tail == EDGE) -£>(( with_head )) && - return insertBeginning(value); -£>(( with_head )) || - return this.values[this.tail = getNext()] = value; - return insertAfter(value, this.tail); - } -£>fi - -£>if (( with_prev )); then - /** - * Remove the node at the end of the list. - * This methods has constant time complexity. - * - * @return The node that has been removed - */ - public int removeEnd() -£>if (( with_sentinel )); then - { - return removeBefore(this.edge); - } -£>else - { - int node = this.tail; - if (node != EDGE) - this.next[this.tail = this.previous[node]] = EDGE; - return unuse(node); - } -£>fi -£>fi -£>fi - -} - |