Source code: jtemporal/TreeTemporalMultiMap.java
1 /*
2 Copyright (C) 2002 Thomas A Beck (http://thomas.beck.name)
3
4 This library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Lesser General Public
6 License as published by the Free Software Foundation; either
7 version 2.1 of the License, or (at your option) any later version.
8
9 This library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public
15 License along with this library; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
17
18 package jtemporal;
19
20 import java.util.*;
21 import jtemporal.util.*;
22
23 /**
24 * Maintains internally a TreeMap over the periods and an HashMap over the values
25 * so that query performances are acceptable for queries in both dimensions even when
26 * the collection is very large. <BR><BR>
27 * <b>Note: this implementation is not synchronized.</b> If multiple
28 * threads access the map concurrently, and at least one of the threads modifies
29 * the map structurally, it <i>must</i> be synchronized externally. (A
30 * structural modification is any operation that adds or deletes one or more
31 * mappings; merely changing the value associated with an existing key is not
32 * a structural modification.) This is typically accomplished by
33 * synchronizing on some object that naturally encapsulates the map. If no
34 * such object exists, the map should be "wrapped" using the
35 * <tt>SynchronizedTemporalMultiMap.getInstance</tt> method. This is best done at creation
36 * time, to prevent accidental unsynchronized access to the map:
37 * <pre>
38 * TemporalMultiMap tm = SynchronizedTemporalMap.getInstance(new TreeTemporalMultiMap(...));
39 * </pre><p>
40 *
41 * Note the synchronizing proxies are not available yet. <BR>
42 *
43 * <BR>(<A HREF="../uml/TreeTemporalMultiMap.gif">internal structure</a>)<BR>
44 * In a future version, this structure will be optimized in order to reduce the
45 * memory usage when the map contains few values.
46 * @author Thomas Beck
47 * @version $Id$
48 */
49 public class TreeTemporalMultiMap extends AbstractTemporalMultiMap
50 {
51 // primary data structure: indexed first by value
52 // mapkey=value mapvalue=TemporalUnaryMaps,
53 private final Map valueMap = new HashMap();
54
55 // secondary data structure: indexed first by endInstant
56 // mapkey=endInstant mapvalue=TimeNode
57 // this implementation is provisional, will be replaced later by a
58 // bi-dimensional indexing strategy (as some temporal databases do)
59 private final SortedMap timeMap = new TreeMap();
60
61 // accepted type for values
62 private final Class valueType;
63
64 /**
65 * Default constructor. Values of any type will be accepted.
66 */
67 public TreeTemporalMultiMap() {
68 this.valueType = null;
69 }
70
71 /**
72 * @param valueType values must be of this type.
73 */
74 public TreeTemporalMultiMap(Class valueType) {
75 this.valueType = valueType;
76 }
77
78
79 // read methods //
80
81 public Instant firstInstant(Object value) {
82 return this.getTemporalUnaryMap(value).firstInstant();
83 }
84 public Instant lastInstant(Object value) {
85 return this.getTemporalUnaryMap(value).lastInstant();
86 }
87 public Period getPeriod(Instant instant, Object value) {
88 return this.getTemporalUnaryMap(value).getPeriod(instant);
89 }
90 public boolean contains(Instant instant, Object value) {
91 TemporalUnaryMap tum = this.getTemporalUnaryMapOrNull(value);
92 return tum == null ? false : tum.containsInstant(instant);
93 }
94 public boolean containsValue(Object value) {
95 TemporalUnaryMap tum = this.getTemporalUnaryMapOrNull(value);
96 return tum == null ? false : !tum.isEmpty();
97 }
98 public Period firstPeriod(Object value) {
99 return this.getTemporalUnaryMap(value).firstPeriod();
100 }
101 public Period lastPeriod(Object value) {
102 return this.getTemporalUnaryMap(value).lastPeriod();
103 }
104 public boolean isEmpty() {
105 return this.timeMap.isEmpty();
106 }
107
108
109 public int size(Object value) {
110 TemporalUnaryMap tum = this.getTemporalUnaryMapOrNull(value);
111 return tum == null ? 0 : tum.size();
112 }
113
114
115
116 // sub-structures //
117
118 /* public TemporalMultiMap subMap(Period p) {
119 if (p == null) throw new NullPointerException();
120 //@todo: implement this jtemporal.AbstractTemporalMultiMap abstract method
121 throw new UnsupportedOperationException("Method not implemented yet, and it is not clear whether it is feasible :-)");
122 }*/
123 public Set periodSet(Object value) {
124 if (value == null) throw new NullPointerException();
125 TemporalUnaryMap tum = this.getTemporalUnaryMapOrNull(value);
126 if (tum == null) return EmptySet.getInstance();
127 return tum.periodSet();
128 }
129
130 public Set valueSet() {
131 return new ReadOnlySet(this.valueMap.keySet());
132 }
133
134 public Set valueSet(Instant instant) {
135 if (instant == null) throw new NullPointerException();
136 return new ValueSetView(instant);
137 }
138
139
140 private class ValueSetView extends AbstractSet {
141 private final Instant instant;
142 private final SortedMap tailMap; // efficient for recent instants
143
144 public ValueSetView(Instant instant) {
145 this.instant = instant;
146 this.tailMap = TreeTemporalMultiMap.this.timeMap.tailMap(instant);
147 }
148
149 public int size() {
150 Iterator i = iterator();
151 int size = 0;
152 for (;i.hasNext(); size++)
153 i.next();
154 return size;
155 }
156
157 public boolean isEmpty() {
158 Iterator i = iterator();
159 return (!i.hasNext()) ;
160 }
161
162 public boolean contains(Object value) {
163 Iterator i = iterator();
164 while (i.hasNext()) {
165 if (i.next().equals(value)) return true;
166 }
167 return false;
168 }
169
170 public boolean remove(Object value) {
171 throw new UnsupportedOperationException();
172 }
173
174 public Iterator iterator() {
175 return new ValueSetIterator();
176 } // iterator()
177
178 private class ValueSetIterator implements Iterator
179 {
180 private Iterator endInstantIterator;
181 private Iterator timeNodeIterator;
182 private TimedObject theNext; // buffers one value in advance
183 private boolean hasNext; // value available in the buffer
184
185 private boolean advanceInnerSuccessful() {
186 while (timeNodeIterator.hasNext()) {
187 TimedObject to = (TimedObject) timeNodeIterator.next();
188 if (to.getPeriod().contains(ValueSetView.this.instant)) {
189 hasNext = true;
190 theNext = to;
191 return true;
192 }
193 }
194
195 // no next
196 timeNodeIterator = null; // iterator consumed, garbage
197 return false;
198 }
199
200
201
202 private boolean advanceOuterSuccessful() {
203 if (endInstantIterator.hasNext() == false) {
204 endInstantIterator = null; // iterator consumed
205 hasNext = false;
206 theNext = null;
207 return false;
208 }
209 Map.Entry entry = (Map.Entry) endInstantIterator.next();
210 TimeNode tn = (TimeNode) entry.getValue();
211 timeNodeIterator = tn.iterator();
212 return true;
213 }
214
215 private void advance() {
216 while (true) {
217 if (advanceInnerSuccessful()) break;
218 else {
219 if (advanceOuterSuccessful()) continue;
220 else {
221 hasNext = false;
222 break;
223 }
224 }
225 } // while
226 }
227
228 public ValueSetIterator() {// constructor
229 endInstantIterator = TreeTemporalMultiMap.this.timeMap
230 .tailMap(ValueSetView.this.instant)
231 .entrySet().iterator();
232 if (advanceOuterSuccessful()) {
233 advance();
234 }
235 }
236
237 public boolean hasNext() {
238 return hasNext;
239 }
240 public Object next() {
241 if (hasNext == false) throw new NoSuchElementException();
242 TimedObject to = theNext;
243 advance();
244 return to.getValue();
245 }
246 public void remove() {
247 throw new UnsupportedOperationException();
248 }
249 } // ValueSetIterator
250 } // ValueSetView
251
252 // updates //
253
254 public void clear() {
255 this.valueMap.clear();
256 this.timeMap.clear();
257 }
258
259 public void removeValue(Object value) {
260 if (value == null) throw new NullPointerException();
261
262 TemporalUnaryMap tum = this.getTemporalUnaryMap(value);
263 tum.clear();
264 this.valueMap.remove(tum);
265 }
266
267 public boolean remove(Period p, Object value) {
268 if (value == null || p == null) throw new NullPointerException();
269 TemporalUnaryMap tum = this.getTemporalUnaryMap(value);
270 boolean result = tum.remove(p);
271 if (tum.isEmpty()) this.valueMap.remove(tum);
272 return result;
273 }
274
275 public boolean removePeriod(Period p) {
276 boolean ret = false;
277 if (p == null) throw new NullPointerException();
278 for (Iterator v = this.valueMap.values().iterator(); v.hasNext(); ) {
279 TemporalUnaryMap tum = (TemporalUnaryMap) v.next();
280 ret |= tum.remove(p);
281 }
282 return ret;
283 }
284
285
286 /*
287 * javadoc inherited from interface
288 */
289 public boolean put(Period p, Object value) {
290 if (value == null) throw new NullPointerException();
291
292 if (this.valueType != null) {
293 if (! this.valueType.isInstance(value) ) {
294 throw new ClassCastException();
295 }
296 }
297
298 TemporalUnaryMap tum = this.getTemporalUnaryMapOrNull(value);
299 // check whether a new TemporalUnaryMap must be created for this value
300 if (tum == null) {
301 tum = new TreeTemporalUnaryMap(this.valueType, new SortedMapSubscriber(value));
302 valueMap.put(value, tum);
303 }
304
305 return tum.put(p, value);
306
307 } // put
308
309
310
311 // tools //
312
313 /**
314 * @return the TemporalUnaryMap associated to the value,
315 * or null is this value is unknown
316 */
317 private TemporalUnaryMap getTemporalUnaryMapOrNull(Object value) {
318 TemporalUnaryMap tum = (TemporalUnaryMap) (valueMap.get(value));
319 return tum;
320 }
321
322
323 /**
324 * @return the TemporalUnaryMap associated to the value, or null if not
325 * @throws NoSuchElementException is this value is unknown
326 */
327 private TemporalUnaryMap getTemporalUnaryMap(Object value) {
328 TemporalUnaryMap tum = (TemporalUnaryMap) (valueMap.get(value));
329 if (tum == null) throw new NoSuchElementException(valueMap.toString());
330 return tum;
331 }
332
333
334 /**
335 * This inner class has been created because it is impossible to implement a non public insterface
336 * without declaring the implementing methods as public :-(
337 * (http://developer.java.sun.com/developer/bugParade/bugs/4456057.html)
338 */
339 private final NodeParent nodeDeadListener = new NodeParent() {
340 public void nodeDead(TimeNode node) {
341 Object r = TreeTemporalMultiMap.this.timeMap.remove(node.getEndInstant());
342 if (r == null) {
343 throw new IllegalStateException();
344 }
345 }
346 };
347
348
349
350 /**
351 * Listening the inner loop treeMaps, allows to know what is really changed,
352 * because for example a "put" invocation can partially overwrite preexisting
353 * information. Also a user can make updates using sets or iterators.
354 * Whith this "cleaned" information we can now easly replicate the information
355 * in the structure having orthogonal indexing.
356 * These methods are called by the TemporalUnaryMaps which are inside the valueMap
357 * Maintains TreeTemporalMultiMap.this.timeMap in Synch.
358 */
359 class SortedMapSubscriber implements MapSubscriber
360 {
361 // the value that the client has added with a Period to the UnaryMap
362 // there is one subscriber per UnaryMap
363 private final Object value;
364
365 public SortedMapSubscriber(Object value) {
366 this.value = value;
367 //this.timeMap = TreeTemporalMultiMap.this.timeMap;
368 }
369
370 public void put(Map publisher, Object key, Object value) {
371 // pre-conditions
372 if (!this.value.equals(value)) {
373 throw new IllegalStateException(value.toString());
374 }
375
376 Period period = (Period) key;
377
378 // in a later version, to improve performances,
379 // TimedObjects will not be created anymore
380 TimedObject to = new TimedObject(period, value);
381 TimeNode tNode = (TimeNode) TreeTemporalMultiMap.this.timeMap.get(period.getEnd());
382 if (tNode == null) {
383 tNode = new TimeNode(TreeTemporalMultiMap.this.nodeDeadListener, to);
384 Object r = TreeTemporalMultiMap.this.timeMap.put(period.getEnd(), tNode);
385 if (r != null) {
386 throw new IllegalStateException(r.toString());
387 }
388 }
389 else {
390 tNode.add(to);
391 }
392 }
393
394 public void removed(Map publisher, Object key) {
395 Period period = (Period) key;
396
397 // in a later varsion, TimedObjects will not be created anymore,
398 TimedObject to = new TimedObject((Period)key, this.value);
399
400 TimeNode tn = (TimeNode) TreeTemporalMultiMap.this.timeMap.get(period.getEnd());
401 if (tn == null) {
402 throw new NoSuchElementException(period.toString());
403 }
404 tn.remove(to);
405
406 }
407
408 } // SortedMapSubscriber
409
410 }