RedBlackBST

From EOJ Wiki
Jump to navigation Jump to search

代码很长,但是封装的很好,肯定不会错。 有一堆又一堆的异常处理。 效率远不如C++的红黑树。

import java.util.NoSuchElementException;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.Locale;
import java.util.Scanner;
import java.util.regex.Pattern;
import java.util.Iterator;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;


public class RedBlackBST<Key extends Comparable<Key>, Value> {

	private static final boolean RED = true;
	private static final boolean BLACK = false;

	private Node root; // root of the BST

	// BST helper node data type
	private class Node {
		private Key key; // key
		private Value val; // associated data
		private Node left, right; // links to left and right subtrees
		private boolean color; // color of parent link
		private int size; // subtree count

		public Node(Key key, Value val, boolean color, int size) {
			this.key = key;
			this.val = val;
			this.color = color;
			this.size = size;
		}
	}

	/**
	 * Initializes an empty symbol table.
	 */
	public RedBlackBST() {
	}

	/***************************************************************************
	 * Node helper methods.
	 ***************************************************************************/
	// is node x red; false if x is null ?
	private boolean isRed(Node x) {
		if (x == null)
			return false;
		return x.color == RED;
	}

	// number of node in subtree rooted at x; 0 if x is null
	private int size(Node x) {
		if (x == null)
			return 0;
		return x.size;
	}

	/**
	 * Returns the number of key-value pairs in this symbol table.
	 * 
	 * @return the number of key-value pairs in this symbol table
	 */
	public int size() {
		return size(root);
	}

	/**
	 * Is this symbol table empty?
	 * 
	 * @return {@code true} if this symbol table is empty and {@code false}
	 *         otherwise
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/***************************************************************************
	 * Standard BST search.
	 ***************************************************************************/

	/**
	 * Returns the value associated with the given key.
	 * 
	 * @param key
	 *            the key
	 * @return the value associated with the given key if the key is in the symbol
	 *         table and {@code null} if the key is not in the symbol table
	 * @throws IllegalArgumentException
	 *             if {@code key} is {@code null}
	 */
	public Value get(Key key) {
		if (key == null)
			throw new IllegalArgumentException("argument to get() is null");
		return get(root, key);
	}

	// value associated with the given key in subtree rooted at x; null if no such
	// key
	private Value get(Node x, Key key) {
		while (x != null) {
			int cmp = key.compareTo(x.key);
			if (cmp < 0)
				x = x.left;
			else if (cmp > 0)
				x = x.right;
			else
				return x.val;
		}
		return null;
	}

	/**
	 * Does this symbol table contain the given key?
	 * 
	 * @param key
	 *            the key
	 * @return {@code true} if this symbol table contains {@code key} and
	 *         {@code false} otherwise
	 * @throws IllegalArgumentException
	 *             if {@code key} is {@code null}
	 */
	public boolean contains(Key key) {
		return get(key) != null;
	}

	/***************************************************************************
	 * Red-black tree insertion.
	 ***************************************************************************/

	/**
	 * Inserts the specified key-value pair into the symbol table, overwriting the
	 * old value with the new value if the symbol table already contains the
	 * specified key. Deletes the specified key (and its associated value) from this
	 * symbol table if the specified value is {@code null}.
	 *
	 * @param key
	 *            the key
	 * @param val
	 *            the value
	 * @throws IllegalArgumentException
	 *             if {@code key} is {@code null}
	 */
	public void put(Key key, Value val) {
		if (key == null)
			throw new IllegalArgumentException("first argument to put() is null");
		if (val == null) {
			delete(key);
			return;
		}

		root = put(root, key, val);
		root.color = BLACK;
		// assert check();
	}

	// insert the key-value pair in the subtree rooted at h
	private Node put(Node h, Key key, Value val) {
		if (h == null)
			return new Node(key, val, RED, 1);

		int cmp = key.compareTo(h.key);
		if (cmp < 0)
			h.left = put(h.left, key, val);
		else if (cmp > 0)
			h.right = put(h.right, key, val);
		else
			h.val = val;

		// fix-up any right-leaning links
		if (isRed(h.right) && !isRed(h.left))
			h = rotateLeft(h);
		if (isRed(h.left) && isRed(h.left.left))
			h = rotateRight(h);
		if (isRed(h.left) && isRed(h.right))
			flipColors(h);
		h.size = size(h.left) + size(h.right) + 1;

		return h;
	}

	/***************************************************************************
	 * Red-black tree deletion.
	 ***************************************************************************/

	/**
	 * Removes the smallest key and associated value from the symbol table.
	 * 
	 * @throws NoSuchElementException
	 *             if the symbol table is empty
	 */
	public void deleteMin() {
		if (isEmpty())
			throw new NoSuchElementException("BST underflow");

		// if both children of root are black, set root to red
		if (!isRed(root.left) && !isRed(root.right))
			root.color = RED;

		root = deleteMin(root);
		if (!isEmpty())
			root.color = BLACK;
		// assert check();
	}

	// delete the key-value pair with the minimum key rooted at h
	private Node deleteMin(Node h) {
		if (h.left == null)
			return null;

		if (!isRed(h.left) && !isRed(h.left.left))
			h = moveRedLeft(h);

		h.left = deleteMin(h.left);
		return balance(h);
	}

