Shuffle Linked List

5 posts / 0 new
Log in or register to post comments
Last post
Tue, 2011-08-16 17:29
#1
DanielAllsopp
DanielAllsopp's picture
Offline
Last seen: 13 years 3 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

Top
Wed, 2011-08-17 13:31
salass00
salass00's picture
Offline
Last seen: 6 months 3 weeks 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. }
Top
Wed, 2011-08-17 22:44
(Reply to #2)
trixie
trixie's picture
Offline
Last seen: 7 months 4 days ago
Joined: 2011-02-03 13:58
Re: Shuffle Linked List

Thanks Fredrik, very useful!

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

Top
Thu, 2011-08-18 10:35
(Reply to #3)
DanielAllsopp
DanielAllsopp's picture
Offline
Last seen: 13 years 3 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!

Top
Wed, 2011-10-19 11:42
(Reply to #4)
salass00
salass00's picture
Offline
Last seen: 6 months 3 weeks 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. }
Top
Log in or register to post comments