Author Topic: Linked List Demo  (Read 3832 times)

0 Members and 1 Guest are viewing this topic.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Linked List Demo
« on: December 20, 2020, 05:59:39 pm »
Hello all,

Everyone knows the arrays-in-types issue can be subverted by linked lists, but not everyone embraces this (maybe two people I can name). I've been sitting on this "tech" for a while now, and realized a long time ago this this can be a hard swallow. What I've done here is implemented (one of) the simplest possible uses of this thing. We set up a simple type, insist that a string array be contained in the type there, and the rest is history. Just wanted to show, once more in 2020, how damn easy this can be. There is so much to explain, I've decided to explain none of it. Just see what the code is doing.

Code: QB64: [Select]
  1. ' This program demonstrates using a linked list as a substitute for array in type.
  2.  
  3.  
  4. REM $Include: 'SoftArrays.bi'
  5.  
  6. ' *****************************
  7. ' *** TYPEs and Definitions ***
  8. ' *****************************
  9.  
  10. TYPE Person
  11.     NickName AS STRING
  12.     Country AS STRING
  13.     FriendList AS SoftArrayStructure
  14.     '             - Stores a Label for human readability.
  15.     '             - Stores a LONG integer to denote place in memory.
  16.  
  17. DIM Steve AS Person
  18.  
  19. ' *******************************
  20. ' *** Populate regular values ***
  21. ' *******************************
  22.  
  23. Steve.NickName = "SMcNeill"
  24. Steve.Country = "USA"
  25.  
  26. ' Nothing new so far, right? Confusion level: zero
  27.  
  28. ' **************************
  29. ' *** Create linked list ***
  30. ' **************************
  31.  
  32. Steve.FriendList.HeadNode = NewSoftArray("Steve's Friends")
  33.  
  34. ' This line initializes a linked list ^, and stores the head node address in Steve.FriendList.HeadNode.
  35. ' Note we have not specified the size, the data it holds, etc.
  36. ' The head node address is calculated automatically - think of it like an image handle.
  37.  
  38. ' ********************************
  39. ' *** Structure of linked list ***
  40. ' ********************************
  41.  
  42. ' Now we populate Steve's list of friends. The end result is going to look like:
  43. '
  44. '     Steve's Friends ------- Friend 1 (Joe)
  45. '                                |
  46. '                             Friend 2 (Tom)
  47. '                                |
  48. '                             Friend 3 (Biff)
  49. '
  50. ' Note that "Friend 1" appears to the "East" of the Label.
  51. ' Note that "Frinds 2" appears to the "South" of Friend 1.
  52. ' Note that "Frinds 3" appears to the "South" of Friend 2.
  53.  
  54. ' ****************************
  55. ' *** Populate linked list ***
  56. ' ****************************
  57.  
  58. ' Define a helper variable to keep the notation slim:
  59.  
  60. a = Steve.FriendList.HeadNode
  61. a = LinkEast(a, NewTextNode("Joe"))
  62. a = LinkSouth(a, NewTextNode("Tom"))
  63. a = LinkSouth(a, NewTextNode("Biff"))
  64.  
  65. ' ... And that's it. The data is stored according to the structure above.
  66. ' Each piece of data is stored in a Node, each with its own address.
  67. ' The name of the game now is getting used to handling these addresses.
  68.  
  69. ' *************************
  70. ' *** Print linked list ***
  71. ' *************************
  72.  
  73. ' The following line will print the entire list, including the head node.
  74.  
  75. PRINT PrintSoftArray("Steve's Friends")
  76.  
  77. ' ************************************
  78. ' *** Retrieve first piece of data ***
  79. ' ************************************
  80.  
  81. ' The very first item on the list can be printed by:
  82.  
  83. PRINT Literal$(Content("Steve's Friends"))
  84.  
  85. ' ************************
  86. ' *** Typical FOR loop ***
  87. ' ************************
  88.  
  89. FOR j = 0 TO Bottom("Steve's Friends")
  90.     PRINT Literal$(JumpFrom(Content("Steve's Friends"), "s", j))
  91.  
  92.  
  93. REM $Include: 'SoftArrays.bm'
  94.  

* SoftArrays.bi (Filesize: 2.02 KB, Downloads: 201)
* SoftArrays.bm (Filesize: 30.12 KB, Downloads: 216)
« Last Edit: December 20, 2020, 06:06:41 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline SpriggsySpriggs

  • Forum Resident
  • Posts: 1145
  • Larger than life
    • View Profile
    • GitHub
Re: Linked List Demo
« Reply #1 on: December 21, 2020, 10:49:42 am »
Even though I responded to you on this on Discord, might as well give this a bump and let the forum-ites know what I was thinking about.

I saw where you replied to my code on mapped variables and said that the idea would/could work with your JSON writer. Makes me even more interested in what is going on with this. I hope more people take an interest into the idea since the way your code is laid out makes it easy for someone to take it up and learn about the parent-child relationships between the nodes. Looking forward to seeing more developments on this in the future.
Shuwatch!

Offline SpriggsySpriggs

  • Forum Resident
  • Posts: 1145
  • Larger than life
    • View Profile
    • GitHub
Re: Linked List Demo
« Reply #2 on: August 19, 2021, 12:11:16 pm »
@STxAxTIC I think this will be useful for an EDI parser I'm writing but I'm needing some help getting started. The file is structured with a purchase order, then a part number, then the shipping terms, dates, and quantities. I want to store all that in an "object", which your library can do. I'm curious about how I'd dynamically retrieve the specific information I want. If I want all the shipping quantities from that part, how could I grab only that information from the structure? Thank you in advance.
Shuwatch!

Offline Qwerkey

  • Forum Resident
  • Posts: 755
    • View Profile
Re: Linked List Demo
« Reply #3 on: August 19, 2021, 01:03:11 pm »
Everyone knows the arrays-in-types issue can be subverted by linked lists, but not everyone embraces this

Everyone??  Have not the slightest idea what you're talking about.  Better not tell Odin.  He'll erase my account.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Linked List Demo
« Reply #4 on: August 19, 2021, 01:23:15 pm »
Everyone??  Have not the slightest idea what you're talking about.  Better not tell Odin.  He'll erase my account.

Here is another discussion about having arrays in types: https://www.qb64.org/forum/index.php?topic=3977.0

and another https://www.qb64.org/forum/index.php?topic=915.msg101222#msg101222

and another https://www.qb64.org/forum/index.php?topic=841.msg100453#msg100453

Basically you store a bunch of info in a string and parse or read lengths of it for "array" values or store an array pointer in memory as Spriggsy says.
« Last Edit: August 19, 2021, 01:30:02 pm by bplus »