FB II Compiler

PG PRO

Debugging

Memory

System

Mathematics

Resources

Disk I/O

Windows

Controls

Menus

Mouse

Keyboard

Text

Fonts

Drawing

Sound

Clipboard

Printing

Communication

ASM

Made with FB

MEMORY

Understand linked lists


"Tedd's Linked List", the source code for which is posted on the FBwebring, is a very well presented piece of code. Using this as a starting point, I would like to ask a couple of questions about Linked Lists, which might be useful in my present work.
Question 1: In the quoted example, record data seems to be stored progressively in a block of memory as follows: address(2)info(1)address(3)info(2)....address(n+1)info(n).
Here info(i) indicates the variable data in the ith record and address(i+1) is the address of record (i+1), which stored as an element of record i. If the memory block required for the list has to be relocated when n grows, then I would expect the early addresses to become out of date, judging from the order in which this information is stored in the example. But, since Tedd's algorithm works, my fear is evidently unfounded. Could someone please explain how the address information keeps up to date with memory relocation?
Question 2: While "Tedd's Linked List" demonstrates how to construct a Linked List, I would appreciate a simple example of a situation where a Linked List is of particular value. Alternatively, could someone kindly refer me to a book refenece that discusses the elements of Linked Lists?
Help in understanding the Linked List concept would be appreciated

Vic Maslen


<< Question 1: In the quoted example, record data seems to be stored progressively in a block of memory as follows:
If the memory block required for the list has to be relocated when n grows, then I would expect the early addresses to become out of date, judging from the order in which this information is stored in the example. But, since Tedd's algorithm works, my fear is evidently unfounded. Could someone please explain how the address information keeps up to date with memory relocation? >>


I haven't seen Tedd's example, so I can't comment on how he does it.

However, there is no reason all of the elements in a linked list have to be stored together. Since each one contains a pointer to the next, you can have linked list records scattered all over memory. As long as you have the address of the first record, you can "walk the list" from beginning to end at any time.

So when you run out of space in the first block, it's okay to leave it alone, create a new, separate block, and start allocating records in that.

<< Question 2: While "Tedd's Linked List" demonstrates how to construct a Linked List, I would appreciate a simple example of a situation where a Linked List is of particular value. >>

The MacOS uses a linked list to keep track of the windows on the desktop. A linked list works perfectly, because windows always work in front-to-back order, and can be created or deleted at any time.

The function FN FRONTWINDOW gives you the address of the frontmost window's record. Each window's record contains the address of the window record behind it.

The MacOS uses linked lists extensively. Besides window lists, control lists, driver queues, event queues, and other internal OS structures are based on the linked list.

Mars


<< .... Alternatively, could someone kindly refer me to a book refenece that discusses the elements of Linked Lists? >>

Linked Lists are an interesting and useful concept. They are not too difficult to understand.
Think of them as a database. The database is not just one record occurring immediately after the previous record. The last part of a record is a pointer (an address) to where the next record is to be found. You can also make a pointer back to the previous record.
So, when you modify a linked list, you only modify the last part of the record, the part that points to the next record, or the previos record.

Here is an example

Item 1 is initially linked to item 2. Later I want to link item ! to item 24. All I need to do is change Item 1's link. I change it from 2 to 24.

You could implement this as an array.
With some of the array elements being the address of the links.

Peter


<< You could implement this as an array. With some of the array elements being the address of the links. >>

This seems to me to be a bad suggestion. The beauty of the linked list is that you don't have to worry about free records, remaining space (you have the whole heap basically at your disposal), and other administration.

Maybe I'm missing something, but I'd sooner die than code a linked list using anything but handles.

It's easy to prototype a linked list in an array so that a beginner could get the hang of how it all works. For a beginner this _may_ be fast enough. It certainly was for me when I wrote an assembler for the 8048 series of microprocessors. It didn't matter to me if it took 5 seconds or 2 minutes to run.

