[java] API bug bij converteren TreeSet naar ArrayList

[Verbal Kint]

Uit een (automatisch gesorteerd) lijstje vluchten wil ik soms weten wat de volgende vlucht is, gegeven een vlucht uit de lijst:

Java:

Public class FlightList extends TreeSet
{

   public Flight next(Flight last)
    {
        if (!this.contains(last))
        {
            System.out.println("Treeset does not contain " + last);
            
        }
        if (this.last().equals(last))
        {
            return null;
        }
        ArrayList list = new ArrayList(this);
        if (!list.contains(last))
        {
            System.out.println("Arraylist does not contain " + last);
        }
        return (Flight) list.get(list.indexOf(last) + 1);
    }
}

Maar wat gebeurd er nu:

code:

console:
Arraylist does not contain [(..aFlight..)]

Hoe is dit nu mogelijk? Het betreffende element zit wél in de TreeSet flightList (this), maar niet in de ArrayList list die is opgebouwd uit de elementen van flightList? Als ik de inhoud van beide lijstjes naar de console print zie ik geen verschil, ik zie ook in beide lijstjes het gevraagde element. Toch geeft de eerste contains() true en de tweede false. Is dit een bug in mijn Java (j2re1.4.2_04) of doe ik zelf iets verkeerd?

[Alarmnummer]

