diff options
Diffstat (limited to 'src/datastructures')
22 files changed, 242 insertions, 42 deletions
diff --git a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java index 22cd43a..a77de10 100644 --- a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java @@ -30,6 +30,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayCircularDoublyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 +£>export name=ArrayCircularDoublyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java index db5d5b8..b67eb69 100644 --- a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java @@ -30,6 +30,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayCircularSinglyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=0 +£>export name=ArrayCircularSinglyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java new file mode 100644 index 0000000..862433b --- /dev/null +++ b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java @@ -0,0 +1,37 @@ +/** + * 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 XOR doubly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. In an XOR doubly linked list each node as a + * reference that is the bitwise exclusive-or or the + * address to both the next and the previous node. In + * this implementation, when a node is removed the value + * stored that that position is not removed before that + * position is reused. Insertion methods have constant + * amortised time complexity, and constant amortised + * memory complexity, removal methods have constant time + * complexity and constant memory complexity. + * + * @param <T> The value stored in the structure + */ +£>export name=ArrayCircularXORDoublyLinkedList array=1 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 with_xor=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' + diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java index a7fc1dd..4a1df1d 100644 --- a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java @@ -29,6 +29,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 +£>export name=ArrayDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java index 97437c9..0b357f5 100644 --- a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java @@ -33,6 +33,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArraySentinelDoublyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=1 +£>export name=ArraySentinelDoublyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java index 2ca034d..aab6b2f 100644 --- a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java @@ -33,6 +33,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArraySentinelSinglyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=0 +£>export name=ArraySentinelSinglyLinkedList array=1 with_sentinel=1 with_head=0 with_tail=0 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java index 7310695..635bf83 100644 --- a/src/datastructures/linkedlists/ArraySinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java @@ -29,6 +29,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArraySinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=0 +£>export name=ArraySinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java index 19cad2e..24b9740 100644 --- a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java @@ -30,6 +30,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayTaillessDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 +£>export name=ArrayTaillessDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java index 7e72881..20e71c0 100644 --- a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java @@ -30,6 +30,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=ArrayTaillessSinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 +£>export name=ArrayTaillessSinglyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java new file mode 100644 index 0000000..6984c19 --- /dev/null +++ b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java @@ -0,0 +1,37 @@ +/** + * 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 XOR doubly linked list class. An array + * linked list is a linked list constructed by parallel + * arrays. In an XOR doubly linked list each node as a + * reference that is the bitwise exclusive-or or the + * address to both the next and the previous node. In this + * implementation, when a node is removed the value stored + * that that position is not removed before that position + * is reused. Insertion methods have constant amortised + * time complexity, and constant amortised memory + * complexity, removal methods have constant time + * complexity and constant memory complexity. + * + * @param <T> The value stored in the structure + */ +£>export name=ArrayTaillessXORDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 with_xor=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' + diff --git a/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java new file mode 100644 index 0000000..a06302d --- /dev/null +++ b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java @@ -0,0 +1,37 @@ +/** + * 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 XOR doubly linked list class. An array linked + * list is a linked list constructed by parallel arrays. + * In an XOR doubly linked list each node as a reference + * that is the bitwise exclusive-or or the address to + * both the next and the previous node. In this + * implementation, when a node is removed the value + * stored that that position is not removed before that + * position is reused. Insertion methods have constant + * amortised time complexity, and constant amortised + * memory complexity, removal methods have constant time + * complexity and constant memory complexity. + * + * @param <T> The value stored in the structure + */ +£>export name=ArrayXORDoublyLinkedList array=1 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 with_xor=1 +£>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' + diff --git a/src/datastructures/linkedlists/CircularDoublyLinkedList.java b/src/datastructures/linkedlists/CircularDoublyLinkedList.java index 327305c..21e7a48 100644 --- a/src/datastructures/linkedlists/CircularDoublyLinkedList.java +++ b/src/datastructures/linkedlists/CircularDoublyLinkedList.java @@ -36,6 +36,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=CircularDoublyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 +£>export name=CircularDoublyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=0 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/CircularSinglyLinkedList.java b/src/datastructures/linkedlists/CircularSinglyLinkedList.java index 6ed8dcb..df60349 100644 --- a/src/datastructures/linkedlists/CircularSinglyLinkedList.java +++ b/src/datastructures/linkedlists/CircularSinglyLinkedList.java @@ -36,6 +36,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=CircularSinglyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=0 with_prev=0 +£>export name=CircularSinglyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=0 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java index 9be4ad8..699ea12 100644 --- a/src/datastructures/linkedlists/DoublyLinkedList.java +++ b/src/datastructures/linkedlists/DoublyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=DoublyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 +£>export name=DoublyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=1 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java index 626234a..636e12a 100644 --- a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=HeadlessDoublyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=1 with_prev=1 +£>export name=HeadlessDoublyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=1 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java index 900ad17..43c006c 100644 --- a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java @@ -43,6 +43,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=HeadlessSinglyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=1 with_prev=0 +£>export name=HeadlessSinglyLinkedList array=0 with_sentinel=0 with_head=0 with_tail=1 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java index bb1f1d4..d13c676 100644 --- a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java @@ -44,6 +44,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=SentinelDoublyLinkedList array=0 with_sentinel=1 with_head=0 with_tail=0 with_prev=1 +£>export name=SentinelDoublyLinkedList array=0 with_sentinel=1 with_head=0 with_tail=0 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java index 4af09b7..7ee3512 100644 --- a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java +++ b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java @@ -43,6 +43,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=SentinelSinglyLinkedList array=0 with_sentinel=1 with_head=0 with_tail=0 with_prev=0 +£>export name=SentinelSinglyLinkedList array=0 with_sentinel=1 with_head=0 with_tail=0 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/SinglyLinkedList.java b/src/datastructures/linkedlists/SinglyLinkedList.java index 0fc85c6..acbc55b 100644 --- a/src/datastructures/linkedlists/SinglyLinkedList.java +++ b/src/datastructures/linkedlists/SinglyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=SinglyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=1 with_prev=0 +£>export name=SinglyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=1 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java index 777e060..ea88413 100644 --- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java @@ -34,6 +34,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=TaillessDoublyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 +£>export name=TaillessDoublyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=0 with_prev=1 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java index c7b55db..7cf113f 100644 --- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java +++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java @@ -33,6 +33,6 @@ package datastructures.linkedlists; * * @param <T> The value stored in the structure */ -£>export name=TaillessSinglyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=0 with_prev=0 +£>export name=TaillessSinglyLinkedList array=0 with_sentinel=0 with_head=1 with_tail=0 with_prev=0 with_xor=0 £>$GPP -s £ < src/datastructures/linkedlists/template | sed -e '/^[/ ]\*/d' -e '/^$/d' diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template index 8cc0470..bb20620 100644 --- a/src/datastructures/linkedlists/template +++ b/src/datastructures/linkedlists/template @@ -19,12 +19,17 @@ 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}]" @@ -107,13 +112,22 @@ public class £{name}<T> /** * Sentinel value indicating that an edge has been reached */ - public static final int EDGE = -1; + public static final int EDGE = 0xFFFFFFFF; £>fi /** * Sentinel value indicating that the position is unused */ - public static final int UNUSED = -2; + 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. + */ @@ -145,8 +159,11 @@ public class £{name}<T> } this.capacity = initialCapacity; +£>(( with_xor )) && + this.next_previous = new int[initialCapacity]; +£>(( with_xor )) || this.next = new int[initialCapacity]; -£>(( with_prev )) && +£>(( with_prev )) && (( 1 - with_xor )) && this.previous = new int[initialCapacity]; this.reusable = new int[initialCapacity]; this.values = (T[])(new Object[initialCapacity]); @@ -180,6 +197,16 @@ public class £{name}<T> */ 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 @@ -187,8 +214,8 @@ public class £{name}<T> * 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 @@ -198,6 +225,7 @@ public class £{name}<T> public int[] previous; £>fi £>fi +£>fi £>if (( with_sentinel )); then /** @@ -215,9 +243,13 @@ public class £{name}<T> 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 @@ -263,42 +295,61 @@ public class £{name}<T> 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) && (this.next[head] == UNUSED)) + 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 != EDGE;) + for (int ptr = 0, node = this.head; node != £{null};) £>fi { vals[ptr++] = this.values[node]; - node = this.next[node]; + node = £($forward node)£{x:+ ^ prev}; } +£>(( 1 - with_head )) && + } if (cap != this.capacity) { this.reusable = new int[cap]; - this.next = new int[cap]; -£>(( with_prev )) && +£>(( 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 ; BEGINNING=0 ; (( circular )) && { LAST=0; BEGINNING=1; } +£>LAST=EDGE ; (( circular )) && LAST=0 for (int i = 0; i < size;) - this.next[i] = ++i; - this.next[size - 1] = £{LAST}; + £($forward i) = ++i; + £($forward "size - 1") = £{LAST}; £>if (( with_prev )); then - for (int i = £{BEGINNING}; i < size; i++) - this.previous[i] = i - 1; + for (int i = 1; i < size; i++) + £($backward i) £{x}= i - 1; £>(( circular )) && - this.previous[0] = size - 1; + £($backward 0) £{x}= size - 1; +£>(( circular )) || + £($backward 0) £{x}= EDGE; £>fi this.values = vals; @@ -326,11 +377,15 @@ public class £{name}<T> 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); + 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); + System.arraycopy(this.previous, 0, this.previous = new int[this.capacity], 0, this.end); +£>fi } return this.end++; } @@ -344,10 +399,17 @@ public class £{name}<T> */ private int unuse(int node) { - this.reusable[reuseHead++] = node; - this.next[node] = UNUSED; + 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; + this.previous[node] = UNUSED; +£>fi + } return node; } £>fi @@ -364,8 +426,11 @@ public class £{name}<T> public £{Node} create(T value) { £>new node value -£>(( with_prev )) && +£>(( with_prev )) && (( 1 - with_xor)) && £(previous node) = node; +£>(( with_xor )) && + return £(xor node) = £{mirror}; +£>(( with_xor )) || return £(next node) = node; } £>fi @@ -386,11 +451,16 @@ public class £{name}<T> £>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; @@ -414,11 +484,19 @@ public class £{name}<T> { £{Node} node = this.head; if (node != £{null}) - this.head = £(next this.head); +£>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}; @@ -429,6 +507,7 @@ public class £{name}<T> £>fi +£>if (( 1 - with_xor )); then /** * Insert a value after a specified, reference, node * @@ -556,9 +635,11 @@ public class £{name}<T> 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 * @@ -582,6 +663,7 @@ public class £{name}<T> return insertAfter(value, this.tail); } £>fi +£>fi £>if (( with_prev )); then /** @@ -598,7 +680,14 @@ public class £{name}<T> { £{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 |