What is IComparable, CompareTo function, and ArrayList.Sort()

Questions & Answers
1

:expressionless: Read the title above. P.S. how can we sort an arraylist from greatest to least based on one variable?

I want to know this because on the Procedural Cave Generation tutorial, there is this code bit.

// [...]
    void ProcessMap() {
        // [...]
        List<Room> survivingRooms = new List<Room> ();
        // [...]
        
        survivingRooms.Sort ();
        survivingRooms [0].isMainRoom = true;
        survivingRooms [0].isAccessibleFromMainRoom = true;
        
        ConnectClosestRooms (survivingRooms);
    }
    
    struct Coord {
        public int tileX;
        public int tileY;
        
        public Coord(int x, int y) {
            tileX = x;
            tileY = y;
        }
    }
    
    
    class Room : IComparable<Room> {
        public List<Coord> tiles;
        public List<Coord> edgeTiles;
        public List<Room> connectedRooms;
        public int roomSize;
        public bool isAccessibleFromMainRoom;
        public bool isMainRoom;
        
        public Room() {
        }
        
        public Room(List<Coord> roomTiles, int[,] map) {
            tiles = roomTiles;
            roomSize = tiles.Count;
            connectedRooms = new List<Room>();
            
            edgeTiles = new List<Coord>();
            foreach (Coord tile in tiles) {
                for (int x = tile.tileX-1; x <= tile.tileX+1; x++) {
                    for (int y = tile.tileY-1; y <= tile.tileY+1; y++) {
                        if (x == tile.tileX || y == tile.tileY) {
                            if (map[x,y] == 1) {
                                edgeTiles.Add(tile);
                            }
                        }
                    }
                }
            }
        }
        
        public void SetAccessibleFromMainRoom() {
            if (!isAccessibleFromMainRoom) {
                isAccessibleFromMainRoom = true;
                foreach (Room connectedRoom in connectedRooms) {
                    connectedRoom.SetAccessibleFromMainRoom();
                }
            }
        }
        
        public static void ConnectRooms(Room roomA, Room roomB) {
            if (roomA.isAccessibleFromMainRoom) {
                roomB.SetAccessibleFromMainRoom ();
            } else if (roomB.isAccessibleFromMainRoom) {
                roomA.SetAccessibleFromMainRoom();
            }
            roomA.connectedRooms.Add (roomB);
            roomB.connectedRooms.Add (roomA);
        }
        
        public bool IsConnected(Room otherRoom) {
            return connectedRooms.Contains(otherRoom);
        }
        
        public int CompareTo(Room otherRoom) {
            return otherRoom.roomSize.CompareTo (roomSize);
        }
    }
}
2

Icomparable is the interface for comparable objects and CompareTo is the function called when determining how two objects should be sorted.

Sorting simple datatypes like numbers is easy and fairly unambiguous. 15 > 7 > 2 > 0. So, if you were to sort a list containing the elements {15, 2, 7, 15, 0}, the result would be 0,2,7,15,15.

But what if you were to sort a list of a custom class of colours say: {black, red, white, blue}? Is white > black? Is dog > cat? That’s why you’d need to override the CompareTo function to specify how you want the comparison to operate.

Incidentally, Arraylist is very old and not very good. I’d recommend you use generic List <> or native arrays if your collections are of fixed size.

3

Even @tanoshimi’s answer does already answer your original question, here are a few more details.

The generic List class has a Sort method to sort the elements of the List. It comes with 4 overloads:

The first Sort overload takes no parameters at all. It does only work for element types which are comparable either by default (primitive types like int, float, string) or by implementing the IComparable<T> interface.

In the example code you posted that’s the version that is used. As you can see when you look at the documentation of IComparable< T >, it only has one method that need to be implemented: CompareTo. This method has only one parameter and it get passed another object / element to which this object should be compared to. The method return an integer which indicates the relationship between those two objects. It basically can return 3 different values:

  • A value less than 0 (usually “-1”)
  • “0” (zero)
  • A value greater than 0 (usually “1”)

When CompareTo returns a negative value, that means the object should appear before the “other” object in the sorted list.
When CompareTo return 0 it means both objects are equal, so it doesn’t care which one goes first.
When CompareTo return a positive value, that means the object should appear after the “other” object.

As i said primitive types like “int” also implement this interface and can be sorted natively. Sorting always sort from the lowest to the greatest value by default. If you want to sort the values the other way round you just have to “invert” the return value of CompareTo. This can be done by literaly inverting the value by placing a “-” infront of the return value, or by swapping the two compared objects. The second solution is what has beed used in your code example. So instead of comparing the roomSize of this room with the roomSize of the other room, he swapped the two variables.

So this:

return otherRoom.roomSize.CompareTo (roomSize);

would be the same as:

return -roomSize.CompareTo (otherRoom.roomSize);

The Sort method will internally iterate through all elements and call the CompareTo method of the elements inside the List in order to determine the order of the elements.

The other 3 overloads work the same way, but they don’t require the element type to implement the IComparable< T > interface. Instead you either have to pass a delegate (method reference) to a method that can compare two elements of your List:

private static int Compare(Room room1, Room room2)
{
    return room2.roomSize.CompareTo (room1.roomSize);
}

Or you have to pass a “comparer object” which does the comparison of two elements. It’s basically the same as using a delegate, but the method has to be inside an object that implements the IComparer interface. This might be useful when you have external dependencies that you need during your comparing operation. For example to sort the elements based on a threshold value. Such a comparer object can only dynamically handle the sort order by checking a bool member variable. However those are more advanced things which you only need when you want to sort the list in many different ways.

To sum up:

  • The IComparable interface can define the default sorting order of a certain class / struct.
  • Passing a IComparison delegate to the Sort method is an easy way to specify a custom sorting logic
  • Creating a seperate IComparer object can be used when a more advanced sorting is required.

Note: instead of explicitly creating a comparer object you can also use a lambde expression / anonymous method / closure. Those will automatically create a hidden class which serves the same purpose as a comparer object due to the ability to reference variables from the outer scope.

// passing a lambda expression which does the same as the CompareTo method above
list.Sort((a,b)=>b.roomSize.CompareTo(a.roomSize));