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

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 2

          +=======+        +=======+        +=======+
          |  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