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