sorting in keywords, symbols

6 files changed, 127 insertions, 12 deletions

diff --git a/clojure.markdown b/clojure.markdown
index 2b666586..f356be56 100644
--- a/clojure.markdown
+++ b/clojure.markdown
@@ -431,12 +431,19 @@ Clojure strings are Java `Strings`.
 Clojure characters are Java `Characters`.
 
 ### Keywords
-Keywords are symbolic identifiers that evaluate to themselves. They provide very fast equality tests. Like Symbols, they have names and optional namespaces, both of which are strings. The leading ':' is not part of the namespace or name.
+Keywords are symbolic identifiers that evaluate to themselves. They provide very fast equality tests. Like Symbols, they have names and optional namespaces, both of which are strings. The leading ':' is not part of the namespace or name. Keywords implement IFn, for invoke() of one argument, which they expect to be a map, in which they look themselves up, i.e. keywords are functions of maps.
+
+<pre><code>
+(def m {:a 1 :b 2 :c 3})
+
+(:b m)
+> 2
+</code></pre>
 
 ### Symbols
 Symbols are identifiers that are normally used to refer to something else. They can be used in program forms to refer to function parameters, let bindings, class names and global vars. They have names and optional namespaces, both of which are strings. Symbols can have metadata.
 
-### Collections
+### _Collections_
 
 All of the Clojure collections are immutable and [persistent][pd]. In particular, the Clojure collections support efficient creation of 'modified' versions, by utilizing structural sharing, and make all of their performance bound guarantees for persistent use. The collections are efficient and inherently thread-safe. Collections are represented by abstractions, and there may be one or more concrete realizations. In particular, since 'modification' operations yield new collections, the new collection might not have the same concrete type as the source collection, but will have the same logical (interface) type. All the collections support these functions:
 
@@ -446,19 +453,65 @@ Returns the number of items in the collection. `(count nil)` returns `0`.
 
 ---
 ### (*conj* coll item)
-Conj[oin]. Returns a new collection with the item added. `(conj nil item)` returns `(item)`.
+Conj[oin]. Returns a new collection with the item 'added'. `(conj nil item)` returns `(item)`.
 
 ---
 ### (*seq* coll)
 Sequence. Returns a new ISeq on the collection. If the collection is empty, returns `nil`. `(seq nil)` returns `nil`.
 
 
-### Lists (IPersistentList)
-	
-### Maps (IPersistentMap)
+### _Lists (IPersistentList)_
+Lists are collections. They implement the ISeq interface directly. `count` is O(1). `conj` puts the item at the front of the list. In addition, lists support the functions:
+
+---
+### (*list*  & items)
+Creates a new list containing the items.
+
+---
+### (*peek* list)
+Same as `first`. Returns the first item in the list. If the list is empty, returns `nil`.
+
+---
+### (*pop* list)
+Returns a new list without the first item. If the list is empty, throws an exception. Note - *not* the same as `rest`.
+		
+### _Maps_ (IPersistentMap)
+
+Map keys to values. Two different map types are provided - hashed and sorted. Hash maps require keys that correctly support hashCode and equals. Sorted maps require keys that implement Comparable, or an instance of Comparator. Hash maps provide faster access O(log32N) vs O(logN), but sorted maps are, well, sorted. `count` is O(1). `conj` expects another (possibly single entry) map as the item, and returns a new map which is the old map plus the entries from the new, which may overwrite entries of the old. `seq` returns a sequence of map entries, which are key/value pairs. Maps implement IFn, for invoke() of one argument, which they presume is a key and look up in themselves, i.e. maps are functions of their keys. 
+
+They share these functions:
+
+---
+### (*assoc* map key val)
+Assoc[iate]. Returns a new map of the same (hashed/sorted) type, that contains the mapping of key to val.
+
+---
+### (*dissoc* map key)
+Dissoc[iate]. Returns a new map of the same (hashed/sorted) type, that does not contain a mapping for key.
+
+---
+### (*get* map key)
+Returns the value mapped to key, or `nil` if key not present.
+
+---
+### (*contains* map key)
+Returns `nil` if key not present, else non-nil.
+
+---
+### (*find* map key)
+Returns the map entry for key, or `nil` if key not present.
+
+---
+### (*keys* map)
+Returns a sequence of the map's keys.
+
+---
+### (*vals* map)
+Returns a sequence of the map's values.
 	
 ### Vectors (IPersistentVector)
 
+
 <h2 id="metadata">Metadata</h2>
 
 <h2 id="sequences">Sequences</h2>
diff --git a/src/boot.clj b/src/boot.clj
index d40d4699..f687c487 100644
--- a/src/boot.clj
+++ b/src/boot.clj
@@ -17,6 +17,14 @@
       ([& args]
           (. clojure.lang.PersistentHashMap (create args))))
 
