aboutsummaryrefslogtreecommitdiffstats
path: root/src/datastructures
diff options
context:
space:
mode:
authorMattias Andrée <maandree@operamail.com>2014-10-12 03:39:31 +0200
committerMattias Andrée <maandree@operamail.com>2014-10-12 03:39:31 +0200
commitb4489e38bff16c4f6ce9ef186f2feed80644fa32 (patch)
tree5d1bd6983d6231160841b8bae07ab2a51bc5321b /src/datastructures
parentnote on performance (diff)
downloadalgorithms-and-data-structures-b4489e38bff16c4f6ce9ef186f2feed80644fa32.tar.gz
algorithms-and-data-structures-b4489e38bff16c4f6ce9ef186f2feed80644fa32.tar.bz2
algorithms-and-data-structures-b4489e38bff16c4f6ce9ef186f2feed80644fa32.tar.xz
fix errors and start on a performance test
Signed-off-by: Mattias Andrée <maandree@operamail.com>
Diffstat (limited to 'src/datastructures')
-rw-r--r--src/datastructures/PerformanceTest.java95
-rw-r--r--src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArrayDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArraySinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/CircularDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/CircularSinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/DoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/HeadlessDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/HeadlessSinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/SentinelDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/SentinelSinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/SinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/TaillessDoublyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/TaillessSinglyLinkedList.java1
-rw-r--r--src/datastructures/linkedlists/template63
23 files changed, 162 insertions, 17 deletions
diff --git a/src/datastructures/PerformanceTest.java b/src/datastructures/PerformanceTest.java
new file mode 100644
index 0000000..b771aad
--- /dev/null
+++ b/src/datastructures/PerformanceTest.java
@@ -0,0 +1,95 @@
+/**
+ * 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;
+import datastructures.linkedlists.*;
+
+import java.util.Random;
+
+
+/**
+ * This program be used to test the performance of
+ * some datastructures
+ */
+public class PerformanceTest
+{
+ /**
+ * This is the main entry point of the test
+ *
+ * @param args Command line arguments
+ */
+ public static void main(final String... args)
+ {
+ int numElements, maxElements = 1 << 23;
+ Random rng = new Random();
+
+ for (numElements = 1; numElements <= maxElements; numElements <<= 1)
+ {
+ long time, subtime;
+ Integer[] elements = new Integer[numElements];
+ System.out.println("Using " + numElements + " random elements.");
+ for (int i = 0; i < numElements; i++)
+ elements[i] = Integer.valueOf(rng.nextInt());
+
+ ArrayDoublyLinkedList<Integer> arrayDoublyLinkedList =
+ new ArrayDoublyLinkedList<Integer>(Integer.class);
+ DoublyLinkedList<Integer> doublyLinkedList =
+ new DoublyLinkedList<Integer>(Integer.class);
+ ArraySinglyLinkedList<Integer> arraySinglyLinkedList =
+ new ArraySinglyLinkedList<Integer>(Integer.class);
+ SinglyLinkedList<Integer> singlyLinkedList =
+ new SinglyLinkedList<Integer>(Integer.class);
+ ArraySentinelDoublyLinkedList<Integer> arraySentinelDoublyLinkedList =
+ new ArraySentinelDoublyLinkedList<Integer>(Integer.class);
+ SentinelDoublyLinkedList<Integer> sentinelDoublyLinkedList =
+ new SentinelDoublyLinkedList<Integer>(Integer.class);
+ ArraySentinelSinglyLinkedList<Integer> arraySentinelSinglyLinkedList =
+ new ArraySentinelSinglyLinkedList<Integer>(Integer.class);
+ SentinelSinglyLinkedList<Integer> sentinelSinglyLinkedList =
+ new SentinelSinglyLinkedList<Integer>(Integer.class);
+
+ System.out.println();
+ System.out.println("Insert at beginning:");
+
+£<for class in {Array,}{Sentinel,}{Doubly,Singly}LinkedList; do
+ list_a=${class::1}
+ list_b=${class:1}
+£>list=${list_a,,}${list_b}
+ System.gc();
+ try
+ {
+ Thread.sleep(100);
+ } catch(InterruptedException e) {}
+ time = 0;
+ for (int i = 0; i < numElements; i++)
+ {
+ subtime = System.nanoTime();
+ £{list}.insertBeginning(elements[i]);
+ time += System.nanoTime() - subtime;
+ }
+ time /= numElements;
+ System.out.printf("%30s: %7d.%03d µs/element\n", "£{class}",
+ time / 1000, time % 1000);
+ £{list} = null;
+£>done
+
+ System.out.println();
+ System.out.println();
+ }
+ }
+
+}
+
diff --git a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
index a77de10..cb2c1b6 100644
--- a/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayCircularDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
index b67eb69..bc5e2e8 100644
--- a/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayCircularSinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java
index 862433b..d29d39b 100644
--- a/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayCircularXORDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
index 4a1df1d..182787f 100644
--- a/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
index 0b357f5..93b9abd 100644
--- a/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySentinelDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
index aab6b2f..79822ea 100644
--- a/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySentinelSinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArraySinglyLinkedList.java b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
index 635bf83..efe69c0 100644
--- a/src/datastructures/linkedlists/ArraySinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArraySinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
index 24b9740..3c41d56 100644
--- a/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayTaillessDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
index 20e71c0..06f9210 100644
--- a/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayTaillessSinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java
index 6984c19..c530ca2 100644
--- a/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayTaillessXORDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java
index a06302d..3b4bb40 100644
--- a/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/ArrayXORDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/CircularDoublyLinkedList.java b/src/datastructures/linkedlists/CircularDoublyLinkedList.java
index 21e7a48..63997e2 100644
--- a/src/datastructures/linkedlists/CircularDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/CircularDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/CircularSinglyLinkedList.java b/src/datastructures/linkedlists/CircularSinglyLinkedList.java
index df60349..08f2754 100644
--- a/src/datastructures/linkedlists/CircularSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/CircularSinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/DoublyLinkedList.java b/src/datastructures/linkedlists/DoublyLinkedList.java
index 699ea12..fc0eeb0 100644
--- a/src/datastructures/linkedlists/DoublyLinkedList.java
+++ b/src/datastructures/linkedlists/DoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java
index 636e12a..444e7b3 100644
--- a/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/HeadlessDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java
index 43c006c..821439c 100644
--- a/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/HeadlessSinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java
index d13c676..c448c52 100644
--- a/src/datastructures/linkedlists/SentinelDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/SentinelDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java
index 7ee3512..2bef187 100644
--- a/src/datastructures/linkedlists/SentinelSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/SentinelSinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/SinglyLinkedList.java b/src/datastructures/linkedlists/SinglyLinkedList.java
index acbc55b..8e9e1d3 100644
--- a/src/datastructures/linkedlists/SinglyLinkedList.java
+++ b/src/datastructures/linkedlists/SinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
index ea88413..b58599f 100644
--- a/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
+++ b/src/datastructures/linkedlists/TaillessDoublyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
index 7cf113f..106decd 100644
--- a/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
+++ b/src/datastructures/linkedlists/TaillessSinglyLinkedList.java
@@ -15,6 +15,7 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package datastructures.linkedlists;
+import java.lang.reflect.Array;
/**
diff --git a/src/datastructures/linkedlists/template b/src/datastructures/linkedlists/template
index 53a7c4a..b225457 100644
--- a/src/datastructures/linkedlists/template
+++ b/src/datastructures/linkedlists/template
@@ -120,6 +120,21 @@ public class £{name}<T>
}
+ /**
+ * Constructor
+ */
+ public £{name}(Class<T> tClass)
+ {
+ this.tClass = tClass;
+£>if (( with_sentinel )); then
+£>new node null
+ this.edge = node;
+£>for var in $refs; do
+ £($var this.edge) = £(singularity this.edge);
+£>done
+£>fi
+ }
+
£>else
/**
@@ -153,9 +168,10 @@ public class £{name}<T>
/**
* Constructor
*/
- public £{name}()
+ @SuppressWarnings("unchecked")
+ public £{name}(Class<T> tClass)
{
- this(DEFAULT_INITIAL_CAPACITY);
+ this(tClass, DEFAULT_INITIAL_CAPACITY);
}
/**
@@ -164,15 +180,23 @@ public class £{name}<T>
* @param initialCapacity The initial size of the arrays
*/
@SuppressWarnings("unchecked")
- public £{name}(int initialCapacity)
+ public £{name}(Class<T> tClass, int initialCapacity)
{
+ this.tClass = tClass;
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]);
+ this.values = (T[])(Array.newInstance(this.tClass, initialCapacity));
+£>if (( with_sentinel )); then
+£>new node null
+ this.edge = node;
+£>for var in $refs; do
+ £($var this.edge) = £(singularity this.edge);
+£>done
+£>fi
}
@@ -233,22 +257,27 @@ public class £{name}<T>
£>fi
£>fi
+ /**
+ * Java's generics erasure is kind of silly
+ * when it comes to arrays. We can either
+ * create {@code Object[]} and cast it to
+ * {@code T[]} and let the user of the class
+ * cast it back to {@code Object[]}, get an
+ * element and cast it back to {@code T}; or
+ * we can let the user not only specify
+ * {@code <T>} when calling the constructor,
+ * but also add an {@code T.class} argument
+ * and then store that argument so we can
+ * at any time use the class {@link Array}
+ * to create an array.
+ */
+ private Class<T> tClass;
+
£>if (( with_sentinel )); then
/**
* The sentinel node in the list
*/
public £{Node} edge;
-
- /**
- * Initialiser
- */
- {
-£>new node null
- this.edge = node;
-£>for var in $refs; do
- £($var this.edge) = £(singularity this.edge);
-£>done
- }
£>fi
£>if (( with_head )); then
@@ -290,7 +319,7 @@ public class £{name}<T>
£>(( with_xor )) &&
int prev = EDGE;
@SuppressWarnings("unchecked")
- T[] vals = (T[])(new Object[cap]);
+ T[] vals = (T[])(Array.newInstance(this.tClass, cap));
£>if (( 1 - with_head )); then
int head = 0;
while ((head < this.end) && (£($forward head) == UNUSED))
@@ -359,7 +388,7 @@ 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.values, 0, this.values = (T[])(Array.newInstance(this.tClass, 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