******I need help with my project. Here's the specs**********
CS123 MP2
Database Table
On Load of the program it will read all files and put its data to the memory.
a. Data file - this must be in CVS (Comma Separated Values). The first line
is a header that contains the field names.
b. Index File(s) - I leave it up to you how you will store the AVL into a
file. Remember that you need to create the AVL from the file when the program
is first started.
Note : Windows and Linux have different file separator character. Your program
must be able to run on both Windows and Linux. Use the File.separator.The program must be able to do the following
a. Add a record
b. Update a record
c. Delete a record
Note: I leave it up to you how the program will ask for field values. In the
case of update and delete where you need to know which record to update or
delete. The program should ask for an int value, which corresponds on the
position of the record on the file.
e. Search a record - User may specify any number of search criterias, joined
or or and. Note that and will always take precedence over or. Suppose the
following search criteria is formed, S1 and S2 or S3 or S4 and S5, then this
is the order of performing the search. (S1 and S2) or S3 or (S4 and S5). A
search criteria is made up of the following. a Field, an operator (=, >, >=, <, <=)
and the Field value. I leave it up to you how you will ask the user.
f. Create an index on a field - creates an AVL Tree on the values of on all
of the records on the specified field. Note that an index changes how the
whole data base works. If a record is added or deleted, the index must also
be updated to reflect the addition or the loss of the record. If the record
is updated, you need to perform a delete then an add on the AVL Tree. The
existence of an index field, should change the way you search for records.
If the index is available, you need to use it.
g. Drop an index on a field - removes the index in memory.
h. Save Changes unto a file (or files as needed).Program must keep on running until the user chooses to exit the program.
Additional notes:
Use the HashMap or Hashtable as your record. An ArrayList containing your
records (HashMap) will serve as your in memory data structure to keep track
of all the records.
To avoid confusion I will call the record index as (RI) and the indexes on the
field as Field Index (FI).
The RI will serve as the index to your array list for easy access. In your
FI you need to store the RI's along side the Field value.
For example I have the following records.
FirstName,LastName,StdNo
Jose Marciano,Patino,99-60088
Benjamin,Herrera,99-12564
Che Ann,Alib,99-78945
Erik,Bulatao,99-01011
And I have an FI on LastName,
the AVL will look as such:
Herrera (1)
/ \
Alib(2) Patino (0)
\
Bulatao(3)
Note that rotations have been performed on the AVL already to keep it balanced.
This means if i have to search "Bulatao" I just traverse the AVL. Retreive
the index (which is 3) then use it to access the ArrayList. Do not allow
duplicates on your AVL instead you just add the RI to the node
Suppose I will add the record:
Juan Bernardo,Patino,05-54236
The AVL will look as such:
Herrera (1)
/ \
Alib(2) Patino (0, 5)
\
Bulatao(3)
Some other things to consider. Notice that all if you delete a records from
the ArrayList it performs shift on the array. Meaning the RI's on the AVL
needs to be updated. Also note that Suppose I am to delete record 5. The AVL
should not automatically delete the node containing "Patino" since the it
still has an RI.
You need to delete only the RI on the node, once you have deleted all RI's on
the node then that is the time that you will proceed with the removal of
the node. This should also be the case for update.
Things to consider when searching.
Suppose my search criteria is LastName <= Herrera. I first traverse the AVL
to Herrera node, then create a set containing all the RI's on the left Sub
tree of Herrera node and all the RI's on the Herrera node (since = is also
specified).
The harder question is actually what if Herrera does not exist on the AVL?
I leave that question for you to answer. Good luck on your MP.
******Here's what I've done so far..*************
>>>>>>>>>>>>>>>>>Class DBRecord<<<<<<<<<<<<<<<<<<
import java.util.*;
public class DBRecord {
public HashMap<String, String> hashMap;
public ArrayList<String> dbHeaders;
//constructor
public DBRecord(ArrayList<String> headers, String[] values){
hashMap =new HashMap<String, String>();
for(int i=0; i<headers.size(); i++){
hashMap.put(headers.get(i), values[i]);
}
this.dbHeaders = headers;
}
//get field value from hashMap
public String get(String field){
return hashMap.get(field);
}
//put fields as keys and values as field values into hashMap
public void put(String fields, String values){
hashMap.put(fields, values);
}
public String toString(){
String string = "";
for(int i = 0; i <dbHeaders.size(); i++){
if(i == 0)
string += hashMap.get(dbHeaders.get(i));
else
string += ", " + hashMap.get(dbHeaders.get(i));
}
return string;
}
}
>>>>>>>>>>>>>>>>>Class DBTable<<<<<<<<<<<<<<<<<<
import java.io.*;
import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class DBTable {
private JFrame frame;
private JPanel panel1,panel2, panel3;
private JTextField fields;
private JLabel labels;
private JButton ok, reset, back;
public static ArrayList<String> dbHeaders;
public static ArrayList<DBRecord> dbTable;
public ArrayList<Integer> popList1, popList2;
public static DBRecord record;
static String[] values;
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
//constructor
public DBTable(ArrayList<String> headers){
dbTable = new ArrayList<DBRecord>();
dbHeaders = headers;
}
//returns size of dbTable
public int size() {
return dbTable.size();
}
//returns list of fields
public ArrayList<String> getField(){
return dbHeaders;
}
//adds a record into dbTable
public void add(DBRecord record){
dbTable.add(record);
}
public DBRecord get(int index){
return dbTable.get(index);
}
//prints contents of text file
public void printRecord(){
//System.out.println("*********************************************");
//System.out.println("Printing Records..");
//System.out.println();
for(int i=0; i<dbHeaders.size();i++){
JOptionPane.showMessageDialog(null,dbHeaders.get(i)+", ");
}
//System.out.println();
for(int j=0; j<dbTable.size();j++){
JOptionPane.showMessageDialog(null, dbTable.get(j));
}
}
// adds a new record into dbTable
public void addRecord()throws IOException{
int n = dbHeaders.size();
values = new String[dbHeaders.size()];
frame=new JFrame("Add new record");
frame.setLayout(new FlowLayout());
frame.setSize(400,200);
frame.setVisible(true);
panel1=new JPanel();
panel1.setLayout(new GridLayout(n,1,4,4));
String[] temp=new String[dbHeaders.size()];
//String line="";
for(int i=0; i<dbHeaders.size();i++){
labels=new JLabel("Please enter "+dbHeaders.get(i)+": ");
fields=new JTextField(15);
panel1.add(labels);
panel1.add(fields);
frame.add(panel1);
//line=JOptionPane.showInputDialog("Please enter "+dbHeaders.get(i)+": ");
}
panel2=new JPanel();
panel2.setLayout(new FlowLayout());
ok=new JButton("OK");
panel2.add(ok);
ok.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent event){
for(int i=0; i<dbHeaders.size();i++){
values[i]= fields.getText();
System.out.println("fields: "+values[i]);
}
record = new DBRecord(dbHeaders, values);
dbTable.add(record);
JOptionPane.showMessageDialog(null, "Record added.");
}
});
reset=new JButton("RESET");
panel2.add(reset);
panel3=new JPanel();
panel3.setLayout(new BorderLayout());
back=new JButton("Back to Main Menu");
panel3.add(back,BorderLayout.EAST);
back.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent event){
frame.setVisible(false);
}
});
frame.add(panel2);
frame.add(panel3,BorderLayout.EAST);
}
//searches record number (0 to n records) and deletes entire record
public void deleteRecord(){
String recIndex;
recIndex=JOptionPane.showInputDialog("Please enter record number: ");
int index = Integer.parseInt(recIndex);
if(index>dbTable.size()){
JOptionPane.showMessageDialog(null,"Index out of bounds!");
}else if(index<=dbTable.size()){
dbTable.remove(index);
}else{
JOptionPane.showMessageDialog(null,"Bad input!");
}
}
//updates record
public void updateRecord(){
try{
String recKey;
String newValue;
recKey=JOptionPane.showInputDialog("Enter record number: ");
int recordNumber = Integer.parseInt(recKey);
DBRecord record = dbTable.get(recordNumber);
String[] values = record.toString().split(",");
int choice= displayFieldMenu();
if(choice<=dbHeaders.size()){
newValue=JOptionPane.showInputDialog("Enter value to replace with "+values[choice]+":");
record.put(dbHeaders.get(choice), newValue);
}else{
JOptionPane.showMessageDialog(null, "Error! Bad input!");
}
}
catch(IOException io){
JOptionPane.showMessageDialog(null, "Bad input!");
}
catch(NullPointerException ne){
JOptionPane.showMessageDialog(null,"Null pointer exception!");
}
}
//searches for the particular record then searches for the particular field with conditions
public void searchRecord(){
try{
Object[] array;
Object[] popArray;
ArrayList<Integer> orList = new ArrayList<Integer>();
Stack stack = getConditions();
while(stack.size()!=1){
popList1 = (ArrayList<Integer>)stack.pop();
popList2 = (ArrayList<Integer>)stack.pop();
orList = implementOR(popList1,popList2);
stack.push(orList);
}
popList1 = (ArrayList<Integer>)stack.pop();
for(int i=0; i<popList1.size();i++){
System.out.println("popList1: "+popList1.get(i));
}
//popArray =popList1.toArray();
//array = removedElementsArray(popArray);
for(int i=0; i<popList1.size(); i++){
int index= (Integer)popList1.get(i);
System.out.println(dbTable.get(index));
}
}
catch(IOException io){
System.err.println("Bad input!");
}
}
//asks user for a search criteria made up of a field, an operator and a fieldvalue
//returns an arraylist of indices of records in the dbTable
public ArrayList<Integer> getCriteria(Stack aStack)throws IOException{
String operator;
String fieldValue;
ArrayList<Integer> intList = new ArrayList<Integer>();
int choice=displayFieldMenu();
String field=dbHeaders.get(choice);
operator=JOptionPane.showInputDialog("Enter operator: ");
//String operator = input.readLine();
fieldValue=JOptionPane.showInputDialog("Enter field value: ");
//String fieldValue=input.readLine();
intList=getComparison(field, operator, fieldValue);
/*for(int i=0; i<intList.size();i++){
System.out.println("intList: "+intList.get(i));
}*/
return intList;
}
//displays menu of fields
public int displayFieldMenu() throws IOException{
int choice=0;
String fieldNum;
try{
for(int i=0; i<dbHeaders.size();i++){
System.out.println("["+i+"]"+ dbHeaders.get(i));
}
fieldNum=JOptionPane.showInputDialog("Enter field number: ");
choice= Integer.parseInt(fieldNum);
}catch(NumberFormatException ne){
JOptionPane.showMessageDialog(null,"Bad input!","Warning!Error!",JOptionPane.ERROR_MESSAGE);
displayFieldMenu();
}
return choice;
}
//compares field values and returns a list of the indices matching the criteria
public ArrayList<Integer> getComparison(String field, String operator, String fieldValue){
ArrayList<Integer> indexSet = new ArrayList<Integer>();
if(operator.equals("=")){//equals
for(int i=0; i<dbTable.size();i++){
if(dbTable.get(i).get(field).equals(fieldValue))
indexSet.add(i);
}
}else if(operator.equals(">") || operator.equals(">=")){
//greater than or greater than or equal to
for(int i=0; i<dbTable.size();i++){
if((dbTable.get(i).get(field).compareTo(fieldValue))>0 ||
(dbTable.get(i).get(field).compareTo(fieldValue))>=0){
indexSet.add(i);
}
}
}else if(operator.equals("<")||operator.equals("<=")){
//less than or less than or equal to
for(int i=0; i<dbTable.size();i++){
if((dbTable.get(i).get(field).compareTo(fieldValue))<0||
(dbTable.get(i).get(field).compareTo(fieldValue))<=0){
indexSet.add(i);
}
}
}
for(int i=0; i<indexSet.size();i++){
System.out.println("indexSet: "+indexSet.get(i));
}
return indexSet;
}
public Stack<ArrayList<Integer>> getConditions()throws IOException{
String condition="";
Stack stack = new Stack<ArrayList<Integer>>();
ArrayList<Integer> criteria=new ArrayList<Integer>();
criteria=getCriteria(stack);
for(int i=0; i<criteria.size();i++){
System.out.println("criteria list: "+criteria.get(i));
}
stack.push(criteria);
while(true){
String input;
int choice;
input=JOptionPane.showInputDialog("Enter a condition: ([1]=OR, [2]=AND, [3]=END): ");
//System.out.println("[1]OR");
//System.out.println("[2]AND");
//System.out.println("[3]END");
choice = Integer.parseInt(input);
if(choice==1){//perform OR condition
stack.push(getCriteria(stack));
}else if(choice==2){//perform AND condition
stack.push(getCriteria(stack));
popList1 = (ArrayList<Integer>)stack.pop();
popList2 = (ArrayList<Integer>)stack.pop();
stack.push(implementAND(popList1, popList2));
}else{
break;
}
}
return stack;
}
public ArrayList<Integer> implementOR(ArrayList<Integer>a, ArrayList<Integer>b){
int count = 0;
int size = b.size();
while(count != size){
a.add(b.get(count));
count++;
}
for(int i=0; i<a.size();i++){
System.out.println("implementOR: "+a.get(i));
}
return a;
}
public ArrayList<Integer> implementAND(ArrayList<Integer>a, ArrayList<Integer>b){
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
if(a.get(i).equals(b.get(j)))
list.add(a.get(i));
}
}
for(int i=0; i<list.size();i++){
System.out.println("implementAND: "+list.get(i));
}
return list;
}
public Object[] removedElementsArray(Object[] aList){
/*Object[] removeElement = new Object[array.length];
int counter=0;
int k=0;
for(int i=0; i<array.length;i++){
for(int j=1;j<array.length;j++){
if(array[i].toString().equals(array[j].toString())){
counter++;
}
}
if(counter==0){
removeElement[k]=array[i];
k++;
}
}
return removeElement;*/
Object[] removed = new Object[aList.length];
int i = 0, j = 1, index = 0;
while(i != aList.length){
int ctr = 0;
while( j != aList.length){
if(aList[i].toString().equals(aList[j].toString()))
ctr++;
j++;
}
if(ctr == 0){
removed[index] = aList[i];
index++;
}
i++;
j = i+1;
}
for(int x=0; x<removed.length;x++){
System.out.println("remove duplicates: "+removed[x]);
}
return removed;
}
//save changes into a new file
public void saveChanges(){
String filename;
try{
filename=JOptionPane.showInputDialog("Enter filename: ");
PrintWriter output = new PrintWriter(new FileOutputStream(filename,true));
for(int count=0;count<dbTable.size();count++){
output.println(dbTable.get(count));
}
output.flush();
}
catch(FileNotFoundException fe){
JOptionPane.showMessageDialog(null, "Error opening file!");
System.exit(0);
}
JOptionPane.showMessageDialog(null,"Saved changes.");
}
public void createAVL(){
try{
String delRec;
AVLTree tree=new AVLTree();
int choice=displayFieldMenu();
String string = dbHeaders.get(choice);
for(int i=0; i<dbTable.size();i++){
//System.out.println(dbTable.get(i).get(string));
tree.insert(new TreeNode(dbTable.get(i).get(string),i));
tree.updateBalanceFactor(tree.getRoot());
tree.balance(tree.getRoot());
}
System.out.println("inorder tree: "+tree.inorder(tree.getRoot()));
System.out.println(tree);
System.out.println("Enter record number to delete:");
delRec=input.readLine();
int index=Integer.parseInt(delRec);
String str2=dbHeaders.get(index);
for(int j=0; j<dbTable.size();j++){
System.out.println(dbTable.get(j).get(string));
}
tree.delete(new TreeNode(dbTable.get(index).get(str2),index));
for(int j=0; j<dbTable.size();j++){
System.out.println(dbTable.get(j).get(string));
}
//System.out.println(dbTable);
}
catch(IOException io){
System.err.println("bad input");
}
}
}
>>>>>>>>>>>>>>>>>Class TreeNode<<<<<<<<<<<<<<<<<<
public class TreeNode {
protected String key;
protected int balanceFactor, recordNum;
protected TreeNode left, right,parent;
public TreeNode(String aKey, int recordNum){
key=aKey;
this.recordNum=recordNum;
left=right=null;
}
public TreeNode(){
key = "";
balanceFactor = 0;
right = left = parent = null;
}
/*public TreeNode(String element, TreeNode left, TreeNode right){
key=element;
this.left=left;
this.right=right;
}*/
public void setKey(String aKey){
key=aKey;
}
public String getKey(){
return key;
}
public void setLeft(TreeNode leftNode){
left=leftNode;
}
public TreeNode getLeft(){
return left;
}
public void setRight(TreeNode rightNode){
right=rightNode;
}
public TreeNode getRight(){
return right;
}
public void setParent(TreeNode parentNode){
parent=parentNode;
}
public TreeNode getParent(){
return parent;
}
public void setBalanceFactor(int aBalanceFactor){
balanceFactor=aBalanceFactor;
}
public int getBalanceFactor(){
return balanceFactor;
}
}
>>>>>>>>>>>>>>>>>Class AVLTree<<<<<<<<<<<<<<<<<<
public class AVLTree {
protected TreeNode root,parent;
private String string;
public AVLTree(){
root=null;
}
public TreeNode getRoot(){
return root;
}
//inserts node into the tree
public void insert(TreeNode aNode){
TreeNode p=root;
while(p!=null){
parent=p;
if(p.getKey().compareTo(aNode.getKey())<0)
p=p.getRight();
else
p=p.getLeft();
}
if(isEmpty())
root=aNode;
else if(parent.getKey().compareTo(aNode.getKey())<0){
parent.setRight(aNode);
aNode.setParent(parent.getRight());
}
else{
parent.setLeft(aNode);
aNode.setParent(parent.getLeft());
}
System.out.println(aNode.getKey());
}
public String inorder(TreeNode p){
if(p!=null){
inorder(p.getLeft());
string+=visit(p);
inorder(p.getRight());
}
return string;
}
public TreeNode search(TreeNode aNode){
TreeNode p=root;
while(aNode!=null){
if(aNode.getKey().equals(p.getKey()))
return aNode;
else if(aNode.getKey().compareTo(p.getKey())<0)
p=p.getLeft();
else
p=p.getRight();
}
System.out.println("Node not found!");
return null;
}
public void delete(TreeNode aNode){
TreeNode node, p=root;
node=search(aNode);
if(p!=null && (p.getKey().equals(aNode.getKey()))){
if(node.getRight()==null)
node=node.getLeft();
else if(node.getLeft()==null)
node=node.getRight();
else{
TreeNode tmp=node.getLeft();
TreeNode previous =node;
while(tmp.getRight()!=null){
previous=tmp;
tmp=tmp.getRight();
}
node.setKey(tmp.getKey());
if(previous==node)
previous.setLeft(tmp.getLeft());
else
previous.setRight(tmp.getLeft());
}
if(p==root)
root=node;
else if(parent.getLeft()==p)
parent.setLeft(node);
else
parent.setRight(node);;
}
else if(root!=null)
System.out.println("key"+aNode.getKey()+" is not in the tree");
else
System.out.println("the tree is empty!");
}
/*public void swap(TreeNode a, TreeNode b){
String temp = a.getKey();
a.setKey(b.getKey());
b.setKey(temp);
}*/
public int getHeight(){
return getHeight(getRoot(), 0);
}
public int getHeight(TreeNode p, int currentHeight){
if(p == null)
return currentHeight;
return max(getHeight(p.getLeft(), currentHeight ), getHeight(p.getRight(), currentHeight));
}
public int max(int aValue, int bValue){
return aValue > bValue ? aValue : bValue;
}
public void updateBalanceFactor(TreeNode p){
if(isEmpty())
System.out.println("Tree is Empty!");
else if(p != null){
p.setBalanceFactor(getHeight(p.getLeft(),0) - getHeight(p.getRight(), 0));
updateBalanceFactor(p.getLeft());
updateBalanceFactor(p.getRight());
}
}
public void balance(TreeNode aNode){
if(isEmpty())
System.out.println("Tree is Empty!");
if(aNode != null && aNode.getBalanceFactor() == -2){
if(aNode.getRight().getBalanceFactor() == -1){
if(aNode == root)
root = aNode.getRight();
else{
aNode.getRight().setParent(aNode.getParent());
aNode.getParent().setLeft(aNode.getRight());
}if(aNode.getRight() != null){
aNode.setParent(aNode.getRight());
aNode.getRight().setLeft(aNode);
}else{
aNode.setParent(aNode.getRight().getLeft());
aNode.getRight().getLeft().setLeft(aNode);
}
aNode.setRight(null);
}
updateBalanceFactor(getRoot());
}else if(aNode != null && aNode.getBalanceFactor() == 2){
if(aNode.getLeft().getBalanceFactor() == 1){
if(aNode == root)
root = aNode.getLeft();
else{
aNode.getParent().setLeft(aNode.getLeft());
aNode.getLeft().setParent(aNode.getParent());
}
aNode.getLeft().setRight(aNode);
aNode.setParent(aNode.getLeft());
aNode.setLeft(null);
}
updateBalanceFactor(getRoot());
}
if(aNode != null){
balance(aNode.getLeft());
balance(aNode.getRight());
}
}
protected String visit(TreeNode p){
return p.getKey() + " " + p.getBalanceFactor() + "\n";
}
public boolean isEmpty(){
return root == null;
}
}
I'm stuck with the search and creating an AVL tree part coz I really don't
know what to do with it... please help...