Enumeration von sich wiederholenden Elementen

[Beni]

Hallo zusammen

Erstmals das Problem
Es gibt die Klassen Leaf und Kontrollpunkt (eigentlich 3 dimensionale Punkte)
Jedes Leaf besitzt 9 Kontrollpunkte (und die Kontrollpunkte wissen wiederum, von wem sie besessen sind).
Leafs können benachbart sein, in diesem Fall besitzen mehrere Leafs dieselbe Referenz eines Kontrollpunktes.

Nun bekomme ich von irgendwoher eine Enumeration von Leafs. Aus dieser Enumeration muss ich eine Enumeration von Kontrollpunkten bauen.

Der naive Ansatz, einfach für jedes Leaf seine 9 Kontrollpunkte auszugeben funktioniert nicht, da dann einige Kontrollpunkte mehrfach ausgegeben würden (das Problem kommt von den benachbarten Leafs).

Mein Lösungsansatz
Es wird eine Liste (nach dem Schema des *Move-To-Front) geführt, welche Kontrollpunkte schon ausgegeben wurde.
Bevor also ein Kontrollpunkt zurückgegeben wird, wird in der Liste nachgeguckt, ob der schoneinmal da war.

*Ich geh davon aus, dass Leafs die "räumlich" nahe beieinander liegen auch nahe in der Enumeration sind.

Ach ja: direkt in den Kontrollpunkten möchte ich nichts speichern. Es könnten ja mehrere (sogar unsynchonisierte) Enumerations geben (und auch solche, die nie fertig benutzt werden, und als Speicherleichen herumliegen würden).

Die Frage
Das ist irgendwie nicht das Gelbe vom Ei... Die Liste ist so lange wie die gesammte Anzahl Kontrollpunkte, eigentlich ein gigantischer Overhead.

Gibts da eine praktischere Lösung?

mfg Beni

 

[semi]

Vielleicht irgendeine ID für die Iteration in den Leafs speichern?

Leaf {
  byte visitID=0;
  ... die anderen Leafs bzw Kontrollpunkte


  public void addTo(Collection c, byte visitID) {
    // War schon hier, dann raus
    if(this.visitID == visitID)
      return;
    this.visitID = visitID;
    c.add(this);
    // Alle Kontrollpunkte durchgehen
    for(int i=0; i<anzahlKontrollpunkte; i++) {
      kontrollpunkt[i].addTo(c, visitID);
    }
  }
}

Du rufst es dann immer mit einer anderen ID auf (egal, ob byte-Überlauf oder nicht)

firstLeaf.addTo(c, visitID++);

Nur so eine Idee... ???:L

Edit: Setzt voraus, dass es keine freistehenden Leafs gibt.

 

[semi]

Vergiss meine Antwort. Ich sollte Fragen genauer lesen

 

[bygones]

mhm - weiß net ob ich das Problem umrissen habe, ich aber würde alle Kontrollpunkte in ein Set speichern (z.b. HashSet). Das unterbindet automatisch doppelte einträge. D.h. von allen leafs die Kontrollpunkte einfach ins Set hauen und dann einen Enum über das Set zurückgeben....

Kontrollpunkte braucht dann nur die Methode hashCode zu überschreiben. HashSet garantiert dann einen konstante Zeit beim einfügen....

oder ?

 

[Beni]

@semi
Ok

@deathbyaclown
Das Programm das ich schreibe wird vorallem eines tun: alle Ressourcen des PC's konsumieren, insbesondere auch Speicherplatz.

Es kann nun also gut sein, dass es 100'000 oder noch mehr Kontrollpunkte geben wird. Jede Variante die auf einen Array zurückgreifft ist damit aus dem Rennen (versuch mal einen 10'000-Array herzustellen, da wartest du erstmals eine Minute...). Damit entfallen aber leider die mir bekannten Hash-Verfahren, da die ja genau auf Arrays aufbauen.

Naja, dann bliebe noch irgendein sortierter Baum (TreeSet), das wäre wohl möglich.

Also, die Enumeration der Leafs, wird unter normalen Umständen etwa diese Reihenfolge haben:

Ich frage mich gerade, was wohl schneller ist (TreeSet oder MFT-List), wenn man den "Ausgabe"-Index der Leafs betrachtet, liegen ja schon oft ähnliche Nummern nebeneinander (und d.h. die Frage "Punkt schoneinmal ausgegeben", kommt ziemlich schnell nachdem der Punkt tatsächlich ausgegeben wurde).

Hm, beim TreeSet kommt noch dazu, dass ich ein Comparator schreiben muss, der zwei verschiedene Objekte auch wirklich unterscheidet (Edit: den HashCode verwenden!)

Aber ich nimm jetzt mal das TreeSet.