yet another implementation of a linkedlist

pcfreak · Post by **pcfreak** » Tue Feb 03, 2009 8:14 pm

here you go, with a little usage example at the end.
the aim was it to make it possible to put a linkedlist into another linkedlist...

Code: Select all

Prototype.i CompareFunction(*a, *b, options.i)

Interface IDoublyLinkedList
 addE()     ;return pointer to data memory
 insertE()  ;return pointer to data memory
 deleteE()  ;return pointer to data memory
 currentE() ;return pointer to data memory
 nextE()    ;return pointer to data memory
 priorE()   ;return pointer to data memory
 firstE()   ;return pointer to data memory
 lastE()    ;return pointer to data memory
 index()    ;return index of the current element
 selectE(index.i) ;return pointer to data memory
 size()     ;return number of elments in the list
 reset()    ;reset list index
 clear()    ;remove all elements in the list
 sort(compare.CompareFunction, options.i)
 ;free object
 delete()
EndInterface

Structure EDoubleLinkedList
 *after.EDoubleLinkedList
 *before.EDoubleLinkedList
EndStructure

Structure ODoublyLinkedList
 ;Address to the methods array
 methodAddress.i
 ;Pointer to each method
 methods.i[SizeOf(IDoublyLinkedList) / (SizeOf(INTEGER))]
 ;Class Attributes
  ;Constants
  elementSize.i
  ;Variables
  size.i
  index.i
  *first.EDoubleLinkedList
  *last.EDoubleLinkedList
  *current.EDoubleLinkedList
EndStructure


Declare.i newDoublyLinkedList(dataSize.i)
Declare.i DoublyLinkedList_addE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_insertE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_deleteE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_currentE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_nextE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_priorE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_firstE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_lastE(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_index(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_selectE(*this.IDoublyLinkedList, index.i)
Declare.i DoublyLinkedList_size(*this.IDoublyLinkedList)
Declare   DoublyLinkedList_reset(*this.IDoublyLinkedList)
Declare   DoublyLinkedList_clear(*this.IDoublyLinkedList)
Declare.i DoublyLinkedList_mergeSort(*this.IDoublyLinkedList, compare.CompareFunction, options.i)
Declare   DoublyLinkedList_delete(*this.IDoublyLinkedList)


DataSection
 ODoublyLinkedList_methods:
  Data.i @DoublyLinkedList_addE()
  Data.i @DoublyLinkedList_insertE()
  Data.i @DoublyLinkedList_deleteE()
  Data.i @DoublyLinkedList_currentE()
  Data.i @DoublyLinkedList_nextE()
  Data.i @DoublyLinkedList_priorE()
  Data.i @DoublyLinkedList_firstE()
  Data.i @DoublyLinkedList_lastE()
  Data.i @DoublyLinkedList_index()
  Data.i @DoublyLinkedList_selectE()
  Data.i @DoublyLinkedList_size()
  Data.i @DoublyLinkedList_reset()
  Data.i @DoublyLinkedList_clear()
  Data.i @DoublyLinkedList_mergeSort()
  Data.i @DoublyLinkedList_delete()
EndDataSection


Procedure.i newDoublyLinkedList(dataSize.i)
 Protected *object.ODoublyLinkedList
 *object = AllocateMemory(SizeOf(ODoublyLinkedList))
 If *object = #Null
  ProcedureReturn #Null
 EndIf
 *object\methodAddress = @*object\methods
 CopyMemory(?ODoublyLinkedList_methods, @*object\methods, SizeOf(IDoublyLinkedList))
 *object\elementSize = SizeOf(EDoubleLinkedList) + dataSize
 *object\size    = 0
 *object\index   = -1
 *object\first   = #Null
 *object\last    = #Null
 *object\current = #Null
 ProcedureReturn *object
EndProcedure


Procedure.i DoublyLinkedList_addE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList, *newEntry.EDoubleLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 *newEntry = AllocateMemory(*object\elementSize)
 If *newEntry = #Null
  ProcedureReturn #Null
 EndIf
 *object\index = *object\size
 *object\size + 1
 If *object\last = #Null
  *object\first = *newEntry
  *object\last  = *newEntry
 Else
  *newEntry\before   = *object\last
  *object\last\after = *newEntry
  *object\last       = *newEntry
 EndIf
 *object\current = *newEntry
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_insertE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList, *newEntry.EDoubleLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 *newEntry = AllocateMemory(*object\elementSize)
 If *newEntry = #Null
  ProcedureReturn #Null
 EndIf
 *object\size + 1
 If *object\current = #Null
  *object\index = -1
  If *object\first = #Null
   *object\first = *newEntry
   *object\last  = *newEntry
  Else
   *newEntry\after      = *object\first
   *object\first\before = *newEntry
   *object\first        = *newEntry
  EndIf
  *object\current = *newEntry
 Else
  If *object\current = *object\first
   *newEntry\after      = *object\first
   *object\first\before = *newEntry
   *object\first        = *newEntry
   *object\current      = *newEntry
  Else
   *newEntry\after              = *object\current
   *newEntry\before             = *object\current\before
   *object\current\before\after = *newEntry
   *object\current\before       = *newEntry
   *object\current              = *newEntry
  EndIf
 EndIf
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_deleteE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 If *object\current = #Null
  ProcedureReturn #Null
 EndIf
 *object\size - 1
 If *object\current = *object\first And *object\current = *object\last
  FreeMemory(*object\current)
  *object\first   = #Null
  *object\last    = #Null
  *object\current = #Null
  *object\index   = -1
 ElseIf *object\current = *object\first
  *object\first        = *object\first\after
  *object\first\before = #Null
  FreeMemory(*object\current)
  *object\current      = *object\first
 ElseIf *object\current = *object\last
  *object\last       = *object\last\before
  *object\last\after = #Null
  FreeMemory(*object\current)
  *object\current    = *object\last
  *object\index      - 1
 Else
  *newCurrent.EDoubleLinkedList = *object\current\after
  *object\current\before\after  = *object\current\after
  *object\current\after\before  = *object\current\before
  FreeMemory(*object\current)
  *object\current               = *newCurrent
 EndIf
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_currentE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 If *object\current = #Null
  ProcedureReturn #Null
 EndIf
 ProcedureReturn *object\current + SizeOf(EDoubleLinkedList)
EndProcedure


Procedure.i DoublyLinkedList_nextE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 If *object\current = #Null
  *object\current = *object\first
  *object\index   = 0
 ElseIf *object\current = *object\last
  *object\current = #Null
  *object\index   = -1
 Else
  *object\current = *object\current\after
  *object\index   + 1
 EndIf
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_priorE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 If *object\current = #Null
  *object\current = *object\last
  *object\index   = *object\size - 1
 ElseIf *object\current = *object\first
  *object\current = #Null
  *object\index   = -1
 Else
  *object\current = *object\current\before
  *object\index   - 1
 EndIf
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_firstE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 *object\current = *object\first
 *object\index   = 0
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_lastE(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 *object\current = *object\last
 *object\index   = *object\size - 1
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_index(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn 0
 EndIf
 *object = *this
 ProcedureReturn *object\index
EndProcedure


Procedure.i DoublyLinkedList_selectE(*this.IDoublyLinkedList, index.i)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn #Null
 EndIf
 *object = *this
 If index < 0 Or index >= *object\size
  *object\current = #Null
  *object\index   = -1
 ElseIf index = 0 And *object\first
  *object\current = *object\first
  *object\index   = 0
 ElseIf index = *object\size - 1
  *object\current = *object\last
  *object\index   = *object\size - 1
 ElseIf index < *object\index
  If index < *object\index - index
   *object\current = *object\first
   For i = 1 To index
    *object\current = *object\current\after
   Next
   *object\index = index
  Else
   While *object\index > index
    *object\current = *object\current\before
    *object\index   - 1
   Wend
  EndIf
 ElseIf index > *object\index
  If *object\current = #Null
   If index < (*object\size - 1) - index
    *object\current = *object\first
    For i = 1 To index
     *object\current = *object\current\after
    Next
    *object\index = index
   Else
    *object\current = *object\last
    *object\index   = *object\size - 1
    While *object\index > index
     *object\current = *object\current\before
     *object\index   - 1
    Wend
   EndIf
  Else
   If (*object\size - 1) - index < index - *object\index
    *object\current = *object\last
    *object\index   = *object\size - 1
    While *object\index > index
     *object\current = *object\current\before
     *object\index   - 1
    Wend
   Else
    While *object\index < index
     *object\current = *object\current\after
     *object\index   + 1
    Wend
   EndIf
  EndIf
 EndIf
 ProcedureReturn *this\currentE()
EndProcedure


Procedure.i DoublyLinkedList_size(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn 0
 EndIf
 *object = *this
 ProcedureReturn *object\size
EndProcedure


Procedure DoublyLinkedList_reset(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList
 If *this = #Null
  ProcedureReturn
 EndIf
 *object = *this
 *object\current = #Null
 *object\index   = -1
EndProcedure


Procedure DoublyLinkedList_clear(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList, *nextElement.EDoubleLinkedList
 If *this = #Null
  ProcedureReturn
 EndIf
 *object = *this
 If *object\size = 0
  ProcedureReturn
 EndIf
 *object\current = *object\first
 While *object\current <> #Null
  *nextElement    = *object\current\after
  FreeMemory(*object\current)
  *object\current = *nextElement
 Wend
 *object\first   = #Null
 *object\last    = #Null
 *object\current = #Null
 *object\index   = -1
 *object\size    = 0
EndProcedure


Procedure.i DoublyLinkedList_mergeSort(*this.IDoublyLinkedList, compare.CompareFunction, options.i)
 Protected *object.ODoublyLinkedList
 Protected left.i, right.i, start.i, sortLen.i, length.i, dir.i
 Protected posL.i, posR.i, posM.i
 If *this = #Null Or compare = #Null
  ProcedureReturn #False
 EndIf
 *object = *this
 If *object\size < 2
  *object\current =  #Null
  *object\index   = -1
  ProcedureReturn #True
 EndIf
 Dim *hArray.EDoubleLinkedList(1, *object\size - 1)
 *object\current = *object\first
 index.i = 0
 While *object\current <> #Null
  *hArray(0, index) = *object\current
  *object\current = *object\current\after
  index + 1
 Wend
 ;sort here >>
 left    = 1
 right   = 1
 start   = 0
 sortLen = 1
 length  = *object\size
 dir     = 1
 While left <= length
  sortLen << 1
  start = 0
  While start < length
   If (length - start) < sortLen
    If (length - start) > (sortLen >> 1)
     left = sortLen >> 1
     right = length - start - left
    Else
     left = length - start
     right = 0
    EndIf
   EndIf
   posL = start
   posR = start + left
   posM = start
   While (posL < (start + left)) And (posR < (start + left + right))
    If compare(*hArray(dir ! 1, posL) + SizeOf(EDoubleLinkedList), *hArray(dir ! 1, posR) + SizeOf(EDoubleLinkedList), options) <= 0
     *hArray(dir, posM) = *hArray(dir ! 1, posL)
     posL + 1
    Else
     *hArray(dir, posM) = *hArray(dir ! 1, posR)
     posR + 1
    EndIf
    posM + 1
   Wend
   While (posL < (start + left))
    *hArray(dir, posM) = *hArray(dir ! 1, posL)
    posL + 1
    posM + 1
   Wend
   While (posR < (start + left + right))
    *hArray(dir, posM) = *hArray(dir ! 1, posR)
    posR + 1
    posM + 1
   Wend
   start = start + sortLen
  Wend
  dir = dir ! 1
  left  = sortLen
  right = sortLen
 Wend
 ;sort here <<
 dir = dir ! 1
 For index = 0 To *object\size - 1
  If index = 0
   *hArray(dir, index)\before = #Null
  Else
   *hArray(dir, index)\before = *hArray(dir, index - 1)
  EndIf
  If index = *object\size - 1
   *hArray(dir, index)\after = #Null
  Else
   *hArray(dir, index)\after = *hArray(dir, index + 1)
  EndIf
 Next
 *object\first = *hArray(dir, 0)
 *object\last = *hArray(dir, *object\size - 1)
 ReDim *hArray(1, 0)
 *object\current =  #Null
 *object\index   = -1
 ProcedureReturn #True
EndProcedure


Procedure DoublyLinkedList_delete(*this.IDoublyLinkedList)
 Protected *object.ODoublyLinkedList, *nextElement.EDoubleLinkedList
 If *this = #Null
  ProcedureReturn
 EndIf
 *object = *this
 If *object\size <> 0
  *object\current = *object\first
  While *object\current <> #Null
   *nextElement    = *object\current\after
   FreeMemory(*object\current)
   *object\current = *nextElement
  Wend
 EndIf
 FreeMemory(*object)
EndProcedure



;##################################################################################################
Debug "##########"
o.IDoublyLinkedList = newDoublyLinkedList(SizeOf(LONG))

*e.LONG
For i = 0 To 10
 *e = o\addE()
 *e\l = Random(100)
Next

Debug o\size()

Debug "--"
o\reset()
While o\nextE()
 *e = o\currentE()
 Debug *e\l
Wend

Debug "--"
o\selectE(5)
*e = o\currentE()
Debug *e\l

Debug "--"
o\deleteE()
*e = o\currentE()
Debug *e\l

Debug "======="
Procedure.i compareLongs(*a.LONG, *b.LONG, options.i)
 If options & #PB_Sort_Descending
  If *a\l > *b\l
   ProcedureReturn -1
  ElseIf *a\l = *b\l
   ProcedureReturn 0
  Else
   ProcedureReturn 1
  EndIf
 Else
  If *a\l > *b\l
   ProcedureReturn 1
  ElseIf *a\l = *b\l
   ProcedureReturn 0
  Else
   ProcedureReturn -1
  EndIf
 EndIf
EndProcedure
o\sort(@compareLongs(), #PB_Sort_Ascending)
o\reset()
While o\nextE()
 *e = o\currentE()
 Debug *e\l
Wend

o\delete()

;##################################################################################################
Debug "##########"
o.IDoublyLinkedList = newDoublyLinkedList(SizeOf(INTEGER)) ;size of the string pointer

*s.STRING
For i = 0 To 10
 *s = o\addE()
 *s\s = "item " + Str(i)
Next

Debug o\size()

Debug "--"
o\reset()
While o\nextE()
 *s = o\currentE()
 Debug *s\s
Wend

Debug "--"
o\selectE(5)
*s = o\currentE()
Debug *s\s

Debug "--"
o\deleteE()
*s = o\currentE()
Debug *s\s

Debug "======="
Procedure.i compareStrings(*a.STRING, *b.STRING, options.i)
 If options & #PB_Sort_NoCase
  a$ = LCase(*a\s)
  b$ = LCase(*b\s)
 Else
  a$ = *a\s
  b$ = *b\s
 EndIf
 If options & #PB_Sort_Descending
  If a$ > b$
   ProcedureReturn -1
  ElseIf a$ = b$
   ProcedureReturn 0
  Else
   ProcedureReturn 1
  EndIf
 Else
  If a$ > b$
   ProcedureReturn 1
  ElseIf a$ = b$
   ProcedureReturn 0
  Else
   ProcedureReturn -1
  EndIf
 EndIf
EndProcedure
o\sort(@compareStrings(), #PB_Sort_Descending)
o\reset()
While o\nextE()
 *s = o\currentE()
 Debug *s\s
Wend

o\delete()

PS: sort method can be exchanged on runtime

Edit: forgot the reset the size on clear()

Edit: fixed bug in insertE()

Post by **idle** » Tue Feb 03, 2009 8:44 pm

Looks good pcfreak.

Mistrel · Post by **Mistrel** » Tue Feb 03, 2009 9:25 pm

Here is a generic method I wrote a while ago:

http://www.purebasic.fr/english/viewtopic.php?t=34139

pcfreak · Post by **pcfreak** » Tue Feb 03, 2009 11:07 pm

well, i posted a generic one last year too, but i thought it was easier to handle with oop..

http://www.purebasic.fr/english/viewtopic.php?t=33417

Deeem2031 · Post by **Deeem2031** » Wed Mar 25, 2009 1:20 am

There seems to be a problem with insertE():

Code: Select all

*x.IDoublyLinkedList = newDoublyLinkedList(SizeOf(long))
*xe.long = *x\adde()
*xe\l = 1
*xe.long = *x\adde()
*xe\l = 3
*xe.long = *x\inserte()
*xe\l = 2

*x\reset()
While *x\nextE()
  *xe.long = *x\currente()
  Debug *xe\l
Wend

Debug "---"

NewList y.l()
AddElement(y())
y() = 1
AddElement(y())
y() = 3
InsertElement(y())
y() = 2

ForEach y()
  Debug y()
Next

[EDIT]

I guess line 89

Code: Select all

  If *object\current = *object\first Or *object\current\before = *object\first

should be

Code: Select all

  If *object\current = *object\first

because if the current element is the second one in the list insertE shouldn't add the element at the first position.

SFSxOI · Post by **SFSxOI** » Wed Mar 25, 2009 1:21 pm

should that not be this instead?

Code: Select all


If (*object\current = *object\first) Or (*object\current\before = *object\first)

Deeem2031 · Post by **Deeem2031** » Wed Mar 25, 2009 2:53 pm

SFSxOI wrote:should that not be this instead?
Code: Select all
If (*object\current = *object\first) Or (*object\current\before = *object\first)

How should that solve the problem? I don't see any difference between your code and the original except the brackets, which don't change the behavior of that line.

SFSxOI · Post by **SFSxOI** » Wed Mar 25, 2009 4:45 pm

I didn't say it would solve the problem, I was just asking if it should be like that.

kinglestat · Post by **kinglestat** » Sat Mar 28, 2009 2:40 pm

thanks for this
I love linked lists
I assume they can be used inside structures too?
and
with structures rather than simple types?
an example would be nice
cheers