Any suggestions on the best way to set up a linked list?

New to FreeBASIC? Post your questions here.
dodicat
Posts: 6765
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Any suggestions on the best way to set up a linked list?

Postby dodicat » Jun 20, 2020 9:34

Simple list based on storage files.

Code: Select all


#include "file.bi"
Sub loadfile(file As String,p() As zstring * 100)
   If Fileexists(file)=0 Then Print file;" not found":Sleep:End
    Var  f=Freefile
    Open file For Binary Access Read As #f
    If Lof(f) > 0 Then
        Get #f, ,p()
    End If
    Close #f
End Sub

Sub savefile(filename As String,p() As zString * 100 )
    Dim As Integer n=Freefile
    If Open (filename For Binary Access Write As #n)=0 Then
        Put #n,,p()
        Close
    Else
        Print "Unable to save " + filename
    End If
End Sub


#define pushtop(a) ubound(a)+1
#define poptop(a) ubound(a)
#define bottom(a) lbound(a)

#macro push(a,index,insert)
If (index)>=Lbound(a) And (index)<=Ubound(a)+1 Then
    Var index2=(index)-Lbound(a)
    Redim Preserve a(Lbound(a) To  Ubound(a)+1)
    For x As long= Ubound(a) To Lbound(a)+index2+1 Step -1
        Swap a(x),a(x-1)
    Next x
    a(Lbound(a)+index2)=(insert)
End If
#endmacro

#macro pop(a,index)
If index>=Lbound(a) And (index)<=Ubound(a) Then
    For x As long=(index) To Ubound(a)-1
        a(x)=a(x+1)
    Next x
    Redim Preserve a(Lbound(a) To Ubound(a)-1)
End If
#endmacro

#define lim 2000 'limit of elements
Type tree
    Declare Constructor
    Declare Constructor(As long,As String)
    Private:
    Declare Sub build()
    Declare Sub revamp()
    Dim As long idx
    Dim As String   Name
    Static As tree mem(lim)'memory stack
    Static As Long inc     'memory increment
    Public:
    Dim As tree Ptr subtree(Any)
    Declare Sub create(As Long)
    Declare Sub remove(As Long)
    Declare Sub Add(As Long,As String)
    Declare Sub set(As long,As String)
    Declare Sub Print()
    Declare Function find Overload(As String) As long
    Declare Function find Overload(As long) As String
    Declare Sub save(filename As String)
    Declare Sub load(filename As String)
End Type 'activate the memory fields
Dim As tree tree.mem(lim)
Dim As Long tree.inc

Constructor tree
End Constructor

Constructor tree(i As long,g As String)
idx=i
Name=g
End Constructor

Sub tree.build()
    If tree.inc>lim Then tree.inc=0
    tree.inc+=1
    push(subtree,pushtop(subtree),@mem(tree.inc))
End Sub

Sub tree.revamp()
    For n As Long=Lbound(subtree) To Ubound(subtree)
        *(subtree(n)).idx=n
    Next n
End Sub

Sub tree.create(num As Long)
    For n As Long=1 To num
        build()
    Next
    Redim Preserve subtree(1 To num)
End Sub

Sub tree.remove(i As Long)
    pop(subtree,i)
    revamp()
End Sub

Sub tree.add(n As Long,g As String)
    If tree.inc>lim Then tree.inc=0
    tree.inc+=1
    push(subtree,n,@mem(tree.inc))
    *(subtree(n)).name=g
    revamp()
End Sub

Function tree.find(g As String) As long
    For n As Long=Lbound(subtree) To Ubound(subtree)
        If *(subtree(n)).name=g Then Return *(subtree(n)).idx
    Next
End Function

Function tree.find(g As long) As String
    For n As Long=Lbound(subtree) To Ubound(subtree)
        If *(subtree(n)).idx=g Then Return *(subtree(n)).name
    Next
End Function

Sub tree.print
    For n As Long=Lbound(subtree) To Ubound(subtree)
        ..print *(subtree(n)).idx,*(subtree(n)).name
    Next
End Sub

Sub tree.set(n As long,g As String)
    *(subtree(n))=Type<tree>(n,g)
    revamp
End Sub

Sub tree.save(filename As String)
    Redim As zstring * 100  a(Lbound(subtree) To Ubound(subtree))
    For n As Long=Lbound(subtree) To Ubound(subtree)
        a(n)=*(subtree(n)).name
    Next
    savefile(filename,a())
End Sub

Sub tree.load(filename As String)
    Var L=Filelen("listdata.txt")/Sizeof(zstring * 100)
    Dim As zstring * 100 b(1 To L)
    loadfile(filename,b())
    create(L)
    For n As Long=1 To L
        set(n,b(n))'set in values from file
    Next n
End Sub


'save some data to a file to start
Dim As zstring * 100 a(...)={"Peter","Paul","Mary","Henry","Peggy"}

savefile("listdata.txt",a())
Erase a

'============================================================
'START

Dim As tree x

x.load("listdata.txt")

Print
Print "data from file"
x.print

Print
Print "add ABC at position 2"
x.add(2,"ABC")
x.print
Print
Print "add DEF at position 4"
x.add(4,"DEF")
x.print
Print
Print "remove position 3"
x.remove(3)
x.print
Print

Print x.find(3);"  (value at position 3)"
Print x.find("ABC");"   (position of ABC)"
Print
Print "push to top On Top"
x.add(pushtop(x.subtree),"On Top")
x.print
Print
print "push to bottom START"
x.add(bottom(x.subtree),"START")

'save to disk
x.save("listdata.txt")
'check
Print
Print "Data saved to file"
Print "Check the disk"
Dim As tree test
test.load("listdata.txt")
test.print
print

Dim As tree bye
bye.create(1)
bye.set(1,"GoodBye!")
bye.print

Sleep
'kill "listdata.txt"

 

Remember to uncomment kill when you are done.
grindstone
Posts: 770
Joined: May 05, 2015 5:35
Location: Germany

Re: Any suggestions on the best way to set up a linked list?

Postby grindstone » Jun 20, 2020 11:40

The list doesn't necessarily have to be organized as a chain or a tree. Here an example of 6 rooms arranged in a 3-by-2 - grid:

Code: Select all

Enum
   N
   E
   S
   W
End Enum

Type tRoom
   Dim As tRoom Ptr door(3) 'contains the pointer of the room you get to if you walk through the door
   Dim As String text
   Dim As Integer number   
End Type

Dim As tRoom Ptr room(1 To 6)
Dim As Integer x, actualRoom

'create an array of 6 rooms
For x = LBound(room) To UBound(room)
   room(x) = New tRoom
   room(x)->number = x
Next

'initialize the rooms
room(1)->door(N) = room(3)
room(1)->door(E) = room(2)
room(1)->text = "You are in room 1. There's a door in the north and a door in the east"

room(2)->door(N) = room(4)
room(2)->door(W) = room(1)
room(2)->text = "You are in room 2. There's a door in the north and a door in the west"

room(3)->door(N) = room(5)
room(3)->door(E) = room(4)
room(3)->door(S) = room(1)
room(3)->text = "You are in room 3. There's a door in the north, a door in the south and a door in the east"

room(4)->door(N) = room(6)
room(4)->door(W) = room(3)
room(4)->door(S) = room(2)
room(4)->text = "You are in room 4. There's a door in the north, a door in the south and a door in the west"

room(5)->door(S) = room(3)
room(5)->door(E) = room(6)
room(5)->text = "You are in room 5. There's a door in the south and a door in the east"

room(6)->door(S) = room(4)
room(6)->door(W) = room(5)
room(6)->text = "You are in room 6. There's a door in the south and a door in the west"

'walk through the rooms
actualRoom = 1
Do
   Cls
   Print room(actualRoom)->text
   Do
      Select Case InKey
         Case "n"
            If room(actualRoom)->door(N) Then
               actualRoom = room(actualRoom)->door(N)->number
               Exit Do
            Else
               Print "You are running against the wall"
            EndIf
         Case "e"
            If room(actualRoom)->door(E) Then
               actualRoom = room(actualRoom)->door(E)->number
               Exit Do
            Else
               Print "You are running against the wall"
            EndIf
         Case "s"
            If room(actualRoom)->door(S) Then
               actualRoom = room(actualRoom)->door(S)->number
               Exit Do
            Else
               Print "You are running against the wall"
            EndIf
         Case "w"
            If room(actualRoom)->door(W) Then
               actualRoom = room(actualRoom)->door(W)->number
               Exit Do
            Else
               Print "You are running against the wall"
            EndIf
         Case Chr(27) 'esc
            Exit Do, Do
      End Select
      Sleep 1
   Loop
Loop

For x = LBound(room) To UBound(room)
   Delete room(x)
Next

You can link the rooms in any way you want. Thus you could also create one way doors or dimension gates like in Philip José Farmer's "The world of tiers".
dodicat
Posts: 6765
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Any suggestions on the best way to set up a linked list?

Postby dodicat » Jun 20, 2020 17:31

Nice grindstone.
I can adapt my own linked list for a similar array of rooms.

Code: Select all

 

#include "fbgfx.bi"
Const lngth=70
#include "file.bi"
Sub loadfile(file As String,p() As zstring * lngth)
   If Fileexists(file)=0 Then Print file;" not found":Sleep:End
    Var  f=Freefile
    Open file For Binary Access Read As #f
    If Lof(f) > 0 Then
        Get #f, ,p()
    End If
    Close #f
End Sub

Sub savefile(filename As String,p() As zString * lngth )
    Dim As Integer n=Freefile
    If Open (filename For Binary Access Write As #n)=0 Then
        Put #n,,p()
        Close
    Else
        Print "Unable to save " + filename
    End If
End Sub


#define pushtop(a) ubound(a)+1
#define poptop(a) ubound(a)
#define bottom(a) lbound(a)

#macro push(a,index,insert)
If (index)>=Lbound(a) And (index)<=Ubound(a)+1 Then
    Var index2=(index)-Lbound(a)
    Redim Preserve a(Lbound(a) To  Ubound(a)+1)
    For x As Long= Ubound(a) To Lbound(a)+index2+1 Step -1
        Swap a(x),a(x-1)
    Next x
    a(Lbound(a)+index2)=(insert)
End If
#endmacro

#macro pop(a,index)
If index>=Lbound(a) And (index)<=Ubound(a) Then
    For x As Long=(index) To Ubound(a)-1
        a(x)=a(x+1)
    Next x
    Redim Preserve a(Lbound(a) To Ubound(a)-1)
End If
#endmacro

#define lim 100 'limit of elements for this program
Type tree
    Private:
    Declare Sub build()
    Declare Sub revamp() 'reset idx
    Static As tree mem(lim)'memory stack
    Static As Long inc     'memory increment
    Public:
    Declare Constructor
    Declare Constructor(As Long,As String)
    Dim As Long idx
    Dim As String   Name
    Dim As tree Ptr subtree(Any)
    Declare Sub create(As Long)
    Declare Sub remove(As Long)
    Declare Sub Add(As Long,As String)
    Declare Sub set(As Long,As String)
    Declare Sub Print()
    Declare Function find Overload(As String) As Long
    Declare Function find Overload(As Long) As String
    Declare Sub save(filename As String)
    Declare Sub load(filename As String)
End Type 'activate the memory fields
Dim As tree tree.mem(lim)
Dim As Long tree.inc

Constructor tree
End Constructor

Constructor tree(i As Long,g As String)
idx=i
Name=g
End Constructor

Sub tree.build()
    If tree.inc>=lim Then tree.inc=0
    tree.inc+=1
    push(subtree,pushtop(subtree),@mem(tree.inc))
End Sub

Sub tree.revamp()
    For n As Long=Lbound(subtree) To Ubound(subtree)
        *(subtree(n)).idx=n
    Next n
End Sub

Sub tree.create(num As Long)
    For n As Long=1 To num
        build()
    Next
    Redim Preserve subtree(1 To num)
End Sub

Sub tree.remove(i As Long)
    pop(subtree,i)
    revamp()
End Sub

Sub tree.add(n As Long,g As String)
    If tree.inc>=lim Then tree.inc=0
    tree.inc+=1
    push(subtree,n,@mem(tree.inc))
    *(subtree(n)).name=g
    revamp()
End Sub

Function tree.find(g As String) As Long
    For n As Long=Lbound(subtree) To Ubound(subtree)
        If *(subtree(n)).name=g Then Return *(subtree(n)).idx
    Next
End Function

Function tree.find(g As Long) As String
    For n As Long=Lbound(subtree) To Ubound(subtree)
        If *(subtree(n)).idx=g Then Return *(subtree(n)).name
    Next
End Function

Sub tree.print
    For n As Long=Lbound(subtree) To Ubound(subtree)
        ..print *(subtree(n)).idx,*(subtree(n)).name
    Next
End Sub

Sub tree.set(n As Long,g As String)
    *(subtree(n))=Type<tree>(n,g)
    revamp
End Sub

Sub tree.save(filename As String)
    Redim As zstring * lngth  a(Lbound(subtree) To Ubound(subtree))
    For n As Long=Lbound(subtree) To Ubound(subtree)
        a(n)=*(subtree(n)).name
    Next
    savefile(filename,a())
End Sub

Sub tree.load(filename As String)
    Var L=Filelen(filename)/Sizeof(zstring * lngth)
    Dim As zstring * lngth b(1 To L)
    loadfile(filename,b())
    create(L)
    For n As Long=1 To L
        set(n,b(n))'set in values from file
    Next n
End Sub

'=========================

Screen 20

Sub drawrooms
    Dim As Long ct=0
    For x As Long=1 To 3
        For y As Long=1 To 2
            ct+=1
            Line(20,20)-(200*x,200*y),15,b
            Draw String(20+190*x-100,20+190*y-100),"room " &(ct)
        Next y
    Next x
    Line(200,120)-(200,130),0
    Line(200,285)-(200,295),0 
   
    Line(400,120)-(400,130),0
    Line(400,285)-(400,295),0 
   
    Line(100,200)-(110,200),0
    Line(300,200)-(310,200),0
    Line(500,200)-(510,200),0
End Sub


'save some data to  files
Dim As tree room(1 To 6)
Dim As zstring * lngth a(...)={"in room 3","in room 2","wall","wall"}
savefile("room 1",a())
room(1).load("room 1")

Dim As zstring * lngth b(...)={"in room 4","wall","wall","in room 1"}
savefile("room 2",b())
room(2).load("room 2")

Dim As zstring * lngth c(...)={"in room 5","in room 4","in room 1","wall"}
savefile("room 3",c())
room(3).load("room 3")

Dim As zstring * lngth d(...)={"in room 6","wall","in room 2","in room 3"}
savefile("room 4",d())
room(4).load("room 4")

Dim As zstring * lngth e(...)={"wall","in room 6","in room 3","wall"}
savefile("room 5",e())
room(5).load("room 5")

Dim As zstring * lngth f(...)={"wall","wall","in room 4","in room 5"}
savefile("room 6",f())
room(6).load("room 6")
'done with arrays and files now.
Erase a,b,c,d,e,f
Kill "room 1"
Kill "room 2"
Kill "room 3"
Kill "room 4"
Kill "room 5"
Kill "room 6"

For n As Long=1 To 6
    room(n).idx=n
Next

Dim As String msg
Dim As Long i
Dim As Long start=1

Do
    i=0
    If Multikey(fb.sc_up)   Then i=4
    If Multikey(fb.sc_down) Then i=2
    If Multikey(fb.sc_left) Then i=3
    If Multikey(fb.sc_right)Then i=1
    If Multikey(fb.sc_escape) Then Exit Do
   
    While Len(Inkey)<>0:Wend
       
        Cls
       
        If i Then  msg=room(start).find(i)
           
        Locate 30,40
        print "Use arrow keys"
        Locate 32,40
        Print msg
        Select Case msg
        Case "in room 1"
            start=1
        Case "in room 2"
            start=2
        Case "in room 3"
            start=3
        Case "in room 4"
            start=4
        Case "in room 5"
            start=5
        Case "in room 6"
            start=6
        End Select
       
        Select Case start
        Case 1
            Circle(110,125),5,15,,,,f
        Case 2
            Circle(110,290),5,15,,,,f
        Case 3
            Circle(300,125),5,15,,,,f
        Case 4
            Circle(300,290),5,15,,,,f
        Case 5
            Circle(500,125),5,15,,,,f
        Case 6
            Circle(500,290),5,15,,,,f
        End Select
       
        drawrooms
        Sleep
       
    Loop
   
     

use the arrow keys, a quick sharp press.
Last edited by dodicat on Jun 20, 2020 22:54, edited 2 times in total.
olympic sleeper
Posts: 41
Joined: Jun 07, 2020 15:47

Re: Any suggestions on the best way to set up a linked list?

Postby olympic sleeper » Jun 20, 2020 22:14

Hi,

Many thanks for the code, it's going to take me a while to read through it. What I find most frustrating is that I used to know this stuff, though I didn't realise quite what a can of worms I was opening when I started. If it wasn't for the idea of being able to put things in things etc the implementation would have been a lot simpler.

I didn't know pointers existed in Free Basic, are they implemented the same way as C or are there any differences I need to watch for?

Once again many thanks for the help.
MrSwiss
Posts: 3663
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Any suggestions on the best way to set up a linked list?

Postby MrSwiss » Jun 20, 2020 22:24

olympic sIeeper wrote: didn't know pointers existed in FreeBASIC, are they implemented the same way as C or are there any differences I need to watch for?

Not that I'm aware off, except declaration is a bit different:
in C:

Code: Select all

int *any_name
whereas, in FB:

Code: Select all

Dim As Long Ptr any_name
BasicCoder2
Posts: 3636
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Any suggestions on the best way to set up a linked list?

Postby BasicCoder2 » Jun 20, 2020 22:38

After trying to figure out what you are trying to do it seems to me you need a simple example which can be extended without adding complexity. You also seem to be concentrating on the coding part (pointers, linked lists and so on..) when I would suggest you need a higher level description of what you are attempting to do for I must confess it is unclear to me. My impression is you are wanting to describe a world in which agents can act. So you start with an agent as your first "object" and construct a simple world in which that agent can operate.

The way I would tackle it, assuming I have some idea of what you are wanting to do, is to have a data base which you can edit. You don't want that data base of things, their attributes and their relationships to be hard coded. The code should stand apart from the data base. A data base would start with a list of objects? Is all this inside a building? A room might be a container object meaning it can contain things. But again I would suggest start with a simple (reduced) world to work out the mechanics to be coded. Then you should be able to extend the complexity by editing the data base not the actual code.
Last edited by BasicCoder2 on Jun 20, 2020 23:17, edited 2 times in total.
dodicat
Posts: 6765
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Any suggestions on the best way to set up a linked list?

Postby dodicat » Jun 20, 2020 23:07

Hi basiccoder2.
You have done a lot of this kind of stuff, an agent and an environment.
I have kept my tree (list) file based in order to keep the running code separate.
I hate using pointers but they are necessary in my code, you cannot have a recursive type, unless you make it static, in which case I would have only one room, the others would be clones.
Funny in Freebasic you start off with a simple idea, try and make it reusable and general, and you end up having many lines of code to get it running, especially with OOP methods e.t.c.
grindstone
Posts: 770
Joined: May 05, 2015 5:35
Location: Germany

Re: Any suggestions on the best way to set up a linked list?

Postby grindstone » Jun 21, 2020 12:47

olympic sleeper wrote:What I find most frustrating is that I used to know this stuff, though I didn't realise quite what a can of worms I was opening when I started.
Welcome to the club! And now use that worms to get a big fish. ;-)

olympic sleeper wrote: If it wasn't for the idea of being able to put things in things etc the implementation would have been a lot simpler.
That's exactly what objects are good for. A TYPE can contain other TYPEs, that will be the next step.

@dodicat: Nice work. I'd also thought about a visualizing, but I rather kept the code lean.
BasicCoder2
Posts: 3636
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Any suggestions on the best way to set up a linked list?

Postby BasicCoder2 » Jun 21, 2020 21:11

dodicat wrote:Hi basiccoder2.
You have done a lot of this kind of stuff, an agent and an environment.


But the specific question was for any suggestions on the best way to set up a linked list and others can demonstrate that better than I can although often with fairly unreadable code to someone like me. My impression is the poster really wanted something more complex than a simple linked list. That what was required was a network of nodes containing networks of nodes containing networks of node .....

As for pointers I used them all the time in assembler code (before Windows came along). Most of my confusion is with the nomenclature used in a high level language. You can often work without them in BASIC by using indexing within a list as Leopardpm and myself did with a version of the ASTAR algorithm. I also use indexing as pointers in my Neural networks examples.
Lost Zergling
Posts: 376
Joined: Dec 02, 2011 22:51
Location: France

Re: Any suggestions on the best way to set up a linked list?

Postby Lost Zergling » Jun 22, 2020 11:34

There are different ways to design an application. By taking documentary (or non-relational) technologies as a reference, we design the structure in an essentially hierarchical manner, and we add relational glue to it at places and at times in the algorithm that we consider relevant. With an indexer controlled by keywords and with the object design, it is possible to control memory buffers (FIFO, LIFO or other custom), to do some big data, or to organize software glue between the objects, and many other things. A neural network will require more knowledge in mathematics and dynamic conceptual analysis. The design of a network of nodes network of nodes (and so on ^ n) is partly opposed in its intrinsic logic to the object design in the sense that the behavior of the object becomes sufficiently complex to no longer be able to be apprehended in an "atomic" way (or very hard). Complexity no longer comes from the interaction of objects with each other but from the complex mathematically exact modeling, in general of behavior thus presumed to be autonomous. In the case, for example, of a role play, behavior is at first glance in essence at the service of decision-making (and not decision-making in itself), which implies that the atomicity of objects would be a predominant criterion, but one could not exclude a part "against the machine" in which case a neural network type kernel could find its relevance.
To summarize, I would say that a list engine (ie lzle) would rather be a complementary and non-competitive tool compared to a network of nodes network of nodes (see above). A possible approach (according to me), would be 1) to make intelligible and coherent choices in the design, 2) to adapt technical choices to specific needs, 3) to use the tools for what they can do best (thus measuring 'backward' their adequacy to design).

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 10 guests