Share your advanced PureBasic knowledge/code with the community.
StarBootics
Addict
Posts: 984 Joined: Sun Jul 07, 2013 11:35 am
Location: Canada
Post
by StarBootics » Wed Jun 09, 2021 9:08 pm
Before I start, I want to clarify something : YES A QUEUE DATA STRUCTURE CAN BE DONE WITH STANDARD PB LINKED LIST.
There a prototype of a Queue data structure implementation. See the source code for the YouTube link about where the inspiration came from.
Best regards
StarBootics
Code: Select all
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : Data Structure - Queue
; File Name : Queue - OOP.pb
; File version: 1.0.0
; Programming : Prototype
; Programmed by : StarBootics
; Date : June 9th, 2021
; Last Update : June 9th, 2021
; PureBasic code : V5.73 LTS
; Platform : Windows, Linux, MacOS X
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Based on the code presented by the YouTube channel
;
; https://www.youtube.com/channel/UC8butISFwT-Wl7EV0hUK0BQ
; Video link : https://www.youtube.com/watch?v=B31LgI4Y4DQ
; Video name : Data Structures - Full Course Using C And C++
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
DeclareModule Queue
Interface Queue
Enqueue(Value.l)
Dequeue()
Front.l()
IsEmpty.b()
Free()
EndInterface
Declare.i New()
EndDeclareModule
Module Queue
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Structures declaration <<<<<
Structure Node
Value.l
*Link.Node
EndStructure
Structure Private_Members
VirtualTable.i
*Front.Node
*Rear.Node
EndStructure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Enqueue operator <<<<<
Procedure Enqueue(*This.Private_Members, Value.l)
*Temp.Node = AllocateStructure(Node)
*Temp\Value = Value
*Temp\Link = #Null
If *This\Front = #Null And *This\Rear = #Null
*This\Front = *Temp
*This\Rear = *Temp
ProcedureReturn 0
EndIf
*This\Rear\Link = *Temp
*This\Rear = *Temp
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Dequeue operator <<<<<
Procedure Dequeue(*This.Private_Members)
*Temp.Node = *This\Front
If *This\Front = #Null
; MessageRequester("Queue Error", "The Queue is already Empty !")
ProcedureReturn 0
EndIf
If *This\Front = *This\Rear
*This\Front = #Null
*This\Rear = #Null
Else
*This\Front = *This\Front\Link
EndIf
FreeStructure(*Temp)
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Front operator <<<<<
Procedure.l Front(*This.Private_Members)
If *This\Front <> #Null
ProcedureReturn *This\Front\Value
Else
MessageRequester("Queue Error", "The Queue is Empty !")
EndIf
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The IsEmpty operator <<<<<
Procedure.b IsEmpty(*This.Private_Members)
If *This\Front = #Null
ProcedureReturn #True
Else
ProcedureReturn #False
EndIf
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Destructor <<<<<
Procedure Free(*This.Private_Members)
While IsEmpty(*This) <> #True
Dequeue(*This)
Wend
FreeStructure(*This)
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Constructor <<<<<
Procedure.i New()
*This.Private_Members = AllocateStructure(Private_Members)
*This\VirtualTable = ?START_METHODS
*This\Front = #Null
*This\Rear = #Null
ProcedureReturn *This
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The VirtualTable entries <<<<<
DataSection
START_METHODS:
Data.i @Enqueue()
Data.i @Dequeue()
Data.i @Front()
Data.i @IsEmpty()
Data.i @Free()
END_METHODS:
EndDataSection
EndModule
CompilerIf #PB_Compiler_IsMainFile
MyQueue.Queue::Queue = Queue::New()
MyQueue\Enqueue(25)
MyQueue\Enqueue(35)
MyQueue\Enqueue(15)
MyQueue\Enqueue(45)
While MyQueue\IsEmpty() <> #True
Debug MyQueue\Front()
MyQueue\Dequeue()
Wend
MyQueue\Free()
CompilerEndIf
; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<
The Stone Age did not end due to a shortage of stones !
StarBootics
Addict
Posts: 984 Joined: Sun Jul 07, 2013 11:35 am
Location: Canada
Post
by StarBootics » Thu Jun 10, 2021 4:43 am
Hello everyone,
This is the version 2.0.0 of a Queue data structure specifically design to hold element of different type in this case Allocated Structures but it can be object created with Dev-Object.
If the Queue contain identical objects created with Dev-Object for example you have to specify the address of the destructor in the Queue constructor. If the Queue contain different objects you have to specify the address of the destructor when you Enqueue element in the Queue. If the destructor are not specified the Dequeue method will consider a simple FreeStructure is safe to do.
Best regards
StarBootics
Code: Select all
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : Data Structure - Queue
; File Name : Queue - OOP.pb
; File version: 2.0.0
; Programming : OK
; Programmed by : StarBootics
; Date : June 9th, 2021
; Last Update : June 9th, 2021
; PureBasic code : V5.73 LTS
; Platform : Windows, Linux, MacOS X
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
DeclareModule Queue
Interface Queue
Enqueue(Tag.l, *ObjectPtr, *ObjectDestructor = #Null)
Dequeue()
FrontTag.l()
FrontObjectPtr.i()
IsEmpty.b()
Free()
EndInterface
Declare.i New(*ObjectDestructor = #Null)
EndDeclareModule
Module Queue
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Structures declaration <<<<<
Structure Node
Tag.l
ObjectPtr.i
ObjectDestructor.i
*Link.Node
EndStructure
Structure Private_Members
VirtualTable.i
ObjectDestructor.i
*Front.Node
*Rear.Node
EndStructure
Prototype DestructorFunction(*ObjectPtr)
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Enqueue operator <<<<<
Procedure Enqueue(*This.Private_Members, Tag.l, *ObjectPtr, *ObjectDestructor = #Null)
*Temp.Node = AllocateStructure(Node)
*Temp\Tag = Tag
*Temp\ObjectPtr = *ObjectPtr
*Temp\ObjectDestructor = *ObjectDestructor
*Temp\Link = #Null
If *This\Front = #Null And *This\Rear = #Null
*This\Front = *Temp
*This\Rear = *Temp
ProcedureReturn 0
EndIf
*This\Rear\Link = *Temp
*This\Rear = *Temp
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Dequeue operator <<<<<
Procedure Dequeue(*This.Private_Members)
*Temp.Node = *This\Front
If *This\Front = #Null
; MessageRequester("Queue Error", "The Queue is already Empty !")
ProcedureReturn 0
EndIf
If *This\Front = *This\Rear
*This\Front = #Null
*This\Rear = #Null
Else
*This\Front = *This\Front\Link
EndIf
If *Temp\ObjectDestructor <> #Null
Destructor.DestructorFunction = *Temp\ObjectDestructor
Destructor(*Temp\ObjectPtr)
ElseIf *This\ObjectDestructor <> #Null
Destructor.DestructorFunction = *This\ObjectDestructor
Destructor(*Temp\ObjectPtr)
Else
FreeStructure(*Temp\ObjectPtr)
EndIf
FreeStructure(*Temp)
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The FrontTag operator <<<<<
Procedure.l FrontTag(*This.Private_Members)
If *This\Front <> #Null
ProcedureReturn *This\Front\Tag
Else
MessageRequester("Queue Error", "The Queue is Empty !")
EndIf
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The FrontObjectPtr operator <<<<<
Procedure.i FrontObjectPtr(*This.Private_Members)
If *This\Front <> #Null
ProcedureReturn *This\Front\ObjectPtr
Else
MessageRequester("Queue Error", "The Queue is Empty !")
EndIf
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The IsEmpty operator <<<<<
Procedure.b IsEmpty(*This.Private_Members)
If *This\Front = #Null
ProcedureReturn #True
Else
ProcedureReturn #False
EndIf
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Destructor <<<<<
Procedure Free(*This.Private_Members)
While IsEmpty(*This) <> #True
Dequeue(*This)
Wend
FreeStructure(*This)
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Constructor <<<<<
Procedure.i New(*ObjectDestructor = #Null)
*This.Private_Members = AllocateStructure(Private_Members)
*This\VirtualTable = ?START_METHODS
*This\Front = #Null
*This\Rear = #Null
*This\ObjectDestructor = *ObjectDestructor
ProcedureReturn *This
EndProcedure
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The Virtual table entries <<<<<
DataSection
START_METHODS:
Data.i @Enqueue()
Data.i @Dequeue()
Data.i @FrontTag()
Data.i @FrontObjectPtr()
Data.i @IsEmpty()
Data.i @Free()
END_METHODS:
EndDataSection
EndModule
CompilerIf #PB_Compiler_IsMainFile
Enumeration
#TAG_DODECAHEDRON
#TAG_SPHERE
#TAG_CUBE
#TAG_PYRAMID
EndEnumeration
Structure Dodecahedron
Volume.d
Size.d
Whatever.s
EndStructure
Structure Sphere
Volume.d
Radius.d
Whatever.s
EndStructure
Structure Cube
Volume.d
Size.d
Whatever.s
EndStructure
Structure Pyramid
Volume.d
Size.d
Whatever.s
EndStructure
MyQueue.Queue::Queue = Queue::New(#Null)
MyQueue\Enqueue(#TAG_PYRAMID, AllocateStructure(Pyramid), #Null)
MyQueue\Enqueue(#TAG_SPHERE, AllocateStructure(Sphere), #Null)
MyQueue\Enqueue(#TAG_CUBE, AllocateStructure(Cube), #Null)
MyQueue\Enqueue(#TAG_SPHERE, AllocateStructure(Sphere), #Null)
MyQueue\Enqueue(#TAG_DODECAHEDRON, AllocateStructure(Dodecahedron), #Null)
MyQueue\Enqueue(#TAG_PYRAMID, AllocateStructure(Pyramid), #Null)
While MyQueue\IsEmpty() <> #True
Select MyQueue\FrontTag()
Case #TAG_DODECAHEDRON
*Dodecahedron.Dodecahedron = MyQueue\FrontObjectPtr()
Debug "In the queue there is a Dodecahedron"
Case #TAG_SPHERE
*Sphere.Sphere = MyQueue\FrontObjectPtr()
Debug "In the queue there is a Sphere"
Case #TAG_CUBE
*Cube.Cube = MyQueue\FrontObjectPtr()
Debug "In the queue there is a Cube"
Case #TAG_PYRAMID
*Pyramid.Pyramid = MyQueue\FrontObjectPtr()
Debug "In the queue there is a Pyramid"
EndSelect
MyQueue\Dequeue()
Wend
MyQueue\Free()
CompilerEndIf
; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<
The Stone Age did not end due to a shortage of stones !