Welcome to our exploration of sorted maps using custom classes and comparators in TypeScript. In today's lesson, we'll learn how to use custom classes as keys in sorted maps. This approach enhances data organization and access. While TypeScript does not possess a built-in sorted map, we can use the @datastructures-js/binary-search-tree library to achieve this functionality, leveraging TypeScript’s robust type system to enforce type safety and clarity.
Custom classes enable us to create objects that align with our data requirements — for instance, a Person class for employee information or a Book class for a library database. In TypeScript, classes not only serve as blueprints for creating objects but also offer type annotations for ensuring type safety.
Consider this simple class, for example:
TypeScript1class Person { 2 name: string; 3 age: number; 4 5 constructor(name: string, age: number) { 6 this.name = name; 7 this.age = age; 8 } 9} 10 11let person = new Person("John Doe", 30); 12console.log(person.name); // Outputs "John Doe" 13console.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:
TypeScript1import { BinarySearchTree } from '@datastructures-js/binary-search-tree'; 2 3class Person { 4 name: string; 5 age: number; 6 occupation: string; 7 8 constructor(name: string, age: number, occupation: string) { 9 this.name = name; 10 this.age = age; 11 this.occupation = occupation; 12 } 13 14 compare(other: Person): number { 15 return this.age - other.age; 16 } 17 18 toString(): string { 19 return `${this.name} is a ${this.occupation}`; 20 } 21} 22 23let tree = new BinarySearchTree<Person>((a, b) => a.compare(b)); 24 25let john = new Person("John", 30, "Programmer"); 26let alice = new Person("Alice", 25, "Designer"); 27 28tree.insert(john); 29tree.insert(alice); 30 31// In-order traversal to print sorted entries 32tree.traverseInOrder((node) => { 33 console.log(node.getValue().toString()); 34}); 35// Output: 36// Alice is a Designer 37// John is a Programmer
In-order traversal is a method of traversing a binary search tree where nodes are visited in ascending order, ensuring sequential data access.
TypeScript's type annotations enforce type safety in comparator functions, ensuring that we only compare compatible types. To implement comparison logic, we add a compare method to our class, which maintains order during BST operations.
Below is another example of how to incorporate a different comparator:
TypeScript1import { BinarySearchTree } from '@datastructures-js/binary-search-tree'; 2 3class Person { 4 name: string; 5 age: number; 6 occupation: string; 7 8 constructor(name: string, age: number, occupation: string) { 9 this.name = name; 10 this.age = age; 11 this.occupation = occupation; 12 } 13 14 compare(other: Person): number { 15 // Different comparator: prioritize by occupation first, then by name 16 if (this.occupation === other.occupation) { 17 return this.name.localeCompare(other.name); 18 } 19 return this.occupation.localeCompare(other.occupation); 20 } 21 22 toString(): string { 23 return `${this.name} is a ${this.occupation}`; 24 } 25} 26 27let tree = new BinarySearchTree<Person>((a, b) => a.compare(b)); 28 29let john = new Person("John", 30, "Programmer"); 30let alice = new Person("Alice", 25, "Designer"); 31let bob = new Person("Bob", 27, "Programmer"); 32 33tree.insert(john); 34tree.insert(alice); 35tree.insert(bob); 36 37// In-order traversal to print sorted entries 38tree.traverseInOrder((node) => { 39 console.log(node.getValue().toString()); 40}); 41// Output: 42// Alice is a Designer 43// Bob is a Programmer 44// 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, all while leveraging TypeScript’s type system to ensure safety and clarity. Now, prepare for some hands-on exercises to reinforce these concepts.