CS310 Tree, Array, and List

Tree Dictionary

Many data (e.g, records of movies, songs, video games, etc) come with keywords so these data can be eaily found using keywords. You are tasked to implement a binary tree structure that allows querys composed of one or multiple keywords. For example, you can find pokemons using their attacts as illustrated below.

Welcome to CS310 PA02: Tree Dictionary
Read 124 records from json/pokemon.json
Options:
f: find records
p: print the tree
q: quit
> f
> Provide keywords (seprate by ,): thundershock, spark
> Found 2 records
> ... [Magnemite, (tackle, thundershock, spark)]
> ... [Magneton, (tackle, thundershock, spark, zap cannon)]

Introduction and Definitions

The following code is provided to you. There are five java files: PA02.java, DynamicArray.java, LinkedList.java, Record.java, and TreeDictionary.java.

Note, we use an external library called json-simple-1.1.1.jar. Therefore, to compile the code from command line, you need:

javac -cp .:json-simple-1.1.1.jar PA02.java

To run the code, you need:

java -cp .:json-simple-1.1.1.jar PA02 -name name -keyword moves -max 10 json/pokemon.json

A script, called "run", is provided to help you compile and run the examples.

Tasks

Coding

These are the only files you should modify to finish the code. You are recommended to finish them in the given order below.

• DynamicArray.java
• LinkedList.java,
• TreeDictionary.java

Complete README.txt

You should complete the provided README.txt and submit it with the rest of the code.

DynamicArray.java

import java.util.Iterator;

//
// Complete this class
//
public class DynamicArray< t > implements Iterable< t > {

public static void main(String[] args) {
}

public DynamicArray() {
}

public void insert(T data) {
}

public T get(int index) {
}

public int size() {
}

void delete() {
}

void delete(int index) {
}

boolean is_empty() {
}

public Iterator< t > iterator() {
}

//Note: You will need to implement an iterator class using java.util.Iterator
// interface
//TO DO: implement iterator here
}

LinkedList.java

import java.util.Iterator;

//
// Complete this class:
//
public class LinkedList< T > implements Iterable< T > {

public static void main(String[] args) {
}

public LinkedList(T[] A) {
}

public void insert(T data) {
}

private void delete(Node< T > n) {
}

public boolean is_empty() {
}

public Iterator< T > iterator() {
}

//Note: You will need to implement an iterator class using java.util.Iterator
// interface

// ----------------------------------------------------------------------
//
// !!! READ but Do NOT Change anything after this line
//
// ----------------------------------------------------------------------
private class Node< T > {

Node() {
}

Node(T data) {
this.data = data;
}
public T data;
public Node< T > next;
public Node< T > prev; //for doubly linked list
}

Node< T > head; //pointing to the location BEFORER the first element
Node< T > tail; //for doubly linked list
//pointing to the location AFTER the last element

public LinkedList() //constructor
{
head = new Node< T >();
tail = new Node< T >();
head.next = tail;
tail.prev = head;
}

public T last() {
//nothing to return
if (head.next == tail) {
return null;
}
return tail.prev.data;
}

public String toString() {
String S = "(";
for (T t : this) {
S = S + t + ", ";
}
if (is_empty() == false) {
S = S.substring(0, S.length() - 2);
}
S = S + ")";
return S;
}
}

TreeDictionary.java

//
// Complete this class:
// TreeDictionary implements the (self-balance) binary search tree as a Dictionary
//
public class TreeDictionary< T extends Comparable< T > > {

public static void main(String[] args) {
}

public void insert(Record< T > record)
{
//insert this records into the tree based on its keywords

//1. for each keyword in this record, find the node that contains this keyword
//2. if no such node exists, create a new node and assign the keyword
//3. insert the record into the node
//4. repeat until all keywords in the record are processed
//(bonus: implement AVL insertion that balances the tree)
}

public DynamicArray< Record< T > > find(LinkedList< T > keywords) {
}


private TreeDictionary< T > correct_find_then_build(T keyword) {
}

// ----------------------------------------------------------------------
//
// !!! READ but Do NOT Change anything after this line
//
// ----------------------------------------------------------------------
private class Node< T > {

Node() {
records = new DynamicArray< Record< T > >();
}

Node(T k) {
keyword = k;
records = new DynamicArray< Record< T > >();
}

T keyword; //nodes are ordered by Keywords
Node< T > parent;
Node< T > left, right; //children
DynamicArray< Record< T > > records;

public String toString() {
return "[" + keyword + " (" + records.size() + ")]";
}
}

private Node< T > root; //root of the tree, can be null

//build this tree by inserting the records
public void build(DynamicArray< Record< T > > records) {
for (Record< T > r : records) {
insert(r);
}
}

//find a node that contains the given keyword and then
//build a tree using the records stored in the found node
//finally return the tree
private TreeDictionary< T > find_then_build(T keyword) {
//
//use keyword to find the node
Node< T > node = find(keyword);

if (node == null) {
return null;
}

//
//build the tree from this node's record
TreeDictionary< T > newT = new TreeDictionary< T >();
newT.build(node.records);

//
//remove the keyword from the Tree
newT.remove(keyword);

//done
return newT;
}

public String toString() {
//list all the keyworkds and number of records for each keyword
//visit all nodes in In-Order traversal.
LinkedList< Node< T > > nodes = InOrderTraversal();
String S = "Tree Dictionary: {";
for (Node< T > node : nodes) {
S += node.toString() + ", ";
}
if (!nodes.is_empty()) {
S = S.substring(0, S.length() - 2);
}
S += "}";
return S;
}
}