/*
***Put your name here***

Template for the BSTMap classes
Spring 2019
CS 231 Project 6
*/
import java.util.ArrayList;
import java.util.Comparator;

public class BSTMap<K, V> implements MapSet<K, V> {

	// fields here
	// need a TNode root
	// need a Comparator<K> to compare Keys
	// probably want a size field

	// constructor: takes in a Comparator object
	public BSTMap( Comparator<K> comp ) {
		// initialize fields here
	}

	// adds or updates a key-value pair
	// If there is already a piar with new_key in the map, then update
	// the pair's value to new_value.
	// If there is not already a pair with new_key, then
	// add pair with new_key and new_value.
	// returns the old value or null if no old value existed
	public V put( K key, V value ) {
				// check for and handle the special case
				// call the root node's put method

				// stub code
				return null;
        }

    // gets the value at the specified key or null
    public V get( K key ) {
            // check for and handle the special case
            // call the root node's get method

            // stub code
            return null;
    }

    // Write stubs (functions with no code) for the remaining
    // functions in the MapSet interface


    // You can make this a nested class, doesn't have to be
    private class TNode {
            // need fields for the left and right children
            // need a KeyValuePair to hold the data at this node

            // constructor, given a key and a value
            public TNode( K k, V v ) {
                    // initialize all of the TNode fields
            }

            // Takes in a key, a value, and a comparator and inserts the TNode
            // Returns the old value of the node, if replaced, or null if inserted
            public V put( K key, V value, Comparator<K> comp ) {
                    // implement the binary search tree put
                    // insert only if the key doesn't already exist

                    // stub code
                    return null;
            }

            // Takes in a key and a comparator
            // Returns the value associated with the key or null
            public V get( K key, Comparator<K> comp ) {

                    // stub code
                    return null;
            }

            // Remaining methods below, mostly for building ArrayLists
            
            
    }// end of TNode class

    // test function
    public static void main( String[] argv ) {
            // create a BSTMap
            BSTMap<String, Integer> bst = new BSTMap<String, Integer>( new StringAscending() );

            bst.put( "twenty", 20 );
            bst.put( "ten", 10 );
            bst.put( "eleven", 11 );
            bst.put( "five", 5 );
            bst.put( "six", 6 );

            System.out.println( bst.get( "eleven" ) );

            // put more test code here
    }

}

// comparator class separate
class StringAscending implements Comparator<String> {
		public int compare( String a, String b ) {
				return a.compareTo(b);
		}
}