Difference between revisions of "Linked List Tutorial"

Jump to navigation Jump to search

Linked List Tutorial (edit)

Revision as of 14:33, 18 May 2006

7,545 bytes added ,  14:33, 18 May 2006
Fixed some small script issues. Added Queue section.
imported>Tegid
(Further Linked List Information)
imported>Tegid
(Fixed some small script issues. Added Queue section.)
Line 77: Line 77:
     set pDSTDataMgrRef.Number_of_Nodes to pDSTDataMgrRef.Number_of_Nodes + 1
     set pDSTDataMgrRef.Number_of_Nodes to pDSTDataMgrRef.Number_of_Nodes + 1
     set Parent to pDSTDataMgrRef.ParentRef
     set Parent to pDSTDataMgrRef.ParentRef
     set pDSTDataMgrRef.ParentRef to 0
     set pDSTDataMgrRef.ParentRef to Self
end
end


Line 110: Line 110:
     if (Prev == 0)
     if (Prev == 0)
       set pDSTDataMgrRef.ParentRef to pDSTDataMgrRef
       set pDSTDataMgrRef.ParentRef to pDSTDataMgrRef
    else
      set pDSTDataMgrRef.ParentRef to Prev
     endif
     endif
     set NewNodeRef to PlaceAtMe DSTDataNode 1, 0, 0
     set NewNodeRef to PlaceAtMe DSTDataNode 1, 0, 0
Line 209: Line 207:
   endif
   endif


   if (count < 20)
   if (count < 20 && pDSTDataMgrRef.dataRequest != 1)
     set count to count + 1
     set count to count + 1
     ;This code checks to see if this is the first iteration
     ;This code checks to see if this is the first iteration
Line 231: Line 229:


===Queues===
===Queues===
Coming Soon
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.
<pre>
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
</pre>
 
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.
<pre>
 
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</pre>
 
In both version we still need to handle someone ASKING for data, so we also add this if block inside the OnActivate block.
<pre>
  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
</pre>
 
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.
<pre>
  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
</pre>
 
Then 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 
    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
</pre>
 
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.
<pre>
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
</pre>
 
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
<pre>
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
</pre>
 
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===
===Stacks===
Coming Soon
Coming Soon
Anonymous user
Retrieved from "https://cs.uesp.net/wiki/Special:MobileDiff/24537"

Navigation menu