2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
6 * The Java Pathfinder core (jpf-core) platform is licensed under the
7 * Apache License, Version 2.0 (the "License"); you may not use this file except
8 * in compliance with the License. You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0.
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
18 package gov.nasa.jpf.util;
20 import java.io.PrintStream;
21 import java.util.ArrayList;
22 import java.util.Arrays;
23 import java.util.Comparator;
24 import java.util.Iterator;
25 import java.util.NoSuchElementException;
28 * more customizable alternative to java.util.Vector. Other than Vector, it
29 * supports dynamic growth on set() operations. While it supports list
30 * functions such as append, ObjVector resembles mostly an array, i.e.
31 * is meant to be a random-access collection
33 * this collection does not keep a count of non-null elements, but does maintain the
34 * highest set index as its size through set/add and remove operations. Note that size
35 * only shrinks through remove operations, not by setting null values. This means there
36 * is no guarantee that data[size-1] is not null. The converse however is true - there is no
37 * non-null element at an index >= size.
41 public class ObjVector<E> implements ReadOnlyObjList<E>, Cloneable {
42 public static final int defaultInitCap = 40;
44 /** <i>size</i> as in a java.util.Vector. */
47 /** the backing array. */
48 protected Object[] data;
50 /** growth strategy. */
51 protected Growth growth;
56 public ObjVector(Growth initGrowth, int initCap) {
58 data = new Object[initCap];
62 public ObjVector(Growth initGrowth) {
63 this(initGrowth,defaultInitCap);
66 public ObjVector(int initCap) {
67 this(Growth.defaultGrowth, initCap);
71 this(Growth.defaultGrowth,defaultInitCap);
74 public <F extends E> ObjVector(F[] init) {
79 public <F extends E> ObjVector(ObjVector<F> from) {
80 this.data = new Object[from.data.length];
81 this.size = from.size;
82 this.growth = from.growth;
83 System.arraycopy(from.data, 0, this.data, 0, size);
86 //--- set/add/remove operations
88 public void add(E x) {
89 if (size >= data.length) {
90 ensureCapacity(size+1);
96 public void addNulls (int length) {
97 int newSize = size + length;
98 if (newSize > data.length) {
99 ensureCapacity(size + length);
101 for (int i = size; i < newSize; i++) {
107 public <F extends E> void append(F[] x) {
108 if (size + x.length > data.length) {
109 ensureCapacity(size + x.length);
111 System.arraycopy(x, 0, data, size, x.length);
115 public <F extends E> void append(F[] x, int pos, int len) {
116 if (size + len > data.length) {
117 ensureCapacity(size + len);
119 System.arraycopy(x, pos, data, size, len);
123 public <F extends E> void append(ObjVector<F> x) {
124 if (size + x.size > data.length) {
125 ensureCapacity(size + x.size);
127 System.arraycopy(x.data, 0, data, size, x.size);
131 @SuppressWarnings("unchecked")
132 public <F extends E> void append(ObjArray<F> x) {
133 append((F[])(x.data));
136 public <F extends E> void append(ArrayList<F> x){
138 int newSize = size + n;
139 if (newSize > data.length) {
140 ensureCapacity(newSize);
142 for (int i = size, j=0; i < newSize; i++,j++) {
148 public <F extends E> void addAll(Iterable<F> x) {
149 if (x instanceof ObjVector) {
150 append((ObjVector<F>) x);
154 if (x instanceof ObjArray) {
155 append((ObjArray<F>) x);
159 if (x == null) return;
166 public int nextNull (int fromIndex){
167 for (int i=fromIndex; i<size; i++){
168 if (data[i] == null){
173 ensureCapacity(size+1);
178 @SuppressWarnings("unchecked")
179 public E get(int idx) {
183 return (E) data[idx];
187 public void set(int idx, E v) {
193 * set range of values
194 * @param fromIndex first index (inclusive)
195 * @param toIndex last index (exclusive)
196 * @param val value to set
198 public void setRange (int fromIndex, int toIndex, E val) {
200 Arrays.fill(data, fromIndex, toIndex, val);
203 public <F> F[] toArray (F[] dst) {
204 System.arraycopy(data,0,dst,0,size);
208 public ObjArray<E> toObjArray () {
209 ObjArray<E> dst = new ObjArray<E>(size);
210 System.arraycopy(data,0,dst.data,0,size);
214 public int dumpTo (Object[] dst, int pos) {
215 System.arraycopy(data,0,dst,pos,size);
220 public ObjVector<E> clone() {
221 return new ObjVector<E>(this);
224 public void squeeze() {
225 while (size > 0 && data[size - 1] == null) size--;
228 public void setSize(int sz) {
240 public void clear() {
241 // faster than iterating over the whole array
242 data = new Object[data.length];
246 @SuppressWarnings("unchecked")
247 public void clearAllSatisfying (Predicate<E> pred) {
250 for (int i=size-1; i>=0; i--) {
253 if (pred.isTrue(e)) {
271 public int length() {
275 public void ensureSize(int sz) {
282 public void ensureCapacity(int desiredCap) {
283 if (data.length < desiredCap) {
284 Object[] newData = new Object[growth.grow(data.length, desiredCap)];
285 System.arraycopy(data, 0, newData, 0, size);
290 @SuppressWarnings("unchecked")
291 public void sort(Comparator<? super E> comp) {
292 Arrays.sort(data, 0, size, (Comparator<Object>) comp);
295 public static <E> void copy(ObjVector<? extends E> src, int srcPos,
296 ObjVector<E> dst, int dstPos, int len) {
297 src.ensureCapacity(srcPos + len);
298 dst.ensureSize(dstPos+len);
299 System.arraycopy(src.data, srcPos, dst.data, dstPos, len);
302 public static <E> void copy(ObjVector<? extends E> src, int srcPos,
303 E[] dst, int dstPos, int len) {
304 src.ensureCapacity(srcPos + len);
305 //dst.ensureSize(dstPos+len);
306 System.arraycopy(src.data, srcPos, dst, dstPos, len);
310 * remove all non-null elements between 'fromIdx' (inclusive) and
311 * 'toIdx' (exclusive)
312 * throw IndexOutOfBoundsException if index values are out of range
314 public int removeRange(int fromIdx, int toIdx){
316 Object[] data = this.data;
318 // it's the callers responsibility to ensure proper index ranges
319 //if (fromIdx < 0) fromIdx = 0;
320 //if (toIdx > size) toIdx = size;
322 for (int i=fromIdx; i<toIdx; i++){
323 if (data[i] != null){
331 for (; i>=0 && (data[i] == null); i--);
338 public int removeFrom(int fromIdx){
339 return removeRange(fromIdx,size);
342 public E remove (int i) {
349 for (; j>=0 && (data[j] == null); j--);
357 //--- store/restore snapshot operations
359 static final int DEFAULT_MAX_GAP = 10;
362 * this is a block operation snapshot that stores chunks of original data with
363 * not more than DEFAULT_MAX_GAP consecutive null elements. Use this if
364 * elements can be stored directly
366 public static class Snapshot<E> {
372 Block (int baseIndex, Object[] data, Block next){
373 this.baseIndex = baseIndex;
379 // the ObjVector state we directly store
383 // where we keep the data
386 int saveBlock (Object[] d, int start, int end) {
387 int len = end-start+1;
388 Object[] bd = new Object[len];
389 System.arraycopy(d, start, bd, 0, len);
390 head = new Block(start, bd, head);
395 Snapshot (ObjVector<E> v, int maxGap){
401 int end = -1, start = -1;
403 for (int i=n-1; (i>=0) && (n>0); i--) {
405 if (start > 0 && (start - i) > maxGap ) { // store prev block
406 n -= saveBlock( d, start, end);
419 if (end >=0 && end >= start) {
420 saveBlock( d, start, end);
424 public void restore (ObjVector<E> v) {
425 // this is faster than iterating through the array
426 Object[] d = new Object[size];
429 for (Block block = head; block != null; block = block.next) {
430 Object[] bd = block.data;
431 System.arraycopy(bd, 0, d, block.baseIndex, bd.length);
440 public Snapshot<E> getSnapshot(){
441 return new Snapshot<E>(this, DEFAULT_MAX_GAP);
445 * create a snapshot that doesn't store more than maxGap consecutive null values
447 public Snapshot<E> getSnapshot( int maxGap){
448 return new Snapshot<E>(this, maxGap);
451 public void restore (Snapshot<E> snap) {
457 * snapshot that can mutate element values, but therefore can't use block operations.
458 * This is slower to store/restore, but can be more memory efficient if the elements
459 * are fragmented (lots of small holes in data)
462 public static class MutatingSnapshot<E,T>{
466 @SuppressWarnings("unchecked")
467 MutatingSnapshot (ObjVector<E> vec, Transformer<E,T> transformer){
468 E[] d = (E[])vec.data;
472 //--- get number of non-null elements
473 for (int i=0; i<size; i++) {
480 T[] values = (T[])new Object[len];
481 int[] indices = new int[len];
485 for (int i=0; j < len; i++) {
488 values[j] = transformer.transform(d[i]);
493 this.values = values;
494 this.indices = indices;
497 @SuppressWarnings("unchecked")
498 protected void restore (ObjVector<E> vec, Transformer<T,E> transformer) {
499 T[] values = this.values;
500 int[] indices = this.indices;
501 int len = indices.length;
502 int size = indices[len-1] +1;
505 vec.ensureSize(size);
506 E[] d = (E[])vec.data;
508 for (int i=0; i<len; i++){
509 E obj = transformer.transform(values[i]);
510 int index = indices[i];
518 public <T> MutatingSnapshot<E,T> getSnapshot( Transformer<E,T> transformer){
519 return new MutatingSnapshot<E,T>(this, transformer);
522 public <T> void restore (MutatingSnapshot<E,T> snap, Transformer<T,E> transformer) {
523 snap.restore(this, transformer);
530 * iterator that goes over all elements regardless of value (i.e. also includes null values)
532 protected class OVIterator implements Iterator<E> {
536 public boolean hasNext () {
541 @SuppressWarnings("unchecked")
543 if (idx >= data.length) throw new NoSuchElementException();
550 public void remove () {
551 throw new UnsupportedOperationException();
556 public Iterator<E> iterator () {
557 return new OVIterator();
561 * iterator that only includes element values that are not null
563 protected class NonNullIterator implements Iterator<E>, Iterable<E> {
568 public boolean hasNext() {
569 return (idx < size); // size is max set index
573 @SuppressWarnings("unchecked")
575 int len = data.length;
576 for (int i=idx; i<len; i++){
585 throw new NoSuchElementException();
589 public void remove () {
590 throw new UnsupportedOperationException();
594 public Iterator<E> iterator() {
601 public Iterator<E> nonNullIterator() {
602 return new NonNullIterator();
605 public Iterable<E> elements() {
606 return new NonNullIterator();
609 public void process (Processor<E> processor) {
610 for (int i=0; i<data.length; i++) {
613 processor.process( (E)o);
618 //--- misc (debugging etc.)
620 public void printOn (PrintStream ps) {
621 ps.println("ObjVector = [");
622 for (int i=0; i<size; i++) {