1305

pending completion

Build # 1305

Build Type

Pull #258

travis-ci-com

Committed by

web-flow

Commit Message

<a href="https://github.com/apache/commons-collections/commit/<a class=hub.com/apache/commons-collections/commit/<a class="double-link" href="https://git"><a class=hub.com/apache/commons-collections/commit/<a class="double-link" href="https://git"><a class=hub.com/apache/commons-collections/commit/<a class="double-link" href="https://git"><a class=hub.com/apache/commons-collections/commit/566f8a8450c8903d4e19e5ed1360382d4b12815f">566f8a845">&lt;a href=&quot;https://github.com/apache/commons-collections/commit/</a><a class="double-link" href="https://github.com/apache/commons-collections/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/commons-collections/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/commons-collections/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/commons-collections/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/commons-collections/commit/566f8a8450c8903d4e19e5ed1360382d4b12815f">566f8a845</a><a href="https://github.com/apache/commons-collections/commit/566f8a8450c8903d4e19e5ed1360382d4b12815f">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/apache/commons-collections/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/commons-collections/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/apache/commons-collections/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/apache/commons-collections/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/apache/commons-collections/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/apache/commons-collections/commit/566f8a8450c8903d4e19e5ed1360382d4b12815f&quot;&gt;566f8a845&lt;/a&gt;&lt;a href=&quot;https://github.com/apache/commons-collections/commit/566f8a8450c8903d4e19e5ed1360382d4b12815f&quot;&gt;&amp;quot;&amp;gt;&amp;amp;lt;a href=&amp;amp;quot;https://github.com/apache/commons-collections/co... (continued)

Pull Request Pull Request #258: Simplify bloom filters

Run Details

476 of 476 new or added lines in 15 files covered. (100.0%)

12087 of 13438 relevant lines covered (89.95%)

0.9 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.5

/src/main/java/org/apache/commons/collections4/bloomfilter/BitMapProducer.java

/*
 * 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.commons.collections4.bloomfilter;

import java.util.Arrays;
import java.util.Objects;
import java.util.function.IntPredicate;
import java.util.function.LongPredicate;

/**
 * Produces BitMap longs for a Bloom filter.
 *
 * Each bit map is a little-endian long value representing a block of bits of this filter.
 *
 * <p>The returned array will have length {@code ceil(m / 64)} where {@code m} is the
 * number of bits in the filter and {@code ceil} is the ceiling function.
 * Bits 0-63 are in the first long. A value of 1 at a bit position indicates the bit
 * index is enabled.
 *
 * The producer may stop at the last non zero BitMap or may produce zero value bit maps to the limit determined by
 * a shape..
 *
 * @since 4.5
 */
public interface BitMapProducer {

    /**
     * Each BitMap is passed to the predicate in order.  The predicate is applied to each
     * bitmap value, if the predicate returns {@code false} the execution is stopped, {@code false}
     * is returned, and no further bitmaps are processed.
     *
     * <p>Any exceptions thrown by the action are relayed to the caller.</p>
     *
     * @param predicate the function to execute
     * @return {@code true} if all bitmaps returned {@code true}, {@code false} otherwise.
     * @throws NullPointerException if the specified consumer is null
     */
    boolean forEachBitMap(LongPredicate predicate);

    /**
     * Creates a BitMapProducer from an array of Long.
     * @param bitMaps the bitMaps to return.
     * @return a BitMapProducer.
     */
    static BitMapProducer fromLongArray(long... bitMaps) {
        return new BitMapProducer() {

            @Override
            public boolean forEachBitMap(LongPredicate predicate) {
                for (long word : bitMaps) {
                    if (!predicate.test(word)) {
                        return false;
                    }
                }
                return true;
            }

        };
    }

    /**
     * Creates a BitMapProducer from an IndexProducer.
     * @param producer the IndexProducer that specifies the indexes of the bits to enable.
     * @param numberOfBits the number of bits in the Bloom filter.
     * @return A BitMapProducer that produces the BitMap equivalent of the Indices from the producer.
     */
    static BitMapProducer fromIndexProducer(IndexProducer producer, int numberOfBits) {
        Objects.requireNonNull(producer, "producer");
        Objects.requireNonNull(numberOfBits, "numberOfBits");

        return new BitMapProducer() {
            private int maxBucket = -1;
            private long[] result = new long[BitMap.numberOfBitMaps(numberOfBits)];

            @Override
            public boolean forEachBitMap(LongPredicate predicate) {
                Objects.requireNonNull(predicate, "predicate");
                /*
                 * we can not assume that all the ints will be in order and not repeated. This
                 * is because the HasherCollection does not make the guarantee.
                 */
                // process all the ints into a array of BitMaps
                IntPredicate builder = new IntPredicate() {
                    @Override
                    public boolean test(int i) {
                        int bucketIdx = BitMap.getLongIndex(i);
                        maxBucket = maxBucket < bucketIdx ? bucketIdx : maxBucket;
                        result[bucketIdx] |= BitMap.getLongBit(i);
                        return true;
                    }
                };
                producer.forEachIndex(builder);
                // send the bitmaps to the consumer.
                for (int bucket = 0; bucket <= maxBucket; bucket++) {
                    if (!predicate.test(result[bucket])) {
                        return false;
                    }
                }
                return true;
            }
        };
    }

