concept group representative in category software development

This is an excerpt from Manning's book Seriously Good Software: Code that works, survives, and wins. Login to get full access to this book.

Figure 3.8. The memory layout of Speed3 after executing the first three parts of UseCase. The amount and size fields of a and c are grayed out because they contain stale values that are irrelevant to the behavior of their objects. Only the fields of the group representatives are relevant and up-to-date.

I’ll talk about the find operation and the path compression technique first. All operations on a Container need to find the group representative, because that’s where the water amount information is located. Given the previous discussion on parent pointer trees, finding the group representative is easy. You just follow the parent references until you reach the root of your tree, recognizable by having parent==this. The path compression technique consists of turning every node that you encounter into a direct child of the root. You modify the tree while you navigate it, in such a way that future operations will be more efficient.