test for 129566

1 files changed, 591 insertions, 0 deletions

diff --git a/tests/bugs151/pr129566/SkipList.java b/tests/bugs151/pr129566/SkipList.java
new file mode 100644
index 000000000..6fc41d16b
--- /dev/null
+++ b/tests/bugs151/pr129566/SkipList.java
@@ -0,0 +1,591 @@
+
+package common;
+
+import java.lang.reflect.Array;
+import java.util.*;
+
+/**
+ * Class SkipList implements a skip list that uses int primitives for
+ * the element keys. The modification methods defined by <code>Set</code>
+ * are not supported. Instead, methods with keys are required. Note that
+ * the keys have a many to one relationship with the elements (that is,
+ * a range of key values will map to a single element).
+ *
+ * <p><b>Note that this implementation is not synchronized.</b> If multiple
+ * threads access a set concurrently, and at least one of the threads modifies
+ * the set, it <i>must</i> be synchronized externally.  This is typically
+ * accomplished by synchronizing on some object that naturally encapsulates
+ * the set.  If no such object exists, the set should be "wrapped" using the
+ * <code>Collections.synchronizedList</code> method.  This is best done at
+ * creation time, to prevent accidental unsynchronized access to the set:</p>
+ *<pre>
+ *     List l = Collections.synchronizedList(new DisjointSet(...));
+ *</pre>
+ *
+ * <p>The Iterators returned by this class's <tt>iterator</tt> method are
+ * <i>fail-fast</i>: if the set is modified at any time after the iterator is
+ * created, in any way except through the iterator's own <tt>remove</tt>
+ * method, the iterator will throw a <tt>ConcurrentModificationException</tt>.
+ * Thus, in the face of concurrent modification, the iterator fails quickly
+ * and cleanly, rather than risking arbitrary, non-deterministic behavior at
+ * an undetermined time in the future.</p>
+ *
+ * @author Original version: Nathan Fiedler (2001)
+ * @author Several important bugfixes: Holger Hoffstaette 
+ *
+ * @version $Revision$ $Date$
+ */
+
+public class SkipList<T extends Comparable> extends Object implements Set<T>, Iterable<T>
+{
+	/** Optimal probability of most skip lists. */
+	public static final double OPTIMAL_P = 0.25;
+
+	// MaxLevel = L(N) (where N is an upper bound on the number of
+	// elements in a skip list). If p = 0.5, using MaxLevel = 16 is
+	// appropriate for data structures containing up to 2^16 elements.
+	/** Maximum level of any SkipList instance. */
+	protected final int MAX_LEVEL;
+
+	/** Probability value for this skip list. */
+	protected final double P;
+
+	/** Tail of this skip list. */
+	protected final SkipListElement<T> _NIL;
+
+	/** The level of this skip list. */
+	protected int _listLevel;
+
+	/** Header is an element with no data. */
+	protected SkipListElement<T> _listHeader;
+
+	/** Number of elements in this skip list. */
+	protected int _elementCount;
+
+	/** Increments each time the list changes. */
+	protected int _modCount;
+
+	/**
+	 * Constructs an empty SkipList using the default probability
+	 * and maximum element size.
+	 */
+	public SkipList()
+	{
+		this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
+	}
+
+	/**
+	 * Constructs an empty SkipList object using the given probability
+	 * and maximum level.
+	 *
+	 * @param  probability  skip list probability value.
+	 * @param  maxLevel     maximum skip list level.
+	 */
+	public SkipList(double probability, int maxLevel)
+	{
+		P = probability;
+		MAX_LEVEL = maxLevel;
+
+		// Header is the root of our skip list.
+		_listHeader = new SkipListElement<T>(MAX_LEVEL, Integer.MIN_VALUE, null);
+
+		// Allocate NIL with a key greater than any valid key;
+		// all levels of skip lists terminate on NIL.
+		_NIL = new SkipListElement<T>(0, Integer.MAX_VALUE, null);
+
+		this.clear();
+	}
+
+	public SkipList(Collection<? extends T> c)
+	{
+		this();
+		this.addAll(c);
+	}
+
+	public boolean add(T o)
+	{
+		this.insert(o.hashCode(), o);
+		return true;
+	}
+
+	public boolean addAll(Collection<? extends T> c)
+	{
+		boolean added = false;
+
+		if (!c.isEmpty())
+		{
+			for (Iterator<? extends T> iter = c.iterator(); iter.hasNext();)
+			{
+				added |= this.add(iter.next());
+			}
+		}
+
+		return added;
+	}
+
+	public void clear()
+	{
+		// List level is started at one.
+		_listLevel = 1;
+
+		// All forward pointers of list's header point to NIL.
+		for (int i = _listHeader._forward.length - 1; i >= 0; i--)
+		{
+			_listHeader._forward[i] = _NIL;
+		}
+
+		// Reset element count.
+		_elementCount = 0;
+		_modCount++;
+	}
+
+	public boolean contains(Object o)
+	{
+		for (SkipListElement e = _listHeader._forward[0]; e != _NIL; e = e._forward[0])
+		{
+			if ((e._value == o) || e._value != null && e._value.equals(o))
+			{
+				return true;
+			}
+		}
+
+		return false;
+	}
+
+	public boolean containsAll(Collection<?> c)
+	{
+		if ((this.size() < c.size()) || (this.isEmpty() && c.isEmpty()))
+		{
+			return false;
+		}
+
+		for (Iterator<?> iter = c.iterator(); iter.hasNext();)
+		{
+			if (!this.contains(iter.next()))
+			{
+				return false;
+			}
+		}
+
+		return true;
+	}
+
+	/**
+	 * Removes the element with the given key from the list.
+	 *
+	 * @param  searchKey  key of element to remove.
+	 * @return  <code>true</code> if element was found and removed.
+	 */
+	public boolean remove(int searchKey)
+	{
+		SkipListElement[] update = new SkipListElement[MAX_LEVEL];
+		SkipListElement e = _listHeader;
+
+		for (int i = _listLevel; i >= 0; i--)
+		{
+			while (e._forward[i]._key < searchKey)
+			{
+				e = e._forward[i];
+			}
+
+			update[i] = e;
+		}
+
+		e = e._forward[0];
+
+		if (e._key == searchKey)
+		{
+			for (int i = 0; i < _listLevel; i++)
+			{
+				if (update[i]._forward[i] != e)
+				{
+					break;
+				}
+
+				update[i]._forward[i] = e._forward[i];
+			}
+
+			while (_listLevel > 0 && _listHeader._forward[_listLevel] == _NIL)
+			{
+				_listLevel--;
+			}
+
+			_elementCount--;
+			_modCount++;
+			return true;
+		}
+
+		return false;
+	}
+
+	/**
+	 * Inserts the element using the given search key. If an element
+	 * with the same key already exists in the skip lists, its value
+	 * will be replaced with <code>newValue</code>.
+	 *
+	 * @param  searchKey  key for element.
+	 * @param  newValue   new element to insert.
+	 */
+	@SuppressWarnings("unchecked")
+	public void insert(int searchKey, T newValue)
+	{
+		SkipListElement<T>[] update = new SkipListElement[MAX_LEVEL];
+		SkipListElement<T> e = _listHeader;
+
+		for (int i = _listLevel - 1; i >= 0; i--)
+		{
+			while (e._forward[i]._key < searchKey)
+			{
+				e = e._forward[i];
+			}
+
+			update[i] = e;
+		}
+
+		e = e._forward[0];
+
+		if (e._key == searchKey)
+		{
+			e._value = newValue;
+		}
+		else
+		{
+			int lvl = randomLevel();
+			if (lvl > _listLevel)
+			{
+				for (int i = _listLevel; i <= lvl; i++)
+				{
+					update[i] = _listHeader;
+				}
+
+				_listLevel = lvl;
+			}
+
+			e = new SkipListElement<T>(lvl, searchKey, newValue);
+
+			for (int i = 0; i < lvl; i++)
+			{
+				e._forward[i] = update[i]._forward[i];
+				update[i]._forward[i] = e;
+			}
+		}
+
+		_elementCount++;
+		_modCount++;
+	}
+
+	public boolean isEmpty()
+	{
+		return (_elementCount == 0);
+	}
+
+	public Iterator<T> iterator()
+	{
+		return new SkipListIterator<T>();
+	}
+
+	/**
+	 * Return a random level.
+	 *
+	 * @return  level selected randomly.
+	 */
+	protected int randomLevel()
+	{
+		int lvl = 1;
+
+		while (lvl < MAX_LEVEL && Math.random() < P)
+		{
+			lvl++;
+		}
+
+		return lvl;
+	}
+
+	public boolean remove(Object o)
+	{
+		return this.remove(o.hashCode());
+	}
+
+	public boolean removeAll(Collection c)
+	{
+		boolean removed = false;
+
+		for (Iterator iter = c.iterator(); iter.hasNext();)
+		{
+			removed |= this.remove(iter.next());
+		}
+
+		return removed;
+	}
+
+	public boolean retainAll(Collection c)
+	{
+		throw new UnsupportedOperationException();
+	}
+
+	/**
+	 * Searches for the element with the given key.
+	 *
+	 * @param  searchKey  key to look for.
+	 * @return  element if found, null if not found. Note that you may
+	 *          not want to store nulls in this list as it would then
+	 *          be difficult to know the difference.
+	 */
+	public T get(int searchKey)
+	{
+		SkipListElement<T> e = _listHeader;
+
+		for (int i = _listLevel - 1; i >= 0; i--)
+		{
+			while (e._forward[i]._key < searchKey)
+			{
+				e = e._forward[i];
+			}
+		}
+
+		e = e._forward[0];
+
+		if (e._key == searchKey)
+		{
+			return e._value;
+		}
+		else
+		{
+			return null;
+		}
+	}
+
+	/**
+	 * Searches for the element with a key that is the least smaller
+	 * value of the given key.
+	 *
+	 * @param  searchKey  key to look for.
+	 * @return  element if found, null if not found.
+	 */
+	public T searchLeastSmaller(int searchKey)
+	{
+		SkipListElement<T> e = _listHeader;
+
+		for (int i = _listLevel - 1; i >= 0; i--)
+		{
+			while (e._forward[i]._key < searchKey)
+			{
+				e = e._forward[i];
+			}
+		}
+
+		if (e._forward[0]._key == searchKey)
+		{
+			return e._forward[0]._value;
+		}
+		else
+		{
+			return e._value;
+		}
+	}
+
+	/**
+	 * Searches for the element just after the one found using the
+	 * given key (where the key value may be the least smaller of
+	 * the given key).
+	 *
+	 * @param  searchKey  key to look for.
+	 * @return  next element if found, null if not found.
+	 */
+	public T searchNextLarger(int searchKey)
+	{
+		SkipListElement<T> e = _listHeader;
+
+		for (int i = _listLevel - 1; i >= 0; i--)
+		{
+			while (e._forward[i]._key < searchKey)
+			{
+				e = e._forward[i];
+			}
+		}
+
+		SkipListElement<T> t = null;
+
+		if (e._forward[0]._key == searchKey)
+		{
+			t = e._forward[0];
+		}
+		else
+		{
+			t = e;
+		}
+
+		if (t._forward[0] == _NIL)
+		{
+			return null;
+		}
+		else
+		{
+			return t._forward[0]._value;
+		}
+	}
+
+	/**
+	 * Returns the number of elements in this list. If this list contains
+	 * more than <tt>Integer.MAX_VALUE</tt> elements, returns
+	 * <tt>Integer.MAX_VALUE</tt>.
+	 *
+	 * @return the number of elements in this list.
+	 */
+	public int size()
+	{
+		return _elementCount;
+	}
+
+	/**
+	 * Returns an array containing all of the elements in this list in
+	 * proper sequence. Obeys the general contract of the
+	 * <tt>Collection.toArray()</tt> method.
+	 *
+	 * @return an array containing all of the elements in this list in
+	 *         proper sequence.
+	 * @see Arrays#asList(Object[])
+	 */
+	public Object[] toArray()
+	{
+		return toArray(new Object[_elementCount]);
+	}
+
+	/**
+	 * Returns an array containing all of the elements in this list in
+	 * proper sequence; the runtime type of the returned array is that
+	 * of the specified array. Obeys the general contract of the
+	 * <tt>Collection.toArray(Object[])</tt> method.
+	 *
+	 * @param  a  the array into which the elements of this list are to
+	 *            be stored, if it is big enough; otherwise, a new array
+	 *            of the same runtime type is allocated for this purpose.
+	 * @return  an array containing the elements of this list.
+	 * @exception  ArrayStoreException
+	 *             Throw if the runtime type of the specified array is not
+	 *             a supertype of the runtime type of every element in this
+	 *             list.
+	 */
+	@SuppressWarnings({"unchecked","hiding"})
+	public <T> T[] toArray(T[] a)
+	{
+		int size = this.size();
+
+		if (a.length < size)
+		{
+			a = (T[])Array.newInstance(a.getClass().getComponentType(), size);
+		}
+
+		SkipListElement e = _listHeader;
+
+		for (int i = 0; i < _elementCount; i++)
+		{
+			a[i] = (T)e._forward[0]._value;
+			e = e._forward[0];
+		}
+
+		return a;
+	}
+
+	/**
+	 * Class Element represents an element of a skip list.
+	 */
+	protected class SkipListElement<E> extends Object
+	{
+		/** Key of element. */
+		int _key;
+
+		/** Value of element. */
+		E _value;
+
+		/** List of forward pointers. */
+		SkipListElement<E>[] _forward;
+
+		/**
+		 * Constructs an Element for the given key and value.
+		 *
+		 * @param  level  level for this node (number of forward pointers).
+		 * @param  key    key for element.
+		 * @param  value  value for element.
+		 */
+		@SuppressWarnings("unchecked")
+		public SkipListElement(int level, int key, E value)
+		{
+			_key = key;
+			_value = value;
+			_forward = new SkipListElement[level];
+		}
+	}
+
+	/**
+	 * An iterator over a skip list.
+	 */
+	protected class SkipListIterator<E> implements Iterator<T>
+	{
+		/** Index into the skip list. */
+		protected int _index;
+
+		/** The modCount of the list at the time we were instantiated. */
+		protected int _listModCount;
+
+		/** Current element being examined. */
+		protected SkipListElement<T> _elem;
+
+		/**
+		 * Constructs a skip list iterator.
+		 */
+		public SkipListIterator()
+		{
+			_listModCount = SkipList.this._modCount;
+			_elem = _listHeader;
+		}
+
+		/**
+		 * Returns <tt>true</tt> if the iteration has more elements. (In
+		 * other words, returns <tt>true</tt> if <tt>next</tt> would return
+		 * an element rather than throwing an exception.)
+		 *
+		 * @return  <tt>true</tt> if the iterator has more elements.
+		 */
+		public boolean hasNext()
+		{
+			if (this._listModCount != SkipList.this._modCount)
+			{
+				throw new ConcurrentModificationException();
+			}
+
+			return _elem._forward[0] != _NIL;
+		}
+
+		/**
+		 * Returns the next element in the iteration.
+		 *
+		 * @return  the next element in the iteration.
+		 * @exception  NoSuchElementException
+		 *             iteration has no more elements.
+		 */
+		public T next()
+		{
+			if (this._listModCount != SkipList.this._modCount)
+			{
+				throw new ConcurrentModificationException();
+			}
+
+			if (this.hasNext())
+			{
+				_elem = _elem._forward[0];
+				return _elem._value;
+			}
+			else
+			{
+				throw new NoSuchElementException();
+			}
+		}
+
+		public void remove()
+		{
+			throw new UnsupportedOperationException();
+		}
+	}
+
+}