Linked List Tutorial
By Tegid 23:48, 4 May 2006 (EDT)
Unfortunate Realities
Before we get started, let me address some unfortunate realities. The code I wrote earlier won't work. You can't call
set Curr.Child to Something
On a non-persistent reference. That means I can't call it on any of the objects I create in game. So that causes a serious problem. Fortunately there is a way to address it.
Creating a Real World Linked List
We create a Persistent Reference that the Nodes can talk to and pass data through. I call the base object of this Persistent Reference the DSTDataMgr. So a very basic DSTDataMgrScript will look like this
scn DSTDataMgrScript
ref Head ;This script will store the head of my list
ref ChildRef ;This is somewhere to store the data we need to know as a
;child node
long Number_of_Nodes ;It is helpful to know this information and it allows us to
;number the nodes
Now I know how to store the ChildRef that the Prev Node needs to store, but how do I tell the Prev Node that it needs to set it's Child Node? We add one more line to the DSTDataMgrScript
short setChild
Then we need to add an OnActivate block to the DSTDataMgrNode. This is an easy way to tell a node to do something. We will also need to define a new Persistent Reference DSTDataMgr. Do this by dragging a DSTDataMgr into a gameworld Cell (I like to put it by the exit to the Imperial Sewers (Tamriel->ICPrisonSewerExit01) but that's just personal taste). Then name it pDSTDataMgrRef and check the Persistent reference checkbox. Now we can access it in our DSTDataNodeScript
scn DSTDataNodeScript
ref Child
long Number
begin OnActivate
if (pDSTDataMgrRef.setChild == 1)
set Child to pDSTDataMgrRef.ChildRef
set Number to pDSTDataMgrRef.Number_of_Nodes
set pDSTDataMgrRef.Number_of_Nodes to pDSTDataMgrRef.Number_of_Nodes + 1
set pDSTDataMgrRef.ChildRef to 0
set pDSTDataMgrRef.setChild to 0
return
endif
end
With these two scripts we can set up our list like so
scn DSTTestScript1
short count
ref NewNodeRef
ref Prev
begin GameMode
if (count < 20)
set count to count + 1
set NewNodeRef to PlaceAtMe DSTDataNode 1, 0, 0
if (Prev == 0)
set pDSTDataMgrRef.Head to NewNodeRef
else
set pDSTDataMgrRef.ChildRef to NewNodeRef
set pDSTDataMgrRef.setChild to 1
Prev.Activate Prev 1
endif
set Prev to NewNodeRef
endif
end
But there are a couple of problems. Not the least of these is that even though I've created the list, I have absolutely no way to get any information out of it. Also, The last node won't have it's Number set, because the number doesn't get set until the child node get's set. That is easily fixed by using an OnLoad block added to the DSTDataNodeScript. The OnLoad block will run when the Node is created and the model loaded into memory. While we are modifying the script, let's add a Parent reference and set it.
scn DSTDataNodeScript
ref Child
ref Parent
long Number
begin OnLoad
set Number to pDSTDataMgrRef.Number_of_Nodes
set pDSTDataMgrRef.Number_of_Nodes to pDSTDataMgrRef.Number_of_Nodes + 1
set Parent to pDSTDataMgrRef.ParentRef
set pDSTDataMgrRef.ParentRef to Self
end
begin OnActivate
if (pDSTDataMgrRef.setChild == 1)
set Child to pDSTDataMgrRef.ChildRef
set pDSTDataMgrRef.ChildRef to 0
set pDSTDataMgrRef.setChild to 0
return
endif
end
To allow for this we need to add just two lines of code, one in the DSTDataMgrScript and one in DSTTestScript1 which we will now call DSTTestScript2
In DSTDataMgrScript we add
ref ParentRef
and DSTTestScript2 should now look like this
scn DSTTestScript2
short count
ref NewNodeRef
ref Prev
begin GameMode
if (count < 20)
set count to count + 1
;If there is no Prev ref, then the DataMgr should be the parent
if (Prev == 0)
set pDSTDataMgrRef.ParentRef to pDSTDataMgrRef
endif
set NewNodeRef to PlaceAtMe DSTDataNode 1, 0, 0
if (Prev == 0)
set pDSTDataMgrRef.Head to NewNodeRef
else
set pDSTDataMgrRef.ChildRef to NewNodeRef
set pDSTDataMgrRef.setChild to 1
Prev.Activate Prev 1
endif
set Prev to NewNodeRef
endif
end
Retrieving Data
So, we have a this wonderful list, but absolutely no way to get any data from it. So how do we solve this problem? Well, first, we need to add a flag to the DSTDataMgr like the setChild flag, so that we can check for it in our DSTDataNode's OnActivate block. Then we need a place to store the contents of the Node that we are returning. It would probably also be good for the DSTDataNode to be able to set a flag that says the data has been returned. So we add
short dataRequest short dataAvail long Data
Now we need to add to the OnActivate block of the DSTDataNodeScript to handle this new request. We add this.
if (pDSTDataMgrRef.dataRequest)
set pDSTDataMgrRef.Data to Number
set pDSTDataMgrRef.dataAvail to 1
set pDSTDataMgrRef.dataRequest to 0
return
endif
So, when a node receives a request for data, it will put it's Number into the Persistent References Data field so that an external script can read it. Then it will inform that script that the data is there by setting the dataAvail to 1.
There is still one problem. We have no way to traverse the list for information. We could ask the Head to return it's data by using the following code
set pDSTDataMgrRef.dataRequest to 1
ref lHead
set lHead to pDSTDataMgrRef.Head
if (lHead != 0)
lHead.Activate lHead 1
endif
Please note that the activating reference (the value after Activate and before the 1) doesn't mean anything and is unimportant. (The 1 means use the default activation, or run the OnActivate script, don't for instance pick the object up. More details can be found on the Activate page).
But we have no way to get to nodes further down the list and to do that, we are going to have to decide what kind of list we are.
Types of Lists
Lists
We have been talking about linked lists this whole time surely. Yes, but there are other types of Linked Lists. To traverse a List, you have what is called an Iterator that moves down the list and points at each node in turn. In this case it is as simple as a reference variable and a little new code. In DSTDataMgrScript we add
short getNext ref Current
in DSTDataNodeScript, we modify the dataRequest if statement like this
if (pDSTDataMgrRef.dataRequest)
set pDSTDataMgrRef.Data to Number
set pDSTDataMgrRef.dataAvail to 1
set pDSTDataMgrRef.dataRequest to 0
if (pDSTDataMgrRef.getNext)
set pDSTDataMgrRef.Current to Child
set pDSTDataMgrRef.getNext to 0 ;This is not NECESSARY, but I like to
;clean up after myself
endif
return
endif
;We also need to add this block in case we just want to move down the list
;but don't want the data in this node
if (pDSTDataMgrRef.getNext)
set pDSTDataMgrRef.Current to Child
set pDSTDataMgrRef.getNext to 0
return
endif
So, in this model to retrieve the numbers of each node, we write a new DSTTestScript3. Assume that DSTTestScript2 has already been run.
scn DSTTestScript3
ref Curr
short count
long Num
begin GameMode
if (pDSTDataMgrRef.dataAvail == 1)
set Num to pDSTDataMgrRef.Data
set pDSTDataMgrRef.dataAvail to 0
Message "I have received the data for Node #%.0f", Num, 1
endif
if (count < 20 && pDSTDataMgrRef.dataRequest != 1)
set count to count + 1
;This code checks to see if this is the first iteration
if (pDSTDataMgrRef.Current == 0)
set pDSTDataMgrRef.Current to pDSTDataMgrRef.Head
if (pDSTDataMgrRef.Current == 0) ;We need to make sure there are elements in
;the list
Message "There are no nodes in the list", 1
return
endif
endif
set Curr to pDSTDataMgrRef.Current
set pDSTDataMgrRef.getNext to 1
set pDSTDataMgrRef.dataRequest to 1
Curr.Activate Curr 1
endif
end
Now we should print out a message for each of the nodes in order as we traverse down the list. Of course these Nodes don't contain any real data, but we could store a Reference or 6 references or a reference and a location or anything inside of a node as long as the equivalent variable ares on our Persistent Reference so that when a node is asked for it's data, it can put them somewhere that other scripts can reference them.
Queues
A Queue is what we call a FIFO data structure. FIFO stands for First In, First Out. Basically the British amongst us will have no trouble with this concept because they call a line of people a queue, and that is what this acts like. You add new elements to the end of the line and pull data from the front. (Like getting in the back of a line and serving the person at the front). Data is constantly moving in and out of a queue.
We call getting the first Node from the front of the queue "popping it from the queue" and adding a new item to the end is "pushing it on the queue". When you pop a Node from the queue, it is no longer stored in the queue. You have to decide what to do with it now. This data structure is not as useful in Oblivion since generally we want to keep the items we put on a list, but I include it because there are times when we might want to iterate through our list once, and this is an easy way to make sure it just happens once.
So we will replace the scripts used in the List example. In DSTDataMgrScript, instead of the Iterator reference, we need to know the reference for the end of our Queue. We also want to take more control over getting and adding data to the Queue (take care of pushing and popping). So we are going to add an OnActivate block to handle adding new data. There are two valid ways to handle this. I like letting the Queue create the new Node itself, but at times it might be better to actually create the node and pass it in as the Acting Reference. So I'll show you how to do both. But remember to just pick one of these scripts to use.
Creating the new node inside the OnActivate block. I'll write the full script here, because it is enough of a change.
scn DSTDataMgrScript
ref Head ;This script will store the head of my list
ref Tail ;This is where we store the Tail of the list
ref ParentRef ;Store the value for the node's parent
ref ChildRef ;Store the new node for the Tail to grab
long Number_of_Nodes ;It is helpful to know this information and it allows us to
;number the nodes
short dataRequest
short dataAvail
long Data
short Inserting
begin OnActivate
if (Inserting)
if (Head == 0)
set Head to PlaceAtMe DSTDataNode 1, 0, 0
set Tail to Head
set Inserting to 0
return
endif
;We could let the Tail generate the child, but to keep the code the same for
;The DSTDataNodeScript, we will generate it here so that only the DSCDataMgrScript has
;to change for external node generation as opposed to List Managed new node generation
set ChildRef to PlaceAtMe DSTDataNode 1, 0, 0
Tail.Activate ChildRef 1 ;We'll let the Tail add the child to the list
return
endif
end
If we wanted instead to have the external code generate the Node for us and just pass is the reference to the new Node, then it would look like this.
scn DSTDataMgrScript
ref Head ;This script will store the head of my list
ref Tail ;This is where we store the Tail of the list
ref ChildRef ;Store the new node for the Tail to grab
long Number_of_Nodes ;It is helpful to know this information and it allows us to
;number the nodes
short dataRequest
short dataAvail
short Empty
long Data
short Inserting
begin OnActivate
if (Inserting)
set ChildRef to GetActionRef ;Now we care about the incoming reference
if (Head == 0)
set Head to ChildRef ;This line changes
set Tail to Head
set ChildRef to 0
set Inserting to 0
return
endif
;Notice this line looks the same. We just removed the PlaceAtMe since that has
;already been done.
Tail.Activate ChildRef 1 ;We'll let the Tail add the child to the list
return
endif
end
In both version we still need to handle someone ASKING for data, so we also add this if block inside the OnActivate block.
if (dataRequest)
if (Head != 0)
set Empty to 0
Head.Activate Head 1
else ;If there is no Head, then the list is empty and asking for data is an error.
set Empty to 1
set dataAvail to 1
set Data to 0
set dataRequest to 0
endif
return
endif
in DSTDataNodeScript, we modify the OnActivate block in a couple of ways. First we add code to handle someone requesting a new node to be inserted.
if (pDSTDataMgrRef.Inserting)
set Child to pDSTDataMgrRef.ChildRef
set pDSTDataMgrRef.Tail to Child
set pDSTDataMgrRef.Inserting to 0
set pDSTDataMgrRef.ChildRef to 0
return
endif
Then we modify the dataRequest if statement like this
if (pDSTDataMgrRef.dataRequest)
set pDSTDataMgrRef.Data to Number
set pDSTDataMgrRef.dataAvail to 1
set pDSTDataMgrRef.dataRequest to 0
set pDSTDataMgrRef.Head to Child ;This removes us from the list
if (Child != 0)
Child.Activate Self 1 ;We need to activate our child to let them know
;That we are no longer their parent
else
set pDSTDataMgrRef.Empty to 1
endif
Self.Disable
set Child to 0
set Parent to 0
endif
return
endif
;We also need to add this block to handle being activated by our
;parent node to inform us we are now the head node
if (Self == pDSTDataMgrRef.Head)
set Parent to pDSTDataMgrRef
return
endif
Notice that I have avoided using the GetActionRef call in anywhere but the DSTDataMgrScript? That's because GetActionRef doesn't seem to work correctly when a reference is passed down a certain number of times through OnActivate calls. In practice you can pass it down 4 times, (So activating the Tail with the GetActionRef value should work) but to avoid becoming dependent on it, I would rather check values set in the DSTDataMgrScript.
Assuming we want to use the method when the nodes are created by the list, our insertion code (DSTTestScript2) becomes a bit simpler. I'm going to make a new DSTTestScript4 to demonstrate.
scn DSTTestScript4
short count
ref Self
begin GameMode
if (count == 0)
set Self to GetSelf
set pDSTDataMgrRef.ParentRef to pDSTDataMgrRef
endif
if (count < 20)
set count to count + 1
set pDSTDataNodeRef.Inserting to 1
pDSTDataNodeRef.Activate Self 1
endif
end
Woah! That's a lot easier. Remember this is because the list itself takes care of most of the business of inserting for us.
So how do we get data from the Queue? I'll replace DSTTestScript3 with DSTTestScript5
scn DSTTestScript5
short done
long Num
begin GameMode
if (pDSTDataMgrRef.dataAvail == 1)
if (pDSTDataMgrRef.Empty)
set done to 1
return
endif
set Num to pDSTDataMgrRef.Data
set pDSTDataMgrRef.dataAvail to 0
Message "I have received the data for Node #%.0f", Num, 1
endif
if (done == 0 && pDSTDataMgrRef.dataRequest != 1)
set pDSTDataMgrRef.dataRequest to 1
pDSTDataMgrRef.Activate pDSTDataMgrRef 1 ;The activating reference doesn't matter
endif
end
That's easier too. However, remember we destroy the list as we read it. I could choose to reinsert the nodes at the end of the queue if I allowed myself to insert already generated nodes. I could stick them in some other list, or I could accept that they are destroyed. In any case, this code is easier. Is there a reason why the code for the list can't be almost as simple? I leave that for the reader to determine
Stacks
Coming Soon
Sorted Lists
Coming Soon
Cleaning Up
Coming Soon