whoops + add array sentinel linked lists

Signed-off-by: Mattias Andrée <maandree@operamail.com>

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;
     }