fix errors and start on a performance test

Signed-off-by: Mattias Andrée <maandree@operamail.com>

22 files changed, 67 insertions, 17 deletions

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