Swap items in list

	Bottom Previous Topic Next Topic
Register To Post

mritter0

Swap items in list

Posted on: 2019/8/6 0:12 #1

Just popping in

Does anyone have some code that will swap 2 items in a List? Using Exec functions: AddHead(), Insert(), AddTail().

I have a list with 10 items. I want to swap items 4 and 5, or 7 and 3.

SwapListItems(struct List *List,uint32 Item1,uint32 Item2)
{
}

broadblues

Re: Swap items in list

Posted on: 2019/8/6 4:17 #2

Home away from home

@mritter0


BOOL SwapListItems(struct List *List,uint32 Item1,uint32 Item2)

{

    BOOL succes = FALSE;

    struct Node * a, *b;

    a = FindNodeByIndex(List,Item1);

    b = FindNodeByIndex(List,Item2);

    if ( a && b)

    {

         struct Node *s,*p;

         s = a->ln_Succ;

         p = a->ln_Pred;



         a->ln_Succ = b->ln_Succ;

         a->ln_Pred = b->ln_Pred;



         b->ln_Succ = s;

         b->ln_Pred = p;

         success = TRUE;

    }

     return success;

}

I'll leave as an excercise for the reader to write the function FindNodeByIndex() (walk the list counting as you go).

It doesn't use the Exec functions but they would just get in the way in this specialist case.

Blender For OS4.x : Blues : Walker Broad

Daytona675x

Re: Swap items in list

Posted on: 2019/8/6 6:31 #3

Not too shy to talk

This one only makes one combined run through the list instead of two independent runs as does broadblues' variant above. And in contrast to that it does correct un/re-linking for all situations. Untested

EDIT: relinking neighbours was missing!
EDIT: special case direct neighbour swap!
EDIT: some redundancy removed.
EDIT: now it should work for all (still untested though ;) )


BOOL SwapListItems(struct List *List,uint32 Item1,uint32 Item2)

{

    BOOL success=FALSE;

    // catch special case of identical indices, return immediately with success

    if(Item1!=Item2) {

        // make sure Item1 is the smaller index

        if(Item2<Item1) {

            uint32 tmp=Item1;

            Item1=Item2;

            Item2=tmp;

        }

        // adjust Item2 index so that it becomes relativ to Item1

        Item2-=Item1;

        // walk to Item1

        struct Node *a=IExec->GetHead(List);

        while(a && Item1--) {

            a=a->ln_Succ;

        }

        if(a) {

            // walk to Item2, starting from Item1.

            // we can do a do...while and pre-dec because we know that Item2 is > 0 ;)

            struct Node *b=a;

            do {

                b=b->ln_Succ;

            }while(b && --Item2);

            if(b && b->ln_Succ) { // second check is to verify that we didn't tap into the "physical" tail (or use b=IExec->GetSucc(b) in the loop)

                // the actual swap

                struct Node *s=a->ln_Succ;

                struct Node *p=a->ln_Pred;

                a->ln_Succ=b->ln_Succ;

                // b->ln_Pred=p; * bug, ouch, this one has to ... (see at bottom)

                // special case: a is direct pred of b, then a std. link swap would cause interesting stuff, like a pointing to a etc. :P

                if(s==b) {

                    a->ln_Pred=b;

                    b->ln_Succ=a;

                } else {

                    a->ln_Pred=b->ln_Pred;

                    b->ln_Succ=s;

                    // don't forget to relink the surrounding items!

                    a->ln_Pred->ln_Succ=a;

                    b->ln_Succ->ln_Pred=b;

                }

                b->ln_Pred=p; // ... * go from above to here

                // more relinking

                a->ln_Succ->ln_Pred=a;

                b->ln_Pred->ln_Succ=b;

                success=TRUE;

            }

        } 

    } else success=TRUE;

    return success;

}

Edited by Daytona675x on 2019/8/6 6:49:09
Edited by Daytona675x on 2019/8/6 8:58:16
Edited by Daytona675x on 2019/8/6 8:58:55
Edited by Daytona675x on 2019/8/6 9:49:01
Edited by Daytona675x on 2019/8/6 22:34:17
Edited by Daytona675x on 2019/8/6 22:40:55
Edited by Daytona675x on 2019/8/7 6:42:09
Edited by Daytona675x on 2019/8/7 7:12:29
Edited by Daytona675x on 2019/8/7 7:13:41

[Facebook] [YouTube Channel] [ko-fi]

mritter0

Re: Swap items in list

Posted on: 2019/8/7 0:45 #4

Just popping in

@Daytona675x

Nice! Your first version did not work, the latest one does.

Thank you both!

EDIT:
It works with neighboring nodes, but not with like 1&3, 3&7. Neighboring nodes is all I really need, though.

Daytona675x

Re: Swap items in list

Posted on: 2019/8/7 6:46 #5

Not too shy to talk

@mritter0
Oops, I think I fixed it to work for all now (see the * comments), still didn't test it

Anyway, a good example on how a even such a conceptually and technically very simply thingy requires quite some attention when it comes to implementation details.

[Facebook] [YouTube Channel] [ko-fi]

mritter0

Re: Swap items in list

Posted on: 2019/8/7 23:01 #6

Just popping in

@Daytona675x

Bingo! You got it!

I was creating a new node either before or after node1, copy node1 to new node, copy node2 to node1, delete node2. Had to modify it for every program. There should be an easier way........

Thanks for your persistence. This could help a lot of people.

Register To Post
	Top Previous Topic Next Topic

Currently Active Users Viewing This Thread: 1 ( 0 members and 1 Anonymous Users )