<file_sep>import java.util.regex.Matcher;
import java.util.regex.Pattern;

/*****************************************************
 * 
 * 95-772 Data Structures for Application Programmers
 * 
 * Homework 1 My Array implementation
 * 
 * Name: <NAME> 
 * ID: jiaqiluo
 * 
 * Description:
 * 		handling array list problem, such as enlarge 
 * the array, add element, remove element, get size and
 * so on.
 * 
 *****************************************************/
public class MyArray {

	private int capacity;
	private String[] array;

	public MyArray(int length) {

		this.capacity = length;
		array = new String[this.capacity];

	}

	public int size() {
		int count = 0;
		for (int i = 0; i < this.capacity; i++) {
			if (array[i] != null)
				count++;
			else
				break;
		}
		return count;

	}

	public int getCapacity() {
		return this.capacity;
	}
	
	
	// if the string is not a character word, we should neglect it
	public void add(String string) {
		Pattern p = Pattern.compile("[a-zA-Z]");
		Matcher m = p.matcher(string);

		if (m.find() && !string.contains("_")) {

			int size = this.size();
			if (size == this.capacity) {
				if (this.capacity == 0)
					this.capacity = 1;
				else
					this.capacity = 2 * this.capacity;
				String[] newArray = new String[this.capacity];
				System.arraycopy(array, 0, newArray, 0, size);
				array = newArray;
			}
			array[size] = string;

		}
	}

	public boolean search(String string) {
		for (int i = 0; i < this.size(); i++) {
			if (array[i].equals(string))
				return true;
		} 
		return false; 
	}

	public void display() {
		for (int i = 0; i < this.size(); i++)
			System.out.print(array[i] + " ");
		System.out.print("\n");
	}

	// give another empty array, search the old array,
	// if it is a new word, add it to the new array.
	public void removeDups() {
		String[] tempArray = new String[this.size()];
		tempArray[0] = array[0];

		for (int i = 1; i < this.size(); i++) {
			int size = arrayGetSize(tempArray);
			tempArray[size] = array[i];

			for (int k = 0; k < size; k++) {
				if (array[i].equals(tempArray[k])) {
					tempArray[size] = null;
					break;
				}
			}
		}
		array = tempArray;
	}

	// basically use for the removeDups(). 
	// it can return the size of an array.
	private int arrayGetSize(String[] array) {
		int count = 0;
		while (array[count] != null)
			count++;
		return count;
	}

}
<file_sep>package hw6;

/*****************************************************
 * 
 * 95-772 Data Structures for Application Programmers
 * 
 * Homework 6: Building Index using BST
 * 
 * Andrew ID: jiaqiluo
 * Name: <NAME>
 * 
 *****************************************************/
