diff options
21 files changed, 375 insertions, 641 deletions
@@ -21,7 +21,6 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F)) $(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template -$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/array-template obj/algorithms/searching/MultiinterpolationSearch.class: obj/algorithms/searching/InterpolationSearch.class obj/algorithms/searching/MultibinarySearch.class: obj/algorithms/searching/BinarySearch.class diff --git a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java index a72847c..dc4453f 100644 --- a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java @@ -26,6 +26,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayCircularDoublyLinkedList with_sentinel=0 with_head=0 with_tail=0 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArrayCircularDoublyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java index b8d7571..43c7737 100644 --- a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java @@ -26,6 +26,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayCircularSinglyLinkedList with_sentinel=0 with_head=0 with_tail=0 with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArrayCircularSinglyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=0 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java index 6be1dab..df9fa40 100644 --- a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java @@ -26,6 +26,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayDoublyLinkedList with_sentinel=0 with_head=1 with_tail=1 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArrayDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java index 4cd7b6d..33d127a 100644 --- a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java @@ -29,6 +29,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArraySentinelDoublyLinkedList with_sentinel=1 with_head=0 with_tail=0 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArraySentinelDoublyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java index c0aaa11..4101183 100644 --- a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java @@ -29,6 +29,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArraySentinelSinglyLinkedList with_sentinel=1 with_head=0 with_tail=0 with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArraySentinelSinglyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=0 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java index 1e1b6a7..e1421b7 100644 --- a/src/datastructures/linkedlists/ArraySinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java @@ -26,6 +26,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArraySinglyLinkedList with_sentinel=0 with_head=1 with_tail=1 with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArraySinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=0 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java index 45f47e8..d2c05d6 100644 --- a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java @@ -26,6 +26,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayTaillessDoublyLinkedList with_sentinel=0 with_head=1 with_tail=0 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArrayTaillessDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java index f09be45..09de059 100644 --- a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java @@ -26,6 +26,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayTaillessSinglyLinkedList with_sentinel=0 with_head=1 with_tail=0 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' +£>export name=ArrayTaillessSinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/CircularDoublyLinkedList.java b/src/datastructures/linkedlists/CircularDoublyLinkedList.java index a82c924..327305c 100644 --- a/src/datastructures/linkedlists/CircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/CircularDoublyLinkedList.java @@ -36,6 +36,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=CircularDoublyLinkedList with_sentinel=0 with_head=0 with_tail=0 with_prev=1 +£>export name=CircularDoublyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/CircularSinglyLinkedList.java b/src/datastructures/linkedlists/CircularSinglyLinkedList.java index cb20386..6ed8dcb 100644 --- a/src/datastructures/linkedlists/CircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/CircularSinglyLinkedList.java @@ -36,6 +36,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=CircularSinglyLinkedList with_sentinel=0 with_head=0 with_tail=0 with_prev=0 +£>export name=CircularSinglyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=0 with_prev=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java index 5978860..9be4ad8 100644 --- a/src/datastructures/linkedlists/DoublyLinkedList.java +++ b/src/datastructures/linkedlists/DoublyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=DoublyLinkedList with_sentinel=0 with_head=1 with_tail=1 with_prev=1 +£>export name=DoublyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java index 6bb2d91..626234a 100644 --- a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=HeadlessDoublyLinkedList with_sentinel=0 with_head=0 with_tail=1 with_prev=1 +£>export name=HeadlessDoublyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=1 with_prev=1 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java index 8ee71ee..900ad17 100644 --- a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java @@ -43,6 +43,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=HeadlessSinglyLinkedList with_sentinel=0 with_head=0 with_tail=1 with_prev=0 +£>export name=HeadlessSinglyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=1 with_prev=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java index 6da15c5..bb1f1d4 100644 --- a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java @@ -44,6 +44,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=SentinelDoublyLinkedList with_sentinel=1 with_head=0 with_tail=0 with_prev=1 +£>export name=SentinelDoublyLinkedList array=0 with_sentinel=1 with_head=0 with_tail=0 with_prev=1 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java index 66030ba..4af09b7 100644 --- a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java @@ -43,6 +43,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=SentinelSinglyLinkedList with_sentinel=1 with_head=0 with_tail=0 with_prev=0 +£>export name=SentinelSinglyLinkedList array=0 with_sentinel=1 with_head=0 with_tail=0 with_prev=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/SinglyLinkedList.java b/src/datastructures/linkedlists/SinglyLinkedList.java index 2f40db3..0fc85c6 100644 --- a/src/datastructures/linkedlists/SinglyLinkedList.java +++ b/src/datastructures/linkedlists/SinglyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=SinglyLinkedList with_sentinel=0 with_head=1 with_tail=1 with_prev=0 +£>export name=SinglyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=1 with_prev=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java index a5bba64..777e060 100644 --- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=TaillessDoublyLinkedList with_sentinel=0 with_head=1 with_tail=0 with_prev=1 +£>export name=TaillessDoublyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java index ceccceb..c7b55db 100644 --- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java @@ -33,6 +33,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=TaillessSinglyLinkedList with_sentinel=0 with_head=1 with_tail=0 with_prev=0 +£>export name=TaillessSinglyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=0 with_prev=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' 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 - -} - diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template index d207f5a..8cc0470 100644 --- a/src/datastructures/linkedlists/template +++ b/src/datastructures/linkedlists/template @@ -15,8 +15,50 @@ * 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/>. */ +£< + EDGE=EDGE ; (( with_sentinel )) && EDGE=edge + null=null ; (( array )) && null=EDGE + Node=Node ; (( array )) && Node=int + + circular=0 + if (( with_sentinel )) || (( (1 - with_head) * (1 - with_tail) )); then + circular=1 + fi + + function next + { + (( array )) && echo "this.next[${1}]" + (( array )) || echo "${1}.next" + } + function previous + { + (( array )) && echo "this.previous[${1}]" + (( array )) || echo "${1}.previous" + } + function free + { + (( array )) && echo "unuse(${1})" + (( array )) || echo "${1}" + } +£> +£>if (( 1 - array )); then +£> function new +£> { + £{Node} £{1} = new Node(£{2}); +£> } +£>else +£> function new +£> { + £{Node} £{1} = getNext(); + this.values[£{1}] = £{2}; +£> } +£>fi + + + public class £{name}<T> { +£>if (( 1 - array )); then /** * Node for the list */ @@ -54,79 +96,303 @@ public class £{name}<T> } + +£>else + /** + * 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; + + /** + * 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 +£>fi + £>if (( with_sentinel )); then /** * The sentinel node in the list */ - public Node edge; + public £{Node} edge; + + + + /** + * Initialiser + */ + { +£>(( array )) || + this.edge = new Node(null); +£>(( array )) && + this.values[this.edge = getNext()] = null; + £(next this.edge) = this.edge; +£>(( with_prev )) && + £(previous this.edge) = this.edge; + } £>fi £>if (( with_head )); then /** * The first node in the list */ - public Node head = null; + public £{Node} head = £{null}; £>fi £>if (( with_tail )); then /** * The last node in the list */ - public Node tail = null; + public £{Node} tail = £{null}; £>fi -£>if (( with_sentinel )); then +£>if (( array )); then /** - * Initialiser + * 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() { - this.edge = new Node(null); - this.edge.next = this.edge; + 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.edge.previous = this.edge; + 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; } -£>elif (( 1 - with_head )) && (( 1 - with_tail )); then + + /** + * 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; + } +£>fi + + + +£>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 Node create(T value) + public £{Node} create(T value) { - Node node = new Node(value); +£>new node value £>(( with_prev )) && - node.previous = node; - return node.next = node; + £(previous node) = node; + return £(next node) = node; } £>fi -£>if (( with_head )); then +£>if (( with_head )) || (( with_sentinel )); then /** * Insert a value in the beginning of the list * * @param value The value to insert * @return The node that has been created and inserted */ - public Node insertBeginning(T value) + public £{Node} insertBeginning(T value) £>if (( with_sentinel )); then { return insertAfter(value, this.edge); } £>else { - Node node = new Node(value); - node.next = this.head; +£>new node value + £(next node) = this.head; £>if (( with_prev )); then - if (node.next != null) - node.next.previous = node; + if (£(next node) != £{null}) + £(previous "$(next node)") = node; £>fi £>if (( with_tail )); then - if (this.head == null) + if (this.head == £{null}) this.tail = node; £>fi this.head = node; @@ -139,29 +405,30 @@ public class £{name}<T> * * @return The node that has been removed */ - public Node removeBeginning() + public £{Node} removeBeginning() £>if (( with_sentinel )); then { return removeAfter(this.edge); } £>else { - Node node = this.head; - if (node != null) - this.head = this.head.next; + £{Node} node = this.head; + if (node != £{null}) + this.head = £(next this.head); £>if (( with_prev )); then - if (this.head != null) - this.head.previous = null; + if (this.head != £{null}) + £(previous this.head) = £{null}; £>fi £>if (( with_tail )); then if (this.tail == node) - this.tail = null; + this.tail = £{null}; £>fi - return node; + return £(free node); } £>fi £>fi + /** * Insert a value after a specified, reference, node * @@ -169,16 +436,16 @@ public class £{name}<T> * @param predecessor The reference node * @return The node that has been created and inserted */ - public Node insertAfter(T value, Node predecessor) + public £{Node} insertAfter(T value, £{Node} predecessor) { - Node node = new Node(value); - node.next = predecessor.next; - predecessor.next = node; +£>new node value + £(next node) = £(next predecessor); + £(next predecessor) = node; £>if (( with_prev )); then - node.previous = predecessor; + £(previous node) = predecessor; £>(( with_sentinel )) || - if (node.next != null) - node.next.previous = node; + if (£(next node) != £{null}) + £(previous "$(next node)") = node; £>fi £>if (( with_tail )); then if (this.tail == predecessor) @@ -193,26 +460,27 @@ public class £{name}<T> * @param predecessor The reference node * @return The node that has been removed */ - public Node removeAfter(Node predecessor) + public £{Node} removeAfter(£{Node} predecessor) { - Node node = predecessor.next; + £{Node} node = £(next predecessor); £>(( with_sentinel )) || - if (node != null) + if (node != £{null}) { - predecessor.next = node.next; + £(next predecessor) = £(next node); £>if (( with_prev )); then £>(( with_sentinel )) || - if (node.next != null) - node.next.previous = predecessor; + if (£(next node) != £{null}) + £(previous "$(next node)") = predecessor; £>fi £>if (( with_tail )); then if (this.tail == node) this.tail = predecessor; £>fi } - return node; + return £(free node); } + £>if (( with_prev )); then /** * Insert a value before a specified, reference, node @@ -221,15 +489,15 @@ public class £{name}<T> * @param successor The reference node * @return The node that has been created and inserted */ - public Node insertBefore(T value, Node successor) + public £{Node} insertBefore(T value, £{Node} successor) { - Node node = new Node(value); - node.previous = successor.previous; - successor.previous = node; - node.next = successor; +£>new node value + £(previous node) = £(previous successor); + £(previous successor) = node; + £(next node) = successor; £>(( with_sentinel )) || - if (node.previous != null) - node.previous.next = node; + if (£(previous node) != £{null}) + £(next "$(previous node)") = node; £>if (( with_head )); then if (this.head == successor) this.head = node; @@ -243,88 +511,95 @@ public class £{name}<T> * @param successor The reference node * @return The node that has been removed */ - public Node removeBefore(Node successor) + public £{Node} removeBefore(£{Node} successor) { - Node node = successor.previous; + £{Node} node = £(previous successor); £>(( with_sentinel )) || - if (node != null) + if (node != £{null}) { - successor.previous = node.previous; + £(previous successor) = £(previous node); £>(( with_sentinel )) || - if (node.previous != null) - node.previous.next = successor; + if (£(previous node) != £{null}) + £(next "$(previous node)") = successor; £>if (( with_head )); then if (this.head == node) this.head = successor; £>fi } - return node; + return £(free node); } + /** * Remove the node from the list * * @param node The node to remove */ - public void remove(Node node) + public void remove(£{Node} node) { £>(( with_sentinel )) || - if (node.previous != null) - node.previous.next = node.next; + if (£(previous node) != £{null}) + £(next "$(previous node)") = £(next node); £>if (( with_head )); then else - this.head = node.next; + this.head = £(next node); £>fi + £>(( with_sentinel )) || - if (node.next != null) - node.next.previous = node.previous; + if (£(next node) != £{null}) + £(previous "$(next node)") = £(previous node); £>if (( with_tail )); then else - this.tail = node.previous; + this.tail = £(previous node); £>fi +£>(( array )) && + unuse(node); } £>fi -£>if (( with_tail )); then + +£>if (( with_tail )) || (( with_sentinel * with_prev )); then /** * Insert a value in the end of the list * * @param value The value to insert * @return The node that has been created and inserted */ - public Node insertEnd(T value) + public £{Node} insertEnd(T value) £>if (( with_sentinel )); then { return insertBefore(value, this.edge); } £>else { - if (this.tail == null) + if (this.tail == £{null}) £>(( with_head )) && return insertBeginning(value); -£>(( with_head )) || - return this.tail = new Node(value); +£>(( 1 - with_head )) && (( 1 - array )) && + return this.tail = new £{Node}(value); +£>(( 1 - with_head )) && (( array )) && + 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 * * @return The node that has been removed */ - public Node removeEnd() + public £{Node} removeEnd() £>if (( with_sentinel )); then { return removeBefore(this.edge); } £>else { - Node node = this.tail; - if (node != null) - (this.tail = node.previous).next = null; - return node; + £{Node} node = this.tail; + if (node != £{null}) + £(next "(this.tail = $(previous node))") = £{null}; + return £(free node); } £>fi £>fi |