How to cache data in JavaScript for non-sequential shifting range?

Edit: For simplicity, and in order to try and make this question and the sample code more generic, I left out a detail. A detail which, in light of one of the responses (which was great), turns out to be important. This system will be used primarily to show things within a date range. The low/high numbers in the code will often represent Unix timestamps the range of which could span weeks or months. End Edit

I have a page where I provide a view of data objects which have properties that fall within a certain range. As the user interacts with the view to change it, it generally is a sequential change to the range (0-9, 10-19...). I am retrieving this data from the server, and as it comes in I cache it such that a subsequent request for data in that range is already available. On each read of the data, I first check to see if I have the cache data, and if not I read it from the server and adjust the cache.

A crude, overly simplified example is here:

var cache, haveCache, read;

cache = {
    rangeLow: 0,
    rangeHigh: 10,
    data: [
        //whatever has been read so far between current low and high
        {
            low: 1,
            high: 3,
            // ...other props
        },
        {
            low: 5,
            high: 6,
            // ...other props
        },
        //...
    ]
};

haveCache = function( low, high )
{
    return ! ( low < cache.rangeLow || high > cache.rangeHigh );
};

read = function( low, high )
{
    var data;

    if( ! haveCache( low, high ) )
    {
        //go to outside source and read in info , then merge to cache
        //
        // when merging to cache:
        //    if `low` param is lower than `cache.rangeLow`, overwrite cache.rangeLow with `low`
        //    if `high` param is higher than `cache.rangeHigh`, overwrite `cache.rangeHigh` with `high`
    }

    //read data from cache

    return data;
};

This works great as long as the change in range really is sequential. However, I realized there is a way to change the view non-sequentially and skip a large set of values. So Let's say I am currently showing for ranges 10-19, and I have a cache holding for ranges 0-29. Then the user asks for a view of data for range 60-69. The way it currently works, I'll ask the server for data and get it back and present it fine. But now the ca开发者_如何学JAVAche rangeLow and rangeHigh run from 0-69 while it only actually holds data for ranges 0-29 and 60-69. Items with properties ranging 30-59 are not in the cache and will never be retrieved.

What (better, efficient) mechanism or algorithm can I use to store cached information and determine whether my current displayed range is in the cache?

Thanks very much, Jim

You seem to have "chunks" of data with a range of 10 objects each. Calculate how many of these chunks you can store in your cache, let's call this cache_size. Now you can use a list of chunks you have in your cache, f.e. for cache_size 4:

20-29
0-9
40-49
30-39

It will be a bit more complicated this way to maintain this list and to check if a certain object is in the cache, but I think it's worth the effort.

You might also think about keeping a time or date index with each chunk to determine when an object from it was retrieved the last time so when your cache is full and you'll have to discard a cached chunk, you can discard the oldest.

I think you should change your haveCache to have more flatten key=>values.

For example one could be instead:

1..4
5..7
10..14

Just:

1,1,1,1,   // means like 1=>true,    2=>true,   3=>true,   4=>true
1,1,1,     // means like 5=>true,    6=>true,   7=>true
0,0,       // means like 8=>false,   9=>false
1,1,1,1,1  // means like 10=>false, 11=>false, 12=>false, 13=>false, 13=>false

Then you just change your haveCache function to determine is you have cache on any range. And on cache update you also need update your new cache index by filling/adding needed values by 1.

For the timestamps case

You just should to flatten in another view:

var cache = {
    1304960585 : {/* your data for 1304960585 */},
    1304960586 : {/* your data for 1304960586 */},
    1304960999 : {/* your data for 1304960999 */},
};
// then in haveCache function you should have something like:
function haveCache(start, end) {
    for (var i = start; i <= end; i++) {
        if (undefined == cache[i]) {
            return false;
        }
    }
    return true;
}

For the cases when you have part of the range in cache and part not -- you should invent for your own.

I'd change the havecashe

haveCache = function( low, high )
{
    if( low < cache.rangeLow || high > cache.rangeHigh )return undefined;
    for(var i = 0;i<cashe.data.length;i++){
        if( !(low < cache.data[i].low || high > cache.data[i].high) )
             return cache.data[i]
    }
    return undefined;
};

this also returns the data element in the cashe so you don't need to search again

var data;
if((data=haveCashe(low,high))==undefined){
    //read from server and store in cashe
}
return data;