From b9b9ceb459f528347f2433357697370fa3fa67b4 Mon Sep 17 00:00:00 2001
From: Rich Hickey <richhickey@gmail.com>
Date: Wed, 9 Aug 2006 14:45:16 +0000
Subject: made seq.count constant-time

---
 src/cli/runtime/ArraySeq.cs               |  4 ++++
 src/cli/runtime/MapEntry.cs               |  7 ++++++-
 src/cli/runtime/PersistentArrayMap.cs     |  3 +++
 src/cli/runtime/PersistentHashtableMap.cs | 33 ++++++++++++++++++++-----------
 src/cli/runtime/PersistentList.cs         |  2 +-
 src/cli/runtime/PersistentQueue.cs        |  3 +++
 src/cli/runtime/PersistentTreeMap.cs      | 19 ++++++++++++------
 7 files changed, 52 insertions(+), 19 deletions(-)

(limited to 'src/cli/runtime')

diff --git a/src/cli/runtime/ArraySeq.cs b/src/cli/runtime/ArraySeq.cs
index 144d872f..4503792e 100644
--- a/src/cli/runtime/ArraySeq.cs
+++ b/src/cli/runtime/ArraySeq.cs
@@ -50,6 +50,10 @@ override public ISeq rest() {
 //    return _rest;
 }
 
+public override int count() {
+    return array.Length - i;
+}
+	
 public int index(){
 	return i;
 }
