Multiple key swap algorithm [closed]

Question

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.

Answer 1

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.

comments

     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.