# Multiple key swap algorithm [closed]

I have a dictionary with key - data pairs. My data comes from excel sheets. When I create the dictionary my objects are placed in order by their keys ex. 1 -> data of sheet1, 2 -> data of sheet2 ... When I physically reorder my sheets ex I move sheet1 to the last position I want to reconstruct the dictionary keys so that every key points to the correct sheet index.

I track when sheet indexes change inside Worksheet_Calculate function so I can get results like

function executes... prints: "OLDKEY:3 must change to newkey: 2"

function executes... prints: "OLDKEY:1 must change to newkey: 5"

function executes.... prints: "OLDKEY:4 must change to newkey: 3"

and so on

I cannot track those changes before or after the function runs so the swap must be done inside the function

So my algorithm goes as follows:

    If mydictionary.Exists(newkey) Then

If mydictionary.Exists(OLDKEY & "t") Then
mydictionary.key(newkey) = newkey & "t"
mydictionary.key(OLDKEY & "t") = newkey
Else
mydictionary.key(newkey) = newkey & "t"
mydictionary.key(OLDKEY) = newkey
End If
Else
If mydictionary.Exists(OLDKEY & "t") Then
mydictionary.key(OLDKEY & "t") = newkey
Else
mydictionary.key(OLDKEY) = newkey
End If
End If


As my data relies heavily on this indexing I would like an opinion if this algorithm has a bug.

• Is that code complete? Where are mydictionary, OLDKEY and newkey defined? And what language is that? Commented Apr 26 at 16:18
• This is vba code. I'm mainly interested for the algorithm. Keys can be anything like numbers or strings. In case of integers instead of adding a "t" at the end I multiply the key by -1. Commented Apr 26 at 20:48
• Excuse my ignorance (I don't know VBA), but I can't see in the code where that multiplication happens. Have you definitely presented complete code? Also, do you have any unit tests that demonstrate how it's called and that it functions correctly? Commented Apr 27 at 5:22

You describe this as "key swap", but I suggest that you think of it as "key remapping".

# approach

When I physically reorder my sheets

I suggest you think in terms of logically reordering the sheets. This stems from the Fundamental theorem of software engineering:

"We can solve any problem by introducing an extra level of indirection."

Here, I'm proposing a permutation that maps from old to new, for your 0 .. N-1 sheets. Significantly, it is very cheap to manipulate a permutation of N integers.

To model e.g. four sheets, start with a vector [0, 1, 2, 3] which offers the identity mapping. You mention that you might move the zeroth sheet to the last position. That gives us [1, 2, 3, 0]. Sure, it has $$\O(N)\$$ linear cost, but we anticipate $$\N \ll 10^6\$$, and the constant being hidden within Big-Oh is pretty small for those integers.

I cannot track those changes before or after the function runs so the swap must be done inside the function.

I choose to reject that assertion. Let the zeroth sheet retain a name of 0 across your sequence of move operations, so it might appear in the ultimate position as above, and then in the penultimate position. Similarly for all other sheets. Then after the final move operation, make a final pass across all sheets, outputting them in their final destination position.

Significantly, it is very easy to verify if an implementation is correct, since it continually obeys the following invariant:

We always have a permutation of 0 .. N-1

During debugging you can verify this at any step, by sorting a copy of those integers and using a counting loop to ensure each appears just once. If you have N distinct integers, then you've not lost any of the sheets.

     If mydictionary.Exists(OLDKEY & "t") Then ...


The Review Context or a comment should explain that

1. We're using a certain programming language (I don't recognize which one)
2. The & operator performs string catenation, e.g. "hello " & "world"
3. Keys are drawn from a restricted namespace, and never end with "t"
4. We're inventing a Temporary namespace by appending "t" to keynames, in order to implement swap(a, b) with: t = a; a = b; b = t

And then when the swap() function exits, its local temp var t is destroyed when it goes out of scope, so it can't cause any confusion in future. In contrast, it appears that you never delete a key, so we permanently wind up with both "SHEET7" and "SHEET7t" in the dictionary, a confusing state of affairs when debugging.

# invariants

I would like an opinion if this algorithm has a bug.

I share your trepidation. I don't know. Source code has a greater responsibility than to be Correct. Rather, it must be Obviously Correct.

This algorithm has clear potential for destroying information if we accidentally step on a keyname before preserving it.

You haven't offered any intellectual scaffolding for making a convincing argument that such an accident never happens. I'm looking for comments which disclose invariants that demonstrate safety, and perhaps variants which assure us that we're making forward progress toward some measurable goal.

If you offered us better tools for reasoning about the code, we likely could make stronger assertions about its correctness. I proposed the permutation datastructure as one possible way out. There are others, including using whole-sheet content hashes.

• J_H yes this algorithm runs N times. Tested several times for 10000 oldkeys and 10000 randomly ordered newkeys and works without any errors. When the function runs I don't know the number of keys that must be changed. Commented Apr 26 at 20:50