Finding all neighbors of any given element in a matrix like structure

Question

This is the code I currently have to get all neighbors of any given element in a matrix like structure:

struct Coordinates: IEquatable<Coordinates>
{
 public int Row { get; }
 public int Column { get; }
 public Coordinates(int row, int column)
 {
 Row = row;
 Column = column;
 }
 public bool Equals(Coordinates other) => Column == other.Column && Row == other.Row;
 public override bool Equals(object obj)
 {
 if (obj is Coordinates)
 {
 return Equals((Coordinates)obj);
 }
 return false;
 }
 public override int GetHashCode() => unchecked(27947 ^ Row ^ Column); 
 public IEnumerable<Coordinates> GetNeighbors(int numberOfRows, int numberOfColumns)
 {
 var increasedRow = Row + 1;
 var decreasedRow = Row - 1;
 var increasedColumn = Column + 1;
 var decreasedColumn = Column - 1;
 var canIncreaseRow = increasedRow < numberOfRows;
 var canIncreaseColumn = increasedColumn < numberOfColumns;
 var canDecreaseRow = decreasedRow > -1;
 var canDecreaseColumn = decreasedColumn > -1;
 if (canDecreaseRow)
 {
 if (canDecreaseColumn)
 {
 yield return new Coordinates(decreasedRow, decreasedColumn);
 }
 yield return new Coordinates(decreasedRow, Column);
 if (canIncreaseColumn)
 {
 yield return new Coordinates(decreasedRow, increasedColumn);
 }
 }
 if (canIncreaseRow)
 {
 if (canDecreaseColumn)
 {
 yield return new Coordinates(increasedRow, decreasedColumn);
 }
 yield return new Coordinates(increasedRow, Column);
 if (canIncreaseColumn)
 {
 yield return new Coordinates(increasedRow, increasedColumn);
 }
 }
 if (canDecreaseColumn)
 {
 yield return new Coordinates(Row, decreasedColumn);
 }
 if (canIncreaseColumn)
 {
 yield return new Coordinates(Row, increasedColumn);
 }
 }
}

This works but it seems kind of clunky and I can't help thinking there is a more elegant, concise and obvious way of doing this.

Considerations to take into account:

1. By elegant I mean more concise but readable and mantainable even if performance is slightly worse.
2. I don't want dependencies on System.Drawing.Point or similar because I don't want to use mutable structs and I don't like using types that conceptually represent unrelated things even though they happen to provide usable functionality to solve the problem at hand.
3. There is no bound checking in the arguments. This is simply because the code where I'm using this algorithm already ensures that the current coordinates instance is a valid location. As per comments, the current implementation will give erroneous results if you happen to enter matrix bounds that makes the current coordinates invalid. This is not an issue that concerns me.

• t3chb0t: I'm not sure if I understand how it works. If you need only neigbours why do you need these parameters int numberOfRows, int numberOfColumns? Can you explain what a neighbor is?
• InBetween: @t3chb0t neighbor = adjacent element. Neighbors of (0,0) would be (0, 1); (1, 0); (1, 1).
• t3chb0t: Ok, nothing exceptional so far, this is exacly how I understand neighbours... so what are the parameters for?
• InBetween: @t3chb0t well, how are you going to figure out all neighbors of any given position without indexes out range exceptions if you don't know the dimensions of the matrix to begin with?
• InBetween: @t3chb0t And how many adjacent elements does (10, 10) have exactly?

Answer 1

You could use a 2-dimensional loop to iterate over neighbors as follows:

public IEnumerable<Coordinates> GetNeighbors(int numberOfRows, int numberOfColumns)
{
 var canIncreaseRow = Row < numberOfRows - 1;
 var canIncreaseColumn = Column < numberOfColumns - 1;
 var canDecreaseRow = Row > 0;
 var canDecreaseColumn = Column > 0;
 var maxRow = canIncreaseRow ? Row + 1 : Row;
 var minRow = canDecreaseRow ? Row - 1 : Row;
 var maxColumn = canIncreaseColumn ? Column + 1 : Column;
 var minColumn = canDecreaseColumn ? Column - 1 : Column;
 for (int row = minRow; row <= maxRow; row++)
 {
 for (int column = minColumn; column <= maxColumn; column++)
 {
 if (row != Row || column != Column)
 {
 yield return new Coordinates(row, column);
 }
 }
 }
}

• t3chb0t: I just wanted to say where are the {} or why are there any for the if :-]
• Dmitry: @t3chb0t They have always been there. :P
• InBetween: Yeah, this would do also but the level of clunkiness is similar ;p

Answer 2

But you don't actually implement IEquatable Interface

If you implement IEquatable, you should also override the base class implementations of Object.Equals(Object) and GetHashCode so that their behavior is consistent with that of the IEquatable.Equals method. If you do override Object.Equals(Object), your overridden implementation is also called in calls to the static Equals(System.Object, System.Object) method on your class. In addition, you should overload the op_Equality and op_Inequality operators. This ensures that all tests for equality return consistent results.

There is already a struct that takes x y coordinates
Point

It appears only 0 and positive columns and rows are allows and yet that is not enforced

Below lacks input bounds checking

public IEnumerable GetNeighbors(int numberOfRows, int numberOfColumns)

• Mathieu Guindon: Comments are not for extended discussion; this conversation has been moved to chat.
• Mathieu Guindon: OP has now included the omitted code, feel free to amend your answer.
• Mathieu Guindon: Aye, I just wanted to give you the heads up; because the OP was specifically asked to include the omitted code, I'm not considering it an answer-invalidating edit.
• paparazzo: OP added the IEquatable implementation many hours after this answer.

Answer 3

Let's start with the name. The struct should be called Coordinate. We use plural names only for collections.

---

Now to the algorithm. You wanted it to be less verbose and I think it cannot be shorter then this.

It uses the Rectangle struct for checking whether the coordinate is within the grid bounds.

public IEnumerable<Coordinate> GetNeighbors(int gridWidth, int gridHeight)
{
 var rect = new Rectangle(0, 0, gridWidth, gridHeight);
 var offsets = new[] { -1, 0, 1 };
 foreach (var rowOffset in offsets)
 {
 foreach (var colOffset in offsets)
 {
 var coord = new Coordinate(Row + rowOffset, Column + colOffset);
 if (rect.Contains(coord.Row, coord.Column) && coord != this)
 {
 yield return coord;
 }
 }
 }
}

It also requires two operators so that the comparison for coord != this works:

public static bool operator ==(Coordinate left, Coordinate right) 
{
 return left.Row == right.Row && left.Column == right.Column;
}
public static bool operator !=(Coordinate left, Coordinate right)
{
 return !(left == right);
}

Performance & Components

It's been claimed (by many sources) that this solution would waist resources by doing unnecessary comparisons or struct allocations but... the biggest waist of resources is of course LINQ and its state machine. Tunring all three methods into ones that return a List<Coordinate> makes them nearly equal. The difference between the original solution and mine averages merely to ~30ms for 10.000.000 calls.

It's been also claimed (by many sources) that for an algorithm of this complexity (or simplicity) it wouldn't be necessary to use other .net components like the Rectangle... and it turnes out that original solution does not work for a grid of size 3x3 and a coordinate anywhere outside the bounds. It returns always three points whereas none should be returned.

The lesson is the same as always:

• no performance problems --> no optimization and
• if you find in the .net framework a ready-to-use component then use it instead of inventing your own solution that you'll have to test and debug and maintain

• Mathieu Guindon: Comments are not for extended discussion; this conversation has been moved to chat.