1 // ==========================================================================
  2 // Project:   SproutCore Costello - Property Observing Library
  3 // Copyright: ©2006-2011 Strobe Inc. and contributors.
  4 //            Portions ©2008-2011 Apple Inc. All rights reserved.
  5 // License:   Licensed under MIT license (see license.js)
  6 // ==========================================================================
  7 
  8 sc_require('mixins/enumerable') ;
  9 sc_require('mixins/observable') ;
 10 sc_require('mixins/freezable');
 11 sc_require('mixins/copyable');
 12 
 13 // IMPORTANT NOTE:  This file actually defines two classes:
 14 // SC.Set is a fully observable set class documented below.
 15 // SC.CoreSet is just like SC.Set but is not observable.  This is required
 16 // because SC.Observable is built on using sets and requires sets without
 17 // observability.
 18 //
 19 // We use pointer swizzling below to swap around the actual definitions so
 20 // that the documentation will turn out right.  (The docs should only
 21 // define SC.Set - not SC.CoreSet)
 22 
 23 /**
 24   @class
 25 
 26   An unordered collection of objects.
 27 
 28   A Set works a bit like an array except that its items are not ordered.
 29   You can create a set to efficiently test for membership for an object. You
 30   can also iterate through a set just like an array, even accessing objects
 31   by index, however there is no gaurantee as to their order.
 32 
 33   Whether or not property observing is enabled, sets offer very powerful
 34   notifications of items being added and removed, through the
 35   `:addSetObserver` and `:removeSetObserver` methods; this can be
 36   very useful, for instance, for filtering or mapping sets.
 37 
 38   Note that SC.Set is a primitive object, like an array.  It does implement
 39   limited key-value observing support, but it does not extend from SC.Object
 40   so you should not subclass it.
 41 
 42   Creating a Set
 43   --------------
 44   You can create a set like you would most objects using SC.Set.create().
 45   Most new sets you create will be empty, but you can also initialize the set
 46   with some content by passing an array or other enumerable of objects to the
 47   constructor.
 48 
 49   Finally, you can pass in an existing set and the set will be copied.  You
 50   can also create a copy of a set by calling SC.Set#clone().
 51 
 52         // creates a new empty set
 53         var foundNames = SC.Set.create();
 54 
 55         // creates a set with four names in it.
 56         var names = SC.Set.create(["Charles", "Tom", "Juan", "Alex"]);
 57 
 58         // creates a copy of the names set.
 59         var namesCopy = SC.Set.create(names);
 60 
 61         // same as above.
 62         var anotherNamesCopy = names.clone();
 63 
 64   Adding/Removing Objects
 65   -----------------------
 66   You generally add or remove objects from a set using add() or remove().
 67   You can add any type of object including primitives such as numbers,
 68   strings, and booleans.
 69 
 70   Note that objects can only exist one time in a set.  If you call add() on
 71   a set with the same object multiple times, the object will only be added
 72   once.  Likewise, calling remove() with the same object multiple times will
 73   remove the object the first time and have no effect on future calls until
 74   you add the object to the set again.
 75 
 76   Note that you cannot add/remove null or undefined to a set.  Any attempt to
 77   do so will be ignored.
 78 
 79   In addition to add/remove you can also call push()/pop().  Push behaves just
 80   like add() but pop(), unlike remove() will pick an arbitrary object, remove
 81   it and return it.  This is a good way to use a set as a job queue when you
 82   don't care which order the jobs are executed in.
 83 
 84   Testing for an Object
 85   ---------------------
 86   To test for an object's presence in a set you simply call SC.Set#contains().
 87   This method tests for the object's hash, which is generally the same as the
 88   object's guid; however, if you implement the hash() method on the object, it will
 89   use the return value from that method instead.
 90 
 91   Observing changes
 92   -----------------
 93   When using `:SC.Set` (rather than `:SC.CoreSet`), you can observe the
 94   `:"[]"` property to be alerted whenever the content changes.
 95 
 96   This is often unhelpful. If you are filtering sets of objects, for instance,
 97   it is very inefficient to re-filter all of the items each time the set changes.
 98   It would be better if you could just adjust the filtered set based on what
 99   was changed on the original set. The same issue applies to merging sets,
100   as well.
101 
102   `:SC.Set` and `:SC.CoreSet` both offer another method of being observed:
103   `:addSetObserver` and `:removeSetObserver`. These take a single parameter:
104   an object which implements `:didAddItem(set, item)` and
105   `:didRemoveItem(set, item)`.
106 
107   Whenever an item is added or removed from the set, all objects in the set
108   (a SC.CoreSet, actually) of observing objects will be alerted appropriately.
109 
110   BIG WARNING
111   ===========
112   SetObservers are not intended to be used "_creatively_"; for instance, do
113   not expect to be alerted immediately to any changes. **While the notifications
114   are currently sent out immediately, if we find a fast way to send them at end
115   of run loop, we most likely will do so.**
116 
117   @extends SC.Enumerable
118   @extends SC.Observable
119   @extends SC.Copyable
120   @extends SC.Freezable
121 
122   @since SproutCore 1.0
123 */
124 SC.Set = SC.mixin({},
125   SC.Observable,
126   SC.Enumerable,
127   SC.Freezable,
128 /** @scope SC.Set.prototype */ {
129 
130   /**
131     Creates a new set, with the optional array of items included in the
132     return set.
133 
134     @param {SC.Enumerable} items items to add
135     @return {SC.Set}
136   */
137   create: function(items) {
138     var ret, idx, pool = SC.Set._pool, isObservable = this.isObservable, len;
139     if (!isObservable && items===undefined && pool.length>0) {
140       return pool.pop();
141     } else {
142       ret = SC.beget(this);
143       if (isObservable) ret.initObservable();
144 
145       if (items && items.isEnumerable && items.get('length') > 0) {
146 
147         ret.isObservable = NO; // suspend change notifications
148 
149         // arrays and sets get special treatment to make them a bit faster
150         if (items.isSCArray) {
151           len = items.get('length');
152           for(idx = 0; idx < len; idx++) ret.add(items.objectAt(idx));
153 
154         } else if (items.isSet) {
155           len = items.length;
156           for(idx = 0; idx < len; idx++) ret.add(items[idx]);
157 
158         // otherwise use standard SC.Enumerable API
159         } else {
160           items.forEach(function(i) { ret.add(i); }, this);
161         }
162 
163         ret.isObservable = isObservable;
164       }
165     }
166     return ret ;
167   },
168 
169   /**
170     Walk like a duck
171 
172     @type Boolean
173   */
174   isSet: YES,
175 
176   /**
177     This property will change as the number of objects in the set changes.
178 
179     @type Number
180   */
181   length: 0,
182 
183   /**
184     Returns the first object in the set or null if the set is empty
185 
186     @type Object
187   */
188   firstObject: function() {
189     return (this.length > 0) ? this[0] : undefined ;
190   }.property(),
191 
192   /**
193     Clears the set
194 
195     @returns {SC.Set}
196   */
197   clear: function() {
198     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
199     this.length = 0;
200 
201     return this;
202   },
203 
204   /**
205     Call this method to test for membership.
206 
207     @returns {Boolean}
208   */
209   contains: function(obj) {
210 
211     // because of the way a set is "reset", the guid for an object may
212     // still be stored as a key, but points to an index that is beyond the
213     // length.  Therefore the found idx must both be defined and less than
214     // the current length.
215     if (obj === null) return NO ;
216     var idx = this[SC.hashFor(obj)] ;
217     return (!SC.none(idx) && (idx < this.length) && (this[idx]===obj)) ;
218   },
219 
220   /**
221     Returns YES if the passed object is also a set that contains the same
222     objects as the receiver.
223 
224     @param {SC.Set} obj the other object
225     @returns {Boolean}
226   */
227   isEqual: function(obj) {
228     // fail fast
229     if (!obj || !obj.isSet || (obj.get('length') !== this.get('length'))) {
230       return NO ;
231     }
232 
233     var loc = this.get('length');
234     while(--loc>=0) {
235       if (!obj.contains(this[loc])) return NO ;
236     }
237 
238     return YES;
239   },
240 
241   /**
242     Adds a set observers. Set observers must implement two methods:
243 
244     - didAddItem(set, item)
245     - didRemoveItem(set, item)
246 
247     Set observers are, in fact, stored in another set (a CoreSet).
248   */
249   addSetObserver: function(setObserver) {
250     // create set observer set if needed
251     if (!this.setObservers) {
252       this.setObservers = SC.CoreSet.create();
253     }
254 
255     // add
256     this.setObservers.add(setObserver);
257   },
258 
259   /**
260     Removes a set observer.
261   */
262   removeSetObserver: function(setObserver) {
263     // if there is no set, there can be no currently observing set observers
264     if (!this.setObservers) return;
265 
266     // remove the set observer. Pretty simple, if you think about it.
267     this.setObservers.remove(setObserver);
268   },
269 
270   /**
271     Call this method to add an object. performs a basic add.
272 
273     If the object is already in the set it will not be added again.
274 
275     @param {Object} obj the object to add
276     @returns {SC.Set} receiver
277   */
278   add: function(obj) {
279     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
280 
281     // Implementation note:  SC.none() and SC.hashFor() is inlined because sets are
282     // fundamental in SproutCore, and the inlined code is ~ 25% faster than
283     // calling SC.hashFor() in IE8.
284 
285     // Cannot add null to a set.
286     if (obj === null || obj === undefined) return this;
287 
288     var hashFunc,
289         guid = ((hashFunc = obj.hash) && (typeof hashFunc === "function")) ? hashFunc.call(obj) : SC.guidFor(obj),
290         idx  = this[guid],
291         len  = this.length;
292 
293     if ((idx >= len) || (this[idx] !== obj)) {
294       this[len] = obj;
295       this[guid] = len;
296       this.length = len + 1;
297       if (this.setObservers) this.didAddItem(obj);
298     }
299 
300     if (this.isObservable) this.enumerableContentDidChange();
301 
302     return this;
303   },
304 
305   /**
306     Add all the items in the passed array or enumerable
307 
308     @param {Array} objects
309     @returns {SC.Set} receiver
310   */
311   addEach: function(objects) {
312     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
313     if (!objects || !objects.isEnumerable) {
314       throw new Error("%@.addEach must pass enumerable".fmt(this));
315     }
316 
317     var idx, isObservable = this.isObservable ;
318 
319     if (isObservable) this.beginPropertyChanges();
320     if (objects.isSCArray) {
321       idx = objects.get('length');
322       while(--idx >= 0) this.add(objects.objectAt(idx)) ;
323     } else if (objects.isSet) {
324       idx = objects.length;
325       while(--idx>=0) this.add(objects[idx]);
326 
327     } else objects.forEach(function(i) { this.add(i); }, this);
328     if (isObservable) this.endPropertyChanges();
329 
330     return this ;
331   },
332 
333   /**
334     Removes the object from the set if it is found.
335 
336     If the object is not in the set, nothing will be changed.
337 
338     @param {Object} obj the object to remove
339     @returns {SC.Set} receiver
340   */
341   remove: function(obj) {
342     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
343 
344     // Implementation note:  SC.none() and SC.hashFor() are inlined because
345     // sets are fundamental in SproutCore, and the inlined code is ~ 25%
346     // faster than calling them "normally" in IE8.
347     if (obj === null || obj === undefined) return this ;
348 
349     var hashFunc,
350         guid = (obj && (hashFunc = obj.hash) && (typeof hashFunc === SC.T_FUNCTION)) ? hashFunc.call(obj) : SC.guidFor(obj),
351         idx  = this[guid],
352         len  = this.length,
353         tmp;
354 
355     // not in set.
356     // (SC.none is inlined for the reasons given above)
357     if ((idx === null || idx === undefined) || (idx >= len) || (this[idx] !== obj)) return this;
358 
359     // clear the guid key
360     delete this[guid];
361 
362     // to clear the index, we will swap the object stored in the last index.
363     // if this is the last object, just reduce the length.
364     if (idx < (len-1)) {
365       // we need to keep a reference to "obj" so we can alert others below;
366       // so, no changing it. Instead, create a temporary variable.
367       tmp = this[idx] = this[len-1];
368       guid = (tmp && (hashFunc = tmp.hash) && (typeof hashFunc === SC.T_FUNCTION)) ? hashFunc.call(tmp) : SC.guidFor(tmp);
369       this[guid] = idx;
370     }
371 
372     // Throw away the last object (it has been moved or is the object we are removing).
373     delete this[len-1];
374     this.length = len-1;
375 
376     if (this.isObservable) this.enumerableContentDidChange();
377     if (this.setObservers) this.didRemoveItem(obj);
378 
379     return this ;
380   },
381 
382   /**
383     Removes an arbitrary object from the set and returns it.
384 
385     @returns {Object} an object from the set or null
386   */
387   pop: function() {
388     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
389     var obj = (this.length > 0) ? this[this.length-1] : null ;
390     this.remove(obj) ;
391     return obj ;
392   },
393 
394   /**
395     Removes all the items in the passed array.
396 
397     @param {Array} objects
398     @returns {SC.Set} receiver
399   */
400   removeEach: function(objects) {
401     if (this.isFrozen) throw new Error(SC.FROZEN_ERROR);
402     if (!objects || !objects.isEnumerable) {
403       throw new Error("%@.addEach must pass enumerable".fmt(this));
404     }
405 
406     var idx, isObservable = this.isObservable ;
407 
408     if (isObservable) this.beginPropertyChanges();
409     if (objects.isSCArray) {
410       idx = objects.get('length');
411       while(--idx >= 0) this.remove(objects.objectAt(idx)) ;
412     } else if (objects.isSet) {
413       idx = objects.length;
414       while(--idx>=0) this.remove(objects[idx]);
415     } else objects.forEach(function(i) { this.remove(i); }, this);
416     if (isObservable) this.endPropertyChanges();
417 
418     return this ;
419   },
420 
421   /**
422    Clones the set into a new set.
423 
424     @returns {SC.Set} new copy
425   */
426   copy: function() {
427     return this.constructor.create(this);
428   },
429 
430   /**
431     Return a set to the pool for reallocation.
432 
433     @returns {SC.Set} receiver
434   */
435   destroy: function() {
436     this.isFrozen = NO; // unfreeze to return to pool
437 
438     if (!this.isObservable) SC.Set._pool.push(this.clear());
439 
440     return this;
441   },
442 
443   // .......................................
444   // PRIVATE
445   //
446 
447   /** @private - optimized */
448   forEach: function(iterator, target) {
449     var len = this.length;
450 
451     if (!target) target = this;
452     for (var idx = 0; idx < len; idx++) iterator.call(target, this[idx], idx, this);
453     return this ;
454   },
455 
456   /** @private */
457   toString: function() {
458     var len = this.length, idx, ary = [];
459     for (idx = 0; idx < len; idx++) ary[idx] = this[idx];
460     return "SC.Set<%@>".fmt(ary.join(',')) ;
461   },
462 
463   /**
464     @private
465     Alerts set observers that an item has been added.
466   */
467   didAddItem: function(item) {
468     // get the set observers
469     var o = this.setObservers;
470 
471     // return if there aren't any
472     if (!o) return;
473 
474     // loop through and call didAddItem.
475     var len = o.length, idx;
476     for (idx = 0; idx < len; idx++) o[idx].didAddItem(this, item);
477   },
478 
479   /**
480     @private
481     Alerts set observers that an item has been removed.
482   */
483   didRemoveItem: function(item) {
484     // get the set observers
485     var o = this.setObservers;
486 
487     // return if there aren't any
488     if (!o) return;
489 
490     // loop through and call didAddItem.
491     var len = o.length, idx;
492     for (idx = 0; idx < len; idx++) o[idx].didRemoveItem(this, item);
493   },
494 
495   /** @private */
496   isObservable: YES
497 
498 });
499 
500 SC.Set.constructor = SC.Set;
501 
502 // Make SC.Set look a bit more like other enumerables
503 
504 /** @private */
505 SC.Set.clone = SC.Set.copy;
506 
507 /** @private */
508 SC.Set.push = SC.Set.unshift = SC.Set.add;
509 
510 /** @private */
511 SC.Set.shift = SC.Set.pop;
512 
513 // add generic add/remove enumerable support
514 
515 /** @private */
516 SC.Set.addObject = SC.Set.add;
517 
518 /** @private */
519 SC.Set.removeObject = SC.Set.remove;
520 
521 SC.Set._pool = [];
522 
523 // ..........................................................
524 // CORE SET
525 //
526 
527 /** @class
528 
529   CoreSet is just like Set but not observable.  If you want to use the set
530   as a simple data structure with no observing, CoreSet is slightly faster
531   and more memory efficient.
532 
533   @extends SC.Set
534   @since SproutCore 1.0
535 */
536 SC.CoreSet = SC.beget(SC.Set);
537 
538 /** @private */
539 SC.CoreSet.isObservable = NO;
540 
541 /** @private */
542 SC.CoreSet.constructor = SC.CoreSet;
543