What are the advantages of handles in linked lists, apart from saving your life? 8)

PB


<< .... Alternatively, could someone kindly refer me to a book refenece that discusses the elements of Linked Lists? >

As a reference check out "The Art of Computer Programming; Vol. 1 Fundamental Algorithms" by Donald Knuth.

Charlie Dickman


<< I would appreciate a simple example of a situation where a Linked List is of particular value. >>

OK... the Mac Toolbox bases its window records on linked lists. The data for any window is stored in a window record. Each window record has a field called nextWindow&, which points to the window behind it. The window record does not exist until a window is created.

The advantage is flexibility: the user can create as many windows as memory allows, and a window record will be created every time. No worries about having to dim arrays or resize handles. Also, no memory is wasted. A window record doesn't exist until a window is created; it is destroyed immediately when the window is closed. There is no need to reserve memory space just in case more records are required.

I used linked lists in a WDEF I was working on last summer. Each window that I drew had a separate record in addition to the regular window record to store information that was private to my WDEF. First I made sure the code worked for three windows using linked lists. Then I tested it by opening and closing more and more windows. There were no problems; it worked like a charm.

wave


I have nothing against linked lists, but for ease of use, understanding, and maintenance, I have just one word (with apologies to the long-timers who have heard me say it too often):

XREF@

It gives instant access without "walking" lists. Familiar array format (single- or multi-dimensional). Adjusting handle size is (usually) no more difficult than creating new handles. MUCH simpler if you want to save your records to (or retrieve them from) disk. (Just one handle to write/read.) Saves one master pointer, 12 bytes header space and 8 bytes of links for each record after the first.

Window-record lists are usually fairly short, and the record itself a bit bulky. An obvious case for a linked list. Another would be variable-size records. For most any other situation, it's XREF@ for me!

Jay


<< Pau Bruneau commented on Peter Bancrofts comments...
You could implement this as an array. With some of the array elements being the address of the links. This seems to me to be a bad suggestion. The beauty of the linked list is that you don't have to worry about free records, remaining space (you have the whole heap basically at your disposal), and other administration. Maybe I'm missing something, but I'd sooner die than code a linked list using anything but handles.
It's easy to prototype a linked list in an array so that a beginner could get the hang of how it all works. For a beginner this _may_ be fast enough. It certainly was for me when I wrote an assembler for the 8048 series of microprocessors. It didn't matter to me if it took 5 seconds or 2 minutes to run.
What are the advantages of handles in linked lists, apart from saving your life? 8) >>


The advantage is you don't have to worry about your array running out of space, because there is no array. You don't have to worry about how big to make your array, thereby limiting the size of your list, again, because there is no array.

You don't have to worry about wasting memory, because no matter how big or small the list is, it always takes up exactly (number of elements) * (size of element) bytes.

I agree that speed is not a concern either way in 99% of the cases. In fact, your method may be faster because you can jump directly to an element. But for me, the nature of a linked list is such that I only use it for the type of applications that wouldn't benefit much from that capability.

Perhaps to open my eyes a little, Peter, tell me what you would do when your list gets full and you have to add another element to it.

PB


<< Perhaps to open my eyes a little, Peter, tell me what you would do when your list gets full and you have to add another element to it. >>

In my particular application, an assembler for 8048 microprocessors, I was strictly limited to the size of an EPROM. I cannot go beyond that physical size limit. Therefore in processing my mnemonics, I make an array that is big enough to hold all the mnemonics while I sort out forward references etc.

I'll have a look at using your method or XREF, if I ever get around to rewriting it.

Peter


Jay wrote:
<< I have nothing against linked lists, but for ease of use, understanding, and maintenance, I have just one word (with appologies to the long-timers who have heard me say it too often):
XREF@
It gives instant access without "walking" lists. Familiar array format (single- or multi-dimensional). Adjusting handle size is (usually) no more difficult than creating new handles. MUCH simpler if you want to save your records to (or retrieve them from) disk. (Just one handle to write/read.) Saves one master pointer, 12 bytes header space and 8 bytes of links for each record after the first.
Window-record lists are usually fairly short, and the record itself a bit bulky. An obvious case for a linked list. Another would be variable-size records. For most any other situation, it's XREF@ for me! >>


