Enum tricks: hierarchical data structure

Java enums are typically used to hold array like data. This tip shows how to use enum for hierarchical structures.

 

Motivation

Once upon a time I wanted to create enum that contains various operating system, i.e.

public enum OsType {
            WindowsNTWorkstation,
            WindowsNTServer,
            Windows2000Server,
            Windows2000Workstation,
            WindowsXp,
            WindowsVista,
            Windows7,
            Windows95,
            Windows98,
            Fedora,
            Ubuntu,
            Knopix,
            SunOs,
            HpUx,

I did not like this structure because I'd like to see a group of WindowsNT that contains WinNTWorkstation and WindNT server. All windows versions should be in super group of "windows". Fedora, Knopix and Ubuntu are distributions of Linux. All Linux distributions together with SunOs and HpUx are Unix systems. All Windows systems have common properties. The same is about Unix systems. And I hate copy/paste programming.

 

 

 

Solutions

As always there are several solutions.

Class per OS Solution

The obvious solution here is to create separate classes per operating system and abstract classes that represent OS groups. For example class Fedora extends class Linux that extends class Unix that extends class OperatingSystem. We can enjoy all advantages of inheritance, so all common properties of Windows OS are stored in class Windows and can be overridden by its subclasses.

But now we cannot see all operating systems together, iterate over them etc., i.e. very useful features of Java enum are missing.
No problem! Now we can create enum like previous that holds custom field of type Class:

public enum OsType {
            WindowsNTWorkstation(WindowsNTWorkstation.class),
            WindowsNTServer(WindowsNTServer.class),
            Windows2000Server(Windows2000Server.class),
            Windows2000Workstation(Windows2000Workstation.class),
            WindowsXp(WindowsXp.class),
            WindowsVista(WindowsVista.class),
            Windows7(Windows7.class),
            Windows95(Windows7.class),
            Windows98(Windows98.class),
            Fedora(Fedora.class),
            Ubuntu(Ubuntu.class),
            Knopix(Knopix.class),
            SunOs(SunOs.class),
            HpUx(HpUx.class),
            ;
            private Class clazz;
            OsType(Class clazz) {
                this.clazz = clazz;
            }
}

This solution is better but it still has disadvantages:

1. Implementation of method that retrieves all "children" of specific OS (for example all Linux distributions) is hard and ineffective.
2. Grouping is separate from enum.
3. The solution is very verbose: each OS is represented by its own class even if the class has nothing to override.

Hierarchical Enum

To create hierarchy using enum we need custom field "parent" that is initialized by constructor:

public enum OsType {
    OS(null),
        Windows(OS),
            WindowsNT(Windows),
                WindowsNTWorkstation(WindowsNT),
                WindowsNTServer(WindowsNT),
            Windows2000(Windows),
                Windows2000Server(Windows2000),
                Windows2000Workstation(Windows2000),
            WindowsXp(Windows),
            WindowsVista(Windows),
            Windows7(Windows),
            Windows95(Windows),
            Windows98(Windows),
        Unix(OS) {
                @Override
                public boolean supportsXWindows() {
                    return true;
                }
            },
            Linux(Unix),
            AIX(Unix),
            HpUx(Unix),
            SunOs(Unix),
    ;
    private OsType parent = null;

    private OsType(OsType parent) {
        this.parent = parent;
    }
}

This structure allows implementation of method "is" that works like operator instanceof for classes and interfaces. For example Windows2000 is Windows, Fedora is Linux, Windows is not Unix etc.

public boolean is(OsType other) {
    if (other == null) {
        return false;
    }
   
    for (OsType t = this;  t != null;  t = t.parent) {
        if (other == t) {
            return true;
        }
    }
    return false;
}

Sometimes we need a method that returns all "children" of current nodes, e.g. all Linux systems or all variants of Windows2000. The easiest way to implement this is to hold collection of children per element and fill it from constructor:

private List<OsType> children = new ArrayList<OsType>();
private OsType(OsType parent) {
    this.parent = parent;
    if (this.parent != null) {
        this.parent.addChild(this);
    }
}

Now method "children()" that returns direct node's children is trivial:

public OsType[] children() {
    return children.toArray(new OsType[children.size()]);
}

It is not hard to implement recursive method "allChildren()" that returns all children of current node (see full source code). 

But hierarchy term is always accompanied by inheritance that allows overriding methods of parent. This is the basic feature of classes in all object oriented languages. Is it possible to implement a kind of inheritance relationship for elements of one enum?

 

Overriding parent's method

Unix systems support X Window graphical environment. MS Windows does not. We would like to be able to ask OS whether it supports X Window.

We can define boolean flag "supportsX" and boolean method

public boolean supportsX() {return suppotsX;}

Now we have to add yet another argument to OsType constructor and pass true/false for each element of the enum. But it is too verbose. Is it possible to say that Unix supports X, Windows does not support X and be sure that Fedora's supportX() returns true while Winddows95's supportX() returns false?

The implementation is pretty simple. First for simplicity let's say that X Window is supported by all Unix systems and is not supported by others.
So, we can implement method supportsXWindowSystem() at enum level as following:

public boolean supportsXWindowSystem() {
    return false;
}

Now we have to override it for all Unix systems. To implement this we change the default implementation to following:

public boolean supportsXWindowSystem() {
    return parent == null ? false : parent.supportsXWindowSystem();
}

The method of first parent in hierarchy that implements the method will be used. If no one of parents and parents of parents does not implement this method itself we call method of root element. 


Now we can say the following:

...
        Unix(OS) {
                @Override
                public boolean supportsXWindowSystem() {
                    return true;
                }
            },
            Linux(Unix),
            AIX(Unix),
            HpUx(Unix),
            SunOs(Unix),
...

The method is overridden for Unix element only and all its children will use this method.

The problem is solved. We got enum based hierarchical polymorphic structure! We can implement method in base element (using it like a super class) and then override it in any element we want.

The only disadvantage of this solution is that now we have to create similar implementation for each method we add to this enum and for all other enums that hold hierarchical structure. 

Conclusions

 
Although we are regular to use enums as some kind of static arrays they also can be used to present hierarchical tree-like data structures where each node can find its parent, its children and even inherit and override parent's method almost exactly as we do with class inheritance.

 

Acknowledgments

First version of this article has been written in my blog. Method supportsXWindowSystem() there was implemented using reflection. 4 guys discussed this solution and suggested me to simplify it. I would like to thank Todo, Anton Dumler, Nick and Johannes Schneider that helped me to improve the article.