I have this cute data structure that I just found a second opportunity
to use. I googled for references to it, but came up empty. I
probably just don't know its name.
The algorithm on this data structure typically has an array of
pointers, and in a loop refers to array[i % n] .. array[(i+n-1) % n],
modifies array[i % n], then increments i. I do away with i by having
an array of size 2*n, where array[i] = array[i+n]. Then I use array2
instead of array, increment array2 instead of i, and reference
array2[0]..array2[n-1]. The loop has to remember to reset array2
whenever it walks too far, but otherwise i and %n are gone.
What's this data structure called? Where is it used? 2 2197
Bob Jenkins wrote: I have this cute data structure that I just found a second opportunity to use. I googled for references to it, but came up empty. I probably just don't know its name.
The algorithm on this data structure typically has an array of pointers, and in a loop refers to array[i % n] .. array[(i+n-1) % n], modifies array[i % n], then increments i. I do away with i by having an array of size 2*n, where array[i] = array[i+n]. Then I use array2 instead of array, increment array2 instead of i, and reference array2[0]..array2[n-1]. The loop has to remember to reset array2 whenever it walks too far, but otherwise i and %n are gone.
What's this data structure called? Where is it used?
A "circular queue" or a "circular buffer".
I searched Google http://www.google.com/
for
+"circular queue"
and I found lots of stuff.
E. Robert Tisdale wrote: Bob Jenkins wrote:
I have this cute data structure that I just found a second opportunity to use. I googled for references to it, but came up empty. I probably just don't know its name.
The algorithm on this data structure typically has an array of pointers, and in a loop refers to array[i % n] .. array[(i+n-1) % n], modifies array[i % n], then increments i. I do away with i by having an array of size 2*n, where array[i] = array[i+n]. Then I use array2 instead of array, increment array2 instead of i, and reference array2[0]..array2[n-1]. The loop has to remember to reset array2 whenever it walks too far, but otherwise i and %n are gone.
What's this data structure called? Where is it used?
A "circular queue" or a "circular buffer".
I searched Google
http://www.google.com/
for
+"circular queue"
and I found lots of stuff.
This is also known as a ring buffer.
--
Thomas Matthews
C++ newsgroup welcome message: http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq: http://www.raos.demon.uk/acllc-c++/faq.html
Other sites: http://www.josuttis.com -- C++ STL Library book This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Dennis Gavrilov |
last post by:
Hi, All!
I have two questions: strategic and technical.
Technical one first:
I need to share an array of objects (implemented as hashes, having
references to other objects and hashes, sharing...
|
by: sneill |
last post by:
How is it possible to take the value of a variable (in this case,
MODE_CREATE, MODE_UPDATE, etc) and use that as an object property name?
In the following example I want 'oIcon' object to have...
|
by: herrcho |
last post by:
#include <stdio.h>
#define MAX 10
int queue;
int front, rear;
void init_queue()
{
front=rear=0;
}
|
by: Kenneth Lantrip |
last post by:
Anyone got any ideas as to how this process could be improved for speed?
this is what I have...
Dim j, q As Integer
Dim x(16), y(16) As Byte
x.CopyTo(y, 0) ' shift left circular 24 bits
|
by: James |
last post by:
I am using vb.net and need to keep in memory a large data structure, so I am
looking for the best option. And after several test I am pretty confused. So
I will be grateful if anyone can help me.
...
|
by: Kyle Teague |
last post by:
What would give better performance, serializing a multidimensional array
and storing it in a single entry in a table or storing each element of
the array in a separate table and associating the...
|
by: rajiv07 |
last post by:
Hi to all,
I have a script to list the file names in a directory .When i run this script locally (command prompt) it displays the exact file name (even though the file name has two spaces).But i...
|
by: =?Utf-8?B?U2hhdW5P?= |
last post by:
I have a TCPIP socket providing data to my app.
My app works on messages (not textual) with a predefined footer (eg 0x01
followed by 0x02)
How should i go about buffering this and retrieving the...
|
by: james457 |
last post by:
Hi all,
I am sending data from a linux application through serial port to an embedded device.
In the current implementation a byte circular buffer is used in the firmware. (Nothing but an array...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |