Conceptual inheritance implementation

Question

Hi there,

I'm writing a spatial data structure and I have a doubt about what's the best NODE implementation. According to my design I have an abstract node entity and three classes which inherit from it: EMPTYNODE, FULLNODE, INTERNALNODE.

The first one has no particular data.

The second one has 1 reference to a generic element.

The third one has 2 references to other nodes.

I have found several ways to implement this situation (that I have already coded) but I can't decide what's the best.

The first solution that I have found is to use a single class Node that potentially performs all the operation in this way:

private static class Node {
    private Elem elem = null;
    private Node left = null, right = null;
    public Elem getElem() {
        assert isFull();
        return elem;
    }

    public boolean isEmpty() {
        return elem == null && left == null;
    }

    public boolean isFull() {
        return  elem != null;
    }


    public boolean isInternal() {
        return elem == null && left != null;
    }
}

The second solution is to write an explicit division by classes where every class offers only its methods. Obviously in this way we are obliged to perform several casts to the node objects.

private static abstract class Node {

    public abstract boolean isEmpty();

    public abstract boolean isFull();

    public abstract boolean isInternal();

}


private static class FullNode extends Node{

    private ITriangle elem;

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public final boolean isFull() {
        return true;
    }

    @Override
    public final boolean isInternal() {
        return false;
    }

    public Elem getElem() {
        return elem;
    }
}

The third one solution is to use the inheritance allowing every classes to offer all the methods, but the object type should by check by "isEmpty()" and similar methods. In case of wrong call we'll throw an exception.

private static abstract class Node {

    public abstract boolean isEmpty();

    public abstract boolean isFull();

    public abstract boolean isInternal();

    public abstract Elem getElem();

}


private static class Empty extends Node{

    @Override
    public boolean isEmpty() {
        return true;
    }

    @Override
    public final boolean isFull() {
        return false;
    }

    @Override
    public final boolean isInternal() {
        return false;
    }

    @Override
    public Elem getElem() {
        throw new AssertionError();
    }
}

What do you think about these three solutions?

Which one would you use?

Any other ideas?

Thanks for your help. Every idea will be appreciated.

Answer 1

The answer would depend on how the nodes are used. Once a node is created would it ever need to change from empty to internal to full, or is it immutable?

From the options given if a node is immutable then I'd go for option 3 if you're expecting the internal state to change then I'd go with option 1.

If you wanted a mutable node where the behaviour would change I'd look at using a Node class to hold the data with an enumeration to hold the states, the node would then delegate to the appropriate enumeration for it's implementation. For example:

public class Node {

   private enum NodeState {
      /* each state overrides specific methods to implement custom behaviour */
      FULL { public boolean isFull() { return true; } },
      INTERNAL { public boolean isInternal() { return true; } },
      EMPTY { public boolean isEmpty() { return true; } };

      /* the default behaviour */
      public boolean isFull() { return false; }
      public boolean isEmpty() { return false; }
      public boolean isInternal() { return false; }
   }

   private NodeState state = NodeState.EMPTY;
   private Elem      elem  = null;
   private Node      left  = null, right = null;

   public Elem getElem() {
      assert isFull();
      return elem;
   }

   /* TODO: constructors/mutators implement state changes go here */

   public boolean isEmpty() {
      return state.isEmpty();
   }

   public boolean isFull() {
      return state.isFull();
   }

   public boolean isInternal() {
      return state.isInternal();
   }
}

class Elem {
   /* implementation of this class */
}