From 462bb1bb37d8ab9226f563852e4a53f670237d9c Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Thu, 23 Jan 2014 10:25:39 +0100 Subject: add array linked lists MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- Makefile | 4 +- .../linkedlists/ArrayCircularDoublyLinkedList.java | 31 ++ .../linkedlists/ArrayCircularSinglyLinkedList.java | 31 ++ .../linkedlists/ArrayDoublyLinkedList.java | 31 ++ .../linkedlists/ArraySinglyLinkedList.java | 31 ++ .../linkedlists/ArrayTaillessDoublyLinkedList.java | 31 ++ .../linkedlists/ArrayTaillessSinglyLinkedList.java | 31 ++ src/datastructures/linkedlists/array-template | 468 +++++++++++++++++++++ 8 files changed, 657 insertions(+), 1 deletion(-) create mode 100644 src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java create mode 100644 src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java create mode 100644 src/datastructures/linkedlists/ArrayDoublyLinkedList.java create mode 100644 src/datastructures/linkedlists/ArraySinglyLinkedList.java create mode 100644 src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java create mode 100644 src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java create mode 100644 src/datastructures/linkedlists/array-template diff --git a/Makefile b/Makefile index 0e85b78..becac32 100644 --- a/Makefile +++ b/Makefile @@ -20,7 +20,9 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F)) env GPP="$(GPP)" $(GPP) -s £ < "$<" > "$@" -$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template src/datastructures/linkedlists/sentinel-template +$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template +$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/sentinel-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 new file mode 100644 index 0000000..7e059bd --- /dev/null +++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java @@ -0,0 +1,31 @@ +/** + * 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 . + */ +package datastructures.linkedlists; + + +/** + * Array circular doubly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. In this implementation, when a node is + * removed the value stored that that position is not + * removed before that position is reused. + * + * @param The value stored in the structure + */ +£>export name=ArrayCircularDoublyLinkedList with_head=0 with_tail=0 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' + diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java new file mode 100644 index 0000000..10496d4 --- /dev/null +++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java @@ -0,0 +1,31 @@ +/** + * 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 . + */ +package datastructures.linkedlists; + + +/** + * Array circular singly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. In this implementation, when a node is + * removed the value stored that that position is not + * removed before that position is reused. + * + * @param The value stored in the structure + */ +£>export name=ArrayCircularSinglyLinkedList with_head=0 with_tail=0 with_prev=0 +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' + diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java new file mode 100644 index 0000000..bcc2bc1 --- /dev/null +++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java @@ -0,0 +1,31 @@ +/** + * 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 . + */ +package datastructures.linkedlists; + + +/** + * Array doubly linked list class. An array linked list + * is a linked list constructed by parallel arrays. In + * this implementation, when a node is removed the value + * stored that that position is not removed before that + * position is reused. + * + * @param The value stored in the structure + */ +£>export name=ArrayDoublyLinkedList with_head=1 with_tail=1 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' + diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java new file mode 100644 index 0000000..a4668d1 --- /dev/null +++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java @@ -0,0 +1,31 @@ +/** + * 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 . + */ +package datastructures.linkedlists; + + +/** + * Array singly linked list class. An array linked list + * is a linked list constructed by parallel arrays. In + * this implementation, when a node is removed the value + * stored that that position is not removed before that + * position is reused. + * + * @param The value stored in the structure + */ +£>export name=ArraySinglyLinkedList with_head=1 with_tail=1 with_prev=0 +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' + diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java new file mode 100644 index 0000000..5098bf1 --- /dev/null +++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java @@ -0,0 +1,31 @@ +/** + * 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 . + */ +package datastructures.linkedlists; + + +/** + * Array tailless doubly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. In this implementation, when a node is + * removed the value stored that that position is not + * removed before that position is reused. + * + * @param The value stored in the structure + */ +£>export name=ArrayTaillessDoublyLinkedList with_head=1 with_tail=0 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' + diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java new file mode 100644 index 0000000..bd27cee --- /dev/null +++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java @@ -0,0 +1,31 @@ +/** + * 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 . + */ +package datastructures.linkedlists; + + +/** + * Array tailless singly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. In this implementation, when a node is + * removed the value stored that that position is not + * removed before that position is reused. + * + * @param The value stored in the structure + */ +£>export name=ArrayTaillessSinglyLinkedList with_head=1 with_tail=0 with_prev=1 +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' + diff --git a/src/datastructures/linkedlists/array-template b/src/datastructures/linkedlists/array-template new file mode 100644 index 0000000..5fce858 --- /dev/null +++ b/src/datastructures/linkedlists/array-template @@ -0,0 +1,468 @@ +/* -*- 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 >>= 1; + initialCapacity >>= 2; + initialCapacity >>= 4; + initialCapacity >>= 8; + 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 >>= 1; + cap >>= 2; + cap >>= 4; + cap >>= 8; + 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 + +} + -- cgit v1.2.3-70-g09d2