CODEWITHSUNDEEP
javacollections
bfishman
bfishman

Reputation: 579

Name this collection

This question is language-agnostic (although it assumes one that is both procedural and OO).

I'm having trouble finding if there is a standard name for a collection with the following behavior:

-Fixed-capacity of N elements, maintaining insertion order.

-Elements are added to the 'Tail'

-Whenever an item is added, the head of the collection is returned (FIFO), although not necessarily removed.

-If the collection now contains more than N elements, the Head is removed - otherwise it remains in the collection (now having advanced one step further towards its ultimate removal).

I often use this structure to keep a running count - i.e. the frame length of the past N frames, so as to provide 'moving window' across which I can average, sum, etc.

Upvotes: 0

Views: 77

Answers (2)

user3437460
user3437460

Reputation: 17454

The programming riddle sounds like a circular linked list to me.

Well, all these description fits, doesn't it?

• Fixed-capacity of N elements, maintaining insertion order.

• Elements are added to the 'Tail'

• Whenever an item is added, the head of the collection is returned (FIFO), although not necessarily removed.

This link with source codes for counting frames probably helps too: frameCounter

Upvotes: 1

Edwin Buck
Edwin Buck

Reputation: 70909

Sounds very similar to a circular buffer to me; with the exception that you are probably under-defining or over constraining the add / remove behavior.

Note that there are two "views" of a circular buffer. One is the layout view, which has a section of memory being written to with "head" and "tail" indexes and a bit of logic to "wrap" around when the tail is "before" the head. The other is a "logical" view where you have a queue that's not exposing how it is being laid out, but definately has a limited number of slots which it can "grow to".

Within the context of doing computation, there is a very long standing project that I love (although the cli interface is a bit foreign if you're not use to such things). It's called the RoundRobinDatabase, where each databases stores exactly N copies of a single value (providing graphs, averages, etc). It adjusts the next bin based on a number of parameters, but most often it advances bins based on time. It's often the tool behind a large number of network throughput graphs, and it has configurable bin collision resolution, etc.

In general, algorithims that are sensitive to the last "some number" of entries are often called "sliding box" algorithms, but that's focusing on the algorithm and not on the data structure :)

Upvotes: 5

Related Questions