add array linked lists

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

8 files changed, 657 insertions, 1 deletions

diff --git a/Makefile b/Makefile
index 0e85b78..becac32 100644
--- a/Makefile
+++ b/Makefile
@@ -20,7 +20,9 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F))
 	env GPP="$(GPP)" $(GPP) -s £ < "$<" > "$@"
 
 
-$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template src/datastructures/linkedlists/sentinel-template
+$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template
+$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/sentinel-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
new file mode 100644
index 0000000..7e059bd
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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 doubly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. 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=ArrayCircularDoublyLinkedList 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
new file mode 100644
index 0000000..10496d4
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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 singly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. 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=ArrayCircularSinglyLinkedList 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
new file mode 100644
index 0000000..bcc2bc1
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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 doubly linked list class. An array linked list
+ * is a linked list constructed by parallel arrays. 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=ArrayDoublyLinkedList 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/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
new file mode 100644
index 0000000..a4668d1
--- /dev/null
+++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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 singly linked list class. An array linked list
+ * is a linked list constructed by parallel arrays. 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=ArraySinglyLinkedList 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
new file mode 100644
index 0000000..5098bf1
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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 doubly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. 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=ArrayTaillessDoublyLinkedList 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
new file mode 100644
index 0000000..bd27cee
--- /dev/null
+++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
@@ -0,0 +1,31 @@
+/**
+ * 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 singly linked list class. An array
+ * linked list is a linked list constructed by parallel
+ * arrays. 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=ArrayTaillessSinglyLinkedList 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
new file mode 100644
index 0000000..5fce858
--- /dev/null
+++ b/src/datastructures/linkedlists/array-template
@@ -0,0 +1,468 @@
+/* -*- 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>
+{
+    /**
+     * The default initial capacity
+     */
+    private static final int DEFAULT_INITIAL_CAPACITY = 128;
+    
+    /**
+     * Sentinel value indicating that an edge has been reached
+     */
+    public static final int EDGE = -1;
+    
+    /**
+     * 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 >>= 1;
+	    initialCapacity >>= 2;
+	    initialCapacity >>= 4;
+	    initialCapacity >>= 8;
+	    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_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
+    
+    
+    
+    /**
+     * 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 >>= 1;
+	    cap >>= 2;
+	    cap >>= 4;
+	    cap >>= 8;
+	    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);)
+£>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];
+	}
+	
+	for (int i = 0; i < size;)
+	    this.next[i] = ++i;
+	this.next[size - 1] = EDGE;
+	
+£>if (( with_prev )); then
+	for (int i = 0; i < size; i++)
+	    this.previous[i] = i - 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_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 )); 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)
+    {
+	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;
+    }
+    
+    /**
+     * 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()
+    {
+	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
+    
+    
+    /**
+     * 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;
+	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];
+	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;
+£>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;
+	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];
+	if (node == EDGE)
+	    this.previous[successor] = this.previous[node];
+	else 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)
+    {
+	if (this.previous[node] != EDGE)
+	    this.next[this.previous[node]] = this.next[node];
+£>if (( with_head )); then
+	else
+	    this.head = this.next[node];
+£>fi
+	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 )); 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 (this.tail == EDGE)
+£>(( with_head )) &&
+	    return insertBeginning(value);
+£>(( with_head )) ||
+	    return this.values[this.tail = getNext()] = value;
+	return insertAfter(value, this.tail);
+    }
+    
+£>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()
+    {
+	int node = this.tail;
+	if (node != EDGE)
+	    this.next[this.tail = this.previous[node]] = EDGE;
+	return unuse(node);
+    }
+£>fi
+£>fi
+    
+}
+