added Counted interface and counted? predicate

implement stack/heap safe count in RT
stack-safe count in ASeq/Cons, patch from Chouser

13 files changed, 51 insertions, 18 deletions

diff --git a/src/clj/clojure/core.clj b/src/clj/clojure/core.clj
index e68f7c3b..09ff3acb 100644
--- a/src/clj/clojure/core.clj
+++ b/src/clj/clojure/core.clj
@@ -3713,6 +3713,10 @@
  "Returns true if coll implements Sorted"
   [coll] (instance? clojure.lang.Sorted coll))
 
+(defn counted?
+ "Returns true if coll implements count in constant time"
+  [coll] (instance? clojure.lang.Counted coll))
+
 (defn reversible?
  "Returns true if coll implements Reversible"
   [coll] (instance? clojure.lang.Reversible coll))
diff --git a/src/jvm/clojure/lang/APersistentVector.java b/src/jvm/clojure/lang/APersistentVector.java
index fe891ef7..dbdbacd1 100644
--- a/src/jvm/clojure/lang/APersistentVector.java
+++ b/src/jvm/clojure/lang/APersistentVector.java
@@ -471,7 +471,7 @@ public IStream stream() throws Exception {
 	}
 }
 
-static class RSeq extends ASeq implements IndexedSeq{
+static class RSeq extends ASeq implements IndexedSeq, Counted{
 	final IPersistentVector v;
 	final int i;
 
diff --git a/src/jvm/clojure/lang/ASeq.java b/src/jvm/clojure/lang/ASeq.java
index 8bd830d1..068f9060 100644
--- a/src/jvm/clojure/lang/ASeq.java
+++ b/src/jvm/clojure/lang/ASeq.java
@@ -98,7 +98,8 @@ public int hashCode(){
 public int count(){

 	int i = 1;

 	for(ISeq s = rest(); s != null; s = s.rest(), i++)

-		;

+		if(s instanceof Counted)

+			return i + s.count();

 	return i;

 }

 

diff --git a/src/jvm/clojure/lang/Cons.java b/src/jvm/clojure/lang/Cons.java
index c9e65eb3..193526ff 100644
--- a/src/jvm/clojure/lang/Cons.java
+++ b/src/jvm/clojure/lang/Cons.java
@@ -37,10 +37,6 @@ public ISeq rest(){
 	return _rest;
 }
 
-public int count(){
-	return 1 + RT.count(_rest);
-}
-
 public ISeq seq(){
 	return this;
 }
diff --git a/src/jvm/clojure/lang/Counted.java b/src/jvm/clojure/lang/Counted.java
new file mode 100644
index 00000000..84b14b63
--- /dev/null
+++ b/src/jvm/clojure/lang/Counted.java
@@ -0,0 +1,18 @@
+package clojure.lang;
+
+/**
+ * Copyright (c) Rich Hickey. All rights reserved.
+ * The use and distribution terms for this software are covered by the
+ * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ * which can be found in the file epl-v10.html 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.
+ */
+
+/* A class that implements Counted promises that it is a collection
+ * that implement a constant-time count() */
+
+public interface Counted {
+    int count();
+}
diff --git a/src/jvm/clojure/lang/IPersistentMap.java b/src/jvm/clojure/lang/IPersistentMap.java
index 3271141e..87108155 100644
--- a/src/jvm/clojure/lang/IPersistentMap.java
+++ b/src/jvm/clojure/lang/IPersistentMap.java
@@ -11,7 +11,7 @@
 package clojure.lang;

 

 

-public interface IPersistentMap extends Iterable, Associative{

+public interface IPersistentMap extends Iterable, Associative, Counted{

 

 

 IPersistentMap assoc(Object key, Object val);

diff --git a/src/jvm/clojure/lang/IPersistentSet.java b/src/jvm/clojure/lang/IPersistentSet.java
index 2e6f96b8..36fa1ead 100644
--- a/src/jvm/clojure/lang/IPersistentSet.java
+++ b/src/jvm/clojure/lang/IPersistentSet.java
@@ -12,7 +12,7 @@
 
 package clojure.lang;
 
-public interface IPersistentSet extends IPersistentCollection{
+public interface IPersistentSet extends IPersistentCollection, Counted{
 	public IPersistentSet disjoin(Object key) throws Exception;
 	public boolean contains(Object key);
 	public Object get(Object key);
diff --git a/src/jvm/clojure/lang/IPersistentVector.java b/src/jvm/clojure/lang/IPersistentVector.java
index fb20921a..b85f2ab2 100644
--- a/src/jvm/clojure/lang/IPersistentVector.java
+++ b/src/jvm/clojure/lang/IPersistentVector.java
@@ -10,7 +10,7 @@ package clojure.lang;
  * You must not remove this notice, or any other, from this software.

  */

 

-public interface IPersistentVector extends Associative, Sequential, IPersistentStack, Reversible{

+public interface IPersistentVector extends Associative, Sequential, IPersistentStack, Reversible, Counted{

 int length();

 

 Object nth(int i);

diff --git a/src/jvm/clojure/lang/IndexedSeq.java b/src/jvm/clojure/lang/IndexedSeq.java
index 6dbfca29..fd1eba4b 100644
--- a/src/jvm/clojure/lang/IndexedSeq.java
+++ b/src/jvm/clojure/lang/IndexedSeq.java
@@ -10,7 +10,7 @@
 

 package clojure.lang;

 

-public interface IndexedSeq extends ISeq{

+public interface IndexedSeq extends ISeq, Counted{

 

 public int index();

 }

diff --git a/src/jvm/clojure/lang/PersistentArrayMap.java b/src/jvm/clojure/lang/PersistentArrayMap.java
index d8fbd354..a28eb308 100644
--- a/src/jvm/clojure/lang/PersistentArrayMap.java
+++ b/src/jvm/clojure/lang/PersistentArrayMap.java
@@ -197,7 +197,7 @@ public ISeq seq(){
 	return null;

 }

 

-static class Seq extends ASeq{

+static class Seq extends ASeq implements Counted{

 	final Object[] array;

 	final int i;

 

diff --git a/src/jvm/clojure/lang/PersistentList.java b/src/jvm/clojure/lang/PersistentList.java
index b3949007..7daf32a0 100644
--- a/src/jvm/clojure/lang/PersistentList.java
+++ b/src/jvm/clojure/lang/PersistentList.java
@@ -12,7 +12,7 @@ package clojure.lang;
 

 import java.util.*;

 

-public class PersistentList extends ASeq implements IPersistentList, IReduce, List{

+public class PersistentList extends ASeq implements IPersistentList, IReduce, List, Counted{

 

 private final Object _first;

 private final IPersistentList _rest;

@@ -114,7 +114,7 @@ public Object reduce(IFn f, Object start) throws Exception{
 

 

 

-static class EmptyList extends Obj implements IPersistentList, List{

+static class EmptyList extends Obj implements IPersistentList, List, Counted{

 

 	public int hashCode(){

 		return 1;

diff --git a/src/jvm/clojure/lang/RT.java b/src/jvm/clojure/lang/RT.java
index a3383cfe..dd86c76a 100644
--- a/src/jvm/clojure/lang/RT.java
+++ b/src/jvm/clojure/lang/RT.java
@@ -508,9 +508,22 @@ static public IPersistentMap meta(Object x){
 public static int count(Object o){
 	if(o == null)
 		return 0;
-	else if(o instanceof IPersistentCollection)
-		return ((IPersistentCollection) o).count();
-	else if(o instanceof String)
+	else if(o instanceof Counted)
+		return ((Counted) o).count();
+    else if(o instanceof IPersistentCollection)
+       {
+       ISeq s = seq(o);
+       o = null;
+       int i = 0;
+       for(;s!=null;s = s.rest())
+           {
+		   if(s instanceof Counted)
+			    return i + s.count();
+           i++;
+           }
+       return i;
+       }
+    else if(o instanceof String)
 		return ((String) o).length();
 	else if(o instanceof Collection)
 		return ((Collection) o).size();
@@ -518,7 +531,8 @@ public static int count(Object o){
 		return ((Map) o).size();
 	else if(o.getClass().isArray())
 		return Array.getLength(o);
-	throw new UnsupportedOperationException("count not supported on this type: " + o.getClass().getSimpleName());
+
+    throw new UnsupportedOperationException("count not supported on this type: " + o.getClass().getSimpleName());
 }
 
 static public IPersistentCollection conj(IPersistentCollection coll, Object x){
diff --git a/src/jvm/clojure/lang/Range.java b/src/jvm/clojure/lang/Range.java
index 226a77ba..8f794f27 100644
--- a/src/jvm/clojure/lang/Range.java
+++ b/src/jvm/clojure/lang/Range.java
@@ -14,7 +14,7 @@ package clojure.lang;
 
 import java.util.concurrent.atomic.AtomicInteger;
 
-public class Range extends ASeq implements IReduce, Streamable{
+public class Range extends ASeq implements IReduce, Streamable, Counted{
 final int end;
 final int n;