Conditional swapping of items in an array

Question

I have a collection of items of type A, B, and C. I would like to process the collection and swap all A and B pairs, but if there is C (which is also a collection), I want to process that recursively.

So

#(A1 A2 B1 B2 A3 #(A4 A5 B3) )

would be translated into

#(A1 B1 A2 B2 A3 #(A4 B3 A5) )

The swap isn't transitive so #(A1 B1 B2) will be translated into #(B1 A1 B2) and not #(B1 B2 A1).

I wanted to use overlappingPairsDo: but the problem is that the second element is always processed twice.

Can this be achieved somehow with Collection API without resorting to primitive forloops?

I am looking for readable, not performant solution.

Answer 1

I think my solution below should do what you're after, but a few notes up front:

• The "requirements" seem a bit artificial - as in, I'm having a hard time imagining a use case where you'd want this sort of swapping. But that could just be my lack of imagination, of course, or due to your attempt to simplify the problem.
• A proper solution should, in my opinion, create the objects required so that code can be moved where it belongs. My solution just plunks it (mostly) in a class-side method for demonstration purposes.
• You're asking for this to be "achieved somehow with [the] Collection API without resorting to primitive for[-]loops" - I wouldn't be so quick to dismiss going down to the basics. After all, if you look at the implementation of, say, #overlappingPairsDo:, that's exactly what they do, and since you're asking your question within the pharo tag, you're more than welcome to contribute your new way of doing something useful to the "Collections API" so that we can all benefit from it.

To help out, I've added a class SwapPairsDemo with two class-side methods. The first one is just a helper, since, for demonstration purposes, we're using the Array objects from your example, and they contain ByteSymbol instances as your A and B types which we want to distinguish from the C collection type - only, ByteSymbols are of course themselves collections, so let's pretend they're not just for the sake of this exercise.

isRealCollection: anObject

^anObject isCollection
    and: [anObject isString not
    and: [anObject isSymbol not]]

The second method holds the code to show swapping and to allow recursion:

swapPairsIn: aCollection ifTypeA: isTypeABlock andTypeB: isTypeBBlock

| shouldSwapValues wasJustSwapped |
shouldSwapValues := OrderedCollection new: aCollection size - 1 withAll: false.
aCollection overlappingPairsWithIndexDo: [:firstItem :secondItem :eachIndex |
    (self isRealCollection: firstItem)
        ifTrue: [self swapPairsIn: firstItem ifTypeA: isTypeABlock andTypeB: isTypeBBlock]
        ifFalse: [
            shouldSwapValues at: eachIndex put: ((self isRealCollection: secondItem) not
                and: [(isTypeABlock value: firstItem)
                and: [isTypeBBlock value: secondItem]])
            ]
    ].
(self isRealCollection: aCollection last)
    ifTrue: [self swapPairsIn: aCollection last ifTypeA: isTypeABlock andTypeB: isTypeBBlock].
wasJustSwapped := false.
shouldSwapValues withIndexDo: [:eachBoolean :eachIndex |
    (eachBoolean and: [wasJustSwapped not])
        ifTrue: [
            aCollection swap: eachIndex with: eachIndex + 1.
            wasJustSwapped := true
            ]
        ifFalse: [wasJustSwapped := false]
    ]

That's a bit of a handful, and I'd usually refactor a method this big, plus you might want to take care of nil, empty lists, etc., but hopefully you get the idea for an approach to your problem. The code consists of three steps:

1. Build a collection (size one less than the size of the main collection) of booleans to determine whether two items should be swapped by iterating with overlappingPairsWithIndexDo:.
2. This iteration doesn't handle the last element by itself, so we need to take care of this element possibly being a collection in a separate step.
3. Finally, we use our collection of booleans to perform the swapping, but we don't swap again if we've just swapped the previous time (I think this is what you meant by the swap not being transitive).

To run the code, you need to supply your collection and a way to tell whether things are type "A" or "B" - I've just used your example, so I just ask them whether they start with those letters - obviously that could be substituted by whatever fits your use case.

| collection target isTypeA isTypeB  |
collection := #(A1 A2 B1 B2 A3 #(A4 A5 B3) ).
target := #(A1 B1 A2 B2 A3 #(A4 B3 A5) ).
isTypeA := [:anItem | anItem beginsWith: 'A'].
isTypeB := [:anItem | anItem beginsWith: 'B'].
SwapPairsDemo swapPairsIn: collection ifTypeA: isTypeA andTypeB: isTypeB.
^collection = target

Inspecting this in a workspace returns true, i.e. the swaps on the collection have been performed so that it is now the same as the target.