Shuffle Linked List

5 posts / 0 new

Last post

Tue, 2011-08-16 17:29

DanielAllsopp

Offline

Last seen: 11 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

Wed, 2011-08-17 13:31

salass00

Offline

Last seen: 1 month 2 weeks ago

Joined: 2011-02-03 11:27

int32 CountNodes (struct List

int32 CountNodes (struct List *list) {
	struct Node *node;
	int32 cnt = 0;
	for (node = IExec->GetHead(list); node; node = IExec->GetSucc(node)) {
		cnt++;
	}
	return cnt;
}
 
struct Node *GetNthNode (struct List *list, int32 index) {
	struct Node *node;
	int32 i = 0;
	for (node = IExec->GetHead(list); node; node = IExec->GetSucc(node)) {
		if (i == index) {
			return node;
		}
		i++;
	}
	return NULL;
}
 
void ShuffleList (struct List *source, struct List *dest) {
	struct Node *node;
	int32 cnt;
	cnt = CountNodes(source);
	while (cnt > 0) {
		node = GetNthNode(source, rand() % cnt);
		IExec->Remove(node);
		IExec->AddTail(dest, node);
		cnt--;
	}
}

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:

void InPlaceShuffleList (struct List *list) {
	struct List temp;
	temp = *list;
	IExec->NewList(list);
	ShuffleList(&temp, list);
}

Wed, 2011-08-17 22:44

(Reply to #2) #3

trixie

Offline

Last seen: 6 hours 27 min ago

Joined: 2011-02-03 13:58

Thanks Fredrik, very useful!

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

Thu, 2011-08-18 10:35

(Reply to #3) #4

DanielAllsopp

Offline

Last seen: 11 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!

Wed, 2011-10-19 11:42

(Reply to #4) #5

salass00

Offline

Last seen: 1 month 2 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:

void InPlaceShuffleList (struct List *list) {
	struct List temp;
	temp = *list;
	IExec->NewList(list);
	ShuffleList(&temp, list);
}

This won't work. Use this instead:

void InPlaceShuffleList (struct List *list) {
	struct List temp;
	IExec->NewList(&temp);
	ShuffleList(list, &temp);
	IExec->MoveList(list, &temp);
}

Search form

User login