Do I use Trie correctly for implementation of a phonebook?
0
$begingroup$
I implemented a PhoneBook utilizing a Trie data structure.
Could I ask you to evaluate it?
Did I apply Trie correctly for such case or is it better to store data somehow else?
I'm looking not only for working solution but also for an optimal one in terms of run-time and storage.
From my calculations, it takes NlogT to add() and get() where N is a number of chars and T is a number of children.
Am I right?
Here is the logic
public final class PhoneBook {
private final Node name;
private final Node surname;
private final Comparator<Record> comparator;
public PhoneBook() {
this.name = new Node();
this.surname = new Node();
comparator = (r1, r2) -> {
int result = r1.getName().compareTo(r2.getName());
if (result == 0) {
result = r1.getSurname().compareTo(r2.getSurname());
if (result == 0) {
result = r1.getNumber().compareTo(r2.getNumber());
}
}
return result;
};
}
public void add(final Record record) {
add(record.getName().toLowerCase(), record, name);
add(record.getSurname().toLowerCase(), record, surname);
}
public SortedSet<Record> get(final String prefix) {
final String lc = prefix.toLowerCase();
final List<Record> recordsRetrievedByName = get(lc, name);
final List<Record> recordsRetrievedBySurname = get(lc, surname);
final SortedSet<Record> result = new TreeSet<>(comparator);
result.addAll(recordsRetrievedByName);
result.addAll(recordsRetrievedBySurname);
return result;
}
private List<Record> get(final String prefix, final Node ancestor) {
Node node = ancestor;
for (final char c: prefix.toCharArray()) {
final Node child = node.children.get(c);
if (child == null) {
return Collections.emptyList();
}
node = child;
}
return node.records;
}
private void add(final String str, final Record record, final Node ancestor) {
Node node = ancestor;
for (final char c: str.toCharArray()) {
final Node child;
if (node.children.containsKey(c)) {
child = node.children.get(c);
} else {
child = new Node();
node.children.put(c, child);
}
child.records.add(record);
node = child;
}
}
private static final class Node {
private final Map<Character, Node> children = new TreeMap<>();
private final List<Record> records = new ArrayList<>();
}
}
And the Record immutable object
public final class Record {
private final String name;
private final String surname;
private final String number;
//constructor, getters, toString
}
java algorithm tree complexity trie
asked 11 mins ago
PavelPavel
1012
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
0
$begingroup$
I implemented a PhoneBook utilizing a Trie data structure.
Could I ask you to evaluate it?
Did I apply Trie correctly for such case or is it better to store data somehow else?
I'm looking not only for working solution but also for an optimal one in terms of run-time and storage.
From my calculations, it takes NlogT to add() and get() where N is a number of chars and T is a number of children.
Am I right?
Here is the logic
public final class PhoneBook {
private final Node name;
private final Node surname;
private final Comparator<Record> comparator;
public PhoneBook() {
this.name = new Node();
this.surname = new Node();
comparator = (r1, r2) -> {
int result = r1.getName().compareTo(r2.getName());
if (result == 0) {
result = r1.getSurname().compareTo(r2.getSurname());
if (result == 0) {
result = r1.getNumber().compareTo(r2.getNumber());
}
}
return result;
};
}
public void add(final Record record) {
add(record.getName().toLowerCase(), record, name);
add(record.getSurname().toLowerCase(), record, surname);
}
public SortedSet<Record> get(final String prefix) {
final String lc = prefix.toLowerCase();
final List<Record> recordsRetrievedByName = get(lc, name);
final List<Record> recordsRetrievedBySurname = get(lc, surname);
final SortedSet<Record> result = new TreeSet<>(comparator);
result.addAll(recordsRetrievedByName);
result.addAll(recordsRetrievedBySurname);
return result;
}
private List<Record> get(final String prefix, final Node ancestor) {
Node node = ancestor;
for (final char c: prefix.toCharArray()) {
final Node child = node.children.get(c);
if (child == null) {
return Collections.emptyList();
}
node = child;
}
return node.records;
}
private void add(final String str, final Record record, final Node ancestor) {
Node node = ancestor;
for (final char c: str.toCharArray()) {
final Node child;
if (node.children.containsKey(c)) {
child = node.children.get(c);
} else {
child = new Node();
node.children.put(c, child);
}
child.records.add(record);
node = child;
}
}
private static final class Node {
private final Map<Character, Node> children = new TreeMap<>();
private final List<Record> records = new ArrayList<>();
}
}
And the Record immutable object
public final class Record {
private final String name;
private final String surname;
private final String number;
//constructor, getters, toString
}
java algorithm tree complexity trie
asked 11 mins ago
PavelPavel
1012
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
0
0
0
$begingroup$
I implemented a PhoneBook utilizing a Trie data structure.
Could I ask you to evaluate it?
Did I apply Trie correctly for such case or is it better to store data somehow else?
I'm looking not only for working solution but also for an optimal one in terms of run-time and storage.
From my calculations, it takes NlogT to add() and get() where N is a number of chars and T is a number of children.
Am I right?
Here is the logic
public final class PhoneBook {
private final Node name;
private final Node surname;
private final Comparator<Record> comparator;
public PhoneBook() {
this.name = new Node();
this.surname = new Node();
comparator = (r1, r2) -> {
int result = r1.getName().compareTo(r2.getName());
if (result == 0) {
result = r1.getSurname().compareTo(r2.getSurname());
if (result == 0) {
result = r1.getNumber().compareTo(r2.getNumber());
}
}
return result;
};
}
public void add(final Record record) {
add(record.getName().toLowerCase(), record, name);
add(record.getSurname().toLowerCase(), record, surname);
}
public SortedSet<Record> get(final String prefix) {
final String lc = prefix.toLowerCase();
final List<Record> recordsRetrievedByName = get(lc, name);
final List<Record> recordsRetrievedBySurname = get(lc, surname);
final SortedSet<Record> result = new TreeSet<>(comparator);
result.addAll(recordsRetrievedByName);
result.addAll(recordsRetrievedBySurname);
return result;
}
private List<Record> get(final String prefix, final Node ancestor) {
Node node = ancestor;
for (final char c: prefix.toCharArray()) {
final Node child = node.children.get(c);
if (child == null) {
return Collections.emptyList();
}
node = child;
}
return node.records;
}
private void add(final String str, final Record record, final Node ancestor) {
Node node = ancestor;
for (final char c: str.toCharArray()) {
final Node child;
if (node.children.containsKey(c)) {
child = node.children.get(c);
} else {
child = new Node();
node.children.put(c, child);
}
child.records.add(record);
node = child;
}
}
private static final class Node {
private final Map<Character, Node> children = new TreeMap<>();
private final List<Record> records = new ArrayList<>();
}
}
And the Record immutable object
public final class Record {
private final String name;
private final String surname;
private final String number;
//constructor, getters, toString
}
java algorithm tree complexity trie
asked 11 mins ago
PavelPavel
1012
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I implemented a PhoneBook utilizing a Trie data structure.
Could I ask you to evaluate it?
Did I apply Trie correctly for such case or is it better to store data somehow else?
I'm looking not only for working solution but also for an optimal one in terms of run-time and storage.
From my calculations, it takes NlogT to add() and get() where N is a number of chars and T is a number of children.
Am I right?
Here is the logic
public final class PhoneBook {
private final Node name;
private final Node surname;
private final Comparator<Record> comparator;
public PhoneBook() {
this.name = new Node();
this.surname = new Node();
comparator = (r1, r2) -> {
int result = r1.getName().compareTo(r2.getName());
if (result == 0) {
result = r1.getSurname().compareTo(r2.getSurname());
if (result == 0) {
result = r1.getNumber().compareTo(r2.getNumber());
}
}
return result;
};
}
public void add(final Record record) {
add(record.getName().toLowerCase(), record, name);
add(record.getSurname().toLowerCase(), record, surname);
}
public SortedSet<Record> get(final String prefix) {
final String lc = prefix.toLowerCase();
final List<Record> recordsRetrievedByName = get(lc, name);
final List<Record> recordsRetrievedBySurname = get(lc, surname);
final SortedSet<Record> result = new TreeSet<>(comparator);
result.addAll(recordsRetrievedByName);
result.addAll(recordsRetrievedBySurname);
return result;
}
private List<Record> get(final String prefix, final Node ancestor) {
Node node = ancestor;
for (final char c: prefix.toCharArray()) {
final Node child = node.children.get(c);
if (child == null) {
return Collections.emptyList();
}
node = child;
}
return node.records;
}
private void add(final String str, final Record record, final Node ancestor) {
Node node = ancestor;
for (final char c: str.toCharArray()) {
final Node child;
if (node.children.containsKey(c)) {
child = node.children.get(c);
} else {
child = new Node();
node.children.put(c, child);
}
child.records.add(record);
node = child;
}
}
private static final class Node {
private final Map<Character, Node> children = new TreeMap<>();
private final List<Record> records = new ArrayList<>();
}
}
And the Record immutable object
public final class Record {
private final String name;
private final String surname;
private final String number;
//constructor, getters, toString
}
java algorithm tree complexity trie
java algorithm tree complexity trie
asked 11 mins ago
PavelPavel
1012
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 11 mins ago
PavelPavel
1012
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 11 mins ago
PavelPavel
1012
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 11 mins ago
PavelPavel
1012
asked 11 mins ago
PavelPavel
1012
1012
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Pavel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Pavel is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215468%2fdo-i-use-trie-correctly-for-implementation-of-a-phonebook%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Pavel is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Pavel is a new contributor. Be nice, and check out our Code of Conduct.
Pavel is a new contributor. Be nice, and check out our Code of Conduct.
Pavel is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215468%2fdo-i-use-trie-correctly-for-implementation-of-a-phonebook%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
