made seq.count constant-time

14 files changed, 100 insertions, 38 deletions

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;

+	}

 }

 
 
diff --git a/src/jvm/clojure/lang/ArraySeq.java b/src/jvm/clojure/lang/ArraySeq.java
index d9af61a1..1c9906d0 100644
--- a/src/jvm/clojure/lang/ArraySeq.java
+++ b/src/jvm/clojure/lang/ArraySeq.java
@@ -46,6 +46,10 @@ public ISeq rest() {
 //    return _rest;
 }
 
+public int count() {
+    return array.length - i;
+    }
+
 public int index(){
 	return i;
 }
diff --git a/src/jvm/clojure/lang/MapEntry.java b/src/jvm/clojure/lang/MapEntry.java
index 702b2937..f4dace75 100644
--- a/src/jvm/clojure/lang/MapEntry.java
+++ b/src/jvm/clojure/lang/MapEntry.java
@@ -99,7 +99,7 @@ public ISeq seq()  {
 }

 

 static class Seq extends ASeq{

-    MapEntry e;

+    final MapEntry e;

 

     public Seq(MapEntry e) {

         this.e = e;

@@ -112,5 +112,8 @@ static class Seq extends ASeq{
     public ISeq rest() {

         return null;

     }

+    public int count() {

+        return 1;

+    }

 }

 }

diff --git a/src/jvm/clojure/lang/PersistentArrayMap.java b/src/jvm/clojure/lang/PersistentArrayMap.java
index ee539ba4..620a6520 100644
--- a/src/jvm/clojure/lang/PersistentArrayMap.java
+++ b/src/jvm/clojure/lang/PersistentArrayMap.java
@@ -205,6 +205,9 @@ static class Seq extends ASeq implements IMapEntry{
             return new Seq(array, i + 2);

         return null;

     }

+    public int count() {

+        return (array.length - i)/2;

+    }

 }

 

 static class Iter implements Iterator,IMapEntry{

diff --git a/src/jvm/clojure/lang/PersistentHashtableMap.java b/src/jvm/clojure/lang/PersistentHashtableMap.java
index a701156b..cee7bb55 100644
--- a/src/jvm/clojure/lang/PersistentHashtableMap.java
+++ b/src/jvm/clojure/lang/PersistentHashtableMap.java
@@ -163,35 +163,39 @@ public Iterator iterator() {
 }

 

 public ISeq seq() {

-    return Seq.create(array);

+    if(count() == 0)

+        return null;

+    return Seq.create(array,count());

 }

 

 static class Seq extends ASeq{

-    PersistentArray buckets;

-    int b;

-    ISeq e;

+    final PersistentArray buckets;

+    final int b;

+    final ISeq e;

+    final 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;

     }

 

     public Object first() {

@@ -199,7 +203,11 @@ static class Seq extends ASeq{
     }

 

     public ISeq rest() {

-        return next(buckets,b,e);

+        return next(buckets,b,e,cnt-1);

+    }

+

+    public int count() {

+        return cnt;

     }

 }

 

diff --git a/src/jvm/clojure/lang/PersistentList.java b/src/jvm/clojure/lang/PersistentList.java
index 22424e0c..923ca53e 100644
--- a/src/jvm/clojure/lang/PersistentList.java
+++ b/src/jvm/clojure/lang/PersistentList.java
@@ -23,7 +23,7 @@ public PersistentList(Object first) {
     this._count = 1;

 }

 

-private PersistentList(Object first, PersistentList rest) {

+PersistentList(Object first, PersistentList rest) {

     this._first = first;

     this._rest = rest;

 

diff --git a/src/jvm/clojure/lang/PersistentQueue.java b/src/jvm/clojure/lang/PersistentQueue.java
index 32346a40..8f891ab6 100644
--- a/src/jvm/clojure/lang/PersistentQueue.java
+++ b/src/jvm/clojure/lang/PersistentQueue.java
@@ -139,6 +139,11 @@ static class Seq extends ASeq {
             }

         return new Seq(f1, r1);

     }

+

+    public int count() {

+        return RT.count(f) + RT.count(rseq);

+    }

+

 }

 

 public static void main(String[] args) {

diff --git a/src/jvm/clojure/lang/PersistentTreeMap.java b/src/jvm/clojure/lang/PersistentTreeMap.java
index 5f07ac80..31271f18 100644
--- a/src/jvm/clojure/lang/PersistentTreeMap.java
+++ b/src/jvm/clojure/lang/PersistentTreeMap.java
@@ -84,13 +84,13 @@ public PersistentTreeMap without(Object key){
 
 public ISeq seq() {
     if(_count > 0)
-        return Seq.create(tree, true);
+        return Seq.create(tree, true,_count);
     return null;
 }
 
 public ISeq rseq() throws Exception {
     if(_count > 0)
-        return Seq.create(tree, false);
+        return Seq.create(tree, false,_count);
     return null;
 }
 
@@ -619,14 +619,16 @@ static class RedBranchVal extends RedBranch{
 static public class Seq extends ASeq{
 	final ISeq stack;
 	final boolean asc;
+    final int cnt;
 
-    public Seq(ISeq stack, boolean asc) {
+    public Seq(ISeq stack, boolean asc,int cnt) {
         this.stack = stack;
         this.asc = asc;
+        this.cnt = cnt;
     }
 
-    static Seq create(Node t, boolean asc)  {
-        return new Seq(push(t, null, asc),asc);
+    static Seq create(Node t, boolean asc,int cnt)  {
+        return new Seq(push(t, null, asc),asc,cnt);
     }
 
 	static ISeq push(Node t, ISeq stack, boolean asc) {
@@ -647,10 +649,14 @@ static public class Seq extends 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 int count() {
+        return cnt;
+    }
 }
 
 static public class NodeIterator implements Iterator{