	/**
	 * Removes the largest key and associated value from the symbol table.
	 * 
	 * @throws NoSuchElementException
	 *             if the symbol table is empty
	 */
	public void deleteMax() {
		if (isEmpty())
			throw new NoSuchElementException("BST underflow");

		// if both children of root are black, set root to red
		if (!isRed(root.left) && !isRed(root.right))
			root.color = RED;

		root = deleteMax(root);
		if (!isEmpty())
			root.color = BLACK;
		// assert check();
	}

	// delete the key-value pair with the maximum key rooted at h
	private Node deleteMax(Node h) {
		if (isRed(h.left))
			h = rotateRight(h);

		if (h.right == null)
			return null;

		if (!isRed(h.right) && !isRed(h.right.left))
			h = moveRedRight(h);

		h.right = deleteMax(h.right);

		return balance(h);
	}

	/**
	 * Removes the specified key and its associated value from this symbol table (if
	 * the key is in this symbol table).
	 *
	 * @param key
	 *            the key
	 * @throws IllegalArgumentException
	 *             if {@code key} is {@code null}
	 */
	public void delete(Key key) {
		if (key == null)
			throw new IllegalArgumentException("argument to delete() is null");
		if (!contains(key))
			return;

		// if both children of root are black, set root to red
		if (!isRed(root.left) && !isRed(root.right))
			root.color = RED;

		root = delete(root, key);
		if (!isEmpty())
			root.color = BLACK;
		// assert check();
	}

	// delete the key-value pair with the given key rooted at h
	private Node delete(Node h, Key key) {
		// assert get(h, key) != null;

		if (key.compareTo(h.key) < 0) {
			if (!isRed(h.left) && !isRed(h.left.left))
				h = moveRedLeft(h);
			h.left = delete(h.left, key);
		} else {
			if (isRed(h.left))
				h = rotateRight(h);
			if (key.compareTo(h.key) == 0 && (h.right == null))
				return null;
			if (!isRed(h.right) && !isRed(h.right.left))
				h = moveRedRight(h);
			if (key.compareTo(h.key) == 0) {
				Node x = min(h.right);
				h.key = x.key;
				h.val = x.val;
				// h.val = get(h.right, min(h.right).key);
				// h.key = min(h.right).key;
				h.right = deleteMin(h.right);
			} else
				h.right = delete(h.right, key);
		}
		return balance(h);
	}

	/***************************************************************************
	 * Red-black tree helper functions.
	 ***************************************************************************/

	// make a left-leaning link lean to the right
	private Node rotateRight(Node h) {
		// assert (h != null) && isRed(h.left);
		Node x = h.left;
		h.left = x.right;
		x.right = h;
		x.color = x.right.color;
		x.right.color = RED;
		x.size = h.size;
		h.size = size(h.left) + size(h.right) + 1;
		return x;
	}

	// make a right-leaning link lean to the left
	private Node rotateLeft(Node h) {
		// assert (h != null) && isRed(h.right);
		Node x = h.right;
		h.right = x.left;
		x.left = h;
		x.color = x.left.color;
		x.left.color = RED;
		x.size = h.size;
		h.size = size(h.left) + size(h.right) + 1;
		return x;
	}

	// flip the colors of a node and its two children
	private void flipColors(Node h) {
		// h must have opposite color of its two children
		// assert (h != null) && (h.left != null) && (h.right != null);
		// assert (!isRed(h) && isRed(h.left) && isRed(h.right))
		// || (isRed(h) && !isRed(h.left) && !isRed(h.right));
		h.color = !h.color;
		h.left.color = !h.left.color;
		h.right.color = !h.right.color;
	}

	// Assuming that h is red and both h.left and h.left.left
	// are black, make h.left or one of its children red.
	private Node moveRedLeft(Node h) {
		// assert (h != null);
		// assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

		flipColors(h);
		if (isRed(h.right.left)) {
			h.right = rotateRight(h.right);
			h = rotateLeft(h);
			flipColors(h);
		}
		return h;
	}

	// Assuming that h is red and both h.right and h.right.left
	// are black, make h.right or one of its children red.
	private Node moveRedRight(Node h) {
		// assert (h != null);
		// assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
		flipColors(h);
		if (isRed(h.left.left)) {
			h = rotateRight(h);
			flipColors(h);
		}
		return h;
	}

	// restore red-black tree invariant
	private Node balance(Node h) {
		// assert (h != null);

		if (isRed(h.right))
			h = rotateLeft(h);
		if (isRed(h.left) && isRed(h.left.left))
			h = rotateRight(h);
		if (isRed(h.left) && isRed(h.right))
			flipColors(h);

		h.size = size(h.left) + size(h.right) + 1;
		return h;
	}

	/***************************************************************************
	 * Utility functions.
	 ***************************************************************************/

	/**
	 * Returns the height of the BST (for debugging).
	 * 
	 * @return the height of the BST (a 1-node tree has height 0)
	 */
	public int height() {
		return height(root);
	}

	private int height(Node x) {
		if (x == null)
			return -1;
		return 1 + Math.max(height(x.left), height(x.right));
	}

	/***************************************************************************
	 * Ordered symbol table methods.
	 ***************************************************************************/

	/**
	 * Returns the smallest key in the symbol table.
	 * 
	 * @return the smallest key in the symbol table
	 * @throws NoSuchElementException
	 *             if the symbol table is empty
	 */
	public Key min() {
		if (isEmpty())
			throw new NoSuchElementException("called min() with empty symbol table");
		return min(root).key;
	}

