diff options
Diffstat (limited to 'src/cli/runtime/PersistentQueue.cs')
| -rw-r--r-- | src/cli/runtime/PersistentQueue.cs | 186 |
1 files changed, 186 insertions, 0 deletions
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());
+}
+//*/
+
+}
+
+ }
|