PureBasic Forums - English

Posted: **Mon Sep 20, 2004 2:48 pm**

Code updated For 5.20+

Functions to have nested lists and sort/find according to field element offset.

The sorting is based on a code a found here,
viewtopic.php?t=2506&highlight=sort+list

there isn't LLDeleteElement(), i still don't need it.

The sorting will be much more slower than sortarray() but sometimes a sortable list is the only way of doing things(not counting the weird pb array behaviour, global, no pointer..) so i did this functions.

Look at the end of the code for an example.

Code: Select all

;LIST FUNCTIONS
;Justin 9/2004

Structure _LL_DATA_
  pFirst.l      ;pointer to the first element
  pLast.l         ;pointer to the last element
  pCurrent.l   ;pointer to the current element
  Index.l         ;0 based index of current element, -1 if no current element
  Count.l         ;number of elements in list
  elSize.l      ;element size (not including extra pointers pNext, pPrev)
EndStructure

;Creates a new list
;elSize : size of an element, use sizeof() PB command.
;Returns : handle of new list
Procedure LLNew(elSize)
  *pList._LL_DATA_ = AllocateMemory(SizeOf(_LL_DATA_))
  *pList\Index = -1
  *pList\Count = 0
  *pList\elSize = elSize
  ProcedureReturn *pList
EndProcedure

;Gets the index of the selected element
;pList : list handle
;Returns : 0 based index of selected element or -1 if there is no selected element
Procedure LLIndex(*pList._LL_DATA_) : ProcedureReturn *pList\Index : EndProcedure

;Gets the number of elements
;pList : list handle
;Returns : number of elements in list
Procedure LLCount(*pList._LL_DATA_) : ProcedureReturn *pList\Count : EndProcedure

;Adds a new element after the selected element or as the first if there is no
;selected element, the newly added element becomes the selected element.
;Returns : pointer to the new element.
Procedure LLAdd(*pList._LL_DATA_)
  nExtraPtr = 2 ;(pNext, pPrev)
  Count = *pList\Count
  elSize = *pList\elSize
  pElement = AllocateMemory(elSize + (nExtraPtr * 4))
  If count=0 ;no items, add as first
    *pList\pFirst = pElement
    *pList\pLast = pElement
    *pList\pCurrent = pElement
  Else ;items, add after current
    *paTemp.LONG
    pCurrent = *pList\pCurrent
    
    If pCurrent=*pList\pLast ;current element is the last
      ;work on current, set next of current
      *paTemp = pCurrent + elSize ;(pNext)
      *paTemp\l = pElement
      
      ;work on new, set previous of new
      *paTemp = pElement + elSize + 4 ;(pPrev)
      *paTemp\l = pCurrent
      
      ;new last element
      *pList\pLast = pElement
    Else ;current element is not the last   
      ;work on current, set next
      ;get pointer of next element
      *paTemp = pCurrent + elSize ;(pNext)
      pNextEl = *paTemp\l ;save next of current
      ;set new next element of the current element
      *paTemp\l = pElement
      
      ;work on next of current , set its previous
      *paTemp = pNextEl + elSize + 4 ;(pPrev)
      *paTemp\l = pElement
      
      ;work on new, set previous and next
      *paTemp = pElement + elSize ;(pNext)
      *paTemp\l = pNextEl
      *paTemp + 4 ;(pPrev)
      *paTemp\l = pCurrent
    EndIf
  EndIf
  *pList\Index + 1
  *pList\Count + 1
  *pList\pCurrent = pElement
  ProcedureReturn pElement
EndProcedure

;Selects an element
;pList : list handle
;iElement : 0 based index of the element to select. If it is greater than the number
;                  of elements selects the last. If it is negative selects the first.
;Returns  : pointer to the selected element or 0 if there were no elements.
Procedure LLSelect(*pList._LL_DATA_, iElement)
  elSize = *pList\elSize
  Count = *pList\Count
  *pFirst = *pList\pFirst
  
  If Count=0 : ProcedureReturn 0 : EndIf
  
  If iElement<=0 ;return first
    *pList\Index = 0
    *pList\pCurrent = *pFirst
    ProcedureReturn *pFirst
  ElseIf iElement>=Count-1 ;return last
    *pList\Index = Count-1
    *pList\pCurrent = *pList\pLast
    ProcedureReturn *pList\pLast
  EndIf
  
  *pMov = *pFirst
  *paNext.LONG
  For i=1 To iElement
    *paNext = *pMov + elSize
    *pElement = *paNext\l
    *pMov = *pElement
  Next
  ;select
  *pList\pCurrent = *pElement
  *pList\Index = iElement
  ProcedureReturn *pElement
