add element to ordered array in CoffeeScript

Question

I have a sorted array, which I add elements to as the server gives them to me. The trouble I'm having is determining where to place my new element and then placing it in the same loop

in javascript this would look like this

for(var i = 0; i < array.length; ++i){
   if( element_to_add < array[i]){
      array.splice(i,0,element_to_add);
      break;
   }
}

The problem is that in coffee script I dont have access to the counter, so I cant tell it to splice my array at the desired index.

How can I add an element to a sorted array in CoffeeScript?

for element in array and I also tried rapping some plane javascript code in back-ticks, but it keeps on putting return infront once it's compiled — Loourr
– Loourr, Commented Jun 5, 2013 at 1:32
Assuming your array is not sorted in reverse, that code is wrong - it inserts the element just in the first position. And it forgets to break after having it inserted, so it will loop forever. — Bergi
– Bergi, Commented Jun 5, 2013 at 1:44

Blender · Accepted Answer · 2013-06-05 01:36:53Z

5

The default for loop returns the index as well:

a = [1, 2, 3]
item = 2

for elem, index in a
    if elem >= item
        a.splice index, 0, item
        break

You may want to do a binary search instead.

answered Jun 5, 2013 at 1:36

Blender

300k55 gold badges462 silver badges511 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

epidemian · Accepted Answer · 2013-06-05 02:30:21Z

2

If you are using Underscore.js (very recommended for these kind of array manipulations), _.sortedIndex, which returns the index at which a value should be inserted into an array to keep it ordered, can come very handy:

sortedInsert = (arr, val) ->
  arr.splice (_.sortedIndex arr, val), 0, val
  arr

If you're not using Underscore, making your own sortedIndex is not that hard either; is's basically a binary search (if you want to keep its complexity as O(log n)):

sortedIndex = (arr, val) ->
  low = 0
  high = arr.length
  while low < high
    mid = Math.floor (low + high) / 2
    if arr[mid] < val then low = mid + 1 else high = mid
  low

answered Jun 5, 2013 at 2:30

epidemian

19.3k3 gold badges64 silver badges73 bronze badges

Comments

WhyMe · Accepted Answer · 2013-06-05 01:29:55Z

0

If I understood you correctly, why not save the position, like so,

var pos=-1;
for(var i = 0; i < array.length; ++i){
   if( element_to_add < array[i]){

      pos=i; break;
   }
}
if(pos<0)
  array.push(element_to_add);
else array.splice(pos,0,element_to_add);

answered Jun 5, 2013 at 1:29

WhyMe

5352 silver badges13 bronze badges

Collectives™ on Stack Overflow

add element to ordered array in CoffeeScript

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related