Repository: giraph Updated Branches: refs/heads/trunk 9b6d6f9f6 -> 4321e4483
http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2DoubleMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2DoubleMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2DoubleMapEntryIterable.java new file mode 100644 index 0000000..f636b6b --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2DoubleMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.ints.Int2DoubleMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Int2DoubleMap.Entry> + */ +public interface Int2DoubleMapEntryIterable + extends ObjectIterable<Int2DoubleMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Int2DoubleMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2FloatMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2FloatMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2FloatMapEntryIterable.java new file mode 100644 index 0000000..70fd2eb --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2FloatMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.ints.Int2FloatMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Int2FloatMap.Entry> + */ +public interface Int2FloatMapEntryIterable + extends ObjectIterable<Int2FloatMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Int2FloatMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2IntMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2IntMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2IntMapEntryIterable.java new file mode 100644 index 0000000..0762276 --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2IntMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.ints.Int2IntMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Int2IntMap.Entry> + */ +public interface Int2IntMapEntryIterable + extends ObjectIterable<Int2IntMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Int2IntMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2LongMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2LongMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2LongMapEntryIterable.java new file mode 100644 index 0000000..3e03d14 --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Int2LongMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.ints.Int2LongMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Int2LongMap.Entry> + */ +public interface Int2LongMapEntryIterable + extends ObjectIterable<Int2LongMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Int2LongMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2ByteMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2ByteMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2ByteMapEntryIterable.java new file mode 100644 index 0000000..490464c --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2ByteMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.longs.Long2ByteMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Long2ByteMap.Entry> + */ +public interface Long2ByteMapEntryIterable + extends ObjectIterable<Long2ByteMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Long2ByteMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2DoubleMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2DoubleMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2DoubleMapEntryIterable.java new file mode 100644 index 0000000..fc57b9f --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2DoubleMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.longs.Long2DoubleMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Long2DoubleMap.Entry> + */ +public interface Long2DoubleMapEntryIterable + extends ObjectIterable<Long2DoubleMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Long2DoubleMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2FloatMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2FloatMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2FloatMapEntryIterable.java new file mode 100644 index 0000000..43a8d6f --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2FloatMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.longs.Long2FloatMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Long2FloatMap.Entry> + */ +public interface Long2FloatMapEntryIterable + extends ObjectIterable<Long2FloatMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Long2FloatMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2IntMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2IntMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2IntMapEntryIterable.java new file mode 100644 index 0000000..08e44d4 --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2IntMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.longs.Long2IntMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Long2IntMap.Entry> + */ +public interface Long2IntMapEntryIterable + extends ObjectIterable<Long2IntMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Long2IntMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2LongMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2LongMapEntryIterable.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2LongMapEntryIterable.java new file mode 100644 index 0000000..b696ea2 --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/Long2LongMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.longs.Long2LongMap;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<Long2LongMap.Entry> + */ +public interface Long2LongMapEntryIterable + extends ObjectIterable<Long2LongMap.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<Long2LongMap.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/main/java/org/apache/giraph/types/heaps/package-info.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/types/heaps/package-info.java b/giraph-core/src/main/java/org/apache/giraph/types/heaps/package-info.java new file mode 100644 index 0000000..ed8e581 --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/types/heaps/package-info.java @@ -0,0 +1,21 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** + * Heaps for different types + */ +package org.apache.giraph.types.heaps; http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/generate/GeneratePrimitiveClasses.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/generate/GeneratePrimitiveClasses.java b/giraph-core/src/test/java/org/apache/giraph/generate/GeneratePrimitiveClasses.java index be2417a..4e19ca2 100644 --- a/giraph-core/src/test/java/org/apache/giraph/generate/GeneratePrimitiveClasses.java +++ b/giraph-core/src/test/java/org/apache/giraph/generate/GeneratePrimitiveClasses.java @@ -17,6 +17,8 @@ */ package org.apache.giraph.generate; +import org.junit.Test; + import java.io.File; import java.io.FileNotFoundException; import java.io.FileOutputStream; @@ -133,12 +135,16 @@ public class GeneratePrimitiveClasses { EnumSet<PrimitiveType> writableSet = EnumSet.noneOf(PrimitiveType.class); EnumSet<PrimitiveType> ids = EnumSet.noneOf(PrimitiveType.class); + EnumSet<PrimitiveType> numerics = EnumSet.noneOf(PrimitiveType.class); for (PrimitiveType type : EnumSet.allOf(PrimitiveType.class)) { if (type.hasWritable()) { writableSet.add(type); if (type.isId()) { ids.add(type); } + if (type.isNumeric()) { + numerics.add(type); + } } } @@ -160,6 +166,41 @@ public class GeneratePrimitiveClasses { "WTypeArrayList.java", "src/main/java/org/apache/giraph/types/ops/collections/array/W%sArrayList.java"); + generateForAll( + cfg, + writableSet, + writableSet, + "TypeTypeConsumer.java", + "src/main/java/org/apache/giraph/function/primitive/pairs/%s%sConsumer.java"); + + generateForAll( + cfg, + writableSet, + writableSet, + "TypeTypePredicate.java", + "src/main/java/org/apache/giraph/function/primitive/pairs/%s%sPredicate.java"); + + generateForAll( + cfg, + ids, + numerics, + "Type2TypeMapEntryIterable.java", + "src/main/java/org/apache/giraph/types/heaps/%s2%sMapEntryIterable.java"); + + generateForAll( + cfg, + ids, + numerics, + "FixedCapacityType2TypeMinHeap.java", + "src/main/java/org/apache/giraph/types/heaps/FixedCapacity%s%sMinHeap.java"); + + generateForAll( + cfg, + ids, + numerics, + "TestFixedCapacityType2TypeMinHeap.java", + "src/test/java/org/apache/giraph/types/heaps/TestFixedCapacity%s%sMinHeap.java"); + System.out.println("Successfully generated classes"); } @@ -178,6 +219,26 @@ public class GeneratePrimitiveClasses { } } + /** + * Generate a set of files from a template, one for each combination of + * types in the passed sets, where added entry for "type1" and "type2" to + * that object is added, on top of default entries. + */ + private static void generateForAll(Configuration cfg, + EnumSet<PrimitiveType> types1, EnumSet<PrimitiveType> types2, + String template, String outputPattern) throws TemplateNotFoundException, MalformedTemplateNameException, ParseException, FileNotFoundException, IOException, TemplateException { + for (PrimitiveType type1 : types1) { + for (PrimitiveType type2 : types2) { + Map<String, Object> props = defaultMap(); + props.put("type1", type1); + props.put("type2", type2); + generateAndWrite(cfg, props, + template, + String.format(outputPattern, type1.getCamel(), type2.getCamel())); + } + } + } + /** Generate a single file from a template, replacing mappings from given properties */ private static void generateAndWrite(Configuration cfg, Map<String, Object> props, String template, String outputFile) http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntByteMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntByteMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntByteMinHeap.java new file mode 100644 index 0000000..a832a75 --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntByteMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityIntByteMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityIntByteMinHeap heap = + new FixedCapacityIntByteMinHeap(heapCapacity); + int[] keys = new int[]{0, 1, 0, 10, 20, 0, 3, 4}; + byte[] values = new byte[]{ + (byte) 0, (byte) 1, (byte) 2, (byte) 2, (byte) 2, + (byte) 3, (byte) 3, (byte) 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i]); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntDoubleMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntDoubleMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntDoubleMinHeap.java new file mode 100644 index 0000000..2495783 --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntDoubleMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityIntDoubleMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityIntDoubleMinHeap heap = + new FixedCapacityIntDoubleMinHeap(heapCapacity); + int[] keys = new int[]{0, 1, 0, 10, 20, 0, 3, 4}; + double[] values = new double[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i], 0); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntFloatMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntFloatMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntFloatMinHeap.java new file mode 100644 index 0000000..7b07d56 --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntFloatMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityIntFloatMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityIntFloatMinHeap heap = + new FixedCapacityIntFloatMinHeap(heapCapacity); + int[] keys = new int[]{0, 1, 0, 10, 20, 0, 3, 4}; + float[] values = new float[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i], 0); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntIntMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntIntMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntIntMinHeap.java new file mode 100644 index 0000000..68e5189 --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntIntMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityIntIntMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityIntIntMinHeap heap = + new FixedCapacityIntIntMinHeap(heapCapacity); + int[] keys = new int[]{0, 1, 0, 10, 20, 0, 3, 4}; + int[] values = new int[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i]); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntLongMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntLongMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntLongMinHeap.java new file mode 100644 index 0000000..c4611fc --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityIntLongMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityIntLongMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityIntLongMinHeap heap = + new FixedCapacityIntLongMinHeap(heapCapacity); + int[] keys = new int[]{0, 1, 0, 10, 20, 0, 3, 4}; + long[] values = new long[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i]); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongByteMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongByteMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongByteMinHeap.java new file mode 100644 index 0000000..1935149 --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongByteMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityLongByteMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityLongByteMinHeap heap = + new FixedCapacityLongByteMinHeap(heapCapacity); + long[] keys = new long[]{0, 1, 0, 10, 20, 0, 3, 4}; + byte[] values = new byte[]{ + (byte) 0, (byte) 1, (byte) 2, (byte) 2, (byte) 2, + (byte) 3, (byte) 3, (byte) 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i]); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongDoubleMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongDoubleMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongDoubleMinHeap.java new file mode 100644 index 0000000..198602d --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongDoubleMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityLongDoubleMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityLongDoubleMinHeap heap = + new FixedCapacityLongDoubleMinHeap(heapCapacity); + long[] keys = new long[]{0, 1, 0, 10, 20, 0, 3, 4}; + double[] values = new double[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i], 0); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongFloatMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongFloatMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongFloatMinHeap.java new file mode 100644 index 0000000..f9d152c --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongFloatMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityLongFloatMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityLongFloatMinHeap heap = + new FixedCapacityLongFloatMinHeap(heapCapacity); + long[] keys = new long[]{0, 1, 0, 10, 20, 0, 3, 4}; + float[] values = new float[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i], 0); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongIntMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongIntMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongIntMinHeap.java new file mode 100644 index 0000000..70e78ff --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongIntMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityLongIntMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityLongIntMinHeap heap = + new FixedCapacityLongIntMinHeap(heapCapacity); + long[] keys = new long[]{0, 1, 0, 10, 20, 0, 3, 4}; + int[] values = new int[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i]); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongLongMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongLongMinHeap.java b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongLongMinHeap.java new file mode 100644 index 0000000..336b477 --- /dev/null +++ b/giraph-core/src/test/java/org/apache/giraph/types/heaps/TestFixedCapacityLongLongMinHeap.java @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +// AUTO-GENERATED class via class: +// org.apache.giraph.generate.GeneratePrimitiveClasses + +public class TestFixedCapacityLongLongMinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacityLongLongMinHeap heap = + new FixedCapacityLongLongMinHeap(heapCapacity); + long[] keys = new long[]{0, 1, 0, 10, 20, 0, 3, 4}; + long[] values = new long[]{ + 0, 1, 2, 2, 2, + 3, 3, 4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i]); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/templates/FixedCapacityType2TypeMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/templates/FixedCapacityType2TypeMinHeap.java b/giraph-core/templates/FixedCapacityType2TypeMinHeap.java new file mode 100644 index 0000000..d381ddf --- /dev/null +++ b/giraph-core/templates/FixedCapacityType2TypeMinHeap.java @@ -0,0 +1,361 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.${type1.lower}s.Abstract${type1.camel}2${type2.camel}Map; +import it.unimi.dsi.fastutil.${type1.lower}s.${type1.camel}2${type2.camel}Map; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +import java.util.NoSuchElementException; + +import org.apache.giraph.function.primitive.pairs.${type1.camel}${type2.camel}Consumer; +import org.apache.giraph.function.primitive.pairs.${type1.camel}${type2.camel}Predicate; + +${generated_message} +<#macro cast2><#if type2.lower == "byte">(${type2.lower}) </#if></#macro> + +/** + * Min heap which holds (${type1.lower} key, ${type2.lower} value) pairs with + * the largest values as its elements, up to the given maximum number of + * elements. + * + * When multiple elements with same values are added and there is no space for + * all of them in the heap, the one with larger keys will be kept in the heap. + * + * You can remove a pair with the minimum value currently in the heap. + */ +public class FixedCapacity${type1.camel}${type2.camel}MinHeap + implements ${type1.camel}2${type2.camel}MapEntryIterable { + /** Keys in the heap */ + private final ${type1.lower}[] keys; + /** Values in the heap */ + private final ${type2.lower}[] values; + /** Number of elements currently in the heap */ + private int size; + /** Capacity of the heap */ + private final int capacity; + /** Reusable iterator instance */ + private final IteratorImpl iterator; + + /** + * Initialize the heap with desired capacity + * + * @param capacity Capacity + */ + public FixedCapacity${type1.camel}${type2.camel}MinHeap(int capacity) { + keys = new ${type1.lower}[capacity]; + values = new ${type2.lower}[capacity]; + size = 0; + this.capacity = capacity; + iterator = new IteratorImpl(); + } + + /** Clear the heap */ + public void clear() { + size = 0; + } + + /** + * Add a key value pair + * + * @param key Key + * @param value Value + */ + public void add(${type1.lower} key, ${type2.lower} value) { + if (size == capacity && compare(keys[0], values[0], key, value) >= 0) { + // If the heap is full and smallest element in it is not smaller + // than value, do nothing + return; + } + int position; + if (size < capacity) { + // If the heap is not full, increase its size and find the position for + // new element (up-heap search) + position = size; + size++; + while (position > 0) { + int parent = (position - 1) >> 1; + if (compare(keys[parent], values[parent], key, value) < 0) { + break; + } + values[position] = values[parent]; + keys[position] = keys[parent]; + position = parent; + } + } else { + // If the heap is full, remove element from the root and find the position + // for new element (down-heap search) + position = removeRootAndFindPosition(key, value); + } + // Fill position with key value pair + keys[position] = key; + values[position] = value; + } + + /** + * @return Key corresponding to the minimum value currently in the heap + * @throws NoSuchElementException if the heap is empty. + */ + public ${type1.lower} getMinKey() { + if (size() > 0) { + return keys[0]; + } else { + throw new NoSuchElementException(); + } + } + + /** + * @return Minimum value currently in the heap + * @throws NoSuchElementException if the heap is empty. + */ + public ${type2.lower} getMinValue() { + if (size() > 0) { + return values[0]; + } else { + throw new NoSuchElementException(); + } + } + + /** + * Removes the (key, value) pair that corresponds to the minimum value + * currently in the heap. + */ + public void removeMin() { + if (size() > 0) { + size--; + int position = removeRootAndFindPosition(keys[size], values[size]); + keys[position] = keys[size]; + values[position] = values[size]; + } + } + + /** + * Comapre two (key, value) entries + * + * @param key1 First key + * @param value1 First value + * @param key2 Second key + * @param value2 Second value + * @return 0 if entries are equal, < 0 if first entry is smaller than the + * second one, and > 0 if first entry is larger than the second one + */ + protected int compare(${type1.lower} key1, ${type2.lower} value1, + ${type1.lower} key2, ${type2.lower} value2) { + int t = ${type2.boxed}.compare(value1, value2); + return (t == 0) ? ${type1.boxed}.compare(key1, key2) : t; + } + + @Override + public ObjectIterator<${type1.camel}2${type2.camel}Map.Entry> iterator() { + iterator.reset(); + return iterator; + } + + @Override + public int size() { + return size; + } + + /** + * Check if the heap is empty + * + * @return True iff the heap is empty + */ + public boolean isEmpty() { + return size == 0; + } + + /** + * Get capacity of the heap + * + * @return Heap capacity + */ + public int getCapacity() { + return capacity; + } + + /** + * Serializes an object into data output. + * + * @param heap Object instance to serialize + * @param out Data output + * @throws java.io.IOException + */ + public static void write(FixedCapacity${type1.camel}${type2.camel}MinHeap heap, + DataOutput out) throws IOException { + out.writeInt(heap.capacity); + out.writeInt(heap.size); + for (int i = 0; i < heap.size(); i++) { + out.write${type1.camel}(heap.keys[i]); + out.write${type2.camel}(heap.values[i]); + } + } + + /** + * Deserializes an object from data input. + * + * @param heap Object to reuse if possible + * @param in Data input + * @return FixedCapacity${type1.camel}${type2.camel}MinHeap deserialized from data input. + * @throws IOException + */ + public static FixedCapacity${type1.camel}${type2.camel}MinHeap read( + FixedCapacity${type1.camel}${type2.camel}MinHeap heap, DataInput in) + throws IOException { + int capacity = in.readInt(); + if (heap == null || heap.capacity != capacity) { + heap = new FixedCapacity${type1.camel}${type2.camel}MinHeap(capacity); + } else { + heap.clear(); + } + heap.size = in.readInt(); + for (int i = 0; i < heap.size; i++) { + heap.keys[i] = in.read${type1.camel}(); + heap.values[i] = in.read${type2.camel}(); + } + return heap; + } + + /** + * Takes a (key, value) pair, removes the root of the heap, and finds + * a position where the pair can be inserted. + * + * @param key Key + * @param value Value + * @return Position in the heap where the (key, value) pair can be inserted + * while preserving the heap property. + */ + private int removeRootAndFindPosition(${type1.lower} key, ${type2.lower} value) { + int position = 0; + while (position < size) { + // Find the left child + int minChild = (position << 1) + 1; + // Compare the left and the right child values - find the smaller one + if (minChild + 1 < size && + compare(keys[minChild + 1], values[minChild + 1], + keys[minChild], values[minChild]) < 0) { + minChild++; + } + if (minChild >= size || compare(keys[minChild], values[minChild], + key, value) >= 0) { + break; + } + keys[position] = keys[minChild]; + values[position] = values[minChild]; + position = minChild; + } + return position; + } + + /** + * Traverse all elements of the heap, calling given function on each element. + * + * @param f Function to call on each element. + */ + public void forEach${type1.camel}${type2.camel}(${type1.camel}${type2.camel}Consumer f) { + for (int i = 0; i < size(); ++i) { + f.apply(keys[i], values[i]); + } + } + + /** + * Traverse all elements of the heap, calling given function on each element, + * or until predicate returns false. + * + * @param f Function to call on each element. + * @return true if the predicate returned true for all elements, + * false if it returned false for some element. + */ + public boolean forEachWhile${type1.camel}${type2.camel}(${type1.camel}${type2.camel}Predicate f) { + for (int i = 0; i < size(); ++i) { + if (!f.apply(keys[i], values[i])) { + return false; + } + } + return true; + } + + /** Iterator for FixedCapacity${type1.camel}${type2.camel}MinHeap */ + private class IteratorImpl implements ObjectIterator<${type1.camel}2${type2.camel}Map.Entry> { + /** Reusable entry */ + private final MutableEntry entry = new MutableEntry(); + /** Current index */ + private int index; + + /** Reset the iterator so it can be reused */ + public void reset() { + index = -1; + } + + @Override + public boolean hasNext() { + return index < size - 1; + } + + @Override + public ${type1.camel}2${type2.camel}Map.Entry next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } + index++; + entry.set${type1.camel}Key(keys[index]); + entry.set${type2.camel}Value(values[index]); + return entry; + } + + @Override + public void remove() { + throw new UnsupportedOperationException("remove() shouldn't be called"); + } + + @Override + public int skip(int i) { + throw new UnsupportedOperationException("skip(int) shouldn't be called"); + } + } + + /** Helper mutable Entry class */ + private static class MutableEntry extends Abstract${type1.camel}2${type2.camel}Map.BasicEntry { + /** Default constructor */ + private MutableEntry() { + super(0, <@cast2/>0); + } + + /** + * Set key + * + * @param key Key to set + */ + private void set${type1.camel}Key(${type1.lower} key) { + this.key = key; + } + + /** + * Set value + * + * @param value Value to set + */ + private void set${type2.camel}Value(${type2.lower} value) { + this.value = value; + } + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/templates/TestFixedCapacityType2TypeMinHeap.java ---------------------------------------------------------------------- diff --git a/giraph-core/templates/TestFixedCapacityType2TypeMinHeap.java b/giraph-core/templates/TestFixedCapacityType2TypeMinHeap.java new file mode 100644 index 0000000..8d274da --- /dev/null +++ b/giraph-core/templates/TestFixedCapacityType2TypeMinHeap.java @@ -0,0 +1,61 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import org.junit.Assert; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +${generated_message} +<#macro cast2><#if type2.lower == "byte">(${type2.lower}) </#if></#macro> +<#macro precision2><#if type2.lower == "float" || type2.lower == "double">, 0</#if></#macro> + +public class TestFixedCapacity${type1.camel}${type2.camel}MinHeap { + @Test + public void testHeap() { + int heapCapacity = 5; + FixedCapacity${type1.camel}${type2.camel}MinHeap heap = + new FixedCapacity${type1.camel}${type2.camel}MinHeap(heapCapacity); + ${type1.lower}[] keys = new ${type1.lower}[]{0, 1, 0, 10, 20, 0, 3, 4}; + ${type2.lower}[] values = new ${type2.lower}[]{ + <@cast2/>0, <@cast2/>1, <@cast2/>2, <@cast2/>2, <@cast2/>2, + <@cast2/>3, <@cast2/>3, <@cast2/>4}; + + List<Integer> positions = new ArrayList<>(); + for (int i = 0; i < keys.length; i++) { + positions.add(i); + } + Collections.shuffle(positions); + for (Integer position : positions) { + heap.add(keys[position], values[position]); + } + + for (int i = keys.length - heapCapacity; i < keys.length; i++) { + Assert.assertEquals(heap.size(), heapCapacity); + Assert.assertEquals(heap.getMinKey(), keys[i]); + Assert.assertEquals(heap.getMinValue(), values[i]<@precision2/>); + heap.removeMin(); + heapCapacity--; + } + Assert.assertTrue(heap.isEmpty()); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/templates/Type2TypeMapEntryIterable.java ---------------------------------------------------------------------- diff --git a/giraph-core/templates/Type2TypeMapEntryIterable.java b/giraph-core/templates/Type2TypeMapEntryIterable.java new file mode 100644 index 0000000..a03634b --- /dev/null +++ b/giraph-core/templates/Type2TypeMapEntryIterable.java @@ -0,0 +1,44 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.giraph.types.heaps; + +import it.unimi.dsi.fastutil.${type1.lower}s.${type1.camel}2${type2.camel}Map;; +import it.unimi.dsi.fastutil.objects.ObjectIterable; +import it.unimi.dsi.fastutil.objects.ObjectIterator; + +/** + * Iterable which has its size and ObjectIterator<${type1.camel}2${type2.camel}Map.Entry> + */ +public interface ${type1.camel}2${type2.camel}MapEntryIterable + extends ObjectIterable<${type1.camel}2${type2.camel}Map.Entry> { + /** + * Get the iterator. Not thread-safe and reuses iterator object, + * so you can't have several iterators at the same time. + * + * @return Iterator + */ + ObjectIterator<${type1.camel}2${type2.camel}Map.Entry> iterator(); + + /** + * Get the size of this iterable + * + * @return Size + */ + int size(); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/templates/TypeTypeConsumer.java ---------------------------------------------------------------------- diff --git a/giraph-core/templates/TypeTypeConsumer.java b/giraph-core/templates/TypeTypeConsumer.java new file mode 100644 index 0000000..90a4ed5 --- /dev/null +++ b/giraph-core/templates/TypeTypeConsumer.java @@ -0,0 +1,36 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.giraph.function.primitive.pairs; + +import java.io.Serializable; + +${generated_message} + +/** + * Primitive specialization of Function: + * (${type1.lower}, ${type2.lower}) -> void + */ +public interface ${type1.camel}${type2.camel}Consumer extends Serializable { + /** + * Applies this function to {@code input1} and {@code input2} + * + * @param input1 First input + * @param input2 Second input + */ + void apply(${type1.lower} input1, ${type2.lower} input2); +} http://git-wip-us.apache.org/repos/asf/giraph/blob/4321e448/giraph-core/templates/TypeTypePredicate.java ---------------------------------------------------------------------- diff --git a/giraph-core/templates/TypeTypePredicate.java b/giraph-core/templates/TypeTypePredicate.java new file mode 100644 index 0000000..7d29d5c --- /dev/null +++ b/giraph-core/templates/TypeTypePredicate.java @@ -0,0 +1,37 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.giraph.function.primitive.pairs; + +import java.io.Serializable; + +${generated_message} + +/** + * Primitive specialization of Function: + * (${type1.lower}, ${type2.lower}) -> boolean + */ +public interface ${type1.camel}${type2.camel}Predicate extends Serializable { + /** + * Returns the result of applying this predicate to {@code input}. + * + * @param input1 First input + * @param input2 Second input + * @return result + */ + boolean apply(${type1.lower} input1, ${type2.lower} input2); +}
