1 /* 2 * Copyright (C) 2010 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.clearsilver.jsilver.data; 18 19 import java.util.HashSet; 20 import java.util.Iterator; 21 import java.util.LinkedList; 22 import java.util.NoSuchElementException; 23 24 /** 25 * The {@code ResourceStack} represents a LIFO stack of unique objects (resources). 26 * 27 * <p> 28 * An attempt to insert on a stack an object that is already there will fail and result with a 29 * method {@link #push(Object)} returning false. 30 * 31 * <p> 32 * All provided operations ({@link #pop()} and {@link #push(Object)}) are done in average constant 33 * time. 34 * 35 * <p> 36 * This class is iterable 37 */ 38 public class UniqueStack<T> implements Iterable<T> { 39 // Field used for optimization: when only one object was 40 // added we postpone the initialization and use this field. 41 private T firstObject = null; 42 43 // Contains a stack of all stored objects. 44 private LinkedList<T> objectStack = null; 45 // A HashSet allowing quick look-ups on the stack. 46 private HashSet<T> objectsSet = null; 47 48 /** 49 * A wrapper for a {@code Iterator<T>} object that provides immutability. 50 * 51 * @param <T> 52 */ 53 private static class ImmutableIterator<T> implements Iterator<T> { 54 private static final String MODIFICATION_ERROR_MESSAGE = 55 "ResourceStack cannot be modyfied by Iterator.remove()"; 56 57 private final Iterator<T> iterator; 58 ImmutableIterator(Iterator<T> iterator)59 private ImmutableIterator(Iterator<T> iterator) { 60 this.iterator = iterator; 61 } 62 63 @Override hasNext()64 public boolean hasNext() { 65 return iterator.hasNext(); 66 } 67 68 @Override next()69 public T next() { 70 return iterator.next(); 71 } 72 73 @Override remove()74 public void remove() { 75 throw new UnsupportedOperationException(MODIFICATION_ERROR_MESSAGE); 76 } 77 } 78 79 /** 80 * Add an object to a stack. Object will be added only if it is not already on the stack. 81 * 82 * @param object to be added. If it is {@code null} a {@code NullPointerException} will be thrown. 83 * @return true if the object was added successfully 84 */ push(T object)85 public boolean push(T object) { 86 if (object == null) { 87 throw new NullPointerException(); 88 } 89 90 if (objectStack == null) { 91 if (firstObject == null) { 92 firstObject = object; 93 return true; 94 } else { 95 if (firstObject.equals(object)) { 96 return false; 97 } 98 initStackAndSet(); 99 } 100 } else { 101 if (objectsSet.contains(object)) { 102 return false; 103 } 104 } 105 106 objectStack.offerLast(object); 107 objectsSet.add(object); 108 return true; 109 } 110 initStackAndSet()111 private void initStackAndSet() { 112 objectStack = new LinkedList<T>(); 113 objectsSet = new HashSet<T>(); 114 115 objectStack.offerLast(firstObject); 116 objectsSet.add(firstObject); 117 118 // there is no need for using firstObject pointer anymore 119 firstObject = null; 120 } 121 122 /** 123 * Removes last added object from the stack. 124 * 125 * @return last added object 126 * @throws NoSuchElementException - if the stack is empty 127 */ pop()128 public T pop() { 129 T returnedValue = null; 130 131 if (isEmpty()) { 132 throw new NoSuchElementException(); 133 } 134 135 if (objectStack == null) { 136 returnedValue = firstObject; 137 firstObject = null; 138 } else { 139 returnedValue = objectStack.pollLast(); 140 objectsSet.remove(returnedValue); 141 } 142 return returnedValue; 143 } 144 145 /** 146 * Returns {@code true} if this stack contains no elements. 147 * 148 * @return {@code true} if this stack contains no elements. 149 */ isEmpty()150 public boolean isEmpty() { 151 if (firstObject != null) { 152 return false; 153 } 154 return (objectStack == null || objectStack.isEmpty()); 155 } 156 157 @Override iterator()158 public Iterator<T> iterator() { 159 if (objectStack == null) { 160 initStackAndSet(); 161 } 162 return new ImmutableIterator<T>(objectStack.iterator()); 163 } 164 } 165