package hw.bst;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

// This implementation is based on the BST class provided by the OpenDSA project:
//
// Distributed under the MIT License
//
// Copyright (c) 2011-2020 - Ville Karavirta and Cliff Shaffer
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

/**
 * Non-self-balancing Binary search tree based dictionary class.
 *
 * This code is a modified version of the OpenDSA Binary Search Tree implementation.
 *
 */
public class BSTDictionary<K extends Comparable<K>, V> implements Dictionary<K, V> {
  protected BSTNode<K, V> root; // Root of the BST
  private int nodeCount; // Number of nodes in the BST

  /** Constructor. */
  BSTDictionary() {
    root = null;
    nodeCount = 0;
  }

  /** Reinitialize tree. */
  public void clear() {
    root = null;
    nodeCount = 0;
  }

  /**
   * Insert a record into the tree. Keys can be anything, but they must be Comparable.
   *
   * @param k The key to insert.
   * @param v The value to insert.
   */
  public void insert(K k, V v) {
    root = insertHelp(root, k, v);
  }

  /**
   * Remove a record from the tree.
   *
   * @param key The key value of record to remove
   * @return The value removed, null if there is none.
   */
  public V remove(K key) {
    V temp = findHelp(root, key); // First find it
    if (temp != null) {
      root = removeHelp(root, key); // Now remove it
      nodeCount--;
    }
    return temp;
  }

  /**
   * Return the record with key k, null if none exists.
   *
   * @param key The key to find
   * @return The value associated with the key, or null if not found
   */
  public V find(K key) {
    return findHelp(root, key);
  }

  /**
   * Return the number of records in the dictionary.
   *
   * @return The number of records in the dictionary
   */
  public int size() {
    return nodeCount;
  }

  /**
   * Return a record that matches the key.
   *
   * @param rt The root of the subtree
   * @param key The key to find
   * @return The value associated with the key, or null if not found
   */
  private V findHelp(BSTNode<K, V> rt, K key) {
    if (rt == null) {
      return null;
    }
    if (rt.key().compareTo(key) > 0) {
      return findHelp(rt.left(), key);
    } else if (rt.key().compareTo(key) == 0) {
      return rt.value();
    } else {
      return findHelp(rt.right(), key);
    }
  }


  /**
   * Return the current subtree, modified to contain the new item.
   *
   * @param rt The root of the subtree
   * @param k The key to insert
   * @param v The value to insert
   * @return The modified subtree
   */
  private BSTNode<K, V> insertHelp(BSTNode<K, V> rt, K k, V v) {
    if (rt == null) {
      nodeCount++;
      return new BSTNode<K, V>(k, v);
    }
    if (rt.key().compareTo(k) > 0) {
      rt.setLeft(insertHelp(rt.left(), k, v));
    } else if (rt.key().compareTo(k) == 0) {
      rt.setValue(v);
    } else {
      rt.setRight(insertHelp(rt.right(), k, v));
    }
    return rt;
  }

  /**
   * Delete the maximum valued element in a subtree.
   *
   * @param rt The root of the subtree
   * @return The modified subtree with the maximum element removed
   */
  private BSTNode<K, V> deleteMax(BSTNode<K, V> rt) {
    if (rt.right() == null) {
      return rt.left();
    }
    rt.setRight(deleteMax(rt.right()));
    return rt;
  }


  /**
   * Get the maximum valued element in a subtree.
   *
   * @param rt The root of the subtree
   * @return The node with the maximum key
   */
  private BSTNode<K, V> getMax(BSTNode<K, V> rt) {
    if (rt.right() == null) {
      return rt;
    }
    return getMax(rt.right());
  }

  /**
   * Remove a node with the given key.
   *
   * @param rt The root of the subtree
   * @param key The key to remove
   * @return The tree with the node removed
   */
  private BSTNode<K, V> removeHelp(BSTNode<K, V> rt, K key) {
    if (rt == null) {
      return null;
    }
    if (rt.key().compareTo(key) > 0) {
      rt.setLeft(removeHelp(rt.left(), key));
    } else if (rt.key().compareTo(key) < 0) {
      rt.setRight(removeHelp(rt.right(), key));
    } else { // Found it
      if (rt.left() == null) {
        return rt.right();
      } else if (rt.right() == null) {
        return rt.left();
      } else { // Two children
        BSTNode<K, V> temp = getMax(rt.left());
        rt.setKey(temp.key());
        rt.setValue(temp.value());
        rt.setLeft(deleteMax(rt.left()));
      }
    }
    return rt;
  }

