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.
If I uncomment either line: msg (room.linked1) or msg (node) (you'll see where I have them commented out), Quest freezes up.
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:
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:
Follow us on Facebook
Follow @TextAdv on Twitter