+(defn sorted-map
+      ([& args]
+          (. clojure.lang.PersistentTreeMap (create args))))
+
+(defn sorted-map-by
+      ([comparator & args]
+          (. clojure.lang.PersistentTreeMap (create comparator args))))
+
 (defn meta [#^IObj x]
  (. x (meta)))
 
@@ -208,9 +216,14 @@
 (defn dissoc [coll key]
  (. RT (dissoc coll key)))
 
-(defn count [coll]
- (. RT (count coll)))
+(defn find [coll key]
+ (. RT (find coll key)))
+
+(defn keys [map]
+  (. RT (keys map)))
 
+(defn vals [map]
+  (. RT (vals map)))
 
 (defn andfn [& args]
       (if (nil? (rest args))
diff --git a/src/jvm/clojure/lang/APersistentMap.java b/src/jvm/clojure/lang/APersistentMap.java
index 8e00853f..18481747 100644
--- a/src/jvm/clojure/lang/APersistentMap.java
+++ b/src/jvm/clojure/lang/APersistentMap.java
@@ -10,7 +10,7 @@
 

 package clojure.lang;

 

-public abstract class APersistentMap extends Obj implements IPersistentMap{

+public abstract class APersistentMap extends AFn implements IPersistentMap{

 int _hash = -1;

 

 

@@ -128,4 +128,8 @@ static public class ValSeq extends ASeq{
 	}

 }

 

+

+public Object invoke(Object arg1) throws Exception{

+	return valAt(arg1);

+}

 }

diff --git a/src/jvm/clojure/lang/Keyword.java b/src/jvm/clojure/lang/Keyword.java
index 1576a20d..479a9b2f 100644
--- a/src/jvm/clojure/lang/Keyword.java
+++ b/src/jvm/clojure/lang/Keyword.java
@@ -15,7 +15,7 @@ package clojure.lang;
 import java.util.concurrent.ConcurrentHashMap;
 
 
-public class Keyword implements IFn{
+public class Keyword implements IFn, Comparable{
 
 private static ConcurrentHashMap<Symbol, Keyword> table = new ConcurrentHashMap();
 public final Symbol sym;
@@ -46,6 +46,11 @@ public Object invoke() throws Exception{
 	return AFn.throwArity();
 }
 
+public int compareTo(Object o){
+	return sym.compareTo(((Keyword) o).sym);
+}
+
+
 /**
  * Indexer implements IFn for attr access
  *
@@ -170,4 +175,6 @@ public Object invoke(Object arg1, Object arg2, Object arg3, Object arg4, Object
 public Object applyTo(ISeq arglist) throws Exception{
 	return AFn.applyToHelper(this, arglist);
 }
+
+
 }
diff --git a/src/jvm/clojure/lang/PersistentTreeMap.java b/src/jvm/clojure/lang/PersistentTreeMap.java
index d56a803e..d806c610 100644
--- a/src/jvm/clojure/lang/PersistentTreeMap.java
+++ b/src/jvm/clojure/lang/PersistentTreeMap.java
@@ -28,6 +28,8 @@ public final Comparator comp;
 public final Node tree;
 public final int _count;
 
+final static public PersistentTreeMap EMPTY = new PersistentTreeMap();
+
 public PersistentTreeMap(){
 	this(null);
 }
@@ -36,7 +38,7 @@ public PersistentTreeMap withMeta(IPersistentMap meta){
 	return new PersistentTreeMap(meta, comp, tree, _count);
 }
 
-public PersistentTreeMap(Comparator comp){
+private PersistentTreeMap(Comparator comp){
 	this(null, comp);
 }
 
@@ -55,6 +57,28 @@ PersistentTreeMap(IPersistentMap meta, Comparator comp, Node tree, int _count){
 	this._count = _count;
 }
 
+static public PersistentTreeMap create(ISeq items){
+	IPersistentMap ret = EMPTY;
+	for(; items != null; items = items.rest().rest())
+		{
+		if(items.rest() == null)
+			throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first()));
+		ret = ret.assoc(items.first(), RT.second(items));
+		}
+	return (PersistentTreeMap) ret;
+}
+
+static public PersistentTreeMap create(Comparator comp, ISeq items){
+	IPersistentMap ret = new PersistentTreeMap(comp);
+	for(; items != null; items = items.rest().rest())
+		{
+		if(items.rest() == null)
+			throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first()));
+		ret = ret.assoc(items.first(), RT.second(items));
+		}
+	return (PersistentTreeMap) ret;
+}
+
 public boolean contains(Object key){
 	return entryAt(key) != null;
 }
diff --git a/src/jvm/clojure/lang/Symbol.java b/src/jvm/clojure/lang/Symbol.java
index 43b05788..dcbce7b2 100644
--- a/src/jvm/clojure/lang/Symbol.java
+++ b/src/jvm/clojure/lang/Symbol.java
@@ -13,7 +13,7 @@
 package clojure.lang;
 
 
-public class Symbol extends Obj{
+public class Symbol extends Obj implements Comparable{
 //these must be interned strings!
 public final String ns;
 public final String name;
@@ -77,4 +77,18 @@ private Symbol(IPersistentMap meta, String ns, String name){
 	this.ns = ns;
 	this.hash = RT.hashCombine(name.hashCode(), RT.hash(ns));
 }
+
+public int compareTo(Object o){
+	Symbol s = (Symbol) o;
+	if(this.equals(o))
+		return 0;
+	if(this.ns == null && s.ns != null)
+		return -1;
+	if(this.ns != null && s.ns == null)
+		return 1;
+	int nsc = this.name.compareTo(s.name);
+	if(nsc != 0)
+		return nsc;
+	return this.name.compareTo(s.name);
+}
 }