EndProcedure

;Selects the first element
;pList : list handle
;Returns : pointer to the first element or 0 if there were no elements.
Procedure LLFirst(*pList._LL_DATA_)
  pFirst = *pList\pFirst
  If pFirst<>0
    *pList\Index = 0
    *pList\pCurrent = pFirst
  EndIf
  ProcedureReturn pFirst
EndProcedure

;Selects the last element
;pList : list handle
;Returns : pointer to the last element or 0 if there were no elements.
Procedure LLLast(*pList._LL_DATA_)
  pLast = *pList\pLast
  If pLast<>0
    *pList\Index = *pList\Count - 1
    *pList\pCurrent = pLast
  EndIf
  ProcedureReturn pLast
EndProcedure

;Selects the next element of the current selected element.
;pList : list handle
;Returns : pointer to the next element or 0 if there was no next element(end of list)
Procedure LLNext(*pList._LL_DATA_)
  *paTemp.LONG
  
  pCurrent = *pList\pCurrent
  If pCurrent
    *paTemp = pCurrent + *pList\elSize ;(pNext)
    pNext = *paTemp\l
    If pNext
      *pList\pCurrent = pNext
      *pList\Index + 1
    EndIf
    ProcedureReturn pNext
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

;Selects the previous element of the current selected element.
;pList : list handle
;Returns : pointer to the previous element or 0 if there was no previous element(end of list)
Procedure LLPrev(*pList._LL_DATA_)
  *paTemp.LONG
  
  pCurrent = *pList\pCurrent
  If pCurrent
    *paTemp = pCurrent + *pList\elSize + 4;(pPrev)
    pPrev = *paTemp\l
    If pPrev
      *pList\pCurrent = pPrev
      *pList\Index - 1
    EndIf
    ProcedureReturn pPrev
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

;Deletes all the elements. The list is still valid but it is empty.
;pList : list handle
;Returns : number of elements deleted
Procedure LLClear(*pList._LL_DATA_)
  Count = *pList\Count
  realCount = 0
  
  *pList\Index = -1
  *pList\pCurrent = 0
  
  If Count=0
    *pList\pFirst = 0
    *pList\pLast = 0
    ProcedureReturn 0
  Else
    pEl = LLFirst(*pList)
    While pEl
      
      
      ;               FreeMemory(pEl)
      
      
      *pList\Count - 1
      realCount + 1
      
      pEl = LLNext(*pList)   
    Wend
  EndIf
  *pList\pFirst = 0
  *pList\pLast = 0
  ProcedureReturn realCount
EndProcedure

;Destroys a list releasing all memory associated with it. The handle is no longer valid.
;pList : list handle
;Returns : number of elements deleted
Procedure LLDestroy(*pList._LL_DATA_)
  Count = LLClear(*pList)
  FreeMemory (*pList)
  ProcedureReturn Count
EndProcedure

;Searches a list for an element matching an integer value.
;pList : list handle
;iStart : index of the element to start the search, this element is excluded
;               from the search. Use -1 to search from the beginning.
;offset : offset of the field to search in the element structure, use offsetoff() PB command.
;elData : integer value to search.
;Returns :    pointer to the element if a match is found or 0 if not found. If an element is
;                  found it becomes the selected element. If no match is found the last element
;                  becomes the selected element, since the list has been searched to the end.
Procedure LLFindI(*pList._LL_DATA_, iStart, offset, elData)
  If iStart = -1
    pEl = LLFirst(*pList)
  Else
    pEl = LLSelect(*pList, iStart+1)
  EndIf
  
  If pEl=0 : ProcedureReturn 0 : EndIf
  
  *pTemp.LONG
  While pEl
    *pTemp = pEl + offset
    If *pTemp\l = elData : ProcedureReturn pEl : EndIf
    
    pEl = LLNext(*pList)   
  Wend
  ProcedureReturn 0 ;not found