diff --git a/src/cli/runtime/MapEntry.cs b/src/cli/runtime/MapEntry.cs
index 88358b27..1ff7f93a 100644
--- a/src/cli/runtime/MapEntry.cs
+++ b/src/cli/runtime/MapEntry.cs
@@ -111,7 +111,7 @@ override public ISeq seq()  {
 }
 
 class Seq : ASeq{
-    MapEntry e;
+    readonly MapEntry e;
 
     public Seq(MapEntry e) {
         this.e = e;
@@ -124,6 +124,11 @@ class Seq : ASeq{
     override public ISeq rest() {
         return null;
     }
+
+	override public int count(){
+		return 1;
+	}
+	
 }
 }
 
diff --git a/src/cli/runtime/PersistentArrayMap.cs b/src/cli/runtime/PersistentArrayMap.cs
index f4e9e6ee..8ffaca76 100644
--- a/src/cli/runtime/PersistentArrayMap.cs
+++ b/src/cli/runtime/PersistentArrayMap.cs
@@ -208,6 +208,9 @@ internal class Seq : ASeq, IMapEntry{
             return new Seq(array, i + 2);
         return null;
     }
+    override public int count() {
+        return (array.Length - i)/2;
+    }
 }
 internal class Iter : IEnumerator,IMapEntry{
     Object[] array;
diff --git a/src/cli/runtime/PersistentHashtableMap.cs b/src/cli/runtime/PersistentHashtableMap.cs
index b54166a0..76dd01f1 100644
--- a/src/cli/runtime/PersistentHashtableMap.cs
+++ b/src/cli/runtime/PersistentHashtableMap.cs
@@ -170,35 +170,41 @@ override public IEnumerator GetEnumerator() {
 }
 
 override public ISeq seq() {
-    return Seq.create(array);
+	if(count() == 0)
+		return null;
+    return Seq.create(array,count());
 }
 
 class Seq : ASeq{
-    PersistentArray buckets;
-    int b;
-    ISeq e;
+    readonly PersistentArray buckets;
+	readonly int b;
+	readonly ISeq e;
+	readonly int cnt;
 
 
-    static public Seq create(PersistentArray buckets) {
-        return next(buckets, -1, null);
+    static public Seq create(PersistentArray buckets,int cnt) {
+        return next(buckets, -1, null,cnt);
     }
 
-    static Seq next(PersistentArray buckets, int b, ISeq e) {
+	static Seq next(PersistentArray buckets, int b, ISeq e, int cnt)
+		{
         if(e != null && e.rest() != null)
-            return new Seq(buckets,b,e.rest());
+            return new Seq(buckets,b,e.rest(),cnt);
         for(b = b+1;b<buckets.length();b++)
             {
             IPersistentCollection a = (IPersistentCollection) buckets.nth(b);
             if(a != null && a.seq() != null)
-                return new Seq(buckets,b,a.seq());
+                return new Seq(buckets,b,a.seq(),cnt);
             }
         return null;
     }
 
-    Seq(PersistentArray buckets, int b, ISeq e) {
+	Seq(PersistentArray buckets, int b, ISeq e, int cnt)
+		{
         this.buckets = buckets;
         this.b = b;
         this.e = e;
+		this.cnt = cnt;
     }
 
     override public Object first() {
@@ -206,8 +212,13 @@ class Seq : ASeq{
     }
 
     override public ISeq rest() {
-        return next(buckets,b,e);
+        return next(buckets,b,e,cnt-1);
     }
+
+	public override int count()
+	{
+		return cnt;
+	}
 }
 
 internal class Iter : IEnumerator{
diff --git a/src/cli/runtime/PersistentList.cs b/src/cli/runtime/PersistentList.cs
index dbe4412c..b29c0908 100644
--- a/src/cli/runtime/PersistentList.cs
+++ b/src/cli/runtime/PersistentList.cs
@@ -26,7 +26,7 @@ public PersistentList(Object first) {
     this._count = 1;
 }
 
-private PersistentList(Object first, PersistentList rest) {
+internal PersistentList(Object first, PersistentList rest) {
     this._first = first;
     this._rest = rest;
 
diff --git a/src/cli/runtime/PersistentQueue.cs b/src/cli/runtime/PersistentQueue.cs
index 2ed5d966..14d7c2f8 100644
--- a/src/cli/runtime/PersistentQueue.cs
+++ b/src/cli/runtime/PersistentQueue.cs
@@ -135,6 +135,9 @@ class Seq : ASeq {
             }
         return new Seq(f1, r1);
     }
+    public override int count() {
+        return RT.count(f) + RT.count(rseq);
+    }
 }
 
 //*
diff --git a/src/cli/runtime/PersistentTreeMap.cs b/src/cli/runtime/PersistentTreeMap.cs
index cbf366c9..77be3e9f 100644
--- a/src/cli/runtime/PersistentTreeMap.cs
+++ b/src/cli/runtime/PersistentTreeMap.cs
@@ -89,13 +89,13 @@ override public IPersistentMap without(Object key){
 
 override public ISeq seq() {
     if(_count > 0)
-        return Seq.create(tree, true);
+        return Seq.create(tree, true,_count);
     return null;
 }
 
 public ISeq rseq() {
     if(_count > 0)
-        return Seq.create(tree, false);
+        return Seq.create(tree, false,_count);
     return null;
 }
 
@@ -636,14 +636,16 @@ class RedBranchVal : RedBranch{
 public class Seq : ASeq{
 	readonly ISeq stack;
 	readonly bool asc;
+	readonly int cnt;
 
-    Seq(ISeq stack, bool asc) {
+    Seq(ISeq stack, bool asc, int cnt) {
         this.stack = stack;
         this.asc = asc;
+    	this.cnt = cnt;
     }
 
-    internal static Seq create(Node t, bool asc){
-		return new Seq(push(t, null, asc),asc);
+    internal static Seq create(Node t, bool asc,int cnt){
+		return new Seq(push(t, null, asc),asc,cnt);
 	}
 
 	static ISeq push(Node t, ISeq stack, bool asc){
@@ -664,10 +666,15 @@ public class Seq : ASeq{
         ISeq nextstack = push(asc ? t.right() : t.left(), stack.rest(), asc);
         if(nextstack != null)
             {
-            return new Seq(nextstack,asc);
+            return new Seq(nextstack,asc,cnt-1);
             }
         return null;
     }
+
+	public override int count()
+	{
+		return cnt;
+	}
 }
 
 
-- 
cgit v1.2.3-70-g09d2