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