Login
Username:

Password:

Remember me



Lost Password?

Register now!

Sections

Who's Online
91 user(s) are online (62 user(s) are browsing Forums)

Members: 0
Guests: 91

more...

Headlines

 
  Register To Post  

Swap items in list
Just popping in
Just popping in


See User information
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)
{
}

Go to top
Re: Swap items in list
Home away from home
Home away from home


See User information
@mritter0
BOOL SwapListItems(struct List *List,uint32 Item1,uint32 Item2)
{
    
BOOL succes FALSE;
    
struct Node a, *b;
    
FindNodeByIndex(List,Item1);
    
FindNodeByIndex(List,Item2);
    if ( 
&& b)
    {
         
struct Node *s,*p;
         
a->ln_Succ;
         
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.

Go to top
Re: Swap items in list
Not too shy to talk
Not too shy to talk


See User information
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(
&& 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(
&& --Item2);
            if(
&& 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
Go to top
Re: Swap items in list
Just popping in
Just popping in


See User information
@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.

Go to top
Re: Swap items in list
Not too shy to talk
Not too shy to talk


See User information
@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.

Go to top
Re: Swap items in list
Just popping in
Just popping in


See User information
@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.

Go to top

  Register To Post

 




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




Powered by XOOPS 2.0 © 2001-2023 The XOOPS Project