code deduplication

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

21 files changed, 375 insertions, 641 deletions

diff --git a/Makefile b/Makefile
index ad34f62..353e64b 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/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 a72847c..dc4453f 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_sentinel=0 with_head=0 with_tail=0 with_prev=1
-£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d'
+£>export name=ArrayCircularDoublyLinkedList array=1 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/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
index b8d7571..43c7737 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_sentinel=0 with_head=0 with_tail=0 with_prev=0
-£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d'
+£>export name=ArrayCircularSinglyLinkedList array=1 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/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
index 6be1dab..df9fa40 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_sentinel=0 with_head=1 with_tail=1 with_prev=1
-£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d'
+£>export name=ArrayDoublyLinkedList array=1 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/ArraySentinelDoublyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
index 4cd7b6d..33d127a 100644
--- a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
@@ -29,6 +29,6 @@ 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' -e '/^$/d'
+£>export name=ArraySentinelDoublyLinkedList array=1 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/ArraySentinelSinglyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
index c0aaa11..4101183 100644
--- a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
@@ -29,6 +29,6 @@ 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' -e '/^$/d'
+£>export name=ArraySentinelSinglyLinkedList array=1 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/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
index 1e1b6a7..e1421b7 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_sentinel=0 with_head=1 with_tail=1 with_prev=0
-£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d'
+£>export name=ArraySinglyLinkedList array=1 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/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
index 45f47e8..d2c05d6 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_sentinel=0 with_head=1 with_tail=0 with_prev=1
-£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d'
+£>export name=ArrayTaillessDoublyLinkedList array=1 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/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
index f09be45..09de059 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_sentinel=0 with_head=1 with_tail=0 with_prev=1
-£>$GPP -s £ < src/datastructures/linkedlists/array-template | sed -e '/^[/ ]\*/d' -e '/^$/d'
+£>export name=ArrayTaillessSinglyLinkedList array=1 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/CircularDoublyLinkedList.java b/src/datastructures/linkedlists/CircularDoublyLinkedList.java
index a82c924..327305c 100644
--- a/src/datastructures/linkedlists/CircularDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/CircularDoublyLinkedList.java
@@ -36,6 +36,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=CircularDoublyLinkedList with_sentinel=0 with_head=0 with_tail=0 with_prev=1
+£>export name=CircularDoublyLinkedList array=0 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 cb20386..6ed8dcb 100644
--- a/src/datastructures/linkedlists/CircularSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/CircularSinglyLinkedList.java
@@ -36,6 +36,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=CircularSinglyLinkedList with_sentinel=0 with_head=0 with_tail=0 with_prev=0
+£>export name=CircularSinglyLinkedList array=0 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 5978860..9be4ad8 100644
--- a/src/datastructures/linkedlists/DoublyLinkedList.java
+++ b/src/datastructures/linkedlists/DoublyLinkedList.java
@@ -34,6 +34,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=DoublyLinkedList with_sentinel=0 with_head=1 with_tail=1 with_prev=1
+£>export name=DoublyLinkedList array=0 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 6bb2d91..626234a 100644
--- a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java
@@ -34,6 +34,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=HeadlessDoublyLinkedList with_sentinel=0 with_head=0 with_tail=1 with_prev=1
+£>export name=HeadlessDoublyLinkedList array=0 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 8ee71ee..900ad17 100644
--- a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java
@@ -43,6 +43,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=HeadlessSinglyLinkedList with_sentinel=0 with_head=0 with_tail=1 with_prev=0
+£>export name=HeadlessSinglyLinkedList array=0 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 6da15c5..bb1f1d4 100644
--- a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java
@@ -44,6 +44,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=SentinelDoublyLinkedList with_sentinel=1 with_head=0 with_tail=0 with_prev=1
+£>export name=SentinelDoublyLinkedList array=0 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 66030ba..4af09b7 100644
--- a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java
@@ -43,6 +43,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=SentinelSinglyLinkedList with_sentinel=1 with_head=0 with_tail=0 with_prev=0
+£>export name=SentinelSinglyLinkedList array=0 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 2f40db3..0fc85c6 100644
--- a/src/datastructures/linkedlists/SinglyLinkedList.java
+++ b/src/datastructures/linkedlists/SinglyLinkedList.java
@@ -34,6 +34,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=SinglyLinkedList with_sentinel=0 with_head=1 with_tail=1 with_prev=0
+£>export name=SinglyLinkedList array=0 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 a5bba64..777e060 100644
--- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
@@ -34,6 +34,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=TaillessDoublyLinkedList with_sentinel=0 with_head=1 with_tail=0 with_prev=1
+£>export name=TaillessDoublyLinkedList array=0 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 ceccceb..c7b55db 100644
--- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
@@ -33,6 +33,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=TaillessSinglyLinkedList with_sentinel=0 with_head=1 with_tail=0 with_prev=0
+£>export name=TaillessSinglyLinkedList array=0 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/array-template b/src/datastructures/linkedlists/array-template
deleted file mode 100644
index 177a6cf..0000000
--- a/src/datastructures/linkedlists/array-template
+++ /dev/null
@@ -1,540 +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/>.
- */
-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
-     */
-    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 |= initialCapacity >> 1;
-	    initialCapacity |= initialCapacity >> 2;
-	    initialCapacity |= initialCapacity >> 4;
-	    initialCapacity |= initialCapacity >> 8;
-	    initialCapacity |= 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_sentinel )); then
-    /**
-     * The sentinel node in the list
-     */
-    public int edge;
-£>fi
-    
-£>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
-    
-    
-    
-£>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
-     * 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 |= cap >> 1;
-	    cap |= cap >> 2;
-	    cap |= cap >> 4;
-	    cap |= cap >> 8;
-	    cap |= 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);)
-£>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
-	    {
-		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];
-	}
-	
-£>LAST=EDGE ; BEGINNING=0 ; (( circular )) && { LAST=0; BEGINNING=1; }
-	for (int i = 0; i < size;)
-	    this.next[i] = ++i;
-	this.next[size - 1] = £{LAST};
-	
-£>if (( with_prev )); then
-	for (int i = £{BEGINNING}; i < size; i++)
-	    this.previous[i] = i - 1;
-£>(( circular )) &&
-	this.previous[0] = size - 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_sentinel )) && (( 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 )) || (( with_sentinel )); 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)
-£>if (( with_sentinel )); then
-    {
-	return insertAfter(value, this.edge);
-    }
-£>else
-    {
-	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;
-    }
-£>fi
-    
-    /**
-     * 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()
-£>if (( with_sentinel )); then
-    {
-	return removeAfter(this.edge);
-    }
-£>else
-    {
-	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
-£>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;
-£>(( 1 - with_sentinel )) &&
-	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];
-£>(( 1 - with_sentinel )) &&
-	if (node != EDGE)
-	{
-	    this.next[predecessor] = this.next[node];
-£>if (( with_prev )); then
-£>(( 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;
-£>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;
-£>(( 1 - with_sentinel )) &&
-	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];
-£>(( 1 - with_sentinel )) &&
-	if (node != EDGE)
-	{
-	    this.previous[successor] = this.previous[node];
-£>(( 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;
-£>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)
-    {
-£>(( 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
-	else
-	    this.tail = this.previous[node];
-£>fi
-	unuse(node);
-    }
-£>fi
-    
-    
-£>if (( with_tail )) || (( with_sentinel * with_prev )); 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 (( with_sentinel )); then
-    {
-	return insertBefore(value, this.edge);
-    }
-£>else
-    {
-	if (this.tail == EDGE)
-£>(( with_head )) &&
-	    return insertBeginning(value);
-£>(( with_head )) ||
-	    return this.values[this.tail = getNext()] = value;
-	return insertAfter(value, this.tail);
-    }
-£>fi
-    
-£>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()
-£>if (( with_sentinel )); then
-    {
-	return removeBefore(this.edge);
-    }
-£>else
-    {
-	int node = this.tail;
-	if (node != EDGE)
-	    this.next[this.tail = this.previous[node]] = EDGE;
-	return unuse(node);
-    }
-£>fi
-£>fi
-£>fi
-    
-}
-
diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template
index d207f5a..8cc0470 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -15,8 +15,50 @@
  * 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/>.
  */