EndProcedure

;Same as LLFindI() but to search a string value.
;bCase : TRUE search is case sensitive, FALSE search is not case sensitive.
Procedure LLFindS(*pList._LL_DATA_, iStart, offset, elData$, bCase.b)
  If iStart = -1
    pEl = LLFirst(*pList)
  Else
    pEl = LLSelect(*pList, iStart+1)
  EndIf
  
  If pEl=0 : ProcedureReturn 0 : EndIf
  
  *pTemp.LONG
  If bCase ;case sensitive
    While pEl
      *pTemp = pEl + offset
      If lstrcmp_(*pTemp\l, elData$)=0 : ProcedureReturn pEl : EndIf
      
      pEl = LLNext(*pList)   
    Wend
  Else ;not case sensitive
    While pEl
      *pTemp = pEl + offset
      If lstrcmpi_(*pTemp\l, elData$)=0 : ProcedureReturn pEl : EndIf
      
      pEl = LLNext(*pList)   
    Wend
  EndIf
  ProcedureReturn 0 ;not found
EndProcedure

;Sorts a list in ascending order according to an element integer field
;pList : list handle
;offset : offset of the element field to sort , use offsetof()
Procedure LLSortI(*pList._LL_DATA_, offset)
  *paTemp.LONG
  Define *pEL
  elSize = *pList\elSize
  temp = AllocateMemory(elSize)
  
  last = LLCount(*pList) -1 
  
  While last >= 1   
    *pEL = LLFirst(*pList)
    uptodo = 0 ; ini     
    *paTemp = *pEL + offset
    iVal = *paTemp\l
    For i = 1 To last       
      *paTemp = *pEL + elSize + 4 ;pPrev
      pPrev = *paTemp\l     
      *pEL = LLNext(*pList) : *paTemp = *pEL + offset 
      If iVal <= *paTemp\l   
        iVal = *paTemp\l   
      Else ;exchange with previous
        CopyMemory(*pEL, temp, elSize)
        
        *paTemp = *pEL + elSize + 4 ;pPrev
        pPrev = *paTemp\l
        
        CopyMemory(pPrev, *pEL, elSize) 
        CopyMemory(temp, pPrev, elSize) 
        
        uptodo = i-1     
      EndIf     
    Next   
    last = uptodo 
  Wend    
  FreeMemory(temp)
EndProcedure

;Same as LLSortI() but for strings.
;fCase : true , sort is case sensitive, false case insensitive
Procedure LLSortS(*pList._LL_DATA_, offset, fCase.b)
  *paTemp.LONG
  Define *pEL
  elSize = *pList\elSize
  temp = AllocateMemory(elSize)
  
  last = LLCount(*pList) -1 
  
  While last >= 1   
    *pEL = LLFirst(*pList)
    uptodo = 0 ; ini     
    *paTemp = *pEL + offset
    iVal = *paTemp\l
    For i = 1 To last       
      *paTemp = *pEL + elSize + 4 ;pPrev
      pPrev = *paTemp\l     
      *pEL = LLNext(*pList) : *paTemp = *pEL + offset 
      
      If fCase
        cmp = lstrcmp_(iVal, *paTemp\l)
      Else
        cmp = lstrcmpi_(iVal, *paTemp\l)
      EndIf
      
      If cmp<=0 
        iVal = *paTemp\l   
      Else ;exchange with previous
        CopyMemory(*pEL, temp, elSize)
        
        *paTemp = *pEL + elSize + 4 ;pPrev
        pPrev = *paTemp\l
        
        CopyMemory(pPrev, *pEL, elSize) 
        CopyMemory(temp, pPrev, elSize) 
        
        uptodo = i-1     
      EndIf     
    Next   
    last = uptodo 
  Wend    
  FreeMemory(temp)
EndProcedure


;- TEST CODE
Structure _PERSONS
  name.s
  phones.l ;phone list
EndStructure

Structure _PHONES
  num.l
EndStructure

*person._PERSONS
*phone._PHONES

persons = LLNew(SizeOf(_PERSONS))

;1st person
*person = LLAdd(persons) : *person\name = "Mike"
phones = LLNew(SizeOf(_PHONES))
*phone = LLAdd(phones) : *phone\num = 555
*phone = LLAdd(phones) : *phone\num = 444
*person\phones = phones

;2nd person
*person = LLAdd(persons) : *person\name = "John"
phones = LLNew(SizeOf(_PHONES))
*phone = LLAdd(phones) : *phone\num = 666
*phone = LLAdd(phones) : *phone\num = 333
*phone = LLAdd(phones) : *phone\num = 222
*person\phones = phones

;3rd person
*person = LLAdd(persons) : *person\name = "Jim"
phones = LLNew(SizeOf(_PHONES))
*phone = LLAdd(phones) : *phone\num = 888
*person\phones = phones

;sort according to name
LLSortS(persons, OffsetOf(_PERSONS\name), 0)

;display
*person = LLFirst(persons)
While *person
  Debug *person\name
  
  phones = *person\phones
  *phone = LLFirst(phones)
  While *phone
    Debug "   " + Str(*phone\num)
    *phone = LLNext(phones)
  Wend
  
  *person = LLNext(persons)   
Wend

;display names in reverse order
Debug ""
*person = LLLast(persons)
While *person
  Debug *person\name
  *person = LLPrev(persons)   
Wend

;find John and display phones
Debug ""
*person = LLFindS(persons, -1, OffsetOf(_PERSONS\name), "John", 0)
If *person
  Debug "John"
  phones = *person\phones
  *phone = LLFirst(phones)
  While *phone
    Debug "   " + Str(*phone\num)
    *phone = LLNext(phones)
  Wend
EndIf    

;free
*person = LLFirst(persons)
While *person
  LLDestroy(*person\phones)
  *person = LLNext(persons)   
Wend
LLDestroy(persons)
End

Posted: **Mon Sep 20, 2004 5:33 pm**

Wouldn't it be quicker just to swap the order of items in the linked list rather than copy the data three times (more so for larger data structures)? You also wouldn't need to allocate memory at the start of your sort routines.

Posted: **Mon Sep 20, 2004 5:43 pm**

Of course, but changing the pointers is a very big mess, you have to handle a lot of cases. i would be very interested in seeing it working, if someone can do it please post.

Posted: **Mon Sep 20, 2004 6:31 pm**

I'm sure horst has updated his list sorting code sine that post you linked to, but I don't know if he still copies data or swaps pointers. The code should be on his homepage, not sure where that is though - link should be in his profile or signature.

However, the pseudocode to do this (I'm too tired to think properly) would be something like this:

Code: Select all

If current item's pNext is null
    Set pointer to end of list to be preceeding item
Else
    Get pointer to next item after current item
    Set pPrev in that item to preceeding item
EndIf

If preceeding item's pPrev is null
    Set pointer to start of list to be current item
Else
    Get pointer to previous item before preceeding item
    Set pNext in that item to current item
EndIf

Set preceeding item's pNext to current item's pNext
Set current item's pNext to preceeding item
Set current item's pPrev to preceeding item's pPrev
Set preceeding item's pPrev to current item

As I said, it's maybe only quicker if you are sorting with large data structures because you are looking at setting at least 6 longwords (that's not including the logic or comparisons) which would be similar to copying structures with 2 longwords (if you do three copies * 2 longwords = 6).

Another suggestion would be to have the next and previous pointers before the user's data. The advantages are that you can generalise your routines more (the next and previous are always in the same place in the structure) and you can save an entire addition (wow! ;) when calculating the positions of the pointers.

EDIT: I just realised that if you swap pointers then you'll also need some way to re-synchronise the current item pointer and the index position. My bad, sorry.

Posted: **Tue Sep 21, 2004 8:55 pm**

> I'm sure horst has updated his list sorting code ...

Latest update is May 2004 for the linked list sort.

My algorithms do not swap elements, I just do CopyMemory(), because I always have a "gap" to fill, and each CopyMemory() leaves a new gap...

Changing pointers would make it much more complicated, and I doubt if that wold be much faster.

PureBasic Forums - English

Dynamic list with sort and find

Dynamic list with sort and find