001/**
002 *
003 * Copyright (c) 2014, the Railo Company Ltd. All rights reserved.
004 *
005 * This library is free software; you can redistribute it and/or
006 * modify it under the terms of the GNU Lesser General Public
007 * License as published by the Free Software Foundation; either 
008 * version 2.1 of the License, or (at your option) any later version.
009 * 
010 * This library is distributed in the hope that it will be useful,
011 * but WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013 * Lesser General Public License for more details.
014 * 
015 * You should have received a copy of the GNU Lesser General Public 
016 * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
017 * 
018 **/
019package lucee.commons.collection;
020
021/**
022 * class to fill objects, objetcs will be sorted by long key.
023 */
024public final class LongKeyList {
025
026        private final Pair root;
027        
028        /**
029         * constructor of the class
030         */
031        public LongKeyList() {
032                root=new Pair();
033        }
034        
035        
036        /**
037         * adds a new object to the stack
038         * @param key key as long
039         * @param value object to fill
040         */
041        public void add(long key, Object value) {
042                add(key, value, root);
043        }
044
045        /**
046         * @param key 
047         * @param value
048         * @param parent
049         */
050        private void add(long key, Object value,Pair parent) {
051                if(parent.value==null) parent.setData(key,value);
052                else if(key<parent.key) add(key,value,parent.left);
053                else add(key,value,parent.right);
054                
055        }
056
057        /**
058         * @return returns the first object in stack
059         */
060        public Object shift() {
061                Pair oldest=root;
062                while(oldest.left!=null && oldest.left.value!=null)oldest=oldest.left;
063                Object rtn=oldest.value;
064                oldest.copy(oldest.right);
065                return rtn;
066        }
067        
068        /**
069         * @return returns the last object in Stack
070         */
071        public Object pop() {
072                Pair oldest=root;
073                while(oldest.right!=null && oldest.right.value!=null)oldest=oldest.right;
074                Object rtn=oldest.value;
075                oldest.copy(oldest.left);
076                return rtn;
077        }
078        
079        /**
080         * @param key key to value
081         * @return returns the value to the key
082         */
083        public Object get(long key) {
084                Pair current=root;
085                while(true) {
086                        if(current==null || current.key==0) {
087                                return null;
088                        }
089                        else if(current.key==key) return current.value;
090                        else if(current.key<key) current=current.right;
091                        else if(current.key>key) current=current.left;
092                }
093        }
094        
095        class Pair {
096                /**
097                 * key for value
098                 */
099                public long key;
100                /**
101                 * value object
102                 */
103                public Object value;
104                /**
105                 * left side
106                 */
107                public Pair left;
108                /**
109                 * right side
110                 */
111                public Pair right;
112                
113
114                /**
115                 * sets data to Pair
116                 * @param key
117                 * @param value
118                 */
119                public void setData(long key, Object value) {
120                        this.key=key;
121                        this.value=value;
122                        left=new Pair();
123                        right=new Pair();
124                }
125                
126                /**
127                 * @param pair
128                 */
129                public void copy(Pair pair) {
130                        if(pair!=null) {
131                                this.left=pair.left;
132                                this.right=pair.right;
133                                this.value=pair.value;
134                                this.key=pair.key;
135                        }
136                        else {
137                                this.left=null;
138                                this.right=null;
139                                this.value=null;
140                                this.key=0;
141                        }
142                }
143        }
144}