xList - Dynamic Lists w/ many features

PolyVector · Post by **PolyVector** » Mon Oct 04, 2004 5:09 am

Here's some list code I came up with for use in FreeStyle... I saw a lot of examples of this sort of thing around the forum and wanted my own... I left out all features I never use and added in some very convenient ones...

xList supports customizable Constructors/Destructores/Enumeration/Sorting
AutoSorting is implimented very efficiently by only sorting the element that was added to the list... I don't have time for detailed documentation... Just try it out, it's wonderful for very dynamic projects...

xList.pb

Code: Select all

Structure xList
  ElementCount.l
  *First.xElement
  *Last.xElement
  DataSize.l
  ConstructorProc.l
  DestructorProc.l
  AutoSortProc.l
  SortReversed.l
EndStructure

Structure xElement
  *Parent.xList
  *Forward.xElement
  *Backward.xElement
EndStructure

Procedure xNewList(DataSize.l)
  Protected *List.xList
  *List=AllocateMemory(SizeOf(xList))
  *List\DataSize=DataSize
  ProcedureReturn *List
EndProcedure

Procedure xEnumElements(*List.xList,CallbackProc.l,Param.l)
  Protected *Element.xElement,*NextElement.xElement
  *Element=*List\first
  While *Element
    *NextElement=*Element\Forward
    If CallFunctionFast(CallbackProc,*Element+SizeOf(xElement),Param)=#Null
      ProcedureReturn #True
    EndIf
    *Element=*NextElement
  Wend
  ProcedureReturn #False
EndProcedure

Procedure xEnumElements_Reversed(*List.xList,CallbackProc.l,Param.l)
  Protected *Element.xElement
  *Element=*List\Last
  While *Element
    CallFunctionFast(CallbackProc,*Element+SizeOf(xElement),Param)
    *Element=*Element\Backward
  Wend
EndProcedure

Procedure xQuickSwapElement(*BaseElement.xElement)
  Protected *List.xList,*TopElement.xElement
  *List=*BaseElement\Parent
  *TopElement=*BaseElement\Forward
  If *TopElement
    If *BaseElement\Backward
      *BaseElement\Backward\Forward=*TopElement
    EndIf
    If *TopElement\Forward
      *TopElement\Forward\Backward=*BaseElement
    EndIf
    *BaseElement\Forward=*TopElement\Forward
    *TopElement\Backward=*BaseElement\Backward
    *BaseElement\Backward=*TopElement
    *TopElement\Forward=*BaseElement
    
    ;/List Cleanup:
    If *List\first=*BaseElement
      *List\first=*TopElement
    EndIf
    If *List\Last=*TopElement
      *List\Last=*BaseElement
    EndIf
    
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure xSortList(*List.xList,SortProc.l)
  Protected *Element.xElement
  Protected I.l,MaxCount.l,Modified.l
  MaxCount=*List\ElementCount-1
  For I=1 To MaxCount
    Modified=#False
    *Element=*List\first
    While *Element And *Element\Forward
      If CallFunctionFast(SortProc,*Element+SizeOf(xElement),*Element\Forward+SizeOf(xElement))<>*List\SortReversed
        xQuickSwapElement(*Element)
        Modified=#True
      Else
        *Element=*Element\Forward
      EndIf
    Wend
    If Modified=#False
      Break
    EndIf
  Next
  ProcedureReturn #True
EndProcedure

Procedure xSortElement(*Element.xElement,SortProc.l)
  Protected *List.xList
  *Element-SizeOf(xElement)
  *List=*Element\Parent
  While *Element And *Element\Forward
    If CallFunctionFast(SortProc,*Element+SizeOf(xElement),*Element\Forward+SizeOf(xElement))<>*List\SortReversed
      xQuickSwapElement(*Element)
      Modified=#True
    Else
      *Element=*Element\Forward
    EndIf
    If Modified=#False
      Break
    EndIf
  Wend
  While *Element And *Element\Backward
    If CallFunctionFast(SortProc,*Element\Backward+SizeOf(xElement),*Element+SizeOf(xElement))<>*List\SortReversed
      xQuickSwapElement(*Element\Backward)
      Modified=#True
    Else
      *Element=*Element\Backward
    EndIf
    If Modified=#False
      Break
    EndIf
  Wend
EndProcedure

Procedure xGetList(*Element.xElement)
  *Element-SizeOf(xElement)
  ProcedureReturn *Element\Parent
EndProcedure

Procedure xFirstElement(*List.xList)
  If *List\first
    ProcedureReturn *List\first+SizeOf(xElement)
  EndIf
  ProcedureReturn #Null
EndProcedure

Procedure xLastElement(*List.xList)
  If *List\Last
    ProcedureReturn *List\Last+SizeOf(xElement)
  EndIf
  ProcedureReturn #Null
EndProcedure

Procedure xNextElement(*Element.xElement)
  *Element-SizeOf(xElement)
  If *Element\Forward
    ProcedureReturn *Element\Forward+SizeOf(xElement)
  EndIf
  ProcedureReturn #Null
EndProcedure

Procedure xPreviousElement(*Element.xElement)
  *Element-SizeOf(xElement)
  If *Element\Backward
    ProcedureReturn *Element\Backward+SizeOf(xElement)
  EndIf
  ProcedureReturn #Null
EndProcedure

;Procedure xCurrentElement(*List.xList)
;  If *List\Current
;    ProcedureReturn *List\Current+SizeOf(xElement)
;  EndIf
;  ProcedureReturn #Null
;EndProcedure

