Selbstprogrammierte LinkedList

Andre · Beitrag von **Andre** » 27.11.2004 03:01

IceSoft hat geschrieben:
IceSoft hat geschrieben:...Geht es Dir aber eher um das dynamische Anlegen einer LinkedList (oder Array) dann denke ich, das das noch ein (wichtiges) fehlendes Feature in PureBasic ist. Es geht hier doch nur darum, das die aktuelle LinkedList auch mit 'PointerVariabeln' klarkommt, "mehr" denke ich, ist es eigentlich nicht.
Hallo @Andre,
was meint eigentlich @Fred zu dieser Behauptung?

Gute Frage....

Werde ihn bei Gelegenheit mal "interviewen".

DrShrek · Beitrag von **DrShrek** » 16.02.2005 09:01

Hallo Andre
Was ist aus dem Interview geworden?

ShadowTurtle · Beitrag von **ShadowTurtle** » 18.02.2005 14:25

Moin.

Ich hab mich mal am selbigen versucht. Bin aber auf 120 Zeilen (Nur library, sample hat mehr) gekommen. Wer eine schlanke Library will, der kann ja mal da vorbei schauen: http://robsite.de/php/pureboard/viewtopic.php?t=2116

cu

Andre · Beitrag von **Andre** » 19.02.2005 20:36

@IceSoft: Interview nicht, aber ich habe nochmal per Mail nachgefragt.

Spirit · Beitrag von **Spirit** » 13.04.2005 19:43

Ich habe mir auch eine eigene LinkedList geschrieben. Sie hat ebenfalls den Vorteil, das sie wähend des Programmablaufs dynamisch erstellt werden kann. Außerdem habe ich alles in ein Interface gepackt, um die ganze Sache etwas übersichtlicher zu machen.

Code: Alles auswählen

;/LinkedList v1.0

