aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--Makefile1
-rw-r--r--src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/ArrayDoublyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/ArraySinglyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java2
-rw-r--r--src/datastructures/linkedlists/CircularDoublyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/CircularSinglyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/DoublyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/HeadlessDoublyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/HeadlessSinglyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/SentinelDoublyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/SentinelSinglyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/SinglyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/TaillessDoublyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/TaillessSinglyLinkedList.java5
-rw-r--r--src/datastructures/linkedlists/sentinel-template198
-rw-r--r--src/datastructures/linkedlists/template57
21 files changed, 82 insertions, 240 deletions
diff --git a/Makefile b/Makefile
index becac32..ad34f62 100644
--- a/Makefile
+++ b/Makefile
@@ -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
}