Move array element to the first position

Question

I wrote an update() function to make an entry the first element in an array.

var arr = [
    {v: 1},
    {v: 2},
    {v: 3},
    {v: 4},
];

function update(e) {
    var i = arr.findIndex(o => o.v === e.v);
    if (i === 0) return;
    if (i > 0) arr = [e].concat(arr.slice(0, i), arr.slice(i+1));
    if (i < 0) arr = [e].concat(arr.slice(0, arr.length - 1)); // keep the array has 4 elements
}

update({v: 1});
update({v: 2});
update({v: 6});

Is there any better way to do this? I think slice and concat will make the performance not good.

Answer 1

function update(e) {

    // find index
    var i = arr.findIndex(o => o.v === e.v);

    // if already at start, nothing to do
    if (i === 0) return;

    // remove old occurrency, if existing
    if (i > 0) {
        arr.splice( i, 1 );
    }

    // add e to the start
    arr.unshift( e );

    // keep array at the correct size
    arr.length = Math.min( arr.length, 4 );
}

Somewhat less code. I don't know about the performance.

Answer 2

Here's a functional solution that might perform well on a browser with tail recursive optimizations. Unfortunately, jsperf is down, so I can't get any metrics for you.

var arr = [
    {v: 1},
    {v: 2},
    {v: 3},
    {v: 4},
];

const moveFirstToHead = ([head, ...tail], predicate, accumulator = []) =>
  (predicate.call(null, head)) ?
    [head].concat(accumulator).concat(tail) :
    moveFirstToHead(tail, predicate, accumulator.concat(head));


const result = moveFirstToHead(arr, element => element.v === 3);
console.log(result);

Answer 3

Wow lots of inefficient operations... Why don't you just swap the first one with the one you want to be the first ... even by de-structuring just to make it look cooler.

This is how i would do it;

var arr = [
           {v: 1},
           {v: 2},
           {v: 3},
           {v: 4},
          ],
 update = (a,e) => { var i = a.findIndex(o => o.v === e.v);
                     i > 0 ? ([a[0],a[i]] = [a[i],a[0]]) : i && a.splice(0,0,e);
                     return a;
                   };

update(arr,{v: 1});
console.log(arr);
update(arr,{v: 2});
console.log(arr);
update(arr,{v: 6});
console.log(arr);

Well OK. as per @roger's comment if swap is not desired the following snippet should handle the requested action. It removes the requested element and inserts it at index 0 position.

var arr = [
    {v: 1},
    {v: 2},
    {v: 3},
    {v: 4},
];

 update = (a,e) => { var i = a.findIndex(o => o.v === e.v);
                     i > 0 ? a.splice(0,0,a.splice(i,1)[0]) 
                           : i && a.splice(0,0,e);
                     (a.length > 5) && a.length--
                     return a;
                   };

update(arr,{v: 3});
console.log(arr);

Answer 4

There are several modes when checking equality, Abstact (==), Strict (===), Same Value Zero, Same Value (Object.is) and some others like nodes deepEqual. Each will give you different results, depending on your values. I will go with Strict equality as that is what you have used.

You have tagged the question ES6, so I will go with that and I am going to use the iterator feature.

I notice that you wish to keep the array the same length as the original, even if the supplied item is prepended to the array. You also speak like scaling is going to be an issue, so I will add some tests that will use a reasonably large data set.

var arr = [
    {v: 1},
    {v: 2},
    {v: 3},
    {v: 4},
];

// using iterators
function update(e) {
  const length = arr.length;
  const it = arr.entries();
  let item = it.next();
  while (!item.done) {
    if (item.value[1].v === e.v) {
      if (item.value[0] === 0) {
        return;
      }
      e = arr.splice(item.value[0], 1)[0];
      break;
    }
    item = it.next();
  }
  arr.unshift(e);
  arr.length = length;
}

update({v: 1});
update({v: 2});
update({v: 6});
console.log(arr);

And here are some tests.

const Darr = [];
for (let x = 0; x < 100000; x += 1) {
	Darr.push({v: x});
}
console.log('Original array length: ', Darr.length);
let arr;

function test(fn) {
	arr = Darr.slice();
  let count = 1000;
  const Ts = performance.now();
  while (count) {
    fn({v: 1});
    fn({v: 2});
    fn({v: 10000001});
    count -= 1;
  }
  const Te = performance.now();
  console.log(`name: ${fn.name} time: ${Math.ceil(Te - Ts)} items: ${arr.length}`);
}

// code from your question
function update(e) {
    var i = arr.findIndex(o => o.v === e.v);
    if (i === 0) return;
    if (i > 0) arr = [e].concat(arr.slice(0, i), arr.slice(i+1));
    if (i < 0) arr = [e].concat(arr.slice(0, arr.length - 1)); // keep the array has 4 elements
}
test(update);

// using iterators
function update1(e) {
  const length = arr.length;
  const it = arr.entries();
  let item = it.next();
  while (!item.done) {
    if (item.value[1].v === e.v) {
      if (item.value[0] === 0) {
        return;
      }
      e = arr.splice(item.value[0], 1)[0];
      break;
    }
    item = it.next();
  }
  arr.unshift(e);
  arr.length = length;
}
test(update1);

// other answers
function update2(e) {

    // find index
    var i = arr.findIndex(o => o.v === e.v);

    // if already at start, nothing to do
    if (i === 0) return;

    // remove old occurrency, if existing
    if (i > 0) {
        arr.splice( i, 1 );
    }

    // add e to the start
    arr.unshift( e );

    // keep array at the correct size
    arr.length = Math.min( arr.length, 4 );
}
test(update2);

const update3 = (e) => { var i = arr.findIndex(o => o.v === e.v);
                     i > 0 ? arr.splice(0,0,arr.splice(i,1)[0]) 
                           : i && arr.splice(0,0,e);
                     (arr.length > 5) && arr.length--
                     return arr;
                   };
test(update3);