fix m bugs + code dedup

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

1 files changed, 107 insertions, 138 deletions

diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template
index 48f642a..53a7c4a 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -19,7 +19,7 @@
   EDGE=EDGE ; (( with_sentinel )) && EDGE=edge
   null=null ; (( array )) && null=EDGE
   Node=Node ; (( array )) && Node=int
-  mirror=0
+  mirror=0 with_next=1 with_previous=${with_prev}
   
   circular=0
   if (( with_sentinel )) || (( (1 - with_head) * (1 - with_tail) )); then
@@ -27,23 +27,37 @@
   fi
   
   function xor
-  {
-      echo "this.next_previous[${1}]"
+  {   echo "this.next_previous[${1}]"
+  }
+  function next_previous
+  {   xor "$@"
   }
   function next
-  {
-      (( array )) && echo "this.next[${1}]"
-      (( array )) || echo "${1}.next"
+  {   (( array )) && echo "this.next[${1}]" || echo "${1}.next"
+  }
+  function set-head-next
+  {   (( with_xor )) && echo "$(xor "${1}") = (${2} ^ ${null})" || echo "$(next "${1}") = ${2}"
+  }
+  function get-head-next
+  {   (( with_xor )) && echo "($(xor "${1}") ^ ${null})" || echo "$(next "${1}")"
+  }
+  function set-next
+  {   (( with_xor )) && echo "$(xor "${1}") ^= (${2} ^ ${3})" || echo "$(next "${1}") = ${2}"
   }
   function previous
-  {
-      (( array )) && echo "this.previous[${1}]"
-      (( array )) || echo "${1}.previous"
+  {   (( array )) && echo "this.previous[${1}]" || echo "${1}.previous"
+  }
+  function get-tail-previous
+  {   (( with_xor )) && echo "($(xor "${1}") ^ ${null})" || echo "$(previous "${1}")"
+  }
+  function set-previous
+  {   (( with_xor )) && echo "$(xor "${1}") ^= (${2} ^ ${3})" || echo "$(previous "${1}") = ${2}"
   }
   function free
-  {
-      (( array )) && echo "unuse(${1})"
-      (( array )) || echo "${1}"
+  {   (( array )) && echo "unuse(${1})" || echo "${1}"
+  }
+  function singularity
+  {   (( with_xor )) && echo "${mirror}" || echo "${1}"
   }
   
   refs=""
@@ -231,13 +245,9 @@ public class £{name}<T>
     {
 £>new node null
 	this.edge = node;
-£>if (( with_xor )); then
-	£(xor this.edge) = £{mirror};
-£>else
-	£(next this.edge) = this.edge;
-£>(( with_prev )) &&
-	£(previous this.edge) = this.edge;
-£>fi
+£>for var in $refs; do
+	£($var this.edge) = £(singularity this.edge);
+£>done
     }
 £>fi
     
@@ -389,12 +399,10 @@ public class £{name}<T>
     public £{Node} create(T value)
     {
 £>new node value
-£>(( with_prev )) && (( 1 - with_xor)) &&
-	£(previous node) = node;
-£>(( with_xor )) &&
-	return £(xor node) = £{mirror};
-£>(( with_xor )) ||
-	return £(next node) = node;
+£>for var in $refs; do
+	£($var node) = £(singularity node);
+£>done
+	return node;
     }
 £>fi
     
@@ -407,31 +415,26 @@ public class £{name}<T>
      * @return         The node that has been created and inserted
      */
     public £{Node} insertBeginning(T value)
-£>if (( with_sentinel )); then
     {
+£>if (( with_sentinel )); then
 	return insertAfter(value, this.edge);
-    }
 £>else
-    {
 £>new node value
+	£(set-head-next node this.head);
 £>if (( with_xor )); then
-	£(xor node) = £{null} ^ this.head;
-	£(xor this.head) ^= £{null} ^ node;
-£>else
-	£(next node) = this.head;
-£>if (( with_prev )); then
+	£(set-previous this.head "${null}" node);
+£>elif (( with_prev )); then
 	if (£(next node) != £{null})
 	    £(previous "$(next node)") = node;
 £>fi
-£>fi
 £>if (( with_tail )); then
 	if (this.head == £{null})
 	    this.tail = node;
 £>fi
 	this.head = node;
 	return node;
-    }
 £>fi
+    }
     
     /**
      * Remove the node at the beginning of the list
@@ -439,38 +442,68 @@ public class £{name}<T>
      * @return  The node that has been removed
      */
     public £{Node} removeBeginning()
-£>if (( with_sentinel )); then
     {
+£>if (( with_sentinel )); then
 	return removeAfter(this.edge);
-    }
 £>else
-    {
 	£{Node} node = this.head;
 	if (node != £{null})
-£>if (( with_xor )); then
 	{
-	    this.head = £(xor node) ^ £{null};
-	    if (this.head != £{null})
-		£(xor this.head) ^= £{null} ^ node;
-	}
-£>else
-	    this.head = £(next node);
+	    this.head = £(get-head-next node);
 £>if (( with_prev )); then
-	if (this.head != £{null})
-	    £(previous this.head) = £{null};
-£>fi
+	    if (this.head != £{null})
+		£(set-previous this.head "${null}" node);
 £>fi
 £>if (( with_tail )); then
-	if (this.tail == node)
-	    this.tail = £{null};
+	    if (this.tail == node)
+		this.tail = £{null};
 £>fi
+	}
 	return £(free node);
-    }
 £>fi
+    }
 £>fi
     
     
 £>if (( 1 - with_xor )); then
+£>function insertDirection
+£>{
+£>new node value
+	£(${2} node) = £(next ${1});
+	£(${2} ${1}) = node;
+£>if (( with_${3} )); then
+	£(${3} node) = £{1};
+£>(( with_sentinel )) ||
+	if (£(${2} node) != £{null})
+	    £(${3} "$(${2} node)") = node;
+£>fi
+£>if (( with_${4} )); then
+	if (this.£{4} == £{1})
+	    this.£{4} = node;
+£>fi
+	return node;
+£>}
+
+£>function removeDirection
+£>{
+	£{Node} node = £(${2} ${1});
+£>(( with_sentinel )) ||
+	if (node != £{null})
+	{
+	    £(${2} ${1}) = £(${2} node);
+£>if (( with_${3} )); then
+£>(( with_sentinel )) ||
+	    if (£(${2} node) != £{null})
+		£(${3} "$(${2} node)") = £{1};
+£>fi
+£>if (( with_${4} )); then
+	    if (this.£{4} == node)
+		this.£{4} = £{1};
+£>fi
+	}
+	return £(free node);
+£>}
+
     /**
      * Insert a value after a specified, reference, node
      * 
@@ -480,20 +513,7 @@ public class £{name}<T>
      */
     public £{Node} insertAfter(T value, £{Node} predecessor)
     {
-£>new node value
-	£(next node) = £(next predecessor);
-	£(next predecessor) = node;
-£>if (( with_prev )); then
-	£(previous node) = predecessor;
-£>(( with_sentinel )) ||
-	if (£(next node) != £{null})
-	    £(previous "$(next node)") = node;
-£>fi
-£>if (( with_tail )); then
-	if (this.tail == predecessor)
-	    this.tail = node;
-£>fi
-	return node;
+£>insertDirection predecessor next previous tail
     }
     
     /**
@@ -504,22 +524,7 @@ public class £{name}<T>
      */
     public £{Node} removeAfter(£{Node} predecessor)
     {
-	£{Node} node = £(next predecessor);
-£>(( with_sentinel )) ||
-	if (node != £{null})
-	{
-	    £(next predecessor) = £(next node);
-£>if (( with_prev )); then
-£>(( with_sentinel )) ||
-	    if (£(next node) != £{null})
-		£(previous "$(next node)") = predecessor;
-£>fi
-£>if (( with_tail )); then
-	    if (this.tail == node)
-		this.tail = predecessor;
-£>fi
-	}
-	return £(free node);
+£>removeDirection predecessor next previous tail
     }
     
     
@@ -533,18 +538,7 @@ public class £{name}<T>
      */
     public £{Node} insertBefore(T value, £{Node} successor)
     {
-£>new node value
-	£(previous node) = £(previous successor);
-	£(previous successor) = node;
-	£(next node) = successor;
-£>(( with_sentinel )) ||
-	if (£(previous node) != £{null})
-	    £(next "$(previous node)") = node;
-£>if (( with_head )); then
-	if (this.head == successor)
-	    this.head = node;
-£>fi
-	return node;
+£>insertDirection successor previous next head
     }
     
     /**
@@ -555,20 +549,7 @@ public class £{name}<T>
      */
     public £{Node} removeBefore(£{Node} successor)
     {
-	£{Node} node = £(previous successor);
-£>(( with_sentinel )) ||
-	if (node != £{null})
-	{
-	    £(previous successor) = £(previous node);
-£>(( with_sentinel )) ||
-	    if (£(previous node) != £{null})
-		£(next "$(previous node)") = successor;
-£>if (( with_head )); then
-	    if (this.head == node)
-		this.head = successor;
-£>fi
-	}
-	return £(free node);
+£>removeDirection successor previous next head
     }
     
     
@@ -579,21 +560,15 @@ public class £{name}<T>
      */
     public void remove(£{Node} node)
     {
+£>for x in "previous next head" "next previous tail"; do x=( $x )
 £>(( with_sentinel )) ||
-	if (£(previous node) != £{null})
-	    £(next "$(previous node)") = £(next node);
-£>if (( with_head )); then
+	if (£(${x[0]} node) != £{null})
+	    £(${x[1]} "$(${x[0]} node)") = £(${x[1]} node);
+£>if (( with_${x[2]} )); then
 	else
-	    this.head = £(next node);
-£>fi
-	
-£>(( with_sentinel )) ||
-	if (£(next node) != £{null})
-	    £(previous "$(next node)") = £(previous node);
-£>if (( with_tail )); then
-	else
-	    this.tail = £(previous node);
+	    this.£{x[2]} = £(${x[1]} node);
 £>fi
+£>done
 £>(( array )) &&
 	unuse(node);
     }
@@ -610,22 +585,22 @@ public class £{name}<T>
      * @return         The node that has been created and inserted
      */
     public £{Node} insertEnd(T value)
-£>if (( with_sentinel )); then
     {
+£>if (( with_sentinel )); then
 	return insertBefore(value, this.edge);
-    }
 £>else
-    {
 	if (this.tail == £{null})
-£>(( with_head )) &&
+	{
+£>if (( with_head )); then
 	    return insertBeginning(value);
-£>(( 1 - with_head )) && (( 1 - array )) &&
-	    return this.tail = new £{Node}(value);
-£>(( 1 - with_head )) && (( array )) &&
-	    return this.values[this.tail = getNext()] = value;
+£>else
+£>new node value
+	    return this.tail = node;
+£>fi
+	}
 	return insertAfter(value, this.tail);
-    }
 £>fi
+    }
 £>fi
     
 £>if (( with_prev )); then
@@ -635,25 +610,19 @@ public class £{name}<T>
      * @return  The node that has been removed
      */
     public £{Node} removeEnd()
-£>if (( with_sentinel )); then
     {
+£>if (( with_sentinel )); then
 	return removeBefore(this.edge);
-    }
 £>else
-    {
 	£{Node} node = this.tail;
 	if (node != £{null})
-£>if (( with_xor )); then
 	{
-	    this.tail = £{null} ^ £(xor node);
-	    £(xor this.tail) ^= £{null} ^ node;
+	    this.tail = £(get-tail-previous node);
+	    £(set-next this.tail "${null}" node);
 	}
-£>else
-	    £(next "(this.tail = $(previous node))") = £{null};
-£>fi
 	return £(free node);
-    }
 £>fi
+    }
 £>fi
 £>fi