SimpleStackNullSupport.java
/*
* Copyright (c) 2001-2017, Zoltan Farkas All Rights Reserved.
*
* This library 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 library 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 Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
* Additionally licensed with:
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.spf4j.ds;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Objects;
import javax.annotation.ParametersAreNullableByDefault;
import org.spf4j.base.Arrays;
/**
* A simple stack implementation that supports null elements.
* @author Zoltan Farkas
* @param <T>
*/
@ParametersAreNullableByDefault
@SuppressWarnings("checkstyle:VisibilityModifier")
public class SimpleStackNullSupport<T>
implements List<T> {
/**
* stack default initial size
*/
private static final int DEFAULT_SIZE = 32;
/**
* the stack storage
*/
T[] elems;
/**
* the top element position
*/
int top;
/**
* construct a stack with specified size
*/
public SimpleStackNullSupport(final int size) {
elems = (T[]) new Object[size];
top = 0;
}
/**
* Construct a stack, default size is 20
*/
public SimpleStackNullSupport() {
this(DEFAULT_SIZE);
}
/**
* check if stack is empty
*
* @return boolean
*/
@Override
public final boolean isEmpty() {
return top == 0;
}
/**
* push object into stack
*
* @param o Object
*/
public final void push(final T o) {
int t = top + 1;
ensureCapacity(t);
elems[top] = o;
top = t;
}
/**
* pushes a null on top of stack.
* cane be overridden to prohibit operation.
*/
public void pushNull() {
int t = top + 1;
ensureCapacity(t);
top = t;
}
public final int pushAndGetIdx(final T o) {
int t = top;
top++;
ensureCapacity(top);
elems[t] = o;
return t;
}
final void ensureCapacity(final int minCapacity) {
int oldCapacity = elems.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
// minCapacity is usually close to size, so this is a win:
elems = java.util.Arrays.copyOf(elems, newCapacity);
}
}
/**
* Push more objects into the stack
*
* @param args
*/
public final void pushAll(final T... args) {
if (args.length == 0) {
return;
}
int newTop = top + args.length;
ensureCapacity(newTop);
System.arraycopy(args, 0, elems, top, args.length);
top = newTop;
}
/**
* pops object out of stack
*
* @return Object
*/
public final T pop() {
final T o = elems[--top];
elems[top] = null;
return o;
}
public final void remove() {
elems[--top] = null;
}
public final T[] pop(final int n) {
int ot = top;
top -= n;
T[] result = (T[]) new Object[n];
for (int i = top, j = 0; i < ot; i++, j++) {
result[j] = elems[i];
elems[i] = null;
}
return result;
}
public final void popTo(final T[] to, final int n) {
int ot = top;
top -= n;
for (int i = top, j = 0; i < ot; i++, j++) {
to[j] = elems[i];
elems[i] = null;
}
}
public final void removeFromTop(final int n) {
int ot = top;
top -= n;
for (int i = top; i < ot; i++) {
elems[i] = null;
}
}
public final T[] popUntil(final T until) {
int i = top - 1;
while (elems[i] != until) {
i--;
}
T[] result = java.util.Arrays.copyOfRange(elems, i + 1, top);
java.util.Arrays.fill(elems, i, top, null);
top = i;
return result;
}
public final boolean hasElements() {
return top > 0;
}
/**
* take a look at the top of stack.
* Throws exception if there is no element.
*
* @return Object
*/
public T peek() {
return elems[top - 1];
}
public final T peekFromTop(final int n) {
return elems[top - 1 - n];
}
public final void replaceFromTop(final int n, final T value) {
elems[top - 1 - n] = value;
}
public final T[] peek(final int n) {
return java.util.Arrays.copyOfRange(elems, top - n, top);
}
public final T[] peekUntil(final T until) {
int i = top - 1;
while (elems[i] != until) {
i--;
}
return java.util.Arrays.copyOfRange(elems, i + 1, top);
}
public final T peekElemAfter(final T until) {
int i = top - 1;
while (elems[i] != until) {
i--;
}
return elems[i - 1];
}
/**
* Clear the stack - also makes sure the stack objects are not referenced anymore
*/
@Override
public final void clear() {
for (int i = 0; i < top; i++) {
elems[i] = null;
}
top = 0;
}
/**
* get the curent stack pos relative to base
*
* @return
*/
public final int getPtr() {
return top;
}
/**
* get element from stack at index relative to base
*
* @param ptr
* @return
*/
public final T getFromPtr(final int ptr) {
if (ptr < 0 || ptr >= top) {
throw new IndexOutOfBoundsException(
"Trying to get from invalid index: " + ptr + " from: " + this);
}
return elems[ptr];
}
/**
* returns a character separated string with the stack elements
*
* @param separator
* @return String
*/
public final String toString(final char separator) {
if (top == 0) {
return "";
}
final StringBuilder result = new StringBuilder(32);
result.append(elems[0]);
for (int i = 1; i < top; i++) {
result.append(separator);
result.append(elems[i]);
}
return result.toString();
}
/**
* to string representation. can be subclassed.
*/
@Override
public String toString() {
return toString('.');
}
@Override
public final int size() {
return top;
}
/**
* can be overwritten to optimize.
*/
@Override
public boolean contains(final Object o) {
for (int i = 0; i < top; i++) {
if (Objects.equals(elems[i], o)) {
return true;
}
}
return false;
}
/**
* Not implemented, can be overwritten.
*/
@Override
public Iterator<T> iterator() {
throw new UnsupportedOperationException();
}
@Override
public final Object[] toArray() {
return java.util.Arrays.copyOf(elems, top);
}
/**
* Not implemented, can be overwritten.
*/
@Override
public <T> T[] toArray(final T[] a) {
throw new UnsupportedOperationException();
}
@Override
public final boolean add(final T e) {
push(e);
return true;
}
/**
* Can be overwritten for better implementation.
* @param o element to remove.
* @return
*/
@Override
public boolean remove(final Object o) {
if (o == null) {
for (int i = 0; i < top; i++) {
if (elems[i] == null) {
fastRemove(i);
return true;
}
}
} else {
for (int i = 0; i < top; i++) {
if (o.equals(elems[i])) {
fastRemove(i);
return true;
}
}
}
return false;
}
/**
* Not implemented, can be overwritten.
*/
@Override
public boolean containsAll(final Collection<?> c) {
throw new UnsupportedOperationException();
}
/**
* Not implemented, can be overwritten.
*/
@Override
public boolean addAll(final Collection<? extends T> c) {
throw new UnsupportedOperationException();
}
/**
* Not implemented, can be overwritten.
*/
@Override
public boolean removeAll(final Collection<?> c) {
throw new UnsupportedOperationException();
}
/**
* Not implemented, can be overwritten.
*/
@Override
public boolean retainAll(final Collection<?> c) {
throw new UnsupportedOperationException();
}
@Override
public final boolean equals(final Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final SimpleStackNullSupport<T> other = (SimpleStackNullSupport<T>) obj;
if (this.top != other.top) {
return false;
}
return Arrays.deepEquals(this.elems, other.elems, 0, top);
}
/**
* can be overwritten for better implementation.
*/
@Override
public int hashCode() {
int hashCode = 7;
for (int i = 0; i < top; i++) {
Object obj = elems[i];
hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
}
return hashCode;
}
/**
* Not implemented, can be overwritten.
*/
@Override
public boolean addAll(final int index, final Collection<? extends T> c) {
throw new UnsupportedOperationException();
}
@Override
public final T get(final int index) {
return elems[index];
}
@Override
public final T set(final int index, final T element) {
ensureCapacity(index);
T result = elems[index];
elems[index] = element;
return result;
}
/**
* Not implemented, can be overwritten.
*/
@Override
public void add(final int index, final T element) {
throw new UnsupportedOperationException();
}
@Override
public final T remove(final int index) {
if (index >= top && index < 0) {
throw new IndexOutOfBoundsException("Invalid index " + index + ", current size " + top);
}
T result = elems[index];
int next = index + 1;
int numMoved = top - next;
if (numMoved > 0) {
System.arraycopy(elems, next, elems, index, numMoved);
}
elems[--top] = null;
return result;
}
final void fastRemove(final int index) {
int next = index + 1;
int numMoved = top - next;
if (numMoved > 0) {
System.arraycopy(elems, next, elems, index, numMoved);
}
elems[--top] = null;
}
/**
* Not implemented, can be overwritten.
*/
@Override
public int indexOf(final Object o) {
throw new UnsupportedOperationException();
}
/**
* Not implemented, can be overwritten.
*/
@Override
public int lastIndexOf(final Object o) {
throw new UnsupportedOperationException();
}
/**
* Not implemented, can be overwritten.
*/
@Override
public ListIterator<T> listIterator() {
throw new UnsupportedOperationException();
}
/**
* Not implemented, can be overwritten.
*/
@Override
public ListIterator<T> listIterator(final int index) {
throw new UnsupportedOperationException();
}
/**
* Not implemented, can be overwritten.
*/
@Override
public List<T> subList(final int fromIndex, final int toIndex) {
throw new UnsupportedOperationException();
}
}