diff options
21 files changed, 82 insertions, 240 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/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 index 7be7dae..a72847c 100644 --- a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java @@ -27,5 +27,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java index a3418c0..b8d7571 100644 --- a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java @@ -27,5 +27,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java index 318e844..6be1dab 100644 --- a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java @@ -27,5 +27,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java index e4658a8..4cd7b6d 100644 --- a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java @@ -30,5 +30,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java index 4423bef..c0aaa11 100644 --- a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java @@ -30,5 +30,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java index d491d83..1e1b6a7 100644 --- a/src/datastructures/linkedlists/ArraySinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java @@ -27,5 +27,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java index f2c9825..45f47e8 100644 --- a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java @@ -27,5 +27,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java index cd86296..f09be45 100644 --- a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java @@ -27,5 +27,5 @@ 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' +£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/CircularDoublyLinkedList.java b/src/datastructures/linkedlists/CircularDoublyLinkedList.java index 5ba0cef..a82c924 100644 --- a/src/datastructures/linkedlists/CircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/CircularDoublyLinkedList.java @@ -36,7 +36,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class CircularDoublyLinkedList<T> -£>export with_head=0 with_tail=0 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=CircularDoublyLinkedList 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 49ddd83..cb20386 100644 --- a/src/datastructures/linkedlists/CircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/CircularSinglyLinkedList.java @@ -36,7 +36,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class CircularSinglyLinkedList<T> -£>export with_head=0 with_tail=0 with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=CircularSinglyLinkedList 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 3500e82..5978860 100644 --- a/src/datastructures/linkedlists/DoublyLinkedList.java +++ b/src/datastructures/linkedlists/DoublyLinkedList.java @@ -34,7 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class DoublyLinkedList<T> -£>export with_head=1 with_tail=1 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=DoublyLinkedList 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 e7ef98b..6bb2d91 100644 --- a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java @@ -34,7 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class HeadlessDoublyLinkedList<T> -£>export with_head=0 with_tail=1 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=HeadlessDoublyLinkedList 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 9ab46d1..8ee71ee 100644 --- a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java @@ -43,7 +43,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class HeadlessSinglyLinkedList<T> -£>export with_head=0 with_tail=1 with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=HeadlessSinglyLinkedList 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 11ab04a..6da15c5 100644 --- a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java @@ -44,7 +44,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class SentinelDoublyLinkedList<T> -£>export with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/sentinel-template | sed -e '/^[/ ]\*/d' +£>export name=SentinelDoublyLinkedList 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 dd1c23f..66030ba 100644 --- a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java @@ -43,7 +43,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class SentinelSinglyLinkedList<T> -£>export with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/sentinel-template | sed -e '/^[/ ]\*/d' +£>export name=SentinelSinglyLinkedList 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 c14bc49..2f40db3 100644 --- a/src/datastructures/linkedlists/SinglyLinkedList.java +++ b/src/datastructures/linkedlists/SinglyLinkedList.java @@ -34,7 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class SinglyLinkedList<T> -£>export with_head=1 with_tail=1 with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=SinglyLinkedList 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 9ea9686..a5bba64 100644 --- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java @@ -34,7 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class TaillessDoublyLinkedList<T> -£>export with_head=1 with_tail=0 with_prev=1 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=TaillessDoublyLinkedList 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 9dd3db8..ceccceb 100644 --- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java @@ -33,7 +33,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -public class TaillessSinglyLinkedList<T> -£>export with_head=1 with_tail=0 with_prev=0 -£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' +£>export name=TaillessSinglyLinkedList 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/sentinel-template b/src/datastructures/linkedlists/sentinel-template deleted file mode 100644 index 9de6019..0000000 --- a/src/datastructures/linkedlists/sentinel-template +++ /dev/null @@ -1,198 +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/>. - */ -{ - /** - * Node for the list - */ - public class Node - { - /** - * Constructor - * - * @param value The value to store in the list - */ - public Node(T value) - { - this.value = value; - } - - - - /** - * The value stored in the list by this node - */ - public T value; - - /** - * The next node in the list - */ - public Node next = null; - -£>if (( with_prev )); then - /** - * The previous node in the list - */ - public Node previous = null; -£>fi - - } - - - - /** - * The sentinel node in the list - */ - public Node edge; - - - - /** - * Initialiser - */ - { - this.edge = new Node(null); - this.edge.next = this.edge; -£>(( with_prev )) && - this.edge.previous = this.edge; - } - - - - /** - * 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) - { - return insertAfter(value, this.edge); - } - - /** - * Remove the node at the beginning of the list - * - * @return The node that has been removed - */ - public Node removeBeginning() - { - return removeAfter(this.edge); - } - - /** - * Insert a value after a specified, reference, node - * - * @param value The value to insert - * @param predecessor The reference node - * @return The node that has been created and inserted - */ - public Node insertAfter(T value, Node predecessor) - { - Node node = new Node(value); - node.next = predecessor.next; - predecessor.next = node; -£>if (( with_prev )); then - node.previous = predecessor; - node.next.previous = node; -£>fi - return node; - } - - /** - * Remove the node after a specified, reference, node - * - * @param predecessor The reference node - * @return The node that has been removed - */ - public Node removeAfter(Node predecessor) - { - Node node = predecessor.next; - predecessor.next = node.next; -£>if (( with_prev )); then - predecessor.next.previous = predecessor; -£>fi - return node; - } - -£>if (( with_prev )); then - /** - * Insert a value before a specified, reference, node - * - * @param value The value to insert - * @param successor The reference node - * @return The node that has been created and inserted - */ - public Node insertBefore(T value, Node successor) - { - Node node = new Node(value); - node.previous = successor.previous; - successor.previous = node; - node.next = successor; - node.previous.next = node; - return node; - } - - /** - * Remove the node before a specified, reference, node - * - * @param successor The reference node - * @return The node that has been removed - */ - public Node removeBefore(Node successor) - { - Node node = successor.previous; - successor.previous = node.previous; - successor.previous.next = successor; - return node; - } - - /** - * Remove the node from the list - * - * @param node The node to remove - */ - public void remove(Node node) - { - node.previous.next = node.next; - node.next.previous = node.previous; - } - - /** - * 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) - { - return insertBefore(value, this.edge); - } - - /** - * Remove the node at the end of the list - * - * @return The node that has been removed - */ - public Node removeEnd() - { - return removeBefore(this.edge); - } -£>fi - -} - diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template index d2f6c84..d207f5a 100644 --- a/src/datastructures/linkedlists/template +++ b/src/datastructures/linkedlists/template @@ -15,6 +15,7 @@ * 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> { /** * Node for the list @@ -53,6 +54,12 @@ } +£>if (( with_sentinel )); then + /** + * The sentinel node in the list + */ + public Node edge; +£>fi £>if (( with_head )); then /** @@ -69,8 +76,19 @@ £>fi - -£>if (( 1 - with_head )) && (( 1 - with_tail )); then + +£>if (( with_sentinel )); then + /** + * Initialiser + */ + { + this.edge = new Node(null); + this.edge.next = this.edge; +£>(( with_prev )) && + this.edge.previous = this.edge; + } + +£>elif (( 1 - with_head )) && (( 1 - with_tail )); then /** * Creates the initial node in a circularly linked list * @@ -86,6 +104,7 @@ } £>fi + £>if (( with_head )); then /** * Insert a value in the beginning of the list @@ -94,6 +113,11 @@ * @return The node that has been created and inserted */ public Node insertBeginning(T value) +£>if (( with_sentinel )); then + { + return insertAfter(value, this.edge); + } +£>else { Node node = new Node(value); node.next = this.head; @@ -108,6 +132,7 @@ this.head = node; return node; } +£>fi /** * Remove the node at the beginning of the list @@ -115,6 +140,11 @@ * @return The node that has been removed */ public Node removeBeginning() +£>if (( with_sentinel )); then + { + return removeAfter(this.edge); + } +£>else { Node node = this.head; if (node != null) @@ -130,6 +160,7 @@ return node; } £>fi +£>fi /** * Insert a value after a specified, reference, node @@ -145,6 +176,7 @@ predecessor.next = node; £>if (( with_prev )); then node.previous = predecessor; +£>(( with_sentinel )) || if (node.next != null) node.next.previous = node; £>fi @@ -164,10 +196,12 @@ public Node removeAfter(Node predecessor) { Node node = predecessor.next; +£>(( with_sentinel )) || if (node != null) { predecessor.next = node.next; £>if (( with_prev )); then +£>(( with_sentinel )) || if (node.next != null) node.next.previous = predecessor; £>fi @@ -178,7 +212,7 @@ } return node; } - + £>if (( with_prev )); then /** * Insert a value before a specified, reference, node @@ -193,6 +227,7 @@ node.previous = successor.previous; successor.previous = node; node.next = successor; +£>(( with_sentinel )) || if (node.previous != null) node.previous.next = node; £>if (( with_head )); then @@ -211,9 +246,11 @@ public Node removeBefore(Node successor) { Node node = successor.previous; +£>(( with_sentinel )) || if (node != null) { successor.previous = node.previous; +£>(( with_sentinel )) || if (node.previous != null) node.previous.next = successor; £>if (( with_head )); then @@ -231,12 +268,14 @@ */ public void remove(Node node) { +£>(( with_sentinel )) || if (node.previous != null) node.previous.next = node.next; £>if (( with_head )); then else this.head = node.next; £>fi +£>(( with_sentinel )) || if (node.next != null) node.next.previous = node.previous; £>if (( with_tail )); then @@ -254,6 +293,11 @@ * @return The node that has been created and inserted */ public Node insertEnd(T value) +£>if (( with_sentinel )); then + { + return insertBefore(value, this.edge); + } +£>else { if (this.tail == null) £>(( with_head )) && @@ -262,6 +306,7 @@ return this.tail = new Node(value); return insertAfter(value, this.tail); } +£>fi £>if (( with_prev )); then /** @@ -270,6 +315,11 @@ * @return The node that has been removed */ public Node removeEnd() +£>if (( with_sentinel )); then + { + return removeBefore(this.edge); + } +£>else { Node node = this.tail; if (node != null) @@ -278,6 +328,7 @@ } £>fi £>fi +£>fi } |