This is a second try at a home brewed linked list now it uses a OOP model and works (the first revision didn't so well:roll:)
I wanted to create this because Linked List in PB aren't as flexible as I would like so this allows more flexibility and clean coding I also comment it alot so people have a basic understanding of what is going on in the code
like any of my code I post here Use and Distribute freely
if you have any improvements or Fixes please feel free to post them in order to make this better
Code: Select all
;////////////////////////////////////////////////////////////////
;//
;// Title: Home Brewed Linked List
;// Author: Steven "Dreglor" Garcia
;// Date: 2-21-06
;// Version: 2.0.0.0
;// Notes: Uses a Object Oriented Programming like structure
;// Use LinkedList_Create(ElementSize) to create a Linkedlist Object
;// then you can use all of the functions to add, remove, insert, move
;// the linked list and its elements around as you wish.
;// to input data use ListObject\SetElement(@MyData) to directly copy
;// data from the pointer into the element (the length is detirmed by
;// the elementsize) or use ListObject\GetElement() and use the returned
;// Pointer fill/modify the element
;//
;////////////////////////////////////////////////////////////////
;- Structures
Structure Element
*Base.LinkedListProperties
*Next.Element
*Previous.Element
;ElementData
EndStructure
Interface LinkedList ;Methods definitions
Release() ;frees all data include the list it self
GetElement.l() ;returns a pointer to the current element
SetElement(*DataPointer.l) ;copies the data from *DataPointer into the element
CountElements() ;returns the number of elements
GetElementIndex.l() ;returns the position of the current element
GetElementSize.l() ;returns the size (in bytes) of each element
FirstElement.l() ;changed the current element to the first element
LastElement.l() ;changed the current element to the last element
NextElement.l() ;changed the current element to the next element
PreviousElement.l() ;changed the current element to the previous element
SelectElement.l(Index.l) ;changed the current element to the a specified index
ChangeCurrentElement(*Element.Element) ;changed the current element to the specified element
Reset() ;changes the current element to NULL (no current element)
Clear() ;frees all elements and sets the current element to NULL
SwapElements(*Element1.Element, *Element2.Element) ;Swaps the position of two Elements in the list
AddElement.l() ;adds a new element after the current element
InsertElement.l() ;inserts a element before the current element
DeleteElement() ;deletes the current element
EndInterface
Structure LinkedListProperties ;VectorTable, and Properties
Methods.l[SizeOf(LinkedList)/4 + 1] ;+1 is a hack look at LinkedList_Create() for more explaination
Size.l
Count.l
Index.l
*First.Element
*Current.Element
*Last.Element
EndStructure
;- Procedures
Procedure LinkedList_Destroy(*LinkedList.LinkedListProperties)
If *LinkedList = #Null
;...it is Already Freed
ProcedureReturn #True
EndIf
If *LinkedList\First <> #Null
;...There is elements to be freed
;jump to first element
;Save the "next" element
*LinkedList\Current = *LinkedList\First
NextElement = *LinkedList\Current\Next
Repeat
;Destroy the current element
;make the current element the last saved "next" element
;store the new "next" element
FreeMemory(*LinkedList\Current)
*LinkedList\Current = NextElement
NextElement = *LinkedList\Current\Next
Until NextElement = #Null
EndIf
;if all elements are freed, free the base
FreeMemory(*LinkedList)
ProcedureReturn #True
EndProcedure
Procedure LinkedList_GetElement(*LinkedList.LinkedListProperties)
If *LinkedList\Current = #Null
ProcedureReturn #Null
Else
ProcedureReturn *LinkedList\Current + SizeOf(Element)
EndIf
EndProcedure
Procedure LinkedList_SetElement(*LinkedList.LinkedListProperties, *DataPointer)
CopyMemory(*DataPointer, *LinkedList\Current + SizeOf(Element), *LinkedList\Size)
EndProcedure
Procedure LinkedList_CountElements(*LinkedList.LinkedListProperties)
ProcedureReturn *LinkedList\Count
EndProcedure
Procedure LinkedList_ElementIndex(*LinkedList.LinkedListProperties)
ProcedureReturn *LinkedList\Index
EndProcedure
Procedure LinkedList_ElementSize(*LinkedList.LinkedListProperties)
ProcedureReturn *LinkedList\Size
EndProcedure
Procedure LinkedList_FirstElement(*LinkedList.LinkedListProperties)
*LinkedList\Current = *LinkedList\First
*LinkedList\Index = 0
ProcedureReturn *LinkedList\Current
EndProcedure
Procedure LinkedList_LastElement(*LinkedList.LinkedListProperties)
*LinkedList\Current = *LinkedList\Last
*LinkedList\Index = *LinkedList\Count - 1
ProcedureReturn *LinkedList\Current
EndProcedure
Procedure LinkedList_NextElement(*LinkedList.LinkedListProperties)
If *LinkedList\Current <> #Null
*LinkedList\Current = *LinkedList\Current\Next
If *LinkedList\Current <> #Null
*LinkedList\Index + 1
Else
*LinkedList\Index = -1
EndIf
Else
*LinkedList\Current = *LinkedList\First
*LinkedList\Index + 1
EndIf
ProcedureReturn *LinkedList\Current
EndProcedure
Procedure LinkedList_PreviousElement(*LinkedList.LinkedListProperties)
If *LinkedList\Current <> #Null
*LinkedList\Current = *LinkedList\Current\Previous
If *LinkedList\Current <> #Null
*LinkedList\Index - 1
Else
*LinkedList\Index = -1
EndIf
Else
*LinkedList\Index = *LinkedList\Count - 1
*LinkedList\Current = *LinkedList\Last
EndIf
ProcedureReturn *LinkedList\Current
EndProcedure
Procedure Linkedlist_SelectElement(*LinkedList.LinkedListProperties, Index.l)
If *LinkedList\First <> #Null
*LinkedList\Index = 0
*LinkedList\Current = *LinkedList\First
For Element = 0 To Index
If *LinkedList\Current\Next = #Null
Break
EndIf
*LinkedList\Current = *LinkedList\Current\Next
Next
*LinkedList\Index = Element
ProcedureReturn *LinkedList\Current
EndIf
EndProcedure
Procedure Linkedlist_ChangeCurrentElement(*LinkedList.LinkedListProperties, *Element.Element)
*LinkedList\Current = *Element
*LinkedList\Index = 0
RevertElement = *Element
PreviousElement = *LinkedList\Current\Previous
Repeat
*LinkedList\Index + 1
*LinkedList\Current = NextPrevious
PreviousElement = *LinkedList\Current\Previous
Until PreviousElement = #Null
*LinkedList\Current = *Element
EndProcedure
Procedure LinkedList_Reset(*LinkedList.LinkedListProperties)
*LinkedList\Current = #Null
*LinkedList\Index = -1
EndProcedure
Procedure LinkedList_Clear(*LinkedList.LinkedListProperties)
*LinkedList\Current = *LinkedList\First
NextElement = *LinkedList\Current\Next
Repeat
FreeMemory(*LinkedList\Current)
*LinkedList\Current = NextElement
NextElement = *LinkedList\Current\Next
Until NextElement = #Null
*LinkedList\Count = 0
*LinkedList\Index = -1
*LinkedList\First = #Null
*LinkedList\Current = #Null
*LinkedList\Last = #Null
EndProcedure
Procedure LinkedList_SwapElements(*LinkedList.LinkedListProperties, *Element1.Element, *Element2.Element)
*Element1\Previous\Next = *Element2
*Element1\Next\Previous = *Element2
*Element2\Previous\Next = *Element1
*Element2\Next\Previous = *Element1
Swap *Element1\next, *Element2\next
Swap *Element1\Previous, *Element2\Previous
EndProcedure
Procedure LinkedList_AddElement(*LinkedList.LinkedListProperties)
*New.Element = AllocateMemory(*LinkedList\Size + SizeOf(Element))
;*New\Base = *LinkedList
If *LinkedList\Current <> #Null
;if there is a current element...
If *LinkedList\Current\Next <> #Null
;...and there is a vaild "Next" element insert the new element before the next element
;and the new element must point the the existing element correctly
*New\Next = *LinkedList\Current\Next
*New\Previous = *LinkedList\Current
;existing elements must point must to the new element correctly
*LinkedList\Current\Next\Previous = *New
*LinkedList\Current\Next = *New
;Change the index to reflect the comming change in the current element
*LinkedList\Index = *LinkedList\Index + 1
Else
;...if end of list the element is appened
;next element is the new element
*LinkedList\Current\Next = *New
;the previous element in the new element is the last old element (if the makes sense)
;make the new last element as new element
*New\Previous = *LinkedList\Current\Next
*LinkedList\Last = *New
;Change the index to reflect the comming change in the current element
*LinkedList\Index = *LinkedList\Index + 1
EndIf
Else
;...there is no current element
If *LinkedList\First = #Null
;and if there is no first element
;Change the index to reflect the comming change in the current element
*LinkedList\First = *New
*LinkedList\Last = *New
*LinkedList\Index = 0
Else
;if elements exist and no current element apeend at end
;the structure doesn't looke right but whats really going on is somthing like:
;old last is new Previous element
*New\Previous = *LinkedList\Last
;*LinkedList\Element\Next = *New
*LinkedList\Last\Next = *New
;make the new last element as new element
;Change the index to reflect the comming change in the current element
*LinkedList\Last = *New
*LinkedList\Index = *LinkedList\Index + 1
EndIf
EndIf
;make the current element the new element
;increment the count
*LinkedList\Current = *New
*LinkedList\Count = *LinkedList\Count + 1
ProcedureReturn *New
EndProcedure
Procedure LinkedList_InsertElement(*LinkedList.LinkedListProperties)
*New.Element = AllocateMemory(*LinkedList\Size + SizeOf(Element))
;*New\Base = *LinkedList
If *LinkedList\Current <> #Null
;if there is a current element
If *LinkedList\Current\Previous <> #Null
;and if there is a vaild previous element
*New\Next = *LinkedList\Current
*New\Previous = *LinkedList\Current\Previous
*LinkedList\Current\Previous\Next = *New
*LinkedList\Current\Previous = *New
*LinkedList\Index = *LinkedList\Index - 1
Else
;if the beginning of the list
*New\Next = *LinkedList\Current
*LinkedList\Current\Previous = *New
*LinkedList\First = *New
*LinkedList\Index = 0
EndIf
Else
;if there is no current element
If *LinkedList\First = #Null
;...and no first element
*LinkedList\First = *New
*LinkedList\Last = *New
*LinkedList\Index = 0
Else
;and there is a first element
*New\Next = *LinkedList\First
*LinkedList\First\Previous = *New
*LinkedList\First = *New
*LinkedList\Index = 0
EndIf
EndIf
;make the current element the new element
*LinkedList\Current = *New
*LinkedList\Count = *LinkedList\Count + 1
ProcedureReturn *New
EndProcedure
Procedure LinkedList_DeleteElement(*LinkedList.LinkedListProperties)
;redirect the pointer to accomidate the hole that freedata is going to make in the list
If *LinkedList\Current <> #Null
;if there is a current element
If *LinkedList\Current\Previous = #Null
;if we are at the beginning of the list
If *LinkedList\Current\Next <> #Null
*LinkedList\First = *LinkedList\Current\Next
*LinkedList\Current\Next\Previous = #Null
FreeMemory(*LinkedList\Current)
*LinkedList\Current = #Null
*LinkedList\Index = -1
Else
;the list is now empty
FreeMemory(*LinkedList\Current)
*LinkedList\First = #Null
*LinkedList\Last = #Null
*LinkedList\Current = #Null
*LinkedList\Index = -1
ProcedureReturn #True
EndIf
ElseIf *LinkedList\Current\Next = #Null
;if we are at the end of the list
If *LinkedList\Current\Previous <> #Null
*LinkedList\Last = *LinkedList\Current\Previous
*LinkedList\Current\Previous\Next = #Null
FreeMemory(*LinkedList\Current)
*LinkedList\Current = *LinkedList\Last
*LinkedList\Index = *LinkedList\Index - 1
Else
;the list is empty
FreeMemory(*LinkedList\Current)
*LinkedList\First = #Null
*LinkedList\Last = #Null
*LinkedList\Current = #Null
*LinkedList\Index = -1
ProcedureReturn #True
EndIf
Else
;middle of the list
NewCurrent = *LinkedList\Current\Previous
*LinkedList\Current\Previous\Next = *LinkedList\Current\Next
*LinkedList\Current\Next\Previous = *LinkedList\Current\Previous
FreeMemory(*LinkedList\Current)
*LinkedList\Current = NewCurrent
*LinkedList\Index = *LinkedList\Index - 1
EndIf
ProcedureReturn #True
*LinkedList\Count = *LinkedList\Count - 1
Else
ProcedureReturn #True
EndIf
EndProcedure
Procedure LinkedList_Create(ElementSize.l)
;Allocate Memory For the Linked List
*New.LinkedListProperties = AllocateMemory(SizeOf(LinkedListProperties))
*New\Methods[0] = @*New\Methods[1] ;Method Pointer To Pointer Hack
;interfaces look at the value and take it to be a pointer to the methods
;im not sure why this happens but it does happen
;this hack just points to where the methods are located (4 bytes down)
;Set up Methods
*New\Methods[1] = @LinkedList_Destroy()
*New\Methods[2] = @LinkedList_GetElement()
*New\Methods[3] = @LinkedList_SetElement()
*New\Methods[4] = @LinkedList_CountElements()
*New\Methods[5] = @LinkedList_ElementIndex()
*New\Methods[6] = @LinkedList_ElementSize()
*New\Methods[7] = @LinkedList_FirstElement()
*New\Methods[8] = @LinkedList_LastElement()
*New\Methods[9] = @LinkedList_NextElement()
*New\Methods[10] = @LinkedList_PreviousElement()
*New\Methods[11] = @Linkedlist_SelectElement()
*New\Methods[12] = @Linkedlist_ChangeCurrentElement()
*New\Methods[13] = @LinkedList_Reset()
*New\Methods[14] = @LinkedList_Clear()
*New\Methods[15] = @LinkedList_SwapElements()
*New\Methods[16] = @LinkedList_AddElement()
*New\Methods[17] = @LinkedList_InsertElement()
*New\Methods[18] = @LinkedList_DeleteElement()
;Set up Element Information
*New\Count = 0
*New\Index = -1
*New\Size = ElementSize
;Set up Element Pointers
*New\First = #Null
*New\Current = #Null
*New\Last = #Null
;variable overloading is at the heart of the OOP hack;
;we will export as LinkedListPropertie Structurere, assign it as a LinkedList interface, And use it as a LinkedListProperties
;confusing eh? well you can get used to it
ProcedureReturn *New
EndProcedure