import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Index {

	/**
	 * Build a tree giving a file name
	 * 
	 * @param fileName
	 *            - input file name
	 * @return BST object
	 * @throws IOException
	 */
	public BST<Word> buildIndex(String fileName) throws IOException {
		if (fileName == null)
			return null;
		BST<Word> b = new BST<Word>();
		ArrayList<String> lines = new ArrayList<String>();
		String line;
		String[] words;
		BufferedReader br = new BufferedReader(new FileReader(fileName));
		while ((line = br.readLine()) != null) {
			lines.add(line);

		}

		for (int i = 0; i < lines.size(); i++) {
			line = lines.get(i);

			words = line.split("\\W");

			Pattern p = Pattern.compile("^[a-zA-Z]+$");
			for (int j = 0; j < words.length; j++) {
				Matcher m = p.matcher(words[j]);

				if (!words[j].equals(" ") && !words[j].contains("_")
						&& m.find()) {

					Word fileWord = new Word(words[j], i + 1);
					Word searchedWord = b.search(fileWord);
					if (searchedWord != null) {
						searchedWord.addFrequency();
						searchedWord.getSet().add(i + 1);
					} else {
						b.insert(fileWord);
					}

				}
			}
		}
		br.close();
		return b;

	}

	/**
	 * Build a tree with a file name and comparator object
	 * 
	 * @param fileName
	 *            - input file name
	 * @param comparator
	 *            - comparator to be used
	 * @return BST object
	 * @throws IOException
	 */
	public BST<Word> buildIndex(String fileName, Comparator<Word> comparator)
			throws IOException {
		if (fileName == null || comparator == null)
			return null;
		BST<Word> b = new BST<Word>();
		ArrayList<String> lines = new ArrayList<String>();
		String line;
		String[] words;

		BufferedReader br = new BufferedReader(new FileReader(fileName));
		while ((line = br.readLine()) != null) {
			lines.add(line);

		}

		for (int i = 0; i < lines.size(); i++) {
			line = lines.get(i);
			if (comparator instanceof IgnoreCase) {
				line = line.toLowerCase();
			}
			words = line.split("\\W");

			Pattern p = Pattern.compile("^[a-zA-Z]+$");
			for (int j = 0; j < words.length; j++) {
				Matcher m = p.matcher(words[j]);

				if (!words[j].equals(" ") && !words[j].contains("_")
						&& m.find()) {

					Word fileWord = new Word(words[j], i + 1);
					Word searchedWord = b.search(fileWord);
					if (searchedWord != null) {
						searchedWord.addFrequency();
						searchedWord.getSet().add(i + 1);
					} else {
						b.insert(fileWord);
					}

				}
			}
		}
		br.close();
		return b;
	}

	/**
	 * Build a tree with a given list and comparator
	 * 
	 * @param list
	 *            - ArrayList of words
	 * @param comparator
	 *            - comparator to be used
	 * @return BST object
	 */
	public BST<Word> buildIndex(ArrayList<Word> list,
			Comparator<Word> comparator) {
		if (list == null || comparator == null)
			return null;
		BST<Word> b = new BST<Word>();

		Word word;

		for (int i = 0; i < list.size(); i++) {
			word = list.get(i);
			if (comparator instanceof IgnoreCase) {
				word.setWord(word.getWord().toLowerCase());
			}

			b.insert(word);
		}

		return b;
	}

	/**
	 * Sort words alphabetically Note: Should keep the state of the tree
	 * 
	 * @param tree
	 *            - BST tree
	 * @return ArrayList of words sorted alphabetically
	 */
	public ArrayList<Word> sortByAlpha(BST<Word> tree) {
		if (tree == null)
			return null;
		ArrayList<Word> list = new ArrayList<Word>();
		Iterator<Word> ite = tree.iterator();
		Word word;
		while (ite.hasNext()) {
			word = ite.next();
			list.add(word);

		}
		Collections.sort(list);
		return list;
	}

	/**
	 * Sort words by frequency Note: Should keep the state of the tree
	 * 
	 * @param tree
	 *            - BST tree
	 * @return ArrayList of words sorted by frequency
	 */
	public ArrayList<Word> sortByFrequency(BST<Word> tree) {
		if (tree == null)
			return null;
		ArrayList<Word> list = new ArrayList<Word>();
		Iterator<Word> ite = tree.iterator();
		Word word;
		while (ite.hasNext()) {
			word = ite.next();
			list.add(word);

		}
		Collections.sort(list, new Frequency());
		return list;
	}

	/**
	 * Find all words of the highest frequency Note: Should keep the state of
	 * the tree
	 * 
	 * @param tree
	 *            - BST tree
	 * @return ArrayList of words that have highest frequency
	 */
	public ArrayList<Word> getHighestFrequency(BST<Word> tree) {
		if (tree == null)
			return null;
		ArrayList<Word> list = new ArrayList<Word>();
		ArrayList<Word> highestList = new ArrayList<Word>();
		Iterator<Word> ite = tree.iterator();
		Word word;
		int highestFreq;
		while (ite.hasNext()) {
			word = ite.next();
			list.add(word);

		}
		Collections.sort(list, new Frequency());

		highestFreq = list.get(0).getFrequency();
		for (Word aWord : list) {
			if (aWord.getFrequency() < highestFreq)
				break;
			highestList.add(aWord);

		}
		return highestList;
	}

}