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.

CodePudding user response：

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