Home | History | Annotate | Download | only in data 
      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 
     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