;{- Strukturen

Structure ListItem
  *NextItem.ListItem
  *PrevItem.ListItem
EndStructure

;}-
;{- Objekt

Interface List
  AddItem()
  ChangeItem(Item)
  Clear()
  CountItems()
  DeleteItem()
  FirstItem()
  Index()
  Item()
  LastItem()
  NextItem()
  PreviousItem()
  Reset()
  SelectItem(Index)
EndInterface

Structure ListFunctions
  Adr.l[SizeOf(List)/4]
EndStructure

Structure ListObject
  *VTable.ListFunctions
  BSize.l
  Items.l
  Index.l
  *Current.ListItem
  *First.ListItem
  *Last.ListItem
EndStructure

;}-
;{- Declares

Declare.l AddItem(*Object.ListObject)
Declare   ChangeItem(*Object.ListObject, Item)
Declare   Clear(*Object.ListObject)
Declare.l CountItems(*Object.ListObject)
Declare   DeleteItem(*Object.ListObject)
Declare.l FirstItem(*Object.ListObject)
Declare.l Index(*Object.ListObject)
Declare.l Item(*Object.ListObject)
Declare.l LastItem(*Object.ListObject)
Declare.l NextItem(*Object.ListObject)
Declare.l PreviousItem(*Object.ListObject)
Declare   Reset(*Object.ListObject)
Declare   SelectItem(*Object.ListObject, Index)

;}-
;{- Konstruktor/Destruktor

Procedure.l CreateList(BlockSize)
  *Functions.ListFunctions=AllocateMemory(SizeOf(List))
  *Functions\Adr[p]       =@AddItem()      : p+1
  *Functions\Adr[p]       =@ChangeItem()   : p+1
  *Functions\Adr[p]       =@Clear()        : p+1
  *Functions\Adr[p]       =@CountItems()   : p+1
  *Functions\Adr[p]       =@DeleteItem()   : p+1
  *Functions\Adr[p]       =@FirstItem()    : p+1
  *Functions\Adr[p]       =@Index()        : p+1
  *Functions\Adr[p]       =@Item()         : p+1
  *Functions\Adr[p]       =@LastItem()     : p+1
  *Functions\Adr[p]       =@NextItem()     : p+1
  *Functions\Adr[p]       =@PreviousItem() : p+1
  *Functions\Adr[p]       =@Reset()        : p+1
  *Functions\Adr[p]       =@SelectItem()
  
  *Object.ListObject      =AllocateMemory(SizeOf(ListObject))
  *Object\VTable          =*Functions
  *Object\BSize           =BlockSize
  *Object\Index           =-1
  
  ProcedureReturn *Object
EndProcedure

Procedure FreeList(*Object.ListObject)
  FreeMemory(*Object\VTable)
  FreeMemory(*Object)
EndProcedure

;}-
;{- Methoden

Procedure.l AddItem(*Object.ListObject)
  DefType.ListItem *Item, *NextItem
  
  *Item.ListItem=AllocateMemory(SizeOf(ListItem)+*Object\BSize)
  If *Item
    
    If *Object\Items
      If *Object\Current=0 : *Object\Current=*Object\First : EndIf
      
      *Item\PrevItem          =*Object\Current
      *NextItem               =*Object\Current\NextItem
      If *NextItem
        *NextItem\PrevItem    =*Item
        *Item\NextItem        =*NextItem
      Else
        *Object\Last          =*Item
      EndIf
      *Object\Current\NextItem=*Item
    Else
      *Object\First=*Item
    EndIf
    
    *Object\Items+1
    *Object\Index+1
    *Object\Current=*Item
    
    ProcedureReturn *Item
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

Procedure ChangeItem(*Object.ListObject, Item)
  *Object\Current=*Object\First
  *Object\Index  =0
  
  While *Object\Current<>Item-SizeOf(ListItem) And *Object\Current
    *Object\Current=*Object\Current\NextItem
    *Object\Index+1
  Wend
EndProcedure

Procedure Clear(*Object.ListObject)
  DefType.ListItem *NextItem
  
  If *Object\Items
    *Object\Current=*Object\First
    
    Repeat
      *NextItem=*Object\Current\NextItem
      FreeMemory(*Object\Current)
      *Object\Current=*NextItem
    Until *Object\Current=0
    
    *Object\Items=0
    *Object\Index=-1 
  EndIf
  
EndProcedure

Procedure.l CountItems(*Object.ListObject)
  ProcedureReturn *Object\Items
EndProcedure

Procedure DeleteItem(*Object.ListObject)
  DefType.ListItem *Item
  
  If *Object\Current
    
    *Item=*Object\Current\NextItem
    If *Item : *Item\PrevItem=*Object\Current\PrevItem : EndIf
    *Item=*Object\Current\PrevItem
    If *Item : *Item\NextItem=*Object\Current\NextItem : EndIf
    
    FreeMemory(*Object\Current)
    
    *Object\Current=*Item
    *Object\Index-1
    *Object\Items-1
    
  EndIf
EndProcedure

Procedure.l FirstItem(*Object.ListObject)
  *Object\Current=*Object\First
  *Object\Index  =0
  ProcedureReturn *Object\Current
EndProcedure

Procedure.l Index(*Object.ListObject)
  ProcedureReturn *Object\Index
EndProcedure

Procedure.l Item(*Object.ListObject)
  ProcedureReturn *Object\Current+SizeOf(ListItem)
EndProcedure

Procedure.l LastItem(*Object.ListObject)
  *Object\Current=*Object\Last
  *Object\Index  =*Object\Items-1
  ProcedureReturn *Object\Current
EndProcedure

Procedure.l NextItem(*Object.ListObject)
  DefType.ListItem *NextItem
  
  If *Object\Current
    *NextItem=*Object\Current\NextItem
  ElseIf *Object\Items
    *NextItem=*Object\First
  EndIf
  
  If *NextItem : *Object\Current=*NextItem : *Object\Index+1 : EndIf
  
  ProcedureReturn *NextItem
EndProcedure

Procedure.l PreviousItem(*Object.ListObject)
  DefType.ListItem *PrevItem
  
  If *Object\Current
    *PrevItem=*Object\Current\PrevItem
    If *PrevItem : *Object\Current=*PrevItem : *Object\Index-1 : EndIf
  EndIf
  
  ProcedureReturn *PrevItem
EndProcedure

Procedure Reset(*Object.ListObject)
  *Object\Current=0
  *Object\Index  =-1
EndProcedure

Procedure SelectItem(*Object.ListObject, Index)
  If *Object\Items-1>=Index
    *Object\Current=*Object\First
    
    While p<Index
      *Object\Current=*Object\Current\NextItem : p+1
    Wend
    
    *Object\Index=Index
    
  EndIf
EndProcedure

;}-

Und zum Abschluss ein kleines Beispiel:

Code: Alles auswählen

MyList.List=CreateList(4) ;4 Byte für eine Long Variable reservieren

*Item.LONG

For p=0 to 10
  MyList\AddItem()
  *Item=MyList\Item()
  *Item\l=p
Next

Debug MyList\CountItems()

MyList\Reset()

While MyList\NextItem()
  *Item=MyList\Item()
  Debug *Item\l
Wend

MyList\Clear()
FreeList(MyList)

ShadowTurtle · Beitrag von **ShadowTurtle** » 14.04.2005 02:04

Cool. Arbeitet ja fast nach dem gleichen schema wie meine Routinen. Ich glaube ich werde bei gelegenheit unsere Codes beim PureArea Codearchiv einsenden.