I too usually find an XREF@ array to suit my needs better; but there are certain things that make linked lists preferable at times. Besides the issue of variable-size records (which I hadn't even thought about), there's this:

1) Inserting and deleting items from the linked list is often faster than doing the same thing with an array. If you have an array full of 1,000 items and you need to insert a new item into slot #5, (between the current item #4 and current item #5), then you need to blockmove a potentially huge chunk of memory (items #5 through #1,000) out of the way in order to make room for the new item. If you had implemented this with linked lists, then the new item #5 can be put anywhere in memory; to insert it into its proper place in the "chain," you just break the link between #4 and (old) #5; then link #4 to (new) #5, and link (new) #5 to (old) #5 (which now becomes #6). No big blockmoves.

2) Big blockmoves may not be a problem for your fast computer, but there may be situations where you _must not_ slide the items around in memory: for example, suppose you have some external pointer which points to item #17. Then suppose you need to insert a new item into slot #5 as above. You cannot slide items around to make room for the new item, for then your pointer to item #17 no longer points to the right place. The linked list of windows in the MacOS is a perfect example of this. Once a window is created, its record _cannot_ be moved in memory, because applications depend on it staying in one spot. The only way to keep it "stationary" and yet allow other windows to be inserted and deleted at arbitrary positions within the list, is to use a linked list.

Rick


I've been reading the arguments for and against linked lists, and I thought I'd throw my two cents in. I think Rick made a good point about inserting an item at the beginning of a huge single-chunk of memory. It might be painful on slow computers to blockmove the huge back-end of the "chunk" to make room. On the other hand, it may also be painful on slow computers to find the 955th item of a 1000 item linked list if you have to walk the whole list just to get there.
What about this...Supposed you combine the two ideas. Make one XREF@ array where each item is 4 bytes. When you need to create new record items, create a new handle (or pointer) and store the address in the XREF@ array at that item number. This way you would have individual records in memory, but one master XREF@ array of the address to each chunk of memory.
Then if you needed to insert an item into slot #5 of a 1000 item list, just create your handle (or pointer) and store the address in the master XREF@ array in slot #5. The most memory you would ever have to move is 4*( the number of following records)....not so bad. Then the other problem would be solved too. To find item #95, just go to slot #95 in your XREF@ array to get the address to the handle (or pointer). No need to walk a list.
Makes sense to me.

Rob


<< I've been reading the arguments for and against linked lists, and I thought I'd throw my two cents in. I think Rick made a good point about inserting an item at the beginning of a huge single-chunk of memory. It might be painful on slow computers to blockmove the huge back-end of the "chunk" to make room. On the other hand, it may also be painful on slow computers to find the 955th item of a 1000 item linked list if you have to walk the whole list just to get there.
What about this...Supposed you combine the two ideas. Make one XREF@ array where each item is 4 bytes. When you need to create new record items, create a new handle (or pointer) and store the address in the XREF@ array at that item number. This way you would have individual records in memory, but one master XREF@ array of the address to each chunk of memory. Then if you needed to insert an item into slot #5 of a 1000 item list, just create your handle (or pointer) and store the address in the master XREF@ array in slot #5. The most memory you would ever have to move is 4*(the number of following records)....not so bad. Then the other problem would be solved to. To find item #95, just go to slot #95 in your XREF@ array to get the address to the handle (or pointer). No need to walk a list. Makes sense to me. >>


