Welcome to the practical segment of our TypeScript programming journey! Today, we're applying the knowledge from past lessons to solve two practice problems using advanced TypeScript data structures: queues, deques, and binary search trees with custom class keys.

Consider an event-driven system, like a restaurant. Orders arrive, and they must be handled in the order they were received, following the First In, First Out (FIFO) principle. This principle makes it a perfect scenario for a queue or deque implementation in TypeScript.

TypeScript
Copy to clipboard
1class Queue<T> {
2    private buffer: T[];
3
4    constructor() {
5        // Initializing an empty queue
6        this.buffer = [];
7    }
8
9    // Adding (enqueueing) an item to the queue
10    enqueue(val: T): void {
11        this.buffer.unshift(val);
12    }
13
14    // Removing (dequeuing) an item from the queue
15    dequeue(): T | undefined {
16        return this.buffer.pop();
17    }
18
19    // Checking if the queue is empty
20    isEmpty(): boolean {
21        return this.buffer.length === 0;
22    }
23
24    // Checking the size (number of items) in the queue
25    size(): number {
26        return this.buffer.length;
27    }
28}
29
30// Example usage:
31const queue = new Queue<string>();
32queue.enqueue('order1');
33queue.enqueue('order2');
34console.log(queue.dequeue()); // Outputs 'order1'
35console.log(queue.isEmpty()); // Outputs false
36console.log(queue.size());    // Outputs 1

This code demonstrates the creation and operation of a Queue class, which leverages TypeScript arrays to efficiently implement a queue. The Queue class includes methods to enqueue (add) an item, dequeue (remove) an item, check if the queue is empty, and return the queue's size. Enqueue operations add an item to the beginning of the array (simulating the arrival of a new order), while dequeue operations remove an item from the end (simulating the serving of an order), maintaining the First In, First Out (FIFO) principle.

We've mimicked a real-world system by implementing a queue using TypeScript arrays. The use of TypeScript's type annotations ensures that our Queue class operates with enhanced type safety, reducing the risk of runtime errors by validating data types at compile time. The enqueuing of an item taps into the FIFO principle, similar to the action of receiving a new order at the restaurant. The dequeuing serves an order, reflecting the preparation and delivery of the order.

For the second problem, envision a leaderboard for a video game. Players with their scores can be represented as objects of a custom class, then stored in a binary search tree (BST) crafted using TypeScript. We will implement the BST, Player, and Leaderboard classes using the @datastructures-js/binary-search-tree library to maintain sorted order and efficient data accessibility.

TypeScript
Copy to clipboard
1import { BinarySearchTree } from '@datastructures-js/binary-search-tree';
2
3class Player {
4    name: string;
5    score: number;
6
7    constructor(name: string, score: number) {
8        this.name = name;
9        this.score = score;
10    }
11
12    compareTo(other: Player): number {
13        if (this.score === other.score) {
14            return this.name.localeCompare(other.name);
15        }
16        return this.score - other.score;
17    }
18
19    toString(): string {
20        return `(${this.name}, ${this.score})`;
21    }
22}
23
24class Leaderboard {
25    private bst: BinarySearchTree<Player>;
26
27    constructor() {
28        this.bst = new BinarySearchTree<Player>((playerA, playerB) => playerA.compareTo(playerB));
29    }
30
31    addPlayer(player: Player): void {
32        this.bst.insert(player);
33    }
34
35    removePlayer(player: Player): void {
36        this.bst.remove(player);
37    }
38
39    getTopPlayers(): Player[] {
40        const players: Player[] = [];
41        this.bst.traverseInOrder((node) => players.push(node.getValue()));
42        return players;
43    }
44}
45
46// Example usage:
47const scores = new Leaderboard();
48const player1 = new Player('John', 900);
49const player2 = new Player('Doe', 1000);
50
51scores.addPlayer(player1);
52scores.addPlayer(player2);
53
54for (const player of scores.getTopPlayers()) {
55    console.log(player.toString()); // Outputs '(John, 900)' then '(Doe, 1000)'
56}

This code snippet introduces a Player class for representing players in a video game, incorporating a custom comparator function to allow sorting by score (primary) and name (secondary). Instances of this class are then stored in a custom Leaderboard class using a binary search tree (BST) from the @datastructures-js/binary-search-tree library. The BST ensures that players are stored in sorted order based on their scores and names. This is essential for functionalities like leaderboards, where players need to be ranked efficiently according to their performance.

In our leaderboard system, we used a Player custom class with a comparator method for sorting. We stored instances of Player in a binary search tree (BST) with their corresponding scores. Implementing the BST using an external library allows us to leverage optimized operations and maintain type safety through TypeScript's type annotations, enhancing reliability in managing our data structure. The BST allows us to access player scores in a sorted order efficiently, a common requirement in a competitive gaming system.

We've successfully employed TypeScript’s built-in data structures — queues, deques, and binary search trees — to solve real-world problems. Our hands-on approach showcases TypeScript's robust type system, enforcing type safety and reducing potential errors at compile time. This journey through TypeScript-specific implementations and methodologies enhances the understanding of data structures and prepares us for more advanced exercises. Happy coding!