ok
ss
unknown
plain_text
3 years ago
11 kB
12
Indexable
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
}Editor is loading...