DEV Community: Marcello La Rocca

5 Tips to Pass Your Next Interview's Coding Exercise

Marcello La Rocca — Thu, 20 Jan 2022 16:57:01 +0000

As part of my job, I started getting more involved in the hiring process, and lately I had the chance to review and discuss many coding exercises, which for us are the first screening for technical interviews.

That made me realize how many people, even some of those who are technically skilled, may fail the screening because of their approach.

Here are a few takeaways that might help you face a coding exercise in your next interview, based on my own past mistakes and my experience on the other side of the barricade.

Don't Rush It (unless you are asked to)

Coding exercises are your business card to your potential employers. Even more than your resume: in your CV you talk about what you can do, but in an exercise you have to actually show that.

They are your chance to show your technical skills, but also all the tacit knowledge and best practices you accumulated over your career.

While it's impossible to come up with a general rule about how much time you should spend on your exercise, an always good rule of thumb is to base that on the feedback from the team. (More in the next points).

Regardless of how much time you spent on it, another golden rule is that you should never give the impression you rushed your solution. Unless you have a short deadline, you should take the time to solve the exercise properly, clean up your code, iterate over your solution and find the possible bottlenecks.

You should never just return a "quick and dirty solution" (unless you are asked to), for two reasons:

The goal of asking for this kind of coding exercise is in part to filter out people who are not used to code on a daily basis, but you can also show much more than your problem solving or coding skills.
If you rush it, the hiring team could get the impression you are not really interested in that position, that you are not willing to make an effort to get it.

Read the Exercise

And I mean read the text of the coding exercise carefully. Devil is in the details, and so is your chance of passing an interview, so you better get those right.

Like any college exam or school test, you need to make sure you understand the questions before you answer them, or understand the problem before you can solve it.

A few tips:

Check what's the goal of the task, and focus on that.
Don't over-engineer your solution: if you are asked for a simple digital phone book, don't try to implement a social network or add voice recognition (while it might show some of your skills, one skill in high demand is being able to judge what's relevant for a task and use a reasonable amount of resources for it).
Not everything can or should be solved with Machine Learning.
If you are asked for production-level code, make sure to polish your solution before you submit it.
Add a proper amount of comments: not too much to be needlessly verbose, but you'd better explain the key points (I'll never get tired of stressing how this is important in your everyday work: while your code might seem obvious to you the moment you wrote it, your colleagues and your future self will thank you for those comments in a year).
Document your classes/methods (rule of thumb: when in doubt thoroughly document the public ones, just pretend you are writing an API).
If it's not clear from the exercise, ask if there is any constraint about tech stack, platform, OS or build system.

Clarify Requirements (or Make Explicit Assumptions)

You should get an idea from the exercise's description, but when in doubt, you have two ways:

Ask your recruiter for clarifications. If you are in touch with the developers team who formulated the exercise, even better, ask them directly, if possible.
Make assumptions about the requirements (and document those thoroughly).

The first alternative is a good way to shed light on some questions that could influence the final result and the effort needed: for instance, it's often a good idea to double check the size of the expected input, if your input data is supposed to fit in memory or if you need more complex solutions. If you don't need to worry about some of these things, you can save time or focus on crucial parts.

At the same you should not take this too far: you don't want to ask every nit about the requirements! Besides becoming potentially annoying, you don't want your potential future team to get the idea you are incapable of making the smallest decisions alone.

And so a good compromise could be using a mix of those solutions. Choose a few (maybe 2 or 3 at most) big questions you'd like to clarify, on topics you would normally discuss with your PM/client on a real project (for example, about how what you are writing will be used) and check your understanding of those requirements.

Then for other small things, like (for example) some input formatting issues (unless already specified in the exercise), make assumptions: the important thing is that you document all these assumptions, explaining (ideally in a README you will include in your bundled answer) what you are assuming and why you are making that particular choice.

Clarify Expectations

Make sure that what you think it's expected from you is aligned with what the team actually expects.

Read the exercise and if in doubt check with your recruiter about the deadline, the code quality and the programming language you are using.

War Story
There was this one time, some 12 years ago, I had two phone interviews in the same days. Both asked me to solve a coding exercise, at home. So for the first one, I was given a time limit, but I decided to go for an unnecessarily fancy solution spilling over the allotted time: despite they told me they liked my solution, they also said that staying within the deadline was more important (e.g. I didn't read the exercise's constraints well + didn't clarify the expectations, and I paid the consequences).
Then on the next day I embarked on the exercise for the second interview (at a different company). Remembering what had happened the day before, instead of going for a complicated solution I rushed to a simple one and sent it back within a couple of hours. Of course, this time they were more interested in clean and tested code, and they wouldn't have minded a fancier algorithm 🤦‍♂️
(e.g. again I didn't clarify expectations + rushed it + didn't test it).

Heads up: if you have a chance, check also with the team or with whom will interview you. Sometimes recruiter can make mistakes or can be unaware of some technical constraints.
For instance, if you know a company works mostly with (say) Java, or if the job post or homework test says you need to use Java, don't rely on a recruiter telling you that you can use (say) Python. Trust me, I wasted a couple of good opportunities because of that (but that's a _war story for another time).

Test It (Thoroughly)

Would you deploy code to production without proper tests? If you would, that's a different problem (and we should talk about a different approach). But hopefully you embrace good practices and thoroughly test your code (which doesn't necessarily mean aiming for 100% coverage, but writing adequate tests depending on reach, risk etc.)

Then, take-at-home tasks are just your best chance to show your possible future colleagues and employers that you do care about best practices.
If you are still not convinced, I'll add that testing your code is also your best shot at nailing the coding exercise, making sure that your code behaves as expected and works for any example provided (and ideally a few more).

Caveat: if you have time constraints to produce your solution, obviously you might not be able to test your code thoroughly (or at all). Likewise, if you are explicitly asked to write some throw-away code, a prototype or proof of concept, extensive testing would not be needed or possibly wanted.

A few tips:

Focus on the most important areas of your code and test those first and more extensively. Then, if you have time, cover more code.
If you have to validate your inputs, be thorough in testing valid and invalid data, especially edge cases.
Reason about edge cases and try to cover them all. Then test a few of the common inputs.
Try to avoid random tests, which might lead to flaky tests.
If possible, write tests first, even before you start writing code: it will help you clarify requirements and plan how to develop your code.
First set your tests up to failure: what I mean is, for instance, if you have to check that the result of function F is always positive, initially assert that F(x) is negative, and see the test fail. This will help you double check that you are testing the right code and that the test would detect an error.

Conclusions

And... that's all you need to thrive! Seriously - well, that, and some hard skills (coding, designing, etc..., depending on the role), of course. To some readers these might seem trivial suggestions, maybe even something you'd take for granted when you assign such a test. But truth to be told, you'd be surprised to see the percentage of applicants rejected because of a misunderstanding about the expectations, or for skipping tests altogether.

I myself had to learn these lessons the hard way, when I started seriously interviewing for developer positions. And even more, learning never ends, at each interview (either as interviewer or interviewee) there is something new to be learned.
But in those early days I got burned a few times, and I wish I had had some advice or a way to practice, to avoid wasting many good opportunities.

So, if you are starting your journey into software engineering, or even if you are a more seasoned engineer who is just preparing to go back to interviewing, I hope these few pieces of advice can help you express your true potential.

Java Profiling: comparing BSTs, tries and TSTs

Marcello La Rocca — Fri, 13 Nov 2020 18:10:37 +0000

So far in this series we have discussed tries and TSTs as possible alternatives to binary search trees when it comes to (in-memory) strings containers.

But is there a real advantage in using them? And do TSTs really allow a further saving on tries?

To answer these questions, in this article I'll be using YourKit Java profiler to check and compare both the memory usage and runtime of simple operations for these data structures.

YourKit is pretty easy to use and it's nicely integrated with IntelliJ Idea, but obviously there are also many alternatives that would serve my purpose, like for instance JProfile.

Profiling Memory

For the memory print, my test is simple: I'll load the full list of words in a typical English dictionary, and see how much RAM each of these data structures take.

The code for profiling these structures might look something like this:

public class StringsTreeProfiler {
    public static final String WORDS_JSON = "words_dictionary.json";

