first pass at ArrayList

2 files changed, 130 insertions, 12 deletions

diff --git a/src/cli/runtime/PerisistentArrayList.cs b/src/cli/runtime/PerisistentArrayList.cs
new file mode 100644
index 00000000..5fe1bc11
--- /dev/null
+++ b/src/cli/runtime/PerisistentArrayList.cs
@@ -0,0 +1,105 @@
+/**

+ *   Copyright (c) Rich Hickey. All rights reserved.

+ *   The use and distribution terms for this software are covered by the

+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)

+ *   which can be found in the file CPL.TXT at the root of this distribution.

+ *   By using this software in any fashion, you are agreeing to be bound by

+ * 	 the terms of this license.

+ *   You must not remove this notice, or any other, from this software.

+ **/

+

+using System;

+using System.Threading;

+using System.Collections;

+

+namespace clojure.lang

+{

+public class PersistentArrayList : PersistentArray{

+

+int _count;

+

+public PersistentArrayList(int initialCapacity) : base(initialCapacity){

+    

+    _count = 0;

+}

+

+PersistentArrayList(Master master,int rev,int baseline, BitArray history, int count):base(master,rev,baseline,history){

+    

+    this._count = count;

+}

+

+PersistentArrayList(int size, Object defaultVal, float loadFactor, int count):base(size, defaultVal, loadFactor) {

+    

+    this._count = count;

+}

+

+override public Object get(int i) {

+    if(i >= _count)

+        throw new IndexOutOfRangeException();

+

+    return base.get(i);

+}

+

+override public IArray set(int i,Object val) {

+    if(i >= _count)

+		throw new IndexOutOfRangeException();

+

+    return (PersistentArrayList) base.set(i, val);

+}

+

+override public int length(){

+    return _count;

+}

+

+public int count(){

+    return _count;

+}

+

+public int capacity(){

+	return data.master.array.Length;

+}

+

+public PersistentArrayList add(Object val) {

+    if(_count == data.master.array.Length) //full

+        {

+        lock(data.master){

+            if(_count == data.master.array.Length) //still full

+                grow();

+            }

+        }

+    PersistentArrayList ret =  (PersistentArrayList) base.set(_count, val);

+    ret._count = _count + 1;

+    return ret;

+}

+

+public PersistentArrayList remove() {

+    if(_count == 0)

+        throw new InvalidOperationException();

+    return new PersistentArrayList(data.master, data.rev, data.baseline, data.history, _count - 1);

+}

+

+

+private void grow() {

+    //must be called inside lock of master

+    if(data.master.next != null) //this master has been trimmed, but this rev is not yet propagated

+        trim();

+

+    Master newMaster = new Master(data.master.array.Length * 2, data.master.defaultVal, data.master.loadFactor);

+    newMaster.rev = data.master.rev;

+    newMaster.load = data.master.load;

+    newMaster.basis = data.master.basis;

+    for(int i=0;i<data.master.array.Length;i++)

+        newMaster.array[i] = data.master.array[i];

+    data.master = newMaster;

+}

+

+override internal PersistentArray create(Master master,int rev,int baseline, BitArray history){

+    return new PersistentArrayList(data.master, rev, baseline, history,_count);

+}

+

+override internal PersistentArray create(int size, Object defaultVal, float loadFactor) {

+    return new PersistentArrayList(size, defaultVal, loadFactor,_count);

+}

+

+}

+}

diff --git a/src/cli/runtime/PersistentArray.cs b/src/cli/runtime/PersistentArray.cs
index 4b83dfea..912e31cc 100644
--- a/src/cli/runtime/PersistentArray.cs
+++ b/src/cli/runtime/PersistentArray.cs
@@ -69,7 +69,7 @@ internal class Master{
 	internal int load;

 	internal readonly int maxLoad;

 	internal readonly float loadFactor;

-    internal readonly int[] basis;

+    internal int[] basis;

     internal volatile Master next;

     

 	internal Master(int size,Object defaultVal, float loadFactor){

@@ -194,7 +194,7 @@ public void Reset()
 	}

 

 internal class Data{

-	internal readonly Master master;

+	internal Master master;

 	internal readonly int rev;

 	internal readonly int baseline;

 	internal readonly BitArray history;

@@ -207,7 +207,7 @@ internal class Data{
 		}	

 	}

 

-volatile Data data;

+internal volatile Data data;

 

 public PersistentArray(int size)

 		: this(size, (Object)null)

@@ -250,11 +250,11 @@ public PersistentArray(IArray init) :this(init.length()) {
 	data.master.load = load;

 }

 

-public int length(){

+virtual public int length(){

 return data.master.array.Length;

 }

 

-public Object get(int i){

+virtual public Object get(int i){

 	Entry e = getEntry(i);

 		if(e != null)

 				return e.val;

@@ -267,7 +267,7 @@ public bool has(int i){
 

 public PersistentArray resize(int newLength)

 	{

-	PersistentArray ret = new PersistentArray(newLength, data.master.defaultVal, data.master.loadFactor);

+	PersistentArray ret = create(newLength, data.master.defaultVal, data.master.loadFactor);

 	for (int i = 0; i < Math.Min(length(), newLength); i++)

 		{

 		Entry e = getEntry(i);

@@ -317,7 +317,7 @@ for (Entry e = (Entry)data.master.array[i]; e != null; e = e.rest())
 	return null;

 }

 

-public IArray set(int i,Object val) {

+virtual public IArray set(int i,Object val) {

 //if (data.master.load >= data.master.maxLoad)

 //		{

 //		isolate();

@@ -334,7 +334,7 @@ public IArray set(int i,Object val) {
 	}

 }

 

-private void trim(){

+protected void trim(){

     //must be called inside lock of master

 	if (data.master.next == null) //this master has never been trimmed

         {

@@ -438,7 +438,7 @@ PersistentArray getSetArray(){
 	//is this a sequential update?

 if (data.master.rev == data.rev)

 		{

-		return new PersistentArray(data.master, ++data.master.rev, data.baseline, data.history);

+		return create(data.master, ++data.master.rev, data.baseline, data.history);

 		}

 	else //gap

 		{

@@ -454,10 +454,21 @@ if (data.master.rev == data.rev)
 			nextHistory = new BitArray(data.rev + 1);

 		for (int i = data.baseline; i <= data.rev; i++)

 			nextHistory.Set(i,true);

-		return new PersistentArray(data.master, nextRev, nextRev, nextHistory);

+		return create(data.master, nextRev, nextRev, nextHistory);

 		}

 }

 

+internal  virtual PersistentArray create(Master master, int rev, int baseline, BitArray history)

+	{

+	return new PersistentArray(data.master, rev, baseline, history);

+	}

+

+internal virtual PersistentArray create(int size, Object defaultVal, float loadFactor)

+	{

+	return new PersistentArray(size, defaultVal, loadFactor);

+	}

+

+

 /*

 [STAThread] 

 static public void Main(String[] args){

@@ -471,12 +482,14 @@ static public void Main(String[] args){
 	int reads = Int32.Parse(args[2]);

 	ArrayList v = ArrayList.Synchronized(new ArrayList(size));

 	//v.setSize(size);

-	IArray p = new PersistentArray(size);

+	//IArray p = new PersistentArray(size);

+	IArray p = new PersistentArrayList(size);

 

 	for(int i = 0; i < size; i++)

 		{

 		v.Add(0);

-		p = p.set(i, 0);

+		//p = p.set(i, 0);

+		p = ((PersistentArrayList)p).add(0);

 		}

 

 	Random rand;