	// the smallest key in subtree rooted at x; null if no such key
	private Node min(Node x) {
		// assert x != null;
		if (x.left == null)
			return x;
		else
			return min(x.left);
	}

	/**
	 * Returns the largest key in the symbol table.
	 * 
	 * @return the largest key in the symbol table
	 * @throws NoSuchElementException
	 *             if the symbol table is empty
	 */
	public Key max() {
		if (isEmpty())
			throw new NoSuchElementException("called max() with empty symbol table");
		return max(root).key;
	}

	// the largest key in the subtree rooted at x; null if no such key
	private Node max(Node x) {
		// assert x != null;
		if (x.right == null)
			return x;
		else
			return max(x.right);
	}

	/**
	 * Returns the largest key in the symbol table less than or equal to
	 * {@code key}.
	 * 
	 * @param key
	 *            the key
	 * @return the largest key in the symbol table less than or equal to {@code key}
	 * @throws NoSuchElementException
	 *             if there is no such key
	 * @throws IllegalArgumentException
	 *             if {@code key} is {@code null}
	 */
	public Key floor(Key key) {
		if (key == null)
			throw new IllegalArgumentException("argument to floor() is null");
		if (isEmpty())
			throw new NoSuchElementException("called floor() with empty symbol table");
		Node x = floor(root, key);
		if (x == null)
			return null;
		else
			return x.key;
	}

	// the largest key in the subtree rooted at x less than or equal to the given
	// key
	private Node floor(Node x, Key key) {
		if (x == null)
			return null;
		int cmp = key.compareTo(x.key);
		if (cmp == 0)
			return x;
		if (cmp < 0)
			return floor(x.left, key);
		Node t = floor(x.right, key);
		if (t != null)
			return t;
		else
			return x;
	}

	/**
	 * Returns the smallest key in the symbol table greater than or equal to
	 * {@code key}.
	 * 
	 * @param key
	 *            the key
	 * @return the smallest key in the symbol table greater than or equal to
	 *         {@code key}
	 * @throws NoSuchElementException
	 *             if there is no such key
	 * @throws IllegalArgumentException
	 *             if {@code key} is {@code null}
	 */
	public Key ceiling(Key key) {
		if (key == null)
			throw new IllegalArgumentException("argument to ceiling() is null");
		if (isEmpty())
			throw new NoSuchElementException("called ceiling() with empty symbol table");
		Node x = ceiling(root, key);
		if (x == null)
			return null;
		else
			return x.key;
	}

	// the smallest key in the subtree rooted at x greater than or equal to the
	// given key
	private Node ceiling(Node x, Key key) {
		if (x == null)
			return null;
		int cmp = key.compareTo(x.key);
		if (cmp == 0)
			return x;
		if (cmp > 0)
			return ceiling(x.right, key);
		Node t = ceiling(x.left, key);
		if (t != null)
			return t;
		else
			return x;
	}

	/**
	 * Return the kth smallest key in the symbol table.
	 * 
	 * @param k
	 *            the order statistic
	 * @return the {@code k}th smallest key in the symbol table
	 * @throws IllegalArgumentException
	 *             unless {@code k} is between 0 and <em>n</em>鈥�1
	 */
	public Key select(int k) {
		if (k < 0 || k >= size()) {
			throw new IllegalArgumentException("called select() with invalid argument: " + k);
		}
		Node x = select(root, k);
		return x.key;
	}

	// the key of rank k in the subtree rooted at x
	private Node select(Node x, int k) {
		// assert x != null;
		// assert k >= 0 && k < size(x);
		int t = size(x.left);
		if (t > k)
			return select(x.left, k);
		else if (t < k)
			return select(x.right, k - t - 1);
		else
			return x;
	}

	/**
	 * Return the number of keys in the symbol table strictly less than {@code key}.
	 * 
	 * @param key
	 *            the key
	 * @return the number of keys in the symbol table strictly less than {@code key}
	 * @throws IllegalArgumentException
	 *             if {@code key} is {@code null}
	 */
	public int rank(Key key) {
		if (key == null)
			throw new IllegalArgumentException("argument to rank() is null");
		return rank(key, root);
	}

	// number of keys less than key in the subtree rooted at x
	private int rank(Key key, Node x) {
		if (x == null)
			return 0;
		int cmp = key.compareTo(x.key);
		if (cmp < 0)
			return rank(key, x.left);
		else if (cmp > 0)
			return 1 + size(x.left) + rank(key, x.right);
		else
			return size(x.left);
	}

	/***************************************************************************
	 * Range count and range search.
	 ***************************************************************************/

	/**
	 * Returns all keys in the symbol table as an {@code Iterable}. To iterate over
	 * all of the keys in the symbol table named {@code st}, use the foreach
	 * notation: {@code for (Key key : st.keys())}.
	 * 
	 * @return all keys in the symbol table as an {@code Iterable}
	 */
	public Iterable<Key> keys() {
		if (isEmpty())
			return new Queue<Key>();
		return keys(min(), max());
	}

