001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * AutomataLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.commons.util.array;
018
019
020import java.lang.reflect.Array;
021import java.util.Arrays;
022
023/**
024 * Class that provides a resizable array storage of a certain type.
025 * 
026 * @author Malte Isberner <malte.isberner@gmail.com>
027 *
028 * @param <T> element class.
029 */
030public class ResizingArrayStorage<T> {
031        /**
032         * The default initial capacity of the array storage.
033         */
034        public static final int DEFAULT_INITIAL_CAPACITY = 10;
035        
036        private final Class<T[]> arrayClazz;
037        public T[] array;
038        private int nextCapacityHint;
039        
040        /**
041         * Constructor. Creates an array storage with a default initial
042         * capacity of {@link ResizingArrayStorage#DEFAULT_INITIAL_CAPACITY}.
043         * 
044         * @param arrayClazz the class of the storage array.
045         */
046        public ResizingArrayStorage(Class<T[]> arrayClazz) {
047                this(arrayClazz, DEFAULT_INITIAL_CAPACITY);
048        }
049        
050        /**
051         * Constructor. Creates an array with the specified initial capacity.
052         * 
053         * @param arrayClazz the class of the storage array.
054         * @param initialCapacity the initial capacity.
055         */
056        @SuppressWarnings("unchecked")
057        public ResizingArrayStorage(Class<T[]> arrayClazz, int initialCapacity) {
058                if(initialCapacity <= 0)
059                        initialCapacity = DEFAULT_INITIAL_CAPACITY;
060                this.array = (T[])Array.newInstance(arrayClazz.getComponentType(),
061                                initialCapacity);
062                this.arrayClazz = arrayClazz;
063        }
064        
065        
066        /**
067         * Ensures that the storage has room for at least the specified number
068         * of elements.
069         * 
070         * @param minCapacity the minimal number of elements the storage array
071         * has to provide room for.
072         * @return <code>true</code> iff the storage array had to be resized,
073         * <code>false</code> otherwise.
074         */
075        public boolean ensureCapacity(int minCapacity) {
076                if (minCapacity <= array.length)
077                        return false;
078
079                int newCapacity = (array.length * 3) / 2 + 1;
080                if (newCapacity < nextCapacityHint)
081                        newCapacity = nextCapacityHint;
082
083                if (newCapacity < minCapacity)
084                        newCapacity = minCapacity;
085
086                array = Arrays.copyOf(array, newCapacity);
087                nextCapacityHint = 0;
088                return true;
089        }
090        
091        /**
092         * Shrinks the storage to the specified maximum capacity.
093         * 
094         * If the current capacity is less or equal to the specified capacity,
095         * nothing happens.
096         * 
097         * @param maxCapacity the maximal number of elements the storage array
098         * has to provide room for.
099         * @return <code>true</code> iff the storage array had to be resized,
100         * <code>false</code> otherwise.
101         */
102        public boolean shrink(int maxCapacity) {
103                if(maxCapacity >= array.length)
104                        return false;
105                
106                array = Arrays.copyOf(array, maxCapacity);
107                return true;
108        }
109        
110        /**
111         * Sets the minimum new capacity that the storage will have
112         * after the next resize. 
113         * @param nextCapacityHint the minimum next capacity hint.
114         */
115        public void hintNextCapacity(int nextCapacityHint) {
116                this.nextCapacityHint = nextCapacityHint;
117        }
118
119        /**
120         * Sets all the elements in the array to the specified value.
121         * @param value the value.
122         */
123        public void setAll(T value) {
124                for(int i = 0; i < array.length; i++)
125                        array[i] = value;
126        }
127        
128        public void swap(ResizingArrayStorage<T> other) {
129                if(arrayClazz != other.arrayClazz)
130                        throw new IllegalArgumentException("Cannot swap array storages of different array classes (" + arrayClazz.getSimpleName() + " vs. " + other.arrayClazz.getSimpleName());
131                T[] arrayTmp = array;
132                int hintTmp = nextCapacityHint;
133                array = other.array;
134                nextCapacityHint = other.nextCapacityHint;
135                other.array = arrayTmp;
136                other.nextCapacityHint = hintTmp;
137        }
138}