# Thread: Circular array

1. ## Circular array

Suppose there's an array defined as A=new int[max] whom which you want to insert entries in:

Code:
```for (int i=0; i<10; i++)
{
A.insert(i);
}```
The void insert( const Item_type &item ) function takes i's and inserts them in A[] in REVERSED order (adds to the left end):
A = [9, 8, 7, ..., 1, 0]

In the header file, other than max, the following are defined:
int front; representing the first used entry in the array,
int count; representing number of items in A[].
Item_type* array;
Assume when A[] was created front and count were both set to zero.

If we were to insert the i's in regular order (added to the right end) the definiton for insert( ... ) in the .cpp definition file would look like:

Code:
```void class::insert( const Item_type &item )
{
array[count+front]=item;
count++;
}```
which, after the for-loop, would output:
A = [0, 1, 2, ..., 9]

How would you define insert() to add the item to the left instead (i.e. in reversed order)? Apparently due to 'circularity' that occurs in this process, no shifting is necessary.

A word of wisdom is appreciated.

P.S> The insert() function should be able to handle all situations. i.e. the following is not what I am asking for:

Code:
```for loop...
{
A.insert(9-i);
}```
By 'all situations' I mean that if you have B[] with 6 items already in it, insert(15) should correctly add 15 to the front (left).

2. If for some reason you don't want to use an STL container, you need to know the size of the array. Instead of count+front, you do back-count(and also -1 if count isn't 0 based like arrays are).

3. By 'all situations' I mean that if you have B[] with 6 items already in it, insert(15) should correctly add 15 to the front (left).
Why would it be incorrect to assign 15 to B[6]?

the insert() function should be able to handle all situations.
If front + count is smaller than max, add to the right, otherwise add to the left at spot front + count - max.

4. Originally Posted by 7stud
Why would it be incorrect to assign 15 to B[6]?
It wouldn't be incorrect, it's just how this particular program is supposed to work like.

Originally Posted by 7stud
If front + count is smaller than max, add to the right, otherwise add to the left at spot front + count - max.
front+count can never be greater than max (or else the code won't work. I perhaps should've mentioned it that when insert() is invoked, if count reaches max then max -i.e. size of array grows. So just take it this way, that max is always bigger than count)

Originally Posted by Syneris
If for some reason you don't want to use an STL container, you need to know the size of the array. Instead of count+front, you do back-count(and also -1 if count isn't 0 based like arrays are).
Assume:
max = 10; // initial array size
this value grows by a factor of 1.5 each time count reaches max, so the array is never 'full'. Baiscally:

if (count>=maxCount) grow();

That's the very first line for insert(). grow() is defined as a helper function to basically increment the array size by 1.5 (e.g. 10 becomes 15 and so on)

Thanks for the responses by the way.

5. front+count can never be greater than max (or else the code won't work. )
If front+count can never be greater than max, then how do you have a circular array? You need to sit down and organize your thoughts, and then clearly articulate what you want to do.

6. You are most likely right! I am somehow confused by all this circularity...

Popular pages Recent additions