<commit_before>/*
 * SUDA2: An implementation of the SUDA2 algorithm for Java
 * Copyright 2017 <NAME>
 * 
 * Licensed 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 de.linearbits.suda2;

/**
 * A very basic integer set using murmur hashing and linear probing.
 * 
 * @author <NAME>
 */
public class SUDA2IntSetHash extends SUDA2IntSet {

    /** Default */
    private static final float DEFAULT_LOAD_FACTOR      = 0.75f;

    /** Default */
    private static final int   DEFAULT_INITIAL_CAPACITY = 8;

    /**
     * Returns a seed for this specific collection
     * @return
     */
    private static final int getSeed() {
        long seed = System.nanoTime();
        seed = (seed ^ (seed >>> 32)) * 0x4cd6944c5cc20b6dL;
        seed = (seed ^ (seed >>> 29)) * 0xfc12c5b19d3259e9L;
        return (int) (seed ^ (seed >>> 32));
    }

    /**
     * Returns the threshold
     * @param size
     * @return
     */
    private static final int getThreshold(int size) {
        return (int) Math.ceil(size * DEFAULT_LOAD_FACTOR);
    }

    /** Seed */
    private final int seed = getSeed();

    /** Number of elements that can be put into table until a rehash occurs */
    private int       threshold;

    /** The entry array. */
    private int[]     buckets;

    /** Current number of elements. */
    private int       size;

    /** Min */
    private int       min  = Integer.MAX_VALUE;

    /** Max */
    private int       max  = Integer.MIN_VALUE;

    /**
     * Creates a new instance
     */
    public SUDA2IntSetHash() {
        this.buckets = new int[DEFAULT_INITIAL_CAPACITY];
        this.threshold = getThreshold(this.buckets.length);
    }

    /* (non-Javadoc)
     * @see de.linearbits.suda2.SUDA2IntSet#add(int)
     */
    @Override
    public void add(int value) {
        min = Math.min(value, min);
        max = Math.max(value, max);
        this.add(this.buckets, value, hashcode(value));
        size++; // TODO: Hopefully, we never add the same value twice
        if (size == threshold) {
            this.rehash();
        }
    }

    /* (non-Javadoc)
     * @see de.linearbits.suda2.SUDA2IntSet#contains(int)
     */
    @Override
    public boolean contains(int value) {
        
        final int mask = buckets.length - 1;
        final int slot = hashcode(value) & mask;

        for (int i = slot; i < buckets.length; i ++) {
            if (buckets[i] == value) {
                return true;
            } else if (buckets[i] == 0) {
                return false;
            }
        }

        for (int i = 0; i < slot; i ++) {
            if (buckets[i] == value) {
                return true;
            } else if (buckets[i] == 0) {
                return false;
            }
        }
        
        throw new IllegalStateException("Illegal state. This should not happen.");
    }
    
    @Override
    public boolean containsSpecialRow(SUDA2Item[] items, SUDA2Item referenceItem, int[][] data) {
        outer: for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != 0) {
                int[] row = data[buckets[i] - 1];
                for (SUDA2Item item : items) {
                    if (!item.isContained(row)) {
                        continue outer;
                    }
                }
                if (referenceItem.isContained(row)) {
                    continue;
                }
                return true;
            }
        }
        return false;
    }
    
    @Override
    public SUDA2IntSet intersectWith(SUDA2IntSet other) {

        // No intersection
        if (this.max < other.min() || other.max() < this.min) {
            return new SUDA2IntSetSmall();
        }

        // Intersect ranges
        int min = Math.max(this.min,  other.min());
        int max = Math.min(this.max,  other.max());
        
        if (this.size > SUDA2IntSetSmall.SIZE) {
            
            // Bitset
            if (SUDA2IntSetBits.makesSense(min, max, this.size)) {
                
                // Intersect support rows with those provided
                SUDA2IntSetBits rows = new SUDA2IntSetBits(min, max);
                for (int i = 0; i < buckets.length; i++) {
                    int row = buckets[i];
                    if (row != 0 && other.contains(row)) {
                        rows.add(row);
                    }
                }
                return rows;
                
            // Hashset
            } else {
    
                // Intersect support rows with those provided
                SUDA2IntSetHash rows = new SUDA2IntSetHash();
                for (int i = 0; i < buckets.length; i++) {
                    int row = buckets[i];
                    if (row != 0 && row >= min && row <= max && other.contains(row)) {
                        rows.add(row);
                    }
                }
                return rows;<commit_msg>More pruning<commit_after>/*
 * SUDA2: An implementation of the SUDA2 algorithm for Java
 * Copyright 2017 <NAME>
 * 
 * Licensed 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 de.linearbits.suda2;

/**
 * A very basic integer set using murmur hashing and linear probing.
 * 
 * @author <NAME>
 */
public class SUDA2IntSetHash extends SUDA2IntSet {

    /** Default */
    private static final float DEFAULT_LOAD_FACTOR      = 0.75f;

    /** Default */
    private static final int   DEFAULT_INITIAL_CAPACITY = 8;

    /**
     * Returns a seed for this specific collection
     * @return
     */
    private static final int getSeed() {
        long seed = System.nanoTime();
        seed = (seed ^ (seed >>> 32)) * 0x4cd6944c5cc20b6dL;
        seed = (seed ^ (seed >>> 29)) * 0xfc12c5b19d3259e9L;
        return (int) (seed ^ (seed >>> 32));
    }

    /**
     * Returns the threshold
     * @param size
     * @return
     */
    private static final int getThreshold(int size) {
        return (int) Math.ceil(size * DEFAULT_LOAD_FACTOR);
    }

    /** Seed */
    private final int seed = getSeed();

    /** Number of elements that can be put into table until a rehash occurs */
    private int       threshold;

    /** The entry array. */
    private int[]     buckets;

    /** Current number of elements. */
    private int       size;

    /** Min */
    private int       min  = Integer.MAX_VALUE;

    /** Max */
    private int       max  = Integer.MIN_VALUE;

    /**
     * Creates a new instance
     */
    public SUDA2IntSetHash() {
        this.buckets = new int[DEFAULT_INITIAL_CAPACITY];
        this.threshold = getThreshold(this.buckets.length);
    }

    /* (non-Javadoc)
     * @see de.linearbits.suda2.SUDA2IntSet#add(int)
     */
    @Override
    public void add(int value) {
        min = Math.min(value, min);
        max = Math.max(value, max);
        this.add(this.buckets, value, hashcode(value));
        size++; // TODO: Hopefully, we never add the same value twice
        if (size == threshold) {
            this.rehash();
        }
    }

    /* (non-Javadoc)
     * @see de.linearbits.suda2.SUDA2IntSet#contains(int)
     */
    @Override
    public boolean contains(int value) {
        
        final int mask = buckets.length - 1;
        final int slot = hashcode(value) & mask;

        for (int i = slot; i < buckets.length; i ++) {
            if (buckets[i] == value) {
                return true;
            } else if (buckets[i] == 0) {
                return false;
            }
        }

        for (int i = 0; i < slot; i ++) {
            if (buckets[i] == value) {
                return true;
            } else if (buckets[i] == 0) {
                return false;
            }
        }
        
        throw new IllegalStateException("Illegal state. This should not happen.");
    }
    
    @Override
    public boolean containsSpecialRow(SUDA2Item[] items, SUDA2Item referenceItem, int[][] data) {
        outer: for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != 0) {
                int[] row = data[buckets[i] - 1];
                for (SUDA2Item item : items) {
                    if (!item.isContained(row)) {
                        continue outer;
                    }
                }
                if (referenceItem.isContained(row)) {
                    continue;
                }
                return true;
            }
        }
        return false;
    }
    
    @Override
    public SUDA2IntSet intersectWith(SUDA2IntSet other) {

        // No intersection
        if (this.max < other.min() || other.max() < this.min) {
            return new SUDA2IntSetSmall();
        }

        // Intersect ranges
        int min = Math.max(this.min,  other.min());
        int max = Math.min(this.max,  other.max());
        
        if (this.size > SUDA2IntSetSmall.SIZE) {
            
            // Bitset
            if (SUDA2IntSetBits.makesSense(min, max, this.size)) {
                
                // Intersect support rows with those provided
                SUDA2IntSetBits rows = new SUDA2IntSetBits(min, max);
                for (int i = 0; i < buckets.length; i++) {
                    int row = buckets[i];
                    if (row != 0 && row >= min && row <= max && other.contains(row)) {
                        rows.add(row);
                    }
                }
                return rows;
                
            // Hashset
            } else {
    
                // Intersect support rows with those provided
                SUDA2IntSetHash rows = new SUDA2IntSetHash();
                for (int i = 0; i < buckets.length; i++) {
                    int row = buckets[i];
                    if (row != 0 && row >= min && row <= max && other.contains(row)) {
                        rows.add(row);
                    }
                }
                return rows;
{'fraction_non_alphanumeric': 0.1092118636237642, 'fraction_numerical': 0.013304998614062645, 'mean_word_length': 1.5612872692853763, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2884407', 'n_tokens_mistral': 3227, 'n_tokens_neox': 3005, 'n_words': 912}