;DLLSORT.inc V1.2 By David Newton (dave@nbsamiga.demon.co.uk)
;
;Dynamic Linked Lists (with variable sized items)
;
;QuickSort routines...see DLL.Guide for more details
;
;Feel free to use this include in any of your programs anyway you require.
;Also make any changes you like, and if you improve anything (mostly the
;sort routines...) let me know, so other people can benefit. I require no
;renumeration for the use of this source code, and I accept no
;responsibility for any harm to hardware/software caused directly or
;indirectly from the use of this source code and/or extracts of this source
;code compiled. But a credit for these routines in your software/manual would
;be nice :).  Dave.....
;
#VARTYPE_STRING=6

Goto END_OF_DLL_SORT

Function.l GET_ARRAY_ITEM{array.l,position.l}
  ;return the long at position from the longword array

  MOVE.l d0,a0:LSL.l #2,d1:ADD.l d1,a0:MOVE.l (a0),d0
  AsmExit
End Function

Statement SET_ARRAY_ITEM{array.l,position.l,longword.l}
  ;place longword in the array at position

  MOVE.l d0,a0:LSL.l #2,d1:ADD.l d1,a0:MOVE.l d2,(a0)
  AsmExit
End Statement

Statement PRIVATE_INSERT_SORT_ARRAY{array.l,lb.l,ub.l,entrypath.l,vartype.l}
  ;quickly insert sort an array of 12 or less items
  ;only to be called by PRIVATE_QUICK_SORT_ARRAY{}

  For i.l=lb+1 To ub
    t.l=GET_ARRAY_ITEM{array,i}
    ;shift elements down until insertion point found.
    j.l=i-1
    While (j>=lb)&(COMPARE_ITEMS{GET_ARRAY_ITEM{array,j},t,entrypath,vartype}=-1)
      SET_ARRAY_ITEM{array,j+1,GET_ARRAY_ITEM{array,j}}:j=j-1
    Wend
    ;now insert t back into array
    SET_ARRAY_ITEM{array,j+1,t}
  Next i
End Statement

Function.l PRIVATE_PARTION_ARRAY{array.l,lb.l,ub.l,entrypath.l,vartype.l}
  ;partion the array given
  ;only to be called by PRIVATE_QUICK_SORT_ARRAY{}
  ;returns the pivot point in array

  ;first get pivot (aim for middle) and swap with first item
  p.l=lb+((ub-lb)LSR 1):pivot.l=GET_ARRAY_ITEM{array,p}
  SET_ARRAY_ITEM{array,p,GET_ARRAY_ITEM{array,lb}}:SET_ARRAY_ITEM{array,lb,pivot}
  ;sort lb...ub based on pivot...fingers crossed for a medium pivot
  i.l=lb:j.l=ub
  While i<j
    While (COMPARE_ITEMS{GET_ARRAY_ITEM{array,j},pivot,entrypath,vartype}=-1)
      j=j-1
    Wend
    SET_ARRAY_ITEM{array,i,GET_ARRAY_ITEM{array,j}}
    While (i<j)&(COMPARE_ITEMS{GET_ARRAY_ITEM{array,i},pivot,entrypath,vartype}>-1)
      i=i+1
    Wend
    SET_ARRAY_ITEM{array,j,GET_ARRAY_ITEM{array,i}}
  Wend
  SET_ARRAY_ITEM{array,i,pivot}
  Function Return i
End Function

Statement PRIVATE_QUICK_SORT_ARRAY{array.l,lb.l,ub.l,entrypath.l,vartype.l}
  ;do the actual quick sort, on an array of item pointers
  ;always do an ascending sort, the returned array can be rebuilt either
  ;ascending, or descending :)
  ;this is recursively called, so make sure enough stack space is available

  While lb<ub
    If (ub-lb)<=12        ;quickly sort short lists
      PRIVATE_INSERT_SORT_ARRAY{array,lb,ub,entrypath,vartype}:lb=ub
    Else
      ;partion into segments
      m.l=PRIVATE_PARTION_ARRAY{array,lb,ub,entrypath,vartype}
      ;sort the smallest partition to minimize stack requirements
      If (m-lb)<=(ub-m)
        PRIVATE_QUICK_SORT_ARRAY{array,lb,m-1,entrypath,vartype}:lb=m+1
      Else
        PRIVATE_QUICK_SORT_ARRAY{array,m+1,ub,entrypath,vartype}:ub=m-1
      EndIf
    EndIf
  Wend
