diff options
10 files changed, 177 insertions, 33 deletions
diff --git a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java index 7e059bd..7be7dae 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_head=0 with_tail=0 with_prev=1 +£>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' diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java index 10496d4..a3418c0 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_head=0 with_tail=0 with_prev=0 +£>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' diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java index bcc2bc1..318e844 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_head=1 with_tail=1 with_prev=1 +£>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' diff --git a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java new file mode 100644 index 0000000..e4658a8 --- /dev/null +++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java @@ -0,0 +1,34 @@ +/** + * 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/>. + */ +package datastructures.linkedlists; + + +/** + * Array sentinel doubly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. A sentinel linked list is a linear linked + * listed constructed as a circular linked listed with + * a sentinel (dummy) node between the first node and + * the last node. In this implementation, when a node + * is removed the value stored that that position is + * not removed before that position is reused. + * + * @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' + diff --git a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java new file mode 100644 index 0000000..4423bef --- /dev/null +++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java @@ -0,0 +1,34 @@ +/** + * 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/>. + */ +package datastructures.linkedlists; + + +/** + * Array sentinel singly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. A sentinel linked list is a linear linked + * listed constructed as a circular linked listed with + * a sentinel (dummy) node between the first node and + * the last node. In this implementation, when a node + * is removed the value stored that that position is + * not removed before that position is reused. + * + * @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' + diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java index a4668d1..d491d83 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_head=1 with_tail=1 with_prev=0 +£>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' diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java index 5098bf1..f2c9825 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_head=1 with_tail=0 with_prev=1 +£>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' diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java index bd27cee..cd86296 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_head=1 with_tail=0 with_prev=1 +£>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' diff --git a/src/datastructures/linkedlists/array-template b/src/datastructures/linkedlists/array-template index bee7e01..177a6cf 100644 --- a/src/datastructures/linkedlists/array-template +++ b/src/datastructures/linkedlists/array-template @@ -17,15 +17,24 @@ */ 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 @@ -92,6 +101,13 @@ public class £{name}<T> */ 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 @@ -112,7 +128,7 @@ public class £{name}<T> public T[] values; /** - * The next node for each node, {@link #EDGE} + * 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 @@ -121,7 +137,7 @@ public class £{name}<T> £>if (( with_prev )); then /** - * The previou node for each node, {@link #EDGE} + * 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 @@ -131,6 +147,21 @@ public class £{name}<T> +£>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 @@ -164,6 +195,8 @@ public class £{name}<T> 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 @@ -180,13 +213,16 @@ public class £{name}<T> 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] = EDGE; + this.next[size - 1] = £{LAST}; £>if (( with_prev )); then - for (int i = 0; i < size; i++) + for (int i = £{BEGINNING}; i < size; i++) this.previous[i] = i - 1; +£>(( circular )) && + this.previous[0] = size - 1; £>fi this.values = vals; @@ -240,7 +276,7 @@ public class £{name}<T> } -£>if (( 1 - with_head )) && (( 1 - with_tail )); then +£>if (( 1 - with_sentinel )) && (( 1 - with_head )) && (( 1 - with_tail )); then /** * Creates the initial node in a circularly linked list * @@ -258,7 +294,7 @@ public class £{name}<T> £>fi -£>if (( with_head )); then +£>if (( with_head )) || (( with_sentinel )); then /** * Insert a value in the beginning of the list. * This methods has constant amortised time complexity. @@ -267,6 +303,11 @@ public class £{name}<T> * @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; @@ -282,6 +323,7 @@ public class £{name}<T> this.head = node; return node; } +£>fi /** * Remove the node at the beginning of the list. @@ -290,6 +332,11 @@ public class £{name}<T> * @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) @@ -305,6 +352,7 @@ public class £{name}<T> return unuse(node); } £>fi +£>fi /** @@ -323,6 +371,7 @@ public class £{name}<T> 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 @@ -343,16 +392,20 @@ public class £{name}<T> public int removeAfter(int predecessor) { int node = this.next[predecessor]; - if (node == EDGE) +£>(( 1 - with_sentinel )) && + 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; +£>(( 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; + if (this.tail == node) + this.tail = predecessor; £>fi + } return unuse(node); } @@ -373,6 +426,7 @@ public class £{name}<T> 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 @@ -392,14 +446,18 @@ public class £{name}<T> public int removeBefore(int successor) { int node = this.previous[successor]; - if (node == EDGE) +£>(( 1 - with_sentinel )) && + if (node != EDGE) + { this.previous[successor] = this.previous[node]; - else if (this.previous[node] != EDGE) - this.next[this.previous[node]] = successor; +£>(( 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; + if (this.head == node) + this.head = successor; £>fi + } return unuse(node); } @@ -412,12 +470,14 @@ public class £{name}<T> */ 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 @@ -429,7 +489,7 @@ public class £{name}<T> £>fi -£>if (( with_tail )); then +£>if (( with_tail )) || (( with_sentinel * with_prev )); then /** * Insert a value in the end of the list. * This methods has constant amortised time complexity. @@ -438,6 +498,11 @@ public class £{name}<T> * @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 )) && @@ -446,6 +511,7 @@ public class £{name}<T> return this.values[this.tail = getNext()] = value; return insertAfter(value, this.tail); } +£>fi £>if (( with_prev )); then /** @@ -455,6 +521,11 @@ public class £{name}<T> * @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) @@ -463,6 +534,7 @@ public class £{name}<T> } £>fi £>fi +£>fi } diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template index c2ff722..d2f6c84 100644 --- a/src/datastructures/linkedlists/template +++ b/src/datastructures/linkedlists/template @@ -164,16 +164,18 @@ public Node removeAfter(Node predecessor) { Node node = predecessor.next; - if (node == null) + if (node != null) + { predecessor.next = node.next; £>if (( with_prev )); then - else if (node.next != null) - node.next.previous = predecessor; + if (node.next != null) + node.next.previous = predecessor; £>fi £>if (( with_tail )); then - if (this.tail == node) - this.tail = predecessor; + if (this.tail == node) + this.tail = predecessor; £>fi + } return node; } @@ -209,14 +211,16 @@ public Node removeBefore(Node successor) { Node node = successor.previous; - if (node == null) + if (node != null) + { successor.previous = node.previous; - else if (node.previous != null) - node.previous.next = successor; + if (node.previous != null) + node.previous.next = successor; £>if (( with_head )); then - if (this.head == node) - this.head = successor; + if (this.head == node) + this.head = successor; £>fi + } return node; } |