Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright 1&1 Internet AG, http://www.1and1.org
   *
   * This program is free software; you can redistribute it and/or modify
   * it under the terms of the GNU Lesser General Public License as published by
   * the Free Software Foundation; either version 2 of the License,
   * or (at your option) any later version.
   *
   * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * See the GNU Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public License
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 package net.sf.beezle.sushi.util;
 
 import java.util.List;

A set of non-negative int values. IntBitSet is particularly usefull to store array indexes. IntBitSet is similar to BitSet, but with additional functionality, mainly subset tests and enumeration of elements. Method names follow the style of collections rather than BitSet because usually collections are better known.

Tuned for speed. Each int value is represented by a staticallly chosen bit in a data array. Thus the space required for a set determined by largest element. This is memory-consuming. However. if the set stores array indexes and memory is available for a big array, there is probably enough memory to store big indexes as well.

The method names follow java.util.BitSet instead of java.util.Set. The main reasons are: 1. IntBitSet stores primitive values instead of Objects. 2. IntBitSet is to limited to be called a collection, because adding large int values result in a huge memory consumption.

Java specifies that the right argument of shift operations is implicitly bit-anded with 0x1f. I rely on this and don't mask any indexes.

 
 
 public class IntBitSet implements IntCollectionSerializable {
    
Number to shift in order to switch from an index to an element.
 
     private static final int SHIFT = 5;

    
Bit mask to obtain SHIFT bits.
 
     private static final int MASK = 0x1f;

    
Number of components data is grown if necessary.
 
     private static final int GROW = 8;


    
Storage for the elements.
 
     private int[] data;
 
     //-------------------------------------------------------------
 
    
Creates an empty set.
 
     public IntBitSet() {
          = new int[];
     }

    
Copy constructor.
 
     public IntBitSet(IntBitSet set) {
          = new int[set.data.length];
         System.arraycopy(set.data, 0, , 0, .);
     }
 
     public IntBitSet(int[] data) {
         this. = data;
     }
 
 
     //-------------------------------------------------------------------
     // iteration
 
    
Gets the first element of the set.

Returns:
first element of the set, -1 if the set is empty
 
     public int first() {
         int val;
         int i;
 
         for (i = 0; i < .i++) {
             if ([i] != 0) {
                 val = [i];
                 i <<= ;
                 while ((val & 1) == 0) {
                     val >>>= 1;
                     i++;
                 }
                 return i;
            }
        }
        return -1;
    }

    
Gets the last element of the set.

Returns:
last element of the set, -1 if the set is empty
    public int last() {
        int val;
        int i;
        for (i = . - 1; i >= 0; i--) {
            if ([i] != 0) {
                val = [i] >>> 1;
                i <<= ;
                while (val != 0) {
                    val >>>= 1;
                    i++;
                }
                return i;
            }
        }
        return -1;
    }

    
Gets the element following ele.

Parameters:
ele the element to start with
Returns:
the element following ele, -1 if nothing follows
    public int next(int ele) {
        int idxbitval;
        idx = ele >> ;
        bit = ele & ;
        val = [idx] >>> bit;
        do {
            val >>>= 1;
            bit++;
            if (val == 0) {
                idx++;
                if (idx == .) {
                    return -1;
                }
                val = [idx];
                bit = 0;
            }
        } while ((val & 1) == 0);
        return (idx << ) + bit;
    }
    public int prev(int ele) {
        // TODO: very expensive
        while (ele > 0) {
            ele--;
            if (contains(ele)) {
                return ele;
            }
        }
        return -1;
    }
    //-----------------------------------------------------------------------
    // access elements

    
Lookup a specific element.

Parameters:
ele element to lookup
Returns:
true, if ele is contained in the set
    public boolean contains(int ele) {
        int idx;
        idx = ele >> ;
        if (idx >= .) {
            return false;
        }
        return ([idx] & (1 << ele)) != 0;
    }
    public boolean containsSome(IntBitSet rest) {
        int ele;
        for (ele = first(); ele != -1; ele = next(ele)) {
            if (rest.contains(ele)) {
                return true;
            }
        }
        return false;
    }

    
Add an element.

Parameters:
ele the element to add
    public void add(int ele) {
        int idx;
        idx = ele >> ;
        if (idx >= .) {
            resize(idx + 1 + );
        }
        [ele >> ] |= (1 << ele);
    }

    
Add all elements in the indicated range. Nothing is set for first > last.

Parameters:
first first element to add
last last element to add
    public void addRange(int firstint last) {
        int ele;
        for (ele = firstele <= lastele++) {
            add(ele);
        }
    }

    
Remove an element from the set.

Parameters:
ele element to remove
    public void remove(int ele) {
        int idx;
        idx = ele >> ;
        if (idx < .) {
            [idx] &= ~(1 << ele);
        }
    }

    
Remove all elements in the indicated range.

Parameters:
first first element to remove
last last element to remove
    public void removeRange(int firstint last) {
        int ele;
        for (ele = firstele <= lastele++) {
            remove(ele);
        }
    }

    
Remove all elements.
    public void clear() {
        int i;
        for (i = 0; i < .i++) {
            [i] = 0;
        }
    }
    //-----------------------------------------------------------------------
    // comparison
    @Override
    public int hashCode() {
        return size();
    }
    
    
Comparison.

Parameters:
obj the Object to compare with
Returns:
true, if obj is a set and contains exactly the same elements as this set
    @Override
    public boolean equals(Object obj) {
        IntBitSet set;
        int i;
        int[] x;
        int[] y;
        if (!(obj instanceof IntBitSet)) {
            return false;
        }
        set = (IntBitSetobj;
        if (. < set.data.length) {
            x = ;
            y = set.data;
        } else {
            x = set.data;
            y = ;
        }
        for (i = 0; i < x.lengthi++) {
            if (x[i] != y[i]) {
                return false;
            }
        }
        for ( ; i < y.lengthi++) {
            if (y[i] != 0) {
                return false;
            }
        }
        return true;
    }

    
The subset test.

Parameters:
set the set to be compared with
Returns:
true, if the argument is contained
    public boolean containsAll(IntBitSet set) {
        int iend;
        if (. < set.data.length) {
            end = .;
            for (i = endi < set.data.lengthi++) {
                if (set.data[i] != 0) {
                    return false;
                }
            }
        } else {
            end = set.data.length;
        }
        for (i = 0; i < endi++) {
            // any bits in set where this has none?  -> false
            if ((set.data[i] & ~[i])!= 0) {
                return false;
            }
        }
        return true;
    }
    //----------------------------------------------------------------------
    // set operations

    
Computes the intersection. The result is stored in this set.

Parameters:
set the set to be combined with
    public void retainAll(IntBitSet set) {
        int i;
        if (set.data.length > .) {
            resize(set.data.length);
        }
        for (i = 0; i < set.data.lengthi++) {
            [i] &= set.data[i];
        }
        for ( ; i < .i++) {
            [i] = 0;
        }
    }

    
Computes the set difference. The result is stored in this set.

Parameters:
set the set to be combined with
    public void removeAll(IntBitSet set) {
        int iend;
        end = (set.data.length < .)? set.data.length : .;
        for (i = 0; i < endi++) {
            [i] &= ~set.data[i];
        }
    }

    
Computes the union. The result is stored in this set.

Parameters:
set the set to be combined with
    public void addAll(IntBitSet set) {
        int i;
        if (set.data.length > .) {
            resize(set.data.length);
        }
        for (i = 0; i < set.data.lengthi++) {
            [i] |= set.data[i];
        }
    }
    public void addAllSets(IntBitSet[] related) {
        int ele;
        for (ele = first(); ele != -1; ele = next(ele)) {
            addAll(related[ele]);
        }
    }
    //----------------------------------------------------------------
    // misc

    
Counts the elements.

Returns:
number of elements in this set
    public int size() {
        int elecount;
        count = 0;
        for (ele = first(); ele != -1; ele = next(ele)) {
            count++;
        }
        return count;
    }

    
Tests for the empty set.

Returns:
true, if the set contains no elements
    public boolean isEmpty() {
        return first() == -1;
    }

    
Creates an array with all elements of the set.

Returns:
array with all elements of the set
    public int[] toArray() {
        int iele;
        int[] result;
        result = new int[size()];
        for (ele = first(), i = 0; ele != -1; ele = next(ele), i++) {
            result[i] = ele;
        }
        return result;
    }

    
Changes data to have data.length >= s components. All data components that fit into the new size are preserved.

Parameters:
s new data size wanted
    private void resize(int s) {
        int[] n;
        int count;
        n = new int[s];
        count = (s < .)? s : .;
        System.arraycopy(, 0, n, 0, count);
         = n;
    }
    //-----------------------------------------------------------------
    // output

    
Returns a String representation of the set.

Returns:
a String listing all elements
    @Override
    public String toString() {
        StringBuilder buffer;
        int ele;
        buffer = new StringBuilder("{");
        for (ele = first(); ele != -1; ele = next(ele)) {
            buffer.append(' ').append(ele);
        }
        buffer.append(" }");
        return buffer.toString();
    }

    
Returns a String representation with each element represented by a String taken from a Symboltable.

Parameters:
symbols supplies the symbols to represent the elements of the set; a RuntimeException is thrown if an element is not found here
Returns:
a String listing all elements of the set
    public String toString(List<?> symbols) {
         StringBuilder buf;
         int ele;
         int max;
         
         max = symbols.size();
         buf = new StringBuilder("{");
         for (ele = first(); ele != -1; ele = next(ele)) {
             buf.append(" ");
             if (ele < max) {
                 buf.append(symbols.get(ele));
             } else {
                 buf.append('<').append(ele).append('>');
             }
         }
         buf.append(" }");
         return buf.toString();
    }
New to GrepCode? Check out our FAQ X