diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/cli/runtime/PersistentArray.cs | 40 | ||||
| -rw-r--r-- | src/cli/runtime/PersistentQueue.cs | 186 | ||||
| -rw-r--r-- | src/cli/runtime/RT.cs | 2 | ||||
| -rw-r--r-- | src/jvm/clojure/lang/PersistentArray.java | 38 | ||||
| -rw-r--r-- | src/jvm/clojure/lang/PersistentQueue.java | 225 |
5 files changed, 361 insertions, 130 deletions
diff --git a/src/cli/runtime/PersistentArray.cs b/src/cli/runtime/PersistentArray.cs index 3c766661..ced36518 100644 --- a/src/cli/runtime/PersistentArray.cs +++ b/src/cli/runtime/PersistentArray.cs @@ -63,7 +63,12 @@ namespace clojure.lang return null;
}
-
+ public ISeq rseq()
+ {
+ if (count() > 0)
+ return new RSeq(this, count() - 1);
+ return null;
+ }
internal class Master{
internal readonly Entry[] array;
@@ -154,6 +159,10 @@ internal class Seq : ASeq, IndexedSeq{ return null;
}
+ public override int count() {
+ return p.count() - i;
+ }
+
#region IndexedSeq Members
public int index()
@@ -164,6 +173,33 @@ public int index() #endregion
}
+class RSeq : ASeq, IndexedSeq{
+ readonly PersistentArray p;
+ readonly int i;
+
+ internal RSeq(PersistentArray p, int i){
+ this.p = p;
+ this.i = i;
+ }
+
+ public override Object first() {
+ return p.nth(i);
+ }
+
+ public override ISeq rest() {
+ if(i > 0)
+ return new RSeq(p, i - 1);
+ return null;
+ }
+
+ public int index() {
+ return i;
+ }
+
+ public override int count() {
+ return i + 1;
+ }
+}
internal class ValIter : IEnumerator
{
internal PersistentArray p;
@@ -491,7 +527,7 @@ internal virtual PersistentArray create(int size, Object defaultVal, float loadF }
-//*
+/*
[STAThread]
static public void Main(String[] args){
if(args.Length != 3)
diff --git a/src/cli/runtime/PersistentQueue.cs b/src/cli/runtime/PersistentQueue.cs new file mode 100644 index 00000000..3069dfd1 --- /dev/null +++ b/src/cli/runtime/PersistentQueue.cs @@ -0,0 +1,186 @@ +/**
+ * 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.Collections;
+
+namespace clojure.lang
+ {
+
+/**
+ * conses onto rear, peeks/pops from front
+ * See Okasaki's Batched Queues
+ * This differs in that it uses a PersistentArrayList as the rear, which is in-order,
+ * so no reversing or suspensions required for persistent use
+ */
+
+public class PersistentQueue : Obj, IPersistentList {
+
+readonly public static PersistentQueue EMPTY = new PersistentQueue(null,null);
+
+readonly ISeq f;
+readonly PersistentArrayList r;
+static readonly int INITIAL_REAR_SIZE = 4;
+
+
+PersistentQueue(ISeq f, PersistentArrayList r) {
+ this.f = f;
+ this.r = r;
+}
+
+public Object peek() {
+ return RT.first(f);
+}
+
+public IPersistentList pop() {
+ if(f == null) //hmmm... pop of empty queue -> empty queue?
+ return this;
+ //throw new IllegalStateException("popping empty queue");
+ ISeq f1 = f.rest();
+ PersistentArrayList r1 = r;
+ if(f1 == null)
+ {
+ f1 = RT.seq(r);
+ r1 = null;
+ }
+ PersistentQueue ret = new PersistentQueue(f1, r1);
+ ret._meta = _meta;
+ return ret;
+}
+
+public int count() {
+ return RT.count(f) + RT.count(r);
+}
+
+public ISeq seq() {
+ if(f == null)
+ return null;
+ return new Seq(f, RT.seq(r));
+}
+
+public IPersistentCollection cons(Object o) {
+ PersistentQueue ret;
+ if(f == null) //empty
+ ret = new PersistentQueue(RT.list(o), null);
+ else
+ ret= new PersistentQueue(f,
+ (PersistentArrayList) (r != null ? r : new PersistentArrayList(INITIAL_REAR_SIZE)).cons(o));
+ ret._meta = _meta;
+ return ret;
+}
+
+public override Obj withMeta(IPersistentMap meta)
+ {
+ if(_meta == meta)
+ return this;
+ Obj ret = (Obj)MemberwiseClone();
+ ret._meta = meta;
+ return ret;
+ }
+
+class Seq : ASeq {
+ readonly ISeq f;
+ readonly ISeq rseq;
+
+ internal Seq(ISeq f, ISeq rseq) {
+ this.f = f;
+ this.rseq = rseq;
+ }
+
+ public override Object first() {
+ return f.first();
+ }
+
+ public override ISeq rest() {
+ ISeq f1 = f.rest();
+ ISeq r1 = rseq;
+ if (f1 == null)
+ {
+ if (rseq == null)
+ return null;
+ f1 = rseq;
+ r1 = null;
+ }
+ return new Seq(f1, r1);
+ }
+}
+
+/*
+public static void Main(String[] args) {
+ if (args.Length != 1)
+ {
+ Console.Error.WriteLine("Usage: PersistentQueue n");
+ return;
+ }
+ int n = Int32.Parse(args[0]);
+
+
+ Random rand;
+
+ rand = new Random(42);
+
+ DateTime startTime;
+ TimeSpan estimatedTime;
+
+ //Queue list = new LinkedList();
+ Queue list = Queue.Synchronized(new Queue());
+ Console.WriteLine("Queue");
+ startTime = DateTime.Now;
+ for (int i = 0; i < n; i++)
+ {
+ list.Enqueue(i);
+ list.Enqueue(i);
+ list.Dequeue();
+ }
+ for (int i = 0; i < n - 10; i++)
+ {
+ list.Dequeue();
+ }
+ estimatedTime = DateTime.Now - startTime;
+ Console.WriteLine("time: " + estimatedTime.Ticks / 10000);
+ Console.WriteLine("peek: " + list.Peek());
+
+
+ PersistentQueue q = PersistentQueue.EMPTY;
+ Console.WriteLine("PersistentQueue");
+ startTime = DateTime.Now;
+ for (int i = 0; i < n; i++)
+ {
+ q = (PersistentQueue) q.cons(i);
+ q = (PersistentQueue) q.cons(i);
+ q = (PersistentQueue) q.pop();
+ }
+ IPersistentList lastq = null;
+ IPersistentList lastq2;
+ for (int i = 0; i < n - 10; i++)
+ {
+ //lastq2 = lastq;
+ //lastq = q;
+ q = (PersistentQueue) q.pop();
+ }
+ estimatedTime = DateTime.Now - startTime;
+ Console.WriteLine("time: " + estimatedTime.Ticks / 10000);
+ Console.WriteLine("peek: " + q.peek());
+
+ IPersistentList q2 = q;
+ for (int i = 0; i < 10; i++)
+ {
+ q2 = (IPersistentList) q2.cons(i);
+ }
+// for(ISeq s = q.seq();s != null;s = s.rest())
+// Console.WriteLine("q: " + s.first());
+// for(ISeq s = q2.seq();s != null;s = s.rest())
+// Console.WriteLine("q2: " + s.first());
+}
+//*/
+
+}
+
+ }
diff --git a/src/cli/runtime/RT.cs b/src/cli/runtime/RT.cs index 7b814154..2dfb46b9 100644 --- a/src/cli/runtime/RT.cs +++ b/src/cli/runtime/RT.cs @@ -328,7 +328,7 @@ static public ISeq list() static public ISeq list(Object arg1)
{
- return cons(arg1, null);
+ return new PersistentList(arg1);
}
static public ISeq list(Object arg1, Object arg2)
diff --git a/src/jvm/clojure/lang/PersistentArray.java b/src/jvm/clojure/lang/PersistentArray.java index a0112abf..1ef6ab7c 100644 --- a/src/jvm/clojure/lang/PersistentArray.java +++ b/src/jvm/clojure/lang/PersistentArray.java @@ -58,7 +58,11 @@ public ISeq seq() { return null; } - +public ISeq rseq() { + if(count() > 0) + return new RSeq(this, count()-1); + return null; +} static class Master{ final Entry[] array; @@ -149,6 +153,38 @@ static class Seq extends ASeq implements IndexedSeq{ public int index() { return i; } + + public int count() { + return p.count() - i; + } +} + +static class RSeq extends ASeq implements IndexedSeq{ + final PersistentArray p; + final int i; + + RSeq(PersistentArray p, int i){ + this.p = p; + this.i = i; + } + + public Object first() { + return p.nth(i); + } + + public ISeq rest() { + if(i > 0) + return new RSeq(p, i - 1); + return null; + } + + public int index() { + return i; + } + + public int count() { + return i + 1; + } } static class ValIter implements Iterator{ diff --git a/src/jvm/clojure/lang/PersistentQueue.java b/src/jvm/clojure/lang/PersistentQueue.java index 299ea176..4ba29e7d 100644 --- a/src/jvm/clojure/lang/PersistentQueue.java +++ b/src/jvm/clojure/lang/PersistentQueue.java @@ -10,54 +10,29 @@ package clojure.lang;
-import java.util.Random;
-import java.util.LinkedList;
import java.util.Queue;
+import java.util.LinkedList;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
* conses onto rear, peeks/pops from front
- * See Okasaki's Bootstrapped Queue
+ * See Okasaki's Batched Queues
+ * This differs in that it uses a PersistentArrayList as the rear, which is in-order,
+ * so no reversing or suspensions required for persistent use
*/
-public class PersistentQueue implements IPersistentList {
-
-static class Empty implements IPersistentList{
+public class PersistentQueue extends Obj implements IPersistentList {
- public Object peek() {
- return null;
- }
-
- public IPersistentList pop() {
- throw new IllegalStateException("popping empty queue");
- }
-
- public int count() {
- return 0;
- }
+final public static PersistentQueue EMPTY = new PersistentQueue(null,null);
- public ISeq seq() {
- return null;
- }
-
- public IPersistentCollection cons(Object o) {
- return new PersistentQueue(1,RT.list(o),EMPTY,null);
- }
-}
-
-final public static Empty EMPTY = new Empty();
-
-final int lenfm;
+//*
final ISeq f;
-final IPersistentList m; //queue of suspended seqs
-final ISeq r;
-
+final PersistentArrayList r;
+static final int INITIAL_REAR_SIZE = 4;
-public PersistentQueue(int lenfm, ISeq f, IPersistentList m, ISeq r) {
- this.lenfm = lenfm;
+PersistentQueue(ISeq f, PersistentArrayList r) {
this.f = f;
- this.m = m;
this.r = r;
}
@@ -65,31 +40,64 @@ public Object peek() { return RT.first(f);
}
-public IPersistentList pop() {
- return checkQ(lenfm - 1, RT.rest(f), m, r);
+public PersistentQueue pop() {
+ if(f == null) //hmmm... pop of empty queue -> empty queue?
+ return this;
+ //throw new IllegalStateException("popping empty queue");
+ ISeq f1 = f.rest();
+ PersistentArrayList r1 = r;
+ if(f1 == null)
+ {
+ f1 = RT.seq(r);
+ r1 = null;
+ }
+ PersistentQueue ret = new PersistentQueue(f1, r1);
+ ret._meta = _meta;
+ return ret;
}
public int count() {
- return lenfm + RT.count(r);
+ return RT.count(f) + RT.count(r);
}
public ISeq seq() {
- ISeq mseq = (r == null) ? m.seq():m.cons(new SuspReverse(r)).seq();
- return new Seq(f, mseq);
+ if(f == null)
+ return null;
+ return new Seq(f, RT.seq(r));
}
-public IPersistentCollection cons(Object o) {
- return checkQ(lenfm, f, m, RT.cons(o, r));
+public PersistentQueue cons(Object o) {
+ PersistentQueue ret;
+ if(f == null) //empty
+ ret = new PersistentQueue(RT.list(o), null);
+ else
+ ret= new PersistentQueue(f,
+ (PersistentArrayList) (r != null ? r : new PersistentArrayList(INITIAL_REAR_SIZE)).cons(o));
+ ret._meta = _meta;
+ return ret;
}
+public Obj withMeta(IPersistentMap meta) {
+ if(_meta == meta)
+ return this;
+ try{
+ Obj ret = (Obj) clone();
+ ret._meta = meta;
+ return ret;
+ }
+ catch(CloneNotSupportedException ignore)
+ {
+ return null;
+ }
+}
-static class Seq extends ASeq{
+static class Seq extends ASeq {
final ISeq f;
- final ISeq mseq; //seq of suspended seqs
+ final ISeq rseq;
- Seq(ISeq f, ISeq mseq) {
+ Seq(ISeq f, ISeq rseq) {
this.f = f;
- this.mseq = mseq;
+ this.rseq = rseq;
}
public Object first() {
@@ -98,119 +106,84 @@ static class Seq extends ASeq{ public ISeq rest() {
ISeq f1 = f.rest();
- ISeq m1 = mseq;
- if(f1 == null)
+ ISeq r1 = rseq;
+ if (f1 == null)
{
- if(mseq == null)
+ if (rseq == null)
return null;
- f1 = ((SuspReverse) mseq.first()).force();
- m1 = mseq.rest();
+ f1 = rseq;
+ r1 = null;
}
- return new Seq(f1, m1);
- }
-}
-
-//////////// implementation ///////////////
-static IPersistentList checkQ(int lenfm, ISeq f, IPersistentList m, ISeq r) {
- if(RT.count(r) <= lenfm)
- return checkF(lenfm,f,m,r);
- return checkF(lenfm + RT.count(r), f, (IPersistentList) m.cons(new SuspReverse(r)), null);
-}
-
-static IPersistentList checkF(int lenfm, ISeq f, IPersistentList m, ISeq r) {
- if(f == null)
- {
- if(m.count() == 0)
- return EMPTY;
- return new PersistentQueue(lenfm,((SuspReverse)m.peek()).force(),m.pop(),r);
- }
- return new PersistentQueue(lenfm,f,m,r);
-}
-
-static ISeq reverse(ISeq r){
- Object[] rev = new Object[RT.count(r)];
-
- ISeq s;
- int i;
- for (s = r, i=0; s != null; s = s.rest(), ++i)
- rev[i] = s.first();
- ISeq ret = null;
- for (i = 0; i < rev.length; i++)
- ret = RT.cons(rev[i], ret);
-
- return ret;
-}
-
-static class SuspReverse {
- volatile Object result;
- final ISeq s;
-
- public SuspReverse(ISeq s) {
- this.s = s;
- this.result = this;
- }
-
- public ISeq force() {
- if(result == this)
- result = reverse(s);
- return (ISeq) result;
+ return new Seq(f1, r1);
}
}
public static void main(String[] args) {
- if(args.length != 1)
+ if (args.length != 1)
{
System.err.println("Usage: PersistentQueue n");
return;
}
int n = Integer.parseInt(args[0]);
- IPersistentList q = PersistentQueue.EMPTY;
- Random rand;
-
- rand = new Random(42);
-
- System.out.println("PersistentQueue");
- long startTime = System.nanoTime();
- for(int i=0;i<n;i++)
- {
- q = (IPersistentList) q.cons(i);
- }
- for(int i=0;i<n-10;i++)
- {
- q = (IPersistentList) q.pop();
- }
- long estimatedTime = System.nanoTime() - startTime;
- System.out.println("time: " + estimatedTime/1000000);
- System.out.println("peek: " + q.peek());
+ long startTime, estimatedTime;
+ //*
//Queue list = new LinkedList();
Queue list = new ConcurrentLinkedQueue();
- System.out.println("LinkedList");
+ System.out.println("Queue");
startTime = System.nanoTime();
- for(int i=0;i<n;i++)
+ for (int i = 0; i < n; i++)
{
list.add(i);
+ list.add(i);
+ list.remove();
}
- for(int i=0;i<n-10;i++)
+ for (int i = 0; i < n - 10; i++)
{
list.remove();
}
estimatedTime = System.nanoTime() - startTime;
- System.out.println("time: " + estimatedTime/1000000);
+ System.out.println("time: " + estimatedTime / 1000000);
System.out.println("peek: " + list.peek());
+//*/
+
+//*
+ PersistentQueue q = PersistentQueue.EMPTY;
+ System.out.println("PersistentQueue");
+ startTime = System.nanoTime();
+ for (int i = 0; i < n; i++)
+ {
+ q = q.cons(i);
+ q = q.cons(i);
+ q = q.pop();
+ }
+ IPersistentList lastq = null;
+ IPersistentList lastq2;
+ for (int i = 0; i < n - 10; i++)
+ {
+ //lastq2 = lastq;
+ //lastq = q;
+ q = q.pop();
+ }
+ estimatedTime = System.nanoTime() - startTime;
+ System.out.println("time: " + estimatedTime / 1000000);
+ System.out.println("peek: " + q.peek());
+ //*/
+
IPersistentList q2 = q;
- for(int i=0;i<10;i++)
+ for (int i = 0; i < 10; i++)
{
q2 = (IPersistentList) q2.cons(i);
}
-
+/*
for(ISeq s = q.seq();s != null;s = s.rest())
- System.out.println(s.first().toString());
+ System.out.println("q: " + s.first().toString());
for(ISeq s = q2.seq();s != null;s = s.rest())
- System.out.println(s.first().toString());
+ System.out.println("q2: " + s.first().toString());
+//*/
}
}
|