	/**
	 * Returns all keys in the symbol table in the given range, as an
	 * {@code Iterable}.
	 *
	 * @param lo
	 *            minimum endpoint
	 * @param hi
	 *            maximum endpoint
	 * @return all keys in the sybol table between {@code lo} (inclusive) and
	 *         {@code hi} (inclusive) as an {@code Iterable}
	 * @throws IllegalArgumentException
	 *             if either {@code lo} or {@code hi} is {@code null}
	 */
	public Iterable<Key> keys(Key lo, Key hi) {
		if (lo == null)
			throw new IllegalArgumentException("first argument to keys() is null");
		if (hi == null)
			throw new IllegalArgumentException("second argument to keys() is null");

		Queue<Key> queue = new Queue<Key>();
		// if (isEmpty() || lo.compareTo(hi) > 0) return queue;
		keys(root, queue, lo, hi);
		return queue;
	}

	// add the keys between lo and hi in the subtree rooted at x
	// to the queue
	private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
		if (x == null)
			return;
		int cmplo = lo.compareTo(x.key);
		int cmphi = hi.compareTo(x.key);
		if (cmplo < 0)
			keys(x.left, queue, lo, hi);
		if (cmplo <= 0 && cmphi >= 0)
			queue.enqueue(x.key);
		if (cmphi > 0)
			keys(x.right, queue, lo, hi);
	}

	/**
	 * Returns the number of keys in the symbol table in the given range.
	 *
	 * @param lo
	 *            minimum endpoint
	 * @param hi
	 *            maximum endpoint
	 * @return the number of keys in the sybol table between {@code lo} (inclusive)
	 *         and {@code hi} (inclusive)
	 * @throws IllegalArgumentException
	 *             if either {@code lo} or {@code hi} is {@code null}
	 */
	public int size(Key lo, Key hi) {
		if (lo == null)
			throw new IllegalArgumentException("first argument to size() is null");
		if (hi == null)
			throw new IllegalArgumentException("second argument to size() is null");

		if (lo.compareTo(hi) > 0)
			return 0;
		if (contains(hi))
			return rank(hi) - rank(lo) + 1;
		else
			return rank(hi) - rank(lo);
	}

	/***************************************************************************
	 * Check integrity of red-black tree data structure.
	 ***************************************************************************/
	private boolean check() {
		if (!isBST())
			StdOut.println("Not in symmetric order");
		if (!isSizeConsistent())
			StdOut.println("Subtree counts not consistent");
		if (!isRankConsistent())
			StdOut.println("Ranks not consistent");
		if (!is23())
			StdOut.println("Not a 2-3 tree");
		if (!isBalanced())
			StdOut.println("Not balanced");
		return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced();
	}

	// does this binary tree satisfy symmetric order?
	// Note: this test also ensures that data structure is a binary tree since order
	// is strict
	private boolean isBST() {
		return isBST(root, null, null);
	}

	// is the tree rooted at x a BST with all keys strictly between min and max
	// (if min or max is null, treat as empty constraint)
	// Credit: Bob Dondero's elegant solution
	private boolean isBST(Node x, Key min, Key max) {
		if (x == null)
			return true;
		if (min != null && x.key.compareTo(min) <= 0)
			return false;
		if (max != null && x.key.compareTo(max) >= 0)
			return false;
		return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
	}

	// are the size fields correct?
	private boolean isSizeConsistent() {
		return isSizeConsistent(root);
	}

	private boolean isSizeConsistent(Node x) {
		if (x == null)
			return true;
		if (x.size != size(x.left) + size(x.right) + 1)
			return false;
		return isSizeConsistent(x.left) && isSizeConsistent(x.right);
	}

	// check that ranks are consistent
	private boolean isRankConsistent() {
		for (int i = 0; i < size(); i++)
			if (i != rank(select(i)))
				return false;
		for (Key key : keys())
			if (key.compareTo(select(rank(key))) != 0)
				return false;
		return true;
	}

	// Does the tree have no red right links, and at most one (left)
	// red links in a row on any path?
	private boolean is23() {
		return is23(root);
	}

	private boolean is23(Node x) {
		if (x == null)
			return true;
		if (isRed(x.right))
			return false;
		if (x != root && isRed(x) && isRed(x.left))
			return false;
		return is23(x.left) && is23(x.right);
	}

	// do all paths from root to leaf have same number of black edges?
	private boolean isBalanced() {
		int black = 0; // number of black links on path from root to min
		Node x = root;
		while (x != null) {
			if (!isRed(x))
				black++;
			x = x.left;
		}
		return isBalanced(root, black);
	}

	// does every path from the root to a leaf have the given number of black links?
	private boolean isBalanced(Node x, int black) {
		if (x == null)
			return black == 0;
		if (!isRed(x))
			black--;
		return isBalanced(x.left, black) && isBalanced(x.right, black);
	}

	/**
	 * Unit tests the {@code RedBlackBST} data type.
	 *
	 * @param args
	 *            the command-line arguments
	 */
	public static void main(String[] args) {
		RedBlackBST<String, Integer> st = new RedBlackBST<String, Integer>();
		for (int i = 0; !StdIn.isEmpty(); i++) {
			String key = StdIn.readString();
			st.put(key, i);
		}
		for (String s : st.keys())
			StdOut.println(s + " " + st.get(s));
		StdOut.println();
	}
}

class Queue<Item> implements Iterable<Item> {
	private Node<Item> first; // beginning of queue
	private Node<Item> last; // end of queue
	private int n; // number of elements on queue

