I see what you are saying Tedd and I think you
are just this close >|< (see that little space
in between) to what I was hoping for.

the difference between what you suggested and
what I was looking for isnt much.  I see how
I added more complexity to the use of linked
lists than was necessary.

event queue:  1 2 3 4 5 6 7 8 9 10
----------------------------------------
input value:  1 2 3 4 5 6 7 8 9 10

OK everything is beautiful until we need to
add the 11th value into a queue that only
holds 10.  To keep the order of the events
in the queue I was looking to push the oldest
entry out and add the newest entry.

event queue:  1 2 3 4 5 6 7 8 9  10
----------------------------------------
input value:  2 3 4 5 6 7 8 9 10 11

the oldest input (1) was pushed out.

so what I would end up doing is a slightly
modified version of what you stated where
I would keep two global variables:  gLastPtr
and gFirstPtr so that I dont have to traverse
the list for every new entry

upon entering a new value
gFirstPtr = new value which
means that I have now 11 entries
then I make gLastPtr = the 10th
entry by looking at the previous 
entry and disposing of the 11th
entry.  So it would need to be a
double-linked list.

I'm going to try both out to see
which is the most processor
intensive.

When I've done it, I'll let you
know what the results were.  Hopefully
I'll have time this evening to try
this out.

Thanks,


W.

-----Original Message-----
From: tedd [mailto:tedd@...]
Sent: Thursday, October 17, 2002 10:16 AM
To: futurebasic@...
Subject: Re: [FB] better queue suggestion desired


W.

>Anyone have a better solution to my problem?

Sure do -- using a linked list is the way to go (did you expect 
anything other from tedd).

>I'm interested in keeping a queue of the
>last 1000 numbers received.  Since there
>will be much more than 1000 numbers received
>I was trying to avoid shuffling queue entries
>but I dont see how to avoid it. 
>
>This code isnt fully developed but shows
>what my intent of a first-in-first-out
>(fifo)algorithm. 
>
>Ultimately I need to know what the last
>1000 numbers used were in the correct
>order
>
>If I use a linked list then I still have to
>build & destroy potentially millions of pointers,
>traverse the links, renumber the entries,
>take first off and put the last on. That
>appears to be more intensive than shuffling
>the array.

Not true as stated.

It goes like this.

Grab first value, allocate memory for a link list record (see below), 
and place the value into the first record.

Link list record:

	next link
	value

Place the first link address into the global gFirstLinkAddrs&

Grab next value, allocate memory for a record, and place the value in 
the record. Place the address of this record under the "next link" of 
past record. Repeat until 1000 records are reached.

When value for record 1001 is provided, repeat the allocate record, 
store link and value as previously described -- then simply go to the 
first record in the link (gFirstLinkAddrs&), find the "next link" 
address in that record and place that value into gFirstLinkAddrs&. 
Then dispose of the original gFirstLinkAddrs& record memory 
allocation.

You don't need to traverse the links and renumber the entries to 
add/delete entries.

So, with every value over 1000, all you have to do is allocate one 
record, dispose of one record, and change one variable. It's 
surprisingly simple. Much easier than working with an array (no 
matter how one attempts it).

As normal, to retrieve any entry, just start at the beginning and 
traverse the link. If you want to start at the end of the link and 
traverse the link, then you'll need a double linked list.

tedd



>this code hasnt been tested because I just
>wrote without the aid of a compiler to
>ensure correctness
>
>Anyone have a better solution to my problem?
>
>Thanks,
>
>
>W.
>
>
>_maxEntries = 1000
>
>begin globals
>dim as long gCount
>dim as long gArray(_maxEntries + 1)
>end globals
>
>
>// max entries to store
>// before queue rolls.
>
>local fn doFIFO(theNum as long)
>dim as long index
>
>long if gCount = _maxEntries
>
>for index = 2 to _maxEntries
>gArray(index -1) = gArray(index)
>// move entries down to make
>// room for new entry placed
>// on top
>next
>
>gArray(_maxEntries) = theNum
>// store last entry on top
>
>xelse
>
>inc(gCount)
>gArray(gCount) = theNum
>
>end if
>
>dim as long theNum
>
>for theNum = 1 to 2000
>// function call simulates
>// the entering of values
>fn doFIFO(theNum)
>next
>
>do
>handleevents
>until 0
>
>--
>To unsubscribe, send ANY message to <futurebasic-unsubscribe@...>


-- 
http://sperling.com/

--
To unsubscribe, send ANY message to <futurebasic-unsubscribe@...>