Collections

[scaary]

Hallo.

Ich hab eine Frage zu Collections.
Vorneweg: Ja, ich habe die API durchgelesen und mich sowohl hier als auch in anderen Foren umgesehen.

Kurz zur Aufgabe:

Wir sollen einen Nichtdeterministischen endlichen Automaten implementieren. Das ist soweit nicht das Problem. Jedoch haben wir Vorgaben bekommen, die mich echt verzweifeln lassen.

Derzeit haenge ich an folgendem Stueck code, der vorgegeben ist:

private List<Collection<Transition>> charAdj = new ArrayList<Colleciton<Transition>>(ALPHABET_LENGTH + 1);

Transition ist eine von mir erstellte Klasse, die einfach nur 3 Werte speichert.

Ich weiss allerdings nichts mit dem gegebenen Code anzufangen. Offensichtlich ist es eine Liste So viel weiss ich. Aber ich kann nichts mit diesem Teil anfangen <Collection<Transition>>. Was bedeutet das? Dass in der Liste eine Collection von Transitionen gespeichert ist???? Und wie zum Henker greif ich auf den Kram zu??

Eigentlich muesste ich da eine Liste haben, in de ich sowohl chars als auch Listen von Transitionen speichern kann, ich hab aber einfach keinen Dunst wie man das macht


Weiss da jemand Rat?

Ausserdem hab ich noch folgende Funktion vorgegeben:

Collection<State> getTargets(char Symbol)

Das heisst, ich bekomme einen char uebergeben, durchsuche die Collection nach dem Char, und gebe dann eine Collection mit allen objekten zurueck, in der der char enthalten ist, korrekt?

 

[Leroy42]

Lies dir einfach mal die Grundlagen zu Generics in Java durch:

Generics in Java 1.5

 

[Landei]

Du hast eine Liste von Collections, in denen Transaktionen gespeichert sind. Collection ist ein sehr allgemeines Interface (z.B. gibt es keinen wahlfreien Zugriff), aber zumindest ist es iterierbar, weswegen z.B. einfach folgendes geht:

List<Collection<Transition>> list = sonswoher();
for(Collection<Transition> col : list) {
    System.out.println("Transitions:");
    for(Transition trans : col) {
        System.out.println(trans);
    }
}

 

[scaary]

Ah, vielen Dank fuer die schnelle Antwort.

D.h. Also, dass ich in folgendem Beispiel

int ALPHABET_LENGTH = 26;

List<Collection<Transition>> charAdj = new ArrayList<Collection<Transition>> (ALPHABET_LENGTH + 1);

eine Liste mit 27 Stellen habe, die an jeder dieser Stellen Transitionen speichert, richtig?

 

[diggaa1984]

nein, du hast eine Liste mit 27 Elementen. Diese Elemente sind Collections von Transitionen, wenn ich Collections mal als Menge bezeichne, hast also 27 versch. Mengen von Transitionen. Verschieden im Sinne von versch. Objekte, die können sich deswegen aber immer noch im mathematischen Sinne überschneiden etc.

Vielleicht wäre es aufschlussreicher die Richtigkeit deiner Gedanken zu prüfen indem du uns ne Beschreibung der Funktionen zeigst. Ich vermute mal da gabs doch bestimmt ne schriftliche Erklärung was welche Funktionen zu tun haben (betrifft zB die Sache mit den getTargets)

 

[scaary]

Ahh, also hab ich eine 27.ig stellige Liste die Listen von Transitionen enthaelt (nicht oder)?
Naja, die Beschreibung hierfuer halt sich sehr in Grenzen (vor allem will ich natuerlich auch nicht durchfallen, sprich ich will mir hier nur Hilfen und keinen fertigen code holen ^^):

Automat als Graph mit Adjazenzlistendarstellung abgespeichert
Klasse für Automat
Kennt alle Zustände
Weiß welcher der Startzustand ist

Klasse für Zustand (state)
Jeder Zustand kennt seine ausgehenden Transitionen
Kollisionsfreies Hashing nach dem Symbol
private List<Collection<Transition>> charAdj
= new ArrayList<Collection<Transition>>(ALPHABET_LENGTH + 1);
Collection<State> getTargets(char symbol) evtl. in O(deg(q))

Klasse für Transition

public class Transition implements Comparable<Transition> {
...
/** ...
**
@return -1 if {@code this < trans}, 0 if equal, and 1 if
* {@code this > trans}.
*/
@Override
public int compareTo(Transition trans) {
...
}
}

Oder wolltest du was anderes haben?

Danke nochmals!!

 

[diggaa1984]

Klasse für Zustand (state)
Jeder Zustand kennt seine ausgehenden Transitionen
Kollisionsfreies Hashing nach dem Symbol
private List<Collection<Transition>> charAdj
= new ArrayList<Collection<Transition>>(ALPHABET_LENGTH + 1);
Collection<State> getTargets(char symbol) evtl. in O(deg(q))

ah das was sich dahinter versteckt hatte ich dann doch grob geahnt.
Also in deiner Zustandsklasse hast eben diese Liste, welche dir zu jeder möglichen Eingabe im Automat ne Menge von Transitionen speichert, welche genau aus diesem Zustand mit der erfolgten Eingabe ausführbar sind. Und da spiegelt sich in meinen Augen auch der nicht-Determinismus wieder, denn man kann für jede Eingabe mehrere Transitionen haben.

