Mercurial > hg > extraction-interface

comparison geotemco/lib/simile/ajax/scripts/data-structure.js @ 0:b12c99b7c3f0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit for previous development
author Zoe Hong <zhong@mpiwg-berlin.mpg.de>
date Mon, 19 Jan 2015 17:13:49 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:b12c99b7c3f0
1 /**
2 * A basic set (in the mathematical sense) data structure
3 *
4 * @constructor
5 * @param {Array or SimileAjax.Set} [a] an initial collection
6 */
7 SimileAjax.Set = function(a) {
8 this._hash = {};
9 this._count = 0;
10
11 if (a instanceof Array) {
12 for (var i = 0; i < a.length; i++) {
13 this.add(a[i]);
14 }
15 } else if (a instanceof SimileAjax.Set) {
16 this.addSet(a);
17 }
18 }
19
20 /**
21 * Adds the given object to this set, assuming there it does not already exist
22 *
23 * @param {Object} o the object to add
24 * @return {Boolean} true if the object was added, false if not
25 */
26 SimileAjax.Set.prototype.add = function(o) {
27 if (!(o in this._hash)) {
28 this._hash[o] = true;
29 this._count++;
30 return true;
31 }
32 return false;
33 }
34
35 /**
36 * Adds each element in the given set to this set
37 *
38 * @param {SimileAjax.Set} set the set of elements to add
39 */
40 SimileAjax.Set.prototype.addSet = function(set) {
41 for (var o in set._hash) {
42 this.add(o);
43 }
44 }
45
46 /**
47 * Removes the given element from this set
48 *
49 * @param {Object} o the object to remove
50 * @return {Boolean} true if the object was successfully removed,
51 * false otherwise
52 */
53 SimileAjax.Set.prototype.remove = function(o) {
54 if (o in this._hash) {
55 delete this._hash[o];
56 this._count--;
57 return true;
58 }
59 return false;
60 }
61
62 /**
63 * Removes the elements in this set that correspond to the elements in the
64 * given set
65 *
66 * @param {SimileAjax.Set} set the set of elements to remove
67 */
68 SimileAjax.Set.prototype.removeSet = function(set) {
69 for (var o in set._hash) {
70 this.remove(o);
71 }
72 }
73
74 /**
75 * Removes all elements in this set that are not present in the given set, i.e.
76 * modifies this set to the intersection of the two sets
77 *
78 * @param {SimileAjax.Set} set the set to intersect
79 */
80 SimileAjax.Set.prototype.retainSet = function(set) {
81 for (var o in this._hash) {
82 if (!set.contains(o)) {
83 delete this._hash[o];
84 this._count--;
85 }
86 }
87 }
88
89 /**
90 * Returns whether or not the given element exists in this set
91 *
92 * @param {SimileAjax.Set} o the object to test for
93 * @return {Boolean} true if the object is present, false otherwise
94 */
95 SimileAjax.Set.prototype.contains = function(o) {
96 return (o in this._hash);
97 }
98
99 /**
100 * Returns the number of elements in this set
101 *
102 * @return {Number} the number of elements in this set
103 */
104 SimileAjax.Set.prototype.size = function() {
105 return this._count;
106 }
107
108 /**
109 * Returns the elements of this set as an array
110 *
111 * @return {Array} a new array containing the elements of this set
112 */
113 SimileAjax.Set.prototype.toArray = function() {
114 var a = [];
115 for (var o in this._hash) {
116 a.push(o);
117 }
118 return a;
119 }
120
121 /**
122 * Iterates through the elements of this set, order unspecified, executing the
123 * given function on each element until the function returns true
124 *
125 * @param {Function} f a function of form f(element)
126 */
127 SimileAjax.Set.prototype.visit = function(f) {
128 for (var o in this._hash) {
129 if (f(o) == true) {
130 break;
131 }
132 }
133 }
134
135 /**
136 * A sorted array data structure
137 *
138 * @constructor
139 */
140 SimileAjax.SortedArray = function(compare, initialArray) {
141 this._a = (initialArray instanceof Array) ? initialArray : [];
142 this._compare = compare;
143 };
144
145 SimileAjax.SortedArray.prototype.add = function(elmt) {
146 var sa = this;
147 var index = this.find(function(elmt2) {
148 return sa._compare(elmt2, elmt);
149 });
150
151 if (index < this._a.length) {
152 this._a.splice(index, 0, elmt);
153 } else {
154 this._a.push(elmt);
155 }
156 };
157
158 SimileAjax.SortedArray.prototype.remove = function(elmt) {
159 var sa = this;
160 var index = this.find(function(elmt2) {
161 return sa._compare(elmt2, elmt);
162 });
163
164 while (index < this._a.length && this._compare(this._a[index], elmt) == 0) {
165 if (this._a[index] == elmt) {
166 this._a.splice(index, 1);
167 return true;
168 } else {
169 index++;
170 }
171 }
172 return false;
173 };
174
175 SimileAjax.SortedArray.prototype.removeAll = function() {
176 this._a = [];
177 };
178
179 SimileAjax.SortedArray.prototype.elementAt = function(index) {
180 return this._a[index];
181 };
182
183 SimileAjax.SortedArray.prototype.length = function() {
184 return this._a.length;
185 };
186
187 SimileAjax.SortedArray.prototype.find = function(compare) {
188 var a = 0;
189 var b = this._a.length;
190
191 while (a < b) {
192 var mid = Math.floor((a + b) / 2);
193 var c = compare(this._a[mid]);
194 if (mid == a) {
195 return c < 0 ? a+1 : a;
196 } else if (c < 0) {
197 a = mid;
198 } else {
199 b = mid;
200 }
201 }
202 return a;
203 };
204
205 SimileAjax.SortedArray.prototype.getFirst = function() {
206 return (this._a.length > 0) ? this._a[0] : null;
207 };
208
209 SimileAjax.SortedArray.prototype.getLast = function() {
210 return (this._a.length > 0) ? this._a[this._a.length - 1] : null;
211 };
212
213 /*==================================================
214 * Event Index
215 *==================================================
216 */
217
218 SimileAjax.EventIndex = function(unit) {
219 var eventIndex = this;
220
221 this._unit = (unit != null) ? unit : SimileAjax.NativeDateUnit;
222 this._events = new SimileAjax.SortedArray(
223 function(event1, event2) {
224 return eventIndex._unit.compare(event1.getStart(), event2.getStart());
225 }
226 );
227 this._idToEvent = {};
228 this._indexed = true;
229 };
230
231 SimileAjax.EventIndex.prototype.getUnit = function() {
232 return this._unit;
233 };
234
235 SimileAjax.EventIndex.prototype.getEvent = function(id) {
236 return this._idToEvent[id];
237 };
238
239 SimileAjax.EventIndex.prototype.add = function(evt) {
240 this._events.add(evt);
241 this._idToEvent[evt.getID()] = evt;
242 this._indexed = false;
243 };
244
245 SimileAjax.EventIndex.prototype.removeAll = function() {
246 this._events.removeAll();
247 this._idToEvent = {};
248 this._indexed = false;
249 };
250
251 SimileAjax.EventIndex.prototype.getCount = function() {
252 return this._events.length();
253 };
254
255 SimileAjax.EventIndex.prototype.getIterator = function(startDate, endDate) {
256 if (!this._indexed) {
257 this._index();
258 }
259 return new SimileAjax.EventIndex._Iterator(this._events, startDate, endDate, this._unit);
260 };
261
262 SimileAjax.EventIndex.prototype.getReverseIterator = function(startDate, endDate) {
263 if (!this._indexed) {
264 this._index();
265 }
266 return new SimileAjax.EventIndex._ReverseIterator(this._events, startDate, endDate, this._unit);
267 };
268
269 SimileAjax.EventIndex.prototype.getAllIterator = function() {
270 return new SimileAjax.EventIndex._AllIterator(this._events);
271 };
272
273 SimileAjax.EventIndex.prototype.getEarliestDate = function() {
274 var evt = this._events.getFirst();
275 return (evt == null) ? null : evt.getStart();
276 };
277
278 SimileAjax.EventIndex.prototype.getLatestDate = function() {
279 var evt = this._events.getLast();
280 if (evt == null) {
281 return null;
282 }
283
284 if (!this._indexed) {
285 this._index();
286 }
287
288 var index = evt._earliestOverlapIndex;
289 var date = this._events.elementAt(index).getEnd();
290 for (var i = index + 1; i < this._events.length(); i++) {
291 date = this._unit.later(date, this._events.elementAt(i).getEnd());
292 }
293
294 return date;
295 };
296
297 SimileAjax.EventIndex.prototype._index = function() {
298 /*
299 * For each event, we want to find the earliest preceding
300 * event that overlaps with it, if any.
301 */
302
303 var l = this._events.length();
304 for (var i = 0; i < l; i++) {
305 var evt = this._events.elementAt(i);
306 evt._earliestOverlapIndex = i;
307 }
308
309 var toIndex = 1;
310 for (var i = 0; i < l; i++) {
311 var evt = this._events.elementAt(i);
312 var end = evt.getEnd();
313
314 toIndex = Math.max(toIndex, i + 1);
315 while (toIndex < l) {
316 var evt2 = this._events.elementAt(toIndex);
317 var start2 = evt2.getStart();
318
319 if (this._unit.compare(start2, end) < 0) {
320 evt2._earliestOverlapIndex = i;
321 toIndex++;
322 } else {
323 break;
324 }
325 }
326 }
327 this._indexed = true;
328 };
329
330 SimileAjax.EventIndex._Iterator = function(events, startDate, endDate, unit) {
331 this._events = events;
332 this._startDate = startDate;
333 this._endDate = endDate;
334 this._unit = unit;
335
336 this._currentIndex = events.find(function(evt) {
337 return unit.compare(evt.getStart(), startDate);
338 });
339 if (this._currentIndex - 1 >= 0) {
340 this._currentIndex = this._events.elementAt(this._currentIndex - 1)._earliestOverlapIndex;
341 }
342 this._currentIndex--;
343
344 this._maxIndex = events.find(function(evt) {
345 return unit.compare(evt.getStart(), endDate);
346 });
347
348 this._hasNext = false;
349 this._next = null;
350 this._findNext();
351 };
352
353 SimileAjax.EventIndex._Iterator.prototype = {
354 hasNext: function() { return this._hasNext; },
355 next: function() {
356 if (this._hasNext) {
357 var next = this._next;
358 this._findNext();
359
360 return next;
361 } else {
362 return null;
363 }
364 },
365 _findNext: function() {
366 var unit = this._unit;
367 while ((++this._currentIndex) < this._maxIndex) {
368 var evt = this._events.elementAt(this._currentIndex);
369 if (unit.compare(evt.getStart(), this._endDate) < 0 &&
370 unit.compare(evt.getEnd(), this._startDate) > 0) {
371
372 this._next = evt;
373 this._hasNext = true;
374 return;
375 }
376 }
377 this._next = null;
378 this._hasNext = false;
379 }
380 };
381
382 SimileAjax.EventIndex._ReverseIterator = function(events, startDate, endDate, unit) {
383 this._events = events;
384 this._startDate = startDate;
385 this._endDate = endDate;
386 this._unit = unit;
387
388 this._minIndex = events.find(function(evt) {
389 return unit.compare(evt.getStart(), startDate);
390 });
391 if (this._minIndex - 1 >= 0) {
392 this._minIndex = this._events.elementAt(this._minIndex - 1)._earliestOverlapIndex;
393 }
394
395 this._maxIndex = events.find(function(evt) {
396 return unit.compare(evt.getStart(), endDate);
397 });
398
399 this._currentIndex = this._maxIndex;
400 this._hasNext = false;
401 this._next = null;
402 this._findNext();
403 };
404
405 SimileAjax.EventIndex._ReverseIterator.prototype = {
406 hasNext: function() { return this._hasNext; },
407 next: function() {
408 if (this._hasNext) {
409 var next = this._next;
410 this._findNext();
411
412 return next;
413 } else {
414 return null;
415 }
416 },
417 _findNext: function() {
418 var unit = this._unit;
419 while ((--this._currentIndex) >= this._minIndex) {
420 var evt = this._events.elementAt(this._currentIndex);
421 if (unit.compare(evt.getStart(), this._endDate) < 0 &&
422 unit.compare(evt.getEnd(), this._startDate) > 0) {
423
424 this._next = evt;
425 this._hasNext = true;
426 return;
427 }
428 }
429 this._next = null;
430 this._hasNext = false;
431 }
432 };
433
434 SimileAjax.EventIndex._AllIterator = function(events) {
435 this._events = events;
436 this._index = 0;
437 };
438
439 SimileAjax.EventIndex._AllIterator.prototype = {
440 hasNext: function() {
441 return this._index < this._events.length();
442 },
443 next: function() {
444 return this._index < this._events.length() ?
445 this._events.elementAt(this._index++) : null;
446 }
447 };