This project has retired. For details please refer to its Attic page.
LongNullHashSetEdges xref
View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * 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 and
16   * limitations under the License.
17   */
18  
19  package org.apache.giraph.edge;
20  
21  import it.unimi.dsi.fastutil.longs.LongIterator;
22  import it.unimi.dsi.fastutil.longs.LongOpenHashSet;
23  
24  import org.apache.giraph.utils.EdgeIterables;
25  import org.apache.giraph.utils.Trimmable;
26  import org.apache.hadoop.io.LongWritable;
27  import org.apache.hadoop.io.NullWritable;
28  
29  import java.io.DataInput;
30  import java.io.DataOutput;
31  import java.io.IOException;
32  import java.util.Iterator;
33  
34  /**
35   * {@link OutEdges} implementation with long ids and null edge values,
36   * backed by a {@link LongOpenHashSet}.
37   * Parallel edges are not allowed.
38   * Note: this implementation is optimized for fast random access and mutations,
39   * and uses less space than a generic {@link HashMapEdges} (but more than
40   * {@link LongNullArrayEdges}.
41   */
42  public class LongNullHashSetEdges
43      implements ReuseObjectsOutEdges<LongWritable, NullWritable>,
44      MutableOutEdges<LongWritable, NullWritable>,
45      StrictRandomAccessOutEdges<LongWritable, NullWritable>,
46      Trimmable {
47    /** Hash set of target vertex ids. */
48    private LongOpenHashSet neighbors;
49  
50    @Override
51    public void initialize(Iterable<Edge<LongWritable, NullWritable>> edges) {
52      EdgeIterables.initialize(this, edges);
53    }
54  
55    @Override
56    public void initialize(int capacity) {
57      neighbors = new LongOpenHashSet(capacity);
58    }
59  
60    @Override
61    public void initialize() {
62      neighbors = new LongOpenHashSet();
63    }
64  
65    @Override
66    public void add(Edge<LongWritable, NullWritable> edge) {
67      neighbors.add(edge.getTargetVertexId().get());
68    }
69  
70    @Override
71    public void remove(LongWritable targetVertexId) {
72      neighbors.remove(targetVertexId.get());
73    }
74  
75    @Override
76    public int size() {
77      return neighbors.size();
78    }
79  
80    @Override
81    public Iterator<Edge<LongWritable, NullWritable>> iterator() {
82      // Returns an iterator that reuses objects.
83      // The downcast is fine because all concrete Edge implementations are
84      // mutable, but we only expose the mutation functionality when appropriate.
85      return (Iterator) mutableIterator();
86    }
87  
88    @Override
89    public Iterator<MutableEdge<LongWritable, NullWritable>> mutableIterator() {
90      return new Iterator<MutableEdge<LongWritable, NullWritable>>() {
91        /** Wrapped neighbors iterator. */
92        private LongIterator neighborsIt = neighbors.iterator();
93        /** Representative edge object. */
94        private ReusableEdge<LongWritable, NullWritable> representativeEdge =
95            EdgeFactory.createReusable(new LongWritable());
96  
97        public boolean hasNext() {
98          return neighborsIt.hasNext();
99        }
100 
101       @Override
102       public MutableEdge<LongWritable, NullWritable> next() {
103         representativeEdge.getTargetVertexId().set(neighborsIt.nextLong());
104         return representativeEdge;
105       }
106 
107       @Override
108       public void remove() {
109         neighborsIt.remove();
110       }
111     };
112   }
113 
114   @Override
115   public void write(DataOutput out) throws IOException {
116     out.writeInt(neighbors.size());
117     LongIterator neighborsIt = neighbors.iterator();
118     while (neighborsIt.hasNext()) {
119       out.writeLong(neighborsIt.nextLong());
120     }
121   }
122 
123   @Override
124   public void readFields(DataInput in) throws IOException {
125     int numEdges = in.readInt();
126     initialize(numEdges);
127     for (int i = 0; i < numEdges; ++i) {
128       neighbors.add(in.readLong());
129     }
130   }
131 
132   @Override
133   public NullWritable getEdgeValue(LongWritable targetVertexId) {
134     if (neighbors.contains(targetVertexId.get())) {
135       return NullWritable.get();
136     } else {
137       return null;
138     }
139   }
140 
141   @Override
142   public void setEdgeValue(LongWritable targetVertexId,
143     NullWritable edgeValue) {
144     // No operation.
145     // Only set value for an existing edge.
146     // If the edge exist, the Null value is already there.
147   }
148 
149   @Override
150   public void trim() {
151     neighbors.trim();
152   }
153 }