code deduplication

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

1 files changed, 0 insertions, 540 deletions

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
-    
-}
-