From 9478f1171a79b4dce25596759db2a2cb1831107c Mon Sep 17 00:00:00 2001 From: stephey Date: Sat, 10 Apr 2010 01:57:43 +0000 Subject: [PATCH] Ported over commonly used operations in ArrayList.java from the Java library --Stephen --- Robust/src/Tests/mlp/stephen/ArrayList.java | 313 ++++++++++++++++++++ Robust/src/Tests/mlp/stephen/makefile | 8 +- 2 files changed, 317 insertions(+), 4 deletions(-) create mode 100644 Robust/src/Tests/mlp/stephen/ArrayList.java diff --git a/Robust/src/Tests/mlp/stephen/ArrayList.java b/Robust/src/Tests/mlp/stephen/ArrayList.java new file mode 100644 index 00000000..5234d907 --- /dev/null +++ b/Robust/src/Tests/mlp/stephen/ArrayList.java @@ -0,0 +1,313 @@ + + +public class ArrayList +{ + /** + * The array buffer into which the elements of the ArrayList are stored. + * The capacity of the ArrayList is the length of this array buffer. + */ + private Object[] elementData; + private int size; + + public ArrayList(int initialCapacity) { + this.elementData = new Object[initialCapacity]; + } + + public ArrayList() { + this.elementData = new Object[10]; + } + + /** + * Returns the number of elements in this list. + * + * @return the number of elements in this list + */ + public int size() { + return size; + } + + /** + * Returns true if this list contains no elements. + * + * @return true if this list contains no elements + */ + public boolean isEmpty() { + return size == 0; + } + + /** + * Returns true if this list contains the specified element. + * More formally, returns true if and only if this list contains + * at least one element e such that + * (o==null ? e==null : o.equals(e)). + * + * @param o element whose presence in this list is to be tested + * @return true if this list contains the specified element + */ + public boolean contains(Object o) { + return indexOf(o) >= 0; + } + + /** + * Returns the index of the first occurrence of the specified element + * in this list, or -1 if this list does not contain the element. + * More formally, returns the lowest index i such that + * (o==null ? get(i)==null : o.equals(get(i))), + * or -1 if there is no such index. + */ + public int indexOf(Object o) { + if (o == null) { + for (int i = 0; i < size; i++) + if (elementData[i]==null) + return i; + } else { + for (int i = 0; i < size; i++) + if (o.equals(elementData[i])) + return i; + } + return -1; + } + + /** + * Returns the index of the last occurrence of the specified element + * in this list, or -1 if this list does not contain the element. + * More formally, returns the highest index i such that + * (o==null ? get(i)==null : o.equals(get(i))), + * or -1 if there is no such index. + */ + public int lastIndexOf(Object o) { + if (o == null) { + for (int i = size-1; i >= 0; i--) + if (elementData[i]==null) + return i; + } else { + for (int i = size-1; i >= 0; i--) + if (o.equals(elementData[i])) + return i; + } + return -1; + } + + /** + * Returns the element at the specified position in this list. + * + * @param index index of the element to return + * @return the element at the specified position in this list + * @throws NOTHING + */ + public Object get(int index) { + RangeCheck(index); + + return elementData[index]; + } + + /** + * Replaces the element at the specified position in this list with + * the specified element. + * + * @param index index of the element to replace + * @param element element to be stored at the specified position + * @return the element previously at the specified position + * @throws NOTHING + */ + public Object set(int index, Object element) { + RangeCheck(index); + + Object oldValue = elementData[index]; + elementData[index] = element; + return oldValue; + } + + /** + * Appends the specified element to the end of this list. + * + * @param e element to be appended to this list + * @return true (as specified by {@link Collection#add}) + */ + public boolean add(Object e) { + ensureCapacity(size + 1); // Increments modCount!! + elementData[size++] = e; + return true; + } + + public void ensureCapacity(int minCapacity) + { + int oldCapacity = elementData.length; + if (minCapacity > oldCapacity) + { + Object oldData[] = elementData; + int newCapacity = (oldCapacity * 3)/2 + 1; + if (newCapacity < minCapacity) + newCapacity = minCapacity; + + // minCapacity is usually close to size, so this is a win: + elementData = copyOf(elementData, newCapacity); + } + } + + public Object[] copyOf(Object[] data, int newCap) + { + Object[] array = new Object[newCap]; + + for(int i = 0; i < size; i++) + array[i] = data[i]; + + return array; + } + + /** + * Inserts the specified element at the specified position in this + * list. Shifts the element currently at that position (if any) and + * any subsequent elements to the right (adds one to their indices). + * + * @param index index at which the specified element is to be inserted + * @param element element to be inserted + * @throws NOTHING + */ + public void add(int index, Object element) { + + ensureCapacity(size+1); // Increments modCount!! + systemArrayCopy(elementData, index, elementData, index + 1, + size - index); + elementData[index] = element; + size++; + } + + //Mimics System.arraycopy + public void systemArrayCopy(Object[] a, int orgStart, Object[] b, int newStart, int length) + { + Object[] original; + + if(a != b) + original = a; + else + { + original = new Object[a.length]; + + for(int i = 0; i < a.length; i++) + original[i] = a[i]; + } + + for(int i = 0; i < length && i < (a.length - orgStart - 1) && i < (b.length - newStart - 1); i++) + { + b[i + newStart] = original[i + orgStart]; + } + } + + + /** + * Removes the element at the specified position in this list. + * Shifts any subsequent elements to the left (subtracts one from their + * indices). + * + * @param index the index of the element to be removed + * @return the element that was removed from the list + * @throws NOTHING + */ + public Object remove(int index) { + RangeCheck(index); + + + Object oldValue = elementData[index]; + + int numMoved = size - index - 1; + if (numMoved > 0) + systemArrayCopy(elementData, index+1, elementData, index, + numMoved); + elementData[--size] = null; // Let gc do its work + + return oldValue; + } + + /** + * Removes the first occurrence of the specified element from this list, + * if it is present. If the list does not contain the element, it is + * unchanged. More formally, removes the element with the lowest index + * i such that + * (o==null ? get(i)==null : o.equals(get(i))) + * (if such an element exists). Returns true if this list + * contained the specified element (or equivalently, if this list + * changed as a result of the call). + * + * @param o element to be removed from this list, if present + * @return true if this list contained the specified element + */ + public boolean remove(Object o) { + if (o == null) { + for (int index = 0; index < size; index++) + if (elementData[index] == null) { + fastRemove(index); + return true; + } + } else { + for (int index = 0; index < size; index++) + if (o.equals(elementData[index])) { + fastRemove(index); + return true; + } + } + return false; + } + + /* + * Private remove method that skips bounds checking and does not + * return the value removed. + */ + private void fastRemove(int index) + { + int numMoved = size - index - 1; + if (numMoved > 0) + systemArrayCopy(elementData, index+1, elementData, index, + numMoved); + elementData[--size] = null; // Let gc do its work + } + + /** + * Removes all of the elements from this list. The list will + * be empty after this call returns. + */ + public void clear() { + + // Let gc do its work + for (int i = 0; i < size; i++) + elementData[i] = null; + + size = 0; + } + + + + + /** + * Removes from this list all of the elements whose index is between + * fromIndex, inclusive, and toIndex, exclusive. + * Shifts any succeeding elements to the left (reduces their index). + * This call shortens the list by (toIndex - fromIndex) elements. + * (If toIndex==fromIndex, this operation has no effect.) + * + * @param fromIndex index of first element to be removed + * @param toIndex index after last element to be removed + * @throws NOTHING + */ + protected void removeRange(int fromIndex, int toIndex) { + int numMoved = size - toIndex; + systemArrayCopy(elementData, toIndex, elementData, fromIndex, + numMoved); + + // Let gc do its work + int newSize = size - (toIndex-fromIndex); + while (size != newSize) + elementData[--size] = null; + } + + /** + * Checks if the given index is in range. If not, throws an appropriate + * runtime exception. This method does *not* check if the index is + * negative: It is always used immediately prior to an array access, + * which throws an ArrayIndexOutOfBoundsException if index is negative. + */ + private void RangeCheck(int index) { + if (index >= size) + System.out.println("Array index out of bounds Exception Occured but cannot be thrown (not yet implemented)"); + } +} diff --git a/Robust/src/Tests/mlp/stephen/makefile b/Robust/src/Tests/mlp/stephen/makefile index ce9662a6..ae8bcf8a 100644 --- a/Robust/src/Tests/mlp/stephen/makefile +++ b/Robust/src/Tests/mlp/stephen/makefile @@ -2,20 +2,20 @@ PROGRAM=test SOURCE_FILES=Test.java -BUILDSCRIPT=../../../buildscript +BUILDSCRIPT=../../../../buildscript USEMLP= -mlp 8 2 -mlpdebug # use to turn mlp on and off and make sure rest of build not broken BSFLAGS= -32bit -nooptimize -debug -garbagestats -mainclass Test OWNERSHIP= -ownership -ownallocdepth 1 -enable-assertions -methodeffects -flatirusermethods -ownwritedots final -ownaliasfile aliases.txt default: - ../../../buildscript -nojava $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) + ../../../../buildscript -nojava $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) single: - ../../../buildscript $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES) + ../../../../buildscript $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES) java: - ../../../buildscript $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) + ../../../../buildscript $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) clean: rm -f $(PROGRAM).bin -- 2.34.1