diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | src/datastructures/linkedlists/template | 99 |
2 files changed, 32 insertions, 69 deletions
@@ -20,7 +20,7 @@ obj/%.java: src/%.java $(foreach F, $(PP), src/$(F)) env GPP="$(GPP)" $(GPP) -s £ < "$<" > "$@" -$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template +$(OBJ_LINKED_LISTS): src/datastructures/linkedlists/template obj/algorithms/bits/Powers.class obj/algorithms/searching/MultiinterpolationSearch.class: obj/algorithms/searching/InterpolationSearch.class obj/algorithms/searching/MultibinarySearch.class: obj/algorithms/searching/BinarySearch.class diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template index bb20620..2be7d1e 100644 --- a/src/datastructures/linkedlists/template +++ b/src/datastructures/linkedlists/template @@ -45,18 +45,23 @@ (( array )) && echo "unuse(${1})" (( array )) || echo "${1}" } -£> -£>if (( 1 - array )); then -£> function new + + 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 +£< } + else + function new £> { £{Node} £{1} = getNext(); this.values[£{1}] = £{2}; -£> } +£< } £>fi @@ -147,25 +152,12 @@ public class £{name}<T> @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++; - } + initialCapacity = algorithms.bits.Powers.toPowerOf2(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]; +£>for var in $refs reusable; do + this.£{var} = new int[initialCapacity]; +£>done this.values = (T[])(new Object[initialCapacity]); } @@ -233,16 +225,12 @@ public class £{name}<T> */ public £{Node} edge; - - /** * Initialiser */ { -£>(( array )) || - this.edge = new Node(null); -£>(( array )) && - this.values[this.edge = getNext()] = null; +£>new node null + this.edge = mode; £>if (( with_xor )); then £(xor this.edge) = £{mirror}; £>else @@ -284,16 +272,7 @@ public class £{name}<T> 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++; - } + int cap = algorithms.bits.Powers.toPowerOf2(size); £>forward=next ; (( with_xor )) && forward=xor £>backward=previous ; (( with_xor )) && backward=xor @@ -329,16 +308,12 @@ public class £{name}<T> 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]; +£>for var in $refs reusable; do + this.£{var} = new int[cap]; +£>done } -£>LAST=EDGE ; (( circular )) && LAST=0 +£>LAST=EDGE FIRST=EDGE ; (( circular )) && LAST=0 FIRST="size - 1" for (int i = 0; i < size;) £($forward i) = ++i; £($forward "size - 1") = £{LAST}; @@ -346,10 +321,7 @@ public class £{name}<T> £>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; + £($backward 0) £{x}= £{FIRST}; £>fi this.values = vals; @@ -377,15 +349,10 @@ 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); -£>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 + 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++; } @@ -402,13 +369,9 @@ public class £{name}<T> 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 +£>for var in $refs; do + this.£{var}[node] = UNUSED; +£>done } return node; } |