Welcome to our exploration of sorted maps using custom classes and comparators in JavaScript. In today's lesson, we'll learn how to use custom classes as keys in sorted maps. This approach enhances data organization and access. Since JavaScript does not have direct support for sorted maps, we'll use a Binary Search Tree (BST) to achieve this functionality by leveraging the @datastructures-js/binary-search-tree library.
Custom classes enable us to create objects that fit our data — for instance, a Person class for employee information or a Book class for a library database. In JavaScript, classes are the blueprints for creating objects.
Consider this simple class, for example:
JavaScript1class Person { 2 constructor(name, age) { 3 this.name = name; 4 this.age = age; 5 } 6} 7 8let person = new Person("John Doe", 30); 9console.log(person.name); // Outputs "John Doe" 10console.log(person.age); // Outputs 30
Using custom classes helps organize complex multivariate data. We will use the @datastructures-js/binary-search-tree library to maintain our data in a sorted order. Below is an example of how to use comparators to dictate the order when using custom classes with this binary search tree:
JavaScript1const { BinarySearchTree } = require('@datastructures-js/binary-search-tree'); 2 3class Person { 4 constructor(name, age, occupation) { 5 this.name = name; 6 this.age = age; 7 this.occupation = occupation; 8 } 9 10 compare(other) { 11 return this.age - other.age; 12 } 13 14 toString() { 15 return `${this.name} is a ${this.occupation}`; 16 } 17} 18 19let tree = new BinarySearchTree((a, b) => a.compare(b)); 20 21let john = new Person("John", 30, "Programmer"); 22let alice = new Person("Alice", 25, "Designer"); 23 24tree.insert(john); 25tree.insert(alice); 26 27// In-order traversal to print sorted entries 28tree.traverseInOrder((person) => { 29 console.log(person.getValue().toString()); 30}); 31// Output: 32// Alice is a Designer 33// John is a Programmer
In-order traversal is a method of traversing a binary search tree where nodes are visited in ascending order. This means visiting the left subtree first, then the current node, and finally the right subtree. This ensures that data is accessed sequentially, from the smallest to the largest value.
JavaScript uses comparison functions to determine the order of two keys. To make this comparison, we add a compare method to our class. This method will be used within our binary search tree to maintain the order of keys during insertion.
Below is another example of how to incorporate a different comparator:
JavaScript1const { BinarySearchTree } = require('@datastructures-js/binary-search-tree'); 2 3class Person { 4 constructor(name, age, occupation) { 5 this.name = name; 6 this.age = age; 7 this.occupation = occupation; 8 } 9 10 compare(other) { 11 // Different comparator: prioritize by occupation first, then by name 12 if (this.occupation === other.occupation) { 13 return this.name.localeCompare(other.name); 14 } 15 return this.occupation.localeCompare(other.occupation); 16 } 17 18 toString() { 19 return `${this.name} is a ${this.occupation}`; 20 } 21} 22 23let tree = new BinarySearchTree((a, b) => a.compare(b)); 24 25let john = new Person("John", 30, "Programmer"); 26let alice = new Person("Alice", 25, "Designer"); 27let bob = new Person("Bob", 27, "Programmer"); 28 29tree.insert(john); 30tree.insert(alice); 31tree.insert(bob); 32 33// In-order traversal to print sorted entries 34tree.traverseInOrder((person) => { 35 console.log(person.getValue().toString()); 36}); 37// Output: 38// Alice is a Designer 39// Bob is a Programmer 40// John is a Programmer
We've explored how to use custom classes as keys in binary search trees and how comparators work in this context. Now, prepare for some hands-on exercises to reinforce these concepts.