How to move an element within a vector?

[Hussein B.]

Hi,

For a vector like [A B C D E], how to remove an element to a specific location? For example [A D B C E] ?

I thought about converting the vector into array but I would feel bad if I did that.

What would be the idiomatic way to do that in Clojure?

Thanks for help and time.

[Fluid Dynamics]

On Tuesday, August 25, 2015 at 1:06:30 PM UTC-4, Hussein B. wrote:

Hi,

For a vector like [A B C D E], how to remove an element to a specific location? For example [A D B C E] ?

How about (assoc (assoc v j (v i)) i (v j)), once you have the indices i and j of two elements you wish to swap?

If you want to actually slide all the other elements to the right, though, then vectors are not well designed for that. In fact doing such a move with arrays, vectors, *or* lists will take time linear in whichever index is larger, the position to move from or the position to move to.

[Georgi Danov]

How about filtering?
BTW I don't see how it would help converting to array - what would be the solution then?

[Linus Ericsson]

It is correct that vectors aren't a suitable choice for datastructures that need "random-access-removal". The problem is that you seem to need both fast index lookup and be able to access elements "after" removed elements quickly even when there are holes in the backing array.

There are some solutions. One is to use clojure.core/subvec, to keep the parts of the vector that should be kept, and concat these two sub vecs. I'm not sure if the removed element will be garbage collected - subvec reuses the structure of original vector, no copying seems to be done, so no "removed" element will be garbage collected until all subvecs of the original vector are realized as some other collection! If you are unsure about why (or, equally likely, prove me wrong), please refer to http://hypirion.com/musings/understanding-persistent-vector-pt-1

There are also the finger-trees, which are not as wide as PersistentVector and are more suitable for splitting etc. Probably one could construct a datastructure more suitable for random access removal with that.

https://github.com/clojure/data.finger-tree

If the hotspot of your application is to quickly lookup things in vectors and quickly remove individual elements it feels like it exists some clever datastructure that, given an virtual index in the (partially shadowed) vector, increments the lookup index for each removed element before the virtual position, to compensate for the holes in the vector, but that was probably not really your question.

However, the problem is to find datastructures which both allow quick lookup and can keep track of the lookup when parts of the datastructure are marked as removed.

What ever you do, make sure to profile it so that you don't hunt for performance in vain.

/Linus

[Sébastien Béal]

This is a old post but I made a few simple helpers to work with vectors that would solve your problem I believe:

https://gist.github.com/sebastibe/27be496c34ba6a3cce3b6425810a3dda