Generics und Comparable

[Individuum]

Hey ich habe eine kurze Frage.

Wie kann ich Werte die generisch festgelget sind vergleichen.
Habe im Internet schon gelesen, dass das Comparable Interface in der compareTo Methode bei gleich 0 zurückgibt etc.
Die muss man aber ja erst schreiben, es ist ja ein Interface.

public class BTreeNode <T extends Number implements Comparable<BTreeNode> {

    public T value;

    public BTreeNode left;

    public BTreeNode right;

    /**
     * @param value
     */
    public BTreeNode(T value) {
        super();
        this.value = value;
    }

    public T getValue() {
        return value;
    }

    @Override
    public int compareTo(BTreeNode test) {
        if (test.value == value) {
            return 0;
        }
    }
}

}

Wenn ich jetzt in meiner Compare to Methode sagen will:
if (test.value < value) {
return -1;
}
funktioniert das wegen generics nicht.

Habt ihr eine Idee?

Liebe Grüße

 

[httpdigest]

Kannst du bitte erst einmal die Generics deiner Klassendefinition korrekt angeben?

public class BTreeNode <T extends Number implements Comparable<BTreeNode> { ... }

ist sicherlich nicht korrekt so.

Falls du einfach nur ein ">" nach "<T extends Number" vergessen hast und somit dein T ein Number ist, delegiere in deiner eigenen compareTo() einfach nach `value.compareTo(test.value)`, da dein T ja eben ein Number und somit auch ein Comparable<Number> ist.
EDIT: Obiges ist falsch! Number implementiert nicht Comparable!

 

[Individuum]

Hat sich erledigt, ich habe es jetzt so geschrieben.

public class BTree <T extends Comparable <T>>  {

    private BTreeNode root;

    public void insert(T value){
        if(root==null){
            this.root = new BTreeNode(value);
            return;
        }
        insert(root,value);
    }


    private void insert(BTreeNode node, T value) {
        if (node.value.compareTo(value) > 0) {
            // links
            if (node.left == null) {
                // hier einfuegen
                node.left = new BTreeNode<>(value);
                return;
            } else {
                // an Kindknoten delegieren
                insert(node.left, value);
            }

        } else if (node.value.compareTo(value) < 0) {
            // rechts
            if (node.right == null) {
                node.right = new BTreeNode<>(value);
                return;
            } else {
                insert(node.right, value);
            }
        } else {
            return;
        }
    }
}

was ich aber nicht verstehe: Wieso kann wenn ich Compareable als Interface implementiere und meine Klasse Numbers extends nicht vergleichen?

 

[httpdigest]

Wieso kann wenn ich Compareable als Interface implementiere und meine Klasse Numbers extends nicht vergleichen?

Was? Kannst du bitte Satzzeichen/Interpunktion verwenden, damit dieser Satz verständlich wird?

Was genau meinst du mit "vergleichen"? Wenn du ein `T extends Number` hast, dann habe ich dir bereits gezeigt, wie du das vergleichen kannst.

 

[Individuum]

Wieso kann ich, wenn ich Compareable als Interface implementiere und meine Klasse Numbers extends/erbt nicht vergleichen?

 

[httpdigest]

Ach sooo... entschuldige bitte, ich habe gedacht, Number wäre Comparable, aber das ist es ja gar nicht. Nur die konkreten Number-Subklassen sind Comparable. Number selbst kannst du nur dadurch vergleichen, dass du es in einen konkreten Primitivtyp wandelst, z.B. mit Number.toDouble().

 

[httpdigest]

Eine Möglichkeit wären Intersection Types in Java:

public class MeineKlasseMitNumber<T extends Number & Comparable<T>> implements Comparable<MeineKlasseMitNumber<T>> {
  T value;
  public int compareTo(MeineKlasseMitNumber<T> o) {
    return value.compareTo(o.value);
  }
}

Hier kann man nun alle Unterklassen von Number für T substituieren, da alle bisher existierenden Number-Subklassen (Integer, BigInteger, BigDecimal, Long, Double, ...) auch Comparable<SieSelbst> sind.

 

[Individuum]

Ah interessant, werde es damit auch probieren.

public class BTreeNode  <T> implements Comparable <BTreeNode>/* <T extends Comparable <T>> */ /*extends Number> implements Comparable<BTreeNode> */ {
    /*extends Number> implements Comparable<BTreeNode> */

    public Integer value;

    ////(node.value.compareTo(value) < 0)

    public BTreeNode left;
    public BTreeNode right;

