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}