List/Array Expansion Question

Questions
1

Hi there -

I’d like to make a fixed array of 4 values - and I’d like to add items to the beginning of the array, while bumping the previous values one place down. The last place would be deleted. For some reason, I’m finding this a little challenging, as my arrays seem to expand and there doesn’t seem to be a method for pushing the array. I can maybe think of a more code-intensive way of doing it, but I’m curious if there is a simple way, first.

Thank you

3

A shift register, basically.

Assuming list already has 4 elements, here are a few:

list = (newItem ++ list).keep(list.size);

list = list.insert(0, newItem).keep(list.size);

list = list.rotate(1).put(0, newItem);

// or, if it absolutely must be done in-place
list.doAdjacentPairs { |a, b, i|
    list[i+1] = a
};
list[0] = newItem;

I’m sure there are others.

hjh

1 Like
4

I think I do want to make a shift-register - I am running into a small snag with your example, though… I converted it to environmental variables, so as to just run the code - but I’m confused about a few things, since it doesn’t entirely seem to work for me:

~newItem = 1;
~list = [20, 30, 40, 90].asList;

~list = (~newItem++~item).keep(~list.size);  //ERROR: Message '++' not understood.
~list = (~list++~newItem).keep(~list.size);  //deletes new item, since it falls outside of list size. 
~list = ~list.insert(0, ~newItem).keep(~list.size);  //seems to expand list size?
~list = ~list.rotate(1).put(0, ~newItem);  //works as expected here..
5

How about this?

~newItem = 1; // -> 1
~array = [20, 30, 40, 90]; // -> [20, 30, 40, 90]
~sizeA = ~array.size; // -> 4

~array = ([~newItem] ++ ~array).keep(~sizeA); // -> [1, 20, 30, 40]

~array = ~array.insert(0, ~newItem).keep(~sizeA); // -> [1, 1, 20, 30]

I think the use of list is not appropriate here:

~newItem = 1; // -> 1
~list = List[20, 30, 40, 90]; // -> [20, 30, 40, 90]
~sizeL = ~list.size; // -> 4

([~newItem] ++ ~list).keep(~sizeL); // -> [1, 20, 30, 40]
~list

~list.insert(0, ~newItem).keep(~sizeL); // -> [1, 1, 20, 30]
~list
2 Likes
6

Those are my mistakes, writing on the phone and missed a couple details… oops.

prko’s alternate ([~newItem] ++ ~list) is good.

.insert, I forgot that it might alter the size of the given array rather than returning a new array – so indeed, the size could have been wrong. Since you don’t want the size to change, prko’s idea (to save the size in a variable) is valid.

hjh

2 Likes
7 
+ Array {
    addFirstLastOut { |newItem|
		var size = this.size;
        var buffer = this.copy;
        var currentIndex = size - 1;

        while { currentIndex > 0 } {
            buffer[currentIndex] = buffer[currentIndex - 1];
            currentIndex = currentIndex - 1;
        };
        buffer[0] = newItem;
        ^buffer.keep(size);
    }
8 
+ List {
    addFirstLastOut { |newItem|
        this.addFirst(newItem); 
        this.removeAt(this.size - 1);  
        ^this;
    }
}
9

@smoge
After seeing your new methods, I re-read the documentation and made a PR with .clipInsert for ArrayedCollection and List:

I think your addFirstLastOut is good too! Could you consider doing a PR with this idea?

1 Like
10

The second one has complexity O(1), the other is O(n). I didn’t spend much time on this, didn’t check them; you can borrow the code and do a pr if you want, it would be an honor.

1 Like
11

I think only a linked list can do this with complexity O(1) – if it’s an array, you have to shift elements, and that’s going to be O(n). The O(n) bit may be hidden in primitives but it’s got to be there.

hjh

12

Do you mean both List and Array? Yes, I was looking just from the sclang side. Maybe just a primitive can deliver this. You’re talking about memory movement costs, maybe that’s an idea for a new collection type.

Implementation is on textbooks: Implementation of Deque using doubly linked list - GeeksforGeeks

13

Negligible for a 4 element array, or a 400 element array. I don’t think it’s necessary to absolutely hyper-optimize everything.

LinkedList already exists – O(1) for push/pop at head or tail, O(n) for random access (where arrays are O(1) random access, O(n) push/pop at the head).

hjh

14

It’s just a method one can use with any number of elements. I didn’t propose the code; it’s not a PR here. The second one is just simpler, and from the point of view of sclang code logic, it is less complex. That’s all.