End Statement

Statement BUILD_ARRAY_OF_ITEMS{headoflist.l,array.l}
  ;build an array of items from the list
  ;array should already be allocated with number_of_items*4

  MOVE.l d0,a0:MOVE.l d1,a1
BUILD_ARRAY_OF_ITEMS_LOOP: MOVE.l (a0),a0:TST.l (a0):BEQ BUILD_ARRAY_OF_ITEMS_EXIT
  MOVE.l a0,(a1)+:BRA BUILD_ARRAY_OF_ITEMS_LOOP
BUILD_ARRAY_OF_ITEMS_EXIT:
  AsmExit
End Statement

Statement REBUILD_LIST_ARRAY_ASCENDING{headoflist.l,array.l,listsize.l}
  ;rebuild the linked list, from an array of items (listsize items)

  MOVE.l d1,a0:SUBQ.l #1,d2:MOVE.l d0,a1
  REBUILD_LIST_ASCENDING_LOOP: MOVE.l (a0)+,a2:MOVE.l a2,(a1):MOVE.l a1,4(a2)
  MOVE.l a2,a1:DBRA d2,REBUILD_LIST_ASCENDING_LOOP
  MOVE.l d0,a2:ADDQ.l #4,a2:MOVE.l a2,(a1):MOVE.l a1,4(a2)
  AsmExit
End Statement

Statement REBUILD_LIST_ARRAY_DESCENDING{headoflist.l,array.l,listsize.l}
  ;rebuild the linked list, from an array of items (listsize items)
  ;and reverse the list for a descending sort

  MOVE.l d1,a0:SUBQ.l #1,d2:MOVE.l d0,a1:ADDQ.l #4,a1
  REBUILD_LIST_DESCENDING_LOOP: MOVE.l (a0)+,a2:MOVE.l a2,4(a1):MOVE.l a1,(a2)
  MOVE.l a2,a1:DBRA d2,REBUILD_LIST_DESCENDING_LOOP
  MOVE.l d0,a2:MOVE.l a2,4(a1):MOVE.l a1,(a2)
  AsmExit
End Statement

Statement QUICK_SORT_LIST_ASCENDING{*listhead.dllhead,entrypath.l,vartype.l}
  ;do an ascending quick sort on a list
  ;need extra memory...atleast 4*listsize, and stack space>40000
  ;doesn't change the list current item pointer

  listsize.l=*listhead\dll_itemsinlist
  If listsize>0 Then array.l=AllocMem(listsize*4,0) Else array.l=0
  If array<>0
    BUILD_ARRAY_OF_ITEMS{*listhead,array}
    PRIVATE_QUICK_SORT_ARRAY{array,0,listsize-1,entrypath,vartype}
    REBUILD_LIST_ARRAY_ASCENDING{*listhead,array,listsize}
    FreeMem array,listsize*4
  EndIf
  RESET_LIST{*listhead}
End Statement

Statement QUICK_SORT_LIST_DESCENDING{*listhead.dllhead,entrypath.l,vartype.l}
  ;do a descending quick sort on a list
  ;need extra memory...atleast 4*listsize, and stack space>40000
  ;doesn't change the list current item pointer

  listsize.l=*listhead\dll_itemsinlist
  If listsize>0 Then array.l=AllocMem(listsize*4,0) Else array.l=0
  If array<>0
    BUILD_ARRAY_OF_ITEMS{*listhead,array}
    PRIVATE_QUICK_SORT_ARRAY{array,0,listsize-1,entrypath,vartype}
    REBUILD_LIST_ARRAY_DESCENDING{*listhead,array,listsize}
    FreeMem array,listsize*4
  EndIf
  RESET_LIST{*listhead}
End Statement

END_OF_DLL_SORT: