text: package soot.jimple.spark.ondemand.genericutil;
  
  /*-
   * #%L
   * Soot - a J*va Optimization Framework
   * %%
   * Copyright (C) 2007 Manu Sridharan
   * %%
   * This program is free software: you can redistribute it and/or modify
   * it under the terms of the GNU Lesser General Public License as
   * published by the Free Software Foundation, either version 2.1 of the
   * License, or (at your option) any later version.
   * 
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Lesser Public License for more details.
   * 
   * You should have received a copy of the GNU General Lesser Public
   * License along with this program.  If not, see
   * <http://www.gnu.org/licenses/lgpl-2.1.html>.
   * #L%
   */
  
  import java.util.Arrays;
  
  public class ImmutableStack<T> {
  
    private static final ImmutableStack<Object> EMPTY = new ImmutableStack<Object>(new Object[0]);
  
    private static final int MAX_SIZE = Integer.MAX_VALUE;
  
    public static int getMaxSize() {
      return MAX_SIZE;
    }
  
    @SuppressWarnings("unchecked")
    public static final <T> ImmutableStack<T> emptyStack() {
      return (ImmutableStack<T>) EMPTY;
    }
  
    final private T[] entries;
  
    private ImmutableStack(T[] entries) {
      this.entries = entries;
    }
  
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (o != null && o instanceof ImmutableStack) {
        ImmutableStack other = (ImmutableStack) o;
        return Arrays.equals(entries, other.entries);
      }
      return false;
    }
  
    public int hashCode() {
      return Util.hashArray(this.entries);
    }
  
    @SuppressWarnings("unchecked")
    public ImmutableStack<T> push(T entry) {
      assert entry != null;
      if (MAX_SIZE == 0) {
        return emptyStack();
      }
      int size = entries.length + 1;
      T[] tmpEntries = null;
      if (size <= MAX_SIZE) {
        tmpEntries = (T[]) new Object[size];
        System.arraycopy(entries, 0, tmpEntries, 0, entries.length);
        tmpEntries[size - 1] = entry;
      } else {
        tmpEntries = (T[]) new Object[MAX_SIZE];
        System.arraycopy(entries, 1, tmpEntries, 0, entries.length - 1);
        tmpEntries[MAX_SIZE - 1] = entry;
  
      }
      return new ImmutableStack<T>(tmpEntries);
    }
  
    public T peek() {
      assert entries.length != 0;
      return entries[entries.length - 1];
    }
  
    @SuppressWarnings("unchecked")
    public ImmutableStack<T> pop() {
      assert entries.length != 0;
      int size = entries.length - 1;
      T[] tmpEntries = (T[]) new Object[size];
      System.arraycopy(entries, 0, tmpEntries, 0, size);
      return new ImmutableStack<T>(tmpEntries);
    }
  
    public boolean isEmpty() {
      return entries.length == 0;
    }
  
    public int size() {
      return entries.length;
    }
  
    public T get(int i) {
      return entries[i];
    }
  
    public String toString() {
      String objArrayToString = Util.objArrayToString(entries);
      assert entries.length <= MAX_SIZE : objArrayToString;
      return objArrayToString;
    }
  
    public boolean contains(T entry) {
      return Util.arrayContains(entries, entry, entries.length);
    }
  
    public boolean topMatches(ImmutableStack<T> other) {
      if (other.size() > size()) {
        return false;
      }
      for (int i = other.size() - 1, j = this.size() - 1; i >= 0; i--, j--) {
        if (!other.get(i).equals(get(j))) {
          return false;
        }
      }
      return true;
    }
  
    @SuppressWarnings("unchecked")
    public ImmutableStack<T> reverse() {
      T[] tmpEntries = (T[]) new Object[entries.length];
      for (int i = entries.length - 1, j = 0; i >= 0; i--, j++) {
        tmpEntries[j] = entries[i];
      }
      return new ImmutableStack<T>(tmpEntries);
    }
  
    @SuppressWarnings("unchecked")
    public ImmutableStack<T> popAll(ImmutableStack<T> other) {
      // TODO Auto-generated method stub
      assert topMatches(other);
      int size = entries.length - other.entries.length;
      T[] tmpEntries = (T[]) new Object[size];
      System.arraycopy(entries, 0, tmpEntries, 0, size);
      return new ImmutableStack<T>(tmpEntries);
    }
  
    @SuppressWarnings("unchecked")
    public ImmutableStack<T> pushAll(ImmutableStack<T> other) {
      // TODO Auto-generated method stub
      int size = entries.length + other.entries.length;
      T[] tmpEntries = null;
      if (size <= MAX_SIZE) {
        tmpEntries = (T[]) new Object[size];
        System.arraycopy(entries, 0, tmpEntries, 0, entries.length);
        System.arraycopy(other.entries, 0, tmpEntries, entries.length, other.entries.length);
      } else {
        tmpEntries = (T[]) new Object[MAX_SIZE];
        // other has size at most MAX_SIZE
        // must keep all in other
        // top MAX_SIZE - other.size from this
        int numFromThis = MAX_SIZE - other.entries.length;
        System.arraycopy(entries, entries.length - numFromThis, tmpEntries, 0, numFromThis);
        System.arraycopy(other.entries, 0, tmpEntries, numFromThis, other.entries.length);
      }
      return new ImmutableStack<T>(tmpEntries);
    }
  }
  