  /**
   * Return a string representation of the dictionary in the format {key1=value1, key2=value2, ...}.
   * Keys are listed in sorted order (in-order traversal of the BST).
   *
   * @return A string representation of the dictionary
   */
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("{");
    boolean first = true;
    for (K key : this) {
      if (!first) {
        sb.append(", ");
      }
      sb.append(key);
      sb.append("=");
      sb.append(find(key));
      first = false;
    }
    sb.append("}");
    return sb.toString();
  }

  // --------------------------------------------------------------------
  // UNFINISHED METHODS FOR ADDED FUNCTIONALITY
  // --------------------------------------------------------------------

  /**
   * Return the minimum key from the tree, or null if the tree is empty.
   */
  public K minKey() {
    // NOTE: this could be implemented recursively or iteratively. Your implementation *must be
    // recursive*. You will need to add a private helper method.
    return null;
  }


  /**
   * Return the maximum key from the tree, or null if the tree is empty.
   */
  public K maxKey() {
    // NOTE: this could be implemented recursively or iteratively. Your implementation *must be
    // recursive*. You will need to add a private helper method.
    return null;
  }


  /**
   * Return an ordered list of all keys.
   */
  public List<K> keyList() {
    // Recall that an in-order traversal of a binary search tree visits the nodes... in order.
    // You will need to add a private helper method
    // The cleanest implementation involves creating an empty list in this method, and passing it to
    // the recursive helper method to be populated.
    return null;
  }


  /**
   * Return an ordered list of keys between min and max. This method will not traverse portions of
   * the tree that could not contain keys in the specified range.
   *
   * @param min Minimum key (inclusive)
   * @param max Minimum key (inclusive)
   * @return An ordered list of keys.
   */
  public List<K> rangeSearch(K min, K max) {
    // Again, you will need to create a private helper method. Your implementation MUST NOT traverse
    // portions of the tree that could not contain keys in the specified range. In other words,
    // don't recursively traverse a subtree if there is no way it could contain a value between min
    // and max.
    return null;

  }


  @Override
  public Iterator<K> iterator() {
    // The simplest way to to create an iterator is to perform a full traversal at the time the
    // iterator is constructed, storing all of the keys in a list. The `next` method can then just
    // return the next available element in the list. This is not a great implementation! It
    // requires O(n) space and O(n) time, even if we only end up iterating through 1 item.
    //
    // A *better* implementation would keep track of where we are in an in-order traversal between
    // calls to `next`. This can be accomplished using a stack to simulate the call stack that would
    // exist during an in-order traversal. You are free to do this the easy way, but I
    // encourage you to think about the smart way if you have time.
    //
    // You do not need to implement remove.
    return null;
  }


  // --------------------------------------------------------------------
  // UNFINISHED METHODS FOR TREE ANALYSIS
  // --------------------------------------------------------------------

  /**
   * Return the height of the tree. (The height of an empty tree is -1)
   */
  public int height() {
    // You will need to create a recursive helper method.
    return -2;
  }

  /**
   * Return the depth of the node with the given key, or -1 if the key is not found. The root is at
   * depth 0.
   */
  public int keyDepth(K key) {
    // You will need to create a recursive helper method.
    return -2;
  }


  /**
   * Return a dictionary mapping depth levels to node counts. This provides a histogram showing the
   * distribution of nodes across different depth levels in the tree. The root is at depth 0.
   *
   * <p>
   * For example:
   *
   * <ul>
   * <li>A tree with a single node returns {0=1}
   * <li>A perfectly balanced tree with 7 nodes returns {0=1, 1=2, 2=4}
   * <li>A completely unbalanced tree (linked list) with 3 nodes returns {0=1, 1=1, 2=1}
   * </ul>
   *
   * <p>
   * The sum of all values in the returned histogram equals the size of the tree.
   *
   * @return A dictionary mapping depth (Integer) to the count of nodes at that depth (Integer)
   */
  public BSTDictionary<Integer, Integer> nodeDepthHistogram() {
    return null;
  }



}