diff options
Diffstat (limited to 'src/datastructures/linkedlists/template')
| -rw-r--r-- | src/datastructures/linkedlists/template | 137 |
1 files changed, 113 insertions, 24 deletions
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 |