UniqueStack.java revision 56ed4167b942ec265f9cee70ac4d71d10b3835ce 
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
17package com.google.clearsilver.jsilver.data;
18
19import java.util.HashSet;
20import java.util.Iterator;
21import java.util.LinkedList;
22import 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 */
38public 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
59    private ImmutableIterator(Iterator<T> iterator) {
60      this.iterator = iterator;
61    }
62
63    @Override
64    public boolean hasNext() {
65      return iterator.hasNext();
66    }
67
68    @Override
69    public T next() {
70      return iterator.next();
71    }
72
73    @Override
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   */
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
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   */
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   */
150  public boolean isEmpty() {
151    if (firstObject != null) {
152      return false;
153    }
154    return (objectStack == null || objectStack.isEmpty());
155  }
156
157  @Override
158  public Iterator<T> iterator() {
159    if (objectStack == null) {
160      initStackAndSet();
161    }
162    return new ImmutableIterator<T>(objectStack.iterator());
163  }
164}
165