Rob, you beat me to the punch. I was just beginning to write that very suggestion when your posting arrived. This is the approach I chose for my current project. If indirection is a good thing, then maybe more indirection is a great thing. Two other points I could make about it:
1) It is easy to create a second (third, etc.) index array in case you want to keep the records sorted in different ways.
2) If you use the index arrays, it may not even be necessary to move all those handles when you delete a record. Just leave it set to 0, and you can plug your next new handle in there. You always need to check for valid handles anyway! It's much quicker to search for an empty slot than to do a blockmove. If there's no empty, just tack the new handle onto the end. (There's even a toolbox call--PTRANDHAND--to do that, although I'm not sure FB supports it.) Your index arrays (which can be _short_ integer XREF@ arrays) will handle the organization.
I'm sure there is a speed penalty for additional levels of indirection, but I'm guessing it doesn't even come close to that of big blockmoves.

Jay


I too usually find an XREF@ array to suit my needs better; but there are certain things that make linked lists preferable at times. Besides the issue of variable-size records (which I hadn't even thought about), there's this:
[SECTION SNIPPED FOR SAKE OF SPACE]
2) Big blockmoves may not be a problem for your fast computer, but there may be situations where you _must not_ slide the items around in memory:
for example, suppose you have some external pointer which points to item#17. Then suppose you need to insert a new item into slot #5 as above. You cannot slide items around to make room for the new item, for then your pointer to item #17 no longer points to the right place.
The linked list of windows in the MacOS is a perfect example of this. Once a window is created, its record _cannot_ be moved in memory, because applications depend on it staying in one spot. The only way to keep it "stationary" and yet allow other windows to be inserted and deleted at arbitrary positions within the list, is to use a linked list.

I'm feeling a little dense. Hopefully someone can tell me why I would want to use pointers for anything, especially a linked list. I've been programming for years and have only used pointers when IM stated that it must be used for a toolbox call. The only benefit I can see in using a pointer would be that I don't have to spend time locking and unlocking it. Outside of this it seems to be a detriment. If you don't allocate your pointers at the beginning of your program then you end up fragmenting memory. I say this based on this supposition: The intent of using a pointer is to permanently allocate memory during the entire life of the program.
Feeling kinda dense and hoping someone would enLIGHTen me.

W.


Firstly, thanks to everyone for their most helpful contributions to the current discussion on Linked Lists. I still have one conceptual problem which might be due to an inadequate grasp on Handles.
In "Tedd's Linked List", published on the FB Webring, Tedd uses just one global handle, namely gDataH&, to store data of the linked list. As one builds up the list and progressively increases the handle size, the memory block contains successive entries like the following
200000
100
1000
200008
101
1001
200016
102
1002

where 200000 and like numbers are addresses to the next record and 100,1000 are two items stored in the first record, 101,1001 are corresponding items in the second record and so on. Tracking through Tedd's algorithm it seems to me that if, as the size of the list grows sufficiently that the memory block associated with gDataH& has to be relocated, then surely the addresses for the early records would become out of date.
I feel sure that my conclusion is wrong but I cannot see why. I do note that the management of windows has been given as a good example of the use of linked lists. However, I understand that window information is always stored in pointers, not in handles.

Vic Maslen


<< I've been programming for years and have only used pointers when IM stated that it must be used for a toolbox call. The only benefit I can see in using a pointer would be that I don't have to spend time locking and unlocking it. Outside of this it seems to be a detriment. If you don't allocate your pointers at the beginning of your program then you end up fragmenting memory. I say this based on this supposition: The intent of using a pointer is to permanently allocate memory during the entire life of the program. >>

In my post about "pointers" to the data elements in a linked list, I was using the word "pointer" in the generic sense, meaning "a long integer containing the address of some (any) useful chunk of memory." The kinds of pointers you're talking about are those which specifically point to a thing called a "non-relocatable block," which is a special kind of data structure managed by the Memory Manager.
In the _generic_ sense, you'll find yourself using pointers all the time: for example whenever you use syntax like "@myVar" you're using a pointer--it's just not a pointer to a non-relocatable memory block, and it's not handled by the Memory Manager.

Rick