	// helper linked list class
	private static class Node<Item> {
		private Item item;
		private Node<Item> next;
	}

	/**
	 * Initializes an empty queue.
	 */
	public Queue() {
		first = null;
		last = null;
		n = 0;
	}

	/**
	 * Returns true if this queue is empty.
	 *
	 * @return {@code true} if this queue is empty; {@code false} otherwise
	 */
	public boolean isEmpty() {
		return first == null;
	}

	/**
	 * Returns the number of items in this queue.
	 *
	 * @return the number of items in this queue
	 */
	public int size() {
		return n;
	}

	/**
	 * Returns the item least recently added to this queue.
	 *
	 * @return the item least recently added to this queue
	 * @throws NoSuchElementException
	 *             if this queue is empty
	 */
	public Item peek() {
		if (isEmpty())
			throw new NoSuchElementException("Queue underflow");
		return first.item;
	}

	/**
	 * Adds the item to this queue.
	 *
	 * @param item
	 *            the item to add
	 */
	public void enqueue(Item item) {
		Node<Item> oldlast = last;
		last = new Node<Item>();
		last.item = item;
		last.next = null;
		if (isEmpty())
			first = last;
		else
			oldlast.next = last;
		n++;
	}

	/**
	 * Removes and returns the item on this queue that was least recently added.
	 *
	 * @return the item on this queue that was least recently added
	 * @throws NoSuchElementException
	 *             if this queue is empty
	 */
	public Item dequeue() {
		if (isEmpty())
			throw new NoSuchElementException("Queue underflow");
		Item item = first.item;
		first = first.next;
		n--;
		if (isEmpty())
			last = null; // to avoid loitering
		return item;
	}

	/**
	 * Returns a string representation of this queue.
	 *
	 * @return the sequence of items in FIFO order, separated by spaces
	 */
	public String toString() {
		StringBuilder s = new StringBuilder();
		for (Item item : this) {
			s.append(item);
			s.append(' ');
		}
		return s.toString();
	}

	/**
	 * Returns an iterator that iterates over the items in this queue in FIFO order.
	 *
	 * @return an iterator that iterates over the items in this queue in FIFO order
	 */
	public Iterator<Item> iterator() {
		return new ListIterator<Item>(first);
	}

	// an iterator, doesn't implement remove() since it's optional
	private class ListIterator<Item> implements Iterator<Item> {
		private Node<Item> current;

		public ListIterator(Node<Item> first) {
			current = first;
		}

		public boolean hasNext() {
			return current != null;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		public Item next() {
			if (!hasNext())
				throw new NoSuchElementException();
			Item item = current.item;
			current = current.next;
			return item;
		}
	}

	/**
	 * Unit tests the {@code Queue} data type.
	 *
	 * @param args
	 *            the command-line arguments
	 */
	public static void main(String[] args) {
		Queue<String> queue = new Queue<String>();
		while (!StdIn.isEmpty()) {
			String item = StdIn.readString();
			if (!item.equals("-"))
				queue.enqueue(item);
			else if (!queue.isEmpty())
				StdOut.print(queue.dequeue() + " ");
		}
		StdOut.println("(" + queue.size() + " left on queue)");
	}
}

final class StdOut {

	// force Unicode UTF-8 encoding; otherwise it's system dependent
	private static final String CHARSET_NAME = "UTF-8";

	// assume language = English, country = US for consistency with StdIn
	private static final Locale LOCALE = Locale.US;

	// send output here
	private static PrintWriter out;

	// this is called before invoking any methods
	static {
		try {
			out = new PrintWriter(new OutputStreamWriter(System.out, CHARSET_NAME), true);
		} catch (UnsupportedEncodingException e) {
			System.out.println(e);
		}
	}

	// don't instantiate
	private StdOut() {
	}

	/**
	 * Closes standard output.
	 */
	public static void close() {
		out.close();
	}

	/**
	 * Terminates the current line by printing the line-separator string.
	 */
	public static void println() {
		out.println();
	}

	/**
	 * Prints an object to this output stream and then terminates the line.
	 *
	 * @param x
	 *            the object to print
	 */
	public static void println(Object x) {
		out.println(x);
	}

	/**
	 * Prints a boolean to standard output and then terminates the line.
	 *
	 * @param x
	 *            the boolean to print
	 */
	public static void println(boolean x) {
		out.println(x);
	}

	/**
	 * Prints a character to standard output and then terminates the line.
	 *
	 * @param x
	 *            the character to print
	 */
	public static void println(char x) {
		out.println(x);
	}

	/**
	 * Prints a double to standard output and then terminates the line.
	 *
	 * @param x
	 *            the double to print
	 */
	public static void println(double x) {
		out.println(x);
	}

	/**
	 * Prints an integer to standard output and then terminates the line.
	 *
	 * @param x
	 *            the integer to print
	 */
	public static void println(float x) {
		out.println(x);
	}

	/**
	 * Prints an integer to standard output and then terminates the line.
	 *
	 * @param x
	 *            the integer to print
	 */
	public static void println(int x) {
		out.println(x);
	}

	/**
	 * Prints a long to standard output and then terminates the line.
	 *
	 * @param x
	 *            the long to print
	 */
	public static void println(long x) {
		out.println(x);
	}

