/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package generics;

import java.util.Iterator;
import java.util.Stack;

/**
 *
 * @author steve
 */
public class GenericTreeMap<K extends Comparable<K>, V> implements MinGenericMap<K,V> {

    GenericTreeNode<K,V> head = null;
    
    @Override
    public void put(K k, V v) {
        if(head == null) head = new GenericTreeNode<>(k,v);
        else put(head, k, v);
    }

    @Override
    public V get(K k) {
        if(head == null) return null;
        else return get(head, k);
    }

    @Override
    public int size() {
        return size(head);
    }

    @Override
    public Iterator<K> iterator() {
        Stack<GenericTreeNode<K, V>> stack = new Stack<>();
        addAll(stack, head);
        return new Iterator<>() {
            @Override
            public boolean hasNext() {
                return stack.size() > 0;
            }

            @Override
            public K next() {
                var node = stack.pop();
                if(node.right != null) addAll(stack, node.right);
                return node.k;
            }
            
        };
    }

    private void put(GenericTreeNode<K, V> node, K k, V v) {
        var result = k.compareTo(node.k);
        if(result < 0) {
            if(node.left == null) node.left = new GenericTreeNode<>(k,v);
            else put(node.left, k, v);
        } else if(result > 0) {
            if(node.right == null) node.right = new GenericTreeNode<>(k,v);
            else put(node.right, k, v);
        } else {
            node.v = v;
        }
    }

    private V get(GenericTreeNode<K, V> node, K k) {
        var result = k.compareTo(node.k);
        if(result < 0) {
            if(node.left == null) return null;
            else return get(node.left, k);
        } else if(result > 0) {
            if(node.right == null) return null;
            else return get(node.right, k);
        } else {
            return node.v;
        }
    }
    public static void main(String[] args) {
        MinGenericMap<String,Integer> map = new GenericTreeMap<>();
        GenericMapTest.test(map);
    }

    static <K,V> void addAll(Stack<GenericTreeNode<K, V>> stack, GenericTreeNode<K, V> x) {
        while(x != null) {
            stack.add(x);
            x = x.left;
        }
    }

    private int size(GenericTreeNode<K, V> node) {
        if(node == null) return 0;
        else return 1 + size(node.left) + size(node.right);
    }
    
}