PureBasic Forums - English

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