summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/jvm/clojure/runtime/ArrayMap.java169
-rw-r--r--src/jvm/clojure/runtime/HashtableMap.java280
-rw-r--r--src/jvm/clojure/runtime/IMap.java31
-rw-r--r--src/jvm/clojure/runtime/IdentityArrayMap.java27
-rw-r--r--src/jvm/clojure/runtime/IdentityHashtableMap.java38
-rw-r--r--src/jvm/clojure/runtime/ListMap.java252
-rw-r--r--src/jvm/clojure/runtime/PersistentHashMap.java101
-rw-r--r--src/jvm/clojure/runtime/RBTree.java759
8 files changed, 0 insertions, 1657 deletions
diff --git a/src/jvm/clojure/runtime/ArrayMap.java b/src/jvm/clojure/runtime/ArrayMap.java
deleted file mode 100644
index 49dec167..00000000
--- a/src/jvm/clojure/runtime/ArrayMap.java
+++ /dev/null
@@ -1,169 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- **/
-
-package org.clojure.runtime;
-
-import java.util.Iterator;
-
-/**
- * Simple implementation of persistent map on an array
-
- * Note that instances of this class are constant values
- * i.e. add/remove etc return new values
- *
- * Copies array on every change, so only appropriate for _very_small_ maps
- *
- * null keys and values are ok, but you won't be able to distinguish a null value via get - use contains/find
- */
-
-public class ArrayMap implements IMap {
-
-final Object[] array;
-
-public ArrayMap(){
- this.array = RT.EMPTY_ARRAY;
-}
-
-/**
- * This ctor captures/aliases the passed array, so do not modify later
- * @param init {key1,val1,key2,val2,...}
- */
-public ArrayMap(Object[] init){
- this.array = init;
-}
-
-public int count() {
- return array.length/2;
-}
-
-public boolean contains(Object key){
- return indexOf(key) >= 0;
-}
-
-public IMapEntry find(Object key) {
- int i = indexOf(key);
- if(i >= 0)
- return new Iter(array,i);
- return null;
-}
-
-public IMap add(Object key) {
-
- return put(key,null);
-}
-
-public IMap put(Object key, Object val) {
- int i = indexOf(key);
- Object[] newArray;
- if(i >= 0) //already have key, same-sized replacement
- {
- if(array[i+1] == val) //no change, no op
- return this;
- newArray = array.clone();
- newArray[i+1] = val;
- }
- else //didn't have key, grow
- {
- newArray = new Object[array.length + 2];
- if(array.length > 0)
- System.arraycopy(array,0,newArray,2,array.length);
- newArray[0] = key;
- newArray[1] = val;
- }
- return new ArrayMap(newArray);
-}
-
-public IMap remove(Object key) {
- int i = indexOf(key);
- if(i >= 0) //have key, will remove
- {
- Object[] newArray = new Object[array.length - 2];
- for(int s=0,d=0;s<array.length;s += 2)
- {
- if(!equalKey(array[s],key)) //skip removal key
- {
- newArray[d] = array[s];
- newArray[d+1] = array[s+1];
- d += 2;
- }
- }
- return new ArrayMap(newArray);
- }
- //don't have key, no op
- return this;
-}
-
-public Object get(Object key) {
- int i = indexOf(key);
- if(i >= 0)
- return array[i + 1];
- return null;
-}
-
-public int capacity() {
- return count();
-}
-
-int indexOf(Object key){
- for(int i=0;i<array.length;i+=2)
- {
- if(equalKey(array[i],key))
- return i;
- }
- return -1;
-}
-
-boolean equalKey(Object k1,Object k2){
- if(k1 == null)
- return k2 == null;
- return k1.equals(k2);
-}
-
-public Iterator iterator() {
- return new Iter(array);
-}
-
-static class Iter implements Iterator,IMapEntry{
- Object[] array;
- int i;
-
- //for iterator
- Iter(Object[] array){
- this(array,-2);
- }
-
- //for find
- Iter(Object[] array, int i){
- this.array = array;
- this.i = i;
- }
-
- public boolean hasNext() {
- return i < array.length - 2;
- }
-
- public Object next() {
- i+=2;
- return this;
- }
-
- public void remove() {
- throw new UnsupportedOperationException();
- }
-
- public Object key() {
- return array[i];
- }
-
- public Object val() {
- return array[i+1];
- }
-}
-}
diff --git a/src/jvm/clojure/runtime/HashtableMap.java b/src/jvm/clojure/runtime/HashtableMap.java
deleted file mode 100644
index a96a9761..00000000
--- a/src/jvm/clojure/runtime/HashtableMap.java
+++ /dev/null
@@ -1,280 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- **/
-
-package org.clojure.runtime;
-
-import java.util.Iterator;
-import java.math.BigInteger;
-
-public class HashtableMap implements IMap, Iterable {
-
-static final float FILL_FACTOR = 0.75f;
-
-final PersistentArray array;
-final int _count;
-final int growAtCount;
-
-public HashtableMap(int initialCapacity) {
- array = new PersistentArray(calcPrimeCapacity(initialCapacity));
- _count = 0;
- this.growAtCount = (int) (this.array.length()*FILL_FACTOR);
-}
-
-/**
- * @param init {key1,val1,key2,val2,...}
- */
-public HashtableMap(Object[] init){
- //start halfway to a rehash
- PersistentArray narray = new PersistentArray(calcPrimeCapacity(init.length));
- for(int i=0;i<init.length;i+=2)
- {
- narray = doPut(bucketFor(init[i],narray),init[i], init[i + 1],narray);
- }
- this.array = narray;
- this._count = init.length/2; //hmmm... presumes no dupe keys in init
- this.growAtCount = (int) (this.array.length()*FILL_FACTOR);
-}
-
-HashtableMap(int count,PersistentArray array) {
- this._count = count;
- this.array = array;
- this.growAtCount = (int) (this.array.length()*FILL_FACTOR);
-}
-
-HashtableMap(int count,PersistentArray array,int growAt) {
- this._count = count;
- this.array = array;
- this.growAtCount = growAt;
-}
-
-int calcPrimeCapacity(int capacity) {
- return BigInteger.valueOf((long) (capacity/FILL_FACTOR)).nextProbablePrime().intValue();
-}
-
-public int count() {
- return _count;
-}
-
-public boolean contains(Object key) {
- IMap entries = entriesFor(key);
- return entries != null && entries.contains(key);
-}
-
-public IMapEntry find(Object key) {
- IMap entries = entriesFor(key);
- if(entries != null)
- return entries.find(key);
- return null;
-}
-
-public IMap add(Object key) {
- return put(key, null);
-}
-
-public IMap put(Object key, Object val) {
- if(_count > growAtCount)
- return grow().put(key, val);
- int i = bucketFor(key,array);
- int incr = 1;
- PersistentArray newArray = doPut(i, key, val, array);
- if(newArray == array)
- return this;
- if(array.get(i) != null && ((IMap)newArray.get(i)).count() == ((IMap)array.get(i)).count()) //key already there, no growth
- incr = 0;
- return create(_count + incr, newArray, growAtCount);
-}
-
-PersistentArray doPut(int i,Object key,Object val,PersistentArray array){
- IMap entries = (IMap) array.get(i);
- IMap newEntries;
- if (entries != null)
- {
- newEntries = entries.put(key, val);
- if(newEntries == entries) //already there with same value, no op
- return array;
- }
- else
- newEntries = createListMap(key, val);
- //newEntries = createArrayMap(new Object[]{key, val});
-
- return array.set(i, newEntries);
-}
-
-public IMap remove(Object key) {
- int i = bucketFor(key,array);
- IMap entries = (IMap) array.get(i);
- if (entries != null)
- {
- IMap newEntries = entries.remove(key);
- if (newEntries != entries)
- return create(_count - 1, array.set(i, newEntries));
- }
- //not there, no op
- return this;
-}
-
-public Object get(Object key) {
- IMap entries = entriesFor(key);
- if(entries != null)
- return entries.get(key);
- return null;
-}
-
-public int capacity() {
- return array.length();
-}
-
-public Iterator<IMapEntry> iterator() {
- return new Iter(array);
-}
-
-
-IMap grow(){
- PersistentArray newArray = new PersistentArray(calcPrimeCapacity(_count * 2));
- for (Object o : this)
- {
- IMapEntry e = (IMapEntry) o;
- newArray = doPut(bucketFor(e.key(),newArray),e.key(), e.val(),newArray);
- }
- return create(_count,newArray);
-}
-
-/*
-static class Iter implements Iterator, IMapEntry{
- PersistentArray buckets;
-
- int b;
-
- Object[] nextEntries;
-
- int nextE;
-
- Object[] entries;
-
- int e;
-
- Iter(PersistentArray buckets){
- this.buckets = buckets;
- this.b = -1;
- nextBucket();
- }
-
- private void nextBucket() {
- nextEntries = null;
- nextE = 0;
- for(b = b+1;b<buckets.length();b++)
- {
- ArrayMap a = (ArrayMap) buckets.get(b);
- if(a != null)
- {
- nextEntries = a.array;
- break;
- }
- }
- }
-
- public boolean hasNext() {
- return nextEntries != null;
- }
-
- public Object next() {
- entries = nextEntries;
- e = nextE;
- nextE += 2;
- if(nextE >= nextEntries.length)
- nextBucket();
- return this;
- }
-
- public void remove() {
- throw new UnsupportedOperationException();
- }
-
- public Object key() {
- return entries[e];
- }
-
- public Object val() {
- return entries[e+1];
- }
-
-}
-*/
-static class Iter implements Iterator{
- PersistentArray buckets;
- int b;
- ListMap e;
-
- Iter(PersistentArray buckets){
- this.buckets = buckets;
- this.b = -1;
- nextBucket();
- }
-
- private void nextBucket() {
- e = null;
- for(b = b+1;b<buckets.length();b++)
- {
- ListMap a = (ListMap) buckets.get(b);
- if(a != null && a != ListMap.EMPTY)
- {
- e = a;
- break;
- }
- }
- }
-
- public boolean hasNext() {
- return e != null;
- }
-
- public Object next() {
- ListMap ret = e;
- e = e.rest();
- if(e == ListMap.EMPTY)
- nextBucket();
- return ret;
- }
-
- public void remove() {
- throw new UnsupportedOperationException();
- }
-}
-
-final IMap entriesFor(Object key){
- return (IMap) array.get(bucketFor(key,array));
-}
-
-static int bucketFor(Object key, PersistentArray array) {
- return (key.hashCode() & 0x7fffffff)%array.length();
-}
-
-IMap create(int capacity) {
- return new HashtableMap(capacity);
-}
-
-IMap create(int count,PersistentArray array) {
- return new HashtableMap(count, array);
-}
-
-private IMap create(int i, PersistentArray newArray, int growAtCount){
- return new HashtableMap(i, newArray, growAtCount);
-}
-
-
-IMap createArrayMap(Object[] init) {
- return new ArrayMap(init);
-}
-
-private IMap createListMap(Object key, Object val){
- return ListMap.create(key,val);
-}
-
-}
diff --git a/src/jvm/clojure/runtime/IMap.java b/src/jvm/clojure/runtime/IMap.java
deleted file mode 100644
index 015df00d..00000000
--- a/src/jvm/clojure/runtime/IMap.java
+++ /dev/null
@@ -1,31 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- */
-
-package org.clojure.runtime;
-
-
-public interface IMap extends Iterable {
-
-int count();
-
-boolean contains(Object key);
-
-IMapEntry find(Object key);
-
-IMap add(Object key);
-
-IMap put(Object key, Object val);
-
-IMap remove(Object key);
-
-Object get(Object key);
-
-int capacity();
-}
diff --git a/src/jvm/clojure/runtime/IdentityArrayMap.java b/src/jvm/clojure/runtime/IdentityArrayMap.java
deleted file mode 100644
index ed0c7106..00000000
--- a/src/jvm/clojure/runtime/IdentityArrayMap.java
+++ /dev/null
@@ -1,27 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- **/
-
-package org.clojure.runtime;
-
-/**
- * ArrayMap using identity (==) comparison instead of equals
- */
-public class IdentityArrayMap extends ArrayMap{
-public IdentityArrayMap() {
-}
-
-public IdentityArrayMap(Object[] init) {
- super(init);
-}
-
-boolean equalKey(Object k1, Object k2) {
- return k1 == k2;
-}
-}
diff --git a/src/jvm/clojure/runtime/IdentityHashtableMap.java b/src/jvm/clojure/runtime/IdentityHashtableMap.java
deleted file mode 100644
index 71d93eeb..00000000
--- a/src/jvm/clojure/runtime/IdentityHashtableMap.java
+++ /dev/null
@@ -1,38 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- **/
-
-package org.clojure.runtime;
-
-public class IdentityHashtableMap extends HashtableMap{
-
-public IdentityHashtableMap(int initialCapacity) {
- super(initialCapacity);
-}
-
-public IdentityHashtableMap(Object[] init) {
- super(init);
-}
-
-IdentityHashtableMap(int count, PersistentArray array) {
- super(count, array);
-}
-
-IMap create(int capacity) {
- return new IdentityHashtableMap(capacity);
-}
-
-IMap create(int count, PersistentArray array) {
- return new IdentityHashtableMap(count, array);
-}
-
-IMap createArrayMap(Object[] init) {
- return new IdentityArrayMap(init);
-}
-}
diff --git a/src/jvm/clojure/runtime/ListMap.java b/src/jvm/clojure/runtime/ListMap.java
deleted file mode 100644
index 16c77e9c..00000000
--- a/src/jvm/clojure/runtime/ListMap.java
+++ /dev/null
@@ -1,252 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- **/
-
-/* rich Jun 6, 2006 */
-
-package org.clojure.runtime;
-
-import java.util.Iterator;
-
-/**
- * Immplementation of persistent map on a linked list
-
- * Note that instances of this class are constant values
- * i.e. add/remove etc return new values
- *
- * Lookups/changes are linear, so only appropriate for _very_small_ maps
- * ArrayMap is generally faster, but this class avoids the double allocation,
- * and so is better/faster as a bucket for hash tables
- *
- * null keys and values are ok, but you won't be able to distinguish a null value via get - use contains/find
- */
-public class ListMap implements IMap, IMapEntry
-{
-
-static public ListMap EMPTY = new ListMap();
-
-static public ListMap create(Object key, Object val){
- return new Tail(key, val);
-}
-
-public Object key(){
- return null;
-}
-
-public Object val(){
- return null;
-}
-
-ListMap rest(){
- return this;
- }
-
-public int count(){
- return 0;
-}
-
-public boolean contains(Object key){
- return false;
-}
-
-public IMapEntry find(Object key){
- return null;
-}
-
-public IMap add(Object key){
- return put(key, null);
-}
-
-public ListMap put(Object key, Object val){
- return new Tail(key, val);
-}
-
-public ListMap remove(Object key){
- return this;
-}
-
-public Object get(Object key){
- return null;
-}
-
-public int capacity(){
- return 0;
-}
-
-static class Iter implements Iterator{
- ListMap e;
-
- Iter(ListMap e)
- {
- this.e = e;
- }
-
- public boolean hasNext(){
- return e != EMPTY;
- }
-
- public Object next(){
- ListMap ret = e;
- e = e.rest();
- return ret;
- }
-
- public void remove(){
- throw new UnsupportedOperationException();
- }
-}
-
-public Iterator iterator(){
- return new Iter(this);
-}
-
-static class Tail extends ListMap{
- final Object _key;
- final Object _val;
-
- Tail(Object key,Object val){
- this._key = key;
- this._val = val;
- }
-
- ListMap rest(){
- return EMPTY;
- }
-
- public int count(){
- return 1;
- }
-
- public Object get(Object key){
- if(equalKey(key,_key))
- return _val;
- return null;
- }
-
- public int capacity(){
- return 1;
- }
-
- public Object key(){
- return _key;
- }
-
- public Object val(){
- return _val;
- }
-
- public boolean contains(Object key){
- return equalKey(key,_key);
- }
-
- public IMapEntry find(Object key){
- if(equalKey(key,_key))
- return this;
- return null;
- }
-
- public ListMap put(Object key, Object val){
- if(equalKey(key,_key)) //replace
- {
- if(val == _val)
- return this;
- return new Tail(key,val);
- }
- return new Link(key,val,this);
- }
-
- public ListMap remove(Object key){
- if(equalKey(key,_key))
- return EMPTY;
- return this;
- }
-}
-
-static class Link extends ListMap{
- final Object _key;
- final Object _val;
- final ListMap _rest;
-
- Link(Object key,Object val,ListMap rest){
- this._key = key;
- this._val = val;
- this._rest = rest;
- }
-
- public Object key(){
- return _key;
- }
-
- public Object val(){
- return _val;
- }
-
- ListMap rest(){
- return _rest;
- }
-
- public int count(){
- return 1 + _rest.count();
- }
-
- public boolean contains(Object key){
- return find(key) != null;
- }
-
- public IMapEntry find(Object key){
- if(equalKey(key,_key))
- return this;
- return _rest.find(key);
- }
-
- public ListMap put(Object key, Object val){
- IMapEntry e = find(key);
- if(e != null)
- {
- if(e.val() == val)
- return this;
- return create(_key,_val,remove(key));
- }
- return new Link(key,val,this);
- }
-
- public ListMap remove(Object key){
- if(equalKey(key,_key))
- return _rest;
- ListMap r = _rest.remove(key);
- if(r == _rest) //not there
- return this;
- return create(_key,_val,r);
- }
-
- public Object get(Object key){
- IMapEntry e = find(key);
- if(e != null)
- return e.val();
- return null;
- }
-
- public int capacity(){
- return count();
- }
-
- ListMap create(Object k,Object v,ListMap r){
- if(r == EMPTY)
- return new Tail(k,v);
- return new Link(k, v, r);
- }
-
-}
-
-boolean equalKey(Object k1,Object k2){
- if(k1 == null)
- return k2 == null;
- return k1.equals(k2);
-}
-}
diff --git a/src/jvm/clojure/runtime/PersistentHashMap.java b/src/jvm/clojure/runtime/PersistentHashMap.java
deleted file mode 100644
index f4ac6330..00000000
--- a/src/jvm/clojure/runtime/PersistentHashMap.java
+++ /dev/null
@@ -1,101 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- **/
-
-package org.clojure.runtime;
-
-import java.util.Iterator;
-
-public class PersistentHashMap implements IMap, Iterable{
-
-IMap impl;
-static final int CAPACITY_THRESHOLD = 42;
-
-public PersistentHashMap(Object[] init){
- if(init.length/2 < CAPACITY_THRESHOLD)
- impl = createArrayMap(init);
- impl = createHashtableMap(init);
-}
-
-public PersistentHashMap(int initialCapacity){
- if(initialCapacity < CAPACITY_THRESHOLD)
- impl = createArrayMap();
- else
- impl = createHashtableMap(initialCapacity);
-}
-
-PersistentHashMap(IMap impl){
- this.impl = impl;
-}
-
-public int count() {
- return impl.count();
-}
-
-public boolean contains(Object key) {
- return impl.contains(key);
-}
-
-public IMapEntry find(Object key) {
- return impl.find(key);
-}
-
-public IMap add(Object key) {
- return put(key, null);
-}
-
-public IMap put(Object key, Object val) {
- IMap newImpl = impl.put(key,val);
- if(newImpl.capacity() == CAPACITY_THRESHOLD)
- {
- newImpl = createHashtableMap(((ArrayMap)newImpl).array);
- }
- return create(newImpl);
-}
-
-public IMap remove(Object key) {
- IMap newImpl = impl.remove(key);
- if(newImpl != impl)
- return create(newImpl);
- return this;
-}
-
-public Object get(Object key) {
- return impl.get(key);
-}
-
-public int capacity() {
- return impl.capacity();
-}
-
-public Iterator iterator() {
- return ((Iterable)impl).iterator();
-}
-
-public IMap create(IMap impl) {
- return new PersistentHashMap(impl);
-}
-
-public ArrayMap createArrayMap(Object[] init) {
- return new ArrayMap(init);
-}
-
-private IMap createArrayMap() {
- return new ArrayMap();
-}
-
-private IMap createHashtableMap(Object[] init) {
- return new HashtableMap(init);
-}
-
-private IMap createHashtableMap(int initialCapacity) {
- return new HashtableMap(initialCapacity);
-}
-
-}
diff --git a/src/jvm/clojure/runtime/RBTree.java b/src/jvm/clojure/runtime/RBTree.java
deleted file mode 100644
index 6aec53e2..00000000
--- a/src/jvm/clojure/runtime/RBTree.java
+++ /dev/null
@@ -1,759 +0,0 @@
-/**
- * Copyright (c) Rich Hickey. All rights reserved.
- * The use and distribution terms for this software are covered by the
- * Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
- * which can be found in the file CPL.TXT 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.
- **/
-
-/* rich May 20, 2006 */
-
-package org.clojure.runtime;
-
-import java.util.*;
-
-/**
- * Persistent Red Black Tree
- * Note that instances of this class are constant values
- * i.e. add/remove etc return new values
- * <p/>
- * See Okasaki, Kahrs, Larsen et al
- */
-
-public class RBTree implements Iterable, IMap {
-
-public final Comparator comp;
-public final Node tree;
-public final int _count;
-
-public RBTree(){
- this(null);
-}
-
-public RBTree(Comparator comp){
- this.comp = comp;
- tree = null;
- _count = 0;
-}
-
-public boolean contains(Object key){
- return find(key) != null;
-}
-
-public RBTree add(Object key){
- return put(key, null);
-}
-
-public RBTree put(Object key, Object val){
- Box found = new Box(null);
- Node t = add(tree, key, val, found);
- if(t == null) //null == already contains key
- {
- Node foundNode = (Node) found.val;
- if(foundNode.val() == val) //note only get same collection on identity of val, not equals()
- return this;
- return new RBTree(comp, replace(tree, key, val), _count);
- }
- return new RBTree(comp, t.blacken(), _count + 1);
-}
-
-
-public RBTree remove(Object key){
- Box found = new Box(null);
- Node t = remove(tree, key, found);
- if(t == null)
- {
- if(found.val == null)//null == doesn't contain key
- return this;
- //empty
- return new RBTree(comp);
- }
- return new RBTree(comp, t.blacken(), _count - 1);
-}
-
-
-public NodeIterator iterator(){
- return new NodeIterator(tree, true);
-}
-
-public NodeIterator reverseIterator(){
- return new NodeIterator(tree, false);
-}
-
-public Iterator keys(){
- return keys(iterator());
-}
-
-public Iterator vals(){
- return vals(iterator());
-}
-
-public Iterator keys(NodeIterator it){
- return new KeyIterator(it);
-}
-
-public Iterator vals(NodeIterator it){
- return new ValIterator(it);
-}
-
-public Object minKey(){
- Node t = min();
- return t!=null?t.key:null;
-}
-
-public Node min(){
- Node t = tree;
- if(t != null)
- {
- while(t.left() != null)
- t = t.left();
- }
- return t;
-}
-
-public Object maxKey(){
- Node t = max();
- return t!=null?t.key:null;
-}
-
-public Node max(){
- Node t = tree;
- if(t != null)
- {
- while(t.right() != null)
- t = t.right();
- }
- return t;
-}
-
-public int depth(){
- return depth(tree);
-}
-
-int depth(Node t){
- if(t == null)
- return 0;
- return 1 + Math.max(depth(t.left()), depth(t.right()));
-}
-
-public Object get(Object key){
- Node n = find(key);
- return (n != null) ? n.val() : null;
-}
-
-public int capacity() {
- return _count;
-}
-
-public int count() {
- return _count;
-}
-
-public Node find(Object key){
- Node t = tree;
- while(t != null)
- {
- int c = compare(key, t.key);
- if(c == 0)
- return t;
- else if(c < 0)
- t = t.left();
- else
- t = t.right();
- }
- return t;
-}
-
-int compare(Object k1, Object k2){
- if(comp != null)
- return comp.compare(k1, k2);
- return ((Comparable) k1).compareTo(k2);
-}
-
-Node add(Node t, Object key, Object val, Box found){
- if(t == null)
- {
- if(val == null)
- return new Red(key);
- return new RedVal(key, val);
- }
- int c = compare(key, t.key);
- if(c == 0)
- {
- found.val = t;
- return null;
- }
- Node ins = c < 0 ? add(t.left(), key, val, found) : add(t.right(), key, val, found);
- if(ins == null) //found below
- return null;
- if(c < 0)
- return t.addLeft(ins);
- return t.addRight(ins);
-}
-
-Node remove(Node t, Object key, Box found){
- if(t == null)
- return null; //not found indicator
- int c = compare(key, t.key);
- if(c == 0)
- {
- found.val = t;
- return append(t.left(), t.right());
- }
- Node del = c < 0 ? remove(t.left(), key, found) : remove(t.right(), key, found);
- if(del == null && found.val == null) //not found below
- return null;
- if(c < 0)
- {
- if(t.left() instanceof Black)
- return balanceLeftDel(t.key, t.val(), del, t.right());
- else
- return red(t.key, t.val(), del, t.right());
- }
- if(t.right() instanceof Black)
- return balanceRightDel(t.key, t.val(), t.left(), del);
- return red(t.key, t.val(), t.left(), del);
-// return t.removeLeft(del);
-// return t.removeRight(del);
-}
-
-static Node append(Node left, Node right){
- if(left == null)
- return right;
- else if(right == null)
- return left;
- else if(left instanceof Red)
- {
- if(right instanceof Red)
- {
- Node app = append(left.right(), right.left());
- if(app instanceof Red)
- return red(app.key, app.val(),
- red(left.key, left.val(), left.left(), app.left()),
- red(right.key, right.val(), app.right(), right.right()));
- else
- return red(left.key, left.val(), left.left(), red(right.key, right.val(), app, right.right()));
- }
- else
- return red(left.key, left.val(), left.left(), append(left.right(), right));
- }
- else if(right instanceof Red)
- return red(right.key, right.val(), append(left, right.left()), right.right());
- else //black/black
- {
- Node app = append(left.right(), right.left());
- if(app instanceof Red)
- return red(app.key, app.val(),
- black(left.key, left.val(), left.left(), app.left()),
- black(right.key, right.val(), app.right(), right.right()));
- else
- return balanceLeftDel(left.key, left.val(), left.left(), black(right.key, right.val(), app, right.right()));
- }
-}
-
-static Node balanceLeftDel(Object key, Object val, Node del, Node right){
- if(del instanceof Red)
- return red(key, val, del.blacken(), right);
- else if(right instanceof Black)
- return rightBalance(key, val, del, right.redden());
- else if(right instanceof Red && right.left() instanceof Black)
- return red(right.left().key, right.left().val(),
- black(key, val, del, right.left().left()),
- rightBalance(right.key, right.val(), right.left().right(), right.right().redden()));
- else
- throw new UnsupportedOperationException("Invariant violation");
-}
-
-static Node balanceRightDel(Object key, Object val, Node left, Node del){
- if(del instanceof Red)
- return red(key, val, lef