Shuffle Linked List

5 posts / 0 new
Last post
DanielAllsopp
DanielAllsopp's picture
Offline
Last seen: 8 years 1 month ago
Joined: 2011-08-16 17:27
Shuffle Linked List
Hi all! Just trying to shuffle the entries in an Exec double-linked list and was wondering if anyone has any handy code I could use before I start delving into something complicated. Thanks, Daniel
salass00
salass00's picture
Offline
Last seen: 1 month 1 week ago
Joined: 2011-02-03 11:27
int32 CountNodes (struct List
  1. int32 CountNodes (struct List *list) {
  2. struct Node *node;
  3. int32 cnt = 0;
  4. for (node = IExec->GetHead(list); node; node = IExec->GetSucc(node)) {
  5. cnt++;
  6. }
  7. return cnt;
  8. }
  9.  
  10. struct Node *GetNthNode (struct List *list, int32 index) {
  11. struct Node *node;
  12. int32 i = 0;
  13. for (node = IExec->GetHead(list); node; node = IExec->GetSucc(node)) {
  14. if (i == index) {
  15. return node;
  16. }
  17. i++;
  18. }
  19. return NULL;
  20. }
  21.  
  22. void ShuffleList (struct List *source, struct List *dest) {
  23. struct Node *node;
  24. int32 cnt;
  25. cnt = CountNodes(source);
  26. while (cnt > 0) {
  27. node = GetNthNode(source, rand() % cnt);
  28. IExec->Remove(node);
  29. IExec->AddTail(dest, node);
  30. cnt--;
  31. }
  32. }
The above code which I quickly put together uses the rand() clib function for random number generation so you may want to seed it first using srand(time(NULL)) f.e. or replace with your own code using UNIT_ENTROPY of timer.device f.e.. If you want to do an in place shuffle then you can do it like this:
  1. void InPlaceShuffleList (struct List *list) {
  2. struct List temp;
  3. temp = *list;
  4. IExec->NewList(list);
  5. ShuffleList(&temp, list);
  6. }
trixie
trixie's picture
Offline
Last seen: 2 weeks 3 days ago
Joined: 2011-02-03 13:58
Thanks Fredrik, very useful!
Thanks Fredrik, very useful!
SAM440ep-flex @ 667MHz / 1GB RAM / Radeon 9250 / AmigaOS 4.1 Final Edition Author of WordNet for OS4
DanielAllsopp
DanielAllsopp's picture
Offline
Last seen: 8 years 1 month ago
Joined: 2011-08-16 17:27
Thanks Salass00, that's the
Thanks Salass00, that's the way I ended up doing in the end. I just thought there would be a different method involving changing the pointers etc. but this seems to be the safest route. Thanks again!
salass00
salass00's picture
Offline
Last seen: 1 month 1 week ago
Joined: 2011-02-03 11:27
If you want to do an in place
If you want to do an in place shuffle then you can do it like this:
  1. void InPlaceShuffleList (struct List *list) {
  2. struct List temp;
  3. temp = *list;
  4. IExec->NewList(list);
  5. ShuffleList(&temp, list);
  6. }
This won't work. Use this instead:
  1. void InPlaceShuffleList (struct List *list) {
  2. struct List temp;
  3. IExec->NewList(&temp);
  4. ShuffleList(list, &temp);
  5. IExec->MoveList(list, &temp);
  6. }
Log in or register to post comments