Hashmap Iterator selbst implementieren

User12345

Mitglied
Hallo,
meine Aufgabe ist es einen Iterator selbst zu implementieren, indem man die Klasse Graph erweitert.
Dazu hat man die Klasse Graph & Edges gegeben, sowie einen Test.
Java:
package IteratorTask;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;


/*
 * @author SOLA
 * Class representing a graph structure.
 * **/
public class Graph implements Iterable<Edge>{

    // Store vertices and their respective edges
    private Map<Integer, List<Integer>> vertex_edge_map = null;

    public Graph() {
        vertex_edge_map = new HashMap<>();
    }

    /**
     * Function to add new vertex to the graph
     */
    public void addVertex(int vertex) {
        if (!vertex_edge_map.containsKey(vertex)) {
            vertex_edge_map.put(vertex, new LinkedList<Integer>());
        }
    }

    /**
     * Function to add new edge to the graph
     */
    public void addEdge(Edge edge) {
        int source = edge.getSource();
        int destination = edge.getDestination();

        if (!vertex_edge_map.containsKey(source))
            addVertex(source);
        if (!vertex_edge_map.containsKey(destination))
            addVertex(destination);
        if (!vertex_edge_map.get(source).contains(destination))
            vertex_edge_map.get(source).add(destination);
    }

    // selbst hinzugefuegt ab hier
    public Iterator<Edge> iterator() {
        return new GraphIterator<Edge>();
    }

    public class GraphIterator<A> implements Iterator<Edge> {
        
        int index = -1;
       // Set <List<Integer>> edges = vertex_edge_map.values();
        //Integer[] arr = (Integer[]) edges.toArray();
        
        @Override
        public boolean hasNext() {
            //if(index < vertex_edge_map.size()) {
            //    return false;
            //}
            return true;
        }

        @Override
        public Edge next() {
            //if(hasNext()) {
            // new Edge(0, arr[index+1]);
            //}
            return null;
        }
        
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
Java:
package IteratorTask;

public class Edge implements Comparable<Edge>{
    private int source;
    private int destination;
    
    public Edge(int vert1,int vert2)
    {
        source = vert1;
        destination = vert2;
    }
    
    public int getSource() {
        return source;
    }
    
    public int getDestination() {
        return destination;
    }
    
    @Override
    public boolean equals(Object o) {
        if (o ==  null){
            return false;
        }
        
        if (!(o instanceof Edge) ) {
            return false;
        }
        
        Edge  other = (Edge) o;
        boolean edgesEqual =(this.source == other.source && this.destination == other.destination);
        return edgesEqual;
        
    }

    @Override
    public int compareTo(Edge o) {
        int c= Integer.compare(this.source, o.source);
                
        if (c!=0) {
            return c;
        }
        return Integer.compare(this.destination, o.destination);
        
    }
    
}
Und hier ein Test:
Java:
package IteratorTask;

import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

import org.junit.jupiter.api.Test;

class IteratorTest {

    @Test
    void test() {
        Graph g = new Graph();
            
        ArrayList<Edge> actual = new ArrayList<Edge>();
        actual.add(new Edge(0, 1));
        actual.add(new Edge(0, 2));
        actual.add(new Edge(2, 1));
        actual.add(new Edge(3, 1));
        actual.add(new Edge(2, 3));
        
        for (Edge e : actual) {
            g.addEdge(e);
        }
        Collections.sort(actual);
        
        
        ArrayList<Edge> expected = new ArrayList<Edge>();
        for(Edge e : g) {
            expected.add(e);
        }
        
        Collections.sort(expected);
        
        assertEquals(actual.size(),expected.size());
        assertArrayEquals(actual.toArray(),expected.toArray());
        
        
        
    }

}

Leider weiß ich irgendwie nicht, wie ich über die Edges iterieren soll, wenn ich als keys Integer habe und als value List<Integer>. Tatsächlich sind ja immer die values die Destination ids, aber dafür müsste ich ja pro key über die edges...

Wichtig! Ich darf nicht entrySet.iterator() verwenden. Ich muss den Iterator selbst schreiben, deshalb hoffe ich auf Tipps:)
 

httpdigest

Top Contributor
Bist du sicher, dass du `vertex_edge_map.entrySet().iterator()` nicht verwenden darfst? Das wird ja nur einer von vielen Bausteinen der fertigen Lösung werden. Alleine damit bist du ja nicht fertig.

EDIT: Oder, um es anders auszudrücken: Jede mögliche Lösung wird zwingend entweder `vertex_edge_map.keySet()` oder `vertex_edge_map.entrySet()` aufrufen müssen, denn du musst dich selbstverständlich einer Möglichkeit bedienen, um über die Schlüssel oder die Einträge der Map zu iterieren. Anders wird keine Lösung funktionieren.
 
Zuletzt bearbeitet:

User12345

Mitglied
Also ich hab jetzt das erste AssertEquals hinbekommen mit folgendem Code:
Code:
public class GraphIterator<A> implements Iterator<Edge> {
        int index =-1;
        int length = vertex_edge_map.values().size();

