path: root/src/datastructures/linkedlists/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/>.
 */
£<
  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}]"
      (( array )) || echo "${1}.next"
  }
  function previous
  {
      (( array )) && echo "this.previous[${1}]"
      (( array )) || echo "${1}.previous"
  }
  function free
  {
      (( array )) && echo "unuse(${1})"
      (( array )) || echo "${1}"
  }
£>
£>if (( 1 - array )); then
£>    function new
£>    {
	£{Node} £{1} = new Node(£{2});
£>    }
£>else
£>    function new
£>    {
	£{Node} £{1} = getNext();
	this.values[£{1}] = £{2};
£>    }
£>fi



public class £{name}<T>
{
£>if (( 1 - array )); then
    /**
     * Node for the list
     */
    public class Node
    {
	/**
	 * Constructor
	 * 
	 * @param  value  The value to store in the list
	 */
	public Node(T value)
	{
	    this.value = value;
	}
	
	
	
	/**
	 * The value stored in the list by this node
	 */
	public T value;
	
	/**
	 * The next node in the list
	 */
	public Node next = null;
	
£>if (( with_prev )); then
	/**
	 * The previous node in the list
	 */
	public Node previous = null;
£>fi
	
    }
    
    
    
£>else
    /**
     * 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 = 0xFFFFFFFF;
£>fi
    
    /**
     * Sentinel value indicating that the position is unused
     */
    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.
     */
    
    
    
    /**
     * 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;
£>(( with_xor )) &&
	this.next_previous = new int[initialCapacity];
£>(( with_xor )) ||
	this.next = new int[initialCapacity];
£>(( with_prev )) && (( 1 - with_xor )) &&
	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;
    
    /**
     * The value stored in each node
     */
    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
     * {@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
£>fi
£>fi
    
£>if (( with_sentinel )); then
    /**
     * The sentinel node in the list
     */
    public £{Node} edge;
    
    
    
    /**
     * Initialiser
     */
    {
£>(( array )) ||
	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
    
£>if (( with_head )); then
    /**
     * The first node in the list
     */
    public £{Node} head = £{null};
£>fi
    
£>if (( with_tail )); then
    /**
     * The last node in the list
     */
    public £{Node} tail = £{null};
£>fi
    
    
    
£>if (( array )); then    
    /**
     * 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++;
	}
	
£>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) && (£($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 != £{null};)
£>fi
	    {
		vals[ptr++] = this.values[node];
		node = £($forward node)£{x:+ ^ prev};
	    }
£>(( 1 - with_head )) &&
	}
	
	if (cap != this.capacity)
	{
	    this.reusable = new int[cap];
£>(( 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 ; (( circular )) && LAST=0
	for (int i = 0; i < size;)
	    £($forward i) = ++i;
	£($forward "size - 1") = £{LAST};
	
£>if (( with_prev )); then
	for (int i = 1; i < size; i++)
	    £($backward i) £{x}= i - 1;
£>(( circular )) &&
	£($backward 0) £{x}= size - 1;
£>(( circular )) ||
	£($backward 0) £{x}= EDGE;
£>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);
£>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);
£>fi
	}
	return this.end++;
    }
    
    
    /**
     * Mark a position as unused
     * 
     * @param   node  The position
     * @return        The position
     */
    private int unuse(int node)
    {
	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;
£>fi
	}
	return node;
    }
£>fi
    
    
    
£>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 £{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;
    }
£>fi
    
    
£>if (( with_head )) || (( with_sentinel )); then
    /**
     * Insert a value in the beginning of the list
     * 
     * @param   value  The value to insert
     * @return         The node that has been created and inserted
     */
    public £{Node} insertBeginning(T value)
£>if (( with_sentinel )); then
    {
	return insertAfter(value, this.edge);
    }
£>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;
£>fi
	this.head = node;
	return node;
    }
£>fi
    
    /**
     * Remove the node at the beginning of the list
     * 
     * @return  The node that has been removed
     */
    public £{Node} removeBeginning()
£>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);
£>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};
£>fi
	return £(free node);
    }
£>fi
£>fi
    
    
£>if (( 1 - with_xor )); then
    /**
     * Insert a value after a specified, reference, node
     * 
     * @param   value        The value to insert
     * @param   predecessor  The reference node
     * @return               The node that has been created and inserted
     */
    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;
    }
    
    /**
     * Remove the node after a specified, reference, node
     * 
     * @param   predecessor  The reference node
     * @return               The node that has been removed
     */
    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);
    }
    
    
£>if (( with_prev )); then
    /**
     * Insert a value before a specified, reference, node
     * 
     * @param   value      The value to insert
     * @param   successor  The reference node
     * @return             The node that has been created and inserted
     */
    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;
    }
    
    /**
     * Remove the node before a specified, reference, node
     * 
     * @param   successor  The reference node
     * @return             The node that has been removed
     */
    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);
    }
    
    
    /**
     * Remove the node from the list
     * 
     * @param  node  The node to remove
     */
    public void remove(£{Node} node)
    {
£>(( with_sentinel )) ||
	if (£(previous node) != £{null})
	    £(next "$(previous node)") = £(next node);
£>if (( with_head )); 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);
£>fi
£>(( array )) &&
	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
     * 
     * @param   value  The value to insert
     * @return         The node that has been created and inserted
     */
    public £{Node} insertEnd(T value)
£>if (( with_sentinel )); then
    {
	return insertBefore(value, this.edge);
    }
£>else
    {
	if (this.tail == £{null})
£>(( with_head )) &&
	    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;
	return insertAfter(value, this.tail);
    }
£>fi
£>fi
    
£>if (( with_prev )); then
    /**
     * Remove the node at the end of the list
     * 
     * @return  The node that has been removed
     */
    public £{Node} removeEnd()
£>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;
	}
£>else
	    £(next "(this.tail = $(previous node))") = £{null};
£>fi
	return £(free node);
    }
£>fi
£>fi
£>fi
    
}