xor-linked array linked lists

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

22 files changed, 242 insertions, 42 deletions

diff --git a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
index 22cd43a..a77de10 100644
--- a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
@@ -30,6 +30,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArrayCircularDoublyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=1
+£>export name=ArrayCircularDoublyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 with_xor=0
 £>$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 db5d5b8..b67eb69 100644
--- a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
@@ -30,6 +30,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArrayCircularSinglyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=0
+£>export name=ArrayCircularSinglyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=0 with_xor=0
 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d'
 
diff --git a/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java
new file mode 100644
index 0000000..862433b
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java
@@ -0,0 +1,37 @@
+/**
+ * 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 circular XOR doubly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. In an XOR doubly linked list each node as a
+ * reference that is the bitwise exclusive-or or the
+ * address to both the next and the previous node. In
+ * this implementation, when a node is removed the value
+ * stored that that position is not removed before that
+ * position is reused. Insertion methods have constant
+ * amortised time complexity, and constant amortised
+ * memory complexity, removal methods have constant time
+ * complexity and constant memory complexity.
+ * 
+ * @param  <T>  The value stored in the structure
+ */
+£>export name=ArrayCircularXORDoublyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 with_xor=1
+£>$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 a7fc1dd..4a1df1d 100644
--- a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
@@ -29,6 +29,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArrayDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=1
+£>export name=ArrayDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 with_xor=0
 £>$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 97437c9..0b357f5 100644
--- a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
@@ -33,6 +33,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArraySentinelDoublyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=1
+£>export name=ArraySentinelDoublyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=1 with_xor=0
 £>$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 2ca034d..aab6b2f 100644
--- a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
@@ -33,6 +33,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArraySentinelSinglyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=0
+£>export name=ArraySentinelSinglyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=0 with_xor=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 7310695..635bf83 100644
--- a/src/datastructures/linkedlists/ArraySinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
@@ -29,6 +29,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArraySinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=0
+£>export name=ArraySinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=0 with_xor=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 19cad2e..24b9740 100644
--- a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
@@ -30,6 +30,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArrayTaillessDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1
+£>export name=ArrayTaillessDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 with_xor=0
 £>$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 7e72881..20e71c0 100644
--- a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
@@ -30,6 +30,6 @@ package datastructures.linkedlists;
  * 
  * @param  <T>  The value stored in the structure
  */
-£>export name=ArrayTaillessSinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1
+£>export name=ArrayTaillessSinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 with_xor=0
 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d'
 
diff --git a/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java
new file mode 100644
index 0000000..6984c19
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java
@@ -0,0 +1,37 @@
+/**
+ * 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 tailless XOR doubly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. In an XOR doubly linked list each node as a
+ * reference that is the bitwise exclusive-or or the
+ * address to both the next and the previous node. In this
+ * implementation, when a node is removed the value stored
+ * that that position is not removed before that position
+ * is reused. Insertion methods have constant amortised
+ * time complexity, and constant amortised memory
+ * complexity, removal methods have constant time
+ * complexity and constant memory complexity.
+ * 
+ * @param  <T>  The value stored in the structure
+ */
+£>export name=ArrayTaillessXORDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 with_xor=1
+£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d'
+
diff --git a/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java
new file mode 100644
index 0000000..a06302d
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java
@@ -0,0 +1,37 @@
+/**
+ * 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 XOR doubly linked list class. An array linked
+ * list is a linked list constructed by parallel arrays.
+ * In an XOR doubly linked list each node as a reference
+ * that is the bitwise exclusive-or or the address to
+ * both the next and the previous node. In this
+ * implementation, when a node is removed the value
+ * stored that that position is not removed before that
+ * position is reused. Insertion methods have constant
+ * amortised time complexity, and constant amortised
+ * memory complexity, removal methods have constant time
+ * complexity and constant memory complexity.
+ * 
+ * @param  <T>  The value stored in the structure
+ */
+£>export name=ArrayXORDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 with_xor=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 327305c..21e7a48 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 array=0 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 with_xor=0
 £>$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 6ed8dcb..df60349 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 array=0 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 with_xor=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 9be4ad8..699ea12 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 array=0 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 with_xor=0
 £>$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 626234a..636e12a 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 array=0 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 with_xor=0
 £>$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 900ad17..43c006c 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 array=0 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 with_xor=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 bb1f1d4..d13c676 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 array=0 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 with_xor=0
 £>$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 4af09b7..7ee3512 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 array=0 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 with_xor=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 0fc85c6..acbc55b 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 array=0 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 with_xor=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 777e060..ea88413 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 array=0 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 with_xor=0
 £>$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 c7b55db..7cf113f 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 array=0 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 with_xor=0
 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d'
 
diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template
index 8cc0470..bb20620 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -19,12 +19,17 @@
   EDGE=EDGE ; (( with_sentinel )) && EDGE=edge
   null=null ; (( array )) && null=EDGE
   Node=Node ; (( array )) && Node=int
+  mirror=0
   
   circular=0
   if (( with_sentinel )) || (( (1 - with_head) * (1 - with_tail) )); then
       circular=1
   fi
   
+  function xor
+  {
+      echo "this.next_previous[${1}]"
+  }
   function next
   {
       (( array )) && echo "this.next[${1}]"
@@ -107,13 +112,22 @@ public class £{name}<T>
     /**
      * Sentinel value indicating that an edge has been reached
      */
-    public static final int EDGE = -1;
+    public static final int EDGE = 0xFFFFFFFF;
 £>fi
     
     /**
      * Sentinel value indicating that the position is unused
      */
-    public static final int UNUSED = -2;
+    public static final int UNUSED = 0x80000000;
+    
+    /* The values of EDGE and UNUSED are choosen so that
+     * the XOR of two indices (including EDGE) should never
+     * reproduce UNUSED. It can only happen if EDGE is XOR:ed
+     * with 0x7FFFFFFF — the most positive integer — which
+     * not only is an impractically large number of elements
+     * but also if the elements are counted it would add up
+     * to −1.
+     */
     
     
     
@@ -145,8 +159,11 @@ public class £{name}<T>
 	}
 	
 	this.capacity = initialCapacity;
+£>(( with_xor )) &&
+	this.next_previous = new int[initialCapacity];
+£>(( with_xor )) ||
 	this.next = new int[initialCapacity];
-£>(( with_prev )) &&
+£>(( with_prev )) && (( 1 - with_xor )) &&
 	this.previous = new int[initialCapacity];
 	this.reusable = new int[initialCapacity];
 	this.values = (T[])(new Object[initialCapacity]);
@@ -180,6 +197,16 @@ public class £{name}<T>
      */
     public T[] values;
     
+£>if (( with_xor )); then
+    /**
+     * The XOR of the next and previous node for
+     * each node. If it resolves to {@link #£{EDGE}}
+     * there is no next node in that direction. If
+     * the value stored in this array is {@link #UNUSED}
+     * that position is not being used
+     */
+    public int[] next_previous;
+£>else
     /**
      * The next node for each node, {@link #£{EDGE}}
      * if the current node is the last node, and
@@ -187,8 +214,8 @@ public class £{name}<T>
      * 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
@@ -198,6 +225,7 @@ public class £{name}<T>
     public int[] previous;
 £>fi
 £>fi
+£>fi
     
 £>if (( with_sentinel )); then
     /**
@@ -215,9 +243,13 @@ public class £{name}<T>
 	this.edge = new Node(null);
 £>(( array )) &&
 	this.values[this.edge = getNext()] = null;
+£>if (( with_xor )); then
+	£(xor this.edge) = £{mirror};
+£>else
 	£(next this.edge) = this.edge;
 £>(( with_prev )) &&
 	£(previous this.edge) = this.edge;
+£>fi
     }
 £>fi
     
@@ -263,42 +295,61 @@ public class £{name}<T>
 	    cap++;
 	}
 	
+£>forward=next ; (( with_xor )) && forward=xor
+£>backward=previous ; (( with_xor )) && backward=xor
+£>x= ; (( with_xor )) && x=^
+£>(( with_xor )) &&
+	int prev = EDGE;
 	@SuppressWarnings("unchecked")
 	T[] vals = (T[])(new Object[cap]);
 £>if (( 1 - with_head )); then
 	int head = 0;
-	while ((head < this.end) && (this.next[head] == UNUSED))
+	while ((head < this.end) && (£($forward head) == UNUSED))
 	    head++;
 	if (head < this.end)
+	{
+£>if (( with_xor )); then
+	    int tail = prev = head;
+	    while (++tail < this.end)
+		if (£($forward tail) != UNUSED)
+		    prev = tail;
+£>fi
 	    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;)
+	for (int ptr = 0, node = this.head; node != £{null};)
 £>fi
 	    {
 		vals[ptr++] = this.values[node];
-		node = this.next[node];
+		node = £($forward node)£{x:+ ^ prev};
 	    }
+£>(( 1 - with_head )) &&
+	}
 	
 	if (cap != this.capacity)
 	{
 	    this.reusable = new int[cap];
-	    this.next     = new int[cap];
-£>(( with_prev )) &&
+£>(( with_xor )) &&
+	    this.next_previous = new int[cap];
+£>(( with_xor )) ||
+	    this.next = new int[cap];
+£>(( with_prev )) && (( 1 - with_xor )) &&
 	    this.previous = new int[cap];
 	}
 	
-£>LAST=EDGE ; BEGINNING=0 ; (( circular )) && { LAST=0; BEGINNING=1; }
+£>LAST=EDGE ; (( circular )) && LAST=0
 	for (int i = 0; i < size;)
-	    this.next[i] = ++i;
-	this.next[size - 1] = £{LAST};
+	    £($forward i) = ++i;
+	£($forward "size - 1") = £{LAST};
 	
 £>if (( with_prev )); then
-	for (int i = £{BEGINNING}; i < size; i++)
-	    this.previous[i] = i - 1;
+	for (int i = 1; i < size; i++)
+	    £($backward i) £{x}= i - 1;
 £>(( circular )) &&
-	this.previous[0] = size - 1;
+	£($backward 0) £{x}= size - 1;
+£>(( circular )) ||
+	£($backward 0) £{x}= EDGE;
 £>fi
 	
 	this.values = vals;
@@ -326,11 +377,15 @@ public class £{name}<T>
 	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);
+	    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);
+£>if (( with_xor )); then
+	    System.arraycopy(this.next_previous, 0, this.next_previous = new int[this.capacity], 0, this.end);
+£>else
+	    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);
+	    System.arraycopy(this.previous,      0, this.previous      = new int[this.capacity], 0, this.end);
+£>fi
 	}
 	return this.end++;
     }
@@ -344,10 +399,17 @@ public class £{name}<T>
      */
     private int unuse(int node)
     {
-	this.reusable[reuseHead++] = node;
-	this.next[node] = UNUSED;
+	if (node >= 0)
+	{
+	    this.reusable[reuseHead++] = node;
+£>if (( with_xor )); then
+	    this.next_previous[node] = UNUSED;
+£>else
+	    this.next[node] = UNUSED;
 £>(( with_prev )) &&
-	this.previous[node] = UNUSED;
+	    this.previous[node] = UNUSED;
+£>fi
+	}
 	return node;
     }
 £>fi
