Get next key-value pair in an object

Question

Given a key, I want to find the next property in an object. I can not rely on the keys to be ordered or sequential (they're uuids). Please see below for trivial example of what I want:

var db = {
  a: 1,
  b: 2,
  c: 3
}

var next = function(db, key) {
  // ???
}

next(db, 'a');  // I want 2
next(db, 'b');  // I want 3

I also want a prev() function, but I'm sure it will be the same solution.

This seems like such a trivial problem but I can't for the life of me figure out how to do it.

Happy for the solution to use underscore.js or be written in coffeescript :)

Solution 1

The correct answer is: you can't do that, as objects are unordered as per ECMAScript's spec.

I'd recommend that you use an ordered structure, like an array, for the purpose of the problem:

var db = [
  {key: 'a', value: 1},
  {key: 'b', value: 2},
  {key: 'c', value: 3}
];

Then the next function can be something like:

var next = function(db, key) {
  for (var i = 0; i < db.length; i++) {
    if (db[i].key === key) {
      return db[i + 1] && db[i + 1].value;
    }
  }
};

In case key does not exist on db or it was the last one, next returns undefined. if you're never going to ask for the next of the last item, you can simplify that function by removing the ternary && operator and returning db[i + 1].value directly.

You can also use some of Underscore.js utility methods to make next simpler:

var next = function(db, key) {
  var i = _.pluck(db, 'key').indexOf(key);
  return i !== -1 && db[i + 1] && db[i + 1].value;
};

(in this case next could return false sometimes... but it's still a falsy value :))

---

Now, a more pragmatic answer could be that, as most browsers will respect the order in which an object was initialized when iterating it, you can just iterate it with a for in loop as the other answers suggest. I'd recommend using Object.keys to simplify the job of iterating over the array:

// Assuming that db is an object as defined in the question.
var next = function(db, key) {
  var keys = Object.keys(db)
    , i = keys.indexOf(key);
  return i !== -1 && keys[i + 1] && db[keys[i + 1]];
};

Solution 2

ts / es6 version. I simply get the keys from the storeObject, look for the next Index.

 let keys = Object.keys(storeObject);
 let nextIndex = keys.indexOf(theCurrentItem) +1;
 let nextItem = keys[nextIndex];

Solution 3

function next(db, key){   
  var found = 0; 
  for(var k in db){
    if(found){ return db[k]; }
    if(k == key){ found = 1; }
  }
}

Solution 4

An immediate solution to this would be to store data in an array and use the object to simply store the index in the array at which an object exists.

var db = {
    data: [1, 2, 3],
    index: {
        a: 0,
        b: 1,
        c: 2
    }
};
function next(db, key) {
    var next = db.index[key] + 1;
    if (next >= db.data.length) {
        return null;
    }
    return db.data[next];
}
function prev(db, key) {
    var next = db.index[key] - 1;
    if (next < 0) {
        return null;
    }
    return db.data[next];
}
function add(db, key, value) {
    db.index[key] = db.data.push(value) - 1;
}
function remove(db, key) {
    var index = db.index[key], x, temp;
    if (index !== undefined) {
        delete db.index[key];
        db.data.splice(index, 1);
        // Update indices of any elements after the removed element
        for (x in db.index) {
            temp = db.index[x];
            if (temp > index) {
                db.index[x] = temp - 1;
            }
        }
    }
}

The basic idea is to use an ordered structure, in this case the array, to hold the data in a sequential manner. In this case, next and prev are both constant time, add is amortized constant time, and delete is O(N).

The ordering of keys isn't guaranteed by the ECMA standard, so for/in doesn't need to be in the order keys were added (though in practice, that does tend to be the common implementation). In this solution, I use an array to explicitly keep track of insert order.

Edit: I overlooked a deletion issue earlier with splice. The index would become incorrect for all values after the spliced value for a remove. The fix doesn't impact the running time complexity of the operation. A faster version with fewer removes could let the array become sparse and instead of splicing, simply set the index to null to free any reference stored there. This would lower the remove operation to O(1).

function remove(db, key) {
    var index = db.index[key];
    if (index !== undefined) {
        delete db.index[key];
        db.data[index] = null;
    }
}

Solution 5

Using undercore.js, you can take the keys of an object and do the trick. But I'm not sure if the key-value pairs are ordered in any way to begin with:

var next = function(db, key) {
    var keys = _.keys(db);
    var index = _.indexOf(keys, key);
    if(index+1<keys.length){
         return db[keys[index+1]];
    }else{
        return null;
    }
}

jsFiddle: http://jsfiddle.net/QWhN2/

View more solutions

Comments

[nnnnnn]

"So, given a "key", I want to look for the first instance of it in an object." - What do you mean the "first instance of it"? You can't have more than one property with the same name, so there can't possibly be a second instance. "I want to return the value of the NEXT property." - You can't rely on object properties being in any particular order (though some - most? - browsers tend to return the properties in the order they're created). If you need them to be ordered you need to use an array.

[captainclam]

@nnnnnn that's a good point about the browser property ordering thanks. I think I may just need to pull this info into an ordered array then traverse THAT.

[island205]

i think it is not a good question. because the order of the db object'key is not consistent. the root of this problem is the data structure——db. if db can't be changed, there is no answer.

[Chris Cirefice]

Even though it's a year old, I disagree with you @island205. This question was something I was going to ask, even though I had a hunch it couldn't be accomplished. The accepted answer also gave me a work-around; though it complicates the process a bit, it is an effective solution.

[Justin Summerlin]

indexOf is O(N), and .keys creates a copy of every key on every invocation (O(N) in both runtime and memory space)

[janith]

Yes, I agree. Didn't think of it. I think @andbeyond 's answer, or something along that line can be used since it saves memory

[epidemian]

@just2n Fair enough, those are all valid points. About the performance overhead, i think we don't have much information about the size of the input or whether this is a performance-critical operation. Without knowing much about how this is going to be used, or even how the input is constructed, i find it difficult to claim that the performance overhead of this solution versus others would be noticeable. About the order of Object.keys, yes, it's undefined, that's why i mentioned it in the "pragmatic" solution, which is not very correct. [...]

[epidemian]

[...] I appreciate the criticism, but i think you're being overly negative in your comment. There is no indication that the answer was accepted based solely on reputation; maybe the OP thought the code was simpler to understand/maintain or they simply preferred the approach of storing everything into a plain array.

[Chewie The Chorkie]

Object.keys has excellent support. Currently, the only major browser versions not compatible are IE 6-8.

[Hashan]

Excellent answer!