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 }