xor-linked array linked lists

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

1 files changed, 113 insertions, 24 deletions

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