# Toroidal array with deletable nodes

Edit: apparently the term toroidal array is a concise name for a grid with the wrapping behavior which I implemented in the Grid class I wrote. So, obviously that much has been done before, as I suspected when I originally posted this article. However, my node “deletion” system may still be something new. Actually, the deletion system seems to be horribly bugged, and I don’t have time to fix it.

I wrote a pair of classes to handle a 2×2 or larger grid of nodes. Each node borders 4 other nodes. For example, a 3×3 grid would look like:

```0 1 2 3 4 5 6 7 8```

Node 0 would be connected to node 6 to the north, node 1 to the east, node 3 to the south, and node 2 to the west. (Node connections wrap to the other side of the grid when the node is on an “edge” of the grid.) Node 4 would be connected to 1, 5, 7, and 3, respectively.

Upon deleting a node, the hole is filled by the remaining nodes. I’m probably not the first one to implement something like this, but I was kinda bored and felt like coding it from scratch.

Grid.java:

``` public class Grid { private int width, height; private GridNode[] nodes; public Grid(int width, int height) { super(); this.width = width; this.height = height; nodes = new GridNode[width * height]; int north, south, east, west; for (int i=0; i<width*height; i++) { north = findNorthBoundary(i); east = findEastBoundary(i); south = findSouthBoundary(i); west = findWestBoundary(i); nodes[i] = new GridNode(north, east, south, west); } } public Grid() { } public GridNode getNode(int index) { return nodes[index]; } public int[] getConnectedNodes(int index) { int allNodes[] = new int[] { nodes[index].getNorth(), nodes[index].getEast(), nodes[index].getSouth(), nodes[index].getWest() }; int intact = 4; for (int i=0; i<4; i++) { if (allNodes[i] == -1) { intact--; } } int intactNodes[] = new int[intact]; int pos = 0; for (int i=0; i<4; i++) { if (allNodes[i] == -1) { continue; } else { intactNodes[pos] = allNodes[i]; pos++; } } return intactNodes; } private int findWestBoundary(int i) { if (isWestEdge(i)) { return i + width - 1; } else { return i - 1; } } private int findSouthBoundary(int i) { if (isSouthEdge(i)) { return i % width; } else { return i + width; } } private int findNorthBoundary(int i) { if (isNorthEdge(i)) { return (width * height - (width - i)); } else { return i - width; } } private int findEastBoundary(int i) { if (isEastEdge(i)) { return i - width + 1; } else { return i + 1; } } private boolean isWestEdge(int index) { return ((index % width) == 0); } private boolean isEastEdge(int index) { return ((index % width) == (width - 1)); } private boolean isSouthEdge(int index) { return (index >= ((width * height) - width)); } private boolean isNorthEdge(int index) { return (index < width); } public void deleteNode(int i) { if (isEastEdge(i)) { nodes[i-1].setEast(i-width + 1); nodes[i-width+1].setWest(i-1); } else if (isWestEdge(i)) { nodes[i+1].setWest(i + width - 1); nodes[i + width - 1].setEast(i+1); } else { nodes[i-1].setEast(i + 1); nodes[i+1].setWest(i-1); } if (isNorthEdge(i)) { nodes[i+width].setNorth((width * height) - width + i); nodes[(width * height) - width + i].setSouth(i+width); } else if (isSouthEdge(i)) { nodes[i-width].setSouth(i % width); nodes[i%width].setNorth(i-width); } else { nodes[i-width].setSouth(i + width); nodes[i+width].setSouth(i-width); } nodes[i].collapse(); } public boolean isAvailable(int i) { return nodes[i].isAvailable(); } } ```

GridNode.java:

``` public class GridNode { private int north, east, south, west; private boolean available; public GridNode(int north, int east, int south, int west) { super(); this.north = north; this.east = east; this.south = south; this.west = west; this.available = true; } public int getNorth() { return north; } public void setNorth(int north) { this.north = north; } public int getEast() { return east; } public void setEast(int east) { this.east = east; } public int getSouth() { return south; } public void setSouth(int south) { this.south = south; } public int getWest() { return west; } public void setWest(int west) { this.west = west; } public boolean isAvailable() { return this.available; } public void collapse() { this.west = -1; this.south = -1; this.north = -1; this.east = -1; this.available = false; } } ```

Usage example:

``` //constructs a grid with nodes 0-25 Grid grid = new Grid(5, 5); grid.deleteNode(8); ```

The resulting grid will have node 7 connected to node 9, and node 3 connected to node 13.

Some limitations:

• You should of course check the result of `grid.isAvailable(index)` before you try to do anything with a given node.
• The grid must have at least two nodes in every row and column, unless it's okay for your nodes to link to themselves.
• I also didn't handle deleting nodes that are adjacent, so try to avoid that unless you want a mess. This was just a quick hackish implementation, after all...