Changeset View
Changeset View
Standalone View
Standalone View
java/server/src/main/java/org/softwareheritage/graph/Neighbors.java
package org.softwareheritage.graph; | package org.softwareheritage.graph; | ||||
import java.util.Iterator; | import java.util.Iterator; | ||||
import it.unimi.dsi.fastutil.longs.LongBigArrays; | import it.unimi.dsi.big.webgraph.LazyLongIterator; | ||||
import org.softwareheritage.graph.AllowedEdges; | import org.softwareheritage.graph.AllowedEdges; | ||||
import org.softwareheritage.graph.Graph; | import org.softwareheritage.graph.Graph; | ||||
/** | /** | ||||
* Iterator class to go over a node neighbors in the graph. | * Iterator class to go over a node neighbors in the graph. | ||||
* <p> | * <p> | ||||
* Wrapper iterator class to easily deal with {@link AllowedEdges} during traversals. | * Wrapper iterator class to easily deal with {@link AllowedEdges} during traversals. | ||||
Show All 38 Lines | public class Neighbors implements Iterable<Long> { | ||||
* Inner class for {@link Neighbors} iterator. | * Inner class for {@link Neighbors} iterator. | ||||
* | * | ||||
* @author Thibault Allançon | * @author Thibault Allançon | ||||
* @version 0.0.1 | * @version 0.0.1 | ||||
* @since 0.0.1 | * @since 0.0.1 | ||||
*/ | */ | ||||
public class NeighborsIterator implements Iterator<Long> { | public class NeighborsIterator implements Iterator<Long> { | ||||
long nextNeighborIdx; | LazyLongIterator neighbors; | ||||
long nbNeighbors; | long nextNeighborId; | ||||
// LongBigArrays to support 64-bit indexing. | |||||
long[][] neighbors; | |||||
public NeighborsIterator() { | public NeighborsIterator() { | ||||
this.nextNeighborIdx = -1; | |||||
this.nbNeighbors = graph.degree(srcNodeId, useTransposed); | |||||
this.neighbors = graph.neighbors(srcNodeId, useTransposed); | this.neighbors = graph.neighbors(srcNodeId, useTransposed); | ||||
this.nextNeighborId = -1; | |||||
} | } | ||||
public boolean hasNext() { | public boolean hasNext() { | ||||
// Case 1: no edge restriction, bypass type checks and skip to next neighbor | // Case 1: no edge restriction, bypass type checks and skip to next neighbor | ||||
if (edges.restrictedTo == null) { | if (edges.restrictedTo == null) { | ||||
if (nextNeighborIdx + 1 < nbNeighbors) { | nextNeighborId = neighbors.nextLong(); | ||||
nextNeighborIdx++; | return (nextNeighborId != -1); | ||||
return true; | |||||
} else { | |||||
return false; | |||||
} | |||||
} | } | ||||
// Case 2: edge restriction, look ahead for next neighbor | // Case 2: edge restriction, look ahead for next neighbor | ||||
for (long lookAheadIdx = nextNeighborIdx + 1; lookAheadIdx < nbNeighbors; lookAheadIdx++) { | while ((nextNeighborId = neighbors.nextLong()) != -1) { | ||||
long nextNodeId = LongBigArrays.get(neighbors, lookAheadIdx); | if (edges.isAllowed(srcNodeId, nextNeighborId)) { | ||||
if (edges.isAllowed(srcNodeId, nextNodeId)) { | |||||
nextNeighborIdx = lookAheadIdx; | |||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
public Long next() { | public Long next() { | ||||
long nextNodeId = LongBigArrays.get(neighbors, nextNeighborIdx); | return nextNeighborId; | ||||
return nextNodeId; | |||||
} | } | ||||
} | } | ||||
} | } |