1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.millscript.commons.util.map;
22
23 import org.millscript.commons.util.IList;
24 import org.millscript.commons.util.IMap;
25 import org.millscript.commons.util.ITreeMapNode;
26 import org.millscript.commons.util.Maplet;
27 import org.millscript.commons.util.comparators.MapletKeyComparator;
28 import org.millscript.commons.util.comparators.NullLowComparableComparator;
29
30 import java.io.Serializable;
31 import java.util.Arrays;
32 import java.util.Comparator;
33
34 /**
35 *
36 */
37 public class IBinaryTreeMap< K extends Comparable< K >, V > extends AbstractITreeMap< K, V, ITreeMapNode< K, V > > implements Cloneable, Serializable {
38
39 /**
40 * This is the ID from the release 0.1.0 for future compatibility.
41 */
42 private static final long serialVersionUID = -999934177514892337L;
43
44 public static class Node< K, V > extends AbstractIBinaryTreeMapNode< K, V > implements Serializable {
45
46 /**
47 * This is the ID from the release 0.1.0 for future compatibility.
48 */
49 private static final long serialVersionUID = 8730722525448844454L;
50
51 /**
52 * The maplet key stored at this node.
53 */
54 final K key;
55
56 /**
57 * The maplet value stored at this node.
58 */
59 final V value;
60
61 public Node( final AbstractIBinaryTreeMapNode< K, V > p, final K k, final V v ) {
62 super( p );
63 this.key = k;
64 this.value = v;
65 }
66
67 public Node( final AbstractIBinaryTreeMapNode< K, V > p, final Maplet< K, V > maplet ) {
68 super( p );
69 this.key = maplet.getKey();
70 this.value = maplet.getValue();
71 }
72
73 public Node( final Node< K, V > p, final Maplet< K, V >[] mapletArray, final int first, final int last ) {
74 super( p );
75
76
77
78
79
80
81
82
83
84
85
86 final int zeroBasedCentralIndex = ( last + first - 1 ) / 2;
87 final Maplet< K, V > thisNodeMaplet = mapletArray[ zeroBasedCentralIndex ];
88 this.key = thisNodeMaplet.getKey();
89 this.value = thisNodeMaplet.getValue();
90
91
92
93
94
95 if ( zeroBasedCentralIndex >= first ) {
96
97 this.setLeft(
98 new Node< K, V >( this, mapletArray, first, zeroBasedCentralIndex )
99 );
100 }
101
102
103 final int lastRight = zeroBasedCentralIndex + 2;
104
105 if ( lastRight <= last ) {
106
107 this.setRight(
108 new Node< K, V >( this, mapletArray, lastRight, last )
109 );
110 }
111 }
112
113 /**
114 * @see org.millscript.commons.util.ITreeMapNode#deepCopy()
115 */
116 @Override
117 public Node< K, V > deepCopy() {
118 final Node< K, V > copy = new Node< K, V >( this.getParent(), this.key, this.value );
119 if ( this.getLeft() != null ) {
120 copy.setLeft( this.getLeft().deepCopy() );
121 }
122 if ( this.getRight() != null ) {
123 copy.setRight( this.getRight().deepCopy() );
124 }
125 return copy;
126 }
127
128 /**
129 * @see org.millscript.commons.util.Maplet#getKey()
130 */
131 public K getKey() {
132 return this.key;
133 }
134
135 /**
136 * @see org.millscript.commons.util.Maplet#getValue()
137 */
138 public V getValue() {
139 return this.value;
140 }
141
142 }
143
144 /**
145 * The comparator for this map.
146 */
147 private final Comparator< K > comparator;
148
149 /**
150 * The root node in the tree.
151 */
152 private ITreeMapNode< K, V > root;
153
154 /**
155 * Constructs a new immutable binary tree map, with the default
156 * {@link NullLowComparableComparator} comparator.
157 */
158 public IBinaryTreeMap() {
159 this.comparator = new NullLowComparableComparator< K >();
160 }
161
162 /**
163 * Constructs a new immutable tree map which contains all the mappings
164 * from the specified map, using the default
165 * {@link NullLowComparableComparator} comparator.
166 *
167 * @param map the <code>Map</code> to copy mappings from
168 */
169 @SuppressWarnings("unchecked")
170 public IBinaryTreeMap( final IMap< K, V > map ) {
171 this( new NullLowComparableComparator< K >(), map );
172 }
173
174 /**
175 * Constructs a new immutable tree map which contains all the mappings
176 * from the specified map, using the specified comparator. If the specified
177 * comparator cannot handle the range of keys in the specified map an
178 * exception will be thrown during construction.
179 *
180 * @param comp the <code>Comparator</code> to order this map with
181 * @param map the <code>Map</code> to copy mappings from
182 * @throws ClassCastException if any of the keys in the specified map
183 * cannot be compared using the specified comparator
184 * @throws NullPointerException if any of the keys in the specified map are
185 * <code>null</code> and the specified comparator cannot handle
186 * <code>null</code> values
187 */
188 @SuppressWarnings("unchecked")
189 public IBinaryTreeMap( final Comparator< K > comp, final IMap< K, V > map ) {
190 this.comparator = comp;
191 if ( map.size() != 0 ) {
192
193 final IList< Maplet< K, V > > mapletList = map.mapletList( true );
194
195 final Maplet< K, V >[] mapletArray = mapletList.toArray( new Maplet[ mapletList.size() ] );
196
197 Arrays.sort( mapletArray, new MapletKeyComparator< K >( this.comparator ) );
198
199 this.root = new Node< K, V >( null, mapletArray, 1, mapletArray.length );
200 }
201 }
202
203 /**
204 * @see java.lang.Object#clone()
205 */
206 @Override
207 public Object clone() throws CloneNotSupportedException {
208
209 return super.clone();
210 }
211
212 /**
213 * @see org.millscript.commons.util.ITreeMap#find(null)
214 */
215 public ITreeMapNode< K, V > find( final K key ) {
216 return this.root == null ? null : this.root.find( this.comparator, key );
217 }
218
219 /**
220 * @see org.millscript.commons.util.ITreeMap#getComparator()
221 */
222 public Comparator< K > getComparator() {
223 return this.comparator;
224 }
225
226 /**
227 * @see org.millscript.commons.util.map.AbstractITreeMap#getRootNode()
228 */
229 public ITreeMapNode< K, V > getRootNode() {
230 return this.root;
231 }
232
233 }