Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
 
How are you iterating over the array now? –  Blender Jun 5 at 1:27
 
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 Jun 5 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 Jun 5 at 1:44

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
up vote 0 down vote

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);
share|improve this answer
up vote 2 down vote

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.