und das getTargets sagt dir nun, welche Zustände du aus diesem Zustand bei Eingabe symbol erreichen kannst. Da nicht-deterministisch können es auch mehrere Zustände sein, die du mit der selben Eingabe erreichst, daher auch hier eine Collection als Rückgabe.

Kennen die Transitionen ihre Anfangs und End-States? Weil das wäre ganz praktisch um aus der Liste<Collection<Transitionen>> mit dem symbol zu ermitteln welche Folgezustände es gibt. Sollte das der Fall sein, dann suchst du dir in der Liste die Collection zum symbol heraus .. und ermittelst dann von jeder Transition den Zielzustand und gibst diese gesammelt zurück.

 

[scaary]

Japp, die kennen die Anfangs und End Zustaende ^^


Ahh, sowas hab ich dann geahnt, dann hab ich das zumindest richtig gemacht


Hey, also nochmals, super vielen lieben Dank, du hast mir echt SEHR geholfen!!

Wenn ich dihc jetzt vllt noch mit einer Kleinigkeit belaestigen duerfte ^^

Und Zwar:

Wie Greife ich auf die einzelnen Transitionen die in den Collections gespeichert sind zu?

Den Zugriff auf die Collections hab ich mittels Iteratoren meines Erachtens nach hinbekommen:


Jetzt hab ich folgende Funktion, die soll eine Transition in die Collection (welche sich inder Liste charAdj befindet) einfuegen:

    void addTransition(Transition trans, char symbol) {
        int position = letterPositionInList(Character.toString(symbol));

        Iterator iter = charAdj.iterator();

        for(int i = 0; iter.hasNext(); ++i) {
            if (i == position) {
                   
            }
        }
    }

Ist warscheinlich nur ne winzige Kleinigkeit, aber wie greife ich jetzt auf die gewuenschte Transition in der Collection zu?

DANKE!

 

[diggaa1984]

die collection selbst kann dir wieder nen iterator liefern
siehe API

 

[scaary]

Ja, das hab ich soweit gewusst. Nur versteh ich nicht ganz, wie ich den Iterator aufrufen kann.

Ich lauf ja mit meiner Funktion solange durch, bis ich das entsprechende Objekt (spricjh die entsprechende Collection) in meiner Liste finde.

Wie mache ich denn fuer die entsprechende Collection jetzt noch nen Iterator?

Ich hatte es jetzt so versucht:
Iterator iter2 = iter.iterator();

Jedoch sagt eclipse mir, dass ich so casten muss:
Iterator iter2 = ((List<Collection<Transition>>) iter).iterator();

Ist das korrekt?

 

[diggaa1984]

Jetzt hab ich folgende Funktion, die soll eine Transition in die Collection (welche sich inder Liste charAdj befindet) einfuegen:

public void addTransition(Transition trans, char symbol) {
    int position = letterPositionInList(Character.toString(symbol));

    Collection<Transition> c = charAdj.get(position);
    c.add(trans);
}

sofern dieses mapping von position 100% passt, brauchst nich mehr zu tun .. denk ich

 

[scaary]

AHHH, ich verstehe, ich hab versucht das PFerd von hinten aufzusatteln ^^

Das macht Sinn! Danke Dir!!

 

[scaary]

Hey,

ich hab schon wieder nen Problemchen mit den Collections..


Naja, auf jeden fall hab ich folgenden Code geschrieben, der mir eine Arraylist, in der sich collections von Transitionen befinden in einen String umschreiben soll:

    public String toString() {
        String result = "";

        for (int i = 0; i < list.length; ++i) {
            List<Collection<Transition>> c = list[i].getCollection();
            for(int j = 0; j < c.size(); ++j) {
                Collection<Transition> tmp = c.get(j);
                Iterator iter = tmp.iterator();
                for(int k = 0; iter.hasNext(); ++i) {


                    Transition trans = iter;


                    result = result + "(" + (i + 1) + ", " 
                    + trans.getNumberTarget() + ")" + trans.getSymbol() + "\n";
                }
            }
        }
        return result;
    }

Wobei das Problem bei folgendem Teil liegt:

Transition trans = iter;

Bei dem will ich ja eigentlich auf die in der Kollektion befindlichen Transition nacheinander zugreifen und die entsprechenden Werte rausziehen. NUR laesst er mich nicht

Description Resource Path Location Type
Type mismatch: cannot convert from Iterator to Transition NDA.java ND Automat/src/fa line 51 Java Problem


Wie greife ich jetzt also auf den inhalt der Transitionen nacheinander zu???

Danke!

 

[Landei]

Au Mann!
- Nimm bitte, bitte im Forum [java] Tags
- Schau dir ein paar Beispiele aus dem Netz an, die Iteratoren benutzen. Es kann doch nicht so furchtbar schwer sein, die Geheimnisse von next und hasNext zu ergründen
- Strings nicht in einer Schleife addieren (außer die Anzahl Durchläufe ist vorher bekannt und klein), dafür gibt es StringBuilder

@Override
public String toString() {
  StringBuilder result = new StringBuilder();
  for (int i = 0; i < list.length; ++i) {
     for(List<Collection<Transition>> c : list[i].getCollection()) {
        for(Transition trans : c.get(j)) {
            result.append("(").append(i + 1).append(", ").append(trans.getNumberTarget()).append(")").append(trans.getSymbol()).append("\n");           
        }
     }
   }
  return result.toString();
}