    @Test
    public void profileTrieMemory() throws FileNotFoundException {
        Trie trie = new Trie();
        Tst tst = new Tst();
        BST<String> bst = new BST<>();

        InputStream inputStream = new FileInputStream(WORDS_JSON);
        try {
            JSONObject json = new JSONObject(new JSONTokener(inputStream));
            for (String key : json.keySet()) {
                trie.add(key);
                tst.add(key);
                bst.add(key);
            }
        } catch (ValidationException e) {
            Assert.fail();
        }
    }

For practical purposes, to easily spot the total memory used, I'll split it into three different methods, one per data structure.
You can check the actual code on GitHub.

Obviously when we do such a practical test we need to be aware that there are many variables that impact on the results, from the implementations (for instance, the degree of optimization of the code, or choices like using java.util.Optional, as we'll see), the compiler options, the libraries used, the operating system, and the architecture of the underlying hardware (for instance, if it's a 32-bit or 64-bit processor).

All of these details make a difference in the final result; do they matter? That depends: clearly when the compared results are close to each other, these factors are more important, because they can make a difference. But, in terms of asymptotic analysis, these choices mostly influence the constant factor that multiplies the running time (unless, of course, there are implementation errors that cause severe inefficiencies, like f.i. implementing a reverse method that takes quadratic time instead of the optimal linear-time version).

Long story short, if the difference is large enough, the system details and compiler options won't matter, and the implementation details will be irrelevant for what concerns fine-grain optimization, and only relevant in case of serious design mistakes affecting the asymptotic running time.

Binary Search Tree

Let's start with our baseline, binary search trees.

First, let's see how much RAM is overall used:

Then, what's even more interesting, we can break down this information by class, and see that we needed 1.8M BST nodes, and a lot of space was also taken up by Optional objects (that, however, were temporary objects used just as return values by some of the methods).

Trie

Now that we have a baseline, let's see how tries are comparatively doing: apparently the total memory used is slightly larger, 206MB versus the 172MB used by binary search trees.

This might be a bit surprising, but breaking it down to the classes level, helps us understand why...

While, in fact, only half as many nodes are created - barely 1M Trie::Node versus 1.8M BST::Node- each trie node has to hold a HashMap, and the total space required by these structures amounts to more than 150MB - almost 75% of the total RAM used.

The overall values, however, are very close, so the two data structures can be considered comparable in their memory print - the actual relative performance will of course depend on the length and overlapping of the strings stored: the more they overlap, the better tries will perform compared to BSTs.

Ternary Search Tree

Now, removing hash tables from nodes is exactly the reason why we introduced TSTs in this series. So, let's see how they do on the same task.

The result is amazing: they just need 61MB of RAM to store the same dictionary that needed three times over with BSTs and tries.

Looking at the breakdown by class, we can see that approximately the same number of nodes is created as it was for tries, but this time we don't have the burden of the HashMaps to store.

Tst Random Insertion Order

Well that would be conclusive, wouldn't it?
There is only one test that we could, and should, make.
In the listing at the beginning of this post, we are adding words in a for-in loop, directly from the JSON object created from the file.

What's the order in which keys are inserted? Are they sorted, or randomly ordered?
A method like keySet doesn't offer any guarantee on the order used to return items, so I arranged two tests: one with all keys sorted ascendingly, and one with keys explicitly shuffled, using a List to hold them and Collections.shuffle.

List<String> keys = new ArrayList<>((new JSONObject(new JSONTokener(inputStream))).keySet());
Collections.shuffle(keys);
for (String key : keys) {
    trie.add(key);
}

Remember that while for tries the order of insertion doesn't matter, it is relevant in TSTs (and BSTs), and an adverse sequence of insertions (like adding keys in a sorted sequence) can result in a skewed, list-like tree.

Despite that, the number of nodes needed stays the same, and the total RAM needed remains consistently below 70MB.

A note on using `Optional`

For BSTs, you can see how a lot of space is taken up by Optional - even without that, the total amount of RAM used would be way more than for TSTs, but it would get closer.

Optional is a great way to make your code cleaner, although the java.util version has some problems limiting its applicability, and it's not meant to be used to store values, like in a class property (it's not even serializable), but just as an intermediate product (especially and originally for Stream's methods).

In other words, projecting this to the case of our tree-like data structures, replacing null with Optional.empty for a missing link to a child is not advisable.

But, just for the sake of curiosity, what would be the impact of doing so, wrapping links to children in Optional?

Even if it wasn't just poor design, it would be as heavy as for BSTs, more than doubling the size needed for storing the same set of strings.

Profiling Running Time

We now have a decent idea of the advantage given by TSTs in terms of RAM, but that's just one side of the coin!
The other important factor to consider is the running time of the most important operations on these containers: core operations, like insertion and deletion, but also search.

For this test as well, we are going to separately evaluate two situations: when the inputs are shuffled, and when they are sorted ascendingly. For the sorted sequences, however, it wasn't possible to test the binary search tree implementation: by inserting the words in the worst possible sequence, a non-balanced binary search tree would become a long (really long!) linked list, and the recursive implementation of method BST::add would cause a stack overflow!

You might wonder, why that doesn't happen with Trie and Tst? If you remember what we discussed in part 2 of this series, the important difference is that with binary search trees the height of the tree depends on the number of elements stored - logarithmically if the tree is balanced, or linearly in the worst case (which happens to be exactly when inputs are added in a sorted sequence). For tries and TSTs, instead, the height of the tree only depends on the length of the words added and, for TSTs only, also on the size of the alphabet: in the worst-case scenario, we are therefore talking about a difference of orders of magnitudes: n is in the order of 370K elements, while the sum of the length of the longest word and the size of the alphabet doesn't reach 50.

Insertion

For the core methods, we are going to focus on testing insertion; We will reuse the code inserting all the keys in the English dictionary in a container, and check the performance in two cases: when the list of keys is shuffled, and when it is sorted lexicographically.

@Test
public void profileRunningTime() throws FileNotFoundException {
    Trie trie  = new Trie();
    Tst tst = new Tst();
    BST<String> bst = new BST<>();

    InputStream inputStream = new FileInputStream(WORDS_JSON);
    try {
        List<String> keys = new ArrayList<>((new JSONObject(new JSONTokener(inputStream))).keySet());
//            Collections.shuffle(keys);
        Collections.sort(keys);
        for (String key : keys) {
            trie.add(key);
            tst.add(key);
//                bst.add(key);
        }
    } catch (ValidationException e) {
        Assert.fail();
    }
}

Shuffled List

What happens when we measure the total time needed to populate the containers with all the words in the dictionary?
Not surprisingly, as we had suggested in the first part of this series, BSTs are the slowest: it takes 1.28 seconds to add the whole dictionary to a BST.

Tries are much better, the whole operation took only 0.51 seconds, less than half the time needed for a BST.

What about TSTs? that's the best part, it only took 0.25 seconds, less than half the time needed for a BST, and 20% of the time used by a BST!

I obviously ran these profiling several times, and besides small variations, the results were always consistent with the image above.

Sorted List

But, as we said, this is the best-case scenario for a TST, because with a random input sequence, the resulting tree will be balanced, on average (with 300K words added, the chances of having a worst-case-scenario input sequence are pretty grim...).

In this case we only could test tries against TSTs, because BSTs, which would have been terribly slow anyway, ran into a stack overflow.

That's one reason why I usually suggest avoiding recursive code, unless you know that your language/compiler has tail-call optimization, or you are sure that your input won't be larger than a safety threshold.

When the input is sorted, tries (which aren't sensitive to the order of insertion) performed better that TSTs.

Longest Shared Prefix

The final step for this post is checking how these three structures are performing on search.
To probe that, I decided to test the method longestPrefixOf that, given a string s, checks what's the longest prefix of s stored in the container.

The testing method will create the containers, and then call longestPrefixOf a million times, using randomly chosen real words actually stored in the containers, to which a variable number of random characters is added.

@Test
public void profileRunningTime() throws FileNotFoundException {
    Trie trie  = new Trie();
    Tst tst = new Tst();

    InputStream inputStream = new FileInputStream(WORDS_JSON);
    try {
        List<String> keys = new ArrayList<>((new JSONObject(new JSONTokener(inputStream))).keySet());
//            Collections.shuffle(keys);
        Collections.sort(keys);
        for (String key : keys) {
            trie.add(key);
            tst.add(key);
        }
        for (int i = 0; i < 1000000; i++) {
            String key = keys.get(random.nextInt(keys.size())) + randomKey(0, 10);
            trie.longestPrefixOf(key);
            tst.longestPrefixOf(key);
        }

    } catch (ValidationException e) {
        Assert.fail();
    }
}

private String randomKey(int minLength, int maxLength) {
    int length = (int) Math.floor(Math.random() * (maxLength - minLength)) + minLength;
    char[] chars = new char[length];
    for (int i = 0; i < length; i++) {
        chars[i] = (char)(random.nextInt(26) + 'a');
    }
    return new String(chars);
}

The results tell us that when a TST is balanced, it performs slightly better than an equivalent trie.

When a TST is skewed, instead, a trie performs much better (approximately twice as fast).

Conclusions

Profiling helped us understand the advantages and pitfalls of using various string containers in a real scenario.
We could prove that the effort of implementing and maintaining a dedicated data structure (like a trie or TST) is compensated by a large saving in terms of space (down to 20% of the RAM used by a BST) and running time.

This concludes this series, if you'd like to get more insight or would like to see more, please feel free to add a comment!

Prefix Search with Ternary Search Trees (Java Implementation)

Marcello La Rocca — Wed, 04 Nov 2020 19:33:07 +0000

In the last post in the series, we went over the core methods (insert, delete, search) for Ternary Search Trees; before that, we had already discussed how tries work. Now, it's time to get to the money, and discuss what makes both these data structures extremely valuable in a lot of areas: prefix search.

There are (at least) two complementary ways to decline this operation:

Finding the longest prefix of a given string s that is stored in our container;
Finding all the keys stored in a container that starts with a given prefix.

Both operations can be implemented in any container, of course: trivially, we can just iterate through all the entries, and select the result, or results.
The difference is that ternary search trees, like tries and radix trees, allow to perform this operation much more efficiently.

`longestPrefix`

Let's start with the first operation: we have a string s (containing m characters), and a container T storing a certain number of keys - let's say n keys.

We would like to know what's the longest prefix p of s that is stored in T.

This operation is pretty useful in many practical situations; even without bringing up bioinformatics (where efficiently finding the longest common prefix of DNA sequences is a must) it can be used in routers, where given an IP address, we need to find the longest prefix of that address for which there are routing information available, but also in network data clustering and telephone network management.

But it can also be used with suffix trees to implement efficient substring search, and as such is very useful in various fields, from full-text search in text-oriented search engines, to bioinformatics.

A suffix tree is a key-value trie where keys are all the suffixes of a given text, and the values stored by each key are the positions of each suffix in the text.

In abstract, the way the algorithm works is simple: we scan the input string key character by character, and in parallel traverse the tree, starting from the root.
At any given point, we will have reached a node n in the tree, after successfully matching a substring s of the input string.

Assuming he next character in the input string is c, we check if in the tree (or, rather, in the subtree rooted at current node) there is a path of left/right links to that character - if we can't find it, then there is no prefix of the input string that includes c, and s is the longest prefix of the input string key for which there is a path in the tree.

Now, there are two ways we might consider this result, which leads to two different versions of the algorithm.

You don't care if the prefix is stored or not, you need to know what's the longest shared part between two strings: this is the case, for instance, in routers, if for an address like 192.168.1.1 you are OK with a result like 192.16;
You might want only the longest prefix that is actually stored in the tree: this might be the case if we are looking for valid words that are prefixes to a longer word or, to go back to the example of routers, you can imagine forcing only full-block matches, and so 192 or 192.168 would be acceptable results, but not 192.16.

Below I implemented the second version, where the prefix must be stored in the tree, but it's easy to change it to return just the longest path traversed, or take a parameter to decide which version is preferred (hint: look for the two places where this.storesKey() is checked).

Another nit: if you remember, in the last post we had discussed how it would be more efficient to pass the index of the next character to check in the input string, rather than resorting to calling substring after every match. For this method, this solution also makes it easier to return the final result, and so it's the one I'm presenting.

public String longestPrefixOf(String key) {
    return this.longestPrefixOf(key, 0);
}

private String longestPrefixOf(String key, int charIndex) {
    if (charIndex >= key.length()) {
        return null;
    }
    String result = null;
    Character c = key.charAt(charIndex);
    if (c.equals(this.character)) {
        if (charIndex == key.length() - 1) {               // case A.1
            return this.storesKey() ? key : null;          
        } else {                                           // case A.2
            result = middle == null 
                ? null                                     / case A.2.a
                : middle.longestPrefixOf(key, charIndex + 1); // case A.2.b
            if (result == null && this.storesKey()) {
                result = key.substring(0, charIndex + 1);  // case A.2.c
            }
        }
    } else if (c.compareTo(this.character) < 0) {
        result = left == null 
            ? null                                         // case B.1
            : left.longestPrefixOf(key, charIndex);        // case B.2
    } else {
        result = right == null
            ? null                                         // case C.1
            : right.longestPrefixOf(key, charIndex);       // case C.2
    }
    return result;
}

Let's see an example to clarify how the method works. Suppose we are looking for the longest prefix of string shop.
We start from the root, looking for the first character, 's':

(A) the root node doesn't match, and we need to take a right, because it holds character 'o', which is less than 's';
(B) at the second attempt we are luckier, we match the searched char, so we can traverse the middle link and advance the pointer in the string: now we'll be looking for character 'h'.

(C) Another match, so again we traverse the middle link and at the same time move to the next character in the input string, 'o`.
(D) This time we are not in luck, 'e' < 'o', so we traverse the right link, still looking for the next 'o' in the subtree.

(E) Another match, so again we traverse the middle link and at the same time move to the next character in the input string, 'p`.
(F) Again, a mismatch, but this case is interesting: the character held by this node, 'r' is larger than 'p`, but there is no left link to traverse, so the search stops here and the method starts backtracking.

With current tree, and if we look for the longest prefix actually stored in the tree, the method would return null (no prefix of "shop" is stored in the tree, and in fact the only key node traversed in the one corresponding to "she", that's not a prefix of the input).
For the sake of illustrating a more interesting scenario, let's now slightly pivot and consider a tree where the key "sh"is also stored, illustrated in the following graphic.

So, let's start from the end: in (F) we had a mismatch on the last node visited, and that node had no children; we thus are in case B.1 in the code above, and we'll return null. The recursion back-traces to the previous call (shown in (E)), where we had a match on 'o', but since we are requesting the longest prefix to be stored in the tree, this call as well will return null (case A.2).
In (D) we were in case C.2, so we'll follow through the result of the recursive call, which is still null; finally, when we get back to the call shown in (C), we hit case A.2.b, and return the string 'sh' as the longest common prefix.

`keysWithPrefix`

The second method that we are going to discuss takes a string and returns an Iterable (a collection, in more generic terms) of strings; this collection can of course be empty, if no element stored in the tree starts with the input string.

This method is very useful, for instance, to create autocomplete systems: while a user is typing (well, ideally not after every keystroke, but that's a story for a different time) we need to perform quick searches on the container to suggest some text that starts with what was already typed - so this search ideally should be quite fast, and trie-like containers are paramount.

The method is, at a high level, very easily described: we need to search for the prefix (in particular, for the node at which the path corresponding to the prefix ends, regardless of if it's storing a key or not), and then return all the keys stored in the subtree rooted at that node.

public Iterable<String> keysWithPrefix(String prefix) {
    // Invariant: prefix is not empty
    TstNode node = this.search(prefix);

    return node == null
            ? new HashSet<>()
            : node.keys().stream()
            // All keys in node.keys already include the last character in prefix
            .map(s -> prefix.substring(0, prefix.length() - 1) + s)
            .collect(Collectors.toSet());
}

The code above assumes we have two methods already implemented: a search method (see the previous post in the series) and a method returning all keys stored in a subtree, which we'll describe next.

The only step that needs carefulness in the code above is mapping the strings returned by method keys: first of all, why we need it? Well, if we don't start collecting keys from the root of the tree, but from a random node, then we'll return only the suffixes of the keys actually stored (unless we tweak the tree structure or the method to remember the full string that a node corresponds to in the full tree, but this would complicate and disrupt the inductive definition of TSTs).

There is another thing that we need to be careful about: if we start gathering keys from node n, holding character c, all the the results will start with c, and so we need to prepend them with characters in the input prefix up to, and not including, c.

Both aspects are more clearly illustrated in the following graphic.

Now, we have one more task left: implementationing the method that collects all keys stored in a (sub-)tree.
In this case as well, the high-level design of the method is not particularly convoluted: we just need to traverse all branches, all nodes of the tree, and add the keys we find to a list.

To make our life simpler, we can write a public method that takes care of initializing this list and starting the traversal, and a private method that takes this list (that Java automatically passes by reference) and add keys to it as soon as they are found; the alternative (merging lists from the recursive calls to a node's children) would be much more expensive.

public List<String> keys() {
    List<String> keys = new ArrayList<>();
    this.keys("", keys);
    return keys;
}

private void keys(String currentPath, List<String> keys) {
    if (this.storesKey()) {
        keys.add(currentPath + this.character);         // case 0
    }
    // For left and right branches, we must not add this node's character to the path
    if (left != null) {
        left.keys(currentPath, keys);                   // case A
    }
    if (right != null) {
        right.keys(currentPath, keys);                  // case B
    }
    // For the middle child, instead, this node's character is part of the path forward
    if (middle != null) {
        middle.keys(currentPath + character, keys);     //case C
    }
}

Another chance for optimization would be replacing the string concatenation in recursive calls, currentPath + character: we could pass currentPath as a list of characters, that would get a new element only when we follow a middle link (case (C) in the code above - just know that it should then be popped after the call returns!), and a String would be constructed from the list only when we find a key stored in the tree (case (0) above).
This, however, would make the code less clean and potentially troublesome, if this code is changed to spread recursive calls over different threads.

If we are going to implement autocomplete, chances are that we only need a handful of results to be shown; we might have a preferred criteria for the keys returned (for instance, the longest results first, or choosing them using lexicographic order), but in most cases, we might avoid traversing the whole tree, and stop as soon as we have enough results to show.
This is saving important resources especially on the first key strokes, where the prefix is shorter and the number of matching results can be huge: there is no point in returning a thousand possible values, if only 5 or 6 can be shown to the user - that would be just a waste of computational resources and, potentially, of bandwidth (but in that case there would also be other errors in the design of the backend and server-client communication).

Changing the code shown above to take into account a threshold for the number of results returned is not too complicated: we just need to check the size of the list after adding a new element - whenever it's filled with enough results, we can just return, without traversing the subtree rooted at current node.

private void keys(String currentPath, List<String> keys, int maxResults) {
    if (this.storesKey()) {
        keys.add(currentPath + this.character);
        if (keys.size >= maxResults) {
            return;
        }
    }
    if (left != null) {
        left.keys(currentPath, keys, maxResults);
    }
    if (right != null) {
        right.keys(currentPath, keys, maxResults);
    }
    if (middle != null) {
        middle.keys(currentPath + character, keys, maxResults);
    }
}

Conclusions

Prefix search is the real "competitive advantage" of tries and TSTs over other data structures.
But you don't have to take my word for granted: in the next post, we'll use a profiler to show the difference in running time between these two data structures and binary search trees , as well as their impact on RAM.

New Features in ES2021

Marcello La Rocca — Tue, 27 Oct 2020 10:34:12 +0000

In this post, we'll take a look at the most interesting features that should be included in ES12, the new version of the standard.

The new feature that will be included in ES12, aka ES2021, the JavaScript specification developed by ECMA for 2021, are currently under discussion, and a few weeks ago, on October 15th, a new draft was released on TC39 website.
You can also check active proposals either here or on GitHub.

`String.prototype.replaceAll`

This is a convenience method that addresses a specific lack in String.prototype.replace.

Now you can easily replace all occurrences of a given string.

const str = "With great power comes great responsibility";

const str1 = str.replaceAll("great", "little");     // "With little power comes little responsibility"

Notice that both these methods return a new string, without affecting the original variable.

Before replaceAll was introduced, if you had to perform string-replacement you could already use the replace method. Things are fine with replace, unless you need to replace all the occurrences of a pattern with a new string.

For instance:

const str2 = str.replace("great", "little");     // "With little power comes great responsibility"

That's probably not exactly what you meant to say, right?
There is already an alternative way to use replace method and achieve what we wanted: we need to use regular expressions.

const str3 = str.replace(/great/g, "no");     // "With no power comes no responsibility"

Better this time. The catch is, you need to be careful and add the 'g' flag to your RegExp in order to make it a *g*lobal replacement. This means it's error prone, of course, because it's easy to forget it, and you won't notice unless you test your code with a string that needs global replacement.

Is that all? Well, to be honest, there isn't a single catch. Regular expressions are slower, but even worse, sometimes you might not know your pattern in advance:

function fillTemplateVar(template, tag, value) {
    return template.replace(tag, value);
}

The example above shows a typical situation where you would like to replace a pattern in some kind of template, something like <h1>{title}<h1>, were you you'd like to substitute the template-variable title with an actual title: fillTemplateVar('<h1>{title}<h1>', /\{title\}/g, someValue).

But if you need to replace the tags dynamically, and you get them passed as strings, that function wouldn't work unless you use a workaround:

fillTemplateVar('<h1>{title}<h1>', new RegExp(tag, 'g'), someValue)

Using replaceAll, instead, allows you to avoid an unnecessary conversion, and use strings comparison instead of regular expressions matching.

This method is not yet supported in NodeJs, but most browsers already implemented it.

`Promise.any`

Another method added to the language's toolbelt for handling promises. In ES2020 Promise.allSettled was added to run multiple promises in parallel and act when all of them were settled, either as fulfilled or as rejected.

This new method also takes an iterable (f.i. an array) of promises, but only resolves when either the first one of them is fulfilled, or all of the promises passed are rejected.

Promise.any([get('www.google.com'), get('www.twitter.com')])
    .then(result => {
        console.log('First promise settled: ', result)
    });

So, you might have noticed that this method is quite similar to an existing one, Promise.race, right? But here is the thing with race: it will settle when any of the promises is settled, it doesn't matter if by being rejected or fulfilled. Hence, in those situations where you try multiple solutions and are happy with at least one working and fulfilling its promise, the promise created by race method wouldn't be helpful.

Let's see an example, building an image roulette:

const p1 = new Promise((resolve, reject) => {
  reject("Rejected");
});

const p2 = new Promise((resolve, reject) => {
  setTimeout(resolve, 1500, "Resolved, but slowly");
});

const p3 = new Promise((resolve, reject) => {
  setTimeout(resolve, 100, "Resolved quickly");
});

// This is resolved, and logs "Resolved quickly"
Promise.any([p1, p2, p3]).then((value) => {
  console.log("Promise.any -> ", value);
});

// This is rejected
Promise.race([p1, p2, p3]).then((value) => {
  console.log("Promise.race -> ", value);
});

There is one question left to discuss: what happens if none of the promises passed is fulfilled?
In that situation (which includes the case where the iterator passed to any is empty), the method throws an AggregateError, a new type of exception contextually introduced in ES2021.

Support is still in development, only some browsers already implemented it, and it's not in NodeJs yet.

Numeric Separators

This is a cosmetic change that might have a low impact on the performance or cleanness of your JavaScript code, but it might help avoiding errors whenever you need to insert numeric values to your code (f.i. while defining constants).
Numeric Separators will make it easier to read these numeric values you define, by letting you use the underscore character _ as a separator between groups of digits.

You can use however many separators you like, and the groups of digits may be of any size - the only limitations are that you can't have two adjacent separators nor you can place them at either end of the number. A few examples will clarify:

const MILLION = 1_000_000;       // 1000000
const BILLION = 1_000_000_000;   // 1000000000

// You can break the digits in any way
const WHATEVER = 1234_5678_9_0;  // 1234567890

// And that's not limited to integers!
const PI = 3.1415_9265_3589;     // 3.141592653589

// Now, do not try this at home! 😁

const BAD_PI = 3.14_15_;          // SyntaxError
const NO_MILLION = _1_000_000;    // ReferenceError! 😱 
      // Remember that variable names can start with underscore... 😉

I don't know how much I'm going to use this feature, but the good news is that it is already supported in most browsers and in NodeJs since version 12.5.0, so we already have a choice.

`Intl.ListFormat`

Before we delve into this new feature, let's take a step back: the Intl object is the namespace for the ECMAScript Internationalization API, which provides a bunch of helper methods to support internalization efforts, like language-sensitive string comparison, number formatting, and date and time formatting.

In this case, the new constructor ListFormat creates and returns a formatter object that (depending on the configuration passed on creation) will join lists of strings using the best localized conventions.

I realize it's better shown than explained, so let's see an example:

let engFormatter = new Intl.ListFormat('en', { style: 'short', type: 'unit' } );
engFormatter.format(["1","2","3"])   // "1, 2, 3"

let engFormatter = new Intl.ListFormat('en', { style: 'narrow', type: 'unit' } );
engFormatter.format(["1","2","3"])   // "1 2 3"

engFormatter = new Intl.ListFormat('en', { style: 'long', type: 'conjunction' } );
engFormatter.format(["1","2","3"])   // "1, 2, and 3"

engFormatter = new Intl.ListFormat('en', { style: 'long', type: 'disjunction' } );
engFormatter.format(["1","2","3"])   //"1, 2, or 3"

The first optional argument for the ListFormat constructor is the language to be used - 'en' for English in our example. You can also pass an array of these BCP 47 language tags.

The second optional parameter is a POJO with three (also optional) fields:

"localeMatcher" sets the locale matching algorithm to be used; it can be either "lookup" or "best fit" (which is the default one).
"style", which affects the separators used to join the input strings, and can be either:
- "long": .format(["1", "2", "3"]) will result in "1, 2, and 3" (assuming that's the only option used).
- "short": .format(["1", "2", "3"]) should result in "1, 2, 3" (but in Chrome, it outputs "1, 2, & 3");
- "narrow": .format(["1", "2", "3"]) should result in "1 2 3".
"type", regulates the format of the output message; it can be:
- "conjunction", if we are trying to say that all the items in the list should be included (hence uses "and" before the last item, when style is "long");
- "disjunction", if we'd like to say that any of the items listed can be included (hence uses "or" before the last item, when style is "long");
- "unit", which doesn't use any separator for the last string. This option is the only officially valid option when "style" is set to "short" or "narrow".

At least in Chrome's current implementation (version 86), however, the behavior when mixing type and style options is not always the expected one.

New options for `Intl.DateTimeFormat`: `dateStyle` and `timeStyle`

Intl.DateTimeFormat is a constructor for a language-sensitive date and time formatter, long-supported in the JavaScript ecosystem.

These new options allow to control the length of the local-specific formatting of date and time strings.

Let's see how to use it with times...

let formatter = new Intl.DateTimeFormat('en' , { timeStyle: 'short' });
formatter.format(Date.now()); // "12:12 PM"

formatter = new Intl.DateTimeFormat('en' , { timeStyle: 'medium'})
formatter.format(Date.now()) // "12:12:57 PM"

formatter = new Intl.DateTimeFormat('en' , { timeStyle: 'long' })
formatter.format(Date.now()) // "12:12:36 PM GMT-5"

...and dates:

formatter = new Intl.DateTimeFormat('us' , { dateStyle: 'short' });
formatter.format(Date.now()); // "10/27/20"

formatter = new Intl.DateTimeFormat('us' , { dateStyle: 'medium' });
formatter.format(Date.now()); // "Oct 27, 2020"

formatter = new Intl.DateTimeFormat('us' , { dateStyle: 'long' });
formatter.format(Date.now()); // "October 27, 2020"

Obviously you can also combine the two options to get a date-time string:

formatter = new Intl.DateTimeFormat('uk' , { 
    timeStyle: 'long',
    dateStyle: 'short'
});
formatter.format(Date.now()); // "27.10.20, 12:20:54 GMT-5"

Logical Operators and Assignment Expressions

Finally, this new draft is about to make it official some already widely-supported assignment operators like ||= and &&=.

What's new in ES2020

Marcello La Rocca — Sun, 18 Oct 2020 17:31:13 +0000

We are closing down to the end of the year, 6 months into the approval of ES2020 specifications - and likely at least 6 months away from ES2021.

Before discussing rumors about next year's release, let's recap what was introduced in ES11, aka ES2020.

You can check how each feature is supported here:

kangax / kangax.github.com

List of my projects and resume

The nullish coalescing operator `??`

It's used to provide a default value in place of null and undefined (only).
Fixes the abuse of ||, which defaults on any falsy!

// With ?? the left operand is returned only with null and undefined
null ?? 1       // 1
undefined ?? 1  // 1
false ?? 1      // false
0 ?? 1          // 0
"" ?? 1         // ""
2 ?? 1          // 2
"a" ?? 1        // "a"
true ?? 1       // true     

// With || the left operand is returned only with all falsey values
null || 1       // 1
undefined || 1  // 1
false || 1      // 1
0 || 1          // 1
"" || 1         // 1
2 || 1          // 2
"a" || 1        // "a"
true || 1       // true

It's well supported already in browsers and NodeJs (from version 14).

Logical nullish assignment (??=)

The assignment version of the ?? operator is also introduced and supported.

It looks like your regular assignment operators: x ??= y, which reminds a lot logical assignment operators like ||=.

x ??= y, however, only assigns a new value to x if x is nullish (null or undefined).

Check the difference:

const car = {  speed: '150mph' };

car.speed ??= '241.4kmh';    // nothing changes

car.doors ??= 0;             // add property doors and set it to 0
car.doors ??= 3              // nothing changes, 0 isn't nullish     
car.doors||= 3               // sets cars.doors to 3

As you can see, it's particularly useful for objects, when you aren't sure if a property has been defined already and you don't want to risk overwriting it (but it can also be used with variables, like car ||= {};).

Optional Chaining `?.`

Allows access to nested object properties without worrying if the properties exist or not.

const car = {  speed: { value: 150, unit: 'mph'}, doors: 5 };

car.wheels.value             // TypeError: Cannot read property 'value' of undefined
car.wheels?.value            // undefined

car.speed?.value             // 150
car.speed?.whatever          // undefined 
car.speed?.whatever?.value   // undefined

Did you know that it can also be used for function calls?
Like this:

const car = {  
    speed: { 
        value: 150,
        unit: 'mph'
    },
    doors: 5,
    brake: x => console.log('braking')
};

car.accelerate        // TypeError: car.accelerate is not a function
car.accelerate?.()    // undefined

car.brake?.()         // logs "braking"

The coolest part is, this works so nicely together with the nullish coalescing operator, providing defaults whenever the property chain doesn't exist!

const car = {  speed: { value: 150, unit: 'mph'}, doors: 0 };

let wheels = car.wheels?.value ?? 4;     // 5
let doors = car.doors?.value ?? 3;       // 0, doors is not nullish!

Optional chaining is supported in modern browsers and NodeJs (starting with version 14).

`globalThis`

A single global object valid and consistent across all JS platforms.

Why is it important? Before ES2020, it was madness when you had to write cross-platform JavaScript referencing the global object.

You had to use:

window on browsers
global in NodeJs
self for web workers

Now instead, it works like a charm.

This feature is already supported in browsers and, of course, in NodeJs: let's double check...

In Chrome's console (check support here):

In NodeJs (since version 12.0.0):

`String.prototype.matchAll`

The matchAll method for strings allows you to iterate through all matched groups of a regular expression.

const regex = /([a-z]+)(\d*)/g;
const txt = "abc1 def ABC WXYZ xyz22 !§ $%& #|";

for (const w of txt.matchAll(regex)) {
    console.log(w);
}

With respect to String#match it allows access to the capture groups, which is particularly convenient to extract info from matched strings! For instance, for an email, you could more easily get username and domain.

Before matchAll, you still could get the same result, but you would have needed to run a loop where you called RegExp.exec

while (true) {
    const match = regex.exec(txt);
    if (match === null) {
        break; 
    }
    console.log(match);
}

This feature is supported in NodeJs since version 12.0.0, and also now widely supported in browsers.

`Promise.allSettled`

This new method takes an array of Promises and resolves once all of them are settled, one way or another (either resolved or rejected).

You can hence run a group of promises in parallel, but get a single "exit point" when all of them are completed - in practice allSettled created a new promise that is fulfilled when all of the original promises are either fulfilled or rejected.

Suppose you have a function that returns a Promise, something like fetch, which makes a http call.

We can use it to create an example where we have an array with 2 or more promises, and implement an action that will be performed only when all of these promises are settled:

Promise.allSettled([fetch('http://www.google.com'), fetch('http://www.twitter.com')])
    .then(results => {
        console.log('All settled', results)
    });

(Obviously the array passed to allSettled can also have promises with a completely different nature and origin, and that can take very different time to settle).

NodeJs supports this method since version 12.9, while you can check out support in browsers here.

Method Promise.all was already defined in ECMAScript specification, with a similar behavior and just a small, yet significant, difference: it will reject as soon as any of the promises passed is rejected.

BigInt

Finally JavaScript is introducing arbitrary-precision integers!

Before ES2020 the largest integer that could be represented and stored in JS was 2^53-1

let n = Number.MAX_SAFE_INTEGER;    // 9007199254740991
++n                                 // 9007199254740992
++n;                                // Still 9007199254740992!

Now the limit is your RAM! 😁

n = BigInt(Number.MAX_SAFE_INTEGER);    // 9007199254740991n
++n                                     // 9007199254740992n
++n;                                    // 9007199254740993n

Well, at least in theory, since each JS engine needs to put a limit, while implementing it, to the maximum size a BigInt can take - for instance, for V8, it's apparently around 16K (😱) bytes (which is still a lot!).

As you might have noticed, BigInts have a peculiarity, there is an 'n' appended at the end of the number's digits; when you declare a BigInt, to distinguish it from a regular int you also have to add that trailing 'n'. You can highlight the difference by checking the type returned with typeof.

let m = 9007199254740991n;
let bigInt=1n;
let num = 1;
typeof(bigInt);              // 'bigint'
typeof(num);                 // 'number'

As you can see in the my first example, it's also possible to convert an existing int value or variable:

let num = BigInt(4);   // 4n
let m = 42;            // 42
num = BigInt(m);       // 42n

Be careful, though, because the value to convert must be an integer, you can't pass a floating point to BigInt constructor:

For the same reason, you cannot mix BigInts and numbers in expressions: while it's kind of obvious for floating points, there is no automatic conversion for integers either:

So, you'll also need to explicitly convert integer values to BigInt:

let n = 4;
let m = BigInt(3n);
n * m          // TypeError: Cannot mix BigInt and other types, use explicit conversions
BigInt(n) * m  //12n

How is it supported, you might ask: NodeJs supports them since version 10.4.0, check out here for browsers.

Dynamic import

Dynamic import in JavaScript allows you to dynamically import JavaScript modules (or more in general, JavaScript files as modules) in your application. Before ES2020, you could do dynamic import through bundlers; now, this is supported natively.

let mymodule;
if (Math.random() < 0.5) {
    // Replace mymodule with a module you have installed!
    mymodule = import('mymodule');  
}
console.log(mymodule);

If you run this code snippet in node's console, half of the time it will print undefined, and half of the time the result of importing your module. You can leverage this to conditionally load one library or another (which, of course, only makes sense if their public interfaces are compatible, i.e. they expose the same methods... or if you find the right workaround).

For instance, something like:

let jsonModule, jsonParse;

if (condition) {
    jsonModule = import('json');
    jsonParse = jsonModule.parseJson;
} else {
    jsonModule = import('myJson');  
    jsonParse = jsonModule.parse;
}

let json = jsonParse(jsonText);

Check out which browsers support it here.

`import.meta`

We only have one last minor feature left to discuss for ES2020, the import.meta object.

This new property exposes context-specific metadata for a given JavaScript module. These data contain information about the module, specifically, at the moment, the module's URL.

$>node --experimental-modules --es-module-specifier-resolution=node temp.mjs

[Object: null prototype] {
  url: 'file://**/temp.mjs'
}

How is it supported? NodeJs supported it since version 10.4, and for what concerns browsers... check it out here.

Create and Draw Graphs in JavaScript with JsGraphs

Marcello La Rocca — Fri, 16 Oct 2020 14:33:42 +0000

JsGraphs is a lightweight library to model graphs, run graph algorithms, and display graphs in the browser.

In this post we'll see how you can use this library to create arbitrarily complex graphs and run algorithms and transformations on them, or just use visualize them in the browser, or save the drawing as an SVG. It's also possible to import graphs or even embeddings created in other languages/platforms and serialized using JSON.

Graphs can be embedded in the plane, vertices can be positioned arbitrarily, and both vertices and edges can be styled individually.

Getting Started

First things first: let's see how you can get started using this library.

NPM

JsGraphs is available on npm: assuming you have you do have npm installed, you just need to run
npm install -g @mlarocca/jsgraphs, to install it globally, or even better add it as a dependency in your project's package.json, and then run npm install (from the project's folder).

Once that's done, to import the library in your scripts, you can use either



import {default as jsgraphs} from '@mlarocca/jsgraphs';



const jsgraphs = require('@mlarocca/jsgraphs');`
```

depending on the module system you employ.

## **Local Clone**

You can also clone/fork JsGraph's [repo](https://github.com/mlarocca/jsgraphs) on GitHub and build the library from the source code.

### **Installation**

From the base folder:

```bash
nvm install stable

npm install
```

### **Run tests**

From the base folder:

```bash
npm t test/$FOLDER/$TEST
```

For instance

```bash
npm t test/geometric/test_point.js
```

### **Bundle**

To bundle the library, I used [Webpack](https://webpack.js.org) - but you can use whatever you like.

```bash
npm run bundle
```

A word of caution, though: the combination of ECMAScript modules and advanced features (ES2019) makes configuration non-trivial.

Check out how to configure babel plugins in [webpack.config.js](https://github.com/mlarocca/jsgraphs/edit/master/webpack.config.js).


# [**Graph Theory**](https://www.manning.com/books/algorithms-and-data-structures-in-action#toc)

How do you feel about graph theory? For an introduction to Graphs, feel free to take a look at ["Algorithms and Data Structures in Action"](https://github.com/mlarocca/AlgorithmsAndDataStructuresInAction#graph)

In particular you can check out online, on Manning's livebook site:

- [Chapter 14](https://livebook.manning.com/book/algorithms-and-data-structures-in-action/chapter-14) for an intro to graph data structure.
- [Appendix B](https://livebook.manning.com/book/algorithms-and-data-structures-in-action/appendix-b) for an intro to Big-O notation.
- [Appendix C](https://livebook.manning.com/book/algorithms-and-data-structures-in-action/appendix-c) for a summary of core data structures like trees or linked lists.

# **Overview**

There are two main entities that can be created in this library: graphs (class [_Graph_](https://github.com/mlarocca/jsgraphs/blob/master/src/graph/graph.js)) and embeddings ([_Embedding_](https://github.com/mlarocca/jsgraphs/blob/master/src/graph/embedding/embedding.js)).

The former focuses on modeling data and transforming it through algorithms, the latter is used to represent graphs on display (or paper!).

The rest of this post is a tutorial, showing how to programmatically create graphs and embeddings with just a few lines of code.

# **Graph**

A graph is a data structure that allows modeling interconnected data, where heterogeneous entities (the graph's vertices) can be in relation among them; these relationships are modeled by the graph's edges.

In _JsGraphs_, creating a graph is quite simple:

```javascript
import Graph from '/src/graph/graph.mjs';

let graph = new Graph();
```

The instance variable `graph` now has been created, without any vertex or edge. Of course, these entities are also modeled in the library:

## **Vertices**

Class [`Vertex`](https://github.com/mlarocca/jsgraphs/blob/master/src/graph/vertex.js) implement the first basic component of any graph, in turn modeling the entities (data) part of a graph.

### **Create a Vertex**

```javascript
import Vertex from '/src/graph/vertex.mjs';

const u = new Vertex('u');
const v = new Vertex('vertex name', {weight: 3, label: 'I am a label', data: [1, 2, 3]});
```

A vertex' name is forever, it can never be changed: it uniquely identifies a vertex, and in fact a vertex' ID is computed from its name.

On creation, you must add a name for the vertex, and optionally you can include:

- A weight: the default weight for a vertex is 1, and generally you don't have to worry about this weight, but some graph applications can use it.
- A label: an optional string that can be changed over time and used to convey non-identifying, mutable info about the vertex.
- Data: this is the most generic field for a vertex, it can include any serializable object, even another graph: this way, for instance, it's possible to create meta-graphs (graphs where each vertex is another graph) and run specific algorithms where whenever a vertex is visited, the graph it holds is also traversed (one example could be the graph of strongly connected components: breaking G into its SCCs, and then representing it with a new meta-graph, the SCC graph, whose vertices hold the actual components).

A vertex's name can either be a string or a number: any other type will be considered invalid.

It is possible to use the `static` method `Vertex.isValidName` to check if a value is a valid name:

```javascript
Vertex.isValidName(1);   // true
Vertex.isValidName('abc');   // true
Vertex.isValidName([1, 2, true, 'a']);   // false
Vertex.isValidName({a: [1, 2, 3], b: {x: -1, y: 0.5}});   // false
Vertex.isValidName(new Map());   // false
Vertex.isValidName(new Vertex('test'));   // false
```

Likewise, there are methods `Vertex.isValidLabel` and `Vertex.isValidData`. Labels must be strings (they are optional, so `null` and `undefined` are accepted to encode the absence of a value, and the empty string is also a valid label).
Data, instead, doesn't have to be a string, it can be any object that can be serialized to the `JSON` format: strings, numbers, arrays, plain JS objects, or custom objects that have a `toJson()` method.

```javascript
Vertex.isValidData(1);   // true
Vertex.isValidData('abc');   // true
Vertex.isValidData([1, 2, true, 'a']);   // true
Vertex.isValidData({a: [1, 2, 3], b: {x: -1, y: 0.5}});   // true
Vertex.isValidData(new Vertex('test'));   // true, Vertex has a toJson() method
Vertex.isValidData(new Graph());   // true!! Graph has a toJson() method

Vertex.isValidData(new Map());   // false
Vertex.isValidData(new Set());   // false
Vertex.isValidData(() => true));   // false, functions can't be serialized to JSON
```

Existing vertices can be added to graphs: notice that it's NOT possible to add two vertices with the same name to the same graph.

```javascript
let graph = new Graph();
const v = new Vertex('v', {weight: 3});
const u = new Vertex('u');

graph.addVertex(v);
graph.addVertex(u);
// graph.addVertex(new Vertex('u)) // ERROR, duplicated vertex 'u'
```

![A simple graph](https://dev-to-uploads.s3.amazonaws.com/i/6kwe6t4g6datf29em30f.jpg)

There is also a shortcut to create those vertices directly on the graph, without first creating them as a separate variable; besides being shorter, this way is also more efficient, because vertices (and edges) _added_ to a graph are actually cloned beforehand (meaning that, in the example above, a clone of `v` and `u` is actually added to `graph`).

```javascript
let graph = new Graph();

const vId = graph.createVertex(['I', 'am', 'a', 'valid', 'name'], {weight: 3});
const uId = graph.createVertex('u');
// graph.createVertex('u) // ERROR, duplicated vertex 'u'
```
### **Vertex ID**

As you can see in the snippet above, `createVertex` (as well as `addVertex`) returns the ID of the vertex created (NOT a reference to the actual instance held by the graph).

Each vertex, in fact, has an `id` property that uniquely identifies it in a graph: as mentioned, there can't be two vertices with the same name, so there is a 1:1 correspondence between names and IDs. This means that the IDs of two instances of `Vertex` can clash even if they are different objects, or if they have different properties.

```javascript
const u1 = new Vertex('u', {weight: 3});
const u2 = new Vertex('u');

console.log(u1.equals(u2));     // false
console.log(u1.id === u2.id);   // true
```

### **Retrieve a Vertex**

You might want to hold to the id of a vertex, because you will need it to retrieve a reference to the actual vertex from the graph, and even to create a new edge (as we'll see in the next section).

```javascript
const u = graph.getVertex(uId);
const v = graph.getVertex(vId);
```

Most of the methods on graphs can take either an id, or a copy of the object to retrieve (namely a vertex or an edge).
For instance:

```javascript
graph.getVertex(uId);
graph.getVertex(graph.getVertex(uId));
```

both work and return a reference to vertex `u` (although the latter does that very inefficiently!).

Once you get ahold of a reference to a graph's vertex, you can read all its fields, but you can only update its weight.


>  Although having vertices as perfectly immutable entities would have been desirable, this would have had repercussions on the performance of the graph, because updating a vertex `v`'s weight would have meant replacing `v` in the graph with a new instance of `Vertex`, and also updating all the references to `v` in (potentially, up to ) all the edges in the graph.
As a compromise, a vertex' name and id are kept immutable and impossible to change, while weight is mutable. Similar compromises will be made for embedded vertices and edges.
Switching to `TypeScript`, or whenever a future `EcmaScript` specification will include protected fields, would allow for more flexibility and possibly this aspect will be reviewed. For now, changing the mutable attributes of a graph's vertices and edges directly is **discouraged**: the **forward-compatible** way is going to be changing them through the `Graph` and `Embedding`'s methods.


## **Edges**

The other fundamental entity on which graphs are based are _edges_, implemented in class [`Edge`](https://github.com/mlarocca/jsgraphs/blob/master/src/graph/edge.js).

Creating a new edge is as simple as creating a new vertex, except that we need to pass two instances of `Vertex` to the edge's constructor, for its source and destination:

```javascript
import Vertex from '/src/graph/vertex.mjs';
import Edge from '/src/graph/edge.mjs';

const v = new Vertex('vertex name', {weight: 3});
const u = new Vertex('u');

const e = new Edge(u, v, {weight: 0.4, label: "I'm an edge!"});
```

Like vertices, Edges are only mutable for what concerns their weight: it's the only field of an edge that can be changed after it's created.

And likewise, edges also have an `id` field, that uniquely identify them in a graph: in simple graphs (like the ones implemented in classes `Graph` and `UndirectedGraph`), there can be at most a single edge between two vertices, so an edge's ID is based on the IDs of its source and destination, and can uniquely identify an edge _within a graph_.

Notice that two edges detached from any graph, or belonging to two different graphs, could be different while having the same ID (because, for instance, they have a different label or weight), but this is not possible within any individual graph.

### **Create an Edge**

You can add an existing edge to a graph with method `addEdge`, or equivalently (and perhaps more easily), you can create the new edge directly through an instance of `graph`:

```javascript
import Vertex from '/src/graph/vertex.mjs';
import Edge from '/src/graph/edge.mjs';
import Graph from '/src/graph/graph.mjs';

let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "I'm an edge!"});
```

![An edge](https://dev-to-uploads.s3.amazonaws.com/i/ytofdl0ahehbjhcbtl2d.jpg)

### **Directed vs Undirected**

While the vertices at the two ends of an edge uniquely determine the edge's ID, it has to be clear that their order matters, at least in directed graphs.

In directed graphs, in fact, each edge has a direction associated, from its source to its destination, and so an edge from vertex `'u'` to vertex `'v'` is different than one from `'v'` to `'u'`.

```javascript
let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e1 = g.createEdge(u, v, {weight: 0.4, label: "back"});
const e2 = g.createEdge(v, u, {weight: 1.4, label: "and forth"});
```

![A couple of edges](https://dev-to-uploads.s3.amazonaws.com/i/2p5gs6zxrivtp8yr6i4a.jpg)

### **Weight Matters**

While for vertices we saw that weight is something useful in niche situations, it's much more common to set a weight for edges: many graph's algorithms like _Dijkstra's_ or _A*_ make sense only on weighted graphs (while for unweighted graphs, i.e. graphs whose edges have no weights associated, we can likely make do with _BFS_).

In many applications we'll need to update the weight of graph edges after its creation: like for vertices, it is possible to retrieve an edge and update its weight, but the safest way to do so is by using the `setEdgeWeight` method on an instance of `Graph`.

```javascript
let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "back"});
g.setEdgeWeight(e, 1.5);
g.setEdgeWeight(e.id, -3.1);
```

### **Retrieving an Edge**

The easiest way to get ahold of a reference to a graph's edge is through its ID:

```javascript
let e = g.getEdge(e.id);
e = g.getEdge(edgeID);  // Assuming you have the ID stored in this variable
```

If you don't have the edge's ID at hand, though, do not despair! You can also retrieve an edge by passing its source and destination to method `getEdgeBetween` (since, as mentioned, there can only be one vertex in a simple graph from a source to a destination).

```javascript
let e = g.getEdgeBetween(u, v);
// You can also pass vertices' IDs
e = g.getEdgeBetween(u.id, v.id);
// ... and even mix them
e = g.getEdgeBetween(u, v.id);
e = g.getEdgeBetween(u.id, v);
```

### **Loops**

Last but not least, so far we have always assumed that the source and the destination of an edge are distinct: this doesn't necessarily need to be true. In other words, it's possible to have an edge starting from and ending to the same vertex: in this case, the edge is called a loop.

```javascript
let loop = g.createEdge(u, u, {label: 'Loop'});
```

![An edge and a loop](https://dev-to-uploads.s3.amazonaws.com/i/3pc9yjv45uxk1wnte0o8.jpg)

## **Graph class**

The only thing that still needs to be said about class `Graph` as a data structure is that it implements an undirected graph.

Class `Graph` implements directed graphs, where the direction of an edge matters.

If, instead, we don't care about that, and edges can be traveled in both directions, then the right class to use is `UndirectedGraph`.

Let's explore the difference with a couple of examples.

### **Generators**

Both classes offer generators to simplify the creation of some of the most common classes of graphs; in the following sections, we'll explore the available ones, and lay out the roadmap to implement more of these.

### **Complete Graphs**

In a complete graph, each vertex is connected by an edge to each other vertex in the graph; in these graphs, the number of edges is maximal for simple graphs, quadratic with respect to the number of vertices.

> Notice that a complete graph doesn't contain loops.

Creating complete graphs is easy, you just need to pass the number of vertices that the graph will hold:

```javascript
import { UndirectedGraph } from '/src/graph/graph.mjs';

let g = Graph.completeGraph(12);
let ug = UndirectedGraph.completeGraph(12);
```

Of course, the names for the vertices are standard, just the numbers between 1 and n.
The representation of such graphs is cool for both directed and undirected ones:

![A complete directed Graph](https://dev-to-uploads.s3.amazonaws.com/i/kxgnh9mx7r9ka2cnetuw.jpg)![A complete undirected Graph](https://dev-to-uploads.s3.amazonaws.com/i/v3zfa1nt7rkz9qtiijl7.jpg)

> We'll discuss how to get these drawings later, in the section about embeddings.

### **Bipartite Complete Graphs**

In a bipartite graph vertices can be partitioned in two groups, such that vertices in each group are only connected with vertices in the other group (in other words, each vertex in group A can't have any edge to another vertex within group A, and likewise for the other group).

A complete bipartite graph just has all the possible edges between the two groups: check the figures to get an idea.

```javascript
let g = Graph.completeBipartiteGraph(4, 6);   // Just pass the sizes of the two groups
let ug = UndirectedGraph.completeBipartiteGraph(7, 3);
```

![A complete bipartite directed Graph](https://dev-to-uploads.s3.amazonaws.com/i/5i0scgsp867mmns0fomc.jpg)![A complete bipartite undirected Graph](https://dev-to-uploads.s3.amazonaws.com/i/794rfx8y01ohy3gm5r7g.jpg)

### **Serialization**

Well, turns out there is another important thing to mention: _serialization_. All the entities in _JsGraphs_ are serializable to _JSON_, and can be created back from a _JSON_ file.

```javascript
let g = new Graph();
// ...
const json = g.toJson();
let g1 = Graph.fromJSON(json);
```
This is an important property (and the reason why we restricted the type of valid names), because it allows you to create a graph in any other platform/language, possibly run algorithms or transformations on it, and then export it to a _JSON_ file, pick it up in you web app with _JsGraphs_, and display it.

Or, vice versa, create it in JS (perhaps with an ad-hoc tool: stay tuned!), and then import it in your application written in any other language, or just store it in a **database** and retrieve it later.

As long as you adhere by the (simple) format used, compatibility is assured.

# **Embedding**

While many graphs' applications are interested in the result of applying one of the algorithms above, there are many, probably just as many, for which either the visual feedback or the actual way we lay out vertices and edges on a plane (or in a 3D space) are fundamental.

An embedding, and in particular a planar embedding, is technically an isomorphism...
but to keep things simple here, we can describe it as a way to assign a position to each vertex and draw each edge with a curve or polyline.

In this library, we will restrict the way in which we draw edges; they will be either:
- Straight line segments;
- Quadratic Bézier curves, with their control point lying on a line perpendicular to the edge and passing through its middle point.

This, obviously, restricts the set of possible ways to draw a graph (for instance, polylines or higher order curves are not allowed), but it allows a simpler approach, while still leaving plenty of options for nice and effective drawings.

We'll see how this simplification is important when we get to automatic embedding generators.

## **Of Appearance and Essence**

This dualism is common in computer science, so much so that there is one of the fundamental design patterns, _MVC_, that guides how the former should be separated from the latter.

Applied to graphs, the substance is the graph data structure, which has the maximum level of abstraction: it's a perfect candidate for the _Model_ part of MVC pattern.

In a way, an embedding is partly more about the form than the graph itself: we arrange vertices and edges as a way to _display_ a graph, to make it easier to comprehend to humans.

An embedding, however, can also be substance: for instance if vertices are electronic components on a circuit board, and edges are connective tracks, then their position is not just about appearance.

For our `Embedding` class, we have thus tried to separate form and substance accordingly: all the attributes that we can associate with an embedding's structure (its substance) can be passed to the constructor and modified using setters.

The form, for class `Embedding`, is the way we can later represent it: this is a separate concern, in line with MVC; regardless of whether we provide methods inside this class to generate the view, it's possible to write separate classes taking an embedding and generating a view.

The build-in methods to generate a view for an `Embedding` are `toJson`, to produce a _JSON_ representation of the embedding (and serialize/deserialize it), and - perhaps more interestingly - `toSvg` that generates _SVG_ markup for vertices and edges.

Again, this method is provided so that you have an out-of-the-box default way to display a graph, but it's decoupled from the model, relying on its public interface only, so that you can also write your own class to handle the view part.

This decoupling also translates to the fact that you will need to pass everything that is related to the _View_ (i.e. the form) to method `toSvg` directly (and each time you call it). More on this in a few lines...

## ***Create an Embedding...***

Embeddings creation works following the same logic as graphs: an embedding, in particular, is a collection of embedded vertices (class `EmbeddedVertex`), meaning graph's vertices to which we assigned a position with respect to some coordinate system, and embedded edges (class `EmbeddedEdge`), whose position is determined by the vertices at their ends, but for which we can still decide how they are drawn.

You should never worry about these two classes: although they are public classes and you can retrieve a reference to either through an instance of `Embedding`, you should never need to interact with those classes directly.

While it is true that the constructor for `Embedding` takes two collections as input, one of embedded vertices and one of embedded edges, there are easier ways to create an embedding from a graph.

### **... From a Graph**

The easiest way is to create an embedding starting from an existing graph:

```javascript
import Embedding from '/src/graph/embedding/embedding.mjs';

let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "back"});

let embedding = Embedding.forGraph(g, {width: 640, height: 480});
```

This will create an embedding for graph `g`, where the positions of the vertices are chosen randomly within a canvas of the specified size (in this case, a box spanning from `(0, 0)` to `(639, 479)`).

To control how the vertices and edges are laid out, we can pass two optional arguments to the static method `forGraph`:

- `vertexCoordinates`, a map between vertices' IDs and `Point2D` objects specifying where the vertex center will lie in the embedding;
- `edgeArcControlDistances`, another map, this time between edges' IDs and a parameter regulating how the edge is drawn (more on this later).

```javascript
let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v, {weight: 0.4, label: "back"});

let embedding = Embedding.forGraph(g, {
  width: 640,
  height: 480,
  vertexCoordinates: {
    [v]: new Point2D(100, 100),
    [u]: new Point2D(400, 300)
  },
  edgeArcControlDistances: {
    [e]: -60
  }
});
```

Alternatively, it's possible to change a vertex' position or an edge's control distance at any time, using:

```javascript
// Depending on your coordinate system, real (or even negative) coordinates can make sense
embedding.setVertexPosition(v, new Point2D(-1, -1));
embedding.setEdgeControlPoint(e, 3.14);
```

### **... or, with Generators**

The other suggested way to create embeddings is through generators. We have already seen how to speed up the creation of graphs for some of the most common types, like complete graphs for instance.

It is totally possible to create a graph first and then the embedding manually, like this:

```javascript
let g = Graph.completeGraph(9);
let embedding = Embedding.forGraph(g, {width: 480, height: 480});
```

The result, however, is not as appalling as you might expect, because the positions of the vertices are assigned randomly.

![A complete directed Graph](https://dev-to-uploads.s3.amazonaws.com/i/b8hbawhiym8h0luimxfl.jpg)

It's still possible to manually set the position of each vertex... but it's quite tedious, right?
Instead, we can use the matching generators provided by class `Embedding`, that will also automatically assign positions to the vertices in order to obtain a nice drawing.

```javascript
let embedding = Embedding.completeGraph(9, 480, false);
```

![An embedding for complete directed Graph](https://dev-to-uploads.s3.amazonaws.com/i/3ztaz24kf78fj1hrv945.jpg)

## **About Edge Drawing**

As already mentioned, we only allow edges to be drawn as line segments or arcs, in the form of quadratic Bézier curves.
If you need a primer on drawing arcs with Bézier curves, you can check out [this section](https://livebook.manning.com/book/algorithms-and-data-structures-in-action/chapter-15/v-14/329) of "Algorithms and Data Structures in Action".

These curves are a subset of second order polynomials whose trajectory is determined by a _control point_, that is going to be the third vertex in a triangle including the two ends of the curve.

The curve will then be the interpolation of the two linear Bézier curves between the first end and the control point, and between the control point and the second end of the curve.

For _JsGraphs_ we further restrict to only the quadratic Bézier curves whose control point lies on a line perpendicular to the segment connecting the two edge's ends, and passing in the middle point of said segment: the following figure illustrates this case:

![Using a quadratic curve to draw an edge](https://dev-to-uploads.s3.amazonaws.com/i/p5bajyp20flpqss63ur9.png

Notice that the distance between the control point and the two ends will always be the same, so the arc drawn for the edge will be symmetrical.

We can control the curvature of the arc by setting the distance of the control point from the segment on which the two ends lie, i.e. parameter `d` in the figure above: that's exactly the value set by method `setEdgeControlPoint`.

If we set this distance to `0`, we will draw the arc as a straight line segment; positive values will cause the edge's curve to point up, while negative values will make the curve point down.

```javascript
let g = new Graph();
const v = g.createVertex('v', {weight: 1.5});
const u = g.createVertex('u', {weight: 1.5});

const e = g.createEdge(u, v);

let embedding = Embedding.forGraph(g);

embedding.setVertexPosition(u, new Point2D(30, 60));
embedding.setVertexPosition(v, new Point2D(270, 60));

embedding.setEdgeControlPoint(e, 70);
// Draw 1
embedding.setEdgeControlPoint(e, 0);
// Draw 2
embedding.setEdgeControlPoint(e, -70);
// Draw 3
```

![Using a quadratic curve to draw an edge](https://dev-to-uploads.s3.amazonaws.com/i/za22dg0lxszg7de2z74k.jpg)

You can also find a deeper explanation of [Bézier curves](https://en.wikipedia.org/wiki/Bézier_curve#Quadratic_curves) on Wikipedia, and of how they work in SVG on [Mozilla's developer blog](https://developer.mozilla.org/en-US/docs/Web/SVG/Tutorial/Paths).

## **Styling**

Styling, i.e. the _appearance_ part, is mainly specified through CSS: each vertex and each edge can individually be assigned one or more CSS classes, at the moment the SVG is generated.

Additionally, there are a few parameters that can be tuned to enable/disable features, like displaying edges' labels and weights, or disabling arcs in favor of line segments.

It's also possible to assign CSS classes to the group containing the whole graph.

```javascript
let embedding = Embedding.forGraph(g);
// [...]
embedding.toSvg(700, 550, {
  graphCss: ['FSA'],          // This class is added to the whole graph, can be used as a selector
  verticesCss: {[u]: ['source'], [v]: ['dest', 'error'],
  edgesCss: {[e]: ['test1', 'test2']},
  drawEdgesAsArcs: true,      // Display edges as curves or segments
  displayEdgesLabel: false,  //  No label added to edges
  displayEdgesWeight: false   // Weights are not displayed either
})
```

The output will look something like:

```html
<svg width="300" height="120">

  <defs>
    <marker id="arrowhead" markerWidth="14" markerHeight="12" markerUnits="userSpaceOnUse" refX="13" refY="6" orient="auto">
      <polygon points="0 0, 14 6, 0 12" style="fill:var(--color-arrow)"/>
    </marker>
    <linearGradient id="linear-shape-gradient" x2="0.35" y2="1">
      <stop offset="0%" stop-color="var(--color-stop)" />
      <stop offset="30%" stop-color="var(--color-stop)" />
      <stop offset="100%" stop-color="var(--color-bot)" />
    </linearGradient>
    <radialGradient id="radial-shape-gradient" cx="50%" cy="50%" r="50%" fx="50%" fy="50%">
      <stop offset="0%" stop-color="var(--color-inner)" style="stop-opacity:1" />
      <stop offset="50%" stop-color="var(--color-mid)" style="stop-opacity:1" />
      <stop offset="100%" stop-color="var(--color-outer)" style="stop-opacity:1" />
    </radialGradient>
  </defs>
  <g class="graph FSA">
    <g class="edges">
      <g class="edge test1 test2" transform="translate(30,60)">
        <path d="M0,0 Q120,70 218,0"
        marker-end="url(#arrowhead)"/>
      </g>
    </g>
    <g class="vertices">
      <g class="vertex dest error" transform="translate(270,60)">
        <circle cx="0" cy="0" r="22.5" />
        <text x="0" y="0" text-anchor="middle" dominant-baseline="central">v</text>
      </g>
      <g class="vertex source" transform="translate(30,60)">
        <circle cx="0" cy="0" r="22.5" />
        <text x="0" y="0" text-anchor="middle" dominant-baseline="central">u</text>
      </g>
    </g>
  </g>
</svg>
```

Finally, an example of how a combination of different visualization styles and different structural changes (directed vs undirected edges) can impact how a graph is perceived:

![Different styles for a complete graph](https://dev-to-uploads.s3.amazonaws.com/i/di7qc9i153lqa0ucnsf3.jpg)


# **Graph Algorithms**

The most interesting part about graphs is that, once we have created one, we can run a ton of algorithms on it.

Here there is a list of algorithms that are implemented (or will be implemented) in _JsGraphs_:


## **BFS**

It's possible to run the **B**readth **F**irst **S**earch algorithm on both directed and undirected graphs.

```javascript
import { range } from '/src/common/numbers.mjs';

let g = new Graph();
range(1, 8).forEach(i => g.createVertex(`${i}`, {weight: 1.5})); // Create vertices "1" to "7"

g.createEdge(v1, v2);
g.createEdge(v1, v3);
g.createEdge(v2, v4);
g.createEdge(v3, v5);
g.createEdge(v3, v4);
g.createEdge(v4, v6);
g.createEdge(v6, v7);

const bfs = g.bfs('"1"');
```

If we print out the result of running bfs, we obtain an object with both the distance and predecessor of each vertex in the graph (at least, each one reachable from the start vertex, `"1"` in this case).

```javascript
{
  distance: {"1": 0, "2": 1, "3": 1, "4": 2, "5": 2, "6": 3, "7": 4},
  predecessor: {"1": null, "2": '"1"', "3": '"1"', "5": '"3"', "4": '"3"', "6": '"4"', "7": '"6"'}
}
```

That's not the easiest to visualize, though. One thing we can do is reconstruct the path from the start vertex to any of the reachable vertices (in this case, any other vertex in the graph, because they are all reachable from `"1"`).

The result of the `Graph.bfs` method, in fact, is an object, an instance of class `BfsResult`, that in turn offers an interesting method: `reconstructPathTo`. This method takes a destination vertex, and returns the shortest path (if any) from the starting point.

```javascript
bfs.reconstructPathTo('"7"');   // [""1"", ""3"", ""4"", ""6"", ""7""]
```

That's better, right? But how cooler would it be if we could also visualize it?
Well, luckily we can! Remember, from the [_Embedding_](#embedding) section, that we can assign custom _CSS_ classes to edges and vertices? Well, this is a good time to use that feature!

Let's start by creating an embedding for the graph:

```javascript
let embedding = Embedding.forGraph(g, {width: 480, height: 320});

embedding.setVertexPosition('"1"', new Point2D(30, 180));
embedding.setVertexPosition('"2"', new Point2D(120, 40));
embedding.setVertexPosition('"3"', new Point2D(150, 280));
embedding.setVertexPosition('"4"', new Point2D(200, 150));
embedding.setVertexPosition('"5"', new Point2D(300, 280));
embedding.setVertexPosition('"6"', new Point2D(350, 220));
embedding.setVertexPosition('"7"', new Point2D(450, 150));

embedding.setEdgeControlPoint('["2"]["4"]', 20);
embedding.toSvg(480, 320, {drawEdgesAsArcs: true, displayEdgesWeight: false});
```

At this point, the result of drawing the embedding is more or less the following:

![A directed graph](https://dev-to-uploads.s3.amazonaws.com/i/z1fswujto723pit8uwpj.jpg)

Now, we want to highlight that path, starting at vertex `"1"` and ending at vertex `"7"`. The issue with the result of `reconstructPathTo` is that it returns the sequence of vertices in the path, and while that does help us highlighting vertices, we would also like to assign a different css class to the edges in the path.

To do so, we also need to use method `Graph.getEdgesInPath`, that given a sequence of vertices, returns the edges connecting each adjacent pair.

Then, it's just up to us to choose the classes to assign to edges and vertices in the path.

```javascript
const path = bfs.reconstructPathTo('"7"');
const edges = g.getEdgesInPath(path);
let vCss = {};
path.forEach(v => vCss[v] = ['inpath']);
vCss['"1"'].push('start');
vCss['"7"'].push('end');

let eCss = {};
edges.forEach(e => eCss[e.id] = ['inpath']);

embedding.toSvg(480, 320, {
  drawEdgesAsArcs: true,
  displayEdgesWeight: false,
  verticesCss: vCss,
  edgesCss: eCss,
  graphCss: ['bfs']
});
```

This is the final result:

![A graph, with a shortest path highlighted](https://dev-to-uploads.s3.amazonaws.com/i/8ezxdcbe6yhvwuxqjipu.jpg)

Although aesthetically questionable 😉, it is significant of what can be achieved!
Of course, to get the style right, we need to add a few CSS rules, for instance:

```css
.graph.bfs g.vertex.inpath circle {
  stroke: crimson;
}
.graph.bfs g.vertex.start circle, .graph.bfs g.vertex.end circle {
  fill: darkorange;
  stroke-width: 7;
}
.graph.bfs g.vertex.start circle, .graph.bfs g.vertex.end text {
  fill: white;
}
.graph,bfs g.edge path {
  fill: none;
  stroke: black;
  stroke-width: 3;
}
.graph.bfs g.edge.inpath path {
  fill: none;
  stroke: crimson;
  stroke-width: 5;
}
```

# **Going Forward**

There are many more algorithms that can be implemented and run on graphs, and much more that can be done with JsGraphs.

The library is still being developed, and if you feel like contributing, how about starting by taking a look at the open [issues](https://github.com/mlarocca/jsgraphs/issues) on GitHub?

Ternary Search Tree: Core Methods (Java Implementation)

Marcello La Rocca — Wed, 14 Oct 2020 11:39:07 +0000

To better understand TST, it's important to look at some concrete implementations - in particular, I chose to use Java in this series.

mlarocca / AlgorithmsAndDataStructuresInAction

Advanced Data Structures Implementation

With recursive structures, like trees and lists, I usually define a class for the container, what will be shared with the clients and implement the public interface of the data structure, and a private class for the list/tree nodes.

public class Tst implements StringsTree {

    private TstNode root;
    public Tst() {
        root = null;
    }

    public Optional<String> search(String element) {
            return root == null || root.search(element) == null ? null : element;
    }
    ...
}

The Tst class is just a wrapper for the root of the tree, and all methods are just forwarded to their equivalents for the single nodes.

Of course, in Java you might also want to define an interface that sets in stone the behavior of the container, if you have another concrete class that can interchangeably perform the same operations (in this case we do, because we can implement a Trie class that has the exact same behavior), or in general if you want to decouple the abstract API from the concrete implementation.

The TstNode class is much more interesting than the tree wrapper, because it contains all the logic.

private class TstNode {

    private Character character;
    private boolean storesKey;

    private TstNode left;
    private TstNode middle;
    private TstNode right;

    public TstNode(String key) {
       ...
    }

It needs to have fields for the three children of a node, and for the character that each node holds.
I t also needs a way to mark nodes that stores a key: in this version of trie/tst, the containers are just sets, holding the strings stored in them, so I used a boolean flag; however, we can easily implement these trees as dictionaries (which will thenn associate a value to each key stored) by replacing the storesKey flag with a generic field for a value, for instance:

private class TstNode<T> {

    private Character character;
    private T value = null;

    private TstNode left = null;
    private TstNode middle = null;
    private TstNode right = null;

    public TstNode(String key, T value) {
        if (key.isEmpty() || value == null) {
            throw new IllegalArgumentException();
        }
        character = key.charAt(0);
        if (key.length() > 1) {
            // Stores the rest of the key in a midlle-link chain
            middle = new TstNode(key.substring(1), value);
        } else {
            this.value = value;
        }
    }

You can also see the implementation of the constructor for the dictionary version above. Obviously value could be any type inheriting from Object.

Constructing a new node to store a key-value pair is easy: we need to create a middle-link chain (which resembles a linked list, at this point!), so we take the first character in the string, store it in the currently-being-created node, and then (unless is was also the last character) create a sub-tree (or better, a sub-chain of nodes, linked through middle-links), that will be stored as the middle-child of current node.

Notice that value will be stored only in the very last node of the chain.

Adding a New Key-Value Pair

Once we have created our empty TST, we need a method to fill it with key/value pairs. This is probably the one method with which we need to be more careful when we write the TST wrapper, because we can deal with an empty root, and in that case we also assign it.

public boolean Tst<T>::add(String element, T value) {
    if (root == null) {
        root = new TstNode<T>(element, value);
        return true;
    } else {
        return root.add(element) != null;
    }
}

The core of the algorithm, however, still lies in the TstNode class.
In the listings above and below I omitted some of the checks on the arguments just for the sake of space: we want to make sure that the key is not null and not empty, and that the value is not null. We can perform those checks once per client call in Tst::add.

The figure below shows the results of adding words in the tongue-twister "she sells sea shells on the sea shore" to an empty TST. All words are added in the order they appear in the sentence, but we don't add duplicates ("sea" appears twice 😉).

Since we start with an empty tree (i.e. Tst::root is null), for the first word, "she", the method just creates a middle-link chain, a list of nodes holding those three characters. As we progress, more and more branches are created, each at the end if the common prefix of an existing word and the newly inserted one.

Let's pause before adding the last word in the sentence, "shore", and review how the add methods work: then we can use this word to detail a step-by-step example.

The first and most important thing that the method needs to check is (assuming key is not empty) how the first character in the key compares to the character stored in the current node.

(A) If it's a mismatch, we need to traverse the left (A.1) or right (A.2) branch respectively (depending on if it's smaller or larger); if the branch we need to traverse doesn't exist, then we can just create a new TstNode-chain that will store the rest of our key, connect it to the current node, and we are done.
(B) If we have a match, then the situation is more interesting. First, are we done with the input key, i.e. is this its last character?
- (B.1) If so, this is the node where we'll store value: to distinguish updates to an existing key, we check if a value was already stored in this node.
- (B.2) Otherwise, if there are more characters in key after the current one, then the situation can be handled like the ones for left/right branches, with one difference: since we have a match, we have to move to the next character in the input key.

private TstNode<T> TstNode<T>::add(String key, T value) {
    Character c = key.charAt(0);
    if (character.equals(c)) {                             // case B
        if (key.length() == 1) {                           // case B.1
            boolean updated = this.storesKey();
            this.value = value;
            // We return a non-null node only for insertion, and null for update
            return updated ? null : this;
        } else if (this.middle != null) {                  // case B.2.1
            return middle.add(key.substring(1));
        } else {                                           // case B.2.2
            this.middle = new TstNode<T>(key.substring(1));
            // We need to find the last node in the chain to return it
            return middle.search(key.substring(1));
        }
    } else if (c.compareTo(character) < 0) {               // case A.1
        if (this.left != null) {                           // case A.1.1
            return left.add(key, value);
        } else {                                           // case A.1.2
            left = new TstNode<T>(key, value);
            return left.search(key);
        }
    } else {                                               // case A.2
        if (this.right != null) {                          // case A.2.1
            return right.add(key, value);
        } else {                                           // case A.2.2
            right = new TstNode<T>(key, value);
            return right.search(key);
        }
    }
}

private boolean TstNode<T>::storesKey() {
    return this.value != null;
}

Above we also declare the storesKey method, that will be useful to abstract checking if a node is marked as "key node", regardless of the implementation.

As promised, here it is an example of the method in action, with a call to add("shore") illustrating a few of the cases that are highlighted in the code.

TST Lookup

As we have already seen, search works similarly to binary search trees: for each character c in our search string, we first need to find out if, in current sub-tree, there is a node that contains c and is reachable only through left/right links (we can only follow middle-links after a match!).

So, without losing generality, we can restrict to the case where we search for the first character in the string starting from the tree's root. Both strings and TSTs are recursive structures: each node in a TST is the root of a subtree, and a TST is either an empty tree (base case) or a node with left, middle and right - possibly empty - sub-trees).

To perform search, we can follow these steps:

We compare root's character to the first character in the string;
Case (A) They match: that's great, we found our string char. Now check: was this the last character in the string?
Case (A.1): Yes, it was the last one. Now we check if there is a value stored in the current node. If so we have found our search string, otherwise it's not in the tree.
Case (A.2) Otherwise, we move to the next character in the string and...
Case (A.2.1)...if there is no middle link for this node (i.e. it's a leaf), then the string is not in the tree.
Case (A.2.2)...if the middle link is not null, we follow the link and repeat the steps from 1.
Case (B) There is no match between our search string's char and our node's char. If the former is smaller we go left, if it's larger we go right.
Case (B.1) If the link we were supposed to follow is null (no left or right child respectively), then our search string is not in the tree.
Case (B.2) Otherwise, we just traverse the link and repeat from step 1.

The following figure illustrates some of the cases above on an example trie.

Let's put this into some Java code:

public TstNode<T> search(String key) {
    if (key.isEmpty()) {
        return null;
    }
    Character c = key.charAt(0);
    if (c.equals(this.character)) {                       // case A
        if (key.length() == 1) {                          // case A.1
            return this;
        } else {                                          //case A.2
            return this.middle == null 
                ? null                                    // case A.2.1
                : this.middle.search(key.substring(1));   // case A.2.2
        }
    } else if (c.compareTo(this.character) < 0) {         // case B.1
        return left == null ? null : left.search(key);
    } else {                                              // case B.2
        return right == null ? null : right.search(key);
    }
}

Now, in practice we would like to avoid all those calls to String::substring, because each of them needs to create a new string, and traversing a large tree this gets really expensive.

The good news is that we can easily find a workaround by just passing around the index of the next character to check. It's not as elegant, and we'll need to define a private method to keep the public API clean, but the efficiency boost we get is really worth it.

public T Tst<T>::search(String key) {
    TstNode node = search(key, 0);
    return  node != null && node.storesKey() ? node.value : null;
}

private TstNode<T> search(String key, int index) {
    if (index >= key.length()) {
        return null;
    }
    Character c = key.charAt(index);
    ...
}

Delete

The next base operation we would like to perform on a container is... removing elements.
Surprise surprise, this method follows the same structure as the other two: comparing the first character in the key passed, and then choosing the right branch to traverse depending on the result.

If it wasn't for a caveat, we could have implemented remove almost by cutting and pasting search.
Where is the catch? Well, if you think about it, what's always the catch, in Java but also in all other programming languages, when you delete something from a collection?

If we are not careful, of course, we won't free the space previously used.

You can see from the figure below that, for such trees like TSTs, there are cases where we can't free any space, because we are deleting a key stored in an internal node. But whenever we delete a key from a leaf, we can delete that node, and all its ancestors that both don't store any key/value, and have no siblings.

private boolean remove(String key, AtomicBoolean purge) {
    Character c = key.charAt(0);
    if (c.equals(this.character)) {
        if (key.length() == 1) {
            if (this.storesKey()) {
                value = null;
                // If this node stores a key, and it's a leaf, 
                // then the path to this node can be purged.
                purge.set(this.isLeaf());
                return true;
            } else {
                return false;
            }
        } else {
            boolean deleted = this.middle == null
                    ? false
                    : this.middle.remove(key.substring(1), purge);
            if (deleted && purge.get()) {
                this.middle = null;
                purge.set(!this.storesKey && this.isLeaf());
            }
            return deleted;
        }
    } else if (c.compareTo(this.character) < 0) {
        boolean deleted = left == null ? false : left.remove(key, purge);
        if (deleted && purge.get()) {
            this.left = null;
            purge.set(!this.storesKey() && this.isLeaf());
        }
        return deleted;
    } else {
        boolean deleted = right == null ? false : right.remove(key, purge);
        if (deleted && purge.get()) {
            this.right = null;
            purge.set(!this.storesKey() && this.isLeaf());
        }
        return deleted;
    }
}

The remove method is still conceptually easier than binary search tree's or, even worse, treaps, because we don't have to perform any rotation nor replace the deleted node with the minimum or maximum of its subtree.

We simply check, while backtracking, that we can remove the link we had traversed and, if so, if current node becomes itself eligible for being purged; the condition to meet is simple: a node can be purged when it's a leaf and it doesn't store a key.

Notice that, the way this method is implemented here, it will never purge the root of the tree. This won't cause problems, but if you'd like to go the extra mile, you'll need to check, in Tst::remove, if after the call to root.remove returns the AtomicBoolean flag purge is set to true: if that's the case, you can set root = null.

Performing this purging is not, however, mandatory: if we know that the rate between add and remove operations is highly skewed towards insertions (and possibly deleted keys get periodically re-inserted), or even better if we have a high ratio of reads-to-writes, we can decide it's not worth to get into the trouble of purging nodes.

Why would you not free-up deleted nodes? First and foremost, it allows you to write a shorter, cleaner and more efficient method: check out the difference in the following snippet, where we called this variant removeNGC as in "no garbage collection".

private boolean removeNGC(String key) {
    Character c = key.charAt(0);
    if (c.equals(this.character)) {
        if (key.length() == 1) {
            if (this.storesKey()) {
                value = null;
                return true;
            } else {
                return false;
            }
        } else {
            return this.middle == null
                   ? false
                   : this.middle.removeNGC(key.substring(1), purge);
        }
    } else if (c.compareTo(this.character) < 0) {
        return left == null ? false : left.removeNGC(key, purge);
    } else {
        return right == null ? false : right.removeNGC(key, purge);
    }
}

Moreover, the point is that if you expect the deleted keys to be added again shortly after, then clearing up those nodes and re-allocating them becomes a huge waste of resources.
So, how do you know which version you should implement? There is no answer but: study the context and requirements, and run some profiling - let the data suggest you what to do.

Conclusions

If you read it this far, you got an idea of how the core methods for TSTs work.
It's time to take a break to process all these new information, but stay tuned, I'll go over prefix search and how to use it for cool stuff like autocomplete or spell check in the next posts.

Ternary Search Trees

Marcello La Rocca — Sun, 11 Oct 2020 16:58:04 +0000

As good as they are, tries are not perfect, and allow for further improvement. In this post we will focus on one of their variants, ternary search trees, that trades search performance for greater memory-efficiency in storing nodes' children.

mlarocca / AlgorithmsAndDataStructuresInAction

Advanced Data Structures Implementation

What's Wrong with Tries?

Tries offer extremely good performance for many string-based operations. Due to their structure, though, they are meant to store an array of children (or a dictionary) for each node. This can quickly become expensive: the total number of edges for a trie with n elements can swing anywhere between |∑|*n and |∑|*n*m, where m is the average word length, depending on the degree of overlap of common prefixes.

We can use associative arrays, dictionaries in particular, in the implementation of nodes, thus only storing edges that are not-null. For instance, we can start with a small hash table, and grow it as we add more keys. But, of course, this solution comes at a cost: not only the cost to access each edge (that can be the cost of hashing the character, plus the cost of resolving key conflicts), but also the cost for resizing the dictionary when new edges are added.
Moreover, any data structure has an overhead in terms of memory it needs: in Java, each empty HashMap needs around 36 bytes plus some 32 byte for each entry stored (without considering the actual storage for each key/value), plus 4 bytes times the set's capacity.

An alternative solution that can help us reduce the space overhead associated with tries nodes is the ternary search trie (TST).
Take a look at an example of a TST, storing the following words: [“an”, “and”, “anti”, “end”, “so”, “top”, “tor”].
Only filled (red) nodes are "key nodes", those correspond to words stored in the tree, while empty (white) vertices are just internal nodes.

What's Good in Binary Search Trees?

Similarly to tries, nodes in a TST also need to store a Boolean value, to mark key nodes.
The first difference that you can spot, with respect to a trie, is that a TST stores characters in nodes, not in edges.
As a matter of fact, each TST node stores exactly three edges: to left, right, and middle children.

The "ternary search” part of the name should ring a bell, right? Indeed, TSTs work somehow similarly to BSTs, only with three links instead of two. This is because they associate a character to each node, and while traversing the tree, we will choose which branch to explore based on how the next character in the input string compares to the current node’s char.

Similarly to BSTs, in TSTs the three outgoing edges of a node N partition the keys in its subtree; if N, holds character c, and its prefix in the tree (the middle-node-path from the TST’s root to N, as we’ll see) is the string s, then the following invariants hold:

All keys sL stored in the left subtree of N starts with s, are longer (in terms of number of characters) than s, and lexicographically less than s+c: sL < s+c (or, to put it in another way, the next character in sL is lexicographically less than c: if |s|=m, sL[m] < c).
All keys sR stored in the right subtree of N starts with s, are longer than s, and lexicographically greater than s+c: sR > s+c.
All keys in the middle subtree of N start with s+c.

This is best illustrated with an example: check out the graphic above and try to work out, for each node, the sets of sub-strings that can be stored in its 3 branches.

Partitioning Keys

For instance, let's take the root of the tree:

Root's middle branch contains all keys starting with 'e';
The left branch contains all keys whose first character precedes 'e' in lexicographic ordering: so, considering only lower-case letters in he English alphabet, one of 'a', 'b', 'c', 'd';
Finally the right branch, which contains all keys that starts with letters from 'f' to 'z'.

When we traverse a TST, we keep track of a "search string", as we do with tries: for each node N, it's the string that could be stored in N, and it's determined by the path from the root to N. The way we build this search string is, however, very different with respect to tries.

As you can see from the example above, a peculiarity of TSTs is that a node's children have different meanings/functions.

The middle child is the one followed on characters match. It links a node N, whose path from root forms the string s, to a sub-tree containing all the stored keys that starts with s. When following the middle node we move one character forward in the search string.

The left and right children of a node, instead, doesn't let us advance in our path. If we had found i characters in a path from the root to N (i.e. we followed i middle links during traversal from root to N), and we traverse a left or right link, the current search string remains of length i.

Above, you can see an example of what happens when we follow a right-link. Differently from middle-links, we can't update the search string, so if on the left half current node corresponded to the word "and", on the right half the highlighted node, whose character is 't', corresponds to "ant": notice that there is no trace of traversing the previous node, holding 'd' (as there is also no trace of the root node, and it's like we didn't go through it, because our path had traversed a left-link from root to get to current node).

Left and right links, in other words, correspond to branching points after a common prefix: for "ant" and "and", for instance, after the first two characters (that can be stored only once, in the same path) we will need to branch out, to store both alternatives.

Which one gets the middle-link, and which one the left or right link? This is not determined beforehand, it only depends on the order they are inserted: first come, first serve! In the figure above, "and" was apparently stored before "anti".

Analysis

Well, TSTs look like a cool alternative to tries, but being cool is not enough for learning and implementing a new data structure with the same use case as another one in our toolbelt that's already well-tested and working fine, right? So we should talk a bit more about why we might want to prefer s TST.

Space

So, the question now arises: how many links (and nodes) are created for such TST?
To answer that, suppose we want to store n keys whose average length is w.
Then we can say that:

The minimum number of links needed we'll be w + n - 2: this is when all words share a prefix of length w-1, we have a middle-node path of |w-2| characters (and |w-1| nodes) from the root, and then we'll branch out n times at the very last character (with exactly 1 middle link, plus n-1 left/right links). An example of this edge case is shown in the figure below, with n=5 and w=4.
The worst case scenario happens when no two words share a common prefix, we need to branch out at the root, and then for each word we'll have w-2 middle-links, for a total of n*(w-1) links. This is shown in the figure below, with n=5 and w~=4.

Now that we have an idea of how to build these trees, in the next section, we will take a close look at search.

All other operations can be derived from tries in the same way, and can be implemented starting with a successful/unsuccessful search, or slightly modifying search.

Running Time

Performance-wise, a search hit or a search miss need, in the worst case, to traverse the longest path from the root to a leaf (there is no backtracking, so the longest path is a reliable measure of the cost of the worst case). That means search can perform at worst |A| * m characters comparisons (for completely skewed trees), where |A| is the size of the alphabet and m is the length of the searched string. Being the alphabet's size a constant, we can consider the time required for a successful search to be O(m) for a string of length m, and only differs for a constant factor from the trie's homologous.
It is also provable that, for a balanced TST storing n keys, a search miss requires O(log n) character comparisons at most (which is relevant for large alphabets, if |A| * m > n).

For remove: it can be performed as a successful search followed by some maintenance (performed during backtracking, it doesn't affect asymptotic analysis), and so its running time is also O(m) in the best case scenario, and an amortized O(log(n)) for unsuccessful removal.

Finally add: it's also a search (either successful or unsuccessful) followed by the creation of a node chain with at most m nodes. Its running time is, then, also O(|A|*m).

Conclusions

TSTs are a valid alternative to tries, trading a slightly worse constant in their running time with an effective saving in the memory used.

Both adhere to the same interface, and allow to implement efficiently some interesting searches on sets of strings.

The way TSTs are implemented, however, allow for a trade-off between memory (which can be considerably less that the one needed for a trie storing the same set of strings) and speed, where both data structures have the asymptotic behavior, but TSTs are a constant factor slower than tries.

In the next post in the series, we'll talk about a Java implementation for TSTs, so stay tuned because the most interesting material is still to come.

Implementing Tries in Java

Marcello La Rocca — Sat, 10 Oct 2020 16:33:41 +0000

Ever wondered how much memory is wasted when you store plain strings in a container, for instance in a binary search tree (BST)? Well, that heavily depends on how many strings you store, and how much they overlap.
Turns out, when you store strings with shared prefixes, you can save a lot of space by storing any duplicate only once.

That's the idea behind a trie (pronounced as try), a tree-like data structure that allows to more efficiently store and query large sets of strings, assuming many of them share some common prefixes.
Many applications manipulating strings, from spell-checkers to bioinformatics, can and do benefit from using tries.

In this post I am not going to describe tries in detail (you can take a look here for a refresher), but I'll present an overview of the methods they provide, and explain when and why they should be used.

mlarocca / AlgorithmsAndDataStructuresInAction

Advanced Data Structures Implementation

Why Trie? (Pun Intended)

First things first: why do we need tries again? After all, we have plenty of containers for strings, including hash tables and binary search trees (BST).

Balanced trees, in particular, guarantee logarithmic running time in the worst-case for all the main operations and, in the general case, when we don’t know anything about the data we need to store and (later) search, this is really the best we can hope.

But… what happens when we know that we will only store certain types of data in a container? There are several cases where we can leverage the information on the kind of data we need to handle to craft better algorithms than the general-purpose ones.

Take, for instance, sorting: it has been proven that it’s not possible to sort any generic list of n elements with less than O(n*log(n)) comparisons, but if we know that keys are integers in a limited range of k possible values, and k << n, we can use RadixSort, which means achieving an amortized O(n) running time, defying the lower bound for sorting by comparison.

Likewise, when we talk about containers, string containers are a special case that we can optimize both with respect to memory and running time.

How do Tries Work?

If we need to store strings whose characters are from an alphabet ∑ with |∑|=k symbols, we can implement a trie as a k-ary tree where each node has (at most) k children, each child marked with a different character in ∑; links to children can point to another node, or to null.

If we only show non-null links, this is what a trie storing words "a", "an", "and", "anti" etc... looks like:

A notable difference with binary and k-ary search trees is that nodes in a trie don't actually store the keys associated with them. Instead, the characters held in the trie are actually stored in the edges between a node and its children.

Each key is stored as a path in the trie, where each path's links are labeled after the characters in the key; black, fully-filled nodes mark the end of paths corresponding to keys stored in the trie, while empty (lighter) nodes are just intermediate nodes.

Some Java code should help clarify how a trie is implemented.

public class TrieNode {
    Map<Character, TrieNode> children;
    boolean storesKey;

    public TrieNode(String key) {
        children = new HashMap<>();
        if (key.isEmpty()) {
            storesKey = true;
        } else {
            storesKey = false;
            Character character = key.charAt(0);
            children.put(character, new TrieNode(key.substring(1)));
        }
    }

    public TrieNode() {
        children = new HashMap<>();
        storesKey = false;
    }
}

The code in this snippet is simplified by omitting validation and by using the inefficient String::substring method, just for the sake of space and clarity.
You can find a cleaned-up, more efficient implementation on GitHub.

If you'd like to read more about how tries are designed and structured, check out this section on Manning's livebook for "Algorithms and Data Structures in Action".

Memory

The memory saving that a trie can achieve in comparison to a BST depends on many factors, first of all the overhead for objects: since this trie has more nodes, the more this overhead is, the larger the delta will be.

Obviously, however, the shape of the tree and the actual number of nodes also play a big role: turns out, tries are more efficient when holding keys with a large shared prefix.

In the example below we assumed that each link needs a 64-bit pointer/reference, that each object has a 4-byte overhead, and a string with m characters takes m+1 bytes to be stored.

In these particular case, most trie nodes are filled (which means key nodes) and when the ratio of key nodes versus intermediate nodes is higher, intuitively it means that the efficiency of the trie is also higher, because when a path has more than one key node, we are storing at least two words in a single path (one of which is a prefix of the other): in a BST they would require two BST nodes storing both of the strings separately.

Another sign of a more efficient storage is when there are deep nodes branching out: in that case as well, the trie is "compressing" the space needed for two strings with a common prefix by storing the common prefix only once.

Running Time

Performance-wise, how fast is searching a string in a trie?
I'll discuss the search method in the next section, but let's take a look at its performance here - the only information you need at this time is that it's going to be a recursive method.

That's because the number of recursive calls search makes is limited by the smaller of two values: the maximum height of the trie and the length of the search string.
The latter is usually shorter than the former, but either way, for a string of length m we can be sure that no more than O(m) calls are going to be made, regardless of the number of keys stored in the trie.

Since each call can be implemented in such a way to require amortized constant time, the whole search takes O(m) amortized running time, while in a balanced BST storing strings the same search would need O(m*log(n)) amortized running time.

The same analysis can be extended to other operations like insert and remove.

But the advantage in using tries is even more apparent when we consider two particular operations:

Finding the longest prefix of a string s stored in the trie.
Finding all strings in the trie starting with a string s.

Both operations are O(m*n) in a BST, while in a trie the former is O(m), and latter is O(m+n).😱

We'll talk about those operations in detail later, in a different post in this series, but you can check how they are implemented for tries on GitHub.

Search

Assuming we have built a proper trie, how do we check if it contains a certain key?

It’s not that complicated, compared to a BST: the main difference is that we need to walk the tree one character (of the searched key) at the time, following the link that is marked precisely with that character.

Both strings and tries are recursive structures, whose unit of iteration is the single character; a string s, in fact, can be described as either:

The empty string "";
The concatenation of a character c and a string s': s=c+s', where s' is a string one character shorter than s, and can possibly be the empty string.

For instance, the string “word” is made of the character 'w' concatenated to the string “ord”, which in turn is 'o' + “rd” etc…, until we get to “d”, which can be written as the character 'd' concatenated to the empty string “”.

And since both strings and tries are recursive, it’s natural to define the search method recursively; we can restrict to consider just the case where we search the first character of a string s=c+s' starting from the root R of the a trie T.
If c, the first character of s, matches an outgoing of R, then we can search s' in the (sub)trie T'. We assume the root of the sub-trie is not null (it's a reasonable assumption, easy to guarantee in implementations).

If at any point s is the empty string, then we have traversed the whole path in the trie corresponding to s: we then need to check current node to verify if it is stored in the tree or not.

If, instead, at some point current node doesn’t have an outgoing edge matching current character c, then we are sure string s is not stored in the trie.

Code is worth a thousand words, so, let's look at the implementation of search:

public TrieNode search(String key) {
    if (key.isEmpty()) {
        return storesKey ? this : null;
    } else {
        Character character = key.charAt(0);
        if (children.containsKey(character)) {
            return children.get(character).search(key.substring(1));
        } else {
            return null;
        }
    }
}

Again, here I'm trying to provide the simplest, cleanest possible implementation - check out the repo for a more efficient and thorough version.

You can also check out a few examples and a more detailed explanation of this method in this section of the book.

Inserting a New Key

Insertion works similarly to search, it could actually be though of as a partially-successful search followed by a call to the constructor (the variant taking a string and creating a chain of nodes).

private boolean add(String key) {
    if (key.isEmpty()) {
        if (this.storesKey) {
            return false;
        } else {
            this.storesKey = true;
            return true;
        }
    } else {
        Character character = key.charAt(0);
        if (children.containsKey(character)) {
            return children.get(character).add(key.substring(1));
        } else {
            children.put(character, new TrieNode(key.substring(1)));
            return true;
        }
    }
}

Deleting a Key

In its simplest implementation, also remove can be implemented as a successful search followed by a key removal (which, in this implementation, means just setting the storesKey flag to false).

But... we can do better than that: in particular, we can decide to free up any unnecessary space held by nodes in branches of the tree that are not storing keys anymore.

In the example above, you can see that if we remove keys stored in a leaf, we can always free up at least one node, and sometimes many more; when, instead, we delete keys stored in internal nodes, there isn't the possibility to free any space.

I'll talk more diffusely about how to free-up space while deleting keys and how we can decide if we need to implement this clean-up in a later post, when describing TSTs; for the moment, let's take a look at the Java code for remove, with a version including freeing-up unused nodes.

private boolean remove(String key, AtomicBoolean purge) {
    if (key.isEmpty()) {
        if (storesKey) {
            storesKey = false;
            if (children.isEmpty()) {
                // We can always purge leaves
                purge.set(true);
            }
            return true;
        } else {
            return false;
        }
    } else {
        Character character = key.charAt(0);
        if (children.containsKey(character)) {
            boolean deleted = children.get(character).remove(key.substring(1), purge);
            if (deleted && purge.get()) {
                // If the node was deleted and this branch was purged up to this node, we can clean its old link
                children.remove(character);
                if (!children.isEmpty() || this.storesKey) {
                    // If there are other branches in the tree rooted at this node, we can't purge the trie any further
                    purge.set(false);
                }
            }
            return deleted;
        } else {
            return false;
        }
    }
}

Conclusions

This first post is a primer in the world of string containers and prefix trees.

Some takeaways from this post:

Tries take less memory than other general-purpose containers when you need to store many strings with a high degree of overlap: if there are many prefixes shared by two or more strings in the set, then tries are the answer.
Tries allow to implement core operations like search, insert and delete with a number of operations proportional to the length of the input string (regardless of how many keys are stored in the container). For general-purpose containers, the best we can get is O(m*log(n)), when there are n keys stored, and the input string has m characters.
Tries vastly outperform general-purpose containers on two key operations on sets of strings:
- Finding the longest prefix of an input string s;
- Enumerating all the strings starting with a certain prefix.

I feel this puts enough on readers' plate for a single post, but stay tuned, because in the next few posts I'll talk more about the core methods that makes these containers invaluable in many fields, including Bioinformatics: finding the longest prefix of a string and all enumerating all keys that have a string s as their prefix.

How to Catch Your Heisenbug 🐞

Marcello La Rocca — Mon, 21 Sep 2020 20:01:52 +0000

A few weeks ago, replying to a tweet about an elusive error, I realized that I hadn't seen much online advice about how to deal with this kind of bug.

What kind, you ask? Well, the kind that always stings you in production, but hides when you try to debug your code.
// Detect dark theme var iframe = document.getElementById('tweet-1293988357492690944-681'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1293988357492690944&theme=dark" }
So I thought, should I try to write something about it? And here we are!

This article won't provide the silver bullet that kills all heisenbugs - unfortunately, there isn't such a thing. It aims to describe the situations where these shifty errors can arise, so that you can try to avoid them first, and then discuss a few tips to hunt them down and save the day.

🐛 Son of a bug...

Strictly speaking, a Heisenbug is that kind of bug that disappears when you are debugging it 😨.
Yeah, I know, that sucks... it's the worst kind of bug.

A looser definition, though, also includes all those bugs that appear and disappear (apparently) at random, even in production.
These are also pretty nasty to solve.

Causes

There can be a few reasons for a bug to behave like a Heisenbug: when a bug is only noticeable in production, but hard to reproduce while debugging, usually it's the context that makes the difference:

Timing: if, while debugging, you run instructions line by line, the delay between operations might be orders of magnitude larger than in production; this is especially relevant when the Heisenbug is caused by the interaction of different thread.
Memory: During debug the addresses of variables might change; running code compiled without optimization might also cause some variables to be moved from registers to RAM, and this, in some languages/compilers, can affect the precision used for floating point comparisons.
Assertions: in production, or whenever your code is compiled with optimization options activated, assertions are usually disabled, while when compiling in dev mode locally they might likely be active (I got burnt myself many times because of this difference, especially with C++ or Python). Evaluating assertions might have side effects (though you should be careful for them not to have any) or simply affect the timing of execution.
Side-effects of debugging: adding logging or prints change the likelihood of the "wrong" interleaving between threads; the expressions checked in the debug's watches can have the same result, or even worse (if you are not careful) have side effects.
Latency: if you are running debug locally, or with mocked services, the latency of sync calls will be orders of magnitude smaller.
Race conditions: for the looser definition of Heisenbug, concurrent executions are highly non-deterministic (from the developer's point of view), because the execution depends on operating systems, and on the resources available at runtime. Many of these bugs only happen when certain edge conditions are faced.
Randomization: if you use randomization in your code, that might also cause inconsistencies across different runs, and the right conditions for your bug to happen might emerge discontinuously - for instance, in sorting a random list, edge cases (like already-sorted input, or empty input) might emerge only in rare cases.

What Can You Do?

Narrow down the portion of code where the bug happens. It's not always easy, because a race condition can cause an error to show up later in the execution, but you should try to focus on the smallest portion of code possible.
If you are running a data-transformation pipeline, store intermediate results at every step and compare them over multiple executions (or between local and production runs).
Check your code for random generators: try to test it by mocking the random generators, and track down the random output for both the happy and buggy runs.
Double check your input: sometimes different results are caused by slightly corrupted inputs - it's kind of a long shot, but by checking upfront either you rule it out early, or - in the lucky case this was it - you save wasting hours debugging your perfectly-working code.
Make sure that your patch fixed the error: with a Heisenbug it might be difficult to ensure that the bug was truly solved and not simply masked.
Run performance testing to identify bottlenecks, but also upfront, before a bug even shows up, to decide which critical areas need to be optimized, and if it's worth parallelizing execution (since it makes your code more fragile, limit concurrent execution to the critical areas, where you really get a sensible improvement).
Run stress tests to identify potential edge cases under extreme conditions. Remember that testing can only show the presence of bugs, it never proves their absence: stress tests help lower the chance of unnoticed (heisen)bugs unexpectedly popping up in production.
Use ad-hoc algorithms to detect potential race conditions:
- The lockset algorithm reports a potential race condition when shared memory is accessed by two or more threads without the threads holding a common lock. It might report false positives.
- The "happens-before" algorithm is based on partial ordering of events (i.e. any instruction, including read/write and locks) in distributed systems, within and across threads: if two or more threads access a shared variable, and the accesses are not deterministically ordered by the "happens-before" relationship, then it reports that a race have occurred. This algorithm generates very few false positives, but it's sensitive to the order of execution, so you might need to run it several times before catching a race condition that's causing a Heisenbug.
- Reverse debugging: the ability of a debugger to stop after a failure in a program has been observed, and go back into the history of the execution to uncover the reason for the failure.
Use ad-hoc debugging tools for race conditions. A few examples (there are many more):
Use a reverse debugging tool:
- Java: Chronon
- C++: UDB
- C#: RevDeBug
- Python: RevPDB

References and Links

Note: Why is it called a bug?🐜

The term "bug" was coined by computer pioneer Grace Hopper, who was working on early electromechanical computers, the Mark II and Mark III.

The story goes that, back in the early days of Mark II, Hopper traced an error in the Mark II's operation down to a moth trapped in a relay, which was then carefully removed and taped to the log book (see the posts's cover image).

That's why, from that first actual bug, today we call errors in code "a bug".

DEV Community: Marcello La Rocca

5 Tips to Pass Your Next Interview's Coding Exercise

Don't Rush It (unless you are asked to)

Read the Exercise

Clarify Requirements (or Make Explicit Assumptions)

Clarify Expectations

Test It (Thoroughly)

Conclusions

Java Profiling: comparing BSTs, tries and TSTs

Profiling Memory

Binary Search Tree

Trie

Ternary Search Tree

Tst Random Insertion Order

A note on using Optional

Profiling Running Time

Insertion

Shuffled List

Sorted List

Longest Shared Prefix

Conclusions

Prefix Search with Ternary Search Trees (Java Implementation)

longestPrefix

keysWithPrefix

Conclusions

New Features in ES2021

String.prototype.replaceAll

Promise.any

Numeric Separators

Intl.ListFormat

New options for Intl.DateTimeFormat: dateStyle and timeStyle

Logical Operators and Assignment Expressions

What's new in ES2020

kangax / kangax.github.com

List of my projects and resume

The nullish coalescing operator ??

Logical nullish assignment (??=)

Optional Chaining ?.

globalThis

String.prototype.matchAll

Promise.allSettled

BigInt

Dynamic import

import.meta

Create and Draw Graphs in JavaScript with JsGraphs

Getting Started

NPM

Ternary Search Tree: Core Methods (Java Implementation)

mlarocca / AlgorithmsAndDataStructuresInAction

Advanced Data Structures Implementation

Adding a New Key-Value Pair

TST Lookup

Delete

Conclusions

Ternary Search Trees

mlarocca / AlgorithmsAndDataStructuresInAction

Advanced Data Structures Implementation

What's Wrong with Tries?

What's Good in Binary Search Trees?

Partitioning Keys

Analysis

Space

Running Time

Conclusions

Implementing Tries in Java

mlarocca / AlgorithmsAndDataStructuresInAction

Advanced Data Structures Implementation

Why Trie? (Pun Intended)

How do Tries Work?

Memory

Running Time

Search

Inserting a New Key

Deleting a Key

Conclusions

How to Catch Your Heisenbug 🐞

🐛 Son of a bug...

Causes

What Can You Do?

References and Links

A note on using `Optional`

`longestPrefix`

`keysWithPrefix`

`String.prototype.replaceAll`

`Promise.any`

`Intl.ListFormat`

New options for `Intl.DateTimeFormat`: `dateStyle` and `timeStyle`

The nullish coalescing operator `??`

Optional Chaining `?.`

`globalThis`

`String.prototype.matchAll`

`Promise.allSettled`

`import.meta`