Soll ich beim Hinzufügen eines neuen Elements klonen? Wann sollte geklont werden?

Question

Ich möchte in Java eine Klasse für den Umgang mit Graph Datenstrukturen implementieren. Ich habe eine Knoten-Klasse und eine Edge-Klasse. Die Graph-Klasse verwaltet zwei Listen: eine Liste von Knoten und eine Liste von Kanten. Jeder Knoten muss einen eindeutigen Namen haben. Wie schützen ich gegen eine Situation wie folgt aus:

Graph g = new Graph(); 

Node n1 = new Node("#1"); 
Node n2 = new Node("#2"); 

Edge e1 = new Edge("e#1", "#1", "#2"); 

// Each node is added like a reference 
g.addNode(n1); 
g.addNode(n2); 
g.addEdge(e1); 

// This will break the internal integrity of the graph 
n1.setName("#3"); 
g.getNode("#2").setName("#4"); 

Ich glaube, sollte ich die Knoten klonen und die Kanten, wenn sie zu dem Graphen hinzugefügt und eine NodeEnvelope Klasse zurückgeben, die das Diagramm strukturelle Integrität beibehalten wird . Ist dies der richtige Weg, oder ist das Design von Anfang an gebrochen?

Answer 1

Ich arbeite viel mit Graph-Strukturen in Java, und mein Rat wäre, jedes Datenelement der Node- und Edge-Klasse zu machen, von der der Graph abhängt, um seine Struktur final ohne Setter zu erhalten. In der Tat, wenn Sie können, würde ich Node und Edge komplett unveränderlich machen, was many benefits hat.

So zum Beispiel:

public final class Node { 

    private final String name; 

    public Node(String name) { 
      this.name = name; 
    } 

    public String getName() { return name; } 
    // note: no setter for name 
} 

würden Sie dann Ihre Einzigartigkeit Prüfung im Objekt Diagramm tun:

public class Graph { 
    Set<Node> nodes = new HashSet<Node>(); 
    public void addNode(Node n) { 
     // note: this assumes you've properly overridden 
     // equals and hashCode in Node to make Nodes with the 
     // same name .equal() and hash to the same value. 
     if(nodes.contains(n)) { 
      throw new IllegalArgumentException("Already in graph: " + node); 
     } 
     nodes.add(n); 
    } 
} 

Wenn Sie einen Namen eines Knotens ändern müssen, entfernen Sie den alten Knoten und füge ein neues hinzu. Das hört sich vielleicht nach zusätzlicher Arbeit an, aber es spart viel Mühe, alles in Ordnung zu halten.

Wirklich, obwohl, das Erstellen Ihrer eigenen Graph-Struktur von Grund auf ist wahrscheinlich unnötig - dieses Problem ist nur die erste von vielen, denen Sie wahrscheinlich begegnen, wenn Sie Ihre eigenen bauen.

Ich würde empfehlen, eine gute Open-Source-Java-Graph-Bibliothek zu finden, und stattdessen verwenden. Abhängig von dem, was Sie tun, gibt es ein paar Möglichkeiten da draußen. Ich habe JUNG in der Vergangenheit verwendet und würde es als einen guten Ausgangspunkt empfehlen.

Answer 2

Meiner Meinung nach sollten Sie das Element nie klonen, es sei denn Sie explizit angeben, dass Ihre Datenstruktur das tut.

Die gewünschte Funktionalität der meisten Dinge benötigt das tatsächliche Objekt in die Datenstruktur by-Verweis übergeben werden.

Wenn Sie die Node Klasse sicherer machen wollen, machen Sie es zu einer inneren Klasse des Graphen.

Answer 3

Es ist mir nicht klar, warum Sie die zusätzliche Indirektion der String-Namen für die Knoten hinzufügen. Wäre es nicht sinnvoller, wenn die Signatur Ihres Edge-Konstruktors etwa public Edge(String, Node, Node) anstelle von public Edge (String, String, String) wäre?

Ich weiß nicht, wo Klon Ihnen hier helfen würde.

ETA: Wenn die Gefahr entsteht, dass der Knotenname nach dem Erstellen des Knotens geändert wird, geben Sie IllegalOperationException ein, wenn der Client versucht, setName() auf einem Knoten mit einem vorhandenen Namen aufzurufen.

Answer 4

Zusätzlich zu den Kommentaren von @ jhkiley.blogspot.com können Sie eine Factory für Edges and Nodes erstellen, die das Erstellen von Objekten mit einem bereits verwendeten Namen verweigert.

Answer 5

Verwenden von NodeEnvelopes oder Edge/Node Factories klingt wie Overbesign für mich.

Möchten Sie wirklich eine Methode setName() auf Knoten verfügbar machen? Es gibt nichts in Ihrem Beispiel, das vorschlägt, dass Sie das brauchen. Wenn Sie sowohl Ihre Node- als auch Ihre Edge-Klasse unveränderlich machen, werden die meisten Szenarien für die Integritätsverletzung, die Sie sich vorstellen, unmöglich. (Wenn sie veränderbar sein sollen, aber nur bis sie einem Graph hinzugefügt werden, können Sie dies durch ein isInGraph-Flag in Ihren Node/Edge-Klassen erzwingen, das von Graph.Add {Node, Edge} und auf true gesetzt ist Lassen Sie Ihre Mutatoren eine Ausnahme auslösen, wenn sie nach dem Setzen dieses Flags ausgelöst wird.)

Ich stimme mit jhkiley überein, dass das Übergeben von Node-Objekten an den Edge-Konstruktor (anstelle von Strings) wie eine gute Idee klingt.

Wenn Sie einen aufdringlicheren Ansatz wünschen, können Sie einen Zeiger von der Node-Klasse zurück zum Graphen haben, in dem er sich befindet, und das Diagramm aktualisieren, wenn sich kritische Eigenschaften (z. B. der Name) des Node ändern. Aber ich würde das nicht tun, es sei denn, Sie sind sicher, dass Sie in der Lage sein müssen, die Namen bestehender Knoten zu ändern, während Kantenbeziehungen erhalten bleiben, was unwahrscheinlich erscheint.

Answer 6

Object.clone() hat einige schwerwiegende Probleme, und in den meisten Fällen wird davon abgeraten. Eine vollständige Antwort finden Sie unter Punkt 11, "Effective Java" von Joshua Bloch. Ich glaube, Sie können Object.clone() problemlos auf primitiven Array-Typen verwenden, aber abgesehen davon müssen Sie vernünftig sein, Clone richtig zu verwenden und zu überschreiben. Sie sollten wahrscheinlich einen Kopierkonstruktor oder eine statische Factory-Methode definieren, die das Objekt explizit nach Ihrer Semantik klont.