@@ -364,8 +426,11 @@ public class £{name}<T>
     public £{Node} create(T value)
     {
 £>new node value
-£>(( with_prev )) &&
+£>(( with_prev )) && (( 1 - with_xor)) &&
 	£(previous node) = node;
+£>(( with_xor )) &&
+	return £(xor node) = £{mirror};
+£>(( with_xor )) ||
 	return £(next node) = node;
     }
 £>fi
@@ -386,11 +451,16 @@ public class £{name}<T>
 £>else
     {
 £>new node value
+£>if (( with_xor )); then
+	£(xor node) = £{null} ^ this.head;
+	£(xor this.head) ^= £{null} ^ node;
+£>else
 	£(next node) = this.head;
 £>if (( with_prev )); then
 	if (£(next node) != £{null})
 	    £(previous "$(next node)") = node;
 £>fi
+£>fi
 £>if (( with_tail )); then
 	if (this.head == £{null})
 	    this.tail = node;
@@ -414,11 +484,19 @@ public class £{name}<T>
     {
 	£{Node} node = this.head;
 	if (node != £{null})
-	    this.head = £(next this.head);
+£>if (( with_xor )); then
+	{
+	    this.head = £(xor node) ^ £{null};
+	    if (this.head != £{null})
+		£(xor this.head) ^= £{null} ^ node;
+	}
+£>else
+	    this.head = £(next node);
 £>if (( with_prev )); then
 	if (this.head != £{null})
 	    £(previous this.head) = £{null};
 £>fi
+£>fi
 £>if (( with_tail )); then
 	if (this.tail == node)
 	    this.tail = £{null};
@@ -429,6 +507,7 @@ public class £{name}<T>
 £>fi
     
     
+£>if (( 1 - with_xor )); then
     /**
      * Insert a value after a specified, reference, node
      * 
@@ -556,9 +635,11 @@ public class £{name}<T>
 	unuse(node);
     }
 £>fi
+£>fi
     
     
 £>if (( with_tail )) || (( with_sentinel * with_prev )); then
+£>if (( 1 - with_xor )); then
     /**
      * Insert a value in the end of the list
      * 
@@ -582,6 +663,7 @@ public class £{name}<T>
 	return insertAfter(value, this.tail);
     }
 £>fi
+£>fi
     
 £>if (( with_prev )); then
     /**
@@ -598,7 +680,14 @@ public class £{name}<T>
     {
 	£{Node} node = this.tail;
 	if (node != £{null})
+£>if (( with_xor )); then
+	{
+	    this.tail = £{null} ^ £(xor node);
+	    £(xor this.tail) ^= £{null} ^ node;
+	}
+£>else
 	    £(next "(this.tail = $(previous node))") = £{null};
+£>fi
 	return £(free node);
     }
 £>fi