package jsat.utils;

import java.io.Serializable;
import java.util.*;

/**
 * A utility class for efficiently storing a set of integers. In order to do 
 * this, the integers are stored in their natural order. 
 * 
 * @author Edward Raff
 */
public class IntSortedSet extends AbstractSet implements Serializable, SortedSet
{

    private static final long serialVersionUID = -2675363824037596497L;

    private static final int defaultSize = 8;

    private int[] store;
    private int size;
    
    public IntSortedSet(int initialSize)
    {
        store = new int[initialSize];
        size = 0;
    }
    
    /**
     * Creates a new set of integers from the given set 
     * @param set the set of integers to create a copy of
     */
    public IntSortedSet(Set set)
    {
        this(set.size());
        for(Integer integer : set)
            this.add(integer);
    }
    
    /**
     * Creates a set of integers from the given collection
     * @param collection a collection of integers to create a set from
     */
    public IntSortedSet(Collection collection)
    {
        this();
        for(Integer integer : collection)
            this.add(integer);
    }
    
    /**
     * Creates a set of integers from the given list of integers. 
     * @param ints a list of integers to create a set from
     * @return a set of integers of all the unique integers in the given list
     */
    public static IntSortedSet from(int... ints)
    {
        return new IntSortedSet(IntList.view(ints, ints.length));
    }
    
    public IntSortedSet()
    {
        this(defaultSize);
    }

    @Override
    public boolean add(Integer e)
    {
        if(e == null)
            return false;
        int insertionPoint = Arrays.binarySearch(store, 0, size, e);
        if(insertionPoint >= 0 )
            return false;//Already in the set
        //Fix up to where we would like to place it
        insertionPoint = (-(insertionPoint) - 1);
        
        //Increase store size if needed
        if(size >= store.length)
            store = Arrays.copyOf(store, Math.max(1, store.length)*2);
        
        for(int i = size; i > insertionPoint; i--)
            store[i] = store[i-1];
        store[insertionPoint] = e;
        size++;
        
        return true;
    }

    public boolean contains(int o)
    {
        int insertionPoint = Arrays.binarySearch(store, 0, size, o);
        if(insertionPoint >= 0 )
            return true;//Already in the set
        else
            return false;
    }
    
    @Override
    public boolean contains(Object o)
    {
        if(o != null && o instanceof Integer)
            return contains(((Integer)o).intValue());
        else
            return false;
    }
    
    
    @Override
    public Iterator iterator()
    {
        final Iterator iterator = new Iterator() 
        {
            int index = 0;
            boolean canRemove = false;

            @Override
            public boolean hasNext()
            {
                return index < size;
            }

            @Override
            public Integer next()
            {
                if(!hasNext())
                    throw new NoSuchElementException("The whole set has been iterated");
                canRemove = true;
                return store[index++];
            }

            @Override
            public void remove()
            {
                if(!canRemove)
                    throw new IllegalStateException("Can not remove, remove can only occur after a successful call to next");
                
                for(int i = index; i < size; i++ )
                    store[i-1] = store[i];
                
                index--;
                size--;
                canRemove = false;
            }
        };
        return iterator;
    }

    @Override
    public int size()
    {
        return size;
    }

    @Override
    public Comparator comparator()
    {
        return new Comparator()
        {
            @Override
            public int compare(Integer o1, Integer o2)
            {
                return o1.compareTo(o2);
            }
        };
    }

    @Override
    public SortedSet subSet(Integer fromElement, Integer toElement)
    {
        if(fromElement > toElement)
            throw new IllegalArgumentException("fromKey was > toKey");
        return new IntSortedSubSet(fromElement, toElement-1, this);
    }

    @Override
    public SortedSet headSet(Integer toElement)
    {
        return new IntSortedSubSet(Integer.MIN_VALUE, toElement-1, this);
    }

    @Override
    public SortedSet tailSet(Integer fromElement)
    {
        return new IntSortedSubSet(fromElement, Integer.MAX_VALUE-1, this);
    }

    @Override
    public Integer first()
    {
        return store[0];
    }

    @Override
    public Integer last()
    {
        return store[size-1];
    }
    
    private class IntSortedSubSet extends AbstractSet implements Serializable, SortedSet
    {
        int minValidValue;
        int maxValidValue;
        IntSortedSet parent;
        
        public IntSortedSubSet(int minValidValue, int maxValidValue, IntSortedSet parent)
        {
            this.minValidValue = minValidValue;
            this.maxValidValue = maxValidValue;
            this.parent = parent;
        }
        
        @Override
        public boolean add(Integer e)
        {
            if(e == null)
                return false;
            if(e < minValidValue || e > maxValidValue)
                throw new IllegalArgumentException("You can not add to a sub-set view outside of the constructed range");
            return parent.add(e);
        }

        public boolean contains(int o)
        {
            if(o < minValidValue || o > maxValidValue)
                return false;
            return parent.contains(o);
        }

        @Override
        public boolean contains(Object o)
        {
            if(o != null && o instanceof Integer)
                return contains(((Integer)o).intValue());
            else
                return false;
        }

        @Override
        public Iterator iterator()
        {
            int start = Arrays.binarySearch(store, 0, size, minValidValue);
            if (start < 0)
                start = (-(start) - 1);
            final int start_pos = start;
            final Iterator iterator = new Iterator() 
            {
                int index = start_pos;
                boolean canRemove = false;

                @Override
                public boolean hasNext()
                {
                    return index < size && store[index] <= maxValidValue;
                }

                @Override
                public Integer next()
                {
                    if(!hasNext())
                        throw new NoSuchElementException("The whole set has been iterated");
                    canRemove = true;
                    return store[index++];
                }

                @Override
                public void remove()
                {
                    if(!canRemove)
                        throw new IllegalStateException("Can not remove, remove can only occur after a successful call to next");

                    for(int i = index; i < size; i++ )
                        store[i-1] = store[i];

                    index--;
                    size--;
                    canRemove = false;
                }
            };
            return iterator;
        }

        @Override
        public int size()
        {
            int start = Arrays.binarySearch(store, 0, size, minValidValue);
            if (start < 0)
                start = (-(start) - 1);
            int end = Arrays.binarySearch(store, 0, size, maxValidValue);
            if (end < 0)
                end = (-(end) - 1);
            if(end < size && store[end] == maxValidValue)//should only happen once b/c we are a set
                end++;
            return end-start;
        }

        @Override
        public Comparator comparator()
        {
            return parent.comparator();
        }

        @Override
        public SortedSet subSet(Integer fromElement, Integer toElement)
        {
            if(fromElement > toElement)
                throw new IllegalArgumentException("fromKey was > toKey");
            return parent.subSet(Math.max(minValidValue, fromElement), Math.min(maxValidValue+1, toElement));
        }

        @Override
        public SortedSet headSet(Integer toElement)
        {
            return new IntSortedSubSet(Math.max(Integer.MIN_VALUE, minValidValue), Math.min(toElement-1, maxValidValue), parent);
//            return parent.headSet(Math.min(toElement, maxValidValue+1));
        }

        @Override
        public SortedSet tailSet(Integer fromElement)
        {
            return new IntSortedSubSet(Math.max(fromElement, minValidValue), Math.min(Integer.MAX_VALUE-1, maxValidValue), parent);
//            return parent.tailSet(Math.max(fromElement, minValidValue));
        }

        @Override
        public Integer first()
        {
            int start = Arrays.binarySearch(store, 0, size, minValidValue);
            if (start < 0)
                start = (-(start) - 1);
            return store[start];
        }

        @Override
        public Integer last()
        {
            int pos = Arrays.binarySearch(store, 0, size, maxValidValue);
            if (pos < 0)
                pos = (-(pos) - 1);
            //can end up at a pos out of valid range, so back up if needed
            while(pos >= 0 && store[pos] > maxValidValue)
                pos--;
            return store[pos];
        }
        
    }
    
}

 

Ads help maintain this website.