001    package railo.commons.collections;
002    
003    /**
004     * class to fill objects, objetcs will be sorted by long key.
005     */
006    public final class LongKeyList {
007    
008            private final Pair root;
009            
010            /**
011             * constructor of the class
012             */
013            public LongKeyList() {
014                    root=new Pair();
015            }
016            
017            
018            /**
019             * adds a new object to the stack
020             * @param key key as long
021             * @param value object to fill
022             */
023            public void add(long key, Object value) {
024                    add(key, value, root);
025            }
026    
027            /**
028             * @param key 
029             * @param value
030             * @param parent
031             */
032            private void add(long key, Object value,Pair parent) {
033                    if(parent.value==null) parent.setData(key,value);
034                    else if(key<parent.key) add(key,value,parent.left);
035                    else add(key,value,parent.right);
036                    
037            }
038    
039            /**
040             * @return returns the first object in stack
041             */
042            public Object shift() {
043                    Pair oldest=root;
044                    while(oldest.left!=null && oldest.left.value!=null)oldest=oldest.left;
045                    Object rtn=oldest.value;
046                    oldest.copy(oldest.right);
047                    return rtn;
048            }
049            
050            /**
051             * @return returns the last object in Stack
052             */
053            public Object pop() {
054                    Pair oldest=root;
055                    while(oldest.right!=null && oldest.right.value!=null)oldest=oldest.right;
056                    Object rtn=oldest.value;
057                    oldest.copy(oldest.left);
058                    return rtn;
059            }
060            
061            /**
062             * @param key key to value
063             * @return returns the value to the key
064             */
065            public Object get(long key) {
066                    Pair current=root;
067                    while(true) {
068                            if(current==null || current.key==0) {
069                                    return null;
070                            }
071                            else if(current.key==key) return current.value;
072                            else if(current.key<key) current=current.right;
073                            else if(current.key>key) current=current.left;
074                    }
075            }
076            
077            class Pair {
078                    /**
079                     * key for value
080                     */
081                    public long key;
082                    /**
083                     * value object
084                     */
085                    public Object value;
086                    /**
087                     * left side
088                     */
089                    public Pair left;
090                    /**
091                     * right side
092                     */
093                    public Pair right;
094                    
095    
096                    /**
097                     * sets data to Pair
098                     * @param key
099                     * @param value
100                     */
101                    public void setData(long key, Object value) {
102                            this.key=key;
103                            this.value=value;
104                            left=new Pair();
105                            right=new Pair();
106                    }
107                    
108                    /**
109                     * @param pair
110                     */
111                    public void copy(Pair pair) {
112                            if(pair!=null) {
113                                    this.left=pair.left;
114                                    this.right=pair.right;
115                                    this.value=pair.value;
116                                    this.key=pair.key;
117                            }
118                            else {
119                                    this.left=null;
120                                    this.right=null;
121                                    this.value=null;
122                                    this.key=0;
123                            }
124                    }
125            }
126    }