Thread: Circular array

  1. #1
    Registered User
    Join Date
    Nov 2005
    Location
    Canada
    Posts
    80

    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. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    203
    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. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    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.
    Last edited by 7stud; 02-16-2006 at 01:27 AM.

  4. #4
    Registered User
    Join Date
    Nov 2005
    Location
    Canada
    Posts
    80
    Quote 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.


    Quote 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)

    Quote 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. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    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. #6
    Registered User
    Join Date
    Nov 2005
    Location
    Canada
    Posts
    80
    You are most likely right! I am somehow confused by all this circularity...
    Last edited by Opel_Corsa; 02-16-2006 at 07:40 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 AM
  3. Replies: 6
    Last Post: 11-09-2006, 03:28 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM