How to design many-to-many relationships on deletion?

Question

I'm creating a canvas drawing with 2 objects: Rectangles, and Lines connecting the Rectangles. Each Line should be aware of the 2 Rectangles it connects. Every Rectangle can have multiple lines that connect it to other Rectangles.

class Rectangle {
    List<Line> connections;
    void setConnection(Line line) {
        connections.add(line);
    }
}

class Line {
    Rectangle from, to;

    public Line(Rectangle from, Rectangle to) {
        this.from = from;
        this.to = to;

        from.setConnection(this);
        to.setConnection(this);
    }
}

I feel this might not be a good design, because when I delete a Line, I will also have to delete the Line from the connections list in the Rectangle it connects.

When I delete a Rectangle, I also have to remove the Lines that are connected to the rectangle, as they should not exist without. Therefore I have to iterate through all connections of the deletable Rectangle, and for each connection get the from/to rectangle, and there again get the connection list and remove the Line reference.

My problem is not to write that code (I already have it working), but it seems to me I'm doing a lot of back-and-forth references.

Can this be done better? Somehow: if a rectangle is deleted, then all deep connections from the lines are removed/invalidated automatically? Something similar to Hibernate's many-to-many cascading? I can't just use Hibernate because this is supposed to be a client side app, without a database.

Answer 1

Essentially you are building graphs. You will need to separate the edges from the vertices.

Let's start by creating some interfaces that separate some concerns:

interface Shape {
}

interface ShapeConnection {
    Shape[] getConnectedShapes();
}

Then let's introduce an annotation that will mark shapes that need to cascade delete their connected shapes.

@interface CascadeDeleteConnectedShapes {
}

Rectangle and Line can then be defined as:

@CascadeDeleteConnectedShapes
class Rectangle implements Shape {

}

class Line implements Shape, ShapeConnection {
    Rectangle from, to;

    public Line(Rectangle from, Rectangle to) {
        this.from = from;
        this.to = to;
    }

    @Override
    public Shape[] getConnectedShapes() {
        return new Shape[] { from, to };
    }
}

Finally, you will need a place where you can put it all together.

class Canvas {
    private ConnectionManager connectionManager = new ConnectionManager();

    private Set<Shape> shapes = new HashSet<Shape>();

    public Canvas() {
    }

    public void removeShape(Shape shape) {
        if (!shapes.remove(shape))
            return; 

        if (shape.getClass().isAnnotationPresent(CascadeDeleteConnectedShapes.class)) {
            cascadeDeleteShape(shape);
        }

        if (shape instanceof ShapeConnection) {
            connectionManager.remove((ShapeConnection) shape);
        }
    }

    private void cascadeDeleteShape(Shape shape) {
        List<ShapeConnection> connections = connectionManager.getConnections(shape);
        for (ShapeConnection connection : connections) {
            if (connection instanceof Shape) {
                this.removeShape((Shape) connection);
            } else {
                connectionManager.remove(connection);
            }
        }
    }

    public void addShape(Shape shape) {
        if (shapes.contains(shape))
            return;

        if (shape instanceof ShapeConnection) {
            addShapeConnection((ShapeConnection) shape);
        }

        shapes.add(shape);
    }

    private void addShapeConnection(ShapeConnection shapeConnection) {
        for (Shape shape : shapeConnection.getConnectedShapes()) {
            if (!shapes.contains(shape))
                throw new Error("cannot connect unknown shapes");
        }
        connectionManager.add(shapeConnection);
    }
}

A shape can be a shape connection at the same time. Once a few rectangles are added to the canvas, lines can be added to connect them. Since a line in your design is recognized as a ShapeConnection any operation involving the line will invoke the Canvas to let the ConnectionManager handle the graph. In this design it is important that Line is immutable.

Cascades are triggered by the removal of an annotated shape. You'll need to manage these cascades carefully: if an exception occurs somewhere along the way you are left with an incomplete graph.

This code only serves to give you an idea. Also I'm leaving the implementation of the connection manager to your imagination. Guava has been mentioned in one of the comments. A BiMultiMap would have served your purpose just right, too bad they haven't released it yet. In any case, I would certainly have a look at letting the specifics of the ConnectionManager be handled by an existing library; many have been written that will fit your needs.

Note that there are no circular dependencies in this design.