// Path: src/main/java/com/queues/Queue.java
// public class Queue<Item> implements Iterable<Item> {
// 
// 	private Node first, last;
// 
// 	/**
// 	 * creates a new empty 
// 	 * Queue object.
// 	 */
// 	public Queue() {
// 		first = null;
// 		last = null;
// 	}
// 	
// 	/**
// 	 * inserts the given item into the queue.
// 	 * @param item Item to be stored.
// 	 */
// 	public void enqueue(Item item) {
// 		Node oldLast = last;
// 		last = new Node();
// 		last.item = item;
// 		last.next = null;
// 		if (isEmpty()) 
// 			first = last;
// 		else     	   
// 			oldLast.next = last;
// 	}
// 	
// 	/**
// 	 * removes the least recent item from the queue.
// 	 * @return an item from the queue.
// 	 */
// 	public Item dequeue() {
// 		if (isEmpty())
// 			throw new NoSuchElementException("Queue is empty");
// 		Item item = first.item;
// 		first = first.next;
// 		return item;
// 	}
// 	
// 	/**
// 	 * checks to see if queue is empty.
// 	 * @return <code>true</code> if queue is empty, <code>false</code> otherwise.
// 	 */
// 	public boolean isEmpty() {
// 		return first == null;
// 	}
// 
// 	/**
// 	 * returns an iterator over the elements of the queue.
// 	 */
// 	public Iterator<Item> iterator() {
// 		return new QueueIterator();
// 	}
// 	
// 	
// 	private class Node {
// 		Item item;
// 		Node next;
// 	}
// 	
// 	private class QueueIterator implements Iterator<Item> {
// 
// 		Node current = first;
// 		public boolean hasNext() {
// 			return current != null;
// 		}
// 
// 		public Item next() {
// 			Item item = current.item;
// 			current = current.next;
// 			return item;
// 		}
// 
// 		public void remove() {
// 			throw new UnsupportedOperationException("Operation is not supported");
// 		}
// 		
// 	}
// }


import com.queues.Queue;
/* 
 *  File: ST.java
 *  Author: Ashish Chopra
 *  Date: 3 June, 2015
 *  ---------------------------------------------------
 *  ST stands for Symbol table. This is an implementation
 *  of a symbol table for ordered data. When the keys are stored
 *  in an order. The search and insert operations can be performed
 *  in logarithmic time.
 *  
 *  Due to orderness in keys, various other operations like min, max, range,
 *  rank, select floor, ceiling etc are supported.
 *  
 */
package com.tables;



public class ST<Key extends Comparable<Key>, Value> {
	private Key[] keys;
	private Value[] vals;
	private int N;
	private int capacity = 2;
	
	/**
	 * creates a new symbol table object
	 */
	@SuppressWarnings("unchecked")
	public ST() {
// Path: src/main/java/com/queues/Queue.java
// public class Queue<Item> implements Iterable<Item> {
// 
// 	private Node first, last;
// 
// 	/**
// 	 * creates a new empty 
// 	 * Queue object.
// 	 */
// 	public Queue() {
// 		first = null;
// 		last = null;
// 	}
// 	
// 	/**
// 	 * inserts the given item into the queue.
// 	 * @param item Item to be stored.
// 	 */
// 	public void enqueue(Item item) {
// 		Node oldLast = last;
// 		last = new Node();
// 		last.item = item;
// 		last.next = null;
// 		if (isEmpty()) 
// 			first = last;
// 		else     	   
// 			oldLast.next = last;
// 	}
// 	
// 	/**
// 	 * removes the least recent item from the queue.
// 	 * @return an item from the queue.
// 	 */
// 	public Item dequeue() {
// 		if (isEmpty())
// 			throw new NoSuchElementException("Queue is empty");
// 		Item item = first.item;
// 		first = first.next;
// 		return item;
// 	}
// 	
// 	/**
// 	 * checks to see if queue is empty.
// 	 * @return <code>true</code> if queue is empty, <code>false</code> otherwise.
// 	 */
// 	public boolean isEmpty() {
// 		return first == null;
// 	}
// 
// 	/**
// 	 * returns an iterator over the elements of the queue.
// 	 */
// 	public Iterator<Item> iterator() {
// 		return new QueueIterator();
// 	}
// 	
// 	
// 	private class Node {
// 		Item item;
// 		Node next;
// 	}
// 	
// 	private class QueueIterator implements Iterator<Item> {
// 
// 		Node current = first;
// 		public boolean hasNext() {
// 			return current != null;
// 		}
// 
// 		public Item next() {
// 			Item item = current.item;
// 			current = current.next;
// 			return item;
// 		}
// 
// 		public void remove() {
// 			throw new UnsupportedOperationException("Operation is not supported");
// 		}
// 		
// 	}
// }


// Path: src/main/java/com/tables/ST.java
import com.queues.Queue;

/* 
 *  File: ST.java
 *  Author: Ashish Chopra
 *  Date: 3 June, 2015
 *  ---------------------------------------------------
 *  ST stands for Symbol table. This is an implementation
 *  of a symbol table for ordered data. When the keys are stored
 *  in an order. The search and insert operations can be performed
 *  in logarithmic time.
 *  
 *  Due to orderness in keys, various other operations like min, max, range,
 *  rank, select floor, ceiling etc are supported.
 *  
 */
package com.tables;



public class ST<Key extends Comparable<Key>, Value> {
	private Key[] keys;
	private Value[] vals;
	private int N;
	private int capacity = 2;
	
	/**
	 * creates a new symbol table object
	 */
	@SuppressWarnings("unchecked")
	public ST() {
		this.keys = (Key[]) new Comparable[capacity];