	/**
	 * Prints a short integer to standard output and then terminates the line.
	 *
	 * @param x
	 *            the short to print
	 */
	public static void println(short x) {
		out.println(x);
	}

	/**
	 * Prints a byte to standard output and then terminates the line.
	 * <p>
	 * To write binary data, see {@link BinaryStdOut}.
	 *
	 * @param x
	 *            the byte to print
	 */
	public static void println(byte x) {
		out.println(x);
	}

	/**
	 * Flushes standard output.
	 */
	public static void print() {
		out.flush();
	}

	/**
	 * Prints an object to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the object to print
	 */
	public static void print(Object x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a boolean to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the boolean to print
	 */
	public static void print(boolean x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a character to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the character to print
	 */
	public static void print(char x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a double to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the double to print
	 */
	public static void print(double x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a float to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the float to print
	 */
	public static void print(float x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints an integer to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the integer to print
	 */
	public static void print(int x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a long integer to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the long integer to print
	 */
	public static void print(long x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a short integer to standard output and flushes standard output.
	 * 
	 * @param x
	 *            the short integer to print
	 */
	public static void print(short x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a byte to standard output and flushes standard output.
	 *
	 * @param x
	 *            the byte to print
	 */
	public static void print(byte x) {
		out.print(x);
		out.flush();
	}

	/**
	 * Prints a formatted string to standard output, using the specified format
	 * string and arguments, and then flushes standard output.
	 *
	 *
	 * @param format
	 *            the <a href =
	 *            "http://docs.oracle.com/javase/7/docs/api/java/util/Formatter.html#syntax">format
	 *            string</a>
	 * @param args
	 *            the arguments accompanying the format string
	 */
	public static void printf(String format, Object... args) {
		out.printf(LOCALE, format, args);
		out.flush();
	}

	/**
	 * Prints a formatted string to standard output, using the locale and the
	 * specified format string and arguments; then flushes standard output.
	 *
	 * @param locale
	 *            the locale
	 * @param format
	 *            the <a href =
	 *            "http://docs.oracle.com/javase/7/docs/api/java/util/Formatter.html#syntax">format
	 *            string</a>
	 * @param args
	 *            the arguments accompanying the format string
	 */
	public static void printf(Locale locale, String format, Object... args) {
		out.printf(locale, format, args);
		out.flush();
	}

	/**
	 * Unit tests some of the methods in {@code StdOut}.
	 *
	 * @param args
	 *            the command-line arguments
	 */
	public static void main(String[] args) {

		// write to stdout
		StdOut.println("Test");
		StdOut.println(17);
		StdOut.println(true);
		StdOut.printf("%.6f\n", 1.0 / 7.0);
	}

}

final class StdIn {

	/*** begin: section (1 of 2) of code duplicated from In to StdIn. */

	// assume Unicode UTF-8 encoding
	private static final String CHARSET_NAME = "UTF-8";

	// assume language = English, country = US for consistency with System.out.
	private static final Locale LOCALE = Locale.US;

	// the default token separator; we maintain the invariant that this value
	// is held by the scanner's delimiter between calls
	private static final Pattern WHITESPACE_PATTERN = Pattern.compile("\\p{javaWhitespace}+");

	// makes whitespace significant
	private static final Pattern EMPTY_PATTERN = Pattern.compile("");

	// used to read the entire input
	private static final Pattern EVERYTHING_PATTERN = Pattern.compile("\\A");

	/*** end: section (1 of 2) of code duplicated from In to StdIn. */

	private static Scanner scanner;

	// it doesn't make sense to instantiate this class
	private StdIn() {
	}

	//// begin: section (2 of 2) of code duplicated from In to StdIn,
	//// with all methods changed from "public" to "public static"

	/**
	 * Returns true if standard input is empty (except possibly for whitespace). Use
	 * this method to know whether the next call to {@link #readString()},
	 * {@link #readDouble()}, etc will succeed.
	 *
	 * @return {@code true} if standard input is empty (except possibly for
	 *         whitespace); {@code false} otherwise
	 */
	public static boolean isEmpty() {
		return !scanner.hasNext();
	}

	/**
	 * Returns true if standard input has a next line. Use this method to know
	 * whether the next call to {@link #readLine()} will succeed. This method is
	 * functionally equivalent to {@link #hasNextChar()}.
	 *
	 * @return {@code true} if standard input has more input (including whitespace);
	 *         {@code false} otherwise
	 */
	public static boolean hasNextLine() {
		return scanner.hasNextLine();
	}

	/**
	 * Returns true if standard input has more input (including whitespace). Use
	 * this method to know whether the next call to {@link #readChar()} will
	 * succeed. This method is functionally equivalent to {@link #hasNextLine()}.
	 *
	 * @return {@code true} if standard input has more input (including whitespace);
	 *         {@code false} otherwise
	 */
	public static boolean hasNextChar() {
		scanner.useDelimiter(EMPTY_PATTERN);
		boolean result = scanner.hasNext();
		scanner.useDelimiter(WHITESPACE_PATTERN);
		return result;
	}

	/**
	 * Reads and returns the next line, excluding the line separator if present.
	 *
	 * @return the next line, excluding the line separator if present; {@code null}
	 *         if no such line
	 */
	public static String readLine() {
		String line;
		try {
			line = scanner.nextLine();
		} catch (NoSuchElementException e) {
			line = null;
		}
		return line;
	}

	/**
	 * Reads and returns the next character.
	 *
	 * @return the next {@code char}
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 */
	public static char readChar() {
		try {
			scanner.useDelimiter(EMPTY_PATTERN);
			String ch = scanner.next();
			assert ch.length() == 1 : "Internal (Std)In.readChar() error!" + " Please contact the authors.";
			scanner.useDelimiter(WHITESPACE_PATTERN);
			return ch.charAt(0);
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'char' value from standard input, but there are no more tokens available");
		}
	}

	/**
	 * Reads and returns the remainder of the input, as a string.
	 *
	 * @return the remainder of the input, as a string
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 */
	public static String readAll() {
		if (!scanner.hasNextLine())
			return "";

		String result = scanner.useDelimiter(EVERYTHING_PATTERN).next();
		// not that important to reset delimeter, since now scanner is empty
		scanner.useDelimiter(WHITESPACE_PATTERN); // but let's do it anyway
		return result;
	}

	/**
	 * Reads the next token and returns the {@code String}.
	 *
	 * @return the next {@code String}
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 */
	public static String readString() {
		try {
			return scanner.next();
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'String' value from standard input, but there are no more tokens available");
		}
	}

	/**
	 * Reads the next token from standard input, parses it as an integer, and
	 * returns the integer.
	 *
	 * @return the next integer on standard input
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 * @throws InputMismatchException
	 *             if the next token cannot be parsed as an {@code int}
	 */
	public static int readInt() {
		try {
			return scanner.nextInt();
		} catch (InputMismatchException e) {
			String token = scanner.next();
			throw new InputMismatchException(
					"attempts to read an 'int' value from standard input, but the next token is \"" + token + "\"");
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attemps to read an 'int' value from standard input, but there are no more tokens available");
		}

	}

	/**
	 * Reads the next token from standard input, parses it as a double, and returns
	 * the double.
	 *
	 * @return the next double on standard input
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 * @throws InputMismatchException
	 *             if the next token cannot be parsed as a {@code double}
	 */
	public static double readDouble() {
		try {
			return scanner.nextDouble();
		} catch (InputMismatchException e) {
			String token = scanner.next();
			throw new InputMismatchException(
					"attempts to read a 'double' value from standard input, but the next token is \"" + token + "\"");
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'double' value from standard input, but there are no more tokens available");
		}
	}

	/**
	 * Reads the next token from standard input, parses it as a float, and returns
	 * the float.
	 *
	 * @return the next float on standard input
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 * @throws InputMismatchException
	 *             if the next token cannot be parsed as a {@code float}
	 */
	public static float readFloat() {
		try {
			return scanner.nextFloat();
		} catch (InputMismatchException e) {
			String token = scanner.next();
			throw new InputMismatchException(
					"attempts to read a 'float' value from standard input, but the next token is \"" + token + "\"");
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'float' value from standard input, but there are no more tokens available");
		}
	}

	/**
	 * Reads the next token from standard input, parses it as a long integer, and
	 * returns the long integer.
	 *
	 * @return the next long integer on standard input
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 * @throws InputMismatchException
	 *             if the next token cannot be parsed as a {@code long}
	 */
	public static long readLong() {
		try {
			return scanner.nextLong();
		} catch (InputMismatchException e) {
			String token = scanner.next();
			throw new InputMismatchException(
					"attempts to read a 'long' value from standard input, but the next token is \"" + token + "\"");
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'long' value from standard input, but there are no more tokens available");
		}
	}

	/**
	 * Reads the next token from standard input, parses it as a short integer, and
	 * returns the short integer.
	 *
	 * @return the next short integer on standard input
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 * @throws InputMismatchException
	 *             if the next token cannot be parsed as a {@code short}
	 */
	public static short readShort() {
		try {
			return scanner.nextShort();
		} catch (InputMismatchException e) {
			String token = scanner.next();
			throw new InputMismatchException(
					"attempts to read a 'short' value from standard input, but the next token is \"" + token + "\"");
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'short' value from standard input, but there are no more tokens available");
		}
	}

	/**
	 * Reads the next token from standard input, parses it as a byte, and returns
	 * the byte.
	 *
	 * @return the next byte on standard input
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 * @throws InputMismatchException
	 *             if the next token cannot be parsed as a {@code byte}
	 */
	public static byte readByte() {
		try {
			return scanner.nextByte();
		} catch (InputMismatchException e) {
			String token = scanner.next();
			throw new InputMismatchException(
					"attempts to read a 'byte' value from standard input, but the next token is \"" + token + "\"");
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'byte' value from standard input, but there are no more tokens available");
		}
	}

	/**
	 * Reads the next token from standard input, parses it as a boolean, and returns
	 * the boolean.
	 *
	 * @return the next boolean on standard input
	 * @throws NoSuchElementException
	 *             if standard input is empty
	 * @throws InputMismatchException
	 *             if the next token cannot be parsed as a {@code boolean}:
	 *             {@code true} or {@code 1} for true, and {@code false} or
	 *             {@code 0} for false, ignoring case
	 */
	public static boolean readBoolean() {
		try {
			String token = readString();
			if ("true".equalsIgnoreCase(token))
				return true;
			if ("false".equalsIgnoreCase(token))
				return false;
			if ("1".equals(token))
				return true;
			if ("0".equals(token))
				return false;
			throw new InputMismatchException(
					"attempts to read a 'boolean' value from standard input, but the next token is \"" + token + "\"");
		} catch (NoSuchElementException e) {
			throw new NoSuchElementException(
					"attempts to read a 'boolean' value from standard input, but there are no more tokens available");
		}

	}

	/**
	 * Reads all remaining tokens from standard input and returns them as an array
	 * of strings.
	 *
	 * @return all remaining tokens on standard input, as an array of strings
	 */
	public static String[] readAllStrings() {
		// we could use readAll.trim().split(), but that's not consistent
		// because trim() uses characters 0x00..0x20 as whitespace
		String[] tokens = WHITESPACE_PATTERN.split(readAll());
		if (tokens.length == 0 || tokens[0].length() > 0)
			return tokens;

		// don't include first token if it is leading whitespace
		String[] decapitokens = new String[tokens.length - 1];
		for (int i = 0; i < tokens.length - 1; i++)
			decapitokens[i] = tokens[i + 1];
		return decapitokens;
	}

	/**
	 * Reads all remaining lines from standard input and returns them as an array of
	 * strings.
	 * 
	 * @return all remaining lines on standard input, as an array of strings
	 */
	public static String[] readAllLines() {
		ArrayList<String> lines = new ArrayList<String>();
		while (hasNextLine()) {
			lines.add(readLine());
		}
		return lines.toArray(new String[lines.size()]);
	}

	/**
	 * Reads all remaining tokens from standard input, parses them as integers, and
	 * returns them as an array of integers.
	 * 
	 * @return all remaining integers on standard input, as an array
	 * @throws InputMismatchException
	 *             if any token cannot be parsed as an {@code int}
	 */
	public static int[] readAllInts() {
		String[] fields = readAllStrings();
		int[] vals = new int[fields.length];
		for (int i = 0; i < fields.length; i++)
			vals[i] = Integer.parseInt(fields[i]);
		return vals;
	}

	/**
	 * Reads all remaining tokens from standard input, parses them as longs, and
	 * returns them as an array of longs.
	 * 
	 * @return all remaining longs on standard input, as an array
	 * @throws InputMismatchException
	 *             if any token cannot be parsed as a {@code long}
	 */
	public static long[] readAllLongs() {
		String[] fields = readAllStrings();
		long[] vals = new long[fields.length];
		for (int i = 0; i < fields.length; i++)
			vals[i] = Long.parseLong(fields[i]);
		return vals;
	}

	/**
	 * Reads all remaining tokens from standard input, parses them as doubles, and
	 * returns them as an array of doubles.
	 * 
	 * @return all remaining doubles on standard input, as an array
	 * @throws InputMismatchException
	 *             if any token cannot be parsed as a {@code double}
	 */
	public static double[] readAllDoubles() {
		String[] fields = readAllStrings();
		double[] vals = new double[fields.length];
		for (int i = 0; i < fields.length; i++)
			vals[i] = Double.parseDouble(fields[i]);
		return vals;
	}

	//// end: section (2 of 2) of code duplicated from In to StdIn

	// do this once when StdIn is initialized
	static {
		resync();
	}

	/**
	 * If StdIn changes, use this to reinitialize the scanner.
	 */
	private static void resync() {
		setScanner(new Scanner(new java.io.BufferedInputStream(System.in), CHARSET_NAME));
	}

	private static void setScanner(Scanner scanner) {
		StdIn.scanner = scanner;
		StdIn.scanner.useLocale(LOCALE);
	}

	/**
	 * Reads all remaining tokens, parses them as integers, and returns them as an
	 * array of integers.
	 * 
	 * @return all remaining integers, as an array
	 * @throws InputMismatchException
	 *             if any token cannot be parsed as an {@code int}
	 * @deprecated Replaced by {@link #readAllInts()}.
	 */
	@Deprecated
	public static int[] readInts() {
		return readAllInts();
	}

	/**
	 * Reads all remaining tokens, parses them as doubles, and returns them as an
	 * array of doubles.
	 * 
	 * @return all remaining doubles, as an array
	 * @throws InputMismatchException
	 *             if any token cannot be parsed as a {@code double}
	 * @deprecated Replaced by {@link #readAllDoubles()}.
	 */
	@Deprecated
	public static double[] readDoubles() {
		return readAllDoubles();
	}

	/**
	 * Reads all remaining tokens and returns them as an array of strings.
	 * 
	 * @return all remaining tokens, as an array of strings
	 * @deprecated Replaced by {@link #readAllStrings()}.
	 */
	@Deprecated
	public static String[] readStrings() {
		return readAllStrings();
	}

	/**
	 * Interactive test of basic functionality.
	 *
	 * @param args
	 *            the command-line arguments
	 */
	public static void main(String[] args) {

		StdOut.print("Type a string: ");
		String s = StdIn.readString();
		StdOut.println("Your string was: " + s);
		StdOut.println();

		StdOut.print("Type an int: ");
		int a = StdIn.readInt();
		StdOut.println("Your int was: " + a);
		StdOut.println();

		StdOut.print("Type a boolean: ");
		boolean b = StdIn.readBoolean();
		StdOut.println("Your boolean was: " + b);
		StdOut.println();

		StdOut.print("Type a double: ");
		double c = StdIn.readDouble();
		StdOut.println("Your double was: " + c);
		StdOut.println();
	}

}