Which data structure can act like a circular queue?

Question

The picture above has 25 action points such that:

1. Each of the four corners of each of the three layers is an action point.
2. The midsection of each of the four sides of each of layer is an action point.
3. The intersection of the vertical and horizontal lines is an action point.

Adjacent action points are any two action points that are joined by a line and are not separated by any other action point.

The state of an action point can be 1, -1, or 0.

I need a data structure, or a combination of any number of data structures that effectively accomplishes the following:

1. Store the states of all action sites.
2. I should be able to quickly swap the states of any two adjacent action points.
3. I should be able to quickly change state of any action point.

Which data structure can help me accomplish this? I figured I would need a list of some sort of circular queue but I'm not sure.

Answer 1

There is two major cases: the action points (AP) pattern MAY change / grow, or it cannot.

Growable/modifiable pattern

I would use a simple array to store each AP, an AP being stored as a structure containing, for each index:

• The state,
• Its coordinates within the pattern (-3 ? x ? 3 and -3 ? y ? 3 here, adapt as needed but keep them as integers),
• A list of adjacent AP (a simple vector containing the indexes inside the array of these adjacent AP, sorted by index preferably).

The array is sorted so that array[i]<array[j] ? (array[i].x<array[j].x) || ((array[i].x=array[j].x) && (array[i].y<array[j].y)). So finding an AP within the array from its coordinates is done in O(log2(n)).

For adjacent AP, if you have a guarantee that no AP can have more than 4 adjacent AP, then you can optimize the list by fixing it to an array of 4 elements, organized as cardinal points around the current AP (example: 0=North, 1=East, 2=South, 3=West), and put "-1" as index if there is no adjacent AP in this direction. Otherwise, use a dynamic list.

Then, once the action point is found, the adjacent AP list can be used to check which ones are indeed adjacent, and if it's required to check if a particular AP is adjacent to another, again it's done in O(log2(n)) if the adjacent AP list is sorted, or even in O(1) if limited to cardinal directions and if the direction is known when searching this adjacent AP.

This should be fast enough even if you grow the pattern to something huge, like a 9999x9999 matrix, while not using too much memory since only existing AP are really stored.

Fixed pattern

For such a small pattern, array can be replaced by a 7x7 matrix - therefore, there is no need for storing coordinates within the AP structure. However, the adjacent AP list is still required, but you need to use the above version with cardinal directions, and it will require only a boolean (true=adjacent AP is here, in this direction). You'll need only to add/substract 1 to current x or y to find the adjacent AP structure.

You also need to store NULL AP structures, or to use a special state value to indicate that there is NO valid AP here. This is indeed a "waste" of memory, but let's face reality: you "only" use twice the memory, i.e. 49 structures, instead of 25 - so 24 structures set to "invalid". Not a big deal... It won't be the same with a 9999x9999 matrix and "only" 100,000 AP inside, obviously, but here it worths the memory waste.

For example, in this matrix, the structure at (1,2) isn't a valid AP - while the (1,1) and (2,2) are valid AP. Of course, the center AP has (0,0) as coordinates, while external corners are at (±3,±3) in this matrix.

For language constraints, you may require to constantly add/substract 3 to all coordinates in order to keep them positive or null (C and C++ would require such an adjustment, for example).

Usage

Both methods allow to find quickly, from O(1) to O(log2(n)) complexity, any possible AP and its adjacent AP. Then, doing the requested operations is now trivial and is done in O(1).

Answer 2

The fundamental data structure needed to represent the action states in the diagram is a simple int[25].

1. Store the states of all action sites.

To store the state of one of those grids, all you need is an array of 25 integers to hold the -1 or 0 or +1 values for each action point.

2. I should be able to quickly swap the states of any two adjacent action points.

Swapping values in two array elements is 3 assignments.

3. I should be able to quickly change state of any action point.

That is a single assignment.

You can easily wrap the array in a custom class with methods to perform the operations in 2. and 3. It can also deal with other things such as logic that depends on the notional graph links between different action points. (These do not need to be encoded as data structures ... assuming that they are unchanging / unchangeable as implied by the stated requirements.)

One design decision you need to make is whether the state sets should be mutable or immutable.

The above assumes that all states sets have 3 layers / 25 action states. If the number of layers is variable, you can use the same approach ... with an array that has different numbers of slots to hold states.

---

The above deals with a single state set. If you have multiple state sets representing a sequence of (game?) states, then you can represent them as a List or Stack of state snapshots, or something else, depending in your applications larger scale requirements.

Unfortunately, there are no real clues in your question as to what those larger scale requirements are. (I am imagining some kind of game where the -1, 0 and +1 represent presence or absence of player pieces. But I could be totally wrong. Advising based on guesses about the problem is (IMO) pointless.)

---

You seem to want things to be "fast". I have two things to say to you about that:

1. There is not enough information in your question to come up with a solution that is going to be fast. The problem is that we do not understand how these data structures are going to be used. It is the "how they will be used" that will determines the performance characteristics required for ... various operations.

2. Beware of premature optimization. Making code "as fast as possible" is not a sensible design goal. Make it as fast as it needs to be ... and don't waste time and effort making it faster.

   When you are doing your initial design and implementation work, you typically cannot predict how fast it is going to be ... relative to your performance goals. Optimizing at this stage is (typically) misguided because:

• you don't know if any optimization will be needed at all, and
• you don't know (and cannot reliably predict) which parts of the design / implementation will present the performance bottlenecks.

My advice would be to focus on getting something that works before trying to make it fast.