I currently have 2 tries one stores names and one stores ID numbers, anywhere from 5,000 to 300,000 depending on how the user runs the program. It works efficiently when I compare either types of data. So my problem:
These names and numbers are parts of a custom class I wrote, and I need to be able to access the additional node information from comparison with the trie.
For example, a "Record" contains an ID number, first, middle, and last name, job organization and position, a boolean value, state of residence, and couple more int values. The (first name + last name) or (ID number) chars are nodes in the tries.
One comparison list has other "Records" in it to be compared by (first name + last name).
The other comparison list has "Records" to compare by (ID number).
I need to be able to change the fields of the "Records" in the tries if a match is found in a respective comparison list.
I need an edit or suggestion of a different data structure so that I can access the rest of the key's Record that's in the trie. I've done extensive research on other data structures, and I've tried an implementation of an AVL Tree without optimal success. Is there a way to store a HashTable or HashMap within the trie? I've looked at HAT Tries and I'm unsure of how to implement or if it's what I'm looking for.
Here is code for the Record class:
public class Record { //the is the general record form, all records imported are put in this form
public int cnum; //constituent number
public String nm;
public String fn; //first name
public String ln; //last name
public String mn; //middle name
public String maid; //maiden name
public String su; //suffix
public boolean FOTL; //front of the line status
public String state; //state
public String jobOrg; //job organization
public String jobPos; //job position
public int fblikes; //facebook likes
public int fbcom; //facebook comments
public Record(int cnum, String nm, String fn, String ln, String mn, String maid, String su, boolean FOTL, String state,
String jobOrg, String jobPos, boolean fb, int fblikes, int fbcom) { //full class declaration
this.cnum = cnum;
this.nm = nm;
this.fn = fn;
this.ln = ln;
this.mn = mn;
this.maid = maid;
this.su = su;
this.FOTL = FOTL;
this.state = state;
this.jobOrg = jobOrg;
this.jobPos = jobPos;
this.fblikes = fblikes;
this.fbcom = fbcom;
}
//getters and setters for class members are included, but not seen
Here is code for Trie that compares by ID or Cnum:
class ReTrieNode {
ReTrieNode[] arr;
boolean isEnd;
public ReTrieNode() {
this.arr = new ReTrieNode[10];
}
}
public class ReTrie {
private ReTrieNode root;
public Record w;
public ReTrie() {
root = new ReTrieNode();
}
public void insert(Record word) {
try {
w = word;
ReTrieNode p = root;
String con = Integer.toString(w.getCnum());
for (int i = 0; i < con.length(); i++){
char c = con.charAt(i);
int index = c-'0';
if (p.arr[index] == null) {
ReTrieNode temp = new ReTrieNode();
p.arr[index] = temp;
p = temp;
}
else {
p = p.arr[index];
}
}
p.isEnd=true;
}
catch (ArrayIndexOutOfBoundsException a) {
System.out.print("ArrayIndexOutOfBoundsException ReTrie.insert(" + word.getNm() + ")");
System.out.println();
}
}
ArrayList<Record> matches = new ArrayList<>();
ArrayList<Record> nonmatch = new ArrayList<>();
PrintWriter found;
PrintWriter notFound;
File dir = new File("DataReports");
public void search(Record word) throws IOException, FileNotFoundException {
if (!dir.exists()) {
try {
dir.mkdir();
}
catch (SecurityException se) {
System.out.println("trie make dir");
}
}
notFound = new PrintWriter(new FileWriter(dir + File.separator + "ReferNotFound." + FileDate.date + ".csv", true));
found = new PrintWriter(new FileWriter(dir + File.separator + "ReferFound." + FileDate.date + ".csv", true));
ReTrieNode p = searchNode(word);
if (p == null) {
String t = word.toString() + "," + "\n";
notFound.append(t);
found.close();
notFound.close();
return;
}
else {
if (p.isEnd) {
String f = w.toString() + "," + "\n";
found.append(f);
found.close();
notFound.close();
return;
}
}
found.close();
notFound.close();
}
public ArrayList<Record> getFind() {
return matches;
}
public ArrayList<Record> getNotFound() {
return nonmatch;
}
public ReTrieNode searchNode(Record s){
try {
ReTrieNode p = root;
String con = Integer.toString(s.getCnum());
for(int i = 0; i < con.length(); i++){
char c = con.charAt(i);
int index = c-'0';
if (p.arr[index] != null) {
p = p.arr[index];
}
else {
return null;
}
}
if (p == root)
return null;
return p;
}
catch (ArrayIndexOutOfBoundsException a) {
System.out.print("ArrayIndexOutOfBoundsException Trie.searchNode(" + s.getNm() + ")");
System.out.println();
return null;
}
}
public String printHeader() {
String COMMA = ",";
return ("Constituent Number" + COMMA + "First Name" + COMMA + "Middle Name" + COMMA
+ "Last Name" + COMMA + "Suffix" + COMMA + "FOTL" + COMMA
+ "State" + COMMA + "Organization" + COMMA + "Position" + COMMA
+ "FB Active" + COMMA + "FB Likes" + COMMA + "FB Comments");
}
}
Here is code for Trie that compares by (first + last name) or Nm:
class TrieNode {
TrieNode[] arr;
boolean isEnd;
public TrieNode() {
this.arr = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
public Record w;
public Trie() {
root = new TrieNode();
}
public void insert(Record word) {
try {
w = word;
TrieNode p = root;
for (int i = 0; i < w.getNm().length(); i++){
char c = w.getNm().charAt(i);
int index = c-'a';
if (p.arr[index] == null) {
TrieNode temp = new TrieNode();
p.arr[index] = temp;
p = temp;
}
else {
p = p.arr[index];
}
}
p.isEnd=true;
}
catch (ArrayIndexOutOfBoundsException a) {
System.out.print("ArrayIndexOutOfBoundsException Trie.insert(" + word.getNm() + ")");
System.out.println();
}
}
ArrayList<Record> matches = new ArrayList<>();
ArrayList<Record> nonmatch = new ArrayList<>();
public Hashtable<String,ArrayList<String>> nam = new Names().getNames();
PrintWriter found;
PrintWriter notFound;
File dir = new File("DataReports");
public void search(Record word) throws IOException, FileNotFoundException {
if (!dir.exists()) {
try {
dir.mkdir();
}
catch (SecurityException se) {
System.out.println("trie make dir");
}
}
notFound = new PrintWriter(new FileWriter(dir + File.separator + "ReviewNotFound." + FileDate.date + ".csv", true));
found = new PrintWriter(new FileWriter(dir + File.separator + "ReviewFound." + FileDate.date + ".csv", true));
TrieNode p = searchNode(word);
if (p == null) {
if (nam.containsKey(word.getFn())) {
ArrayList<String> n = new ArrayList<String>(nam.get(word.getFn()));
for (int j = 0; j < n.size(); j++) {
word.setFn(n.get(j));
word.setNm(word.getFn() + word.getLn());
if (searchR(word) == false) {
String t = word.toString() + "," + "\n";
notFound.append(t);
continue;
}
else {
String s = w.toString() + "," + "\n";
found.append(s);
found.close();
notFound.close();
return;
}
}
}
else {
String u = word.toString() + "," + "\n";
notFound.append(u);
}
found.close();
notFound.close();
return;
}
else {
if (p.isEnd) {
String f = word.toString() + "," + "\n";
found.append(f);
found.close();
notFound.close();
return;
}
}
found.close();
notFound.close();
}
public boolean searchR(Record word) {
TrieNode p = searchNode(word);
if (p == null) {
return false;
}
else {
if (p.isEnd) {
return true;
}
}
return false;
}
public ArrayList<Record> getFind() {
return matches;
}
public ArrayList<Record> getNotFound() {
return nonmatch;
}
public TrieNode searchNode(Record s){
try {
TrieNode p = root;
for(int i = 0; i < s.getNm().length(); i++){
char c = s.getNm().charAt(i);
int index = c-'a';
if (p.arr[index] != null) {
p = p.arr[index];
}
else {
return null;
}
}
if (p == root)
return null;
return p;
}
catch (ArrayIndexOutOfBoundsException a) {
System.out.print("ArrayIndexOutOfBoundsException Trie.searchNode(" + s.getNm() + ")");
System.out.println();
return null;
}
}
public String printHeader() {
String COMMA = ",";
return ("Constituent Number" + COMMA + "First Name" + COMMA + "Middle Name" + COMMA
+ "Last Name" + COMMA + "Suffix" + COMMA + "FOTL" + COMMA
+ "State" + COMMA + "Organization" + COMMA + "Position" + COMMA
+ "FB Active" + COMMA + "FB Likes" + COMMA + "FB Comments");
}
}
I understand this is a rather complex and specific problem. Any and all help is appreciated.
I ended up adding a variable in the trie node that held the instance of the Record class and could be accessed at the end of the trie branch.