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/delegate_support') ;
  9 
 10 /**
 11   @class
 12 
 13   A dynamically filled array.  A SparseArray makes it easy for you to create
 14   very large arrays of data but then to defer actually populating that array
 15   until it is actually needed.  This is often much faster than generating an
 16   array up front and paying the cost to load your data then.
 17 
 18   Although technically all arrays in JavaScript are "sparse" (in the sense
 19   that you can read and write properties at arbitrary indexes), this array
 20   keeps track of which elements in the array have been populated already
 21   and which ones have not.  If you try to get a value at an index that has
 22   not yet been populated, the SparseArray will notify a delegate object first,
 23   giving the delegate a chance to populate the component.
 24 
 25   Most of the time, you will use a SparseArray to incrementally load data
 26   from the server.  For example, if you have a contact list with 3,000
 27   contacts in it, you may create a SparseArray with a length of 3,000 and set
 28   that as the content for a ListView.  As the ListView tries to display the
 29   visible contacts, it will request them from the SparseArray, which will in
 30   turn notify your delegate, giving you a chance to load the contact data from
 31   the server.
 32 
 33   @extends SC.Enumerable
 34   @extends SC.Array
 35   @extends SC.Observable
 36   @extends SC.DelegateSupport
 37   @since SproutCore 1.0
 38 */
 39 
 40 SC.SparseArray = SC.Object.extend(SC.Observable, SC.Enumerable, SC.Array,
 41   SC.DelegateSupport, /** @scope SC.SparseArray.prototype */ {
 42 
 43   // ..........................................................
 44   // LENGTH SUPPORT
 45   //
 46 
 47   _requestingLength: 0,
 48   _requestingIndex: 0,
 49 
 50   /**
 51     The length of the sparse array.  The delegate for the array should set
 52     this length.
 53 
 54     @type Number
 55   */
 56   length: function() {
 57     var del = this.delegate ;
 58     if (del && SC.none(this._length) && del.sparseArrayDidRequestLength) {
 59       this._requestingLength++ ;
 60       del.sparseArrayDidRequestLength(this);
 61       this._requestingLength-- ;
 62     }
 63     return this._length || 0 ;
 64   }.property().cacheable(),
 65 
 66   /**
 67     Call this method from a delegate to provide a length for the sparse array.
 68     If you pass null for this property, it will essentially "reset" the array
 69     causing your delegate to be called again the next time another object
 70     requests the array length.
 71 
 72     @param {Number} length the length or null
 73     @returns {SC.SparseArray} receiver
 74   */
 75   provideLength: function(length) {
 76     var oldLength;
 77     if (SC.none(length)) this._sa_content = null ;
 78     if (length !== this._length) {
 79       oldLength = this._length;
 80       this._length = length ;
 81       if (this._requestingLength <= 0) { this.arrayContentDidChange(0, oldLength||0, length||0) ; }
 82     }
 83     return this ;
 84   },
 85 
 86   // ..........................................................
 87   // READING CONTENT
 88   //
 89 
 90   /**
 91     The minimum range of elements that should be requested from the delegate.
 92     If this value is set to larger than 1, then the sparse array will always
 93     fit a requested index into a range of this size and request it.
 94 
 95     @type Number
 96   */
 97   rangeWindowSize: 1,
 98 
 99   /**
100     This array contains all the start_indexes of ranges requested. This is to
101     avoid calling sparseArrayDidRequestRange to often. Indexes are removed and
102     added as range requests are completed.
103   */
104   requestedRangeIndex: null,
105 
106   /**
107     Make sure to create the index array during init so that it is not shared
108     between all instances.
109   */
110   init: function() {
111     sc_super();
112     this.requestedRangeIndex = [];
113 
114     this._TMP_PROVIDE_ARRAY = [];
115     this._TMP_PROVIDE_RANGE = { length: 1 };
116     this._TMP_RANGE = {};
117   },
118 
119   /**
120     Returns the object at the specified index.  If the value for the index
121     is currently undefined, invokes the didRequestIndex() method to notify
122     the delegate.
123 
124     The omitMaterializing flag ensures that the object will not be materialized,
125     but it simply checks for the presence of an object at the specified index
126     and will return YES (or undefined if not found). This is useful in the case
127     of SparseArrays, where you might NOT want to request the index to be loaded,
128     but simply need a shallow check to see if the position has been filled.
129 
130     @param {Number} idx the index to get
131     @param {Boolean} omitMaterializing
132     @return {Object} the object
133   */
134   objectAt: function(idx, omitMaterializing) {
135     var content = this._sa_content, ret ;
136 
137     if (idx >= this.get('length')) return undefined;
138     if (!content) content = this._sa_content = [] ;
139     if ((ret = content[idx]) === undefined) {
140       if(!omitMaterializing) this.requestIndex(idx);
141       ret = content[idx]; // just in case the delegate provided immediately
142     }
143     return ret ;
144   },
145 
146   /**
147     Returns the set of indexes that are currently defined on the sparse array.
148     If you pass an optional index set, the search will be limited to only
149     those indexes.  Otherwise this method will return an index set containing
150     all of the defined indexes.  Currently this can be quite expensive if
151     you have a lot of indexes defined.
152 
153     @param {SC.IndexSet} indexes optional from indexes
154     @returns {SC.IndexSet} defined indexes
155   */
156   definedIndexes: function(indexes) {
157     var ret = SC.IndexSet.create(),
158         content = this._sa_content,
159         idx, len;
160 
161     if (!content) return ret.freeze(); // nothing to do
162 
163     if (indexes) {
164       indexes.forEach(function(idx) {
165         if (content[idx] !== undefined) ret.add(idx);
166       });
167     } else {
168       len = content.length;
169       for(idx=0;idx<len;idx++) {
170         if (content[idx] !== undefined) ret.add(idx);
171       }
172     }
173 
174     return ret.freeze();
175   },
176 
177   _TMP_RANGE: {},
178 
179   /**
180     Called by objectAt() whenever you request an index that has not yet been
181     loaded.  This will possibly expand the index into a range and then invoke
182     an appropriate method on the delegate to request the data.
183 
184     It will check if the range has been already requested.
185 
186     @param {Number} idx the index to retrieve
187     @returns {SC.SparseArray} receiver
188   */
189   requestIndex: function(idx) {
190     var del = this.delegate;
191     if (!del) return this; // nothing to do
192 
193     // adjust window
194     var len = this.get('rangeWindowSize'), start = idx;
195     if (len > 1) start = start - Math.floor(start % len);
196     if (len < 1) len = 1 ;
197 
198     // invoke appropriate callback
199     this._requestingIndex++;
200     if (del.sparseArrayDidRequestRange) {
201       var range = this._TMP_RANGE;
202       if(this.wasRangeRequested(start)===-1){
203         range.start = start;
204         range.length = len;
205         this.requestedRangeIndex.push(start);
206         del.sparseArrayDidRequestRange(this, range);
207       }
208     } else if (del.sparseArrayDidRequestIndex) {
209       while(--len >= 0) del.sparseArrayDidRequestIndex(this, start + len);
210     }
211     this._requestingIndex--;
212 
213     return this ;
214   },
215 
216   /*
217     This method is called by requestIndex to check if the range has already
218     been requested. We assume that rangeWindowSize is not changed often.
219 
220      @param {Number} startIndex
221      @return {Number} index in requestRangeIndex
222   */
223   wasRangeRequested: function(rangeStart) {
224     var i, ilen;
225     for(i=0, ilen=this.requestedRangeIndex.length; i<ilen; i++){
226       if(this.requestedRangeIndex[i]===rangeStart) return i;
227     }
228     return -1;
229   },
230 
231   /*
232     This method has to be called after a request for a range has completed.
233     To remove the index from the sparseArray to allow future updates on the
234     range.
235 
236      @param {Number} startIndex
237      @return {Number} index in requestRangeIndex
238   */
239   rangeRequestCompleted: function(start) {
240     var i = this.wasRangeRequested(start);
241     if(i>=0) {
242       this.requestedRangeIndex.removeAt(i,1);
243       return YES;
244     }
245     return NO;
246   },
247 
248   /**
249     This method sets the content for the specified to the objects in the
250     passed array.  If you change the way SparseArray implements its internal
251     tracking of objects, you should override this method along with
252     objectAt().
253 
254     @param {Range} range the range to apply to
255     @param {Array} array the array of objects to insert
256     @returns {SC.SparseArray} receiver
257   */
258   provideObjectsInRange: function(range, array) {
259     var content = this._sa_content ;
260     if (!content) content = this._sa_content = [] ;
261     var start = range.start, len = range.length;
262     while(--len >= 0) content[start+len] = array.objectAt(len);
263     if (this._requestingIndex <= 0) this.arrayContentDidChange(range.start, range.length, range.length);
264     return this ;
265   },
266 
267   /**
268     Convenience method to provide a single object at a specified index.  Under
269     the covers this calls provideObjectsInRange() so you can override only
270     that method and this one will still work.
271 
272     @param {Number} index the index to insert
273     @param {Object} the object to insert
274     @return {SC.SparseArray} receiver
275   */
276   provideObjectAtIndex: function(index, object) {
277     var array = this._TMP_PROVIDE_ARRAY, range = this._TMP_PROVIDE_RANGE;
278     array[0] = object;
279     range.start = index;
280     return this.provideObjectsInRange(range, array);
281   },
282 
283   /**
284     Invalidates the array content in the specified range.  This is not the
285     same as editing an array.  Rather it will cause the array to reload the
286     content from the delegate again when it is requested.
287 
288     @param {Range} the range
289     @returns {SC.SparseArray} receiver
290   */
291   objectsDidChangeInRange: function(range) {
292 
293     // delete cached content
294     var content = this._sa_content ;
295     if (content) {
296       // if range covers entire length of cached content, just reset array
297       if (range.start === 0 && SC.maxRange(range)>=content.length) {
298         this._sa_content = null ;
299 
300       // otherwise, step through the changed parts and delete them.
301       } else {
302         var start = range.start, loc = Math.min(start + range.length, content.length);
303         while (--loc>=start) content[loc] = undefined;
304       }
305     }
306     this.arrayContentDidChange(range.start, range.length, range.length) ; // notify
307     return this ;
308   },
309 
310   /**
311     Optimized version of indexOf().  Asks the delegate to provide the index
312     of the specified object.  If the delegate does not implement this method
313     then it will search the internal array directly.
314 
315     @param {Object} obj the object to search for
316     @returns {Number} the discovered index or -1 if not found
317   */
318   indexOf: function(obj) {
319     var c, ret, del = this.delegate ;
320     if (del && del.sparseArrayDidRequestIndexOf) {
321       ret = del.sparseArrayDidRequestIndexOf(this, obj);
322     }
323 
324     if (SC.none(ret)) {
325       c = this._sa_content ;
326       if (!c) c = this._sa_content = [] ;
327       ret = c.indexOf(obj) ;
328     }
329     return ret;
330   },
331 
332   // ..........................................................
333   // EDITING
334   //
335 
336   /**
337     Array primitive edits the objects at the specified index unless the
338     delegate rejects the change.
339 
340     @param {Number} idx the index to begin to replace
341     @param {Number} amt the number of items to replace
342     @param {Array} objects the new objects to set instead
343     @returns {SC.SparseArray} receiver
344   */
345   replace: function(idx, amt, objects) {
346     objects = objects || [] ;
347 
348     // if we have a delegate, get permission to make the replacement.
349     var del = this.delegate ;
350     if (del) {
351       if (!del.sparseArrayShouldReplace ||
352           !del.sparseArrayShouldReplace(this, idx, amt, objects)) {
353             return this;
354       }
355     }
356 
357     // go ahead and apply to local content.
358     var content = this._sa_content ;
359     if (!content) content = this._sa_content = [] ;
360     content.replace(idx, amt, objects) ;
361 
362     // update length
363     var len = objects ? (objects.get ? objects.get('length') : objects.length) : 0;
364     var delta = len - amt ;
365 
366     this.arrayContentWillChange(idx, amt, len) ;
367 
368     if (!SC.none(this._length)) {
369       this.propertyWillChange('length');
370       this._length += delta;
371       this.propertyDidChange('length');
372     }
373 
374     this.arrayContentDidChange(idx, amt, len);
375 
376     return this ;
377   },
378 
379   /**
380     Resets the SparseArray, causing it to reload its content from the
381     delegate again.
382 
383     @returns {SC.SparseArray} receiver
384   */
385   reset: function() {
386     var oldLength;
387     this._sa_content = null ;
388     oldLength = this._length;
389     this._length = null ;
390     this.arrayContentDidChange(0, oldLength, 0);
391     this.invokeDelegateMethod(this.delegate, 'sparseArrayDidReset', this);
392     return this ;
393   }
394 
395 }) ;
396 
397 /**
398   Convenience metohd returns a new sparse array with a default length already
399   provided.
400 
401   @param {Number} len the length of the array
402   @returns {SC.SparseArray}
403 */
404 SC.SparseArray.array = function(len) {
405   return this.create({ _length: len||0 });
406 };
407