|
FIFO data structure |
ngiacomelli
Member #5,114
October 2004
|
I believe that FIFO is the data structure that I am after in my game. Basically when text needs to be displayed, I want it added to list (a maximum of five messages may be shown at once). New messages are added to the bottom of the list and have a lifetime variable that slowly ticks upwards. Once a message has been displayed for X amount of seconds, it perishes. In-game the messages would be rendered in order of oldest to newest: Old message New message Which would mean that, once Old message perishes, the New message will move up and take its place. Now, does anyone have any friendly C examples of a nice simple FIFO structure?
|
Onewing
Member #6,152
August 2005
|
FIFO is just First In First Out. You could do it easily with a linked list, always adding to the beginning of the list and removing from the beginning of the list. A small C-like example would be: [EDIT] - OOops got my FIFO and FILO mixed...editing post...
myList would then only contain the message "Hello". ------------ |
BAF
Member #2,981
December 2002
|
No... he wants FIFO. The older messages (first ones in) will expire before the new ones (last ones in), so the first ones in go out first. |
Onewing
Member #6,152
August 2005
|
I noticed that after I wrote my post and tried to stick a quick edit in saying I was changing the post. Guess it wasn't quick enough. ------------ |
ReyBrujo
Moderator
January 2001
|
I think it is something similar to this:
(Edited: Fixed pop, was doing a pile instead of a queue. Also removed the previous link as it is not a pile and cleared the tail if the last element is popped from the queue). -- |
ngiacomelli
Member #5,114
October 2004
|
Okay, as far as the push and pop commands are concerned: I'm slightly confused as to how the data is actually taken into account? As for the other example of remove... I'm not very familiar with pointers... but I'm assuming I would have to adjust it to loop through lList until lList->next == NULL? Something like:
|
ReyBrujo
Moderator
January 2001
|
In a queue and a pile, data is never taken into account. It doesn't matter what the node is holding, but when it was inserted into the list. In a [ordered] list, the data is used to sort the nodes as they are inserted into the list, but you are not doing that. The problem with your remove is having to iteract until finding the last one. That is why you should keep a pointer to the tail. However, if you are going to remove the last one (which I guess is the last one to be inserted) you are using a LIFO (last in, first out), which is a pile, not a queue. -- |
ngiacomelli
Member #5,114
October 2004
|
If data is not taken into account (I see what you are saying)... then why have you included a data integer in the node_st struct? I've explained my situation (and what I'm looking to achieve)... but now I'm even more confused as to which data structure I actually need!
|
Carrus85
Member #2,633
August 2002
|
Just as a side note, the term used for a LIFO data structure is typically stack, not pile (at least in english).;)
|
ReyBrujo
Moderator
January 2001
|
The data is there just to let you know there is some data in the node. In other words, instead of 'int data' put all the information you need, like text, length, health point, etc, or a struct with your data. The important thing is that the node encapsulates your data, being it a simple integer or a full class. Oh, stack... I always say pile instead of stack -- |
Goalie Ca
Member #2,579
July 2002
|
Quote: Now, does anyone have any friendly C examples of a nice simple FIFO structure? Google search for queue structure. If you are coding in c++ there is one in STL and probably one in BOOST as well. ------------- |
ngiacomelli
Member #5,114
October 2004
|
Here's my attempt using some Queue structure code I found via Google: Most of it works well (messages are added and can be displayed). Except, after the first message dies (see SortQueue), garbage is displayed for that specific string and then the rest functions normally for a few more messages before crashing. I'm guess this is down to me breaking the link between the list elements, but I'm not sure how I should really go about it?
typedef struct { char message[MSG_SIZE]; int lifetime, type; struct listelement *link; } listelement;
|
Tobias Dammers
Member #2,604
August 2002
|
If you have a fixed number of messages, then it can be even easier. Just use a ring buffer.
Something like that. --- |
Paul whoknows
Member #5,081
September 2004
|
Quote: Just as a side note, the term used for a LIFO data structure is typically stack, not pile (at least in english).;)
"Pila" is the Spanish word we use for stack(LIFO), and "pile" is the most common mistake you can expect from a Spanish talker. ____ "The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner. |
A J
Member #3,025
December 2002
|
for 5 text strings ___________________________ |
Tobias Dammers
Member #2,604
August 2002
|
Wow, didn't notice you're from Argentina, Paul. Your English certainly doesn't tell. There are quite a few "false friends" between Spanish and most Germanic languages (English, German and Dutch are the ones I use). Took me a few weeks to find out that German / Dutch / English "tempo" (in music) unfortunately doesn't correspond to "tiempo", but rather to "aire", which, in turn, I had taken to mean something like "atmosphere" or "general feel". Enough OT. --- |
|