/* -*- 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}"
}
refs=""
(( with_xor )) && refs="${refs} next_previous"
(( with_xor )) || { refs="${refs} next" ; (( with_prev )) && refs="${refs} previous" ; }
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)
{
initialCapacity = algorithms.bits.Powers.toPowerOf2(initialCapacity);
this.capacity = initialCapacity;
£>for var in $refs reusable; do
this.£{var} = new int[initialCapacity];
£>done
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
*/
{
£>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
}
£>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 = algorithms.bits.Powers.toPowerOf2(size);
£>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)
{
£>for var in $refs reusable; do
this.£{var} = new int[cap];
£>done
}
£>LAST=EDGE FIRST=EDGE ; (( circular )) && LAST=0 FIRST="size - 1"
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;
£($backward 0) £{x}= £{FIRST};
£>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);
£>for var in $refs reusable; do
System.arraycopy(this.£{var}, 0, this.£{var} = new int[this.capacity], 0, this.end);
£>done
}
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;
£>for var in $refs; do
this.£{var}[node] = UNUSED;
£>done
}
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
}
