Attachment 240042 Details for Bug 428372 – Buggy source file

Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Buggy source file

RandomizedQueue.java (text/x-java), 4.07 KB, created by Jay Kumar

on 2014-02-17 13:42:47 EST

(hide)

Description:

Filename:

MIME Type:

Creator: Jay Kumar

Created: 2014-02-17 13:42:47 EST

Size: 4.07 KB

patch

obsolete

>import java.util.Iterator;
>import java.util.NoSuchElementException;
>
>public class RandomizedQueue<Item> implements Iterable<Item> {
>
>	private Item[] resizingarray;  // a resizing array for the implementation
>	private boolean[] itempresent; // is an item present at the index?
>	private int currarraylength;   // the length of the implementation arrays
>	private int N;                 // number of items
>	
>	/*
>	 * construct an empty randomized queue
>	 */
>	public RandomizedQueue()
>	{
>		resizingarray = (Item[]) new Object[1];
>		resizingarray[0] = null;
>		itempresent = new boolean[1];
>		itempresent[0] = false;
>		currarraylength = 1;
>		N = 0;
>	}
>	
>	/*
>	 * resize the resizingarray and the itempresent array
>	 */
>	private void resize(int max)
>	{
>		Item[] temp = (Item[]) new Object[max];
>		boolean[] booltemp = new boolean[max];
>		int newindex = 0;
>		for (int i = 0; i < currarraylength; i++) {
>			if (itempresent[i]) {
>				booltemp[newindex] = true;
>				temp[newindex] = resizingarray[i];
>				newindex++;
>			}
>		}
>		assert (newindex == N);
>		for (int j = newindex; j < max; j++) {
>			booltemp[j] = false;
>			temp[j] = null;
>		}
>		resizingarray = temp;
>		itempresent = booltemp;
>		currarraylength = max;
>	}
>	
>	/*
>	 * is the queue empty?
>	 */
>	public boolean isEmpty()
>	{
>		return N == 0;
>	}
>	
>	/*
>	 * return the number of items on the queue
>	 */
>	public int size()
>	{
>		return N;
>	}
>	
>	/*
>	 * add the item
>	 */
>	public void enqueue(Item item)
>	{
>		if (item == null)  throw new NullPointerException();
>		if (N == currarraylength)
>			resize(2 * currarraylength);
>		resizingarray[N] = item;
>		itempresent[N] = true;
>		N++;
>	}
>	
>	/*
>	 * delete and return a random item
>	 */
>	public Item dequeue()
>	{
>		if (isEmpty())  throw new NoSuchElementException();
>		
>		Item retval = null;
>		int somerandno = StdRandom.uniform(N);
>		
>		for (int i = 0; i < currarraylength; i++) {
>			if (itempresent[i]) {
>				if (somerandno == 0) {
>					retval = resizingarray[i];
>					itempresent[i] = false;
>					resizingarray[i] = null;
>					break;
>				} else {
>					somerandno--;
>				}
>			}
>		}
>		
>		N--;
>		if ((N > 0) && (N == currarraylength / 4))
>			resize(currarraylength / 2);
>		
>		assert (retval != null);
>		return retval;
>	}
>	
>	/*
>	 * return (but do not delete) a random item
>	 */
>	public Item sample()
>	{
>		if (isEmpty())  throw new NoSuchElementException();
>		
>		Item retval = null;
>		int somerandno = StdRandom.uniform(N);
>		
>		for (int i = 0; i < currarraylength; i++) {
>			if (itempresent[i]) {
>				if (somerandno == 0) {
>					retval = resizingarray[i];
>					break;
>				} else {
>					somerandno--;
>				}
>			}
>		}
>		
>		assert (retval != null);
>		return retval;		
>	}
>
>	/*
>	 * the iterator for the randomized queue
>	 */
>	private class RqueueIterator implements Iterator<Item>
>	{
>		private Item[] joinedarray;
>		private int ind;
>		
>		public RqueueIterator()
>		{
>			joinedarray = (Item[]) new Object[N];
>			int newindex = 0;
>			for (int i = 0; i < currarraylength; i++) {
>				if (itempresent[i]) {
>					joinedarray[newindex] = resizingarray[i]; 
>					newindex++;
>				}
>			}
>			assert (newindex == N);
>			StdRandom.shuffle(joinedarray);
>			ind = 0;
>		}
>		
>		public void remove() { throw new UnsupportedOperationException(); }
>		
>		public boolean hasNext() { return ind < N; }
>		
>		public Item next()
>		{
>			if (!hasNext())  throw new NoSuchElementException();
>			return joinedarray[ind++];
>		}
>	}
>	
>	/*
>	 * (non-Javadoc)
>	 * @see java.lang.Iterable#iterator()
>	 * return an independent iterator over items in random order
>	 */
>	public Iterator<Item> iterator()
>	{
>		return new RqueueIterator();
>	}
>	
>	/*
>	 * unit testing
>	 */
>	public static void main(String[] args)
>	{
>		RandomizedQueue<Integer> rq = new RandomizedQueue<>();
>		for (int i = 1; i < 61; i++) {
>			rq.enqueue(i);
>		}
>		for (int i = 21; i < 41; i++) {
>			System.out.println(rq.dequeue());
>		}
>		System.out.println("-------");
>		for (int i = 701; i < 771; i++) {
>			rq.enqueue(i);
>		}
>		int count = 1;
>		for (int i : rq) {
>			System.out.println(count++ + " : " + i);
>		}
>		System.out.println("-------");
>		rq.enqueue(5);
>		rq.enqueue(7);
>		System.out.println(rq.dequeue());
>		for (int i : rq) {
>			System.out.println(i);
>		}
>	}
>}
>

Actions: View

Attachments on bug 428372: 240041 | 240042 | 240043 | 240044 | 240054