/* -*- 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 . */ public class £{name} { /** * The default initial capacity */ private static final int DEFAULT_INITIAL_CAPACITY = 128; /** * Sentinel value indicating that an edge has been reached */ public static final int EDGE = -1; /** * 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_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 /** * 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);) £>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]; } for (int i = 0; i < size;) this.next[i] = ++i; this.next[size - 1] = EDGE; £>if (( with_prev )); then for (int i = 0; i < size; i++) this.previous[i] = i - 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_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 )); 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) { 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; } /** * 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() { 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 /** * 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; 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]; if (node == EDGE) this.next[predecessor] = this.next[node]; £>if (( with_prev )); then else 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; 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]; if (node == EDGE) this.previous[successor] = this.previous[node]; else 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) { if (this.previous[node] != EDGE) this.next[this.previous[node]] = this.next[node]; £>if (( with_head )); then else this.head = this.next[node]; £>fi 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 )); 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 (this.tail == EDGE) £>(( with_head )) && return insertBeginning(value); £>(( with_head )) || return this.values[this.tail = getNext()] = value; return insertAfter(value, this.tail); } £>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() { int node = this.tail; if (node != EDGE) this.next[this.tail = this.previous[node]] = EDGE; return unuse(node); } £>fi £>fi }