aoqi@0: /*
aoqi@0:  * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
aoqi@0:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
aoqi@0:  *
aoqi@0:  * This code is free software; you can redistribute it and/or modify it
aoqi@0:  * under the terms of the GNU General Public License version 2 only, as
aoqi@0:  * published by the Free Software Foundation.  Oracle designates this
aoqi@0:  * particular file as subject to the "Classpath" exception as provided
aoqi@0:  * by Oracle in the LICENSE file that accompanied this code.
aoqi@0:  *
aoqi@0:  * This code is distributed in the hope that it will be useful, but WITHOUT
aoqi@0:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
aoqi@0:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
aoqi@0:  * version 2 for more details (a copy is included in the LICENSE file that
aoqi@0:  * accompanied this code).
aoqi@0:  *
aoqi@0:  * You should have received a copy of the GNU General Public License version
aoqi@0:  * 2 along with this work; if not, write to the Free Software Foundation,
aoqi@0:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
aoqi@0:  *
aoqi@0:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
aoqi@0:  * or visit www.oracle.com if you need additional information or have any
aoqi@0:  * questions.
aoqi@0:  */
aoqi@0: 
aoqi@0: package com.sun.xml.internal.bind.v2.util;
aoqi@0: 
aoqi@0: import java.util.AbstractList;
aoqi@0: import java.util.Arrays;
aoqi@0: import java.util.List;
aoqi@0: import java.util.Stack;
aoqi@0: 
aoqi@0: /**
aoqi@0:  * {@link Stack}-like data structure that allows the following efficient operations:
aoqi@0:  *
aoqi@0:  * <ol>
aoqi@0:  * <li>Push/pop operation.
aoqi@0:  * <li>Duplicate check. When an object that's already in the stack is pushed,
aoqi@0:  *     this class will tell you so.
aoqi@0:  * </ol>
aoqi@0:  *
aoqi@0:  * <p>
aoqi@0:  * Object equality is their identity equality.
aoqi@0:  *
aoqi@0:  * <p>
aoqi@0:  * This class implements {@link List} for accessing items in the stack,
aoqi@0:  * but {@link List} methods that alter the stack is not supported.
aoqi@0:  *
aoqi@0:  * @author Kohsuke Kawaguchi
aoqi@0:  */
aoqi@0: public final class CollisionCheckStack<E> extends AbstractList<E> {
aoqi@0:     private Object[] data;
aoqi@0:     private int[] next;
aoqi@0:     private int size = 0;
aoqi@0: 
aoqi@0:     private boolean latestPushResult = false;
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * True if the check shall be done by using the object identity.
aoqi@0:      * False if the check shall be done with the equals method.
aoqi@0:      */
aoqi@0:     private boolean useIdentity = true;
aoqi@0: 
aoqi@0:     // for our purpose, there isn't much point in resizing this as we don't expect
aoqi@0:     // the stack to grow that much.
aoqi@0:     private final int[] initialHash;
aoqi@0: 
aoqi@0:     public CollisionCheckStack() {
aoqi@0:         initialHash = new int[17];
aoqi@0:         data = new Object[16];
aoqi@0:         next = new int[16];
aoqi@0:     }
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * Set to false to use {@link Object#equals(Object)} to detect cycles.
aoqi@0:      * This method can be only used when the stack is empty.
aoqi@0:      */
aoqi@0:     public void setUseIdentity(boolean useIdentity) {
aoqi@0:         this.useIdentity = useIdentity;
aoqi@0:     }
aoqi@0: 
aoqi@0:     public boolean getUseIdentity() {
aoqi@0:         return useIdentity;
aoqi@0:     }
aoqi@0: 
aoqi@0:     public boolean getLatestPushResult() {
aoqi@0:         return latestPushResult;
aoqi@0:     }
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * Pushes a new object to the stack.
aoqi@0:      *
aoqi@0:      * @return
aoqi@0:      *      true if this object has already been pushed
aoqi@0:      */
aoqi@0:     public boolean push(E o) {
aoqi@0:         if(data.length==size)
aoqi@0:             expandCapacity();
aoqi@0: 
aoqi@0:         data[size] = o;
aoqi@0:         int hash = hash(o);
aoqi@0:         boolean r = findDuplicate(o, hash);
aoqi@0:         next[size] = initialHash[hash];
aoqi@0:         initialHash[hash] = size+1;
aoqi@0:         size++;
aoqi@0:         this.latestPushResult = r;
aoqi@0:         return latestPushResult;
aoqi@0:     }
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * Pushes a new object to the stack without making it participate
aoqi@0:      * with the collision check.
aoqi@0:      */
aoqi@0:     public void pushNocheck(E o) {
aoqi@0:         if(data.length==size)
aoqi@0:             expandCapacity();
aoqi@0:         data[size] = o;
aoqi@0:         next[size] = -1;
aoqi@0:         size++;
aoqi@0:     }
aoqi@0: 
aoqi@0:     public boolean findDuplicate(E o) {
aoqi@0:         int hash = hash(o);
aoqi@0:         return findDuplicate(o, hash);
aoqi@0:     }
aoqi@0: 
aoqi@0:     @Override
aoqi@0:     public E get(int index) {
aoqi@0:         return (E)data[index];
aoqi@0:     }
aoqi@0: 
aoqi@0:     @Override
aoqi@0:     public int size() {
aoqi@0:         return size;
aoqi@0:     }
aoqi@0: 
aoqi@0:     private int hash(Object o) {
aoqi@0:         return ((useIdentity?System.identityHashCode(o):o.hashCode())&0x7FFFFFFF) % initialHash.length;
aoqi@0:     }
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * Pops an object from the stack
aoqi@0:      */
aoqi@0:     public E pop() {
aoqi@0:         size--;
aoqi@0:         Object o = data[size];
aoqi@0:         data[size] = null;  // keeping references too long == memory leak
aoqi@0:         int n = next[size];
aoqi@0:         if(n<0) {
aoqi@0:             // pushed by nocheck. no need to update hash
aoqi@0:         } else {
aoqi@0:             int hash = hash(o);
aoqi@0:             assert initialHash[hash]==size+1;
aoqi@0:             initialHash[hash] = n;
aoqi@0:         }
aoqi@0:         return (E)o;
aoqi@0:     }
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * Returns the top of the stack.
aoqi@0:      */
aoqi@0:     public E peek() {
aoqi@0:         return (E)data[size-1];
aoqi@0:     }
aoqi@0: 
aoqi@0:     private boolean findDuplicate(E o, int hash) {
aoqi@0:         int p = initialHash[hash];
aoqi@0:         while(p!=0) {
aoqi@0:             p--;
aoqi@0:             Object existing = data[p];
aoqi@0:             if (useIdentity) {
aoqi@0:                 if(existing==o)     return true;
aoqi@0:             } else {
aoqi@0:                 if (o.equals(existing)) return true;
aoqi@0:             }
aoqi@0:             p = next[p];
aoqi@0:         }
aoqi@0:         return false;
aoqi@0:     }
aoqi@0: 
aoqi@0:     private void expandCapacity() {
aoqi@0:         int oldSize = data.length;
aoqi@0:         int newSize = oldSize * 2;
aoqi@0:         Object[] d = new Object[newSize];
aoqi@0:         int[] n = new int[newSize];
aoqi@0: 
aoqi@0:         System.arraycopy(data,0,d,0,oldSize);
aoqi@0:         System.arraycopy(next,0,n,0,oldSize);
aoqi@0: 
aoqi@0:         data = d;
aoqi@0:         next = n;
aoqi@0:     }
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * Clears all the contents in the stack.
aoqi@0:      */
aoqi@0:     public void reset() {
aoqi@0:         if(size>0) {
aoqi@0:             size = 0;
aoqi@0:             Arrays.fill(initialHash,0);
aoqi@0:         }
aoqi@0:     }
aoqi@0: 
aoqi@0:     /**
aoqi@0:      * String that represents the cycle.
aoqi@0:      */
aoqi@0:     public String getCycleString() {
aoqi@0:         StringBuilder sb = new StringBuilder();
aoqi@0:         int i=size()-1;
aoqi@0:         E obj = get(i);
aoqi@0:         sb.append(obj);
aoqi@0:         Object x;
aoqi@0:         do {
aoqi@0:             sb.append(" -> ");
aoqi@0:             x = get(--i);
aoqi@0:             sb.append(x);
aoqi@0:         } while(obj!=x);
aoqi@0: 
aoqi@0:         return sb.toString();
aoqi@0:     }
aoqi@0: }