<< As one builds up the list and progressively increases the handle size, the memory block contains successive entries like the following
200000
100
1000
200008
101
1001
200016
102
1002
where 200000 and like numbers are addresses to the next record and 100,1000 are two items stored in the first record, 101,1001 are corresponding items in the second record and so on. Tracking through Tedd's algorithm it seems to me that if, as the size of the list grows sufficiently that the memory block associated with gDataH& has to be relocated, then surely the addresses for the early records would become out of date. >>


Actually, the real data would look more like;
8
100
1000
16
101
1001
24
102
1002

Then when you got the handle, let's say it contained "5432", you'd look at address "5432" for the pointer, which would be your 200000. That's your "base address"; all references into your list are offsets from this base. So, you'd actually look at address 200008 for the second entry in the list, but the "address" stored in the list for that is the 8; the 200000 comes from the location of the start of your list. If the Mac moves the list, the pointer gets changed as well, from 200000 to say 208000; as long as you use the handle and add the 8, you'll still find the second entry, but now at 208008 instead of 200008!

Bill


<< I'm feeling a little dense. Hopefully someone can tell me why I would want to use pointers for anything, especially a linked list.
-snip-
Feeling kinda dense and hoping someone would enLIGHTen me. >>


W:
Use of pointers is simply another way to use memory. A pointer simply points to a specific memory location. Normally, when one sets a variable (i.e., a = 10) the programming language takes care of the necessary background set-up, namely getting the memory allocation for "a" (i.e., integer -- 2 bytes) and placing "10" at the location. Whereas, if you ask for a memory allocation in getting a pointer, then you are allocating the memory yourself and taking care of the variable type (please note that the variables could be any size and type). And, if you are asking for a handle, then you are also allowing the memory manager to move your memory around as it deems necessary (which is preferable).
Now, why would you use a pointer in a linked list? That's like asking why would you need wheels for a car. Neither goes very far without the other. A Linked list in nothing more than another way to store a bunch of variables
The link is the only way to tie all the variables together for accessing. The beauty of a linked list is that you do not need to know beforehand how much memory you need for your variable list. In other words, you can allocate memory on the fly. By contrast, in using a DIM statement you need to know in advance how much memory you would need. That is not always possible.
One last thing, we have talked about linked lists as if they are just one type. That is not true. There are several types of linked list and the algorithms for searching them, inserting, deleting, balancing, ect. are quite varied and remarkable. They are well worth the effort to study.

Tedd


<< Make one XREF@ array where each item is 4 bytes. When you need to create new record items, create a new handle (or pointer) and store the address in the XREF@ array at that item number. This way you would have individual records in memory, but one master XREF@ array of the address to each chunk of memory. >>

This is a great idea, and actually this is how the Mac trap dispatch mechanism works. Each Toolbox routine lives somewhere in memory, and therefore has an address. These addresses are stored in a table called the trap dispatch table. When the Toolbox wants to find a routine it just looks it up in the table.
The linked list idea also comes into play when you patch a trap, because what you do is insert a new address into the trap dispatch table which now points to your code, and then jump to the old address at the end of your routine. So your patch code becomes an element in a linked list of code sections. If a lot of people patch the same trap, then this chain of patches is really a linked list. So the linked list concept works well for executable code as well as for data.
I once spent an afternoon talking programming with a friend of mine, though, who explained why the linked list mechanism is a better idea than a jump table. He had me convinced, but I can't remember now what his reasons were. :-) Suffice it to say that I'm sold on linked lists. Maybe someone can explain why they're better than dispatch tables or jump tables.

Wave


Sorry Ted, I guess I wasn't too clear on what I meant. I use handles all the time and have no problem understanding the benefits of using them. I understand linked lists and some forms of trees. I've just never come to a clear understanding on the benefits of using pointers. It just seems to me that their purpose is to permanently allocate memory for the life of the program. Since they don't move, using them in a linked list seems counter-productive. Disposing of pointers in a linked list would fragment the applications heap.
Sorry to be so dense.

