Generalisere compareTo metode

[mushin]

Hei

Jeg holder på med å skrive datastrukturen 'binært søke tre' i Java. Oppgaven er for å forstå hvordan ulike datastrukturer fungerer bak kulissene.

Er foreløbig i penn/papir stadiet og har tenkt ut noen løsninger.

Verdiene skal sorteres binært, dvs hvis vi feks skal ha et binært søke tre som holder orden på alle mulig objekter med type-parameteren E. En spesifikk type objekter kan være karakterene i James Bond filmene, og de sorteres etter hvor badass de eller hvor høye de er. Så kan vi enkelt definere en compareTo metode som sammenligner James Bond karakter objektene. Er Jaws mer badass en Oddjob?

Jaws.compareTo(OddJob) (returns: 1) Fordi han er mer badass.

 

Hvordan kan vi få generalisert compareTo til å kunne sammenligne alle typer objekter og ikke bare en spesifikk type objekter? Binær søke treet skal ha type-parameteren E, sånn at vi kan opprette et søketree for alle typer objekter. Er dette i det hele tatt mulig? Det er jo mulig å sette et krav om at alle objekter som skal bruke det binære søke treet må ha en metode som heter .getValue();

 

Noen andre som har noen mer elegante løsningsforslag?

[MailMan13]

La treet ta en Comparator i konstruktor.

[mushin]

Skal prøve, må bare utforske hvordan en comperator er anderledes enn ting klasser som implementerer Comparable interface.

[MailMan13]

Forskjellen er at med Comparator er det den som instansierer treèt som bestemmer hvordan elementene skal sammenlignes. Med Comparable er det kun mulig å definere èn sammenligning, som er gitt av typen som sammenlignes.

 

Da kan ulike trær ha samme generic type, men ulik sammenligning.

 

Lenge siden jeg kodet noe særlig Java, men man kan f.eks se for seg noe sånt (Google finner ikke noe generic variant av Comparator...)

BinaryTree<Villain> baddassTree = new BinaryTree<MyClass>(new Comparable {
   public int compareTo(object left, object right) {
       return ((Villain)left).BadAssFactor() - ((Villain)right).BadAssFactor();
   }
});

BinaryTree<Villain> alphabeticTree = new BinaryTree<MyClass>(new Comparable {
   public int compareTo(object left, object right) {
       return ((Villain)left).getName().compareTo((Villain)right).getName());
   }
});

[mushin]

Forskjellen er at med Comparator er det den som instansierer treèt som bestemmer hvordan elementene skal sammenlignes. Med Comparable er det kun mulig å definere èn sammenligning, som er gitt av typen som sammenlignes.

 

Da kan ulike trær ha samme generic type, men ulik sammenligning.

 

Lenge siden jeg kodet noe særlig Java, men man kan f.eks se for seg noe sånt (Google finner ikke noe generic variant av Comparator...)

BinaryTree<Villain> baddassTree = new BinaryTree<MyClass>(new Comparable {
   public int compareTo(object left, object right) {
       return ((Villain)left).BadAssFactor() - ((Villain)right).BadAssFactor();
   }
});

BinaryTree<Villain> alphabeticTree = new BinaryTree<MyClass>(new Comparable {
   public int compareTo(object left, object right) {
       return ((Villain)left).getName().compareTo((Villain)right).getName());
   }
});

 

 

Nydelig, krystall klar hjelp, mange mange takk. Beklager for seint svar, vært opptatt med ett annet prosjekt. Tror implementasjonen skal gå veldig greit nå. Greit å sette krav til de som skal bruke data-strukturene også. Skjønte fort nå at det kunne bli vanskelig å få til compareTo metode som skal fungere for alle objekter, når det finnes tusenvis av objekter man kan lage.