Difference between revisions of "Linked List Tutorial"

Jump to navigation Jump to search

Linked List Tutorial (edit)

Revision as of 22:48, 4 May 2006

6,238 bytes added ,  22:48, 4 May 2006
Further Linked List Information
imported>Tegid
(Added parent link)
imported>Tegid
(Further Linked List Information)
Line 1: Line 1:
By [[User:Tegid|Tegid]] 23:48, 4 May 2006 (EDT)
==Unfortunate Realities==
==Unfortunate Realities==
Before we get started, let me address some unfortunate realities.  The code I wrote earlier won't work.  You can't call
Before we get started, let me address some unfortunate realities.  The code I wrote earlier won't work.  You can't call
Line 6: Line 8:
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.
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
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
<pre>
<pre>
Line 34: Line 37:
     set pDSTDataMgrRef.ChildRef to 0
     set pDSTDataMgrRef.ChildRef to 0
     set pDSTDataMgrRef.setChild to 0
     set pDSTDataMgrRef.setChild to 0
    return
   endif
   endif
end
end
Line 61: Line 65:
</pre>
</pre>


But there are a couple of problems.  Unfortunately, they will have to wait for a week or so because I am out of time for today and leaving for awhile. This should give you plenty of questions.
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.
<pre>
 
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 0
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
</pre>
 
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
<pre>
ref ParentRef
</pre>
 
and DSTTestScript2 should now look like this
<pre>
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
    else
      set pDSTDataMgrRef.ParentRef to Prev
    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
</pre>
 
 
==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
<pre>
short dataRequest
short dataAvail
long Data
</pre>
 
Now we need to add to the OnActivate block of the DSTDataNodeScript to handle this new request.  We add this.
<pre>
  if (pDSTDataMgrRef.dataRequest)
    set pDSTDataMgrRef.Data to Number
    set pDSTDataMgrRef.dataAvail to 1 
    set pDSTDataMgrRef.dataRequest to 0
    return
  endif
</pre>
 
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
<pre>
  set pDSTDataMgrRef.dataRequest to 1
  ref lHead
  set lHead to pDSTDataMgrRef.Head
  if (lHead != 0)
    lHead.Activate lHead 1
  endif
</pre>
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
<pre>
short getNext
ref Current
</pre>
 
in DSTDataNodeScript, we modify the dataRequest if statement like this
 
<pre>
  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
 
</pre>
 
So, in this model to retrieve the numbers of each node, we write a new DSTTestScript3.  Assume that DSTTestScript2 has already been run.
 
<pre>
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)
    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
</pre>
 
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===
Coming Soon
===Stacks===
Coming Soon
 
==Sorted Lists==
Coming Soon
 
==Cleaning Up==
Coming Soon


==Previous Page==
==Previous Page==
[[Dynamic Storage]]
[[Dynamic Storage]]
Anonymous user
Retrieved from "https://cs.uesp.net/wiki/Special:MobileDiff/24536"

Navigation menu