    /**
     * A LongConsumer that builds an Array of BitMaps as produced by a BitMapProducer.
     *
     */
    class ArrayBuilder implements LongPredicate {
        private long[] result;
        private int idx = 0;
        private int bucketCount = 0;

        /**
         * Constructor that creates an empty ArrayBuilder.
         * @param shape The shape used to generate the BitMaps.
         */
        public ArrayBuilder(Shape shape) {
            this(shape, null);
        }

        /**
         * Constructor that creates an array builder with an initial value.
         * @param shape The shape used to generate the BitMaps.
         * @param initialValue an array of BitMap values to initialize the builder with.  May be {@code null}.
         * @throws IllegalArgumentException is the length of initialValue is greater than the number of
         * buckets as specified by the number of bits in the Shape.
         */
        public ArrayBuilder(Shape shape, long[] initialValue) {
            Objects.requireNonNull(shape, "shape");
            result = new long[BitMap.numberOfBitMaps(shape.getNumberOfBits())];
            if (initialValue != null) {
                if (initialValue.length > result.length) {
                    throw new IllegalArgumentException(
                            String.format("initialValue length (%s) is longer than shape length (%s)",
                                    initialValue.length, result.length));
                }
                bucketCount = initialValue.length;
                System.arraycopy(initialValue, 0, result, 0, initialValue.length);
            }
        }

        @Override
        public boolean test(long bitmap) {
            result[idx++] |= bitmap;
            bucketCount = bucketCount >= idx ? bucketCount : idx;
            return true;
        }