Vreemd idd.. kan je de equals van Flight eens laten zien? (hash dito (alhoewel de hashcode niet wordt gebruikt in de treeset geloof ik).

[ Voor 33% gewijzigd door Alarmnummer op 24-08-2004 17:02 ]

[Verwijderd]

Je zou even moeten kijken of je contains methode by reference OF by value werkt. Dat zou een hoop verklaren. Ook de manier waarop je de kopie van de lijst maakt moet je even nakijken, een shallow copy OF een deep copy.

Succes

[Verwijderd]

Ff snel getest....
Bij mij werkt ie gewoon:

code:

package nl.test;

import java.util.ArrayList;
import java.util.TreeSet;

public class FlightList extends TreeSet {

    public Flight next(Flight last) {
        if (!this.contains(last)) {
            System.out.println("Treeset does not contain " + last);

        }
        if (this.last().equals(last)) {
            return null;
        }
        ArrayList list = new ArrayList(this);
        if (!list.contains(last)) {
            System.out.println("Arraylist does not contain " + last);
        }
        return (Flight) list.get(list.indexOf(last) + 1);
    }
    
    public static void main(String args[]) {
        
        FlightList list = new FlightList();
        for (int i = 0; i < 10; i++) {
            Flight f = new Flight(i);
            list.add(f);
        }
        
        Flight firstFlight = (Flight) list.first();
        System.out.println("First Flight in Treeset: " + firstFlight);
        System.out.println("Next to firstFlight: " + list.next(firstFlight));
        
    }
}

code:

/*
 * Created on Aug 24, 2004
 * Author: Harm de Laat
 */
package nl.test;


/**
 * @author HaLa
 * 
 */
public class Flight implements Comparable {
    private int n;
    
    public Flight(int n) {
        this.n = n;
    }
    
    public int getN() {
        return n;
    }
    
    public boolean equals(Object f) {
        return ((Flight) f).getN() == n;
    }

     /* (non-Javadoc)
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    public int compareTo(Object o) {
        Flight compare = (Flight) o;
        if (compare.getN() < n) {
            return -1;
        } else if (compare.getN() > n) {
            return 1;
        } else {
            return 0;
        }
    }
    
    public String toString() {
        return "Flight: " + n;
    }
   
}

Output:

code:

First Flight in Treeset: Flight: 9
Next to firstFlight: Flight: 8

[ Voor 13% gewijzigd door Verwijderd op 24-08-2004 17:27 ]

[zneek]

Hoe is je Flight implementatie? Zoals razor_harm? (met natuurlijke meer zinnige velden )

[Verwijderd]

zneek schreef op 24 augustus 2004 @ 17:31:
Hoe is je Flight implementatie? Zoals razor_harm? (met natuurlijke meer zinnige velden )

Jah... Dat heb ik ook maar gegokt

[Robtimus]

Verwijderd schreef op 24 augustus 2004 @ 17:25:

Java:

/*
 * Created on Aug 24, 2004
 * Author: Harm de Laat
 */
package nl.test;


/**
 * @author HaLa
 * 
 */
public class Flight implements Comparable {
    private int n;
    
    public Flight(int n) {
        this.n = n;
    }
    
    public int getN() {
        return n;
    }
    
    public boolean equals(Object f) {
        return ((Flight) f).getN() == n;
    }

     /* (non-Javadoc)
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    public int compareTo(Object o) {
        Flight compare = (Flight) o;
        if (compare.getN() < n) {
            return -1;
        } else if (compare.getN() > n) {
            return 1;
        } else {
            return 0;
        }
    }
    
    public String toString() {
        return "Flight: " + n;
    }
   
}

Je moet je eigenlijk schamen: wel equals overriden maar niet hashCode...

Uit de API:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

Dat is in dit geval dus niet waar. Dat het werkt komt omdat je een TreeSet descendant gebruikt en geen HashSet.

[zneek]

Je kunt ipv de Comparable interface implementeren toch ook een aparte Comparator class gebruiken? Dan heb je niet dat probleem met equals en hashcode overriden.

[Robtimus]

zneek schreef op 24 augustus 2004 @ 19:28:
Je kunt ipv de Comparable interface implementeren toch ook een aparte Comparator class gebruiken? Dan heb je niet dat probleem met equals en hashcode overriden.

Ja dat kan, maar dat zijn 2 losstaande problemen. Een equals heb je nml vaak voor andere doeleinden nodig.

Maar misschien is het probleem idd iets met de Comparable. De TreeSet slaat geen 2 objecten op als de compareTo 0 returnt:

...but a TreeSet instance performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the set, equal.

En zoals iedereen weet slaat een set geen 2 dezelfde waarden op.


De contains van de ArrayList gebruikt equals, de contains van TreeSet compareTo van de objecten of compare van de comparator.
Dus misschien zijn de compareTo en equals/hashCode niet consistent.

[Verbal Kint]

Het vreemdste van dit alles is dat het probleem min of meer random optreedt. Dit is natuurlijk erg frustrerend. In mij app zitten zo'n 50 FlightLists die elk weer minstens 40 Flights bevatten. De next() method wordt veelvuldig aangesproken en geeft schijnbaar willekeurig null pointer exceptions.

De contains van de ArrayList gebruikt equals, de contains van TreeSet compareTo van de objecten of compare van de comparator.
Dus misschien zijn de compareTo en equals/hashCode niet consistent.

Een interessante opmerking. Echter, compareTo() en equals() zijn niet overidden, de inhoud van de collections is exact gelijk (de arrayList krijgt alle pointers in zijn construtor mee) en, de belangrijkste, het probleem treedt dus willekeurig op, met steeds andere Flights op steeds andere FlightLists.

[Verwijderd]

kan je niet beter een composer-class schrijven dan treeSet extenden?

[Verbal Kint]

Ik heb de Javadoc er nog even op nageslagen:

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

..en dit geldt zowel voor de TreeSet (Set) als de ArrayList (List). contains() zou dus op beide collections altijd dezelfde uitkomsten moeten geven. Voor de volledigheid nog even equals():

The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true).

Flight heeft geen eigen equals implementatie, dus dat zou ook niet voor problemen mogen zorgen.

[Janoz]

Als je niet zelf een equals methode geschreven hebt zou het kunnen zijn dat je kopies vergelijkt. De elementen in een set zijn inmutable. Het zou dus best kunnen zijn dat je een kopie terug krijgt uit de set. Deze is, ondanks dezelfde vulling, niet meer gelijk aan de orginele Flight, tenzij je de equals methode zelf implementeerd.

[ Voor 5% gewijzigd door Janoz op 25-08-2004 09:44 ]

[Macros]

Ik heb de TreeSet.contains er op nageslagen, en die is niet gebaseerd op .equals(), maar alleen maar op compare(). Als .compare() 0 is tussen het object dat je zoekt en dat hij vind, dan checked hij niet op equals() maar returned dat object meteen.

[Alarmnummer]

Post dus daarom je compare functie en je equal functie. Dan zien we snel genoeg wat er aan de hand is.

[Macros]

Een equals functie had hij niet, dat zal het probleem dus zijn...
Wel leuk als je een contains() doet op een ArrayList terwijl je weet dat het het laatste object is, dan heb je meteen altijd worst case performance

[Robtimus]

Macros schreef op 25 augustus 2004 @ 09:44:
Ik heb de TreeSet.contains er op nageslagen, en die is niet gebaseerd op .equals(), maar alleen maar op compare(). Als .compare() 0 is tussen het object dat je zoekt en dat hij vind, dan checked hij niet op equals() maar returned dat object meteen.

Het "leuke" is dus dat er wel degelijk een fout zit in de API!

De specificatie van TreeSet.contains:

Returns true if this set contains the specified element.

Specified by:
contains in interface Set

Set.contains:

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

Maar zoals wij beiden hadden opgemerkt werkt de contains van TreeSet niet met equals maar met Comparator.compare of Comparable.compareTo! Dus de specificatie van TreeSet.contains is fout!

Maar dus even een advies voor TS: schrijf zelf een equals, hashCode en compareTo, volgens de specificaties. Dus als o1.equals(o2), dan o1.hashCode() == o2.hashCode() en o1.compareTo(o2) == o2.compareTo(o1) == 0, en als !o1.equals(o2) dan o1.compareTo(o2) != 0 en o2.compareTo(o1) != 0.

[Janoz]

Natuurlijk. Een treeset gebruikt compare aangezien het in een boom is opgeslagen. Waarschijnlijk heeft de TS wel compare geimplementeerd die wel aangeeft waneer iets gelijk is terwijl equals dat niet vindt.

Mocht de TS compare ook niet hebben geimplementeerd dan snap ik weinig van zijn code. Op dat moment is de volgorde helemaal niet meer gegarandeerd immers en is het gebruik van een treeset sowieso onzin.

Sowieso kun dit veel netter. Het is een beetje suf om de gehele inhoud van de tree om te zetten naar een lijst en vervolgens deze lijst doorlopen om het volgende element op te halen.

[Macros]

Nee, het is geen bug. De persoon die de Comparable interface implementeerd moet zich houden aan de specificaties. Doet hij dat dan werkt het gewoon. Doet hij dat niet, dan werkt het niet en is het geen bug in de API.

[Verbal Kint]

Macros schreef op 25 augustus 2004 @ 09:44:
Ik heb de TreeSet.contains er op nageslagen, en die is niet gebaseerd op .equals(), maar alleen maar op compare(). Als .compare() 0 is tussen het object dat je zoekt en dat hij vind, dan checked hij niet op equals() maar returned dat object meteen.

Als ik hier kijk: http://java.sun.com/j2se/...ontains(java.lang.Object) dan wordt ik voor contains doorverwezen (is specified by) naar: http://java.sun.com/j2se/...ontains(java.lang.Object) en daar staat toch dat equals() gebruikt wordt voor de vergelijking en niet compare()? Welke documentatie gebruik jij?

edit:

dat is grappig, iemand was me al voor met dit verhaal. Ik zal even de conclusie op me in laten werken

[ Voor 8% gewijzigd door Verbal Kint op 25-08-2004 10:18 ]

[Janoz]

Volgens de api hoor je je comparable zo te implementeren dat

x.compare(y)==0

geldt dan en slechts dan als

x.equals(y)==true

geldt.

Als dit niet het geval is dan kun je de api moeilijk de schuld geven. Sowieso zou compare intern weer equals moeten gebruiken. Het is in principe erg logisch dat er voor een treeset een compareTo nodig is aangezien het anders geen enkele zin heeft om een tree te gebruiken.

@TS : Macros kijkt in de source

[ Voor 18% gewijzigd door Janoz op 25-08-2004 10:22 ]

[Verbal Kint]

Mijn comparator voor FlightList:

Java:

public class FirstOutComparator implements Comparator
{
    /**
     * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
     */
    public int compare(Object o1, Object o2)
    {
        if (o1 instanceof Flight && o2 instanceof Flight)
        {
            return this.compare((Flight) o1, (Flight) o2);
        }
        System.out.println("Error! comparing " + o1.getClass() + " with "
                + o2.getClass());
        throw new IllegalArgumentException("Cannot use comparator to compare "
                + o1 + " and " + o2);
    }

    
    /**
     * compares 2 flight based on their scheduled arrival time.
     * 
     * @param f1 the first flight
     * @param f2 the second flight
     * @return -1,0,1
     */
    private int compare(Flight f1, Flight f2)
    {
        double std1 = f1.getScheduledTimeDeparture();
        double std2 = f2.getScheduledTimeDeparture();
        if (std1 != std2)
        {
            return new Double(std1).compareTo(new Double(std2));
        }
        return f1.getFlightNumber().compareTo(f2.getFlightNumber());
    }
}

Deze comparator geeft dus nooit een 0 terug, de reden daarvoor is dat altijd exact dezelfde volgorde in de elementen moet zitten, ook als twee vluchten dezelfde STD hebben. Als nu deze comparator wordt gebruikt voor contains() dan zou je dus altijd false moeten krijgen. Dat gebeurd niet (zie console). OK, nu lijken we wel iets op het spoor inderdaad! Ik zal de compare nog wat scherper maken. In principe is het onmogelijk dat je een gelijke STD (datum + tijd) en vluchtnummer hebt, maar je weet maar nooit....

Sowieso kun dit veel netter. Het is een beetje suf om de gehele inhoud van de tree om te zetten naar een lijst en vervolgens deze lijst doorlopen om het volgende element op te halen.

Wat zou jou oplossing zijn?

[ Voor 19% gewijzigd door Verbal Kint op 25-08-2004 10:42 ]

[paulh]

Argh wat lelijk, een treeset extenden Ga eens gauw een wrapper class maken.

[Janoz]

Je moet een goed onderscheid maken tussen of vluchten gelijk aan elkaar zijn of vlucht objecten gelijk aan elkaar zijn. De comparator zou 0 terug moeten geven als het object op dezelfde vlucht slaat.

Gelukkig gebeurt dat (ondanks dat je zegt van niet) gewoon aangezien het vlucht object gewoon in de treeset gevonden wordt (Als vertrektijd en flightnumber overeen komen).

Hoe ik het zou doen? Ik denk zo:

Java:

public Flight next(Flight last)
{
   return this.tailSet(last).first();
}

[Verbal Kint]

Janoz schreef op 25 augustus 2004 @ 10:46:
Je moet een goed onderscheid maken tussen of vluchten gelijk aan elkaar zijn of vlucht objecten gelijk aan elkaar zijn. De comparator zou 0 terug moeten geven als het object op dezelfde vlucht slaat.

Gelukkig gebeurt dat (ondanks dat je zegt van niet) gewoon aangezien het vlucht object gewoon in de treeset gevonden wordt (Als vertrektijd en flightnumber overeen komen).

Elke vlucht is een object, dezelfde vlucht == hetzelfde object. Mijn comparator was nog niet verfijnd genoeg, STD + vluchtnummer hoeft niet uniek te zijn in het geval van onderhoud (en zo zie je altijd wle iets over het hoofd..).

Mijn probleem zou dan nog steeds niet hebben opgetreden als contains() voor de TreeSet equals() gebruikte, zoals in de API staat. Natuurlijk blijft het mijn verantwoordelijkheid om er in de comparator voor te zorgen dat compare=0 == equals(), waarmee het onderscheid te niet wordt gedaan, maar dan nog zou het denk ik beter zijn als de API zou zeggen dat contains() op zoek gaat naar compare=0 ipv equals(), dit is tenslotte wat er feitelijk gebeurd.

Hoe ik het zou doen? Ik denk zo:

Java:

public Flight next(Flight last)
{
   return this.tailSet(last).first();
}

Dit zit er op het eerste gezicht sneller uit dan mijn code, ik heb het next() stukje gecopieerd van code van iemand anders, iemand die ik met Java veel hoger aansla dan mijzelf, vandaar dat ik niet verder heb gekeken naar een andere manier. Bedankt in ieder geval, ik zal het eens testen.

[Janoz]

Verbal Kint schreef op 25 augustus 2004 @ 11:20:
[...]
Elke vlucht is een object, dezelfde vlucht == hetzelfde object. Mijn comparator was nog niet verfijnd genoeg, STD + vluchtnummer hoeft niet uniek te zijn in het geval van onderhoud (en zo zie je altijd wle iets over het hoofd..).

Nogmaals. Dat een vlucht maar 1 keer bestaat betekend niet dat een vlucht object maar 1 keer bestaat. Als immers een vlucht dubbel wordt ingevuld zijn dat binnen jou applicatie twee losse vluchten. Ook als je een beetje aan het heen en weer kopieren bent zou het aantal vluchten plots kunnen verdubbelen. Het is zelfs dit dat er voor zorgt dat je appliactie niet werkt zoals je wilt. Zie onderaan

Een vlucht object in je code zou gelijk kunnen zijn aan een ander vlucht object waneer ze naar dezelfde vlucht verwijzen. Het is heel belangrijk dat dit kan zodat je ook daadwerkelijk kunt garanderen dat van elke vlucht er maar 1 voorkomt!

Mijn probleem zou dan nog steeds niet hebben opgetreden als contains() voor de TreeSet equals() gebruikte, zoals in de API staat. Natuurlijk blijft het mijn verantwoordelijkheid om er in de comparator voor te zorgen dat compare=0 == equals(), waarmee het onderscheid te niet wordt gedaan, maar dan nog zou het denk ik beter zijn als de API zou zeggen dat contains() op zoek gaat naar compare=0 ipv equals(), dit is tenslotte wat er feitelijk gebeurd.

Ten eerste staat bij compare duidelijk dat X.compare(Y)==0 hetzelfde resultaat op zou moeten leveren als X.equals(Y). De structuur van een tree maakt het onmogenlijk om enkel met equal te gebruiken om een element op te zoeken.

Sowieso gaat je code niet fout op die compare. Je code gaat fout omdat de vlucht in de list niet gevonden wordt! En dat heeft alles te maken met het feit dat jij vind dat twee vlucht objecten nooit gelijk aan elkaar zijn. Daardoor kan een element nooit gevonden worden omdat het gezochte element immers nooit gelijk is aan een element in de lijst volgens je eigen definitie.

[ Voor 3% gewijzigd door Janoz op 25-08-2004 11:54 ]

[Macros]

Iemand stipte dit al kort aan. Je kan beter niet een Collection class extenden (behalve de abstract versies dan). Waarom? Omdat je nu in je Flight set gewone objecten kan doen. Als je een wrapper class maakt, dan kan je er alleen Flight objecten in doen. Ook verberg je zo methodes in TreeSet die onzinnig zijn in jouw geval. (Dat zijn dus alle methoden die mutaties op de Set aanbrengen met standaard Objecten ipv. Flight objecten).

[Verbal Kint]

Janoz schreef op 25 augustus 2004 @ 11:52:
[...]

Nogmaals. Dat een vlucht maar 1 keer bestaat betekend niet dat een vlucht object maar 1 keer bestaat. Als immers een vlucht dubbel wordt ingevuld zijn dat binnen jou applicatie twee losse vluchten. Ook als je een beetje aan het heen en weer kopieren bent zou het aantal vluchten plots kunnen verdubbelen. Het is zelfs dit dat er voor zorgt dat je appliactie niet werkt zoals je wilt. Zie onderaan

Een vlucht object in je code zou gelijk kunnen zijn aan een ander vlucht object waneer ze naar dezelfde vlucht verwijzen. Het is heel belangrijk dat dit kan zodat je ook daadwerkelijk kunt garanderen dat van elke vlucht er maar 1 voorkomt!

Volgens mij bedoelen we hetzelfde, maar praten we wat langs elkaar heen. Vluchten (vluchtobjecten) worden bij de initialisatie geparsed, er komen er nooit bij en er gaan er nooit af. De diverse verwijzingen naar deze vluchtobjecten (zoals op vluchtlijstjes en toegekende vluchten aan vliegtuigen) veranderen wel. Dit is waar het probleem optrad, ik dacht dat er een inconsistentie zat in die verwijzingen (wat natuurlijk onmogelijk is), maar dat bleek dus aan de contains() implementaties te liggen.

[...]

Ten eerste staat bij compare duidelijk dat X.compare(Y)==0 hetzelfde resultaat op zou moeten leveren als X.equals(Y). De structuur van een tree maakt het onmogenlijk om enkel met equal te gebruiken om een element op te zoeken.

(..)

Dat is waar, maar dat staat bij Comparator, niet bij TreeSet. Een vermelding hiervan bij TreeSet zou wel zou duidelijk zijn. Ik denk overigens dat het wel mogelijk is om alleen met equals een element in een Tree te vinden, maar dat geeft wel een enorme performancedrop, namelijk op de manier die ik ook al toepaste; de Tree eerst omzetten naar een Array.

[Janoz]

Verbal Kint schreef op 25 augustus 2004 @ 12:45:
[...]
Volgens mij bedoelen we hetzelfde, maar praten we wat langs elkaar heen. Vluchten (vluchtobjecten) worden bij de initialisatie geparsed, er komen er nooit bij en er gaan er nooit af. De diverse verwijzingen naar deze vluchtobjecten (zoals op vluchtlijstjes en toegekende vluchten aan vliegtuigen) veranderen wel. Dit is waar het probleem optrad, ik dacht dat er een inconsistentie zat in die verwijzingen (wat natuurlijk onmogelijk is), maar dat bleek dus aan de contains() implementaties te liggen.

Je hebt ook wel gelijk dat er telkens maar 1 vlucht is, maar dat betekend niet dat je er maar van uit kunt gaan dat er dan ook telkens maar 1 object is.

Stel je hebt een object a dat een vlucht is.

Java:

Flight b = a;
boolean result = a.equals(b);

Volgens jou is result nu false omdat twee vlucht objecten toch nooit gelijk zijn.

Trek je dat door naar de rest van de applicatie dan zal de contains van arraylist ook nooit werken aangezien deze met equals werkt. Dat de treeset wel werkte kwam omdat je zelf een compare hebt geimplementeerd die objecten wel gelijk kon stellen. Dat je programma werkte kwam dus juist doordat deze zogenaamde 'bug' in de api zat.

Waarom dacht je dat de 'item niet gevonden' nu juist bij de list optrad ipv de tree?

Dat is waar, maar dat staat bij Comparator, niet bij TreeSet. Een vermelding hiervan bij TreeSet zou wel zou duidelijk zijn. Ik denk overigens dat het wel mogelijk is om alleen met equals een element in een Tree te vinden, maar dat geeft wel een enorme performancedrop, namelijk op de manier die ik ook al toepaste; de Tree eerst omzetten naar een Array.

Bij treeset zie ik anders duidelijk het volgende staan (helemaal bovenaan):

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

[Robtimus]

Janoz schreef op 25 augustus 2004 @ 13:05:
Stel je hebt een object a dat een vlucht is.

Java:

Flight b = a;
boolean result = a.equals(b);

Volgens jou is result nu false omdat twee vlucht objecten toch nooit gelijk zijn.

Slecht voorbeeld, want je hebt nog steeds maar 1 object. Je hebt nu alleen 2 verwijzingen naar dat ene object, nml a en b.

[Verbal Kint]

Janoz schreef op 25 augustus 2004 @ 13:05:
[...]


Je hebt ook wel gelijk dat er telkens maar 1 vlucht is, maar dat betekend niet dat je er maar van uit kunt gaan dat er dan ook telkens maar 1 object is.

Stel je hebt een object a dat een vlucht is.

Java:

Flight b = a;
boolean result = a.equals(b);

Volgens jou is result nu false omdat twee vlucht objecten toch nooit gelijk zijn.

Nee hoor, variabelen a en b verwijzen allebei naar dezelfde flight instantie. True dus. Logisch ook want er is maar één vluchtobject, er zijn alleen meerdere pointers naar deze instantie.

Trek je dat door naar de rest van de applicatie dan zal de contains van arraylist ook nooit werken aangezien deze met equals werkt. Dat de treeset wel werkte kwam omdat je zelf een compare hebt geimplementeerd die objecten wel gelijk kon stellen. Dat je programma werkte kwam dus juist doordat deze zogenaamde 'bug' in de api zat.

Mijn programma functioneerde inderdaad, maar niet goed! Dat kwam pas aan het licht door dit akkefietje met contains(), dus dat komt mooi uit.

Bij treeset zie ik anders duidelijk het volgende staan (helemaal bovenaan):

[...]

Inderdaad, daar wordt het wel genoemd. Jammer dat het bij de method details dan weer niet terug komt.

edit:
IceManX vindt het ook

[ Voor 5% gewijzigd door Verbal Kint op 25-08-2004 13:30 . Reden: . ]

[Janoz]

Wat ik met dat stukje code aan wilde geven is dat dat het gevolg is van de definitie 'twee objecten zijn nooit gelijk aan elkaar' Ik kan er wel weer een heleboel dingen bij verzinnen. Tuurlijk geeft het stukje voorbeeld code true terug, maar dat is niet in lijn met de door jou gestelde definitie. Als ik naar je startpost kijk zie ik dat je je verwonderd over het feit dat het element wel in de lijst staat, maar dat de contains methode false terug geeft.

Java:

Flight b = a;
flightSet.add(b);

//heleboel bewerkingen 
//heleboel bewerkingen

result=flightSet.contains(a);

Dit levert in de code van je startpost false op terwijl het inderdaad true op moet leveren.

mbt de documentatie vind ik persoonlijk dat je redelijk je best moet doen om niet te zien dat de juiste implementatie van de set interface een beetje afhangt van de implementatie van je comparator. Sowieso snapt iedereen die weet wat een tree structuur is dat je dat niet met equals kan doen. Het zoeken moet immers wel met de comperator gebeuren. Wat voor reactie van contains had jij dan het liefst gehad als compare 0 oplevert, maar equalsTo false?

[Verwijderd]

IceManX schreef op 24 augustus 2004 @ 18:25:
[...]
Je moet je eigenlijk schamen: wel equals overriden maar niet hashCode...

Je hebt gelijk... Equals zou een bijbehorende hashcode moeten hebben!

[ Voor 37% gewijzigd door Verwijderd op 25-08-2004 14:04 . Reden: Hier stond wat blaat... ]

[Alarmnummer]

Verwijderd schreef op 25 augustus 2004 @ 13:57:
[...]
Je hebt gelijk... Equals zou een bijbehorende hashcode moeten hebben!

lekker simpel (je krijgt alleen wel een lievelingsemmer)
public int hashcode(){return 0;}

[Verbal Kint]

Janoz schreef op 25 augustus 2004 @ 10:46:
(..)
Hoe ik het zou doen? Ik denk zo:

Java:

public Flight next(Flight last)
{
   return this.tailSet(last).first();
}

Hmmm, headset().last() (voor previous(), want die is er ook) werkt prima, want headset is exclusive. tailset() is echter inclusief, dus .first() geeft me de huidige vlucht weer terug, ipv next. Toch weer terug naar de ArrayList?

[edit]
Of wat ook kan is uit de tailset remove(tailset.first) en dan alsnog return tailset.first(), wat zou de beste performance geven?

[ Voor 14% gewijzigd door Verbal Kint op 25-08-2004 17:38 ]

[Janoz]

Inderdaad. In dat geval gewoon de iterator van de tail set opvragen en dan het 2e element pakken. Blijft dat iig nog een O(1) operatie waardoor het zoeken naar het volgende element een O(log N) operatie blijft.

[Verwijderd]

Alarmnummer schreef op 25 augustus 2004 @ 15:17:
[...]


lekker simpel (je krijgt alleen wel een lievelingsemmer)
public int hashcode(){return 0;}

lievelingsemmer?

[Robtimus]

Hash table werkt met buckets met objecten met dezelfde hashcode. Als hashCode() 0 returnt zal alles dus in dezelfde bucket komen, dus de lievelingsbucket / lievelingsemmer.

[ACM]

Overigens nog wat tips waarom dit nogal kostbare code is:

Java:

Public class FlightList extends TreeSet
{

   public Flight next(Flight last)
    {
        if (!this.contains(last)) // O(sqrt(n)) operatie
        {
            System.out.println("Treeset does not contain " + last);
            
        }
        if (this.last().equals(last))
        {
            return null;
        }
        ArrayList list = new ArrayList(this); // O(n) operatie
        if (!list.contains(last)) // O(n/2) operatie
        {
            System.out.println("Arraylist does not contain " + last);
        }
        return (Flight) list.get(list.indexOf(last) + 1); // O(n/2) operatie (die indexOf)
    } // Totaal: O(2n + sqrt(n))
}

En zoals Janoz al liet zien kan het ook wat handiger en sneller dan dat (en met minder code ook) In zijn geval is het O(sqrt(n) + 1) oid, waarschijnlijk ietsje meer door de allocatie van de nieuwe TreeSet.

[Verbal Kint]

OK, ik heb het volgende geïmplementeerd:

Java:

public Flight next(Flight last)
    {
        if (!this.contains(last))
        {
            throw new IllegalArgumentException(last + " not on list "
                    + last.getAircraft());
        }
        if (this.last().equals(last))
        {
            return null;
        }
        SortedSet tailset = this.tailSet(last);
        //A tailset is inclusive
        tailset.remove(tailset.first());
        return (Flight) tailset.first();
    }

Maar wat ik niet begrijp is dat als ik het eerste element van tailset remove, dit element ook van this (aFlightList) verdwijnt. Java doc zegt:

java.util.Set.remove(..): Removes the specified element from this set if it is present

Waarom wordt de vlucht niet alleen van "this set" verwijderd (tailset) maar ook van de andere (aFlightList)?

[Janoz]

De tailset is een subset van de gehele tree. Door de tailset op te vragen krijg je een view op de orginele set. Er wordt dus geen copie gemaakt. Verwijder je delen uit de subset, dan worden deze ook uit de gehele set verwijderd. Wil je een copie, dan zul je die zelf moeten maken, maar wederom is dat weer veel te duur.

Dit staat trouwens allemaal wel bij de methode definitie. Sowieso werkt jou (en mijn) implementatie alleen goed waneer de vlucht ook daadwerkelijk in de set voorkomt. Waneer de vlucht niet voorkomt wordt de eerste vlucht die volgens de sortering na de opgegeven vlucht zit terug gegeven.

Trouwens.. Hoe vaak gebruik je de tree eigenschap, en waarom heb je uberhaupt voor een tree gekozen? Is het misschien niet handiger om een linked list te gebruiken als je next en previous nodig hebt?

ACM schreef op 25 augustus 2004 @ 22:13:
En zoals Janoz al liet zien kan het ook wat handiger en sneller dan dat (en met minder code ook) In zijn geval is het O(sqrt(n) + 1) oid, waarschijnlijk ietsje meer door de allocatie van de nieuwe TreeSet.

Die van mij was O(Log N +1) = O(Log N). TreeSet hoeft zoals je ziet niet te worden gealloceerd dus dat valt af .

[ Voor 44% gewijzigd door Janoz op 26-08-2004 11:43 ]

[DaCoTa]

JavaDoc van TreeSet:

public SortedSet subSet(Object fromElement, Object toElement)

Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive. (If fromElement and toElement are equal, the returned sorted set is empty.) The returned sorted set is backed by this set, so changes in the returned sorted set are reflected in this set, and vice-versa. The returned sorted set supports all optional Set operations.

[ACM]

Janoz schreef op 26 augustus 2004 @ 11:37:
Die van mij was O(Log N +1) = O(Log N). TreeSet hoeft zoals je ziet niet te worden gealloceerd dus dat valt af .

Er worden wel wat objecten gealloceerd (o.a. een nieuwe TreeSet) maar de data wordt zelf inderdaad niet gekopieerd. Dat blijft een (deel)view op de originele interne TreeMap.

[Verbal Kint]

Janoz schreef op 26 augustus 2004 @ 11:37:
De tailset is een subset van de gehele tree. Door de tailset op te vragen krijg je een view op de orginele set. Er wordt dus geen copie gemaakt. Verwijder je delen uit de subset, dan worden deze ook uit de gehele set verwijderd.

Dat had ik inderdaad zelf wel even mogen vinden...

Wil je een copie, dan zul je die zelf moeten maken, maar wederom is dat weer veel te duur.

Waarmee we dus weer terug zijn bij de ArrayList. Of een iterator, maar dan moet je tweemaal i.next() doen om bij de tweede te komen en maak je een iterator aan. Mjaw, is misschien toch goedkoper.

Trouwens.. Hoe vaak gebruik je de tree eigenschap, en waarom heb je uberhaupt voor een tree gekozen? Is het misschien niet handiger om een linked list te gebruiken als je next en previous nodig hebt?
(..)

Vluchten kunnen continue worden herverdeeld over de flightlists, daarbij moeten ze wel op volgorde (van STD) blijven, vandaar een TreeSet met custom comparator.

[ACM]

Verbal Kint schreef op 26 augustus 2004 @ 12:42:
Waarmee we dus weer terug zijn bij de ArrayList. Of een iterator, maar dan moet je tweemaal i.next() doen om bij de tweede te komen en maak je een iterator aan. Mjaw, is misschien toch goedkoper.

Een iterator van een subset zal alsnog (veel) goedkoper zijn dan je gespeel met een ArrayList omdat het nergens voor nodig is al die objecten te kopieren Je kan - bij mijn weten, trouwens ook de contains weglaten, je zou zoiets kunnen doen:

Java:

SortedSet tailSet = treeSet.tailSet(last);
Iterator i = tailSet.iterator();
if(i.hasNext() && i.next().equals(last))
  return (i.hasNext() ? i.next() : null);
else
  return null; // of gooi een exception

Sterker nog, 't is zelfs goedkoper om gewoon met een iterator door je TreeSet te gaan, net zo lang tot je je 'last'-object tegenkomt en dan nog 1x next te doen... Dan een ArrayList te nemen en daar jouw set van operaties op uit te voeren

[Janoz]

Verbal Kint schreef op 26 augustus 2004 @ 12:42:
Waarmee we dus weer terug zijn bij de ArrayList. Of een iterator, maar dan moet je tweemaal i.next() doen om bij de tweede te komen en maak je een iterator aan. Mjaw, is misschien toch goedkoper.

Bij het maken van een array list worden alle elementen uit de treeset gekopieerd naar een nieuwe structuur. Bij alle elementen wordt dus langs gegaan. Vervolgens wordt in de array list gezocht naar het juiste element waarbij weer bij element 1 begonnen wordt en 1 voor 1 wordt gekeken of dat het gezochte element is. Daarna wordt met de index of weer langs alle elementen gewandeld om de juiste op te halen en deze wordt terug gegeven.

Een iterator is een object dat door de al bestaande structuur heen wandeld. Waneer je een iterator opvraagt van een (subset van een) tree wordt er helemaal niks gekopieerd of opnieuw aangemaakt. De iterator zorgt gewoon dat hij weet waar het volgende terug te geven element staat, en wat de voor die datastructuur de meest handige methode is om de volgende te bepalen.

Zoals je ziet zou het zelfs sneller zijn waneer je mbv een itterator alle elementen bij langs loopt op zoek naar je eigen om vervolgens de volgende terug te geven, aangezien dat alleen al sneller is dan het cre-eeren van de ArrayList uit de TreeSet.


----
Edit: .. Hmm, violgende keer gewoon gelijk reageren en niet tussendoor bellen, overleggen en een planning proberen te maken ...

[ Voor 5% gewijzigd door Janoz op 26-08-2004 13:56 ]

[Verbal Kint]

Het is nu dit geworden:

Java:

public Flight next(Flight last)
    {
        if (!this.contains(last))
        {
            throw new IllegalArgumentException(last + " not on list "
                    + last.getAircraft());
        }
        SortedSet tailSet = this.tailSet(last);
        //tailset is inclusive, we send the second element
        Iterator i = tailSet.iterator();i.next();
        return (i.hasNext() ? (Flight) i.next() : null);
    }

De eerste i.next() levert de huidige vlucht (last) en de volgende (die gereturned wordt) de nextflight. Het contains() statement is absoluut nodig omdat er anders geen check is of "last" überhaupt wel in aFlightlist voorkomt. Als dat niet het geval is geeft tailset je gewoon een verzameling namelijk, in dit geval eentje met alle vluchten met een STD na die van de "foute" vlucht.

_{wat achtergrondinfo:
Deze code is onderdeel van een model waarin vliegbewegingen gesimuleerd worden. Het is ontwikkeld in DSOL, een Java package dat simulatiefunctionaliteit (event-calendar, pseudo-random numbers en statistiek) aan Java toevoegt. Mocht je hier in geïnteresseerd zijn kun je kijken op dsol.sourceforge.net of www.simulation.tudelft.nl}

[Verwijderd]

IceManX schreef op 25 augustus 2004 @ 20:48:
Hash table werkt met buckets met objecten met dezelfde hashcode. Als hashCode() 0 returnt zal alles dus in dezelfde bucket komen, dus de lievelingsbucket / lievelingsemmer.

Tja, en dat wil je dus niet....

Veel beter is dan:

code:

public int hashCode() {
    int result = 17;
    result = 37*result + flightId;
    result = 37*result + flightPrefix;
    result = 37*result + flightSuffix;
    return result;
}

Of iets dergelijks....

[Alarmnummer]

Verwijderd schreef op 31 augustus 2004 @ 16:24:
Tja, en dat wil je dus niet....

Tuurlijk wil je dat niet, vandaar ook mijn

Je programma draait dus wat langzamer, maar wel correct.