path: root/src/datastructures/linkedlists/array-template

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