        /**
         * Returns the array.
         * @return the Array of BitMaps.
         */
        public long[] getArray() {
            return Arrays.copyOf(result, bucketCount);
        }
    }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one or more
3	* contributor license agreements. See the NOTICE file distributed with
4	* this work for additional information regarding copyright ownership.
5	* The ASF licenses this file to You under the Apache License, Version 2.0
6	* (the "License"); you may not use this file except in compliance with
7	* the License. You may obtain a copy of the License at
8	*
9	* http://www.apache.org/licenses/LICENSE-2.0
10	*
11	* Unless required by applicable law or agreed to in writing, software
12	* distributed under the License is distributed on an "AS IS" BASIS,
13	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14	* See the License for the specific language governing permissions and
15	* limitations under the License.
16	*/
17	package org.apache.commons.collections4.bloomfilter;
18
19	import java.util.Arrays;
20	import java.util.Objects;
21	import java.util.function.IntPredicate;
22	import java.util.function.LongPredicate;
23
24	/**
25	* Produces BitMap longs for a Bloom filter.
26	*
27	* Each bit map is a little-endian long value representing a block of bits of this filter.
28	*
29	* <p>The returned array will have length {@code ceil(m / 64)} where {@code m} is the
30	* number of bits in the filter and {@code ceil} is the ceiling function.
31	* Bits 0-63 are in the first long. A value of 1 at a bit position indicates the bit
32	* index is enabled.
33	*
34	* The producer may stop at the last non zero BitMap or may produce zero value bit maps to the limit determined by
35	* a shape..
36	*
37	* @since 4.5
38	*/
39	public interface BitMapProducer {
40
41	/**
42	* Each BitMap is passed to the predicate in order. The predicate is applied to each
43	* bitmap value, if the predicate returns {@code false} the execution is stopped, {@code false}
44	* is returned, and no further bitmaps are processed.
45	*
46	* <p>Any exceptions thrown by the action are relayed to the caller.</p>
47	*
48	* @param predicate the function to execute
49	* @return {@code true} if all bitmaps returned {@code true}, {@code false} otherwise.
50	* @throws NullPointerException if the specified consumer is null
51	*/
52	boolean forEachBitMap(LongPredicate predicate);
53
54	/**
55	* Creates a BitMapProducer from an array of Long.
56	* @param bitMaps the bitMaps to return.
57	* @return a BitMapProducer.
58	*/
59	static BitMapProducer fromLongArray(long... bitMaps) {
60	return new BitMapProducer() {	1✔
61
62	@Override
63	public boolean forEachBitMap(LongPredicate predicate) {
64	for (long word : bitMaps) {	1✔
65	if (!predicate.test(word)) {	1✔
66	return false;	×
67	}
68	}
69	return true;	1✔
70	}
71
72	};
73	}
74
75	/**
76	* Creates a BitMapProducer from an IndexProducer.
77	* @param producer the IndexProducer that specifies the indexes of the bits to enable.
78	* @param numberOfBits the number of bits in the Bloom filter.
79	* @return A BitMapProducer that produces the BitMap equivalent of the Indices from the producer.
80	*/
81	static BitMapProducer fromIndexProducer(IndexProducer producer, int numberOfBits) {
82	Objects.requireNonNull(producer, "producer");	1✔
83	Objects.requireNonNull(numberOfBits, "numberOfBits");	1✔
84
85	return new BitMapProducer() {	1✔
86	private int maxBucket = -1;	1✔
87	private long[] result = new long[BitMap.numberOfBitMaps(numberOfBits)];	1✔
88
89	@Override
90	public boolean forEachBitMap(LongPredicate predicate) {
91	Objects.requireNonNull(predicate, "predicate");	1✔
92	/*
93	* we can not assume that all the ints will be in order and not repeated. This
94	* is because the HasherCollection does not make the guarantee.
95	*/
96	// process all the ints into a array of BitMaps
97	IntPredicate builder = new IntPredicate() {	1✔
98	@Override
99	public boolean test(int i) {
100	int bucketIdx = BitMap.getLongIndex(i);	1✔
101	maxBucket = maxBucket < bucketIdx ? bucketIdx : maxBucket;	1✔
102	result[bucketIdx] \|= BitMap.getLongBit(i);	1✔
103	return true;	1✔
104	}
105	};
106	producer.forEachIndex(builder);	1✔
107	// send the bitmaps to the consumer.
108	for (int bucket = 0; bucket <= maxBucket; bucket++) {	1✔
109	if (!predicate.test(result[bucket])) {	1✔
110	return false;	1✔
111	}
112	}
113	return true;	1✔
114	}
115	};
116	}
117
118	/**
119	* A LongConsumer that builds an Array of BitMaps as produced by a BitMapProducer.
120	*
121	*/
122	class ArrayBuilder implements LongPredicate {
123	private long[] result;
124	private int idx = 0;	1✔
125	private int bucketCount = 0;	1✔
126
127	/**
128	* Constructor that creates an empty ArrayBuilder.
129	* @param shape The shape used to generate the BitMaps.
130	*/
131	public ArrayBuilder(Shape shape) {
132	this(shape, null);	1✔
133	}	1✔
134
135	/**
136	* Constructor that creates an array builder with an initial value.
137	* @param shape The shape used to generate the BitMaps.
138	* @param initialValue an array of BitMap values to initialize the builder with. May be {@code null}.
139	* @throws IllegalArgumentException is the length of initialValue is greater than the number of
140	* buckets as specified by the number of bits in the Shape.
141	*/
142	public ArrayBuilder(Shape shape, long[] initialValue) {	1✔
143	Objects.requireNonNull(shape, "shape");	1✔
144	result = new long[BitMap.numberOfBitMaps(shape.getNumberOfBits())];	1✔
145	if (initialValue != null) {	1✔
146	if (initialValue.length > result.length) {	1✔
147	throw new IllegalArgumentException(	1✔
148	String.format("initialValue length (%s) is longer than shape length (%s)",	1✔
149	initialValue.length, result.length));	1✔
150	}
151	bucketCount = initialValue.length;	1✔
152	System.arraycopy(initialValue, 0, result, 0, initialValue.length);	1✔
153	}
154	}	1✔
155
156	@Override
157	public boolean test(long bitmap) {
158	result[idx++] \|= bitmap;	1✔
159	bucketCount = bucketCount >= idx ? bucketCount : idx;	1✔
160	return true;	1✔
161	}
162
163	/**
164	* Returns the array.
165	* @return the Array of BitMaps.
166	*/
167	public long[] getArray() {
168	return Arrays.copyOf(result, bucketCount);	1✔
169	}
170	}
171
172	}

apache / commons-collections / 1305

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous