package btree;

	
import java.util.*;  // import Collections, Iterable, etc.

/** javadoc comments describing the BTree class should go here */
public abstract class BTree<T> {
	
	protected BNode root;
	
	/** Creates a new empty BTree */
	public BTree () {
		root = null;
	}
	


		/** determines whether or not this BTree is empty
	     @return true if the tree is empty, false otherwise	    
	    */
	public boolean isEmpty() {
		return (root == null);
	}
	

	// traversal methods
	/*
		public Collection<T> inorder() 		//work left for students
		public Collection<T> postorder() 	//work left for students
		public void inorder_display()  		//work left for students
		public void postorder_display()  	//work left for students
	*/

	/** This method returns an ArrayList containing all the data values
		stored in the tree, arranged in the order of a preorder traversal.
	*/
	public Collection<T> preorder() {
		return preorder(root);
	}
	private Collection<T> preorder(BNode<T> parent) {
		Collection<T> list = new ArrayList<T>();
	   	if (parent != null) {
		  	list.add(parent.data);
		  	list.addAll(preorder(parent.left));
		  	list.addAll(preorder(parent.right));
	   }
		return list;
	}
	
	/** This method displays, in the order of a preorder traversal,
	 	all the data values stored in the tree */
	public void preorder_display() {
		Collection<T> preorder_list = preorder(root);
		if (preorder_list != null) {
			Iterator<T> i = preorder_list.iterator();
			while (i.hasNext()) {
				System.out.println(i.next().toString());
			}
		}
		else {
			System.out.println("Empty tree ... No nodes to display");
		}
	}
			
			

	// insert, find, delete methods
	/** The method makes sure that the specified item is stored in the
	    binary tree.  The item is added to the tree if that value is not
	    already stored in the tree.
	    @param item the object to be stored in the binary tree
	    @return true if the item is added, false otherwise	    
	    */
	public abstract boolean insert(T item);
	
	
	/** This method makes sure that the specified item is not in the
	    binary tree
	    @param item the object to be removed from the binary tree
	    @return true if the item is found and removed, false otherwise	    
	    */
	public abstract boolean delete(T item);
	
	
	
	
	
	
	/** This method determines whether or not an item matching the parameter is stored
	    in the binary tree.
	    @param item the object to be searched for in the binary tree
	    @return the matching item found in the tree, else null if no match is found  
	    */
	public T find (T item) {
		// can be overridden ... meant to be overridden in most cases
		/* Uses an iterator on the Collection returned by preorder
		and the equals() method inherited from the Object class
		to find a matching item, if there is one.
		*/
		Collection<T> preorder_list = preorder(root);
		if (preorder_list != null) {
			Iterator<T> i = preorder_list.iterator();
			T current_item = i.next();
			while ((! item.equals(current_item) && i.hasNext())) {
				current_item = i.next();
			}
			if (item.equals(current_item)) {
				return current_item;
			}
			else {
				return null;
			}
		}
		else {
			return null;
		}
	}
}