package edd.util;

import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class TreeSet<E extends Comparable<E>> extends AbstractSet<E> {
    
    private static class Node<E> {
        public Node<E> left;
        public Node<E> right;
        public E info;
        public Node(E info) {
            this.info = info;
            this.left = null;
            this.right = null;
        }
    }
    
    private Node<E> root;
    private int count;
    
    public TreeSet() {
        root = null;
        count = 0;
    }
    
    @Override
    public boolean add(E e) {        
        if (root == null) {                      
            root = new Node<>(e);
            count++;
            return true;
        } else {
            Node<E> p = root;
            while (true) {
                if (e.compareTo(p.info) == 0) {
                    return false;
                }
                if (e.compareTo(p.info) < 0) {
                    if (p.left == null) {
                        p.left = new Node<>(e);
                        count++;
                        return true;
                    } else {
                        p = p.left;
                    }
                } else {
                    if (p.right == null) {
                        p.right = new Node<>(e);
                        count++;
                        return true;
                    } else {
                        p = p.right;
                    }
                }
            }
        }        
    }
    
    @Override
    public boolean contains(Object obj) {
        
        if (obj == null
                || (root != null && obj.getClass() != root.info.getClass())) {
            return false;
        }

        @SuppressWarnings("unchecked")
        Comparable<E> cmp = (Comparable<E>) obj;
        Node<E> p = root;
        
        while (p != null) {            
            if (cmp.compareTo(p.info) == 0) {
                return true;
            }
            if (cmp.compareTo(p.info) < 0) {
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return false;
    }
    
    private void inOrder(Node<E> root, List<E> lst) {
        if (root != null) {
            inOrder(root.left, lst);
            lst.add(root.info);
            inOrder(root.right, lst);
        }        
    }
    
    public List<E> inOrderList() {
        List<E> lst = new ArrayList<>();
        inOrder(root, lst);
        return lst;
    }

    private void preOrder(Node<E> root, List<E> lst) {
        if (root != null) {
            lst.add(root.info);
            preOrder(root.left, lst);            
            preOrder(root.right, lst);
        }        
    }
    
    public List<E> preOrderList() {
        List<E> lst = new ArrayList<>();
        preOrder(root, lst);
        return lst;
    }
    
    private void postOrder(Node<E> root, List<E> lst) {
        if (root != null) {            
            postOrder(root.left, lst);            
            postOrder(root.right, lst);
            lst.add(root.info);
        }        
    }
    
    public List<E> postOrderList() {
        List<E> lst = new ArrayList<>();
        postOrder(root, lst);
        return lst;
    }
    
    @Override
    public Iterator<E> iterator() {
        return inOrderList().iterator();
    }

    @Override
    public int size() {
        return count;
    }
    
    @Override
    public void clear() {
        root = null;
        count = 0;
    }
}