C++ - Circular array with lower/upper bounds ?

Question

I want to create something similar to a double linked list (but with arrays) that works with lower/upper bounds.

A typical circular array would probably look like:

next = (current + 1) % count;
previous = (current - 1) % count;

But what's the mathematical arithmetic to incorporate lower/upper bounds properly into this ?

• 0 (lower bound item 1)
• 1
• 2 (upper bound item 1)
• 3 (lower bound item 2)
• 4 (upper bound item 2)

So that:

-> next on index 2 for item 1 returns 0

-> previous on index 0 for item 1 returns 2

-> next on index 4 for item 2 returns 3

-> previous on index 3 for item 2 returns 4

Thank you !

NOTE: Can't use external libraries.

Answer 1

Boost has a Circular container that I believe you can set bounds on as well.

In fact the Example on that page looks very similar to what you are saying here.

But anyway, you could accomplish the math portion of it easily using a modulus:

So say your max was 3:

int MAX = 3;
someArray[ 0 % MAX ]; // This would return element 0
someArray[ 1 % MAX ]; // This would return element 1
someArray[ 3 % MAX ]; // This would return element 0
someArray[ 4 % MAX ]; // This would return element 1

Answer 2

In general mathematical terms:

next === current + 1 (mod count)
prev === current - 1 (mod count)

where === is the 'congruent' operator. Converting this to the modulus operator, it would be:

count = upper - lower
next = ((current + 1 - (lower%count) + count) % count) + lower
prev = ((current - 1 - (lower%count) + count) % count) + lower

It would be up to you to find out the upper & lower bounds for each item. You could store this in a binary tree for fast retrieval. Maybe I'm not understanding your question.

(note that this assumes lower < upper, and lower > 0)

Answer 3

          +=======+        +=======+        +=======+
          |  Obj  | --->   |  Obj  |  --->  |  Obj  |
buffer    |   1   | <---   |   2   |  <---  |   3   |
          +=======+        +=======+        +=======+  

index       0                  1                2        /* our first run */

index       3                  4                5        /* second run */

and so on ...

So, you see for a 3 member list, the 1st item is indexed by 0, 3, 6, etc. Similarly, the second item is indexed by 1, 4 (1 + 3), 7 (4 + 3), ...

The general rule is: next <- (next + 1) % size, where size = upper - lower + 1

Using this formula we get:

  curr |      next  
-------+-----------------
   0   | (0 + 1) % 3 = 1
-------+-----------------
   1   | (1 + 1) % 3 = 2
-------+-----------------
   2   | (2 + 1) % 3 = 0
-------+-----------------

Hope that helps

Answer 4

I wrote this article a few years back about a circular STL iterator.

http://noveltheory.com/Iterators/Iterator_N0.htm

It will work on any STL collection (vectors & boost:array, etc)