001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2007 Manu Sridharan
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019: package soot.jimple.spark.ondemand.genericutil;
020:
021: import java.util.Arrays;
022:
023: public class ImmutableStack<T> {
024:
025: private static final ImmutableStack<Object> EMPTY = new ImmutableStack<Object>(
026: new Object[0]);
027:
028: private static final int MAX_SIZE = Integer.MAX_VALUE;
029:
030: public static int getMaxSize() {
031: return MAX_SIZE;
032: }
033:
034: @SuppressWarnings("unchecked")
035: public static final <T> ImmutableStack<T> emptyStack() {
036: return (ImmutableStack<T>) EMPTY;
037: }
038:
039: final private T[] entries;
040:
041: private ImmutableStack(T[] entries) {
042: this .entries = entries;
043: }
044:
045: public boolean equals(Object o) {
046: if (this == o)
047: return true;
048: if (o != null && o instanceof ImmutableStack) {
049: ImmutableStack other = (ImmutableStack) o;
050: return Arrays.equals(entries, other.entries);
051: }
052: return false;
053: }
054:
055: public int hashCode() {
056: return Util.hashArray(this .entries);
057: }
058:
059: @SuppressWarnings("unchecked")
060: public ImmutableStack<T> push(T entry) {
061: assert entry != null;
062: if (MAX_SIZE == 0) {
063: return emptyStack();
064: }
065: int size = entries.length + 1;
066: T[] tmpEntries = null;
067: if (size <= MAX_SIZE) {
068: tmpEntries = (T[]) new Object[size];
069: System.arraycopy(entries, 0, tmpEntries, 0, entries.length);
070: tmpEntries[size - 1] = entry;
071: } else {
072: tmpEntries = (T[]) new Object[MAX_SIZE];
073: System.arraycopy(entries, 1, tmpEntries, 0,
074: entries.length - 1);
075: tmpEntries[MAX_SIZE - 1] = entry;
076:
077: }
078: return new ImmutableStack<T>(tmpEntries);
079: }
080:
081: public T peek() {
082: assert entries.length != 0;
083: return entries[entries.length - 1];
084: }
085:
086: @SuppressWarnings("unchecked")
087: public ImmutableStack<T> pop() {
088: assert entries.length != 0;
089: int size = entries.length - 1;
090: T[] tmpEntries = (T[]) new Object[size];
091: System.arraycopy(entries, 0, tmpEntries, 0, size);
092: return new ImmutableStack<T>(tmpEntries);
093: }
094:
095: public boolean isEmpty() {
096: return entries.length == 0;
097: }
098:
099: public int size() {
100: return entries.length;
101: }
102:
103: public T get(int i) {
104: return entries[i];
105: }
106:
107: public String toString() {
108: String objArrayToString = Util.objArrayToString(entries);
109: assert entries.length <= MAX_SIZE : objArrayToString;
110: return objArrayToString;
111: }
112:
113: public boolean contains(T entry) {
114: return Util.arrayContains(entries, entry, entries.length);
115: }
116:
117: public boolean topMatches(ImmutableStack<T> other) {
118: if (other.size() > size())
119: return false;
120: for (int i = other.size() - 1, j = this .size() - 1; i >= 0; i--, j--) {
121: if (!other.get(i).equals(get(j)))
122: return false;
123: }
124: return true;
125: }
126:
127: @SuppressWarnings("unchecked")
128: public ImmutableStack<T> reverse() {
129: T[] tmpEntries = (T[]) new Object[entries.length];
130: for (int i = entries.length - 1, j = 0; i >= 0; i--, j++) {
131: tmpEntries[j] = entries[i];
132: }
133: return new ImmutableStack<T>(tmpEntries);
134: }
135:
136: @SuppressWarnings("unchecked")
137: public ImmutableStack<T> popAll(ImmutableStack<T> other) {
138: // TODO Auto-generated method stub
139: assert topMatches(other);
140: int size = entries.length - other.entries.length;
141: T[] tmpEntries = (T[]) new Object[size];
142: System.arraycopy(entries, 0, tmpEntries, 0, size);
143: return new ImmutableStack<T>(tmpEntries);
144: }
145:
146: @SuppressWarnings("unchecked")
147: public ImmutableStack<T> pushAll(ImmutableStack<T> other) {
148: // TODO Auto-generated method stub
149: int size = entries.length + other.entries.length;
150: T[] tmpEntries = null;
151: if (size <= MAX_SIZE) {
152: tmpEntries = (T[]) new Object[size];
153: System.arraycopy(entries, 0, tmpEntries, 0, entries.length);
154: System.arraycopy(other.entries, 0, tmpEntries,
155: entries.length, other.entries.length);
156: } else {
157: tmpEntries = (T[]) new Object[MAX_SIZE];
158: // other has size at most MAX_SIZE
159: // must keep all in other
160: // top MAX_SIZE - other.size from this
161: int numFromThis = MAX_SIZE - other.entries.length;
162: System.arraycopy(entries, entries.length - numFromThis,
163: tmpEntries, 0, numFromThis);
164: System.arraycopy(other.entries, 0, tmpEntries, numFromThis,
165: other.entries.length);
166: }
167: return new ImmutableStack<T>(tmpEntries);
168: }
169: }
|