[Natürlich ist dies bei dir nur möglich, so fern du das noch nicht selbst getan hast.

]

Spirit · Beitrag von **Spirit** » 14.04.2005 19:53

ShadowTurtle hat geschrieben:Ich glaube ich werde bei gelegenheit unsere Codes beim PureArea Codearchiv einsenden.

[Natürlich ist dies bei dir nur möglich, so fern du das noch nicht selbst getan hast. ]

Ich habe meinen Code noch nicht eingesendet und es wäre schön, wenn du das übernehmen könntest (meine Internetverbindung ist ziemlich lahm

).

Andre · Beitrag von **Andre** » 17.04.2005 19:13

BlueSpirit hat geschrieben:Ich habe meinen Code noch nicht eingesendet und es wäre schön, wenn du das übernehmen könntest (meine Internetverbindung ist ziemlich lahm ).

Nicht mehr nötig, der ist von mir schon vorgemerkt...

Spirit · Beitrag von **Spirit** » 05.05.2005 13:59

Ich habe meine LinkedList ein wenig verbessert:

Repariert: DeleteItem() - wenn das erste oder letzte Item gelöscht wurde, funktionierten FirstItem() und LastItem() nicht mehr
Optimiert: Die VirtualTable wird jetzt nur noch einmal erzeugt und nicht für jede neue Liste.
Hinzugefügt: SwapItems()

Code: Alles auswählen

;/LinkedList v1.24 by BlueSpirit

