1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.trie;
18
19 import java.io.Serializable;
20 import java.util.AbstractMap;
21 import java.util.Map;
22 import java.util.Objects;
23
24 import org.apache.commons.collections4.Trie;
25
26
27
28
29
30
31
32
33
34 public abstract class AbstractBitwiseTrie<K, V> extends AbstractMap<K, V>
35 implements Trie<K, V>, Serializable {
36
37
38
39
40 abstract static class BasicEntry<K, V> implements Map.Entry<K, V>, Serializable {
41
42 private static final long serialVersionUID = -944364551314110330L;
43
44 protected K key;
45
46 protected V value;
47
48 BasicEntry(final K key) {
49 this.key = key;
50 }
51
52 BasicEntry(final K key, final V value) {
53 this.key = key;
54 this.value = value;
55 }
56
57 @Override
58 public boolean equals(final Object o) {
59 if (o == this) {
60 return true;
61 }
62 if (!(o instanceof Map.Entry)) {
63 return false;
64 }
65
66 final Map.Entry<?, ?> other = (Map.Entry<?, ?>) o;
67 if (compare(key, other.getKey())
68 && compare(value, other.getValue())) {
69 return true;
70 }
71 return false;
72 }
73
74 @Override
75 public K getKey() {
76 return key;
77 }
78
79 @Override
80 public V getValue() {
81 return value;
82 }
83
84 @Override
85 public int hashCode() {
86 return (getKey() == null ? 0 : getKey().hashCode()) ^
87 (getValue() == null ? 0 : getValue().hashCode());
88 }
89
90
91
92
93 public V setKeyValue(final K key, final V value) {
94 this.key = key;
95 return setValue(value);
96 }
97
98 @Override
99 public V setValue(final V value) {
100 final V previous = this.value;
101 this.value = value;
102 return previous;
103 }
104
105 @Override
106 public String toString() {
107 return key + "=" + value;
108 }
109 }
110
111 private static final long serialVersionUID = 5826987063535505652L;
112
113
114
115
116 static boolean compare(final Object a, final Object b) {
117 return Objects.equals(a, b);
118 }
119
120
121
122
123 private final KeyAnalyzer<? super K> keyAnalyzer;
124
125
126
127
128
129
130 protected AbstractBitwiseTrie(final KeyAnalyzer<? super K> keyAnalyzer) {
131 this.keyAnalyzer = Objects.requireNonNull(keyAnalyzer, "keyAnalyzer");
132 }
133
134
135
136
137 final int bitIndex(final K key, final K foundKey) {
138 return keyAnalyzer.bitIndex(key, 0, lengthInBits(key), foundKey, 0, lengthInBits(foundKey));
139 }
140
141
142
143
144
145
146 final int bitsPerElement() {
147 return keyAnalyzer.bitsPerElement();
148 }
149
150
151
152
153 @SuppressWarnings("unchecked")
154 final K castKey(final Object key) {
155 return (K) key;
156 }
157
158
159
160
161 final boolean compareKeys(final K key, final K other) {
162 if (key == null) {
163 return other == null;
164 }
165 if (other == null) {
166 return false;
167 }
168
169 return keyAnalyzer.compare(key, other) == 0;
170 }
171
172
173
174
175
176 protected KeyAnalyzer<? super K> getKeyAnalyzer() {
177 return keyAnalyzer;
178 }
179
180
181
182
183
184
185 final boolean isBitSet(final K key, final int bitIndex, final int lengthInBits) {
186 if (key == null) {
187 return false;
188 }
189 return keyAnalyzer.isBitSet(key, bitIndex, lengthInBits);
190 }
191
192
193
194
195
196
197 final int lengthInBits(final K key) {
198 if (key == null) {
199 return 0;
200 }
201
202 return keyAnalyzer.lengthInBits(key);
203 }
204
205 @Override
206 public String toString() {
207 final StringBuilder buffer = new StringBuilder();
208 buffer.append("Trie[").append(size()).append("]={\n");
209 for (final Map.Entry<K, V> entry : entrySet()) {
210 buffer.append(" ").append(entry).append("\n");
211 }
212 buffer.append("}\n");
213 return buffer.toString();
214 }
215 }