Moving the selected items of a listbox UP or DOWN [C# 2002]

[Shaitan00]

Given a form (frmMain) which contains a listbox "lbSelected" (multi-select) and 2 control buttons "btnMoveUp" & "btnMoveDown" that should allow the user to move the selected items (from the listbox) up or down using the buttons. Thing is I have no clue how to change the index of a selected item in a listbox, forget trying to handle multi-select - so I was hoping maybe someone could give me some help/hints.

So far I got to this point:

// Get the current index of all selected items in the listbox
ListBox.SelectedIndexCollection indxcolSelected = lbSelected.SelectedIndices;

So this will give me the index of each of the selected items...

Consequently it could also be good to do it this way I imagine:

ListBox.SelectedObjectCollection objcolSelected = lbSelected.SelectedItems;

Where I am getting the list of selected items instead and somehow modifiying their index?

Now I need to find a way to either +1 or -1 each of the corresponding items indexes (depending on if I am going UP or DOWN) and always be careful that I am not already at the top or bottom...

Any help would be greatly appreciated.
Thanks,

 

[MrPaul]

Remove and insert items

The only way to change the index of an item is to remove it from the listbox then insert it again at the desired index. If moving multiple items it might be prudent to call BeginUpdate before making the changes and EndUpdate when complete, to stop the listbox redrawing itself each time an object is removed or inserted.

Good luck

 

[mskeel]

Re: Remove and insert items

If moving multiple items...

I was unable to find anything on the specific implementation of the ListBox.ObjectCollection class. My concern is that if the collection is implemented as an array then by default an insert is going to be an expensive operation as the Insert method will iterate through, in the average case, half the list. If you have a ton of items in your listbox, reordering items will always be an expensive operation. If the ListBox.ObjectCollection is implemented as a linked list, there is no hit for inserting.

Does anyone know the specific performance implications of Insert() in ListBox.ObjectCollection?

 

[snarfblam]

Re: Remove and insert items

ListView.ObjectCollection stores its items internally within a ListView.ItemArray, which, in turn, stores items in an array of ListView.ItemArray.Entry objects which stores your actual item and a small amount of data for managing the entry. Or, to put it simply, the items are ultimately stored in an array. Regardless, these sort of operations do not become particularly "expensive" until they are performed an enormous number of times or they are performed on extremely large arrays. What you are really looking at here is a very small bit-block transfer for each insertion.

What would concern me more would be the UI and Win32 updates that have to be made for each insertion which could very well be slow and ugly, regardless of the internal representation of this list.

 

[mskeel]

Re: Remove and insert items

What you are really looking at here is a very small bit-block transfer for each insertion.

I wasn't making any assumptions about the size of the ObjectCollection, just thinking about the data structure and the operations to be performed. If the set size is small enough (or not too big if you prefer a glass half-full point of view) then neither order nor UI updates will be an issue. My original post was with regards to the fact that it takes O to remove then insert an item because you have to shift items in the array which takes time. For example, if you insert something at index 0, you have to move everything in the array up and index. The expense isn't in the size of the object moved but in the act of copying everything in the array every time you remove then insert something. With a linked list, inserting an item takes O(1). That is a big difference.

BUT because we're not looking to insert anything new, just shift stuff, removing the item and then inserting it is really an expensive (but easy) way to simply swap something:

//psuedo code
object selected = list[the currently selected index]
object swap = list[currently selected index - 1] // do bounds checking before this because this could give an index out of bounds if the first item is selected.

//swap, essentially moving selected up the list
list[the currently selected index] = swap
list[currently selected index - 1] = selected

swap = null
selected = null

// moving an item down the list would just involve the opposite math

You'll need to check the boundary cases to make sure it doesn't barf and also extend it to be able to handle multiple inserts but it should not be too difficult to see how it would work.

Also, &#91 ; is supposed to be a [ (left bracket). I think there's a bug in the bug forum for that already.

 

[snarfblam]

Re: Remove and insert items

Mskeel, I understand that a linked list makes for quicker insertion. I wasn't disagreeing. But now that we are on the topic, when you say:

The expense isn't in the size of the object moved but in the act of copying everything in the array every time you remove then insert something. With a linked list, inserting an item takes O(1). That is a big difference.

You are looking too hard at the concept and not hard enough at its practical application. My whole point was that the insertion in an array-like list merely requires a bit-block transfer. Yes, that is an O(1) versus O difference, but what does that mean? It means that as n becomes excessively large the performance of the O operation will become unacceptable. That begs the question, what does it mean to be excessively large? To keep things in perspective, remember that the operation we are performing is a bit-block transfer. A bit-block transfer is generally a very fast operation. Realize that when you modify the list, you would need to have thousands (if not tens of thousands) of items in the list before the bit-block transfer performed on the array became larger than the bit-block transfers that are performed to update the screen (this is my segue from philosophy to reality).

My point is, quite simply, that the manipulation of this list will almost certainly be less costly than the updates that will be performed on the UI. The performance cost will (very likely) be negligible. Even when we are moving multiple items and we consider the fact that the list has to be modified twice to swap the position of an item, it doesn't add up to much. Besides, we have no control over the internal representation of a ListBox's item collection. Your real concern should be minimizing unnecessary UI updates so that things don't get ugly.

 

[mskeel]

Re: Remove and insert items

I don't want to risk getting too far off topic (too late?) but I think this discussion is at least tangentially relevant.

The amount of time it takes to copy something is irrelevant. The fact that, in the worst case, every item in the array must be copied when inserting an item into the array is the important piece of information. To put it simply, insert uses a loop and the amount of time it takes depends on the number of items in the array whereas swap will always take 1 iteration to complete -- there is no loop when swapping.

I think it is always best plan for scalability when you can, especially when it is easy. O versus O(1) is a no brainer -- bit-block transfer takes 1 unit of time no matter which way you look at it so why do it more than you need to?

 

[MrPaul]

Swapping vs inserting

because we're not looking to insert anything new, just shift stuff, removing the item and then inserting it is really an expensive (but easy) way to simply swap something:

I was under the impression that the ListBox.ObjectCollection indexer was a read-only property, thus requiring the seperate remove and insert. I just checked and it can also be set so your swapping code snippet should work as with any regular list/array.

object temp = list.Items[index];
list.Items[index] = list.Items[index + 1]; //Or minus 1
list.Items[index + 1] = temp;

Learn something new every day.

 

[snarfblam]

Re: Remove and insert items

I think it is always best plan for scalability when you can, especially when it is easy. O versus O(1) is a no brainer -- bit-block transfer takes 1 unit of time no matter which way you look at it so why do it more than you need to?

I tend to apply concepts such as scalability, extensibility, abstraction, etc. with discretion: only when I foresee a need. It is enough effort to consistently write code that is well formed and self-explanatory (or commented). Most of the time, I simply focus on getting the job done. Otherwise I tend not to get the job done. Perhaps this is due to differences between commercial programming and hobby programming. Ideally, all code would always be extremely scalable, just in case, but you can't cover every single base or over-analyze every aspect of every bit of code. Otherwise the project never gets finished.

You seem really intent on your O versus O(1) point. The concept is absolutely correct and certainly has merit. I don't argue that. If someone said, "Hey, you, there, programmer guy, which would you prefer? O or O(1)?" Well, then, yes, it is a no brainer. But that's not what's happening. Someone is writing code, and anything that works in all foreseeable, reasonable, realistic cases is fine by me, even if it does not satisfy every ideal of computer science.

When your listbox begins to contain hundreds of thousands of items bottlenecks will pop up everywhere. How items are moved up and down the list will be the least of your problems. Am I saying that your solution is not better? Of course not. I'm saying that it is better in a way that probably won't matter, based on a concept that is not really truly relevant (not because it can not be applied, but because it applies only beyond the domain of reality).

And what I am really getting at, what this really breaks down to, is that what you are touting is micro-optimization, and there is no need to do it. Frankly, it is hardly worth all this discussion for something particularly trivial. It just frustrates me when I reiterate that I am not arguing with the concept, but rather with the conclusion, and I just keep getting the concept explained back to me, as though I must not understand it because I didn't reach the same conclusion. I've shared my two cents, and then some, and I think I've thoroughly explained my logic. Feel free to rebut, but I think there is more than enough information and opinion expressed here, and I'm done. These days it seems I spend more time discussing and less time doing.

 

[mskeel]

Spawning a new discussion

It just frustrates me when I reiterate that I am not arguing with the concept, but rather with the conclusion, and I just keep getting the concept explained back to me, as though I must not understand it because I didn't reach the same conclusion.

Point taken.

Since I enjoy these types of design discussions more than writing actual code I've spawned a thread over in the Off-topic section to continue if you (or anyone else) would like: Optimization Opinions

It's related in concept but not necessarily the specifics discussed here -- I'd consider this thread a dead horse beaten brutally.