Shuffle Linked List

5 posts / 0 new
Last post
DanielAllsopp
DanielAllsopp's picture
Offline
Last seen: 12 years 7 months 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 year 1 month 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: 5 months 3 hours ago
Joined: 2011-02-03 13:58
Thanks Fredrik, very useful!

Thanks Fredrik, very useful!

AmigaOne X5000-020 / 2GB RAM / Sapphire Pulse Radeon RX 560 / AmigaOS 4.1 Final Edition Update 2

DanielAllsopp
DanielAllsopp's picture
Offline
Last seen: 12 years 7 months 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 year 1 month 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