Okay. . .

I find linked lists fascinating. I want to make sure I understand them; so, I am now trying to make them work in Quest.

This might be working, but I can't check it.

1. If I uncomment either line: msg (room.linked1) or msg (node) (you'll see where I have them commented out), Quest freezes up.

2. If I open the debugger and select the room object, Quest freezes up.

Something is throwing something for a "loop", but I'm not sure if that's good or bad? (Probably bad.)

The code:

<!--Saved by Quest 5.8.7753.35184-->
<asl version="580">
  <include ref="English.aslx" />
  <include ref="Core.aslx" />
  <game name="Linked Lists">
    <gameid>7c9cbb79-8d5c-4b8b-82d3-1a1aef796b7d</gameid>
    <version>0.2</version>
    <firstpublished>2021</firstpublished>
    <start type="script">
      node1 = NewListNode ("first")
      room.linked1 = NewLinkedList()
      LinkedListAdd (room.linked1, node1)
      node2 = NewListNode("second")
      LinkedListAdd (room.linked1, node2)
      // msg (room.linked1)
    </start>
  </game>
  <object name="room">
    <inherit name="editor_room" />
    <isroom />
    <object name="player">
      <inherit name="editor_object" />
      <inherit name="editor_player" />
    </object>
  </object>
  <function name="NewListNode" parameters="value" type="dictionary">
    node = NewDictionary()
    DictionaryAdd (node, "value", value)
    DictionaryAdd (node, "next", "null")
    DictionaryAdd (node, "previous", "null")
    return (node)
  </function>
  <function name="NewLinkedList" type="dictionary">
    ll = NewDictionary()
    DictionaryAdd (ll, "head", "null")
    DictionaryAdd (ll, "length", 0)
    return (ll)
  </function>
  <function name="LinkedListAdd" parameters="ll, node">
    if (ll["head"] = "null") {
      DictionaryAdd (ll, "head", node)
      int = ll["length"]
      DictionaryAdd (ll, "length", int + 1)
    }
    else {
      msg ("Finding last node. . .")
      current = ll["head"]
      next = current["next"]
      while (not next = "null") {
        current = next
        next = current["next"]
      }
      msg ("Last node found.")
      msg (current)
      msg ("Adding new node. . .")
      DictionaryAdd (current, "next", node)
      msg ("current:")
      msg (current)
      DictionaryAdd (node, "previous", current)
      // msg ("new:")
      // msg (node)
      int = ll["length"]
      DictionaryAdd (ll, "length", int + 1)
      msg ("Done.")
    }
  </function>
</asl>

OUTPUT

Finding last node. . .
Last node found.
Dictionary: value = first;next = null;previous = null
Adding new node. . .
current:
Dictionary: value = first;next = Dictionary: value = second;next = null;previous = null;previous = null
Done.

If I uncomment either line: msg (room.linked1) or msg (node) (you'll see where I have them commented out), Quest freezes up

The problem is with your previous/next links.

Quest attempts to write dictionaries out in full when you msg them.

Dictionary: value = first;next = Dictionary: value = second; next = null; prev = Dictionary: value = first;next = Dictionary: value = second; next = null; prev = Dictionary: value = first;next = Dictionary: value = second; next = null; prev = Dictionary: value = first;next = Dictionary: value = second; next = null; prev = Dictionary: value = first;next = Dictionary: value = second; next = null; prev = …

Or indented a little so it's clearer…

Dictionary:

• value = first;
• next = Dictionary:
  • value = second;
  • next = null;
  • prev = Dictionary:
    • value = first;
    • next = Dictionary:
      • value = second;
      • next = null;
      • prev = Dictionary:
        • …ad infinitum

I think the same will be true with the XML when saving a game.

Might be better creating an object for each node… something like (off the top of my head):

<function name="NewLinkedList" type="object">
  name = GetUniqueElementName("linkedlist")
  create (name)
  list = GetObject(name)
  list.length = 0
  return (list)
</function>

<type name="listnode">
  <attr name="value" />
</type>

<function name="LinkedListAdd" parameters="ll, value" type="object">
  node = null
  if (TypeOf (value) = "object") {
    if (DoesInherit (value, "listnode")) {
      node = value
      LinkedListRemove (node)
    }
  }
  if (node = null) {
    name = GetUniqueElementName ("listnode")
    node = GetObject (name, "listnode")
    name.value = value
  }
  if (ll = null) {
    ll = NewLinkedList()
  }
  node.list = ll
  if (not HasObject (ll, "head")) {
    ll.head = node
  }
  if (HasObject (ll, "tail")) {
    node.prev = ll.tail
  }
  ll.tail = node
  ll.length = ll.length + 1
  return (ll)
</function>

<function name="LinkedListRemove" parameters="node">
  if (HasObject (node, "list")) {
    if (HasObject (node, "next")) {
      node.next.prev = node.prev
      node.next = null
    }
    else {
      node.list.tail = node.prev
    }
    if (HasObject (node, "prev")) {
      node.prev.next = node.next
      node.prev = null
    }
    else {
      node.list.head = node.next
    }
    node.list.length = node.list.length - 1
    node.list = null
  }
</function>

Might be better creating an object for each node…

Hehehe.

I ended up changing everything to objects last night.

I decided it was working with the dictionaries, and that's why trying to look at the dictionaries threw Quest for a loop.

Here's what I ended up doing (far from the final version):

<!--Saved by Quest 5.8.7753.35184-->
<asl version="580">
  <include ref="English.aslx" />
  <include ref="Core.aslx" />
  <game name="Linked Lists">
    <gameid>7c9cbb79-8d5c-4b8b-82d3-1a1aef796b7d</gameid>
    <version>0.4</version>
    <firstpublished>2021</firstpublished>
    <start type="script">
      node1 = NewListNode ("first")
      ll = NewLinkedList()
      LinkedListAdd (ll, node1)
      node2 = NewListNode("second")
      LinkedListAdd (ll, node2)
      msg (ll)
      node3 = NewListNode("second")
      LinkedListAdd (ll, node3)
      msg (ll)
      ll2 = NewLinkedList()
      node4 = NewListNode("fourth")
      LinkedListAdd (ll2, node4)
      msg (ll2.first)
      node5 = NewListNode("fifth")
      LinkedListAdd (ll2, node5)
      msg (ll2.rest)
      LinkedListRemove (ll, node2)
      msg (ll)
      msg ("AllLinkedLists():")
      msg (AllLinkedLists())
    </start>
  </game>
  <object name="room">
    <inherit name="editor_room" />
    <isroom />
    <object name="player">
      <inherit name="editor_object" />
      <inherit name="editor_player" />
    </object>
  </object>
  <object name="LinkedLists">
    <inherit name="editor_object" />
  </object>
  <function name="NewListNode" parameters="value" type="object">
    node = GetObject (value)
    if (not TypeOf(node) = "object") {
      create (value)
      node = GetObject (value)
    }
    else {
      node = CloneObject (node)
    }
    node.value = value
    node.previous = false
    node.next = false
    node.listnode = true
    return (node)
  </function>
  <function name="NewLinkedListBak" type="dictionary">
    ll = NewDictionary()
    DictionaryAdd (ll, "head", false)
    DictionaryAdd (ll, "length", 0)
    return (ll)
  </function>
  <function name="LinkedListAddBak" parameters="ll, node">
    if (not TypeOf(ll["head"]) = "object") {
      DictionaryAdd (ll, "head", node)
      int = ll["length"]
      DictionaryAdd (ll, "length", int + 1)
      DictionaryAdd (ll, "first", First(ll))
      DictionaryAdd (ll, "rest", "null")
      DictionaryAdd (ll, "tail", node)
    }
    else {
      current = ll["head"]
      next = current.next
      while (TypeOf(next) = "object") {
        current = next
        next = current.next
      }
      current.next = node
      node.previous = current
      int = ll["length"]
      DictionaryAdd (ll, node.name, node)
      DictionaryAdd (ll, "length", int + 1)
      DictionaryAdd (ll, "tail", node)
      if (not TypeOf(ll["rest"]) = "object") {
        first = ll["head"]
        rest = first.next
        DictionaryAdd (ll, "rest", rest)
      }
    }
  </function>
  <function name="LinkedListRemove" parameters="ll, node">
    node.parent = null
    node.next.previous = node.previous
    node.previous.next = node.next
    if (ll.tail = node) {
      ll.tail = node.previous
    }
    if (ll.rest = node) {
      ll.rest = node.next
    }
    if (ll.head = node) {
      ll.head = false
    }
    ll.length = ll.length - 1
  </function>
  <function name="First" parameters="ll" type="object">
    return (ll["head"])
  </function>
  <function name="Rest" parameters="ll" type="object">
  </function>
  <function name="NewLinkedList" type="object"><![CDATA[
    name = GetUniqueElementName ("LinkedList1")
    create (name)
    ll = GetObject (name)
    ll.head = false
    ll.changedhead => {
      this.first = this.head
      this.rest = this.head.next
    }
    ll.first = ll.head
    ll.rest = false
    ll.tail = false
    ll.length = 0
    ll.parent = LinkedLists
    return (ll)
  ]]></function>
  <function name="LinkedListAdd" parameters="ll, node">
    if (not TypeOf(ll.head) = "object") {
      ll.head = node
      ll.length = ll.length + 1
      ll.rest = false
      ll.tail = node
    }
    else {
      current = ll.head
      next = current.next
      while (TypeOf(next) = "object") {
        current = next
        next = current.next
      }
      current.next = node
      node.previous = current
      node.parent = ll
      ll.length = ll.length + 1
      ll.tail = node
      if (not TypeOf(ll.rest) = "object") {
        first = ll.head
        rest = first.next
        ll.rest = rest
      }
    }
  </function>
  <function name="AllLinkedLists" type="objectlist">
    return (GetDirectChildren (LinkedLists))
  </function>
</asl>

Mixing objects and dictionaries, as in your example, is probably the best route.

Ummm…

 node = GetObject (value)
   if (not TypeOf(node) = "object") {
     create (value)
     node = GetObject (value)
   }
   else {
     node = CloneObject (node)
   }

If the value passed to the function is an object, you clone it before adding it to the list? That seems a little unstable.

If you're storing in-game objects like rooms in a linked list, this means that functions like AllRooms(), AllExits() or AllNpcs() will now return both the object, and its list node.

And you haven't handled the case where the value isn't a valid object name, such as "7" or "someimage.png".

Yeah... I noticed a few other issues in my "all objects" version, too.

After some waffles, I'm going to use your functions and play around with it that way.

Hmm… I think there might be a little problem with handling list nodes in this way. You need to be careful when removing objects from a list, because the node will still be there. In some cases this might be beneficial. For example, you could remove a node from one list, store it somewhere temporarily, and then add it to a different list. But there's no easy way to do garbage collection, so there may be orphaned nodes lying around all over the place.

This could let you do some interesting things that a standard Quest list can't. For example:

<function name="LinkedListRemove" parameters="node">
  if (HasObject (node, "list") and LinkedListContains (node.list, node)) {
    if (HasObject (node, "next")) {
      node.next.prev = node.prev
    }
    else {
      node.list.tail = node.prev
    }
    if (HasObject (node, "prev")) {
      node.prev.next = node.next
    }
    else {
      node.list.head = node.next
    }
    node.list.length = node.list.length - 1
  }
</function>

<function name="LinkedListContains" parameters="ll, node" type="boolean">
  if (node = null or ll = null) {
    return (false)
  }
  if (not node.list = ll) {
    return (false)
  }
  scan = ll.head
  while (not scan = null) {
    if (Equal (scan, node) or Equal (scan.value, node)) {
      return (true)
    }
    scan = scan.next
  }
  return (false)
</function>

<function name="LinkedListRemovedNodes" parameters="ll" type="objectlist">
  result = FilterByAttribute (FilterByType (AllObjects(), "listnode"), "list", ll)
  node = ll.head
  while (not node=null) {
    list remove (result, node)
    node = node.next
  }
  return (result)
</function>

<function name="LinkedListUnremove" parameters="node" type="object">
  if (not HasObject (node, "list")) {
    ll = NewLinkedList()
    LinkedListAdd (ll, node)
  }
  else {
    ll = node.list
    if (not HasObject (ll, "head")) {
      // list is empty
      ll.head = node
      ll.tail = node
      node.next = null
      node.prev = null
      return (ll)
    }
    else if (LinkedListContains (ll, node.prev)) {
      node.next = node.prev.next
      if (HasObject (node, "next")) {
        node.next.prev = node
      }
      else {
        ll.tail = node
      }
      node.prev.next = node
      ll.length = ll.length + 1
    }
    else if (LinkedListContains (ll, node.next)) {
      node.prev = node.next.prev
      if (HasObject (node, "prev")) {
        node.prev.next = node
      }
      else {
        ll.head = node
      }
      node.next.prev = node
      ll.length = ll.length + 1
    }
    else {
      LinkedListAdd (ll, node)
    }
  }
  return (ll)
</function>

<function name="LinkedListShuffle" parameters="ll">
  if (ll.length < 2) {
    return()
  }

  node = ll.head
  swap = node.next
  for (i, 0, GetRandomInt(ll.length, 2*ll.length) * GetRandomInt (2, ll.length)) {
    while (RandomChance (65)) {
      node = swap
      if (HasObject (node, "next")) {
        swap = node.next
      }
      else {
        swap = ll.head
      }
    }
    swap.prev = node.prev
    node.next = swap.next
    if (ll.tail = node) {
      ll.tail = swap
      ll.head = node
      node.prev = null
      swap.next = null
    }
    else {
      node.prev = swap
      swap.next = node
    }
    if (HasObject (swap, "prev")) swap.prev.next = swap
    if (HasObject (node, "next")) node.next.prev = node
  }
</function>

More silliness, Quest style:

<type name="listnode">
  <changednext type="script">
    if (this.next = null) {
      oldvalue.prev = null
    }
    else {
      if (IsDefined ("oldvalue")) {
        oldvalue.prev = this.next.prev
      }
      this.next.prev = this
    }
  </changednext>

  <changedprev type="script">
    if (this.prev = null) {
      oldvalue.next = null
    }
    else {
      if (IsDefined ("oldvalue")) {
        oldvalue.next = this.prev.next
      }
      this.prev.next = this
    }
  </changedprev>
</type>

Makes the add/remove code a whole lot simpler. Doesn't work with the undeleting silliness above, but it means that changing the next or prev attributes will automatically sort itself out. It can do some crazy things, but sometimes that's what you want.

node_a.next = node_b

If node A is in a list somewhere before node B, this line will neatly remove all elements between them
If node B is before node A, this will remove them (and everything between them) from the list, and make it into a new 'loop' list.
If they're in separate lists, this will split the lists (after A and before B) and swap round their second halfs.

This stuff will mess up metadata (like length and tail) in the list object. So if you're doing stuff like this, it might be better to ignore the list object completely, and treat any node as if it is a list. For example:

<function name="PrintLinkedList" parameters="list">
  node = list
 output = "<ul>"
  while (not node = null) {
    output = output + "<li>" + node.value + "</li>"
    node = node.next
    if (node = list) {
      output = output + "<li><em>" + node.value + " and so on for infinity</em></li>"
      node = null
    }
  }
  msg (output + "</li>")
</function>

This takes a listnode as a parameter, and prints a list of all the values found from that point up to the end of the list. If the list is a loop, it will go round until it reaches the same point again.

For example:

create("spring", "listnode")
spring.value = "Spring!!!"
create("summer", "listnode")
summer.value = "Hotness"
summer.prev = spring
create("autumn", "listnode")
autumn.value = "Fall"
autumn.prev = summer
create("winter", "listnode")
winter.value = "Brrrrr"
autumn.next = winter
winter.next = spring
PrintLinkedList (winter)

will generate:

• Brrrrr
• Spring!!!
• Hotness
• Fall
• Brrrrr and so on for infinity