+£<
+  EDGE=EDGE ; (( with_sentinel )) && EDGE=edge
+  null=null ; (( array )) && null=EDGE
+  Node=Node ; (( array )) && Node=int
+  
+  circular=0
+  if (( with_sentinel )) || (( (1 - with_head) * (1 - with_tail) )); then
+      circular=1
+  fi
+  
+  function next
+  {
+      (( array )) && echo "this.next[${1}]"
+      (( array )) || echo "${1}.next"
+  }
+  function previous
+  {
+      (( array )) && echo "this.previous[${1}]"
+      (( array )) || echo "${1}.previous"
+  }
+  function free
+  {
+      (( array )) && echo "unuse(${1})"
+      (( array )) || echo "${1}"
+  }
+£>
+£>if (( 1 - array )); then
+£>    function new
+£>    {
+	£{Node} £{1} = new Node(£{2});
+£>    }
+£>else
+£>    function new
+£>    {
+	£{Node} £{1} = getNext();
+	this.values[£{1}] = £{2};
+£>    }
+£>fi
+
+
+
 public class £{name}<T>
 {
+£>if (( 1 - array )); then
     /**
      * Node for the list
      */
@@ -54,79 +96,303 @@ public class £{name}<T>
     }
     
     
+    
+£>else
+    /**
+     * 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
+     */
+    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 |= initialCapacity >> 1;
+	    initialCapacity |= initialCapacity >> 2;
+	    initialCapacity |= initialCapacity >> 4;
+	    initialCapacity |= initialCapacity >> 8;
+	    initialCapacity |= 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;
+    
+    /**
+     * 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
+£>fi
+    
 £>if (( with_sentinel )); then
     /**
      * The sentinel node in the list
      */
