Hashmap Iterator selbst implementieren

[User12345]

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.

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();
        }
    }
}

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:

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🙂

 

[mihe7]

Dann verwende halt values().iterator().

 

[httpdigest]

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.

 

[User12345]

Also ich hab jetzt das erste AssertEquals hinbekommen mit folgendem 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]

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]

Also irgendwie komm ich nicht daran vorbei .Iterator() zu benutzen und trotzdem wirft es mir eine IndexOutOfBoundsException

    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();
        }
    }

 

[mihe7]

Dann verwende halt values().iterator().

@User12345 Sorry, das war Quatsch. Du willst ja einen Edge-Iterator und keinen Integer-Iterator.

 

[httpdigest]

Das Problem ist diese Zeile:

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.

 

[User12345]

@mihe7 aber sind nicht value genau die edges
@httpdigest vielen Dank, aber wie löse ich es dann?

 

[httpdigest]

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.

 

[mihe7]

aber sind nicht value genau die edges

Nein, die values sind nur die Zielknoten.