Hi all,
I use Justin Balthrop's (ninjudd) nice ordered-set library [fn:1] in my
application. Because I frequently merge several sets using `into', I
wondered if I could get a performance win if PersistentOrderedSet would
support going transient by implementing the IEditableCollection
interface by providing a new TransientOrderedSet class and the relevant
asTransient() method for PersistentOrderedSet.
I've now added support for that (patch against the git master version
attached to this mail, or the complete java file posted at
http://pastebin.com/H2k9q75u where changes/additions start at line 202).
Unfortunately, it doesn't work correctly, i.e., I get wrong results
(ordered sets that do not contain everything my test cases expect). But
I'm not able to produce some minimal test case at the repl.
My application doesn't use transient directly, but only by calling (into
s1 s2). To exclude that I accidentially broke the persistent
ordered-set implementation, I redefined `into' to not go transient.
When doing so, my application's test suite succeeds again. So it can be
concluded that my TransientOrderedSet class contains some bug.
Sadly, I cannot spot it, and my knowledge of the clojure java classes is
pretty much at level zero. It would be awesome if someone with a better
knowledge could check my code for obvious mistakes.
Bye,
Tassilo
Footnotes:
[fn:1] https://github.com/ninjudd/ordered-set
>From a292366da91ceb9fb346e9edb5a3b40505c631fa Mon Sep 17 00:00:00 2001
From: Tassilo Horn <tass...@member.fsf.org>
Date: Thu, 10 Mar 2011 20:28:55 +0100
Subject: [PATCH] - implement IEditableCollection to allow for going transient
- bump version to 0.2.0
---
project.clj | 7 +-
src/clj/ordered_set.clj | 3 +-
src/jvm/clojure/lang/PersistentOrderedSet.java | 421 ++++++++++++++++--------
3 files changed, 281 insertions(+), 150 deletions(-)
diff --git a/project.clj b/project.clj
index 4a927fd..62c8bd7 100644
--- a/project.clj
+++ b/project.clj
@@ -1,3 +1,6 @@
-(defproject ordered-set "0.1.0"
+(defproject ordered-set "0.2.0"
:description "A Clojure set that maintains the insertion order of items"
- :dependencies [[clojure "1.2.0-master-SNAPSHOT"]])
+ :dependencies [[clojure "1.2.0"]]
+ :source-path "src/clj/"
+ :java-source-path "src/jvm/"
+ :javac-options {:destdir "classes/"})
diff --git a/src/clj/ordered_set.clj b/src/clj/ordered_set.clj
index 7152edb..32baaaa 100644
--- a/src/clj/ordered_set.clj
+++ b/src/clj/ordered_set.clj
@@ -1,5 +1,4 @@
-(ns ordered-set
- (:import [clojure.lang PersistentOrderedSet]))
+(ns ordered-set)
(defn ordered-set [& items]
(clojure.lang.PersistentOrderedSet/create items))
diff --git a/src/jvm/clojure/lang/PersistentOrderedSet.java b/src/jvm/clojure/lang/PersistentOrderedSet.java
index e0a5136..7315a6e 100644
--- a/src/jvm/clojure/lang/PersistentOrderedSet.java
+++ b/src/jvm/clojure/lang/PersistentOrderedSet.java
@@ -4,150 +4,279 @@ import java.io.Serializable;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
-
-public class PersistentOrderedSet extends AFn implements IPersistentSet, IObj, Collection, Set, Serializable, Counted {
-
-static public final PersistentOrderedSet EMPTY = new PersistentOrderedSet(null, PersistentHashSet.EMPTY, PersistentVector.EMPTY);
-
-final IPersistentMap _meta;
-final IPersistentSet items;
-final PersistentVector order;
-
-protected PersistentOrderedSet(IPersistentMap meta, IPersistentSet items, PersistentVector order){
- this._meta = meta;
- this.items = items;
- this.order = order;
-}
-
-static public PersistentOrderedSet create(ISeq items){
- PersistentOrderedSet set = EMPTY;
- for(; items != null; items = items.next()) {
- set = (PersistentOrderedSet) set.cons(items.first());
- }
- return set;
-}
-
-public IPersistentSet disjoin(Object item) throws Exception{
- if (!contains(item)) return this;
-
- PersistentVector.TransientVector new_order = PersistentVector.EMPTY.asTransient();
- ISeq s = seq();
- for (; s != null; s = s.next()) {
- if (s.first() != item) new_order = new_order.conj(s.first());
- }
- return new PersistentOrderedSet(_meta, items.disjoin(item), new_order.persistent());
-}
-
-public IPersistentSet cons(Object item){
- if (contains(item)) return this;
- return new PersistentOrderedSet(_meta, (IPersistentSet) items.cons(item), order.cons(item));
-}
-
-public IPersistentCollection empty(){
- return EMPTY.withMeta(meta());
-}
-
-public PersistentOrderedSet withMeta(IPersistentMap meta){
- return new PersistentOrderedSet(meta, items, order);
-}
-
-public IPersistentMap meta(){
- return _meta;
-}
-
-public String toString(){
- return RT.printString(this);
-}
-
-public Object get(Object key){
- return items.get(key);
-}
-
-public boolean contains(Object key){
- return items.contains(key);
-}
-
-public boolean containsAll(Collection c){
- for (Object item : c) {
- if (!contains(item)) return false;
- }
- return true;
-}
-
-public int count(){
- return order.count();
-}
-
-public int size(){
- return count();
-}
-
-public boolean isEmpty(){
- return count() == 0;
-}
-
-public ISeq seq(){
- return RT.seq(order);
-}
-
-public Iterator iterator(){
- return new SeqIterator(seq());
-}
-
-public Object invoke(Object arg1) throws Exception{
- return get(arg1);
-}
-
-public boolean equals(Object obj){
- if (this == obj) return true;
- if (!(obj instanceof Set)) return false;
- Set s = (Set) obj;
-
- if (s.size() != count()) return false;
- return containsAll(s);
-}
-
-public boolean equiv(Object obj){
- return equals(obj);
-}
-
-public Object[] toArray(){
- return RT.seqToArray(seq());
-}
-
-public Object[] toArray(Object[] a){
- if (count() > a.length) return toArray();
-
- ISeq s = seq();
- for (int i = 0; s != null; ++i, s = s.next()) {
- a[i] = s.first();
- }
- if (a.length > count()) a[count()] = null;
- return a;
-}
-
-public boolean add(Object o){
- throw new UnsupportedOperationException();
-}
-
-public boolean remove(Object o){
- throw new UnsupportedOperationException();
-}
-
-public boolean addAll(Collection c){
- throw new UnsupportedOperationException();
+import java.util.concurrent.Callable;
+
+public class PersistentOrderedSet extends AFn implements IObj,
+ IEditableCollection, IPersistentSet, Counted, IFn, IMeta,
+ IPersistentCollection, Seqable, Serializable, Iterable, Runnable,
+ Collection, Callable, Set {
+
+ private static final long serialVersionUID = 2231700681270951733L;
+
+ static public final PersistentOrderedSet EMPTY = new PersistentOrderedSet(
+ null, PersistentHashSet.EMPTY, PersistentVector.EMPTY);
+
+ final IPersistentMap _meta;
+ final IPersistentSet items;
+ final IPersistentVector order;
+
+ protected PersistentOrderedSet(IPersistentMap meta, IPersistentSet items,
+ IPersistentVector order) {
+ this._meta = meta;
+ this.items = items;
+ this.order = order;
+ }
+
+ static public PersistentOrderedSet create(ISeq items) {
+ PersistentOrderedSet set = EMPTY;
+ for (; items != null; items = items.next()) {
+ set = (PersistentOrderedSet) set.cons(items.first());
+ }
+ return set;
+ }
+
+ public IPersistentSet disjoin(Object item) throws Exception {
+ if (!contains(item)) {
+ return this;
+ }
+
+ PersistentVector.TransientVector new_order = PersistentVector.EMPTY
+ .asTransient();
+ ISeq s = seq();
+ for (; s != null; s = s.next()) {
+ if (s.first() != item) {
+ new_order = new_order.conj(s.first());
+ }
+ }
+ return new PersistentOrderedSet(_meta, items.disjoin(item),
+ new_order.persistent());
+ }
+
+ public IPersistentSet cons(Object item) {
+ if (contains(item)) {
+ return this;
+ }
+ return new PersistentOrderedSet(_meta,
+ (IPersistentSet) items.cons(item), order.cons(item));
+ }
+
+ public IPersistentCollection empty() {
+ return EMPTY.withMeta(meta());
+ }
+
+ public PersistentOrderedSet withMeta(IPersistentMap meta) {
+ return new PersistentOrderedSet(meta, items, order);
+ }
+
+ public IPersistentMap meta() {
+ return _meta;
+ }
+
+ @Override
+ public String toString() {
+ return RT.printString(this);
+ }
+
+ @Override
+ public Object get(Object key) {
+ return items.get(key);
+ }
+
+ @Override
+ public boolean contains(Object key) {
+ return items.contains(key);
+ }
+
+ @Override
+ public boolean containsAll(Collection c) {
+ for (Object item : c) {
+ if (!contains(item)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public int count() {
+ return order.count();
+ }
+
+ @Override
+ public int size() {
+ return count();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return count() == 0;
+ }
+
+ @Override
+ public ISeq seq() {
+ return RT.seq(order);
+ }
+
+ @Override
+ public Iterator iterator() {
+ return new SeqIterator(seq());
+ }
+
+ @Override
+ public Object invoke(Object arg1) throws Exception {
+ return get(arg1);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (!(obj instanceof Set)) {
+ return false;
+ }
+ Set s = (Set) obj;
+
+ if (s.size() != count()) {
+ return false;
+ }
+ return containsAll(s);
+ }
+
+ @Override
+ public boolean equiv(Object obj) {
+ return equals(obj);
+ }
+
+ @Override
+ public Object[] toArray() {
+ return RT.seqToArray(seq());
+ }
+
+ @Override
+ public Object[] toArray(Object[] a) {
+ if (count() > a.length) {
+ return toArray();
+ }
+
+ ISeq s = seq();
+ for (int i = 0; s != null; ++i, s = s.next()) {
+ a[i] = s.first();
+ }
+ if (a.length > count()) {
+ a[count()] = null;
+ }
+ return a;
+ }
+
+ @Override
+ public boolean add(Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean addAll(Collection c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean retainAll(Collection c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean removeAll(Collection c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public ITransientCollection asTransient() {
+ return new TransientOrderedSet(
+ (ITransientSet) ((PersistentHashSet) items).asTransient(),
+ ((PersistentVector) order).asTransient());
+ }
+
+ static final class TransientOrderedSet extends AFn implements ITransientSet {
+ ITransientSet items;
+ ITransientVector order;
+
+ TransientOrderedSet(ITransientSet items, ITransientVector order) {
+ this.items = items;
+ this.order = order;
+ }
+
+ public IPersistentCollection persistent() {
+ return new PersistentOrderedSet(null,
+ (IPersistentSet) items.persistent(),
+ (IPersistentVector) order.persistent());
+ }
+
+ @Override
+ public ITransientCollection conj(Object obj) {
+ if (items.contains(obj)) {
+ return this;
+ }
+
+ ITransientSet s = (ITransientSet) items.conj(obj);
+ if (s != items) {
+ this.items = s;
+ }
+ ITransientVector v = (ITransientVector) order.conj(obj);
+ if (v != order) {
+ this.order = v;
+ }
+
+ return this;
+ }
+
+ @Override
+ public int count() {
+ return items.count();
+ }
+
+ @Override
+ public boolean contains(Object obj) {
+ return items.contains(obj);
+ }
+
+ @Override
+ public ITransientSet disjoin(Object obj) throws Exception {
+ if (!items.contains(obj)) {
+ return this;
+ }
+ ITransientSet set = items.disjoin(obj);
+ if (set != items) {
+ this.items = set;
+ }
+
+ PersistentVector.TransientVector new_order = PersistentVector.EMPTY
+ .asTransient();
+ ISeq s = order.persistent().seq();
+ for (; s != null; s = s.next()) {
+ if (s.first() != obj) {
+ new_order = new_order.conj(s.first());
+ }
+ }
+ if (order != new_order) {
+ order = new_order;
+ }
+
+ return this;
+ }
+
+ @Override
+ public Object get(Object key) {
+ return items.get(key);
+ }
+ }
}
-
-public void clear(){
- throw new UnsupportedOperationException();
-}
-
-public boolean retainAll(Collection c){
- throw new UnsupportedOperationException();
-}
-
-public boolean removeAll(Collection c){
- throw new UnsupportedOperationException();
-}
-
-}
\ No newline at end of file
--
1.7.4.1
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
