001 package railo.commons.collections; 002 003 import java.util.Map; 004 005 import railo.runtime.type.Collection; 006 import railo.runtime.type.KeyImpl; 007 008 public final class BinaryTreeMap { 009 010 private final BinEntry root=new BinEntry(new DummyKey(),null); 011 012 public Object get(String key) { 013 return get(KeyImpl.init(key)); 014 } 015 016 public Object get(Collection.Key key) { 017 BinEntry e = root; 018 int outer=key.getId(),inner; 019 while(true) { 020 if(e==null) return null; 021 if((inner=e.key.getId())==outer) return e.value; 022 if(inner>outer) e=e.left; 023 else e=e.right; 024 } 025 } 026 027 public Object put(String key, Object value) { 028 return put(KeyImpl.init(key), value); 029 } 030 031 public Object put(Collection.Key key, Object value) { 032 BinEntry e = root; 033 int outer=key.getId(),inner; 034 while(true) { 035 if((inner=e.key.getId())==outer) { 036 return e.value=value; 037 } 038 if(inner>outer) { 039 if(e.left==null) { 040 e.left=new BinEntry(key,value); 041 return value; 042 } 043 e=e.left; 044 } 045 else { 046 if(e.right==null) { 047 e.right=new BinEntry(key,value); 048 return value; 049 } 050 e=e.right; 051 } 052 } 053 } 054 055 class BinEntry implements Map.Entry { 056 057 private Collection.Key key; 058 private Object value; 059 private BinEntry left; 060 private BinEntry right; 061 062 private BinEntry(Collection.Key key, Object value) { 063 this.key=key; 064 this.value=value; 065 } 066 067 /** 068 * @see java.util.Map$Entry#getKey() 069 */ 070 public Object getKey() { 071 return key.getString(); 072 } 073 074 /** 075 * @see java.util.Map$Entry#getString() 076 */ 077 public Object getValue() { 078 return value; 079 } 080 081 /** 082 * @see java.util.Map$Entry#setValue(V) 083 */ 084 public Object setValue(Object value) { 085 Object old=value; 086 this.value=value; 087 return old; 088 } 089 090 /** 091 * @see java.lang.Object#toString() 092 */ 093 public String toString() { 094 return key+"="+value; 095 } 096 097 } 098 099 class DummyKey implements Collection.Key { 100 101 public char charAt(int index) {return 0;} 102 public boolean equalsIgnoreCase(Collection.Key obj) {return false;} 103 public int getId() {return 0;} 104 public String getLowerString() {return null;} 105 public String getString() {return null;} 106 public char lowerCharAt(int index) {return 0;} 107 public String getUpperString() {return null;} 108 public char upperCharAt(int index) {return 0;} 109 110 } 111 }