        @Override
        public boolean hasNext() {
            if (index<length) {
                return true;
            }
            return false;
        }

        @Override
        public Edge next() {
            if(hasNext()) {
                Edge edge = new Edge(index,1);
                index++;
                return edge;
            }
            return null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

Wie kann ich aber jetzt immer die richtigen Edges erstellen? Also das der zweite Test funktioniert. Hoffe auf Tipps
 

httpdigest

Top Contributor
Du verwendest aktuell `vertex_edge_map.values()`. Das funktioniert ja offensichtlich nicht, da du jetzt keinen Zugriff mehr auf die Schlüssel der Map hast. Du musst `keySet()` oder `entrySet()` verwenden.
 

User12345

Mitglied
Also irgendwie komm ich nicht daran vorbei .Iterator() zu benutzen und trotzdem wirft es mir eine IndexOutOfBoundsException
Java:
    public class GraphIterator<A> implements Iterator<Edge> {
        int index =-1;
        int length = vertex_edge_map.entrySet().size();
        Iterator<Entry<Integer, List<Integer>>> entry = vertex_edge_map.entrySet().iterator();

        @Override
        public boolean hasNext() {
            if (index<length) {
                return true;
            }
            return false;
        }

        @Override
        public Edge next() {
            if(hasNext()) {
                Map.Entry pair = entry.next();
                int key = (int) pair.getKey();
                List<Integer> edge1 = (List<Integer>) pair.getValue();
                Edge edge = new Edge(key, edge1.get(0));
                index++;
                return edge;
            }
            return null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
 

httpdigest

Top Contributor
Das Problem ist diese Zeile:
Java:
Edge edge = new Edge(key, edge1.get(0));
Du gehst immer davon aus, dass jeder Vertex immer nur der Quellvertex für eine und genau eine Kante ist bzw. jeder Vertex immer nur einen Destination-Vertex in einer Edge besitzt. Das ist aber nicht so. Z.B. ist der Vertex 1 kein Quellvertex/Startvertex in einer Edge. Außerdem gibt es Vertizes, die Startvertex in mehr als nur einer Edge sind.
 

httpdigest

Top Contributor
aber wie löse ich es dann?
Mit mehr Nachdenken. :) Du benötigst effektiv einen zweistufigen Iterator. Also dein Iterator muss zwei Iteratoren als Zustand haben. Einmal den Iterator der Entries der Map und dann den Iterator über die Destination-Vertices jedes Entries der Map.
Und dein eigener hasNext() bzw. next() muss entsprechend durch die zwei Iteratoren "weiterziehen"/"weiterschalten".
Eine andere Alternative wären Java 8 Streams, mit denen du das ganze tatsächlich in einer einzigen Zeile mit einem einzigen return-Statement schreiben könntest.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Z Hashmap Iterator löscht nicht Java Basics - Anfänger-Themen 8
N HashMap mit Iterator durchlaufen Java Basics - Anfänger-Themen 11
N generische HashMap und Iterator Java Basics - Anfänger-Themen 2
R Iterator und HashMap Java Basics - Anfänger-Themen 10
S HashMap mehrere Keys zu einem Value Java Basics - Anfänger-Themen 3
A Daten aus einer HashMap aus einer DB speichern und mit neuen Werten vergleichen Java Basics - Anfänger-Themen 8
T HashMap Lsite gibt die sachen nicht aus wie gewollt. Java Basics - Anfänger-Themen 3
krgewb HashMap Java Basics - Anfänger-Themen 2
B Hashmap richtig bauen, die Tripel auf Zahl abbildet? Java Basics - Anfänger-Themen 10
"java.util.HashMap.get(Object)" is null Java Basics - Anfänger-Themen 10
berserkerdq2 Hashmap, wie prüfe ich ob ein Key schon existiert Java Basics - Anfänger-Themen 19
S Durch HashMap iterieren Java Basics - Anfänger-Themen 8
rafi072001 Sortieren einer HashMap nach Values Java Basics - Anfänger-Themen 2
F gson mit einer Hashmap Java Basics - Anfänger-Themen 2
J JSON-HashMap Java Basics - Anfänger-Themen 3
J Hashmap Java Basics - Anfänger-Themen 13
C Hashmap zickt Java Basics - Anfänger-Themen 9
S HashMap contains() Methode Java Basics - Anfänger-Themen 1
Z Satz aufteilen und die Wörter zählen (HashMap) Java Basics - Anfänger-Themen 15
N enum Attribut von Objekten einer Hashmap ausgeben Java Basics - Anfänger-Themen 6
P Verschachtelte Hashmap Java Basics - Anfänger-Themen 6
I Sortiert eine HashMap nicht gleich wie eine ArrayList? Java Basics - Anfänger-Themen 1
B HashMap alphabetisch sortieren Java Basics - Anfänger-Themen 2
J HashMap Java Basics - Anfänger-Themen 6
M Enum-Variable HashMap zuweisen Java Basics - Anfänger-Themen 5
N HashMap in List good practice? Java Basics - Anfänger-Themen 2
K Value eines HashMaps in einer HashMap wiedergeben. Java Basics - Anfänger-Themen 5
O Hashmap, ArrayList, LinkedList Java Basics - Anfänger-Themen 7
O HashMap - ArrayList Java Basics - Anfänger-Themen 29
J Hashmap langsamer als compareTo? Java Basics - Anfänger-Themen 23
E HashMap+Vererbung Java Basics - Anfänger-Themen 11
J Erhöhen eines Values als Integer bei gleichen Keys in HashMap Java Basics - Anfänger-Themen 12
N Methoden HashMap interne Werte miteinander vergleichen Java Basics - Anfänger-Themen 7
W The type Long is not visible HashMap Java Basics - Anfänger-Themen 4
M Objekt mit Hashmap vergleichen Java Basics - Anfänger-Themen 22
S Gibt es für die Klasse HashMap Generic Implementierungen? Java Basics - Anfänger-Themen 11
C HashMap - alle keys haben values der letzten put-Anweisung Java Basics - Anfänger-Themen 3
J Hashmap auslesen Java Basics - Anfänger-Themen 7
F HashMap sortieren <String, Long> Java Basics - Anfänger-Themen 3
GreenTeaYT HashMap dupliziert meine Elemente? Java Basics - Anfänger-Themen 2
shiroX Methoden Morse-Code Übersetzer mit HashMap Java Basics - Anfänger-Themen 5
E HashMap Problem Java Basics - Anfänger-Themen 5
P Hashmap anstatt LinkedList? Java Basics - Anfänger-Themen 6
T HashMap und die Methoden Java Basics - Anfänger-Themen 13
N Methoden Interaktives PDF mit HashMap befüllen Java Basics - Anfänger-Themen 0
Z Hashmap auseinandernehmen und analysieren Java Basics - Anfänger-Themen 7
B Durchlaufen von Hashmap und Arraylist Java Basics - Anfänger-Themen 8
F HashMap oder welches Array? Java Basics - Anfänger-Themen 4
T HashMap Java Basics - Anfänger-Themen 24
L Hashmap mit variablem Key Java Basics - Anfänger-Themen 9
M Collections Probleme mit Hashmap Java Basics - Anfänger-Themen 4
N Collections String in HashMap umwandeln Java Basics - Anfänger-Themen 3
Z HashMap richtig benutzen Java Basics - Anfänger-Themen 2
lgund HashMap // TS3 Query Java Basics - Anfänger-Themen 7
E Hashmap Wert auslesen Java Basics - Anfänger-Themen 2
S Printstream für einen Hashmap Loop Java Basics - Anfänger-Themen 1
dat_vin OOP Hashmap und Attribute Java Basics - Anfänger-Themen 7
C Check ob eine HashMap schon existiert Java Basics - Anfänger-Themen 16
P Vererbung Eigene HashMap Variante Java Basics - Anfänger-Themen 2
R Hashmap in anderer Klasse nicht benutzbar Java Basics - Anfänger-Themen 1
T Java Hashmap Java Basics - Anfänger-Themen 3
L Gibt es etwas wie "HashMap <String, String, String> Java Basics - Anfänger-Themen 9
K HashMap mit Daten aus ArrayList befüllen Java Basics - Anfänger-Themen 14
S OOP Klasse mit static-Eigenschaften - HashMap füllen Java Basics - Anfänger-Themen 6
O HashMap Fragen Java Basics - Anfänger-Themen 8
T HashMap Werte einfügen, durchsuchen und auslesen Java Basics - Anfänger-Themen 17
M Semantisches Problem HashMap/Netzwerk Java Basics - Anfänger-Themen 4
D HashMap Keys durchlaufen Java Basics - Anfänger-Themen 2
B Zugriff auf csv-Datei per hashmap Java Basics - Anfänger-Themen 5
M HashMap keys ausgeben Java Basics - Anfänger-Themen 2
S In einer Hashmap Klassen regestrieren Java Basics - Anfänger-Themen 2
H Collections Was ist schneller - HashMap + Sort v TreeMap? Java Basics - Anfänger-Themen 75
F HashMap nach kleinstem Value durchsuchen Java Basics - Anfänger-Themen 11
G HashMap Java Basics - Anfänger-Themen 6
F Wortpaare - HashMap - ArrayList Java Basics - Anfänger-Themen 6
M HashMap Frage Java Basics - Anfänger-Themen 3
M HashMap - put() reagiert nicht? Java Basics - Anfänger-Themen 8
N Cast eines Objektes in eine Hashmap Java Basics - Anfänger-Themen 13
A CSV Zeilenweise einlesen und in einer HashMap speichern Java Basics - Anfänger-Themen 12
A Input/Output Hashmap in einem JPanel via JList anzeigen Java Basics - Anfänger-Themen 8
K HashMap auf leere Key-Value-Paare prüfen Java Basics - Anfänger-Themen 14
F Hilfe bei der HashMap. Java Basics - Anfänger-Themen 3
F HashMap vs. TreeMap Java Basics - Anfänger-Themen 5
B HashMap Java Basics - Anfänger-Themen 9
C Collections String[] als value in HashMap Java Basics - Anfänger-Themen 6
V Hashmap Iterieren Java Basics - Anfänger-Themen 4
C Csv File in Hashmap ausgeben Java Basics - Anfänger-Themen 14
T HashMap<String,Object> Werte auslesen Java Basics - Anfänger-Themen 5
I HashMap sortieren Java Basics - Anfänger-Themen 10
I HashMap Java Basics - Anfänger-Themen 11
H Collections Brauche modifizierte HashMap Java Basics - Anfänger-Themen 6
H TreeMap/HashMap synchronisieren Java Basics - Anfänger-Themen 2
A Datentypen Hashmap to Array Java Basics - Anfänger-Themen 11
D HashMap überschreibt Werte Java Basics - Anfänger-Themen 7
pg1337 Interface Comparable-Interface bei HashMap Java Basics - Anfänger-Themen 21
D erweiterte hashmap Java Basics - Anfänger-Themen 5
H HashMap<Int, String> - Er findet die Int-Klasse nicht. Java Basics - Anfänger-Themen 3
L HashMap zu JList Java Basics - Anfänger-Themen 6
S Erste Schritte HashMap Kurze Frage - Werte über Schleife ausgeben Java Basics - Anfänger-Themen 30
F Collections ArrayList oder Hashmap mittel Collections.sychronised Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Neue Themen


Oben