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}