How to sort a chooser list?

12 posts / 0 new
Last post
jabirulo
jabirulo's picture
Offline
Last seen: 7 hours 49 min ago
Joined: 2013-05-30 00:53
How to sort a chooser list?

Hi, is there an easy/fast method to sort a chooser list (alas listbrowser has) alphabetically?

Or do I have to use AVL_AddNode() or some bubble_sort merge_sort of my "own" to chooser nodes/names.

On AMINET there are some c sources of sorting methods (http://aminet.net/dev/src/sort.lha)

THX

salass00
salass00's picture
Offline
Last seen: 1 year 1 month ago
Joined: 2011-02-03 11:27
Re: How to sort a chooser list?

You will want a sort algorithm that works well with linked lists.

For good speed with large lists I recommend a merge sort algorithm. Bubble sort OTOH is really easy to implement but scales really badly with big lists (if your lists are short enough that it doesn't matter though then go for it).

I use a merge sort algorithm for sorting cache nodes in my libdiskio/diskio.library block cache implementation:
https://github.com/salass00/ntfs-3g/blob/master/libdiskio/mergesort.c

jabirulo
jabirulo's picture
Offline
Last seen: 7 hours 49 min ago
Joined: 2013-05-30 00:53
Re: How to sort a chooser list?

Will try to implement/create the bubble_sort (almost have it) and see how it performs, the list wont be too big (theme pointers drawer names), but who knows.
Thx will take a look at your merge_srot code (and if you don't mind i can use on my program).

AOS4.1/SAM460ex/PPC460EX-1155MHZ/2048MB/RadeonHD6570/SSD120GB/DVDRW :-P

jabirulo
jabirulo's picture
Offline
Last seen: 7 hours 49 min ago
Joined: 2013-05-30 00:53
Re: How to sort a chooser list?

Me again, managed to code the bubble_sort method/function (isn't perfect and sure it has bugs), seems to work fine. Suggestion are welcome :-)

  1. void sort_chooserlist(int32 n) {
  2. struct Node *n1, *n2, *n0 = IExec->GetHead(&chooser_list);
  3. STRPTR name1, name2;
  4. int32 i, j;
  5.  
  6. for(i=n; i>0; i--) { // traverse all the chooser_list
  7. n2 = IExec->GetHead(&chooser_list);
  8. for(j=1; j<i; j++) {
  9. n2=IExec->GetSucc(n2);
  10. IChooser->GetChooserNodeAttrs(n2, CNA_Text,&name2, TAG_DONE);
  11. n1 = IExec->GetPred(n2);
  12. IChooser->GetChooserNodeAttrs(n1, CNA_Text,&name1, TAG_DONE);
  13. if(IUtility->Stricmp(name1, name2) > 0) // name-compare of node1 and node2
  14. {
  15. char tmp[MAX_THEME];
  16. IUtility->Strlcpy(tmp, name1, MAX_THEME);
  17. IChooser->SetChooserNodeAttrs(n1, CNA_CopyText,TRUE, CNA_Text,name2, TAG_DONE);
  18. IChooser->SetChooserNodeAttrs(n2, CNA_CopyText,TRUE, CNA_Text,tmp, TAG_DONE);
  19. }
  20. }
  21. n0 = IExec->GetSucc(n0);
  22. }
  23. }

AOS4.1/SAM460ex/PPC460EX-1155MHZ/2048MB/RadeonHD6570/SSD120GB/DVDRW :-P

salass00
salass00's picture
Offline
Last seen: 1 year 1 month ago
Joined: 2011-02-03 11:27
Re: How to sort a chooser list?

Instead of swapping node names which necessitates allocating a temporary before, memory freeing/allocation and lots of copying (especially since you use CNA_CopyText) you should be reordering the nodes themselves. This will not only have a lot less overhead but will also make your function more generic and therefore more easily reusable for other purposes.

Also if you want to make your sort function really reusable for sorting all kinds of exec doubly linked lists I suggest adding a callback parameter of some kind that is used to compare nodes rather than hardcoding the comparison in the sort function.

jabirulo
jabirulo's picture
Offline
Last seen: 7 hours 49 min ago
Joined: 2013-05-30 00:53
Re: How to sort a chooser list?

THX, will re-adapt bubble_sort code then.

AOS4.1/SAM460ex/PPC460EX-1155MHZ/2048MB/RadeonHD6570/SSD120GB/DVDRW :-P

trixie
trixie's picture
Offline
Last seen: 5 months 9 hours ago
Joined: 2011-02-03 13:58
Re: How to sort a chooser list?

Not that I can help Jabirulo with his problem but IMHO sorting should be an inherent feature of all list-based classes. What drives me really really mad about BOOPSI is that it is supposed to be the highest-level Intuition API, yet if forces you to do the lowest-level kind of things. This must get some attention!

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

salass00
salass00's picture
Offline
Last seen: 1 year 1 month ago
Joined: 2011-02-03 11:27
Re: How to sort a chooser list?

Here is a version of bubble sort that I quickly put together:

  1. int CountNodes(struct List *list) {
  2. struct Node *node;
  3. int count = 0;
  4.  
  5. for (node = list->lh_Head; node->ln_Succ != NULL; node = node->ln_Succ)
  6. count++;
  7.  
  8. return count;
  9. }
  10.  
  11. void SortList(struct List *list, struct Hook *cmphook) {
  12. int i, j, count;
  13. struct Node *curr, *next;
  14.  
  15. count = CountNodes(list);
  16.  
  17. if (count <= 1)
  18. return;
  19.  
  20. for (i = 0; i < count; i++) {
  21. curr = IExec->GetHead(list);
  22. for (j = 0; j < count - 1 - i; j++) {
  23. next = IExec->GetSucc(curr);
  24. if ((int)IUtility->CallHookPkt(cmphook, curr, next) > 0) {
  25. IExec->Remove(curr);
  26. IExec->Insert(list, curr, next);
  27. } else {
  28. curr = next;
  29. }
  30. }
  31. }
  32. }

Unless I made some mistake it should be working.

The hook function takes the standard hook pointer and the pointers of the two nodes to compare and should return a negative, zero or positive value depending on if the first node is less than, equal to or greater than the second one.

salass00
salass00's picture
Offline
Last seen: 1 year 1 month ago
Joined: 2011-02-03 11:27
Re: How to sort a chooser list?

@trixie

FWIW there has been for some time a feature request in bugzilla for adding a sort function for exec style doubly linked lists to "utility.library".

If no one else gets round to implementing it first I might just take care of it myself.

thomas
thomas's picture
Offline
Last seen: 13 hours 8 min ago
Joined: 2011-05-16 14:23
Re: How to sort a chooser list?

I usually do something like this, then I don't need to care about implementing my own sort algorithm:

  1. void sort_list (struct List *list, int (*compar)(const void*, const void*))
  2. {
  3. struct Node **array;
  4. struct Node *node,*next;
  5. long n,i;
  6.  
  7. n = 0;
  8. for (node = list->lh_Head; (next = node->ln_Succ); node = next)
  9. n ++;
  10.  
  11. if ((array = malloc (n * sizeof(*array))))
  12. {
  13. for (i = 0; i < n; i++)
  14. array[i] = RemHead (list);
  15.  
  16. qsort (array, n, sizeof(*array), compar);
  17.  
  18. for (i = 0; i < n; i++)
  19. AddTail (list, array[i]);
  20.  
  21. free (array);
  22. }
  23. }
  24.  
  25.  
  26. int compare_nodes (const struct Node **n1, const struct Node **n2)
  27. {
  28. return (Stricmp ((*n1)->ln_Name, (*n2)->ln_Name);
  29. }
OldFart
OldFart's picture
Offline
Last seen: 6 hours 20 min ago
Joined: 2010-11-30 14:09
Re: How to sort a chooser list?

@jabirulo

Here's my two cents to the discussion:

The outer 'while()' loop moves forward through the list, whereas the inner 'while()' loop moves backwards through the list for as long as necessary.
In worst case (full inverse) it will go backwards until it hits the limit of the list '(Prev == NULL)', in which case you better simply inverse the list:

  1. void Reverse_List(struct List *L)
  2. {
  3. struct Node *First = IExec->GetHead(L),
  4. *Next;
  5.  
  6. while ((Next = IExec->GetSucc(First)) != NULL)
  7. {
  8. IExec->Remove(Next);
  9. IExec->AddHead(L, Next);
  10. }
  11. }
  1. void Sort_List(struct List *L)
  2. {
  3. struct Node *Curr = IExec->GetHead(L);
  4.  
  5. if (Curr != NULL)
  6. {
  7. struct Node *Next = IExec->GetSucc(Curr),
  8. *Prev;
  9.  
  10. while (Next != NULL)
  11. {
  12. if ((int)IUtility->CallHook(cmphook, Curr, Next) > 0)
  13. {
  14. IExec->Remove(Curr);
  15. IExec->Insert(L, Curr, Next);
  16. Prev = IExec->GetPred(Next);
  17.  
  18. while (
  19. (Prev != NULL) &&
  20. ((int)IUtility->CallHook(cmphook, Prev, Next) > 0)
  21. )
  22. {
  23. IExec->Remove(Prev);
  24. IExec->Insert(L, Prev, Next);
  25. Prev = IExec->GetPred(Next);
  26. }
  27. }
  28.  
  29. Next = IExec->GetSucc(Curr);
  30. }
  31. }
  32. }

Have fun!
Btw, don't forget to detach the list from the gadget before you meddle with its nodes and reattach it when you're done.

OldFart

jabirulo
jabirulo's picture
Offline
Last seen: 7 hours 49 min ago
Joined: 2013-05-30 00:53
Re: How to sort a chooser list?

@all
thx will try those sort functions provided.

AOS4.1/SAM460ex/PPC460EX-1155MHZ/2048MB/RadeonHD6570/SSD120GB/DVDRW :-P

Log in or register to post comments