    /**
     * @param value
     */
    public BTreeNode(Integer value) {
        super();
        this.value = value;
    }

    public Integer getValue() {
        return value;
    }

    @Override
    public int compareTo(BTreeNode t) {
        if (this.value > t.value) {
            return 1;
        }
        if (this.value < t.value) {
            return -1;
        }
        if (this.value == t.value) {
            return 0;
        }
        return 0;
    }
}

Was hälst du von diesem Code? Ist wenn ich es so schreibe irgendein unterschied zu meinem ersten, außer dass ich meiner Klasse für Value Integer geben muss?

 

[httpdigest]

Warum musst du Integer nehmen?

 

[Individuum]

Ich muss nicht aber bei einem Baum bietet es sich an. Ich nehme Integer weil ich das Interface implementieren muss.

 

[httpdigest]

Ich verstehe nicht, was die Nutzung von Integer mit einem Baum zu tun haben soll...
Mach das doch einfach so, wie ich gezeigt habe:

public class BTreeNode<T extends Number & Comparable<T>> implements Comparable<BTreeNode<T>> {
  private T value;
  private BTreeNode<T> left, right;
  ...
  public int compareTo(BTreeNode<T> o) {
    return value.compareTo(o.value);
  }
}

 

[httpdigest]

Und wenn man nur die totale Ordnung auf den Baumelementen definiert durch den in ihnen gespeicherten Werten haben möchte, braucht man genauer gesagt noch nicht einmal Number. Da reicht doch einfach nur <T extends Comparable<T>>.
Für den Baumknoten ist es völlig irrelevant, welchen konkreten Typ der im Baumknoten gespeicherte Wert hat. Einzig allein die Sortierung ist wichtig. Es könnte genausogut auch ein String oder eine java.net.URI sein.

 

[Individuum]

Sicher reicht es, jedoch müssen wir das Comparable Interface implementieren. Aber ich komme langsam auf den Trichter, danke für deine Mühen!

 

[httpdigest]

Dass du das Comparable Interface implementieren musst, hat doch damit überhaupt nichts zu tun. Natürlich kannst du das Comparable Interface implementieren (und das habe ich ja auch gemacht). Das streitet ja niemand ab und hat auch nichts damit zu tun, keinen konkreten Typ für den value zu verwenden, sondern einfach nur eine Typvariable T.

 

[mihe7]

Sicher reicht es, jedoch müssen wir das Comparable Interface implementieren.

Wenn Du Comparable implementieren musst, dann bezieht sich das wohl auf BTreeNode (übrigens ein besch... Name für einen binären Baum, ein B-Tree ist anders).

Es geht also darum, dass zwei BTreeNode-Instanzen miteinander verglichen werden können, d. h. Deine Klassendefinition die Form (Skizze)

public class  BTreeNode implements Comparable<BTreeNode>

hat.

Wenn Du für den Wert den Datentyp int verwendest, könntest Du schreiben:

    private int value;

    public int compareTo(BTreeNode node) {
        return value - node.value;
    }

Nun willst Du Dich aber für den Wert nicht auf einen bestimmten Typ festlegen, denn je nach Zweck können ganz unterschiedliche Datentypen in Frage kommen. Daher spendierst Du Deiner Klasse einen Typparameter T und erhältst erst einmal

public class  BTreeNode<T> implements Comparable<BTreeNode<T>>

Problem dabei ist, dass Du den Typ nicht kennst, d. h. für den Wert kannst Du (bzw. der Compiler) nur annehmen, dass es sich um irgendein Object handelt. Somit könnte für den Wert auch ein Typ verwendet werden, auf dem keine Ordnung definiert ist. Die einzige Möglichkeit, die Du dann hast, ist auf Gleichheit zu prüfen, was für den Baum nicht ausreichend ist.

Code:

    private T value;
    public int compareTo(BTreeNode<T> node) {
        // wie sollen value und node.value miteinander verglichen werden?!?
    }

D. h. Du willst einen Typ T haben, der einen Vergleich zwischen zwei Objekten vom Typ T zulässt. Das funktioniert wieder über das Comparable-Interface:

public class  BTreeNode<T implements Comparable<T>> implements Comparable<BTreeNode<T>>

Jetzt kennst Du zwar den genauen Typ von T immer noch nicht aber Du (bzw. der Compiler) weißt, dass es sich um einen Typ handelt, der Comparable<T> implementiert, so dass Du jetzt schreiben kannst:

    private T value;
    public int compareTo(BTreeNode<T> node) {
        return value.compareTo(node.value);
    }