W.


No problem being dense. I think I contributed to your confusion in my diction.
The definition I gave for pointers in my linked list (tedd's linked list) was "a pointer simply points to a specific memory location" is somewhat misleading and NOT the same as allocating another hunk of memory as found in the operation of:
pointer& = FN NEWPTR(sizeNeeded&)
The "pointer&" in the above example will fragment memory AND will require you to dispose of it to free up memory.
The pointer (link) I spoke of in the linked list example is only a pointer (link) to the next record. As such, it does not need to be released. However, the handle (or pointer) at the beginning of the list does need to be disposed to free memory.
In my example, I start with a handle and grab a hunk of memory equal to two records. -- The size of the block of memory is not that important. The reason for grabbing more than what's needed is in the older CPU's grabbing memory is time consuming and this allows faster operation, but I digress --
After initialization the block of memory, I then add records as needed and I keep track of their links. Keeping track of their links is done NOT by creating a "pointer", but rather an offset from the start of the linked list. If one will notice in my example, that my function "FN allocateRecord" returns an offset and not a pointer. As such, the link stored in each record is actually an offset from the initial handle.
For example, if the handle was memory location 10,000 and each record was 20 long, then record 10 would be located at 10,000 + 10 x 20, or 10,200.
Now, if the memory manager then chooses to move the linked list somewhere else, let's say 20,000, then record 10 would be 20,000 + 10 x 20, or 20,200.
Now, if one also examines my linked list demo, one can see that when the record demand exceeds the memory allocated, that I then call upon FN SETHANDLESIZE (newSize&) to reset the size of the memory needed for the linked list. As such, the memory manager will look in memory as to where it wants the new list to be. The memory manager may leave it where it is and add additional memory to the end, or it may find another location and move the entire list as a large blockmove. It's the memory manager's call.
You spoke of trees and some linked list allow trees. My personal favorite is the reb/black tree for linked lists. It is one of the fastest searchable list there are and may compete reasonably well with the "zombie" solution previously described by jonathan and Mars, if I could understand fully understand their solution.

tedd


<< you had me ROTFL with this last line. I'm sure you _do_ understand (if it's real, then we continue to discuss off list).
Actually, I didn't really listen to everything about the zombie problem until it was too late. So, I was hoping that you would take the opportunity to explain the algorithm you and Mars came up with. I think the general idea was some kind of large numeric flag to note visited cities. But I'm not sure as of the specifics of how one implements it.
These algorythmic discussions are great, and thanks for the blow- by-blow account of your linked lists. It's fascinating. It's moments like this that i feel a need for a CS background as I'm sure there are times when we're trying to reinvent the wheel.
Now. Whats a 'reb/black' tree (bTW even if this is a 'red/black' tree I still don't know what it is)? >>


You've asked a pretty big question. A red/black tree is a special form of a binary search tree.
One can easily understand a linked list in that it is just a long list of objects. Each object is linked to the next object.
To search a linked list, one would just get the first object, make a comparison -- if correct, then end -- if not correct, then grab the next object and repeat the process. Upon finding what you want, then the search would be over. Please note that the worst case scenario would be n time for a list of n objects.
However, if one places some other things in a linked list, such as red/black or parent/child, or left/right (binary search items/links), then one can get the worst case search scenario down to log n for a list of n objects.
A binary search tree is simply how one can organize a set of objects in a binary fashion (this or that) such that you can find elements fast. For example, lets say your program was given the following objects in this order.
15
18
17
20
6
7
13
9
3
4
2
How would you organize them? You could sort them as they came in or you could place them in a linked list in a special way. Such as the binary decision of: If it's larger, then place it right. If it's smaller, place if left. In other words, place the link to the object in the right or left portions of the link structure depending upon it relationship to the parent object. So...
* 15 was the first object. So, it goes to the beginning of the list (what else? nothing to compare it with).
* 18 was the next object which is larger than 15. So it is placed to the right of 15 (in 15's right link).
* 17 was the next object which is larger than 15 and less than 18. So, it is placed to the left of 18 (in 18's left link -- note that this also places it right of 15).
* 20 was the next object which is larger than 15 and larger than 18. So it is placed to the right of 18.
Using the method presented, the tree would look like this:
__15__
/ \
6 18
/ \ / \
3 7 17 20
/ \ \
2 4 13
/
9
Please note how 13 was placed. First, 13 was compared to 15 and sent left.
Then 13 was compared to 6 and was sent right. Six's right link was filled with 7. So 13 was compared to 7 and was sent right of 7 to 7's vacant link.
Note that every object has a left and right link. However, not all left or right links are filled with anything, such as 20. Note that 20's left and right links are nil, as are 17, 2, 4 and 9. Also, objects 7 and 13 only have half of their left/right links connected to anything.
Now, if someone wanted to find 13, the search would be: 15->6->7->13.
Please note that this is much faster than a search of 2->3->...12->13 as found in a sequential search. Also note, that if I was searching for 5 (not in the list), the search would be 15->6->buzzzzz!
A binary tree search works best when the data/objects in the binary tree are random. If the data is not random, then the tree can become unbalanced.
In other words, one side of the tree (or limb) can become much longer than any other portion of the tree. If this happens, then the overall searches become longer and thus diminishes the effectiveness of the algorithm. To compensate for this type of problem, one much rotate the branches of the tree to balance things out. A red/black tree contains an additional bit of information that ensures that no path is more than twice as long as any other path. So, the tree is approximately balanced. That's why I like red/black trees.
How one programs the entire process is a bunch of code and a long explanation. If you're interested, then I suggest that you check out:
Practical Algorithms For Programmers
by Andrew Binstock and John Rex
ISBN: 0-201-63208-X
My cost $29.95 US
Algorithms in C
by Robert Sedgewick
ISBN: 0-201-51425-7
My cost $46.00 US
Introduction to Algorithms
by Thomas Cormen et al
ISBN 0-262-03141-8 (MIT Press)
ISBN 0-07-013143-0 (McGraw-Hill)
My Cost $ 55.00
I have written a red/black tree in C (complete with search, insert, delete and balancing capabilities). I plan on developing a full red/black tree thingie in FB when I have some time.

tedd


<< you had me ROTFL with this last line. I'm sure you _do_ understand(if it's real, then we continue to discuss off list). >>
<< Actually, I didn't really listen to everything about the zombie problem until it was too late. So, I was hoping that you would take the opportunity >>


The peripatic zombies ride again:
As I described the problem it was zombies wandering from city to city each city has 1 to 8192 gates, that may only be entered once. There are 1 to 16384 cities. Each city has one exit gate, there are no restrictions on exits. A zombie may not come back to a city it has already visited. There can be any number of zombies, moving or not, at any one time.
This was used to describe a mechanism for improving on the ScriptActions demo that I did with Ryan McGann (where is he now?). The zombie being the user input (thus to the computer appearing as obtuse as random wandering zombies, as the user can create actions (the cities) link them to other actions (other cities) in whatever order he/she wishes). An action may not loop, and I needed a mechanism for determining if any two cities could be linked. But I also needed it real quick as i could only refuse a link betwwen the time the user lifts up the mouse after clicking and dragging a link to another action.
I narrowed this down to two techniques: linked lists and a massive byte index. Each action having a spot of memory set down to note all the actions that are linked in downstream so to speak. Then at mouseup I would have to skip thru this memory to determine if the action was already present in the memory for that action, if it was then refuse it. The disadvantage of linked lists being that in a worst case scenario I would have to fly thru 16383 possible entries and so the idea of having a 16384 bits strung together as a variable that the zombie would bring in (ie this would be the accumulated actions/cities that exist in the city the zombie was coming from) and having 16384 bits strung together in the city the zombie was entering and then just do a logical AND on both. if i get a result: it's a no go.
The principal disadvantage (i found another after) of this method is that it is wasteful of space, unlike lists which are potentially dynamic, and so can grow to find the space necessary. If there are only 12 actions there is as much space reserved in each action record as there would be for 16384 action records. But whereas a simple linked list would require longer and longer search times as the number of cities increased (because don't forget you'd need to search each 'visited city' against each already connected city) a simple bit operation would also take exactly the same time be there 1 or 16384 cities.
Looking at your explanation of red/black binary trees, i see that my worst case calculation for linked lists is false, as this would allow must quicker access, probably not as fast as the bit operation, but quite frankly on a modern machine, the two operations would be idistiguishable on a 'typical' case, not necessary a 'worst' case.
Since then, preparing to implant this in the interface code, i have come up against another problem. Undoing. I don't mean just a CMD-Z; that i can implement by just backing up the records before the last operation, and copying them back into place, and provoking a screen redraw. No, what I mean is that the actions are linked like a flow chart and at anytime the user can intervene anywhere, linking actions together, but also cutting links at will (This as in fact the reason that I likened the users actions to the deambulations of a zombie, as the links that would be created, could seem, completely random when seen from the computers point of view.)
If the user cuts a link, I have to remove the connections that that link brought in to the city/action index. OK, again using the logical bit operations I could just XOR the bits present in the calling cities index from the called ciy's index (remember that links have a direction, you may link to the same city/ action, but not create a loop.
Quick sketch of legal and illegal moves:

+------+
I(2) I
I M I
I (2)I=#=#
+------+ H H +------+
H #=>I(1) I
#====# I B I
+------+ H I (3)I=#
I(4) I #=# +------+ +------+ H
I E I #=>I(8) I H
#=>I (7)I==>I N I H
H +------+ I (17)I H
H +------+ H
#===============#

All moves displayed are legal.
B->N would be legal.
However B->M would be illegal as would N->B.
Please note that because of the in doors and the out doors the sense of flow is important (look for the > signs).
So, the only way to undo a link would be to zero the index in the city that had received the visit, then rebuild it by using a logical OR on all the indexes of the cities that still enter (in a worst case scenario +/- 8100 OR operations).
My mind cries out to me that there must be simple ways to do this, and that others must have done this sort of thing before. Or perhaps they just plan better, and don't get painted into such corners.
Well there you are tedd. What do you make of this?

jonathan


<< zombie snip-
Well there you are tedd. What do you make of this? >>


Let's take the worst case. You have 16,384 cities each with 8,192 gates which can be visited by any one of 16,384 zombies. From this you want to know what is the best way to determine if a zombie is attempting to visit a city more than once.
-- Sounds more like spermicide investigation. --
In addition, you want to be able to delete a past action by any zombie to any city at any time.
Question: Why 8,192 gates? Doesn't one gate per city satisfy the action?
What do I make of it? I think that having each zombie create a r/b binary tree for each city it encounters would work very well. You see, upon testing a zombie that has entered all but one city would have a binary tree of 16,383 cities or nodes. Upon searching the tree, each test halves the entire tree. For example, on the first test: Does the city lie in this pile of 8,200 or that pile of 8,200 cities? On the second test: Does the city lie in this pile of 4,100 or that pile of 4,100 cities? And so on.
Therefore, the worst case search (with a properly balanced tree) would be only 14 tests to find any specific city. Not 16,383 tests.
Now, I still don't fully understand your diagram. It looks like one of those old ANSI Star Trek games and I'm not sure where the Enterprise is. But, it sure looks like a mess of Photon torpedoes flying around. :-)

I've corrected my linked list example. You can find a copy at:
http://www.sperling.com/sc/programs/teddsLinkedList.sit
While my old one worked, Vic Maslen pointed out to me that what I had explained (in a previous post as to how linked list worked) was NOT like my example. After careful review, he was right. So, I changed the code to reflect what I know about linked lists.
Thanks to Vic for his sharp eye.

tedd