1/*2 * Licensed to the Apache Software Foundation (ASF) under one3 * or more contributor license agreements. See the NOTICE file4 * distributed with this work for additional information5 * regarding copyright ownership. The ASF licenses this file6 * to you under the Apache License, Version 2.0 (the7 * "License"); you may not use this file except in compliance8 * with the License. You may obtain a copy of the License at9 *10 * http://www.apache.org/licenses/LICENSE-2.011 *12 * Unless required by applicable law or agreed to in writing, software13 * distributed under the License is distributed on an "AS IS" BASIS,14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.15 * See the License for the specific language governing permissions and16 * limitations under the License.17 */1819package org.apache.giraph.utils;
2021import com.google.common.collect.Iterables;
22import org.apache.giraph.edge.Edge;
23import org.apache.giraph.edge.EdgeFactory;
24import org.apache.giraph.edge.OutEdges;
25import org.apache.hadoop.conf.Configuration;
26import org.apache.hadoop.io.Writable;
27import org.apache.hadoop.io.WritableComparable;
28import org.apache.hadoop.io.WritableUtils;
2930import java.util.ArrayList;
31import java.util.Collection;
32import java.util.Collections;
33import java.util.Comparator;
34import java.util.Iterator;
3536/**37 * Utility methods for iterables of edges.38 */39publicclassEdgeIterables {
40/** Utility classes shouldn't be instantiated. */41privateEdgeIterables() { }
4243/**44 * Compare two edge iterables element-wise. The edge value type needs45 * to be Comparable.46 *47 * @param e1 First edge iterable48 * @param e2 Second edge iterable49 * @param <I> Vertex id50 * @param <E> Edge value51 * @return Whether the two iterables are equal element-wise52 */53publicstatic <I extends WritableComparable, E extends WritableComparable>
54boolean equals(Iterable<Edge<I, E>> e1, Iterable<Edge<I, E>> e2) {
55 Iterator<Edge<I, E>> i1 = e1.iterator();
56 Iterator<Edge<I, E>> i2 = e2.iterator();
57while (i1.hasNext()) {
58if (!i2.hasNext()) {
59return false;
60 }
61if (!EdgeComparator.equal(i1.next(), i2.next())) {
62return false;
63 }
64 }
65returntrue;
66 }
6768/**69 * Make a deep copy of an edge iterable and return it as an {@link70 * ArrayList}.71 * Note: this method is slow since it has to deserialize all serialize all72 * the ids and values. It should only be used in unit tests.73 *74 * @param edges Iterable of edges75 * @param <I> Vertex id76 * @param <E> Edge value77 * @return A new list with copies of all the edges78 */79publicstatic <I extends WritableComparable, E extends WritableComparable>
80 ArrayList<Edge<I, E>> copy(Iterable<Edge<I, E>> edges) {
81 Configuration conf = new Configuration();
82 ArrayList<Edge<I, E>> edgeList =
83new ArrayList<Edge<I, E>>(Iterables.size(edges));
84for (Edge<I, E> edge : edges) {
85 edgeList.add(EdgeFactory.create(
86 WritableUtils.clone(edge.getTargetVertexId(), conf),
87 WritableUtils.clone(edge.getValue(), conf)));
88 }
89return edgeList;
90 }
9192/**93 * Compare two edge iterables up to reordering. The edge value type needs94 * to be Comparable.95 *96 * @param e1 First edge iterable97 * @param e2 Second edge iterable98 * @param <I> Vertex id99 * @param <E> Edge value100 * @return Whether the two iterables are equal up to reordering101 */102publicstatic <I extends WritableComparable, E extends WritableComparable>
103boolean sameEdges(Iterable<Edge<I, E>> e1, Iterable<Edge<I, E>> e2) {
104 ArrayList<Edge<I, E>> edgeList1 = copy(e1);
105 ArrayList<Edge<I, E>> edgeList2 = copy(e2);
106 Comparator<Edge<I, E>> edgeComparator = new EdgeComparator<I, E>();
107 Collections.sort(edgeList1, edgeComparator);
108 Collections.sort(edgeList2, edgeComparator);
109return equals(edgeList1, edgeList2);
110 }
111112/**113 * Get the size of edges. Optimized implementation for cases when edges is114 * instance of {@link OutEdges} or {@link Collection} which only calls115 * size() method from these classes.116 *117 * @param edges Edges118 * @param <I> Vertex index119 * @param <E> Edge value120 * @return Size of edges121 */122publicstatic <I extends WritableComparable, E extends Writable> int size(
123 Iterable<Edge<I, E>> edges) {
124if (edges instanceof OutEdges) {
125return ((OutEdges) edges).size();
126 } else {
127return Iterables.size(edges);
128 }
129 }
130131/**132 * Initialize edges data structure and add the edges from edgesIterable.133 *134 * If edgesIterable is instance of {@link OutEdges} or {@link Collection}135 * edges will be initialized with size of edgesIterable,136 * otherwise edges will be initialized without size.137 *138 * @param edges Edges to initialize139 * @param edgesIterable Iterable whose edges to use140 * @param <I> Vertex index141 * @param <E> Edge value142 */143publicstatic <I extends WritableComparable, E extends Writable>
144void initialize(OutEdges<I, E> edges, Iterable<Edge<I, E>> edgesIterable) {
145if (edgesIterable instanceof OutEdges ||
146 edgesIterable instanceof Collection) {
147 edges.initialize(size(edgesIterable));
148 } else {
149 edges.initialize();
150 }
151for (Edge<I, E> edge : edgesIterable) {
152 edges.add(edge);
153 }
154if (edges instanceof Trimmable) {
155 ((Trimmable) edges).trim();
156 }
157 }
158 }