IntSet.java

    1/*******************************************************************************
    2 * Copyright (c) 2009, 2010 Mountainminds GmbH & Co. KG and Contributors
    3 * All rights reserved. This program and the accompanying materials
    4 * are made available under the terms of the Eclipse Public License v1.0
    5 * which accompanies this distribution, and is available at
    6 * http://www.eclipse.org/legal/epl-v10.html
    7 *
    8 * Contributors:
    9 *    Marc R. Hoffmann - initial API and implementation
   10 *    
   11 *******************************************************************************/
   12package org.jacoco.core.instr;
   13
   14import java.util.Arrays;
   15
   16/**
   17 * Lightweight set of sorted int values. The implementation is designed for a
   18 * small number of elements only.
   19 * 
   20 * @author Marc R. Hoffmann
   21 * @version 0.4.1.20101007204400
   22 */
   23final class IntSet {
   24
   25    private int[] store;
   26
   27    private int size;
   28
   29    /**
   30     * Creates a new empty set with a initial capacity of 8 elements.
   31     */
   32    public IntSet() {
   33        this(8);
   34    }
   35
   36    /**
   37     * Creates a new empty set with the given initial capacity.
   38     * 
   39     * @param initialCapacity
   40     *            this is the initial capacity
   41     */
   42    public IntSet(final int initialCapacity) {
   43        this.store = new int[initialCapacity];
   44        this.size = 0;
   45    }
   46
   47    /**
   48     * Adds the given value to the set if it is not already contained.
   49     * 
   50     * @param value
   51     *            value to add
   52     * @return <code>true</code> if the value has actually been added
   53     */
   54    public boolean add(final int value) {
   55        if (contains(value)) {
   56            return false;
   57        }
   58        if (store.length == size) {
   59            final int[] newStore = new int[size * 2];
   60            System.arraycopy(store, 0, newStore, 0, size);
   61            store = newStore;
   62        }
   63        store[size++] = value;
   64        return true;
   65    }
   66
   67    /**
   68     * Clears all elements from the set.
   69     */
   70    public void clear() {
   71        size = 0;
   72    }
   73
   74    /**
   75     * Tests whether the given value is in this set.
   76     * 
   77     * @param value
   78     *            value to check
   79     * @return <code>true</code> if the value is contained
   80     */
   81    public boolean contains(final int value) {
   82        // search backwards as the last value is typically added again
   83        for (int i = size; --i >= 0;) {
   84            if (store[i] == value) {
   85                return true;
   86            }
   87        }
   88        return false;
   89    }
   90
   91    /**
   92     * Returns a sorted array of the current content.
   93     * 
   94     * @return sorted array of the current content
   95     */
   96    public int[] toArray() {
   97        final int[] result = new int[size];
   98        System.arraycopy(store, 0, result, 0, size);
   99        Arrays.sort(result);
  100        return result;
  101    }
  102
  103}