Procedure xCountList(*List.xList)
  ProcedureReturn *List\ElementCount
EndProcedure

Procedure xSetElementConstructor(*List.xList,ConstructorProc.l)
  *List\ConstructorProc=ConstructorProc
EndProcedure

Procedure xSetElementDestructor(*List.xList,DestructorProc.l)
  *List\DestructorProc=DestructorProc
EndProcedure

Procedure xSetElementAutoSortProc(*List.xList,SortProc.l)
  *List\AutoSortProc=SortProc
EndProcedure

Procedure xSetElementSortReversed(*List.xList,TrueFalse.l)
  *List\SortReversed=TrueFalse
EndProcedure
  
Procedure _xAddElement(*List.xList,Param.l)
  Protected *Element.xElement,*NewIndexTable.l
  *Element=AllocateMemory(SizeOf(xElement)+*List\DataSize)
  *Element\Parent=*List
  *Element\Forward=#Null;/Safety First
  *Element\Backward=#Null;/Safety First
  If *List\ElementCount=#Null;/First Element
    *List\first=*Element
    *List\Last=*Element
  Else
    *List\Last\Forward=*Element
    *Element\Backward=*List\Last
    *List\Last=*Element
  EndIf
  
  
  *List\ElementCount+1
  If *List\ConstructorProc
    CallFunctionFast(*List\ConstructorProc,*Element+SizeOf(xElement),Param)
  EndIf
  If *List\AutoSortProc
    xSortElement(*Element+SizeOf(xElement),*List\AutoSortProc)
    ;xSortList(*List,*List\AutoSortProc)
  EndIf
  ProcedureReturn *Element+SizeOf(xElement)  
EndProcedure

Procedure xAddElement(*List.xList)
  ProcedureReturn _xAddElement(*List,#Null)
EndProcedure

Procedure _xDeleteElement(*Element.xElement,QuickDelete.l)
  Protected *List.xList
  *List=*Element\Parent
  If *Element
    If QuickDelete=#False
      If *Element\Forward
        *Element\Forward\Backward=*Element\Backward
      Else
        *List\Last=*Element\Backward
      EndIf
      If *Element\Backward
        *Element\Backward\Forward=*Element\Forward
      Else
        *List\first=*Element\Forward
      EndIf
    EndIf
    If *List\DestructorProc
      CallFunctionFast(*List\DestructorProc,*Element+SizeOf(xElement))
    EndIf
    FreeMemory(*Element)
    *List\ElementCount-1
  EndIf
EndProcedure

Procedure xDeleteElement(*Element.xElement)
  If *Element
    *Element-SizeOf(xElement)
    _xDeleteElement(*Element,#False)
  EndIf
EndProcedure

Procedure _xDeleteList_Enum(*Element.xElement,Param.l)
  *Element-SizeOf(xElement)
  _xDeleteElement(*Element,#True)
  ProcedureReturn #True
EndProcedure

Procedure xDeleteList(*List.xList)
  xEnumElements(*List,@_xDeleteList_Enum(),0)
  *List\ElementCount=#Null
  *List\first=#Null
  *List\Last=#Null
  FreeMemory(*List)
EndProcedure

xListExample.pb

Code: Select all

XIncludeFile "xList.pb"

;-Example Sorting Procedure
Procedure SortNumbers(*Element1.LONG,*Element2.LONG)
  If *Element1\l>*Element2\l
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

;-Example Constructor/Destructor
Procedure ElementConstructor(*Element.LONG,Param.l)
  *Element\l=Param
  Debug "ElementConstructor ( "+Str(*Element\l)+" )"
EndProcedure

Procedure ElementDestructor(*Element.LONG)
  Debug "ElementDestructor ( "+Str(*Element\l)+" )"
EndProcedure

;-Example Enumeration Procedure
Procedure DebugList(*Element.LONG,Param.l)
  Debug "DebugList: "+Str(*Element\l)
  ProcedureReturn #True
EndProcedure



;-Example Program:
List=xNewList(SizeOf(LONG))
xSetElementConstructor(List,@ElementConstructor());/Optional Constructor
xSetElementDestructor(List,@ElementDestructor());/Optional Destructor
xSetElementAutoSortProc(List,@SortNumbers());/Optional AutoSort Procedure (Can be used for regular sorting as well)
xSetElementSortReversed(List,#False)
*Element.LONG

Debug "----------------------"
Debug "*** Create Auto-Sorted List ***"
For x=1 To 5
  *Element=_xAddElement(List,Random(10))
Next

Debug ""
Debug "----------------------"
Debug "*** Auto-Ascending List ***"
*Element=xFirstElement(List)
If *Element
  Repeat
    Debug *Element\l
    *Element=xNextElement(*Element)
  Until *Element=#Null
EndIf

Debug ""
Debug "----------------------"
Debug "*** Decending List ***"
xSetElementSortReversed(List,#True)
xSortList(List,@SortNumbers())
*Element=xFirstElement(List)
If *Element
  Repeat
    Debug *Element\l
    *Element=xNextElement(*Element)
  Until *Element=#Null
EndIf

Debug ""
Debug "----------------------"
Debug "*** Enumerate List ***"
xEnumElements(List,@DebugList(),0)

Debug ""
Debug "----------------------"
Debug "*** Enumerate List Reversed***"
xEnumElements_Reversed(List,@DebugList(),0)

Debug ""
Debug "----------------------"
Debug "*** Destroy ***"
xDeleteList(List)