The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

What do you call this?

I am in need of a name for a data structure that holds a fixed number of ordered elements, accessible by index, which pushes elements off when you add to it beyond the capacity.  It was a simple matter to code it; naming it is the hard part.

It's not a queue, it's not a circularly linked list, it's a ____________!
Befuddled
Monday, August 13, 2007
 
 
The structure is just how the data is stored, so it would simply be an array.
Bill
Monday, August 13, 2007
 
 
What does it push off? The oldest element? Element 0? Element maxIndex?
Daniel
Monday, August 13, 2007
 
 
Sounds like some sort of variant on a Most Recently Used (MRU) list for history tracking...
stoneyowl
Monday, August 13, 2007
 
 
Bill: I'm not going to call my class "Array."  That wouldn't fly with the compiler.

Daniel: It pushes off the oldest element.  Index 0 is the oldest, index n is the newest.  I did it this way because it was the easiest method when inheriting from List<T>.
Befuddled
Monday, August 13, 2007
 
 
isn't it called a stack?
Jonathan A. Send private email
Monday, August 13, 2007
 
 
A stack doesn't allow you to arbitrarily add any number of new elements.  It's also not formally accessible by index.
Befuddled
Monday, August 13, 2007
 
 
Cache?
Jeff Zanooda Send private email
Monday, August 13, 2007
 
 
I remember seeing a couple implementations of deques that had array type access.
http://en.wikipedia.org/wiki/Deque
Peter Send private email
Monday, August 13, 2007
 
 
buffer

Monday, August 13, 2007
 
 
I've heard that called a ring buffer or circular buffer.
Jeffrey Dutky Send private email
Monday, August 13, 2007
 
 
When used in a strictly serial fashion, this would be a FIFO (first-in-first-out):
http://en.wikipedia.org/wiki/FIFO

I don't know if there's a name for a random access variant; it isn't very common.  The only time I remember using it myself is for a scrollable history window.  I used a C++ deque and did a pop off the head for every push after the maximum capacity was reached.
Mark Ransom Send private email
Monday, August 13, 2007
 
 
It's a fixed size queue. Ring buffer is another commonly used name for this kind of thing, although most ring buffers I've used actually block addition when the buffer is full instead of dropping the oldest item off.
Chris Tavares Send private email
Monday, August 13, 2007
 
 
Oh, one big advantage of using a ring-buffer data structure is that, due to the fixed size, you can allocate all the storage you'll ever need up front. As a result, you can use fast array-style accesses instead of chasing pointers.
Chris Tavares Send private email
Monday, August 13, 2007
 
 
I was about to post that since the fixed number of elements are ordered, it's not a stack, a FIFO, a queue, or a ring buffer.

But then OP states that "it pushes off the oldest element.  Index 0 is the oldest, index n is the newest."

So I'm confused as to whether it's ordered -- which I assumed to mean, sorted in some manner -- or just "ordered" by the age of each element.

If it's the latter, then it definitely does sound like a FIFO queue, which can be implemented a number of ways including ring buffers.


I'm interested in finding out what this data structure is & what it really orders.
Ian Johns
Tuesday, August 14, 2007
 
 
Daniel Send private email
Sunday, August 19, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz