ok

ss
mail@pastecode.io avatar
unknown
plain_text
2 years ago
11 kB
1
Indexable
Never
import java.util.*;
import java.util.logging.Logger;
public class StaffBST implements IStaffDB {
    private static final Logger LOGGER = Logger.getLogger(StaffBST.class.getName());
    int three_depth=0;
    static Boolean present= true;

    private class Node {
        Employee data;
        Node left, right;

        private Node(Employee m) {
            data = m;
            left = null;
            right = null;
        }
    }

    private static Node root; // this is the tree
    private int numEntries;

    private  static  Node root_copy;



    public StaffBST() {
        System.out.println("Binary Search Tree");
        clearDB();
    }

    /**
     * Empties the database.
     *
     * @pre true
     */
    @Override
    public void clearDB() {
        root = null; // garbage collector will tidy up
        numEntries = 0;
    }

    /**
     * Determines whether a member's name exists as a key inside the database
     *
     * @param name the member name (key) to locate
     * @return true iff the name exists as a key in the database
     * @pre name is not null and not empty string or all blanks
     */
    @Override
    public boolean containsName(String name) {
        return get(name) != null;
    }

    private Employee retrieve(Node root, String name) {

        if (root == null) {
            return null;
        } else if (name.compareTo(root.data.getName()) == 0){
            //System.out.println(":"+root.data.getName());
            return root.data;
        } else if (name.compareTo(root.data.getName()) > 0){
            System.out.println("Visted:"+root.data.getName());
            return retrieve(root.right, name);
        } else if (name.compareTo(root.data.getName()) < 0) {
            System.out.println("Visted:"+root.data.getName());
            return retrieve(root.left, name);
        }

        return null; // not really


        //return null; // not really

        // to do


    }





    /**
     * Returns a Employee object mapped to the supplied name.
     *
     * @param name The Employee name (key) to locate
     * @return the Employee object mapped to the key name if the name
     * exists as key in the database, otherwise null
     * @pre name not null and not empty string or all blanks
     */
    @Override
    public Employee get(String name) {
        // assert statements here
        //assert root!=null;

        return retrieve(root, name);
    }

    /**
     * Returns the number of members in the database
     *
     * @return number of members in the database.
     * @pre true
     */
    @Override
    public int size() {
        return numEntries;
    }

    /**
     * Determines if the database is empty or not.
     *
     * @return true iff the database is empty
     * @pre true
     */
    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    private Node insert(Node root, Employee employee) {

        //if (root!=null && three_depth==0){
            //System.out.println("Node is parent:"+root.data.getName());

        //}

        if (root == null){

            root = new Node(employee);

            if (three_depth==0){
                three_depth+=1;
                //System.out.println("Node is parent:"+root.data.getName());
                System.out.println("Node is parent:"+employee.getName());

            }

        }





        else if (employee.getName().compareTo(root.data.getName()) > 0){

            three_depth+=1;

            //System.out.println("Visted:"+root.data.getName());
            System.out.println("right:"+employee.getName());

            root.right = insert(root.right, employee);






            return root;
        } else if (employee.getName().compareTo(root.data.getName()) < 0) {
            three_depth+=1;

            //System.out.println("Visted:"+root.data.getName());

            System.out.println("left:"+employee.getName());


            root.left = insert(root.left, employee);





            return root;

        }


        else if (employee.getName().compareTo(root.data.getName()) == 0) {
            System.out.println(employee.getName() + " already exists and is now overriden");
        }
        return root;
    }

    /**
     * Inserts an Employee object into the database, with the key of the supplied
     * member's name.
     * Note: If the name already exists as a key, then then the original entry
     * is overwritten.
     * This method must return the previous associated value
     * if one exists, otherwise null
     *
     * @pre member not null and member name not empty string or all blanks
     */
    @Override
    public Employee put(Employee member) {
        Employee returned;
        returned = null; // for now
        root = insert(root, member);

        //System.out.println("Employee name:"+ member.getName());



        return  null;
    }

    /**
     * Removes and returns a member from the database, with the key
     * the supplied name.
     *
     * @param name The name (key) to remove.
     * @return the removed member object mapped to the name, or null if
     * the name does not exist.
     * @pre name not null and name not empty string or all blanks
     */
    @Override
    public Employee remove(String name) {
    /* based on Object-Oriented Programming in Oberon-2
       Hanspeter Mössenböck Springer-Verlag 1993, page 78
       transcribed into Java by David Lightfoot
    */
        Node parent = null, del, p = null, q = null;
        Employee result;
        del = root;
        while (del != null && !del.data.getName().equals(name)) {
            parent = del;
            if (name.compareTo(del.data.getName()) < 0) {
                //System.out.println(del.data.getName());
                System.out.println(del.data.getName() + "visted");
                del = del.left;

            }
            else {
                System.out.println(del.data.getName() + "visted");
                del = del.right;
            }
        }// del == null || del.data.getName().equals(name))
        if (del != null) { // del.data.getName().equals(name)
            // find the pointer p to the node to replace del
            if (del.right == null) p = del.left;
            else if (del.right.left == null) {
                p = del.right;
                p.left = del.left;
            } else {
                p = del.right;
                while (p.left != null) {
                    q = p;
                    p = p.left;
                }
                q.left = p.right;
                p.left = del.left;
                p.right = del.right;
            }
            if (del == root) root = p;
            else if (del.data.getName().compareTo(parent.data.getName()) < 0)
                parent.left = p;
            else parent.right = p;
            numEntries--;
            result = del.data;
        } else result = null;
        return result;
    } // delete

    private void traverse(Node tree) { //inOrder
        if (tree == null) {
            return;
        }

        traverse(tree.left);
        System.out.println(tree.data);
        traverse(tree.right);


        // to do

    }

    /**
     * Prints the names and affiliations of all the members in the database in
     * alphabetic order.
     *
     * @pre true
     */
    @Override
    public void displayDB() {
        traverse(root);
    }

    public static void main(String[] args) {


        //test data [c , f, a, d, e,b]

        //check_deletion();
        StaffBST ts2= init_data(false);
        Map<String, String> map = new HashMap<String, String>();
        ts2.travel2(root,map);
        System.out.println(map);
        //System.out.println(ts2.travel2(root,map));
















    }



    public static  void  pop(StaffBST tree, String[] lst){
        for (String name : lst) {

            Employee nw_employee=  new Employee(name,"x");
            tree.put(nw_employee);



        }
    }

    public static  void  pop2(StaffBST tree, List<String> lst){
        for (String name : lst) {

            Employee nw_employee=  new Employee(name,"x");
            tree.put(nw_employee);



        }
    }




    public  static  StaffBST init_data(boolean dis){
        String[] test_data = {"c" , "f", "a", "d", "e","b"};

        if(dis){
            System.out.println("This is the test data:");
            System.out.println(Arrays.toString(test_data));

        }



        StaffBST testTree = new StaffBST();

        pop(testTree,test_data);


        return  testTree;

    }



    public  static  void  check_deletion(){
        String[] test_data = {"c" , "f", "a", "d", "e","b"};
        Map<String, String> map = new HashMap<String, String>();




         StaffBST Testree =  init_data(true);
         StaffBST Testree_copy =  init_data(false);






         System.out.println("Deletion test function");
        for( String element: test_data){
            List<String> cop = new ArrayList<>();



            Testree.travel(root,cop);
            System.out.println("before deletion :");
            System.out.println(cop);

            Testree.remove(element);


            cop.clear(); ////
            Testree.travel(root,cop);
            System.out.println("after deletion:"+" name:"+element +" removed");


            System.out.println(cop);

            List<String> al = new ArrayList<>();




            //check wether all non deleted items are present.
            Testree_copy.travel(root,al);

            for( String el :  al){
                if(!cop.contains(el)){
                    System.out.println("Something went wrong,not all non-deleted items are present");
                    present=false;
                    break;

                }



            }









        }


        if(present){
            System.out.println("all non-deleted items are present");
        }













         //check deletion one node





    }

    public  void travel(Node tree,List<String> lst) { //inOrder
        if (tree == null) {
            return;
        }

        travel(tree.left,lst);

        System.out.println(tree.data);
        lst.add(tree.data.getName());
        travel(tree.right,lst);


        // to do

    } //name key , value :left or right

    public void travel2(Node tree, Map<String, String> map) { //inOrder
        if (tree == null) {
            return ;
        }

        Node a=tree.left;
        Node b =tree.right;


        while (true){


            if(tree.left !=null){
                map.put(tree.data.getName(),"left");
                tree.left= a.left;

            }





            if(tree.right !=null){
                map.put(tree.data.getName(),"right");
                tree.right= b.right;

            }
            if(tree.right==null & tree.left==null){
                break;
            }








        }




        //System.out.println(tree.data);



    }





        // to do




}