This project has retired. For details please refer to its Attic page.
BasicSet 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  package org.apache.giraph.types.ops.collections;
19  
20  import it.unimi.dsi.fastutil.ints.IntIterator;
21  import it.unimi.dsi.fastutil.ints.IntOpenHashBigSet;
22  import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
23  import it.unimi.dsi.fastutil.ints.IntSet;
24  import it.unimi.dsi.fastutil.longs.LongIterator;
25  import it.unimi.dsi.fastutil.longs.LongOpenHashBigSet;
26  import it.unimi.dsi.fastutil.longs.LongOpenHashSet;
27  import it.unimi.dsi.fastutil.longs.LongSet;
28  
29  import java.io.DataInput;
30  import java.io.DataOutput;
31  import java.io.IOException;
32  
33  import org.apache.giraph.types.ops.IntTypeOps;
34  import org.apache.giraph.types.ops.LongTypeOps;
35  import org.apache.giraph.types.ops.PrimitiveIdTypeOps;
36  import org.apache.hadoop.io.IntWritable;
37  import org.apache.hadoop.io.LongWritable;
38  import org.apache.hadoop.io.Writable;
39  
40  /**
41   * BasicSet with only basic set of operations.
42   * All operations that return object T are returning reusable object,
43   * which is modified after calling any other function.
44   *
45   * @param <T> Element type
46   */
47  public interface BasicSet<T> extends Writable {
48    /** Threshold for using OpenHashSet and OpenHashBigSet implementations. */
49    long MAX_OPEN_HASHSET_CAPACITY = 800000000;
50  
51    /** Removes all of the elements from this list. */
52    void clear();
53  
54    /**
55     * Number of elements in this list
56     *
57     * @return size
58     */
59    long size();
60  
61    /**
62     * Makes sure set is not using space with capacity more than
63     * max(n,size()) entries.
64     *
65     * @param n the threshold for the trimming.
66     */
67    void trim(long n);
68  
69    /**
70     * Adds value to the set.
71     * Returns <tt>true</tt> if set changed as a
72     * result of the call.
73     *
74     * @param value Value to add
75     * @return true if set was changed.
76     */
77    boolean add(T value);
78  
79    /**
80     * Checks whether set contains given value
81     *
82     * @param value Value to check
83     * @return true if value is present in the set
84     */
85    boolean contains(T value);
86  
87    /**
88     * TypeOps for type of elements this object holds
89     *
90     * @return TypeOps
91     */
92    PrimitiveIdTypeOps<T> getElementTypeOps();
93  
94    /** IntWritable implementation of BasicSet */
95    public static final class BasicIntOpenHashSet
96      implements BasicSet<IntWritable> {
97      /** Set */
98      private final IntSet set;
99  
100     /** Constructor */
101     public BasicIntOpenHashSet() {
102       set = new IntOpenHashSet();
103     }
104 
105     /**
106      * Constructor
107      *
108      * @param capacity Capacity
109      */
110     public BasicIntOpenHashSet(long capacity) {
111       if (capacity <= MAX_OPEN_HASHSET_CAPACITY) {
112         set = new IntOpenHashSet((int) capacity);
113       } else {
114         set = new IntOpenHashBigSet(capacity);
115       }
116     }
117 
118     @Override
119     public void clear() {
120       set.clear();
121     }
122 
123     @Override
124     public long size() {
125       if (set instanceof IntOpenHashBigSet) {
126         return ((IntOpenHashBigSet) set).size64();
127       }
128       return set.size();
129     }
130 
131     @Override
132     public void trim(long n) {
133       if (set instanceof IntOpenHashSet) {
134         ((IntOpenHashSet) set).trim((int) Math.max(set.size(), n));
135       } else {
136         ((IntOpenHashBigSet) set).trim(Math.max(set.size(), n));
137       }
138     }
139 
140     @Override
141     public boolean add(IntWritable value) {
142       return set.add(value.get());
143     }
144 
145     @Override
146     public boolean contains(IntWritable value) {
147       return set.contains(value.get());
148     }
149 
150     @Override
151     public PrimitiveIdTypeOps<IntWritable> getElementTypeOps() {
152       return IntTypeOps.INSTANCE;
153     }
154 
155     @Override
156     public void write(DataOutput out) throws IOException {
157       out.writeInt(set.size());
158       IntIterator iter = set.iterator();
159       while (iter.hasNext()) {
160         out.writeInt(iter.nextInt());
161       }
162     }
163 
164     @Override
165     public void readFields(DataInput in) throws IOException {
166       long size = in.readLong();
167       set.clear();
168       trim(size);
169       for (long i = 0; i < size; ++i) {
170         set.add(in.readInt());
171       }
172     }
173   }
174 
175   /** LongWritable implementation of BasicSet */
176   public static final class BasicLongOpenHashSet
177     implements BasicSet<LongWritable> {
178     /** Set */
179     private final LongSet set;
180 
181     /** Constructor */
182     public BasicLongOpenHashSet() {
183       set = new LongOpenHashSet();
184     }
185 
186     /**
187      * Constructor
188      *
189      * @param capacity Capacity
190      */
191     public BasicLongOpenHashSet(long capacity) {
192       if (capacity <= MAX_OPEN_HASHSET_CAPACITY) {
193         set = new LongOpenHashSet((int) capacity);
194       } else {
195         set = new LongOpenHashBigSet(capacity);
196       }
197     }
198 
199     @Override
200     public void clear() {
201       set.clear();
202     }
203 
204     @Override
205     public long size() {
206       if (set instanceof LongOpenHashBigSet) {
207         return ((LongOpenHashBigSet) set).size64();
208       }
209       return set.size();
210     }
211 
212     @Override
213     public void trim(long n) {
214       if (set instanceof LongOpenHashSet) {
215         ((LongOpenHashSet) set).trim((int) Math.max(set.size(), n));
216       } else {
217         ((LongOpenHashBigSet) set).trim(Math.max(set.size(), n));
218       }
219     }
220 
221     @Override
222     public boolean add(LongWritable value) {
223       return set.add(value.get());
224     }
225 
226     @Override
227     public boolean contains(LongWritable value) {
228       return set.contains(value.get());
229     }
230 
231     @Override
232     public PrimitiveIdTypeOps<LongWritable> getElementTypeOps() {
233       return LongTypeOps.INSTANCE;
234     }
235 
236     @Override
237     public void write(DataOutput out) throws IOException {
238       out.writeLong(set.size());
239       LongIterator iter = set.iterator();
240       while (iter.hasNext()) {
241         out.writeLong(iter.nextLong());
242       }
243     }
244 
245     @Override
246     public void readFields(DataInput in) throws IOException {
247       long size = in.readLong();
248       set.clear();
249       trim(size);
250       for (long i = 0; i < size; ++i) {
251         set.add(in.readLong());
252       }
253     }
254   }
255 }