/*
* Copyright (C) 2010 Google Inc.
*
* 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 com.google.clearsilver.jsilver.data;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
/**
* The {@code ResourceStack} represents a LIFO stack of unique objects (resources).
*
*
* An attempt to insert on a stack an object that is already there will fail and result with a
* method {@link #push(Object)} returning false.
*
*
* All provided operations ({@link #pop()} and {@link #push(Object)}) are done in average constant
* time.
*
*
* This class is iterable
*/
public class UniqueStack implements Iterable {
// Field used for optimization: when only one object was
// added we postpone the initialization and use this field.
private T firstObject = null;
// Contains a stack of all stored objects.
private LinkedList objectStack = null;
// A HashSet allowing quick look-ups on the stack.
private HashSet objectsSet = null;
/**
* A wrapper for a {@code Iterator} object that provides immutability.
*
* @param
*/
private static class ImmutableIterator implements Iterator {
private static final String MODIFICATION_ERROR_MESSAGE =
"ResourceStack cannot be modyfied by Iterator.remove()";
private final Iterator iterator;
private ImmutableIterator(Iterator iterator) {
this.iterator = iterator;
}
@Override
public boolean hasNext() {
return iterator.hasNext();
}
@Override
public T next() {
return iterator.next();
}
@Override
public void remove() {
throw new UnsupportedOperationException(MODIFICATION_ERROR_MESSAGE);
}
}
/**
* Add an object to a stack. Object will be added only if it is not already on the stack.
*
* @param object to be added. If it is {@code null} a {@code NullPointerException} will be thrown.
* @return true if the object was added successfully
*/
public boolean push(T object) {
if (object == null) {
throw new NullPointerException();
}
if (objectStack == null) {
if (firstObject == null) {
firstObject = object;
return true;
} else {
if (firstObject.equals(object)) {
return false;
}
initStackAndSet();
}
} else {
if (objectsSet.contains(object)) {
return false;
}
}
objectStack.offerLast(object);
objectsSet.add(object);
return true;
}
private void initStackAndSet() {
objectStack = new LinkedList();
objectsSet = new HashSet();
objectStack.offerLast(firstObject);
objectsSet.add(firstObject);
// there is no need for using firstObject pointer anymore
firstObject = null;
}
/**
* Removes last added object from the stack.
*
* @return last added object
* @throws NoSuchElementException - if the stack is empty
*/
public T pop() {
T returnedValue = null;
if (isEmpty()) {
throw new NoSuchElementException();
}
if (objectStack == null) {
returnedValue = firstObject;
firstObject = null;
} else {
returnedValue = objectStack.pollLast();
objectsSet.remove(returnedValue);
}
return returnedValue;
}
/**
* Returns {@code true} if this stack contains no elements.
*
* @return {@code true} if this stack contains no elements.
*/
public boolean isEmpty() {
if (firstObject != null) {
return false;
}
return (objectStack == null || objectStack.isEmpty());
}
@Override
public Iterator iterator() {
if (objectStack == null) {
initStackAndSet();
}
return new ImmutableIterator(objectStack.iterator());
}
}