1. Forum
  2. Usenet
  3. COMP.OS.MS-WINDOWS.PROGRA

  • Re-ordering a list of fixed-length records in-place

    From R.Wieser@21:1/5 to All on Thu Jan 14 09:10:38 2021
    Hello all,

    I've got a series of records that I've "sorted" by using a DPA filled with indices to those records, and use DPA_Sort to sort those indices.

    I would now like to re-order the fixed-length records in the order shown by
    the DPA, and to make things interresting I would like to have that done in-place [1].

    The thing is that I've been looking at it and I do not see a simple, lineair approach to it that *doesn't* involve searching for the to-be-swapped-with record.

    Consider the below table. The first colum is the index into the DSA, the second the index the DSA holds into the actual records, and the third those records contents.

    ----|Indx|record content
    ----+----+------------
    0000 0007 I4: 00000384
    0001 0000 I4: 00000438
    0002 0008 I4: 0000087E
    0003 0002 I4: 00000915
    0004 0003 I4: 00000B14
    0005 0009 I4: 00000CD4
    0006 0004 I4: 000011FD
    0007 0001 I4: 0000198F
    0008 000A I4: 00001B74
    0009 0005 I4: 00002245
    000A 0006 I4: 000025F8

    The DSA list shows the record indices in a sorted order. But how do I now
    move the record at index 7 (DSA position 0) to record index 0 without
    trashing ther record already there (which should end up at record index 1) ?

    Am I looking for something that just can't be done under my 'no searching' condition ?

    [1] My current solution is to copy all the records, use that to copy from
    into the origional and finally delete the copy. Which severely limits the maximum size of the to-be-sorted list of records.

    Regards,
    Rudy Wieser

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From JJ@21:1/5 to R.Wieser on Fri Jan 15 07:13:11 2021
    On Thu, 14 Jan 2021 09:10:38 +0100, R.Wieser wrote:
    Hello all,

    I've got a series of records that I've "sorted" by using a DPA filled with indices to those records, and use DPA_Sort to sort those indices.

    I would now like to re-order the fixed-length records in the order shown by the DPA, and to make things interresting I would like to have that done in-place [1].

    The thing is that I've been looking at it and I do not see a simple, lineair approach to it that *doesn't* involve searching for the to-be-swapped-with record.

    Consider the below table. The first colum is the index into the DSA, the second the index the DSA holds into the actual records, and the third those records contents.

    ----|Indx|record content
    ----+----+------------
    0000 0007 I4: 00000384
    0001 0000 I4: 00000438
    0002 0008 I4: 0000087E
    0003 0002 I4: 00000915
    0004 0003 I4: 00000B14
    0005 0009 I4: 00000CD4
    0006 0004 I4: 000011FD
    0007 0001 I4: 0000198F
    0008 000A I4: 00001B74
    0009 0005 I4: 00002245
    000A 0006 I4: 000025F8

    The DSA list shows the record indices in a sorted order. But how do I now move the record at index 7 (DSA position 0) to record index 0 without trashing ther record already there (which should end up at record index 1) ?

    Am I looking for something that just can't be done under my 'no searching' condition ?

    [1] My current solution is to copy all the records, use that to copy from into the origional and finally delete the copy. Which severely limits the maximum size of the to-be-sorted list of records.

    Regards,
    Rudy Wieser

    Do everything manually.
    e.g. move record 3 to record 1 in a 5 records database.

    1. Read record 3 data into memory.

    2. Update record 3 using record 2 data.

    3. Update record 2 using record 1 data.

    4. Update record 1 using previously read record 3 data in memory.

    It's like the variable value swap trick using a third variable as a
    temporary storage.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From R.Wieser@21:1/5 to All on Fri Jan 15 11:39:10 2021
    JJ,

    Do everything manually.
    e.g. move record 3 to record 1 in a 5 records database.
    [snip]

    Thanks.

    First off, I should mention that I have consistently said DSA where I ment DPA.:-( Luckily it didn't change anything and your answer still applied.
    :-)

    I guess I was too fixed on doing everything in place (swapping records) to consider the one-record temporary storage. I did consider following those record-indices, but just could not figure out how to do the swapping without messing up records. :-|

    I also took your advice quite literally, and wrote the whole thing out. :-)
    It turns out that I only need 13 record movements that way. Which is actually less than I expected.

    It's like the variable value swap trick using a third
    variable as a temporary storage.

    :-) I always liked the XOR trick to do that /without/ a temporary variable.

    Regards,
    Rudy Wieser

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From R.Wieser@21:1/5 to All on Fri Jan 15 13:14:25 2021
    JJ,

    I guess I was too fixed on doing everything in place (swapping records)

    Thinking a bot more about your solution I realized that my swapping idea
    would still work, as it constitutes to "bubbeling" the first record to the right, moving all other records to the left :

    legenda:
    x(y,z)
    x - DPA index
    y - current record index
    z - desired record index

    '<>' swap action
    '..' completed swap action

    0(0,7) <> 7(7,1) <> 1(1,0)
    0(7,7) .. 7(0,1) <> 1(1,0)
    0(7,7) .. 7(1,1) .. 1(0,0)

    The problem that I had was that I don't directly see way to also update the indices stored in the DSA - up until that I realised that I don't need them after the swapping. Better yet, I can set them to "already swapped"
    value, so the next iteration steps see that entries #1 and #7 have already
    been processed and must be skipped.

    Regards,
    Rudy Wieser

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)