Find next available id in array of objects

Question

I have an array of objects. These objects have a property id. I need a function which returns the next available id (which is not used by an object).

array = [ { id: 1 }, { id: 2 }, { id: 5 }, { id: 3 } ]

I would like to have a function which takes an array as an input and returns a number (which is the next free id).

In the example case:

findFreeId(array){ magic happens }

result --> 4

Answer 1

How about something like this?

function findFreeId (array) {
  const sortedArray = array
    .slice() // Make a copy of the array.
    .sort(function (a, b) {return a.id - b.id}); // Sort it.
  let previousId = 0;
  for (let element of sortedArray) {
    if (element.id != (previousId + 1)) {
      // Found a gap.
      return previousId + 1;
    }
    previousId = element.id;
  }
  // Found no gaps.
  return previousId + 1;
}

// Tests.
let withGap = [{id: 1}, {id: 2}, {id: 5}, {id: 3}];
let noGap = [{id: 1}, {id: 2}];
let empty = [];

console.log(findFreeId(withGap)); // 4
console.log(findFreeId(noGap)); // 3
console.log(findFreeId(empty)); // 1

Answer 2

A simple approach is to get all the ID values, sort them, then starting at 0 look for the first missing number in the sequence. That may be OK where efficiency doesn't matter, but a more efficient method is to:

1. Get the IDs
2. Sort them
3. Step through the values to get the next available number
4. Insert the value in the list of IDs
5. Store the value so next time it starts at #3 from the previous value + 1

E.g.

class IDStore {
  constructor(dataArray) {
    if (!Array.isArray(dataArray)) {
      return null;
    }
    this.previousIndex = 0;
    this.indexes = dataArray.map(obj => obj.id).sort();
  }
  
  get nextIndex() {
    while (this.indexes[this.previousIndex] == this.previousIndex) {
      this.previousIndex++;
    }
    return this.previousIndex;
  }
  
  addIndex(index) {
    if (!Number.isInteger(index) || this.indexes.find[index]) {
      return null;
    }
    this.indexes.push(index);
    this.indexes.sort();
    return index;
  }
}

var data = [ { id: 1 }, { id: 2 }, { id: 5 }, { id: 3 } ];

// Create an ID store
var idStore = new IDStore(data);

// Insert more objects in the array with unique IDs
for (var i=0, next; i<4; i++) {
  // Current list of indexes
  console.log('Indexes: ' + idStore.indexes);
  // Get the next available index
  next = idStore.nextIndex;
  console.log('Next available: ' + next);
  // Calling nextIndex doesn't affect next index
  next = idStore.nextIndex;
  console.log('Next available: ' + next);

  // Use next index
  data.push({id: next});
  // Adding next index is manual
  idStore.addIndex(next);
  console.log('Added: ' + next);
}

// Data structure is independent
console.log('End: ' + JSON.stringify(data));

This is somewhat simplistic in that it assumes the IDs are sequential integers starting at 0 and doesn't have much validation or error handling.

Maintaining the id is separate from adding new members to the data array. It would be much better to combine the operations, so an "add object" method gets the next available ID, adds it to the object, adds the object to the array, updates the index and returns the new ID.

Answer 3

const findFreeId = (ids) => {
let id = 0;
for (id; ; id++) {
    let isFree = true;
    for (let i = 0; i < array.length; i++) {
        const e = ids[i];
        if (e === id) {
            isFree = false;
            break;
        }
    }
    if (isFree) break;
}
return id;
}