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    }