-    public Node edge;
+    public £{Node} edge;
+    
+    
+    
+    /**
+     * Initialiser
+     */
+    {
+£>(( array )) ||
+	this.edge = new Node(null);
+£>(( array )) &&
+	this.values[this.edge = getNext()] = null;
+	£(next this.edge) = this.edge;
+£>(( with_prev )) &&
+	£(previous this.edge) = this.edge;
+    }
 £>fi
     
 £>if (( with_head )); then
     /**
      * The first node in the list
      */
-    public Node head = null;
+    public £{Node} head = £{null};
 £>fi
     
 £>if (( with_tail )); then
     /**
      * The last node in the list
      */
-    public Node tail = null;
+    public £{Node} tail = £{null};
 £>fi
     
     
     
-£>if (( with_sentinel )); then
+£>if (( array )); then    
     /**
-     * Initialiser
+     * 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()
     {
-	this.edge = new Node(null);
-	this.edge.next = this.edge;
+	int size = this.end - reuseHead;
+	int cap = size;
+	if ((cap & cap - 1) != 0)
+	{
+	    cap |= cap >> 1;
+	    cap |= cap >> 2;
+	    cap |= cap >> 4;
+	    cap |= cap >> 8;
+	    cap |= 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);)
+£>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
+	    {
+		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.edge.previous = this.edge;
+	    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] = £{LAST};
+	
+£>if (( with_prev )); then
+	for (int i = £{BEGINNING}; i < size; i++)
+	    this.previous[i] = i - 1;
+£>(( circular )) &&
+	this.previous[0] = size - 1;
+£>fi
+	
+	this.values = vals;
+	this.end = size;
+	this.reuseHead = 0;
+£>(( with_head )) &&
+	this.head = 0;
+£>(( with_tail )) &&
+	this.tail = this.end - 1;
     }
     
-£>elif (( 1 - with_head )) && (( 1 - with_tail )); then
+    
+    /**
+     * 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;
+    }
+£>fi
+    
+    
+    
+£>if (( 1 - with_sentinel )) && (( 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 Node create(T value)
+    public £{Node} create(T value)
     {
-	Node node = new Node(value);
+£>new node value
 £>(( with_prev )) &&
-	node.previous = node;
-	return node.next = node;
+	£(previous node) = node;
+	return £(next node) = node;
     }
 £>fi
     
     
-£>if (( with_head )); then
+£>if (( with_head )) || (( with_sentinel )); then
     /**
      * 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)
+    public £{Node} insertBeginning(T value)
 £>if (( with_sentinel )); then
     {
 	return insertAfter(value, this.edge);
     }
 £>else
     {
-	Node node = new Node(value);
-	node.next = this.head;
+£>new node value
+	£(next node) = this.head;
 £>if (( with_prev )); then
-	if (node.next != null)
-	    node.next.previous = node;
+	if (£(next node) != £{null})
+	    £(previous "$(next node)") = node;
 £>fi
 £>if (( with_tail )); then
-	if (this.head == null)
+	if (this.head == £{null})
 	    this.tail = node;
 £>fi
 	this.head = node;
@@ -139,29 +405,30 @@ public class £{name}<T>
      * 
      * @return  The node that has been removed
      */
