SinglyLinkedList

Share your advanced PureBasic knowledge/code with the community.
Post Reply
User avatar
pcfreak
User
User
Posts: 75
Joined: Sat May 22, 2004 1:38 am

SinglyLinkedList

Post by pcfreak »

After I searched the Forum if I had already posted the Code I found that
there were quite a lot requests to use LinkedLists in Structures.

Well, this Solution might be not the most beautiful one but you can use it
to make use of dynamic lists within Structures on a more or less easy way.

the Code free to use, but I don't mind to be mentioned in the Credits :wink:
(Examples added to the End of the Code)

SinglyLinkedList.pbi

Code: Select all

Enumeration
 ;adds an element to the end of the linked list
 #SLL_ADD_ELEMENT
 ;returns the element by the passed index
 #SLL_GET_ELEMENT
 ;deletes the element of the specified index
 #SLL_DEL_ELEMENT
 ;moves the pointer to the next element
 #SLL_NEXT_ELEMENT
 ;returns the number of elements in the linked list
 #SLL_COUNT_ELEMENTS
 ;deletes all elements of the linked list
 #SLL_CLEAR_LIST
EndEnumeration

Enumeration
 #SLL_SORT_STRING
 #SLL_SORT_STRING_CASESENSITIVE
 #SLL_SORT_BYTE
 #SLL_SORT_WORD
 #SLL_SORT_LONG
 #SLL_SORT_QUAD
 #SLL_SORT_CHARACTER
 #SLL_SORT_FLOAT
 #SLL_SORT_DOUBLE
 #SLL_SORT_DATA_LITTLE_ENDIAN
 #SLL_SORT_DATA_BIG_ENDIAN
EndEnumeration


;internal macros.. not for extern usage
;======================================
Macro SortSinglyLinkedList_RadixIncStart()
 ;add to index
 While *handle
  *element = *handle\next
  *handle\next = 0
EndMacro

Macro SortSinglyLinkedList_RadixIncEnd()
  *newEntry = *radixArray\n[arrayIndex]
  If *newEntry = 0
   *radixArray\n[arrayIndex] = *handle
  Else
   While *newEntry\next
    *newEntry = *newEntry\next
   Wend
   *newEntry\next = *handle
  EndIf
  *handle = *element
 Wend
 ;collect sorted elements
 *element = 0
 For arrayIndex=0 To 255
  If *radixArray\n[arrayIndex]
   If *element = 0
    *handle = *radixArray\n[arrayIndex]
    *element = *radixArray\n[arrayIndex]
   Else
    *element\next = *radixArray\n[arrayIndex]
   EndIf
   *radixArray\n[arrayIndex] = 0
   While *element\next
    *element = *element\next
   Wend
  EndIf
 Next
EndMacro
;======================================