;{- Strukturen

Structure ListItem
  *NextItem.ListItem
  *PrevItem.ListItem
EndStructure

;}-
;{- Objekt

Interface List
  AddItem()
  ChangeItem(Item)
  Clear()
  CountItems()
  DeleteItem()
  FirstItem()
  Index()
  Item()
  LastItem()
  NextItem()
  PreviousItem()
  Reset()
  SelectItem(index)
  SwapItems(Item1, Item2) 
EndInterface

Structure ListFunctions
  Adr.l[SizeOf(List)/4]
EndStructure

Structure ListObject
  *VTable.ListFunctions
  BSize.l
  Items.l
  index.l
  *Current.ListItem
  *First.ListItem
  *Last.ListItem
EndStructure

;}-
;{- Variablen

Global *LL_VTable.ListFunctions

;}-
;{- Declares

Declare.l AddItem(*Object.ListObject)
Declare   ChangeItem(*Object.ListObject, Item)
Declare   Clear(*Object.ListObject)
Declare.l CountItems(*Object.ListObject)
Declare   DeleteItem(*Object.ListObject)
Declare.l FirstItem(*Object.ListObject)
Declare.l Index(*Object.ListObject)
Declare.l Item(*Object.ListObject)
Declare.l LastItem(*Object.ListObject)
Declare.l NextItem(*Object.ListObject)
Declare.l PreviousItem(*Object.ListObject)
Declare   Reset(*Object.ListObject)
Declare   SelectItem(*Object.ListObject, index)
Declare   SwapItems(*Object.ListObject, Item1, Item2)

;}-
;{- Initialisierung, Konstruktor/Destruktor

Procedure InitLinkedList()
  *LL_VTable.ListFunctions=AllocateMemory(SizeOf(List))
  *LL_VTable\Adr[p]       =@AddItem()      : p+1
  *LL_VTable\Adr[p]       =@ChangeItem()   : p+1
  *LL_VTable\Adr[p]       =@Clear()        : p+1
  *LL_VTable\Adr[p]       =@CountItems()   : p+1
  *LL_VTable\Adr[p]       =@DeleteItem()   : p+1
  *LL_VTable\Adr[p]       =@FirstItem()    : p+1
  *LL_VTable\Adr[p]       =@Index()        : p+1
  *LL_VTable\Adr[p]       =@Item()         : p+1
  *LL_VTable\Adr[p]       =@LastItem()     : p+1
  *LL_VTable\Adr[p]       =@NextItem()     : p+1
  *LL_VTable\Adr[p]       =@PreviousItem() : p+1
  *LL_VTable\Adr[p]       =@Reset()        : p+1
  *LL_VTable\Adr[p]       =@SelectItem()   : p+1
  *LL_VTable\Adr[p]       =@SwapItems()
EndProcedure

Procedure.l CreateList(BlockSize)
  If *LL_VTable=0 : InitLinkedList() : EndIf
  
  *Object.ListObject      =AllocateMemory(SizeOf(ListObject))
  *Object\VTable          =*LL_VTable
  *Object\BSize           =BlockSize
  *Object\index           =-1
  
  ProcedureReturn *Object
EndProcedure

Procedure FreeList(*Object.ListObject)
  Clear(*Object)
  FreeMemory(*Object)
EndProcedure

;}-
;{- Methoden

Procedure.l AddItem(*Object.ListObject)
  DefType.ListItem *Item, *NextItem
  
  *Item.ListItem=AllocateMemory(SizeOf(ListItem)+*Object\BSize)
  If *Item
    
    If *Object\Items
      If *Object\Current=0 : *Object\Current=*Object\First : EndIf
      
      *Item\PrevItem          =*Object\Current
      *NextItem               =*Object\Current\NextItem
      If *NextItem
        *NextItem\PrevItem    =*Item
        *Item\NextItem        =*NextItem
      Else
        *Object\Last          =*Item
      EndIf
      *Object\Current\NextItem=*Item
    Else
      *Object\First=*Item
    EndIf
    
    *Object\Items+1
    *Object\index+1
    *Object\Current=*Item
    
    ProcedureReturn *Item
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

Procedure ChangeItem(*Object.ListObject, Item)
  *Object\Current=*Object\First
  *Object\index  =0
  
  While *Object\Current<>Item-SizeOf(ListItem) And *Object\Current
    *Object\Current=*Object\Current\NextItem
    *Object\index+1
  Wend
EndProcedure

Procedure Clear(*Object.ListObject)
  DefType.ListItem *NextItem
  
  If *Object\Items
    *Object\Current=*Object\First
    
    Repeat
      *NextItem=*Object\Current\NextItem
      FreeMemory(*Object\Current)
      *Object\Current=*NextItem
    Until *Object\Current=0
    
    *Object\Items=0
    *Object\index=-1 
  EndIf
  
EndProcedure

Procedure.l CountItems(*Object.ListObject)
  ProcedureReturn *Object\Items
EndProcedure

Procedure DeleteItem(*Object.ListObject)
  DefType.ListItem *Item
  
  If *Object\Current
    
    *Item=*Object\Current\NextItem
    If *Item : *Item\PrevItem=*Object\Current\PrevItem : Else : *Object\Last =*Object\Current\PrevItem : EndIf
    *Item=*Object\Current\PrevItem
    If *Item : *Item\NextItem=*Object\Current\NextItem : Else : *Object\First=*Object\Current\NextItem : EndIf
    
    FreeMemory(*Object\Current)
    
    *Object\Current=*Item
    *Object\index-1
    *Object\Items-1
    
    ;Last Item/First Item neu auswählen
    
  EndIf
EndProcedure

Procedure.l FirstItem(*Object.ListObject)
  *Object\Current=*Object\First
  *Object\index  =0
  ProcedureReturn *Object\Current
EndProcedure

Procedure.l Index(*Object.ListObject)
  ProcedureReturn *Object\index
EndProcedure

Procedure.l Item(*Object.ListObject)
  ProcedureReturn *Object\Current+SizeOf(ListItem)
EndProcedure

Procedure.l LastItem(*Object.ListObject)
  *Object\Current=*Object\Last
  *Object\index  =*Object\Items-1
  ProcedureReturn *Object\Current
EndProcedure

Procedure.l NextItem(*Object.ListObject)
  DefType.ListItem *NextItem
  
  If *Object\Current
    *NextItem=*Object\Current\NextItem
  ElseIf *Object\Items
    *NextItem=*Object\First
  EndIf
  
  If *NextItem : *Object\Current=*NextItem : *Object\index+1 : EndIf
  
  ProcedureReturn *NextItem
EndProcedure

Procedure.l PreviousItem(*Object.ListObject)
  DefType.ListItem *PrevItem
  
  If *Object\Current
    *PrevItem=*Object\Current\PrevItem
    If *PrevItem : *Object\Current=*PrevItem : *Object\index-1 : EndIf
  EndIf
  
  ProcedureReturn *PrevItem
EndProcedure

Procedure Reset(*Object.ListObject)
  *Object\Current=0
  *Object\index  =-1
EndProcedure

Procedure SelectItem(*Object.ListObject, index)
  If *Object\Items-1>=index
    *Object\Current=*Object\First
    
    While p<index
      *Object\Current=*Object\Current\NextItem : p+1
    Wend
    
    *Object\index=index
    
  EndIf
EndProcedure

Procedure SwapItems(*Object.ListObject, Item1, Item2)
  ItemT=AllocateMemory(*Object\BSize)
  
  CopyMemory(Item1, ItemT, *Object\BSize)
  CopyMemory(Item2, Item1, *Object\BSize)
  CopyMemory(ItemT, Item2, *Object\BSize)
  
  FreeMemory(ItemT)
EndProcedure

;}-

MVXA · Beitrag von **MVXA** » 05.05.2005 14:23

Wie wäre es, wenn du deine Linkedlist zu einer Userlib kompilierst

.

PureBoard

Selbstprogrammierte LinkedList

Update