From 108db3bc660f25860a201fbd2769ef2640f300bf Mon Sep 17 00:00:00 2001 From: Rich Hickey Date: Mon, 7 Aug 2006 17:13:55 +0000 Subject: added PersistentQueue --- src/cli/runtime/PersistentArray.cs | 40 +++++++- src/cli/runtime/PersistentQueue.cs | 186 +++++++++++++++++++++++++++++++++++++ src/cli/runtime/RT.cs | 2 +- 3 files changed, 225 insertions(+), 3 deletions(-) create mode 100644 src/cli/runtime/PersistentQueue.cs (limited to 'src/cli/runtime') 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) -- cgit v1.2.3-70-g09d2