-    public Node removeBeginning()
+    public £{Node} removeBeginning()
 £>if (( with_sentinel )); then
     {
 	return removeAfter(this.edge);
     }
 £>else
     {
-	Node node = this.head;
-	if (node != null)
-	    this.head = this.head.next;
+	£{Node} node = this.head;
+	if (node != £{null})
+	    this.head = £(next this.head);
 £>if (( with_prev )); then
-	if (this.head != null)
-	    this.head.previous = null;
+	if (this.head != £{null})
+	    £(previous this.head) = £{null};
 £>fi
 £>if (( with_tail )); then
 	if (this.tail == node)
-	    this.tail = null;
+	    this.tail = £{null};
 £>fi
-	return node;
+	return £(free node);
     }
 £>fi
 £>fi
     
+    
     /**
      * Insert a value after a specified, reference, node
      * 
@@ -169,16 +436,16 @@ public class £{name}<T>
      * @param   predecessor  The reference node
      * @return               The node that has been created and inserted
      */
-    public Node insertAfter(T value, Node predecessor)
+    public £{Node} insertAfter(T value, £{Node} predecessor)
     {
-	Node node = new Node(value);
-	node.next = predecessor.next;
-	predecessor.next = node;
+£>new node value
+	£(next node) = £(next predecessor);
+	£(next predecessor) = node;
 £>if (( with_prev )); then
-	node.previous = predecessor;
+	£(previous node) = predecessor;
 £>(( with_sentinel )) ||
-	if (node.next != null)
-	    node.next.previous = node;
+	if (£(next node) != £{null})
+	    £(previous "$(next node)") = node;
 £>fi
 £>if (( with_tail )); then
 	if (this.tail == predecessor)
@@ -193,26 +460,27 @@ public class £{name}<T>
      * @param   predecessor  The reference node
      * @return               The node that has been removed
      */
-    public Node removeAfter(Node predecessor)
+    public £{Node} removeAfter(£{Node} predecessor)
     {
-	Node node = predecessor.next;
+	£{Node} node = £(next predecessor);
 £>(( with_sentinel )) ||
-	if (node != null)
+	if (node != £{null})
 	{
-	    predecessor.next = node.next;
+	    £(next predecessor) = £(next node);
 £>if (( with_prev )); then
 £>(( with_sentinel )) ||
-	    if (node.next != null)
-		node.next.previous = predecessor;
+	    if (£(next node) != £{null})
+		£(previous "$(next node)") = predecessor;
 £>fi
 £>if (( with_tail )); then
 	    if (this.tail == node)
 		this.tail = predecessor;
 £>fi
 	}
-	return node;
+	return £(free node);
     }
     
+    
 £>if (( with_prev )); then
     /**
      * Insert a value before a specified, reference, node
@@ -221,15 +489,15 @@ public class £{name}<T>
      * @param   successor  The reference node
      * @return             The node that has been created and inserted
      */
-    public Node insertBefore(T value, Node successor)
+    public £{Node} insertBefore(T value, £{Node} successor)
     {
-	Node node = new Node(value);
-	node.previous = successor.previous;
-	successor.previous = node;
-	node.next = successor;
+£>new node value
+	£(previous node) = £(previous successor);
+	£(previous successor) = node;
+	£(next node) = successor;
 £>(( with_sentinel )) ||
-	if (node.previous != null)
-	    node.previous.next = node;
+	if (£(previous node) != £{null})
+	    £(next "$(previous node)") = node;
 £>if (( with_head )); then
 	if (this.head == successor)
 	    this.head = node;
@@ -243,88 +511,95 @@ public class £{name}<T>
      * @param   successor  The reference node
      * @return             The node that has been removed
      */
-    public Node removeBefore(Node successor)
+    public £{Node} removeBefore(£{Node} successor)
     {
-	Node node = successor.previous;
+	£{Node} node = £(previous successor);
 £>(( with_sentinel )) ||
-	if (node != null)
+	if (node != £{null})
 	{
-	    successor.previous = node.previous;
+	    £(previous successor) = £(previous node);
 £>(( with_sentinel )) ||
-	    if (node.previous != null)
-		node.previous.next = successor;
+	    if (£(previous node) != £{null})
+		£(next "$(previous node)") = successor;
 £>if (( with_head )); then
 	    if (this.head == node)
 		this.head = successor;
 £>fi
 	}
-	return node;
+	return £(free node);
     }
     
+    
     /**
      * Remove the node from the list
      * 
      * @param  node  The node to remove
      */
-    public void remove(Node node)
+    public void remove(£{Node} node)
     {
 £>(( with_sentinel )) ||
-	if (node.previous != null)
-	    node.previous.next = node.next;
+	if (£(previous node) != £{null})
+	    £(next "$(previous node)") = £(next node);
 £>if (( with_head )); then
 	else
-	    this.head = node.next;
+	    this.head = £(next node);
 £>fi
+	
 £>(( with_sentinel )) ||
-	if (node.next != null)
-	    node.next.previous = node.previous;
+	if (£(next node) != £{null})
+	    £(previous "$(next node)") = £(previous node);
 £>if (( with_tail )); then
 	else
-	    this.tail = node.previous;
+	    this.tail = £(previous node);
 £>fi
+£>(( array )) &&
+	unuse(node);
     }
 £>fi
     
-£>if (( with_tail )); then
+    
+£>if (( with_tail )) || (( with_sentinel * with_prev )); then
     /**
      * 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)
+    public £{Node} insertEnd(T value)
 £>if (( with_sentinel )); then
     {
 	return insertBefore(value, this.edge);
     }
 £>else
     {
-	if (this.tail == null)
+	if (this.tail == £{null})
 £>(( with_head )) &&
 	    return insertBeginning(value);
-£>(( with_head )) ||
-	    return this.tail = new Node(value);
+£>(( 1 - with_head )) && (( 1 - array )) &&
+	    return this.tail = new £{Node}(value);
+£>(( 1 - with_head )) && (( array )) &&
+	    return this.values[this.tail = getNext()] = value;
 	return insertAfter(value, this.tail);
     }
 £>fi
-
+    
 £>if (( with_prev )); then
     /**
      * Remove the node at the end of the list
      * 
      * @return  The node that has been removed
      */
-    public Node removeEnd()
+    public £{Node} removeEnd()
 £>if (( with_sentinel )); then
     {
 	return removeBefore(this.edge);
     }
 £>else
     {
-	Node node = this.tail;
-	if (node != null)
-	    (this.tail = node.previous).next = null;
-	return node;
+	£{Node} node = this.tail;
+	if (node != £{null})
+	    £(next "(this.tail = $(previous node))") = £{null};
+	return £(free node);
     }
 £>fi
 £>fi