Macro CreateSinglyLinkedListClass(dataVariable, dataType)
CompilerIf Defined(SINGLY_LINKED_LIST_ENTRY_#dataType, #PB_Structure)=#False
 Structure SINGLY_LINKED_LIST_ENTRY_#dataType
  *next.SINGLY_LINKED_LIST_ENTRY_#dataType
  dataVariable#.dataType#
 EndStructure
 Structure SINGLY_LINKED_LIST_SORTARRAY_#dataType
  *n.SINGLY_LINKED_LIST_ENTRY_#dataType[256]
 EndStructure
 
 Procedure.l SinglyLinkedList_#dataType#(option.l, *handle.SINGLY_LINKED_LIST_ENTRY_#dataType = 0, flag.l = 0)
  Select option
   Case #SLL_ADD_ELEMENT
    If *handle=0
     *handle = AllocateMemory(SizeOf(SINGLY_LINKED_LIST_ENTRY_#dataType))
     ProcedureReturn *handle
    Else
     *lastEntry.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle
     While *lastEntry\next
      *lastEntry = *lastEntry\next
     Wend
     *newEntry.SINGLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(SINGLY_LINKED_LIST_ENTRY_#dataType))
     *lastEntry\next = *newEntry
     ProcedureReturn *newEntry
    EndIf
   Case #SLL_GET_ELEMENT
    If *handle
     If flag=0
      ProcedureReturn *handle
     Else
      a.l=0
      *element.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle
      While a<flag And *element\next
       *element = *element\next
       a+1
      Wend
      If a=flag
       ProcedureReturn *element
      Else
       ProcedureReturn 0
      EndIf
     EndIf
    EndIf
    ProcedureReturn 0
   Case #SLL_DEL_ELEMENT
    If *handle
     If flag=0
      pointer.l = *handle\next
      FreeMemory(*handle)
      ProcedureReturn pointer
     ElseIf flag>0
      a.l=0
      *element.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle
      While a<flag-1 And *element\next
       *element = *element\next
       a+1
      Wend
      If a=flag-1 And *element\next
       pointer.l = *element\next\next
       FreeMemory(*element\next)
       *element\next = pointer
      EndIf
      ProcedureReturn *handle
     EndIf
    EndIf
    ProcedureReturn 0
   Case #SLL_NEXT_ELEMENT
    If *handle
     *handle = *handle\next
    EndIf
    ProcedureReturn *handle
   Case #SLL_COUNT_ELEMENTS
    count.l=0
    If *handle
     While *handle
      *handle = *handle\next
      count + 1
     Wend
    EndIf
    ProcedureReturn count
   Case #SLL_CLEAR_LIST
    If *handle
     *element.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle\next
     FreeMemory(*handle)
     While *element
      *handle = *element
      *element = *element\next
      FreeMemory(*handle)
     Wend
    EndIf
    ProcedureReturn 0
  EndSelect
 EndProcedure
 
 Procedure.l SortSinglyLinkedList_#dataType#(type.l, *handle.SINGLY_LINKED_LIST_ENTRY_#dataType, option.l, offset.l = 0, size.l = -1)
  Protected Result.l, *radixArray.SINGLY_LINKED_LIST_SORTARRAY_#dataType, arrayIndex.l
  Protected *tmpString.STRING, tmpLen.l, i.l, *element.SINGLY_LINKED_LIST_ENTRY_#dataType, *newEntry.SINGLY_LINKED_LIST_ENTRY_#dataType
  Result = 0
  If *handle
   offset + 4
   Select SinglyLinkedList_#dataType#(#SLL_COUNT_ELEMENTS, *handle)
    Case 0, 1
     Result = *handle
    Case 2
     If option = 0 ;increasing
      Select type
       Case #SLL_SORT_STRING
        If LCase(PeekS(PeekL(*handle\next+offset),size)) < LCase(PeekS(PeekL(*handle+offset),size))
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_STRING_CASESENSITIVE
        If PeekS(PeekL(*handle\next+offset),size) < PeekS(PeekL(*handle+offset),size)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_BYTE
        If PeekB(*handle\next+offset) < PeekB(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_WORD
        If PeekW(*handle\next+offset) < PeekW(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_LONG
        If PeekL(*handle\next+offset) < PeekL(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_QUAD
        If PeekQ(*handle\next+offset) < PeekQ(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_CHARACTER
        If PeekC(*handle\next+offset) < PeekC(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_FLOAT
        If PeekF(*handle\next+offset) < PeekF(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_DOUBLE
        If PeekD(*handle\next+offset) < PeekD(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_DATA_LITTLE_ENDIAN
        If size>0
         For i=size-1 To 0 Step -1
          If PeekB(*handle\next+offset+i)&$FF < PeekB(*handle+offset+i)&$FF
           *handle\next\next = *handle
           *handle = *handle\next
           *handle\next\next = 0
           Break
          EndIf
         Next
         Result = *handle
        EndIf
       Case #SLL_SORT_DATA_BIG_ENDIAN
        If size>0
         For i=0 To size-1
          If PeekB(*handle\next+offset+i)&$FF < PeekB(*handle+offset+i)&$FF
           *handle\next\next = *handle
           *handle = *handle\next
           *handle\next\next = 0
           Break
          EndIf
         Next
         Result = *handle
        EndIf
      EndSelect
     Else ;decreasing
      Select type
       Case #SLL_SORT_STRING
        If LCase(PeekS(PeekL(*handle\next+offset),size)) > LCase(PeekS(PeekL(*handle+offset),size))
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_STRING_CASESENSITIVE
        If PeekS(PeekL(*handle\next+offset),size) > PeekS(PeekL(*handle+offset),size)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_BYTE
        If PeekB(*handle\next+offset) > PeekB(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_WORD
        If PeekW(*handle\next+offset) > PeekW(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_LONG
        If PeekL(*handle\next+offset) > PeekL(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_QUAD
        If PeekQ(*handle\next+offset) > PeekQ(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_CHARACTER
        If PeekC(*handle\next+offset) > PeekC(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_FLOAT
        If PeekF(*handle\next+offset) > PeekF(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_DOUBLE
        If PeekD(*handle\next+offset) > PeekD(*handle+offset)
         *handle\next\next = *handle
         *handle = *handle\next
         *handle\next\next = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_DATA_LITTLE_ENDIAN
        If size>0
         For i=size-1 To 0 Step -1
          If PeekB(*handle\next+offset+i)&$FF > PeekB(*handle+offset+i)&$FF
           *handle\next\next = *handle
           *handle = *handle\next
           *handle\next\next = 0
           Break
          EndIf
         Next
         Result = *handle
        EndIf
       Case #SLL_SORT_DATA_BIG_ENDIAN
        If size>0
         For i=0 To size-1
          If PeekB(*handle\next+offset+i)&$FF > PeekB(*handle+offset+i)&$FF
           *handle\next\next = *handle
           *handle = *handle\next
           *handle\next\next = 0
           Break
          EndIf
         Next
         Result = *handle
        EndIf
      EndSelect
     EndIf
    Default
     *radixArray = AllocateMemory(1024)
     If *radixArray
      Select type
       Case #SLL_SORT_STRING
        If size = -1
         *element = *handle
         While *element
          *tmpString = *element+offset
          If *tmpString
           tmpLen = Len(*tmpString\s)
           If tmpLen > size
            size = tmpLen
           EndIf
          EndIf
          *element = *element\next
         Wend
        EndIf
        If size = 0
         Result = *handle
        ElseIf size > 0
         CompilerIf #PB_Compiler_Unicode
          For i=size-1 To 0 Step -1
           SortSinglyLinkedList_RadixIncStart()
            *tmpString = *handle+offset
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i
             arrayIndex = 0
            Else
             arrayIndex = Asc(LCase(Chr(PeekC(@*tmpString\s+(i*2)))))&$FF
            EndIf
           SortSinglyLinkedList_RadixIncEnd()
           SortSinglyLinkedList_RadixIncStart()
            *tmpString = *handle+offset
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i
             arrayIndex = 0
            Else
             arrayIndex = (Asc(LCase(Chr(PeekC(@*tmpString\s+(i*2)))))>>8)&$FF
            EndIf
           SortSinglyLinkedList_RadixIncEnd()
          Next
          Result = *handle
         CompilerElse
          For i=size-1 To 0 Step -1
           SortSinglyLinkedList_RadixIncStart()
            *tmpString = *handle+offset
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i
             arrayIndex = 0
            Else
             arrayIndex = Asc(LCase(Chr(PeekC(@*tmpString\s+i))))&$FF
            EndIf
           SortSinglyLinkedList_RadixIncEnd()
          Next
          Result = *handle
         CompilerEndIf
        EndIf
       Case #SLL_SORT_STRING_CASESENSITIVE
        If size = -1
         *element = *handle
         While *element
          *tmpString = *element+offset
          If *tmpString
           tmpLen = Len(*tmpString\s)
           If tmpLen > size
            size = tmpLen
           EndIf
          EndIf
          *element = *element\next
         Wend
        EndIf
        If size = 0
         Result = *handle
        ElseIf size > 0
         CompilerIf #PB_Compiler_Unicode
          For i=size-1 To 0 Step -1
           SortSinglyLinkedList_RadixIncStart()
            *tmpString = *handle+offset
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i
             arrayIndex = 0
            Else
             arrayIndex = PeekB(@*tmpString\s+(i*2))&$FF
            EndIf
           SortSinglyLinkedList_RadixIncEnd()
           SortSinglyLinkedList_RadixIncStart()
            *tmpString = *handle+offset
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i
             arrayIndex = 0
            Else
             arrayIndex = PeekB(@*tmpString\s+(i*2)+1)&$FF
            EndIf
           SortSinglyLinkedList_RadixIncEnd()
          Next
          Result = *handle
         CompilerElse
          For i=size-1 To 0 Step -1
           SortSinglyLinkedList_RadixIncStart()
            *tmpString = *handle+offset
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i
             arrayIndex = 0
            Else
             arrayIndex = PeekB(@*tmpString\s+i)&$FF
            EndIf
           SortSinglyLinkedList_RadixIncEnd()
          Next
          Result = *handle
         CompilerEndIf
        EndIf
       Case #SLL_SORT_BYTE
        SortSinglyLinkedList_RadixIncStart()
         arrayIndex = PeekB(*handle+offset)+$80
        SortSinglyLinkedList_RadixIncEnd()
        Result = *handle
       Case #SLL_SORT_WORD
        For i=0 To 1
         SortSinglyLinkedList_RadixIncStart()
          arrayIndex = ((PeekW(*handle+offset)+$8000) >> (i*8)) & $FF
         SortSinglyLinkedList_RadixIncEnd()
        Next
        Result = *handle
       Case #SLL_SORT_LONG
        For i=0 To 3
         SortSinglyLinkedList_RadixIncStart()
          arrayIndex = ((PeekL(*handle+offset)+$80000000) >> (i*8)) & $FF
         SortSinglyLinkedList_RadixIncEnd()
        Next
        Result = *handle
       Case #SLL_SORT_QUAD
        For i=0 To 7
         SortSinglyLinkedList_RadixIncStart()
         ;- Quad Sort can be used once this bug is removed
         ;arrayIndex = ((PeekQ(*handle+offset)+$8000000000000000) >> (i*8)) & $FF
         ;workaround for quad until bug is fixed>>
         Protected quad_.q
         quad_ = PeekQ(*handle+offset)
         !MOV edx, dword [p.v_quad_+4]
         !MOV eax, dword [p.v_quad_]
         !ADD eax, $80000000
         !ADC edx, 0
         !MOV ecx, dword [p.v_i]
         !CMP ecx, 0
         !JE @f
          !SHL ecx, 2
          !SHRD eax, edx, cl
          !SHRD eax, edx, cl
         !@@:
         !AND eax, $FF
         !MOV dword [p.v_arrayIndex], eax
         ;<<
         SortSinglyLinkedList_RadixIncEnd()
        Next
        Result = *handle
       Case #SLL_SORT_CHARACTER
        For i=0 To #PB_Compiler_Unicode
         SortSinglyLinkedList_RadixIncStart()
          arrayIndex = PeekB(*handle+offset+i)&$FF
         SortSinglyLinkedList_RadixIncEnd()
        Next
        Result = *handle
       Case #SLL_SORT_FLOAT
        ;SEEEEEEE EFFFFFFF FFFFFFF FFFFFFF
        For i=0 To 1
         SortSinglyLinkedList_RadixIncStart()
          arrayIndex = PeekB(*handle+offset+i)&$FF
         SortSinglyLinkedList_RadixIncEnd()
        Next
        SortSinglyLinkedList_RadixIncStart()
         arrayIndex = PeekB(*handle+offset+2)&$7F
        SortSinglyLinkedList_RadixIncEnd()
        SortSinglyLinkedList_RadixIncStart()
         arrayIndex = (PeekW(*handle+offset+2) >> 7) & $FF
        SortSinglyLinkedList_RadixIncEnd()
        ;add to index
        While *handle
         *element = *handle\next
         *handle\next = 0
         arrayIndex = ((PeekB(*handle+offset+3)&$FF) >> 7)
         *newEntry = *radixArray\n[arrayIndex]
         If *newEntry = 0
          *radixArray\n[arrayIndex] = *handle
         Else
          While *newEntry\next
           *newEntry = *newEntry\next
          Wend
          *newEntry\next = *handle
         EndIf
         *handle = *element
        Wend
        ;collect sorted elements
        *element = 0
        If *radixArray\n[0]
         If *element = 0
          *handle = *radixArray\n[0]
          *element = *radixArray\n[0]
         Else
          *element\next = *radixArray\n[0]
         EndIf
         *radixArray\n[0] = 0
         While *element\next
          *element = *element\next
         Wend
        EndIf
        If *radixArray\n[1]
         While *radixArray\n[1]
          *element = *radixArray\n[1]\next
          *radixArray\n[1]\next = *handle
          *handle = *radixArray\n[1]
          *radixArray\n[1] = *element
         Wend
         *radixArray\n[1] = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_DOUBLE
        ;SEEEEEEE EEEEFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
        For i=0 To 5
         SortSinglyLinkedList_RadixIncStart()
          arrayIndex = PeekB(*handle+offset+i)&$FF
         SortSinglyLinkedList_RadixIncEnd()
        Next
        SortSinglyLinkedList_RadixIncStart()
         arrayIndex = PeekB(*handle+offset+6)&$0F
        SortSinglyLinkedList_RadixIncEnd()
        SortSinglyLinkedList_RadixIncStart()
         arrayIndex = (PeekW(*handle+offset+6) >> 4) & $FF
        SortSinglyLinkedList_RadixIncEnd()
        SortSinglyLinkedList_RadixIncStart()
         arrayIndex = (PeekW(*handle+offset+6) >> 12) & $07
        SortSinglyLinkedList_RadixIncEnd()
        ;add to index
        While *handle
         *element = *handle\next
         *handle\next = 0
         arrayIndex = ((PeekB(*handle+offset+7)&$FF) >> 7)
         *newEntry = *radixArray\n[arrayIndex]
         If *newEntry = 0
          *radixArray\n[arrayIndex] = *handle
         Else
          While *newEntry\next
           *newEntry = *newEntry\next
          Wend
          *newEntry\next = *handle
         EndIf
         *handle = *element
        Wend
        ;collect sorted elements
        *element = 0
        If *radixArray\n[0]
         If *element = 0
          *handle = *radixArray\n[0]
          *element = *radixArray\n[0]
         Else
          *element\next = *radixArray\n[0]
         EndIf
         *radixArray\n[0] = 0
         While *element\next
          *element = *element\next
         Wend
        EndIf
        If *radixArray\n[1]
         While *radixArray\n[1]
          *element = *radixArray\n[1]\next
          *radixArray\n[1]\next = *handle
          *handle = *radixArray\n[1]
          *radixArray\n[1] = *element
         Wend
         *radixArray\n[1] = 0
        EndIf
        Result = *handle
       Case #SLL_SORT_DATA_LITTLE_ENDIAN
        If size > 0
         For i=0 To size-1
          SortSinglyLinkedList_RadixIncStart()
           arrayIndex = PeekB(*handle+offset+i)&$FF
          SortSinglyLinkedList_RadixIncEnd()
         Next
         Result = *handle
        EndIf
       Case #SLL_SORT_DATA_BIG_ENDIAN
        If size > 0
         For i=size-1 To 0 Step -1
          SortSinglyLinkedList_RadixIncStart()
           arrayIndex = PeekB(*handle+offset+i)&$FF
          SortSinglyLinkedList_RadixIncEnd()
         Next
         Result = *handle
        EndIf
      EndSelect
      If option = 1 And Result ;decreasing
       *radixArray\n[0] = Result
       *handle = 0
       While *radixArray\n[0]
        *element =*radixArray\n[0]\next
        *radixArray\n[0]\next = *handle
        *handle = *radixArray\n[0]
        *radixArray\n[0] = *element
       Wend
       Result = *handle
      EndIf
      FreeMemory(*radixArray)
     EndIf
   EndSelect
  EndIf
  ProcedureReturn Result
 EndProcedure
CompilerEndIf
EndMacro

Macro DefineSinglyLinkedList(variable, dataType)
 variable#.SINGLY_LINKED_LIST_ENTRY_#dataType
EndMacro

Macro SinglyLinkedList(dataType, option, handle=0, flag=0)
 SinglyLinkedList_#dataType#(option, handle, flag)
EndMacro

Macro SortSinglyLinkedList(dataType, type, handle, option, offset = 0, size = -1)
 SortSinglyLinkedList_#dataType#(type, handle, option, offset, size)
EndMacro

Macro SLLForEach(handle)
 While handle
EndMacro

Macro SLLNext(handle)
  handle = handle#\next
 Wend
EndMacro


; ################
;#    Example 1   #
; ################

Debug "=============================="
Debug "Example 1"

CreateSinglyLinkedListClass(value, l)
DefineSinglyLinkedList(*list, l)
DefineSinglyLinkedList(*pointer, l)

*list = SinglyLinkedList(l, #SLL_ADD_ELEMENT, *list)
*list\value = -1
For a=1 To 9
 *pointer = SinglyLinkedList(l, #SLL_ADD_ELEMENT, *list)
 *pointer\value = Random(99)
Next

Debug "Added "+Str(SinglyLinkedList(l, #SLL_COUNT_ELEMENTS, *list))+" entries to the linked list."
Debug "The linked list contains the following entries:"

*pointer = *list
SLLForEach(*pointer)
 Debug *pointer\value
SLLNext(*pointer)

*list = SinglyLinkedList(l, #SLL_DEL_ELEMENT, *list,0)
Debug "Deleted the first entry from the linked list."
Debug "The linked list contains the following entries:"

*pointer = *list
SLLForEach(*pointer)
 Debug *pointer\value
SLLNext(*pointer)

*pointer = SinglyLinkedList(l, #SLL_GET_ELEMENT, *list,4)
Debug "The 5th entry equals to "+Str(*pointer\value)+"."

*list = SinglyLinkedList(l, #SLL_DEL_ELEMENT, *list,4)
Debug "Deleted the 5th entry from the linked list."

*pointer = SinglyLinkedList(l, #SLL_GET_ELEMENT, *list,4)
Debug "The 5th entry equals to "+Str(*pointer\value)+"."

*list = SinglyLinkedList(l, #SLL_CLEAR_LIST, *list)
Debug "Deleted all entries from the linked list."
Debug "The linked list contains "+Str(SinglyLinkedList(l, #SLL_COUNT_ELEMENTS, *list))+" entries."
Debug "------------------------------"

; ################
;#    Example 2   #
; ################

Debug "=============================="
Debug "Example 2"

CreateSinglyLinkedListClass(value, s)
DefineSinglyLinkedList(*list2, s)
DefineSinglyLinkedList(*pointer2, s)

*list2 = SinglyLinkedList(s, #SLL_ADD_ELEMENT, *list2)
*list2\value = "First Item"
For a=1 To 9
 *pointer2 = SinglyLinkedList(s, #SLL_ADD_ELEMENT, *list2)
 If Random(2)
  *pointer2\value = "Item " + Str(Random(9999))
 Else
  *pointer2\value = "item " + Str(Random(9999))
 EndIf
Next

Debug "Added "+Str(SinglyLinkedList(s, #SLL_COUNT_ELEMENTS, *list2))+" entries to the linked list."
Debug "The linked list contains the following entries:"

*pointer2 = *list2
SLLForEach(*pointer2)
 Debug *pointer2\value
SLLNext(*pointer2)

Debug "The increasing sorted linked list contains the following entries:"
*list2 = SortSinglyLinkedList(s, #SLL_SORT_STRING, *list2, 0)

*pointer2 = *list2
SLLForEach(*pointer2)
 Debug *pointer2\value
SLLNext(*pointer2)

Debug "The decreasing sorted linked list contains the following entries:"
*list2 = SortSinglyLinkedList(s, #SLL_SORT_STRING, *list2, 1)

*pointer2 = *list2
SLLForEach(*pointer2)
 Debug *pointer2\value
SLLNext(*pointer2)
Debug "------------------------------"
PS: Feedback is welcome :P
Top
User avatar
Deeem2031
Enthusiast
Enthusiast
Posts: 216
Joined: Sat Sep 20, 2003 3:57 pm
Location: Germany
Contact:
Contact Deeem2031

Post by Deeem2031 »

Hm, nice work. But I don't like this "dataVariable#.dataType#" when using a structure instead of a native datatype,so I modified it a bit:

Code: Select all

Enumeration 
 ;adds an element to the end of the linked list 
 #SLL_ADD_ELEMENT 
 ;returns the element by the passed index 
 #SLL_GET_ELEMENT 
 ;deletes the element of the specified index 
 #SLL_DEL_ELEMENT 
 ;moves the pointer to the next element 
 #SLL_NEXT_ELEMENT 
 ;returns the number of elements in the linked list 
 #SLL_COUNT_ELEMENTS 
 ;deletes all elements of the linked list 
 #SLL_CLEAR_LIST 
EndEnumeration 

Enumeration 
 #SLL_SORT_STRING 
 #SLL_SORT_STRING_CASESENSITIVE 
 #SLL_SORT_BYTE 
 #SLL_SORT_WORD 
 #SLL_SORT_LONG 
 #SLL_SORT_QUAD 
 #SLL_SORT_CHARACTER 
 #SLL_SORT_FLOAT 
 #SLL_SORT_DOUBLE 
 #SLL_SORT_DATA_LITTLE_ENDIAN 
 #SLL_SORT_DATA_BIG_ENDIAN 
EndEnumeration 


;internal macros.. not for extern usage 
;====================================== 
Macro SortSinglyLinkedList_RadixIncStart() 
 ;add to index 
 While *handle 
  *element = *handle\next 
  *handle\next = 0 
EndMacro 

Macro SortSinglyLinkedList_RadixIncEnd() 
  *newEntry = *radixArray\n[arrayIndex] 
  If *newEntry = 0 
   *radixArray\n[arrayIndex] = *handle 
  Else 
   While *newEntry\next 
    *newEntry = *newEntry\next 
   Wend 
   *newEntry\next = *handle 
  EndIf 
  *handle = *element 
 Wend 
 ;collect sorted elements 
 *element = 0 
 For arrayIndex=0 To 255 
  If *radixArray\n[arrayIndex] 
   If *element = 0 
    *handle = *radixArray\n[arrayIndex] 
    *element = *radixArray\n[arrayIndex] 
   Else 
    *element\next = *radixArray\n[arrayIndex] 
   EndIf 
   *radixArray\n[arrayIndex] = 0 
   While *element\next 
    *element = *element\next 
   Wend 
  EndIf 
 Next 
EndMacro 
;====================================== 



Macro CreateSinglyLinkedListClass(dataVariable, dataType) 
CompilerIf Defined(SINGLY_LINKED_LIST_ENTRY_#dataType, #PB_Structure)=#False 
 Structure SINGLY_LINKED_LIST_ENTRY_#dataType
  *next.SINGLY_LINKED_LIST_ENTRY_#dataType 
  dataVariable#.dataType# 
 EndStructure 
 CreateSinglyLinkedListClass_Internal(dataType)
CompilerEndIf 
EndMacro

Macro CreateSinglyLinkedListClass_Extend(dataType)
CompilerIf Defined(SINGLY_LINKED_LIST_ENTRY_#dataType, #PB_Structure)=#False 
 Structure SINGLY_LINKED_LIST_ENTRY_#dataType Extends dataType
  *next.SINGLY_LINKED_LIST_ENTRY_#dataType 
 EndStructure 
 CreateSinglyLinkedListClass_Internal(dataType)
CompilerEndIf 
EndMacro

Macro CreateSinglyLinkedListClass_Internal(dataType)
 Structure SINGLY_LINKED_LIST_SORTARRAY_#dataType 
  *n.SINGLY_LINKED_LIST_ENTRY_#dataType[256] 
 EndStructure 
  
 Procedure.l SinglyLinkedList_#dataType#(option.l, *handle.SINGLY_LINKED_LIST_ENTRY_#dataType = 0, flag.l = 0) 
  Select option 
   Case #SLL_ADD_ELEMENT 
    If *handle=0 
     *handle = AllocateMemory(SizeOf(SINGLY_LINKED_LIST_ENTRY_#dataType)) 
     ProcedureReturn *handle 
    Else 
     *lastEntry.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle 
     While *lastEntry\next 
      *lastEntry = *lastEntry\next 
     Wend 
     *newEntry.SINGLY_LINKED_LIST_ENTRY_#dataType = AllocateMemory(SizeOf(SINGLY_LINKED_LIST_ENTRY_#dataType)) 
     *lastEntry\next = *newEntry 
     ProcedureReturn *newEntry 
    EndIf 
   Case #SLL_GET_ELEMENT 
    If *handle 
     If flag=0 
      ProcedureReturn *handle 
     Else 
      a.l=0 
      *element.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle 
      While a<flag And *element\next 
       *element = *element\next 
       a+1 
      Wend 
      If a=flag 
       ProcedureReturn *element 
      Else 
       ProcedureReturn 0 
      EndIf 
     EndIf 
    EndIf 
    ProcedureReturn 0 
   Case #SLL_DEL_ELEMENT 
    If *handle 
     If flag=0 
      pointer.l = *handle\next 
      FreeMemory(*handle) 
      ProcedureReturn pointer 
     ElseIf flag>0 
      a.l=0 
      *element.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle 
      While a<flag-1 And *element\next 
       *element = *element\next 
       a+1 
      Wend 
      If a=flag-1 And *element\next 
       pointer.l = *element\next\next 
       FreeMemory(*element\next) 
       *element\next = pointer 
      EndIf 
      ProcedureReturn *handle 
     EndIf 
    EndIf 
    ProcedureReturn 0 
   Case #SLL_NEXT_ELEMENT 
    If *handle 
     *handle = *handle\next 
    EndIf 
    ProcedureReturn *handle 
   Case #SLL_COUNT_ELEMENTS 
    count.l=0 
    If *handle 
     While *handle 
      *handle = *handle\next 
      count + 1 
     Wend 
    EndIf 
    ProcedureReturn count 
   Case #SLL_CLEAR_LIST 
    If *handle 
     *element.SINGLY_LINKED_LIST_ENTRY_#dataType = *handle\next 
     FreeMemory(*handle) 
     While *element 
      *handle = *element 
      *element = *element\next 
      FreeMemory(*handle) 
     Wend 
    EndIf 
    ProcedureReturn 0 
  EndSelect 
 EndProcedure 
  
 Procedure.l SortSinglyLinkedList_#dataType#(type.l, *handle.SINGLY_LINKED_LIST_ENTRY_#dataType, option.l, offset.l = 0, size.l = -1) 
  Protected Result.l, *radixArray.SINGLY_LINKED_LIST_SORTARRAY_#dataType, arrayIndex.l 
  Protected *tmpString.STRING, tmpLen.l, i.l, *element.SINGLY_LINKED_LIST_ENTRY_#dataType, *newEntry.SINGLY_LINKED_LIST_ENTRY_#dataType 
  Result = 0 
  If *handle
   CompilerIf OffsetOf(SINGLY_LINKED_LIST_ENTRY_#dataType#\next) = 0
    offset + 4 
   CompilerEndIf
   Select SinglyLinkedList_#dataType#(#SLL_COUNT_ELEMENTS, *handle) 
    Case 0, 1 
     Result = *handle 
    Case 2 
     If option = 0 ;increasing 
      Select type 
       Case #SLL_SORT_STRING 
        If LCase(PeekS(PeekL(*handle\next+offset),size)) < LCase(PeekS(PeekL(*handle+offset),size)) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_STRING_CASESENSITIVE 
        If PeekS(PeekL(*handle\next+offset),size) < PeekS(PeekL(*handle+offset),size) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_BYTE 
        If PeekB(*handle\next+offset) < PeekB(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_WORD 
        If PeekW(*handle\next+offset) < PeekW(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_LONG 
        If PeekL(*handle\next+offset) < PeekL(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_QUAD 
        If PeekQ(*handle\next+offset) < PeekQ(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_CHARACTER 
        If PeekC(*handle\next+offset) < PeekC(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_FLOAT 
        If PeekF(*handle\next+offset) < PeekF(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_DOUBLE 
        If PeekD(*handle\next+offset) < PeekD(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_DATA_LITTLE_ENDIAN 
        If size>0 
         For i=size-1 To 0 Step -1 
          If PeekB(*handle\next+offset+i)&$FF < PeekB(*handle+offset+i)&$FF 
           *handle\next\next = *handle 
           *handle = *handle\next 
           *handle\next\next = 0 
           Break 
          EndIf 
         Next 
         Result = *handle 
        EndIf 
       Case #SLL_SORT_DATA_BIG_ENDIAN 
        If size>0 
         For i=0 To size-1 
          If PeekB(*handle\next+offset+i)&$FF < PeekB(*handle+offset+i)&$FF 
           *handle\next\next = *handle 
           *handle = *handle\next 
           *handle\next\next = 0 
           Break 
          EndIf 
         Next 
         Result = *handle 
        EndIf 
      EndSelect 
     Else ;decreasing 
      Select type 
       Case #SLL_SORT_STRING 
        If LCase(PeekS(PeekL(*handle\next+offset),size)) > LCase(PeekS(PeekL(*handle+offset),size)) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_STRING_CASESENSITIVE 
        If PeekS(PeekL(*handle\next+offset),size) > PeekS(PeekL(*handle+offset),size) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_BYTE 
        If PeekB(*handle\next+offset) > PeekB(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_WORD 
        If PeekW(*handle\next+offset) > PeekW(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_LONG 
        If PeekL(*handle\next+offset) > PeekL(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_QUAD 
        If PeekQ(*handle\next+offset) > PeekQ(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_CHARACTER 
        If PeekC(*handle\next+offset) > PeekC(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_FLOAT 
        If PeekF(*handle\next+offset) > PeekF(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_DOUBLE 
        If PeekD(*handle\next+offset) > PeekD(*handle+offset) 
         *handle\next\next = *handle 
         *handle = *handle\next 
         *handle\next\next = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_DATA_LITTLE_ENDIAN 
        If size>0 
         For i=size-1 To 0 Step -1 
          If PeekB(*handle\next+offset+i)&$FF > PeekB(*handle+offset+i)&$FF 
           *handle\next\next = *handle 
           *handle = *handle\next 
           *handle\next\next = 0 
           Break 
          EndIf 
         Next 
         Result = *handle 
        EndIf 
       Case #SLL_SORT_DATA_BIG_ENDIAN 
        If size>0 
         For i=0 To size-1 
          If PeekB(*handle\next+offset+i)&$FF > PeekB(*handle+offset+i)&$FF 
           *handle\next\next = *handle 
           *handle = *handle\next 
           *handle\next\next = 0 
           Break 
          EndIf 
         Next 
         Result = *handle 
        EndIf 
      EndSelect 
     EndIf 
    Default 
     *radixArray = AllocateMemory(1024) 
     If *radixArray 
      Select type 
       Case #SLL_SORT_STRING 
        If size = -1 
         *element = *handle 
         While *element 
          *tmpString = *element+offset 
          If *tmpString 
           tmpLen = Len(*tmpString\s) 
           If tmpLen > size 
            size = tmpLen 
           EndIf 
          EndIf 
          *element = *element\next 
         Wend 
        EndIf 
        If size = 0 
         Result = *handle 
        ElseIf size > 0 
         CompilerIf #PB_Compiler_Unicode 
          For i=size-1 To 0 Step -1 
           SortSinglyLinkedList_RadixIncStart() 
            *tmpString = *handle+offset 
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i 
             arrayIndex = 0 
            Else 
             arrayIndex = Asc(LCase(Chr(PeekC(@*tmpString\s+(i*2)))))&$FF 
            EndIf 
           SortSinglyLinkedList_RadixIncEnd() 
           SortSinglyLinkedList_RadixIncStart() 
            *tmpString = *handle+offset 
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i 
             arrayIndex = 0 
            Else 
             arrayIndex = (Asc(LCase(Chr(PeekC(@*tmpString\s+(i*2)))))>>8)&$FF 
            EndIf 
           SortSinglyLinkedList_RadixIncEnd() 
          Next 
          Result = *handle 
         CompilerElse 
          For i=size-1 To 0 Step -1 
           SortSinglyLinkedList_RadixIncStart() 
            *tmpString = *handle+offset 
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i 
             arrayIndex = 0 
            Else 
             arrayIndex = Asc(LCase(Chr(PeekC(@*tmpString\s+i))))&$FF 
            EndIf 
           SortSinglyLinkedList_RadixIncEnd() 
          Next 
          Result = *handle 
         CompilerEndIf 
        EndIf 
       Case #SLL_SORT_STRING_CASESENSITIVE 
        If size = -1 
         *element = *handle 
         While *element 
          *tmpString = *element+offset 
          If *tmpString 
           tmpLen = Len(*tmpString\s) 
           If tmpLen > size 
            size = tmpLen 
           EndIf 
          EndIf 
          *element = *element\next 
         Wend 
        EndIf 
        If size = 0 
         Result = *handle 
        ElseIf size > 0 
         CompilerIf #PB_Compiler_Unicode 
          For i=size-1 To 0 Step -1 
           SortSinglyLinkedList_RadixIncStart() 
            *tmpString = *handle+offset 
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i 
             arrayIndex = 0 
            Else 
             arrayIndex = PeekB(@*tmpString\s+(i*2))&$FF 
            EndIf 
           SortSinglyLinkedList_RadixIncEnd() 
           SortSinglyLinkedList_RadixIncStart() 
            *tmpString = *handle+offset 
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i 
             arrayIndex = 0 
            Else 
             arrayIndex = PeekB(@*tmpString\s+(i*2)+1)&$FF 
            EndIf 
           SortSinglyLinkedList_RadixIncEnd() 
          Next 
          Result = *handle 
         CompilerElse 
          For i=size-1 To 0 Step -1 
           SortSinglyLinkedList_RadixIncStart() 
            *tmpString = *handle+offset 
            If @*tmpString\s = 0 Or Len(*tmpString\s) <= i 
             arrayIndex = 0 
            Else 
             arrayIndex = PeekB(@*tmpString\s+i)&$FF 
            EndIf 
           SortSinglyLinkedList_RadixIncEnd() 
          Next 
          Result = *handle 
         CompilerEndIf 
        EndIf 
       Case #SLL_SORT_BYTE 
        SortSinglyLinkedList_RadixIncStart() 
         arrayIndex = PeekB(*handle+offset)+$80 
        SortSinglyLinkedList_RadixIncEnd() 
        Result = *handle 
       Case #SLL_SORT_WORD 
        For i=0 To 1 
         SortSinglyLinkedList_RadixIncStart() 
          arrayIndex = ((PeekW(*handle+offset)+$8000) >> (i*8)) & $FF 
         SortSinglyLinkedList_RadixIncEnd() 
        Next 
        Result = *handle 
       Case #SLL_SORT_LONG 
        For i=0 To 3 
         SortSinglyLinkedList_RadixIncStart() 
          arrayIndex = ((PeekL(*handle+offset)+$80000000) >> (i*8)) & $FF 
         SortSinglyLinkedList_RadixIncEnd() 
        Next 
        Result = *handle 
       Case #SLL_SORT_QUAD 
        For i=0 To 7 
         SortSinglyLinkedList_RadixIncStart() 
         ;- Quad Sort can be used once this bug is removed 
         ;arrayIndex = ((PeekQ(*handle+offset)+$8000000000000000) >> (i*8)) & $FF 
         ;workaround for quad until bug is fixed>> 
         Protected quad_.q 
         quad_ = PeekQ(*handle+offset) 
         !MOV edx, dword [p.v_quad_+4] 
         !MOV eax, dword [p.v_quad_] 
         !ADD eax, $80000000 
         !ADC edx, 0 
         !MOV ecx, dword [p.v_i] 
         !CMP ecx, 0 
         !JE @f 
          !SHL ecx, 2 
          !SHRD eax, edx, cl 
          !SHRD eax, edx, cl 
         !@@: 
         !AND eax, $FF 
         !MOV dword [p.v_arrayIndex], eax 
         ;<<          SortSinglyLinkedList_RadixIncEnd() 
        Next 
        Result = *handle 
       Case #SLL_SORT_CHARACTER 
        For i=0 To #PB_Compiler_Unicode 
         SortSinglyLinkedList_RadixIncStart() 
          arrayIndex = PeekB(*handle+offset+i)&$FF 
         SortSinglyLinkedList_RadixIncEnd() 
        Next 
        Result = *handle 
       Case #SLL_SORT_FLOAT 
        ;SEEEEEEE EFFFFFFF FFFFFFF FFFFFFF 
        For i=0 To 1 
         SortSinglyLinkedList_RadixIncStart() 
          arrayIndex = PeekB(*handle+offset+i)&$FF 
         SortSinglyLinkedList_RadixIncEnd() 
        Next 
        SortSinglyLinkedList_RadixIncStart() 
         arrayIndex = PeekB(*handle+offset+2)&$7F 
        SortSinglyLinkedList_RadixIncEnd() 
        SortSinglyLinkedList_RadixIncStart() 
         arrayIndex = (PeekW(*handle+offset+2) >> 7) & $FF 
        SortSinglyLinkedList_RadixIncEnd() 
        ;add to index 
        While *handle 
         *element = *handle\next 
         *handle\next = 0 
         arrayIndex = ((PeekB(*handle+offset+3)&$FF) >> 7) 
         *newEntry = *radixArray\n[arrayIndex] 
         If *newEntry = 0 
          *radixArray\n[arrayIndex] = *handle 
         Else 
          While *newEntry\next 
           *newEntry = *newEntry\next 
          Wend 
          *newEntry\next = *handle 
         EndIf 
         *handle = *element 
        Wend 
        ;collect sorted elements 
        *element = 0 
        If *radixArray\n[0] 
         If *element = 0 
          *handle = *radixArray\n[0] 
          *element = *radixArray\n[0] 
         Else 
          *element\next = *radixArray\n[0] 
         EndIf 
         *radixArray\n[0] = 0 
         While *element\next 
          *element = *element\next 
         Wend 
        EndIf 
        If *radixArray\n[1] 
         While *radixArray\n[1] 
          *element = *radixArray\n[1]\next 
          *radixArray\n[1]\next = *handle 
          *handle = *radixArray\n[1] 
          *radixArray\n[1] = *element 
         Wend 
         *radixArray\n[1] = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_DOUBLE 
        ;SEEEEEEE EEEEFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 
        For i=0 To 5 
         SortSinglyLinkedList_RadixIncStart() 
          arrayIndex = PeekB(*handle+offset+i)&$FF 
         SortSinglyLinkedList_RadixIncEnd() 
        Next 
        SortSinglyLinkedList_RadixIncStart() 
         arrayIndex = PeekB(*handle+offset+6)&$0F 
        SortSinglyLinkedList_RadixIncEnd() 
        SortSinglyLinkedList_RadixIncStart() 
         arrayIndex = (PeekW(*handle+offset+6) >> 4) & $FF 
        SortSinglyLinkedList_RadixIncEnd() 
        SortSinglyLinkedList_RadixIncStart() 
         arrayIndex = (PeekW(*handle+offset+6) >> 12) & $07 
        SortSinglyLinkedList_RadixIncEnd() 
        ;add to index 
        While *handle 
         *element = *handle\next 
         *handle\next = 0 
         arrayIndex = ((PeekB(*handle+offset+7)&$FF) >> 7) 
         *newEntry = *radixArray\n[arrayIndex] 
         If *newEntry = 0 
          *radixArray\n[arrayIndex] = *handle 
         Else 
          While *newEntry\next 
           *newEntry = *newEntry\next 
          Wend 
          *newEntry\next = *handle 
         EndIf 
         *handle = *element 
        Wend 
        ;collect sorted elements 
        *element = 0 
        If *radixArray\n[0] 
         If *element = 0 
          *handle = *radixArray\n[0] 
          *element = *radixArray\n[0] 
         Else 
          *element\next = *radixArray\n[0] 
         EndIf 
         *radixArray\n[0] = 0 
         While *element\next 
          *element = *element\next 
         Wend 
        EndIf 
        If *radixArray\n[1] 
         While *radixArray\n[1] 
          *element = *radixArray\n[1]\next 
          *radixArray\n[1]\next = *handle 
          *handle = *radixArray\n[1] 
          *radixArray\n[1] = *element 
         Wend 
         *radixArray\n[1] = 0 
        EndIf 
        Result = *handle 
       Case #SLL_SORT_DATA_LITTLE_ENDIAN 
        If size > 0 
         For i=0 To size-1 
          SortSinglyLinkedList_RadixIncStart() 
           arrayIndex = PeekB(*handle+offset+i)&$FF 
          SortSinglyLinkedList_RadixIncEnd() 
         Next 
         Result = *handle 
        EndIf 
       Case #SLL_SORT_DATA_BIG_ENDIAN 
        If size > 0 
         For i=size-1 To 0 Step -1 
          SortSinglyLinkedList_RadixIncStart() 
           arrayIndex = PeekB(*handle+offset+i)&$FF 
          SortSinglyLinkedList_RadixIncEnd() 
         Next 
         Result = *handle 
        EndIf 
      EndSelect 
      If option = 1 And Result ;decreasing 
       *radixArray\n[0] = Result 
       *handle = 0 
       While *radixArray\n[0] 
        *element =*radixArray\n[0]\next 
        *radixArray\n[0]\next = *handle 
        *handle = *radixArray\n[0] 
        *radixArray\n[0] = *element 
       Wend 
       Result = *handle 
      EndIf 
      FreeMemory(*radixArray) 
     EndIf 
   EndSelect 
  EndIf 
  ProcedureReturn Result 
 EndProcedure 
EndMacro 

Macro DefineSinglyLinkedList(variable, dataType) 
 variable#.SINGLY_LINKED_LIST_ENTRY_#dataType 
EndMacro 

Macro SinglyLinkedList(dataType, option, handle=0, flag=0) 
 SinglyLinkedList_#dataType#(option, handle, flag) 
EndMacro 

Macro SortSinglyLinkedList(dataType, type, handle, option, offset = 0, size = -1) 
 SortSinglyLinkedList_#dataType#(type, handle, option, offset, size) 
EndMacro 

Macro SLLForEach(handle) 
 While handle 
EndMacro 

Macro SLLNext(handle) 
  handle = handle#\next 
 Wend 
EndMacro
(Changes at line: 73-78, 172 and 643)

Now there's a CreateSinglyLinkedListClass_Extend(dataType), which extends the given structure by "*next.SINGLY_LINKED_LIST_ENTRY_#dataType" instead of creating a whole new structure.
irc://irc.freenode.org/#purebasic
Top
Post Reply

Return to “Tricks 'n' Tips”