I'm currently working on an Android application where I need to implement real-time search functionality using Firebase Database. I've set up a Trie data structure to efficiently search through user names, but I'm encountering an issue.
Here's a my UserTrie class:
class TrieNode {
Map<Character, TrieNode> children;
List<User> users;
boolean isEndOfWord;
TrieNode() {
users = new ArrayList<>();
children = new HashMap<>();
isEndOfWord = false;
}
}
public class UserTrie {
private TrieNode root;
public UserTrie() {
root = new TrieNode();
}
public void insert(String word, User user) {
if (word.isEmpty()) return;
TrieNode current = root;
for (char ch : word.toCharArray()) {
if (!current.children.containsKey(ch)) {
current.children.put(ch, new TrieNode());
}
current = current.children.get(ch);
current.users.add(user);
}
current.isEndOfWord = true;
}
public List<User> search(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
if (!current.children.containsKey(ch)) {
break;
}
current = current.children.get(ch);
}
return current.users;
}
}
Here's how I use it with Firebase :
DatabaseReference reference = FirebaseDatabase.getInstance().getReference();
Query query = reference.child(getString(R.string.user));
query.addListenerForSingleValueEvent(new ValueEventListener() {
@Override
public void onDataChange(DataSnapshot dataSnapshot) {
for(DataSnapshot singleSnapshot : dataSnapshot.getChildren()){
try {
User user = singleSnapshot.getValue(User.class);
if (user != null) {
userTrie.insert(user.getName(), user);
}
} catch (Exception e) {
Log.e(TAG, "Failed to convert value to User: " + e.getMessage());
}
}
mSearchParam.addTextChangedListener(new TextWatcher() {
@Override
public void beforeTextChanged(CharSequence s, int start, int count, int after) {
}
@Override
public void onTextChanged(CharSequence s, int start, int before, int count) {
mUserList.clear();
String text = mSearchParam.getText().toString();
if (text != null && !text.isEmpty() && text.length() > 0) {
mUserList = userTrie.search(text);
//update the users list view
updateUsersList();
}
}
@Override
public void afterTextChanged(Editable s) {
}
});
}
@Override
public void onCancelled(DatabaseError databaseError) {
}
});
The json view of firebase database :
{
"users": {
"0pnms": {
"detail": "",
"name": "name1"
},
"0qx6l": {
"detail": "",
"name": "name2"
},
"1WgTv": {
"detail": "",
"name": "name3"
}
}
}
The issue is that while the real-time search works fine for a text being queried for the first time, subsequent searches for already searched texts don't yield any results, for example the user list for "a", "ab" and "abc" after searching "abc" returns empty. This happens because the search process is sequential, and results for prefixes are generated along the way, leading to no results for already searched queries.
I tried making the List final, also tried to reset current to root after search completes thinking it might be problem with the instance but nothing works.