Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
data-structure-typed
Advanced tools
data-structure-typed - npm Package Compare versions
Comparing version 1.53.2 to 1.53.3
@@ -11,3 +11,3 @@ # Changelog | ||
| ## [v1.53.2](https://github.com/zrwusa/data-structure-typed/compare/v1.51.5...main) (upcoming) | ||
| ## [v1.53.3](https://github.com/zrwusa/data-structure-typed/compare/v1.51.5...main) (upcoming) | ||
@@ -14,0 +14,0 @@ ### Changes |
@@ -20,2 +20,167 @@ /** | ||
| * 8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance. | ||
| * @example | ||
| * // Use Heap to sort an array | ||
| * function heapSort(arr: number[]): number[] { | ||
| * const heap = new Heap<number>(arr, { comparator: (a, b) => a - b }); | ||
| * const sorted: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * sorted.push(heap.poll()!); // Poll minimum element | ||
| * } | ||
| * return sorted; | ||
| * } | ||
| * | ||
| * const array = [5, 3, 8, 4, 1, 2]; | ||
| * console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8] | ||
| * @example | ||
| * // Use Heap to solve top k problems | ||
| * function topKElements(arr: number[], k: number): number[] { | ||
| * const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap | ||
| * arr.forEach(num => { | ||
| * heap.add(num); | ||
| * if (heap.size > k) heap.poll(); // Keep the heap size at K | ||
| * }); | ||
| * return heap.toArray(); | ||
| * } | ||
| * | ||
| * const numbers = [10, 30, 20, 5, 15, 25]; | ||
| * console.log(topKElements(numbers, 3)); // [15, 10, 5] | ||
| * @example | ||
| * // Use Heap to merge sorted sequences | ||
| * function mergeSortedSequences(sequences: number[][]): number[] { | ||
| * const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], { | ||
| * comparator: (a, b) => a.value - b.value // Min heap | ||
| * }); | ||
| * | ||
| * // Initialize heap | ||
| * sequences.forEach((seq, seqIndex) => { | ||
| * if (seq.length) { | ||
| * heap.add({ value: seq[0], seqIndex, itemIndex: 0 }); | ||
| * } | ||
| * }); | ||
| * | ||
| * const merged: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * const { value, seqIndex, itemIndex } = heap.poll()!; | ||
| * merged.push(value); | ||
| * | ||
| * if (itemIndex + 1 < sequences[seqIndex].length) { | ||
| * heap.add({ | ||
| * value: sequences[seqIndex][itemIndex + 1], | ||
| * seqIndex, | ||
| * itemIndex: itemIndex + 1 | ||
| * }); | ||
| * } | ||
| * } | ||
| * | ||
| * return merged; | ||
| * } | ||
| * | ||
| * const sequences = [ | ||
| * [1, 4, 7], | ||
| * [2, 5, 8], | ||
| * [3, 6, 9] | ||
| * ]; | ||
| * console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9] | ||
| * @example | ||
| * // Use Heap to dynamically maintain the median | ||
| * class MedianFinder { | ||
| * private low: MaxHeap<number>; // Max heap, stores the smaller half | ||
| * private high: MinHeap<number>; // Min heap, stores the larger half | ||
| * | ||
| * constructor() { | ||
| * this.low = new MaxHeap<number>([]); | ||
| * this.high = new MinHeap<number>([]); | ||
| * } | ||
| * | ||
| * addNum(num: number): void { | ||
| * if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num); | ||
| * else this.high.add(num); | ||
| * | ||
| * // Balance heaps | ||
| * if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!); | ||
| * else if (this.high.size > this.low.size) this.low.add(this.high.poll()!); | ||
| * } | ||
| * | ||
| * findMedian(): number { | ||
| * if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2; | ||
| * return this.low.peek()!; | ||
| * } | ||
| * } | ||
| * | ||
| * const medianFinder = new MedianFinder(); | ||
| * medianFinder.addNum(10); | ||
| * console.log(medianFinder.findMedian()); // 10 | ||
| * medianFinder.addNum(20); | ||
| * console.log(medianFinder.findMedian()); // 15 | ||
| * medianFinder.addNum(30); | ||
| * console.log(medianFinder.findMedian()); // 20 | ||
| * medianFinder.addNum(40); | ||
| * console.log(medianFinder.findMedian()); // 25 | ||
| * medianFinder.addNum(50); | ||
| * console.log(medianFinder.findMedian()); // 30 | ||
| * @example | ||
| * // Use Heap for load balancing | ||
| * function loadBalance(requests: number[], servers: number): number[] { | ||
| * const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap | ||
| * const serverLoads = new Array(servers).fill(0); | ||
| * | ||
| * for (let i = 0; i < servers; i++) { | ||
| * serverHeap.add({ id: i, load: 0 }); | ||
| * } | ||
| * | ||
| * requests.forEach(req => { | ||
| * const server = serverHeap.poll()!; | ||
| * serverLoads[server.id] += req; | ||
| * server.load += req; | ||
| * serverHeap.add(server); // The server after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return serverLoads; | ||
| * } | ||
| * | ||
| * const requests = [5, 2, 8, 3, 7]; | ||
| * console.log(loadBalance(requests, 3)); // [12, 8, 5] | ||
| * @example | ||
| * // Use Heap to schedule tasks | ||
| * type Task = [string, number]; | ||
| * | ||
| * function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> { | ||
| * const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap | ||
| * const allocation = new Map<number, Task[]>(); | ||
| * | ||
| * // Initialize the load on each machine | ||
| * for (let i = 0; i < machines; i++) { | ||
| * machineHeap.add({ id: i, load: 0 }); | ||
| * allocation.set(i, []); | ||
| * } | ||
| * | ||
| * // Assign tasks | ||
| * tasks.forEach(([task, load]) => { | ||
| * const machine = machineHeap.poll()!; | ||
| * allocation.get(machine.id)!.push([task, load]); | ||
| * machine.load += load; | ||
| * machineHeap.add(machine); // The machine after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return allocation; | ||
| * } | ||
| * | ||
| * const tasks: Task[] = [ | ||
| * ['Task1', 3], | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task4', 5], | ||
| * ['Task5', 4] | ||
| * ]; | ||
| * const expectedMap = new Map<number, Task[]>(); | ||
| * expectedMap.set(0, [ | ||
| * ['Task1', 3], | ||
| * ['Task4', 5] | ||
| * ]); | ||
| * expectedMap.set(1, [ | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task5', 4] | ||
| * ]); | ||
| * console.log(scheduleTasks(tasks, 2)); // expectedMap | ||
| */ | ||
@@ -22,0 +187,0 @@ export declare class Heap<E = any, R = any> extends IterableElementBase<E, R, Heap<E, R>> { |
@@ -22,2 +22,167 @@ "use strict"; | ||
| * 8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance. | ||
| * @example | ||
| * // Use Heap to sort an array | ||
| * function heapSort(arr: number[]): number[] { | ||
| * const heap = new Heap<number>(arr, { comparator: (a, b) => a - b }); | ||
| * const sorted: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * sorted.push(heap.poll()!); // Poll minimum element | ||
| * } | ||
| * return sorted; | ||
| * } | ||
| * | ||
| * const array = [5, 3, 8, 4, 1, 2]; | ||
| * console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8] | ||
| * @example | ||
| * // Use Heap to solve top k problems | ||
| * function topKElements(arr: number[], k: number): number[] { | ||
| * const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap | ||
| * arr.forEach(num => { | ||
| * heap.add(num); | ||
| * if (heap.size > k) heap.poll(); // Keep the heap size at K | ||
| * }); | ||
| * return heap.toArray(); | ||
| * } | ||
| * | ||
| * const numbers = [10, 30, 20, 5, 15, 25]; | ||
| * console.log(topKElements(numbers, 3)); // [15, 10, 5] | ||
| * @example | ||
| * // Use Heap to merge sorted sequences | ||
| * function mergeSortedSequences(sequences: number[][]): number[] { | ||
| * const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], { | ||
| * comparator: (a, b) => a.value - b.value // Min heap | ||
| * }); | ||
| * | ||
| * // Initialize heap | ||
| * sequences.forEach((seq, seqIndex) => { | ||
| * if (seq.length) { | ||
| * heap.add({ value: seq[0], seqIndex, itemIndex: 0 }); | ||
| * } | ||
| * }); | ||
| * | ||
| * const merged: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * const { value, seqIndex, itemIndex } = heap.poll()!; | ||
| * merged.push(value); | ||
| * | ||
| * if (itemIndex + 1 < sequences[seqIndex].length) { | ||
| * heap.add({ | ||
| * value: sequences[seqIndex][itemIndex + 1], | ||
| * seqIndex, | ||
| * itemIndex: itemIndex + 1 | ||
| * }); | ||
| * } | ||
| * } | ||
| * | ||
| * return merged; | ||
| * } | ||
| * | ||
| * const sequences = [ | ||
| * [1, 4, 7], | ||
| * [2, 5, 8], | ||
| * [3, 6, 9] | ||
| * ]; | ||
| * console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9] | ||
| * @example | ||
| * // Use Heap to dynamically maintain the median | ||
| * class MedianFinder { | ||
| * private low: MaxHeap<number>; // Max heap, stores the smaller half | ||
| * private high: MinHeap<number>; // Min heap, stores the larger half | ||
| * | ||
| * constructor() { | ||
| * this.low = new MaxHeap<number>([]); | ||
| * this.high = new MinHeap<number>([]); | ||
| * } | ||
| * | ||
| * addNum(num: number): void { | ||
| * if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num); | ||
| * else this.high.add(num); | ||
| * | ||
| * // Balance heaps | ||
| * if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!); | ||
| * else if (this.high.size > this.low.size) this.low.add(this.high.poll()!); | ||
| * } | ||
| * | ||
| * findMedian(): number { | ||
| * if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2; | ||
| * return this.low.peek()!; | ||
| * } | ||
| * } | ||
| * | ||
| * const medianFinder = new MedianFinder(); | ||
| * medianFinder.addNum(10); | ||
| * console.log(medianFinder.findMedian()); // 10 | ||
| * medianFinder.addNum(20); | ||
| * console.log(medianFinder.findMedian()); // 15 | ||
| * medianFinder.addNum(30); | ||
| * console.log(medianFinder.findMedian()); // 20 | ||
| * medianFinder.addNum(40); | ||
| * console.log(medianFinder.findMedian()); // 25 | ||
| * medianFinder.addNum(50); | ||
| * console.log(medianFinder.findMedian()); // 30 | ||
| * @example | ||
| * // Use Heap for load balancing | ||
| * function loadBalance(requests: number[], servers: number): number[] { | ||
| * const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap | ||
| * const serverLoads = new Array(servers).fill(0); | ||
| * | ||
| * for (let i = 0; i < servers; i++) { | ||
| * serverHeap.add({ id: i, load: 0 }); | ||
| * } | ||
| * | ||
| * requests.forEach(req => { | ||
| * const server = serverHeap.poll()!; | ||
| * serverLoads[server.id] += req; | ||
| * server.load += req; | ||
| * serverHeap.add(server); // The server after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return serverLoads; | ||
| * } | ||
| * | ||
| * const requests = [5, 2, 8, 3, 7]; | ||
| * console.log(loadBalance(requests, 3)); // [12, 8, 5] | ||
| * @example | ||
| * // Use Heap to schedule tasks | ||
| * type Task = [string, number]; | ||
| * | ||
| * function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> { | ||
| * const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap | ||
| * const allocation = new Map<number, Task[]>(); | ||
| * | ||
| * // Initialize the load on each machine | ||
| * for (let i = 0; i < machines; i++) { | ||
| * machineHeap.add({ id: i, load: 0 }); | ||
| * allocation.set(i, []); | ||
| * } | ||
| * | ||
| * // Assign tasks | ||
| * tasks.forEach(([task, load]) => { | ||
| * const machine = machineHeap.poll()!; | ||
| * allocation.get(machine.id)!.push([task, load]); | ||
| * machine.load += load; | ||
| * machineHeap.add(machine); // The machine after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return allocation; | ||
| * } | ||
| * | ||
| * const tasks: Task[] = [ | ||
| * ['Task1', 3], | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task4', 5], | ||
| * ['Task5', 4] | ||
| * ]; | ||
| * const expectedMap = new Map<number, Task[]>(); | ||
| * expectedMap.set(0, [ | ||
| * ['Task1', 3], | ||
| * ['Task4', 5] | ||
| * ]); | ||
| * expectedMap.set(1, [ | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task5', 4] | ||
| * ]); | ||
| * console.log(scheduleTasks(tasks, 2)); // expectedMap | ||
| */ | ||
@@ -24,0 +189,0 @@ class Heap extends base_1.IterableElementBase { |
@@ -62,2 +62,428 @@ /** | ||
| * 4. High Efficiency in Insertion and Deletion: Adding or removing elements in a linked list does not require moving other elements, making these operations more efficient than in arrays. | ||
| * @example | ||
| * // text editor operation history | ||
| * const actions = [ | ||
| * { type: 'insert', content: 'first line of text' }, | ||
| * { type: 'insert', content: 'second line of text' }, | ||
| * { type: 'delete', content: 'delete the first line' } | ||
| * ]; | ||
| * const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions); | ||
| * | ||
| * console.log(editorHistory.last?.type); // 'delete' | ||
| * console.log(editorHistory.pop()?.content); // 'delete the first line' | ||
| * console.log(editorHistory.last?.type); // 'insert' | ||
| * @example | ||
| * // Browser history | ||
| * const browserHistory = new DoublyLinkedList<string>(); | ||
| * | ||
| * browserHistory.push('home page'); | ||
| * browserHistory.push('search page'); | ||
| * browserHistory.push('details page'); | ||
| * | ||
| * console.log(browserHistory.last); // 'details page' | ||
| * console.log(browserHistory.pop()); // 'details page' | ||
| * console.log(browserHistory.last); // 'search page' | ||
| * @example | ||
| * // Use DoublyLinkedList to implement music player | ||
| * // Define the Song interface | ||
| * interface Song { | ||
| * title: string; | ||
| * artist: string; | ||
| * duration: number; // duration in seconds | ||
| * } | ||
| * | ||
| * class Player { | ||
| * private playlist: DoublyLinkedList<Song>; | ||
| * private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined; | ||
| * | ||
| * constructor(songs: Song[]) { | ||
| * this.playlist = new DoublyLinkedList<Song>(); | ||
| * songs.forEach(song => this.playlist.push(song)); | ||
| * this.currentSong = this.playlist.head; | ||
| * } | ||
| * | ||
| * // Play the next song in the playlist | ||
| * playNext(): Song | undefined { | ||
| * if (!this.currentSong?.next) { | ||
| * this.currentSong = this.playlist.head; // Loop to the first song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.next; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Play the previous song in the playlist | ||
| * playPrevious(): Song | undefined { | ||
| * if (!this.currentSong?.prev) { | ||
| * this.currentSong = this.playlist.tail; // Loop to the last song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.prev; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Get the current song | ||
| * getCurrentSong(): Song | undefined { | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Loop through the playlist twice | ||
| * loopThroughPlaylist(): Song[] { | ||
| * const playedSongs: Song[] = []; | ||
| * const initialNode = this.currentSong; | ||
| * | ||
| * // Loop through the playlist twice | ||
| * for (let i = 0; i < this.playlist.size * 2; i++) { | ||
| * playedSongs.push(this.currentSong!.value); | ||
| * this.currentSong = this.currentSong!.next || this.playlist.head; // Loop back to the start if needed | ||
| * } | ||
| * | ||
| * // Reset the current song to the initial song | ||
| * this.currentSong = initialNode; | ||
| * return playedSongs; | ||
| * } | ||
| * } | ||
| * | ||
| * const songs = [ | ||
| * { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * ]; | ||
| * let player = new Player(songs); | ||
| * // should play the next song | ||
| * player = new Player(songs); | ||
| * const firstSong = player.getCurrentSong(); | ||
| * const nextSong = player.playNext(); | ||
| * | ||
| * // Expect the next song to be "Hotel California by Eagles" | ||
| * console.log(nextSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * console.log(firstSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should play the previous song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * const currentSong = player.getCurrentSong(); | ||
| * const previousSong = player.playPrevious(); | ||
| * | ||
| * // Expect the previous song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(previousSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * console.log(currentSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * | ||
| * // should loop to the first song when playing next from the last song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const nextSongToFirst = player.playNext(); // Should loop to the first song | ||
| * | ||
| * // Expect the next song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(nextSongToFirst); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should loop to the last song when playing previous from the first song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the first song | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const previousToLast = player.playPrevious(); // Should loop to the last song | ||
| * | ||
| * // Expect the previous song to be "Billie Jean by Michael Jackson" | ||
| * console.log(previousToLast); // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * | ||
| * // should loop through the entire playlist | ||
| * player = new Player(songs); | ||
| * const playedSongs = player.loopThroughPlaylist(); | ||
| * | ||
| * // The expected order of songs for two loops | ||
| * console.log(playedSongs); // [ | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }, | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * // ] | ||
| * @example | ||
| * // Use DoublyLinkedList to implement LRU cache | ||
| * interface CacheEntry<K, V> { | ||
| * key: K; | ||
| * value: V; | ||
| * } | ||
| * | ||
| * class LRUCache<K = string, V = any> { | ||
| * private readonly capacity: number; | ||
| * private list: DoublyLinkedList<CacheEntry<K, V>>; | ||
| * private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>; | ||
| * | ||
| * constructor(capacity: number) { | ||
| * if (capacity <= 0) { | ||
| * throw new Error('lru cache capacity must be greater than 0'); | ||
| * } | ||
| * this.capacity = capacity; | ||
| * this.list = new DoublyLinkedList<CacheEntry<K, V>>(); | ||
| * this.map = new Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>(); | ||
| * } | ||
| * | ||
| * // Get cached value | ||
| * get(key: K): V | undefined { | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (!node) return undefined; | ||
| * | ||
| * // Move the visited node to the head of the linked list (most recently used) | ||
| * this.moveToFront(node); | ||
| * | ||
| * return node.value.value; | ||
| * } | ||
| * | ||
| * // Set cache value | ||
| * set(key: K, value: V): void { | ||
| * // Check if it already exists | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (node) { | ||
| * // Update value and move to head | ||
| * node.value.value = value; | ||
| * this.moveToFront(node); | ||
| * return; | ||
| * } | ||
| * | ||
| * // Check capacity | ||
| * if (this.list.size >= this.capacity) { | ||
| * // Delete the least recently used element (the tail of the linked list) | ||
| * const removedNode = this.list.tail; | ||
| * if (removedNode) { | ||
| * this.map.delete(removedNode.value.key); | ||
| * this.list.pop(); | ||
| * } | ||
| * } | ||
| * | ||
| * // Create new node and add to head | ||
| * const newEntry: CacheEntry<K, V> = { key, value }; | ||
| * this.list.unshift(newEntry); | ||
| * | ||
| * // Save node reference in map | ||
| * const newNode = this.list.head; | ||
| * if (newNode) { | ||
| * this.map.set(key, newNode); | ||
| * } | ||
| * } | ||
| * | ||
| * // Move the node to the head of the linked list | ||
| * private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void { | ||
| * this.list.delete(node); | ||
| * this.list.unshift(node.value); | ||
| * } | ||
| * | ||
| * // Delete specific key | ||
| * delete(key: K): boolean { | ||
| * const node = this.map.get(key); | ||
| * if (!node) return false; | ||
| * | ||
| * // Remove from linked list | ||
| * this.list.delete(node); | ||
| * // Remove from map | ||
| * this.map.delete(key); | ||
| * | ||
| * return true; | ||
| * } | ||
| * | ||
| * // Clear cache | ||
| * clear(): void { | ||
| * this.list.clear(); | ||
| * this.map.clear(); | ||
| * } | ||
| * | ||
| * // Get the current cache size | ||
| * get size(): number { | ||
| * return this.list.size; | ||
| * } | ||
| * | ||
| * // Check if it is empty | ||
| * get isEmpty(): boolean { | ||
| * return this.list.isEmpty(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should set and get values correctly | ||
| * const cache = new LRUCache<string, number>(3); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * | ||
| * // The least recently used element should be evicted when capacity is exceeded | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * cache.set('d', 4); // This will eliminate 'a' | ||
| * | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // The priority of an element should be updated when it is accessed | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * cache.get('a'); // access 'a' | ||
| * cache.set('d', 4); // This will eliminate 'b' | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')).toBeUndefined(); | ||
| * expect(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // Should support updating existing keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('a', 10); | ||
| * | ||
| * console.log(cache.get('a')); // 10 | ||
| * | ||
| * // Should support deleting specified keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * | ||
| * console.log(cache.delete('a')); // true | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.size); // 1 | ||
| * | ||
| * // Should support clearing cache | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.clear(); | ||
| * | ||
| * console.log(cache.size); // 0 | ||
| * console.log(cache.isEmpty); // true | ||
| * @example | ||
| * // finding lyrics by timestamp in Coldplay's "Fix You" | ||
| * // Create a DoublyLinkedList to store song lyrics with timestamps | ||
| * const lyricsList = new DoublyLinkedList<{ time: number; text: string }>(); | ||
| * | ||
| * // Detailed lyrics with precise timestamps (in milliseconds) | ||
| * const lyrics = [ | ||
| * { time: 0, text: "When you try your best, but you don't succeed" }, | ||
| * { time: 4000, text: 'When you get what you want, but not what you need' }, | ||
| * { time: 8000, text: "When you feel so tired, but you can't sleep" }, | ||
| * { time: 12000, text: 'Stuck in reverse' }, | ||
| * { time: 16000, text: 'And the tears come streaming down your face' }, | ||
| * { time: 20000, text: "When you lose something you can't replace" }, | ||
| * { time: 24000, text: 'When you love someone, but it goes to waste' }, | ||
| * { time: 28000, text: 'Could it be worse?' }, | ||
| * { time: 32000, text: 'Lights will guide you home' }, | ||
| * { time: 36000, text: 'And ignite your bones' }, | ||
| * { time: 40000, text: 'And I will try to fix you' } | ||
| * ]; | ||
| * | ||
| * // Populate the DoublyLinkedList with lyrics | ||
| * lyrics.forEach(lyric => lyricsList.push(lyric)); | ||
| * | ||
| * // Test different scenarios of lyric synchronization | ||
| * | ||
| * // 1. Find lyric at exact timestamp | ||
| * const exactTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 36000); | ||
| * console.log(exactTimeLyric?.text); // 'And ignite your bones' | ||
| * | ||
| * // 2. Find lyric between timestamps | ||
| * const betweenTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 22000); | ||
| * console.log(betweenTimeLyric?.text); // "When you lose something you can't replace" | ||
| * | ||
| * // 3. Find first lyric when timestamp is less than first entry | ||
| * const earlyTimeLyric = lyricsList.findBackward(lyric => lyric.time <= -1000); | ||
| * console.log(earlyTimeLyric).toBeUndefined(); | ||
| * | ||
| * // 4. Find last lyric when timestamp is after last entry | ||
| * const lateTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 50000); | ||
| * expect(lateTimeLyric?.text); // 'And I will try to fix you' | ||
| * @example | ||
| * // cpu process schedules | ||
| * class Process { | ||
| * constructor( | ||
| * public id: number, | ||
| * public priority: number | ||
| * ) {} | ||
| * | ||
| * execute(): string { | ||
| * return `Process ${this.id} executed.`; | ||
| * } | ||
| * } | ||
| * | ||
| * class Scheduler { | ||
| * private queue: DoublyLinkedList<Process>; | ||
| * | ||
| * constructor() { | ||
| * this.queue = new DoublyLinkedList<Process>(); | ||
| * } | ||
| * | ||
| * addProcess(process: Process): void { | ||
| * // Insert processes into a queue based on priority, keeping priority in descending order | ||
| * let current = this.queue.head; | ||
| * while (current && current.value.priority >= process.priority) { | ||
| * current = current.next; | ||
| * } | ||
| * | ||
| * if (!current) { | ||
| * this.queue.push(process); | ||
| * } else { | ||
| * this.queue.addBefore(current, process); | ||
| * } | ||
| * } | ||
| * | ||
| * executeNext(): string | undefined { | ||
| * // Execute tasks at the head of the queue in order | ||
| * const process = this.queue.shift(); | ||
| * return process ? process.execute() : undefined; | ||
| * } | ||
| * | ||
| * listProcesses(): string[] { | ||
| * return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`); | ||
| * } | ||
| * | ||
| * clear(): void { | ||
| * this.queue.clear(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should add processes based on priority | ||
| * let scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * scheduler.addProcess(new Process(3, 15)); | ||
| * | ||
| * console.log(scheduler.listProcesses()); // [ | ||
| * // 'Process 2 (Priority: 20)', | ||
| * // 'Process 3 (Priority: 15)', | ||
| * // 'Process 1 (Priority: 10)' | ||
| * // ] | ||
| * | ||
| * // should execute the highest priority process | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * console.log(scheduler.executeNext()); // 'Process 2 executed.' | ||
| * console.log(scheduler.listProcesses()); // ['Process 1 (Priority: 10)'] | ||
| * | ||
| * // should clear all processes | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * scheduler.clear(); | ||
| * console.log(scheduler.listProcesses()); // [] | ||
| */ | ||
@@ -64,0 +490,0 @@ export declare class DoublyLinkedList<E = any, R = any> extends IterableElementBase<E, R, DoublyLinkedList<E, R>> { |
@@ -71,2 +71,428 @@ "use strict"; | ||
| * 4. High Efficiency in Insertion and Deletion: Adding or removing elements in a linked list does not require moving other elements, making these operations more efficient than in arrays. | ||
| * @example | ||
| * // text editor operation history | ||
| * const actions = [ | ||
| * { type: 'insert', content: 'first line of text' }, | ||
| * { type: 'insert', content: 'second line of text' }, | ||
| * { type: 'delete', content: 'delete the first line' } | ||
| * ]; | ||
| * const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions); | ||
| * | ||
| * console.log(editorHistory.last?.type); // 'delete' | ||
| * console.log(editorHistory.pop()?.content); // 'delete the first line' | ||
| * console.log(editorHistory.last?.type); // 'insert' | ||
| * @example | ||
| * // Browser history | ||
| * const browserHistory = new DoublyLinkedList<string>(); | ||
| * | ||
| * browserHistory.push('home page'); | ||
| * browserHistory.push('search page'); | ||
| * browserHistory.push('details page'); | ||
| * | ||
| * console.log(browserHistory.last); // 'details page' | ||
| * console.log(browserHistory.pop()); // 'details page' | ||
| * console.log(browserHistory.last); // 'search page' | ||
| * @example | ||
| * // Use DoublyLinkedList to implement music player | ||
| * // Define the Song interface | ||
| * interface Song { | ||
| * title: string; | ||
| * artist: string; | ||
| * duration: number; // duration in seconds | ||
| * } | ||
| * | ||
| * class Player { | ||
| * private playlist: DoublyLinkedList<Song>; | ||
| * private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined; | ||
| * | ||
| * constructor(songs: Song[]) { | ||
| * this.playlist = new DoublyLinkedList<Song>(); | ||
| * songs.forEach(song => this.playlist.push(song)); | ||
| * this.currentSong = this.playlist.head; | ||
| * } | ||
| * | ||
| * // Play the next song in the playlist | ||
| * playNext(): Song | undefined { | ||
| * if (!this.currentSong?.next) { | ||
| * this.currentSong = this.playlist.head; // Loop to the first song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.next; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Play the previous song in the playlist | ||
| * playPrevious(): Song | undefined { | ||
| * if (!this.currentSong?.prev) { | ||
| * this.currentSong = this.playlist.tail; // Loop to the last song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.prev; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Get the current song | ||
| * getCurrentSong(): Song | undefined { | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Loop through the playlist twice | ||
| * loopThroughPlaylist(): Song[] { | ||
| * const playedSongs: Song[] = []; | ||
| * const initialNode = this.currentSong; | ||
| * | ||
| * // Loop through the playlist twice | ||
| * for (let i = 0; i < this.playlist.size * 2; i++) { | ||
| * playedSongs.push(this.currentSong!.value); | ||
| * this.currentSong = this.currentSong!.next || this.playlist.head; // Loop back to the start if needed | ||
| * } | ||
| * | ||
| * // Reset the current song to the initial song | ||
| * this.currentSong = initialNode; | ||
| * return playedSongs; | ||
| * } | ||
| * } | ||
| * | ||
| * const songs = [ | ||
| * { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * ]; | ||
| * let player = new Player(songs); | ||
| * // should play the next song | ||
| * player = new Player(songs); | ||
| * const firstSong = player.getCurrentSong(); | ||
| * const nextSong = player.playNext(); | ||
| * | ||
| * // Expect the next song to be "Hotel California by Eagles" | ||
| * console.log(nextSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * console.log(firstSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should play the previous song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * const currentSong = player.getCurrentSong(); | ||
| * const previousSong = player.playPrevious(); | ||
| * | ||
| * // Expect the previous song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(previousSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * console.log(currentSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * | ||
| * // should loop to the first song when playing next from the last song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const nextSongToFirst = player.playNext(); // Should loop to the first song | ||
| * | ||
| * // Expect the next song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(nextSongToFirst); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should loop to the last song when playing previous from the first song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the first song | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const previousToLast = player.playPrevious(); // Should loop to the last song | ||
| * | ||
| * // Expect the previous song to be "Billie Jean by Michael Jackson" | ||
| * console.log(previousToLast); // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * | ||
| * // should loop through the entire playlist | ||
| * player = new Player(songs); | ||
| * const playedSongs = player.loopThroughPlaylist(); | ||
| * | ||
| * // The expected order of songs for two loops | ||
| * console.log(playedSongs); // [ | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }, | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * // ] | ||
| * @example | ||
| * // Use DoublyLinkedList to implement LRU cache | ||
| * interface CacheEntry<K, V> { | ||
| * key: K; | ||
| * value: V; | ||
| * } | ||
| * | ||
| * class LRUCache<K = string, V = any> { | ||
| * private readonly capacity: number; | ||
| * private list: DoublyLinkedList<CacheEntry<K, V>>; | ||
| * private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>; | ||
| * | ||
| * constructor(capacity: number) { | ||
| * if (capacity <= 0) { | ||
| * throw new Error('lru cache capacity must be greater than 0'); | ||
| * } | ||
| * this.capacity = capacity; | ||
| * this.list = new DoublyLinkedList<CacheEntry<K, V>>(); | ||
| * this.map = new Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>(); | ||
| * } | ||
| * | ||
| * // Get cached value | ||
| * get(key: K): V | undefined { | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (!node) return undefined; | ||
| * | ||
| * // Move the visited node to the head of the linked list (most recently used) | ||
| * this.moveToFront(node); | ||
| * | ||
| * return node.value.value; | ||
| * } | ||
| * | ||
| * // Set cache value | ||
| * set(key: K, value: V): void { | ||
| * // Check if it already exists | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (node) { | ||
| * // Update value and move to head | ||
| * node.value.value = value; | ||
| * this.moveToFront(node); | ||
| * return; | ||
| * } | ||
| * | ||
| * // Check capacity | ||
| * if (this.list.size >= this.capacity) { | ||
| * // Delete the least recently used element (the tail of the linked list) | ||
| * const removedNode = this.list.tail; | ||
| * if (removedNode) { | ||
| * this.map.delete(removedNode.value.key); | ||
| * this.list.pop(); | ||
| * } | ||
| * } | ||
| * | ||
| * // Create new node and add to head | ||
| * const newEntry: CacheEntry<K, V> = { key, value }; | ||
| * this.list.unshift(newEntry); | ||
| * | ||
| * // Save node reference in map | ||
| * const newNode = this.list.head; | ||
| * if (newNode) { | ||
| * this.map.set(key, newNode); | ||
| * } | ||
| * } | ||
| * | ||
| * // Move the node to the head of the linked list | ||
| * private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void { | ||
| * this.list.delete(node); | ||
| * this.list.unshift(node.value); | ||
| * } | ||
| * | ||
| * // Delete specific key | ||
| * delete(key: K): boolean { | ||
| * const node = this.map.get(key); | ||
| * if (!node) return false; | ||
| * | ||
| * // Remove from linked list | ||
| * this.list.delete(node); | ||
| * // Remove from map | ||
| * this.map.delete(key); | ||
| * | ||
| * return true; | ||
| * } | ||
| * | ||
| * // Clear cache | ||
| * clear(): void { | ||
| * this.list.clear(); | ||
| * this.map.clear(); | ||
| * } | ||
| * | ||
| * // Get the current cache size | ||
| * get size(): number { | ||
| * return this.list.size; | ||
| * } | ||
| * | ||
| * // Check if it is empty | ||
| * get isEmpty(): boolean { | ||
| * return this.list.isEmpty(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should set and get values correctly | ||
| * const cache = new LRUCache<string, number>(3); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * | ||
| * // The least recently used element should be evicted when capacity is exceeded | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * cache.set('d', 4); // This will eliminate 'a' | ||
| * | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // The priority of an element should be updated when it is accessed | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * cache.get('a'); // access 'a' | ||
| * cache.set('d', 4); // This will eliminate 'b' | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')).toBeUndefined(); | ||
| * expect(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // Should support updating existing keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('a', 10); | ||
| * | ||
| * console.log(cache.get('a')); // 10 | ||
| * | ||
| * // Should support deleting specified keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * | ||
| * console.log(cache.delete('a')); // true | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.size); // 1 | ||
| * | ||
| * // Should support clearing cache | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.clear(); | ||
| * | ||
| * console.log(cache.size); // 0 | ||
| * console.log(cache.isEmpty); // true | ||
| * @example | ||
| * // finding lyrics by timestamp in Coldplay's "Fix You" | ||
| * // Create a DoublyLinkedList to store song lyrics with timestamps | ||
| * const lyricsList = new DoublyLinkedList<{ time: number; text: string }>(); | ||
| * | ||
| * // Detailed lyrics with precise timestamps (in milliseconds) | ||
| * const lyrics = [ | ||
| * { time: 0, text: "When you try your best, but you don't succeed" }, | ||
| * { time: 4000, text: 'When you get what you want, but not what you need' }, | ||
| * { time: 8000, text: "When you feel so tired, but you can't sleep" }, | ||
| * { time: 12000, text: 'Stuck in reverse' }, | ||
| * { time: 16000, text: 'And the tears come streaming down your face' }, | ||
| * { time: 20000, text: "When you lose something you can't replace" }, | ||
| * { time: 24000, text: 'When you love someone, but it goes to waste' }, | ||
| * { time: 28000, text: 'Could it be worse?' }, | ||
| * { time: 32000, text: 'Lights will guide you home' }, | ||
| * { time: 36000, text: 'And ignite your bones' }, | ||
| * { time: 40000, text: 'And I will try to fix you' } | ||
| * ]; | ||
| * | ||
| * // Populate the DoublyLinkedList with lyrics | ||
| * lyrics.forEach(lyric => lyricsList.push(lyric)); | ||
| * | ||
| * // Test different scenarios of lyric synchronization | ||
| * | ||
| * // 1. Find lyric at exact timestamp | ||
| * const exactTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 36000); | ||
| * console.log(exactTimeLyric?.text); // 'And ignite your bones' | ||
| * | ||
| * // 2. Find lyric between timestamps | ||
| * const betweenTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 22000); | ||
| * console.log(betweenTimeLyric?.text); // "When you lose something you can't replace" | ||
| * | ||
| * // 3. Find first lyric when timestamp is less than first entry | ||
| * const earlyTimeLyric = lyricsList.findBackward(lyric => lyric.time <= -1000); | ||
| * console.log(earlyTimeLyric).toBeUndefined(); | ||
| * | ||
| * // 4. Find last lyric when timestamp is after last entry | ||
| * const lateTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 50000); | ||
| * expect(lateTimeLyric?.text); // 'And I will try to fix you' | ||
| * @example | ||
| * // cpu process schedules | ||
| * class Process { | ||
| * constructor( | ||
| * public id: number, | ||
| * public priority: number | ||
| * ) {} | ||
| * | ||
| * execute(): string { | ||
| * return `Process ${this.id} executed.`; | ||
| * } | ||
| * } | ||
| * | ||
| * class Scheduler { | ||
| * private queue: DoublyLinkedList<Process>; | ||
| * | ||
| * constructor() { | ||
| * this.queue = new DoublyLinkedList<Process>(); | ||
| * } | ||
| * | ||
| * addProcess(process: Process): void { | ||
| * // Insert processes into a queue based on priority, keeping priority in descending order | ||
| * let current = this.queue.head; | ||
| * while (current && current.value.priority >= process.priority) { | ||
| * current = current.next; | ||
| * } | ||
| * | ||
| * if (!current) { | ||
| * this.queue.push(process); | ||
| * } else { | ||
| * this.queue.addBefore(current, process); | ||
| * } | ||
| * } | ||
| * | ||
| * executeNext(): string | undefined { | ||
| * // Execute tasks at the head of the queue in order | ||
| * const process = this.queue.shift(); | ||
| * return process ? process.execute() : undefined; | ||
| * } | ||
| * | ||
| * listProcesses(): string[] { | ||
| * return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`); | ||
| * } | ||
| * | ||
| * clear(): void { | ||
| * this.queue.clear(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should add processes based on priority | ||
| * let scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * scheduler.addProcess(new Process(3, 15)); | ||
| * | ||
| * console.log(scheduler.listProcesses()); // [ | ||
| * // 'Process 2 (Priority: 20)', | ||
| * // 'Process 3 (Priority: 15)', | ||
| * // 'Process 1 (Priority: 10)' | ||
| * // ] | ||
| * | ||
| * // should execute the highest priority process | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * console.log(scheduler.executeNext()); // 'Process 2 executed.' | ||
| * console.log(scheduler.listProcesses()); // ['Process 1 (Priority: 10)'] | ||
| * | ||
| * // should clear all processes | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * scheduler.clear(); | ||
| * console.log(scheduler.listProcesses()); // [] | ||
| */ | ||
@@ -457,4 +883,6 @@ class DoublyLinkedList extends base_1.IterableElementBase { | ||
| const nextNode = node.next; | ||
| prevNode.next = nextNode; | ||
| nextNode.prev = prevNode; | ||
| if (prevNode) | ||
| prevNode.next = nextNode; | ||
| if (nextNode) | ||
| nextNode.prev = prevNode; | ||
| this._size--; | ||
@@ -461,0 +889,0 @@ } |
@@ -20,2 +20,167 @@ /** | ||
| * 8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance. | ||
| * @example | ||
| * // Use Heap to sort an array | ||
| * function heapSort(arr: number[]): number[] { | ||
| * const heap = new Heap<number>(arr, { comparator: (a, b) => a - b }); | ||
| * const sorted: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * sorted.push(heap.poll()!); // Poll minimum element | ||
| * } | ||
| * return sorted; | ||
| * } | ||
| * | ||
| * const array = [5, 3, 8, 4, 1, 2]; | ||
| * console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8] | ||
| * @example | ||
| * // Use Heap to solve top k problems | ||
| * function topKElements(arr: number[], k: number): number[] { | ||
| * const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap | ||
| * arr.forEach(num => { | ||
| * heap.add(num); | ||
| * if (heap.size > k) heap.poll(); // Keep the heap size at K | ||
| * }); | ||
| * return heap.toArray(); | ||
| * } | ||
| * | ||
| * const numbers = [10, 30, 20, 5, 15, 25]; | ||
| * console.log(topKElements(numbers, 3)); // [15, 10, 5] | ||
| * @example | ||
| * // Use Heap to merge sorted sequences | ||
| * function mergeSortedSequences(sequences: number[][]): number[] { | ||
| * const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], { | ||
| * comparator: (a, b) => a.value - b.value // Min heap | ||
| * }); | ||
| * | ||
| * // Initialize heap | ||
| * sequences.forEach((seq, seqIndex) => { | ||
| * if (seq.length) { | ||
| * heap.add({ value: seq[0], seqIndex, itemIndex: 0 }); | ||
| * } | ||
| * }); | ||
| * | ||
| * const merged: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * const { value, seqIndex, itemIndex } = heap.poll()!; | ||
| * merged.push(value); | ||
| * | ||
| * if (itemIndex + 1 < sequences[seqIndex].length) { | ||
| * heap.add({ | ||
| * value: sequences[seqIndex][itemIndex + 1], | ||
| * seqIndex, | ||
| * itemIndex: itemIndex + 1 | ||
| * }); | ||
| * } | ||
| * } | ||
| * | ||
| * return merged; | ||
| * } | ||
| * | ||
| * const sequences = [ | ||
| * [1, 4, 7], | ||
| * [2, 5, 8], | ||
| * [3, 6, 9] | ||
| * ]; | ||
| * console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9] | ||
| * @example | ||
| * // Use Heap to dynamically maintain the median | ||
| * class MedianFinder { | ||
| * private low: MaxHeap<number>; // Max heap, stores the smaller half | ||
| * private high: MinHeap<number>; // Min heap, stores the larger half | ||
| * | ||
| * constructor() { | ||
| * this.low = new MaxHeap<number>([]); | ||
| * this.high = new MinHeap<number>([]); | ||
| * } | ||
| * | ||
| * addNum(num: number): void { | ||
| * if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num); | ||
| * else this.high.add(num); | ||
| * | ||
| * // Balance heaps | ||
| * if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!); | ||
| * else if (this.high.size > this.low.size) this.low.add(this.high.poll()!); | ||
| * } | ||
| * | ||
| * findMedian(): number { | ||
| * if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2; | ||
| * return this.low.peek()!; | ||
| * } | ||
| * } | ||
| * | ||
| * const medianFinder = new MedianFinder(); | ||
| * medianFinder.addNum(10); | ||
| * console.log(medianFinder.findMedian()); // 10 | ||
| * medianFinder.addNum(20); | ||
| * console.log(medianFinder.findMedian()); // 15 | ||
| * medianFinder.addNum(30); | ||
| * console.log(medianFinder.findMedian()); // 20 | ||
| * medianFinder.addNum(40); | ||
| * console.log(medianFinder.findMedian()); // 25 | ||
| * medianFinder.addNum(50); | ||
| * console.log(medianFinder.findMedian()); // 30 | ||
| * @example | ||
| * // Use Heap for load balancing | ||
| * function loadBalance(requests: number[], servers: number): number[] { | ||
| * const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap | ||
| * const serverLoads = new Array(servers).fill(0); | ||
| * | ||
| * for (let i = 0; i < servers; i++) { | ||
| * serverHeap.add({ id: i, load: 0 }); | ||
| * } | ||
| * | ||
| * requests.forEach(req => { | ||
| * const server = serverHeap.poll()!; | ||
| * serverLoads[server.id] += req; | ||
| * server.load += req; | ||
| * serverHeap.add(server); // The server after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return serverLoads; | ||
| * } | ||
| * | ||
| * const requests = [5, 2, 8, 3, 7]; | ||
| * console.log(loadBalance(requests, 3)); // [12, 8, 5] | ||
| * @example | ||
| * // Use Heap to schedule tasks | ||
| * type Task = [string, number]; | ||
| * | ||
| * function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> { | ||
| * const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap | ||
| * const allocation = new Map<number, Task[]>(); | ||
| * | ||
| * // Initialize the load on each machine | ||
| * for (let i = 0; i < machines; i++) { | ||
| * machineHeap.add({ id: i, load: 0 }); | ||
| * allocation.set(i, []); | ||
| * } | ||
| * | ||
| * // Assign tasks | ||
| * tasks.forEach(([task, load]) => { | ||
| * const machine = machineHeap.poll()!; | ||
| * allocation.get(machine.id)!.push([task, load]); | ||
| * machine.load += load; | ||
| * machineHeap.add(machine); // The machine after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return allocation; | ||
| * } | ||
| * | ||
| * const tasks: Task[] = [ | ||
| * ['Task1', 3], | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task4', 5], | ||
| * ['Task5', 4] | ||
| * ]; | ||
| * const expectedMap = new Map<number, Task[]>(); | ||
| * expectedMap.set(0, [ | ||
| * ['Task1', 3], | ||
| * ['Task4', 5] | ||
| * ]); | ||
| * expectedMap.set(1, [ | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task5', 4] | ||
| * ]); | ||
| * console.log(scheduleTasks(tasks, 2)); // expectedMap | ||
| */ | ||
@@ -22,0 +187,0 @@ export declare class Heap<E = any, R = any> extends IterableElementBase<E, R, Heap<E, R>> { |
@@ -19,2 +19,167 @@ /** | ||
| * 8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance. | ||
| * @example | ||
| * // Use Heap to sort an array | ||
| * function heapSort(arr: number[]): number[] { | ||
| * const heap = new Heap<number>(arr, { comparator: (a, b) => a - b }); | ||
| * const sorted: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * sorted.push(heap.poll()!); // Poll minimum element | ||
| * } | ||
| * return sorted; | ||
| * } | ||
| * | ||
| * const array = [5, 3, 8, 4, 1, 2]; | ||
| * console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8] | ||
| * @example | ||
| * // Use Heap to solve top k problems | ||
| * function topKElements(arr: number[], k: number): number[] { | ||
| * const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap | ||
| * arr.forEach(num => { | ||
| * heap.add(num); | ||
| * if (heap.size > k) heap.poll(); // Keep the heap size at K | ||
| * }); | ||
| * return heap.toArray(); | ||
| * } | ||
| * | ||
| * const numbers = [10, 30, 20, 5, 15, 25]; | ||
| * console.log(topKElements(numbers, 3)); // [15, 10, 5] | ||
| * @example | ||
| * // Use Heap to merge sorted sequences | ||
| * function mergeSortedSequences(sequences: number[][]): number[] { | ||
| * const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], { | ||
| * comparator: (a, b) => a.value - b.value // Min heap | ||
| * }); | ||
| * | ||
| * // Initialize heap | ||
| * sequences.forEach((seq, seqIndex) => { | ||
| * if (seq.length) { | ||
| * heap.add({ value: seq[0], seqIndex, itemIndex: 0 }); | ||
| * } | ||
| * }); | ||
| * | ||
| * const merged: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * const { value, seqIndex, itemIndex } = heap.poll()!; | ||
| * merged.push(value); | ||
| * | ||
| * if (itemIndex + 1 < sequences[seqIndex].length) { | ||
| * heap.add({ | ||
| * value: sequences[seqIndex][itemIndex + 1], | ||
| * seqIndex, | ||
| * itemIndex: itemIndex + 1 | ||
| * }); | ||
| * } | ||
| * } | ||
| * | ||
| * return merged; | ||
| * } | ||
| * | ||
| * const sequences = [ | ||
| * [1, 4, 7], | ||
| * [2, 5, 8], | ||
| * [3, 6, 9] | ||
| * ]; | ||
| * console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9] | ||
| * @example | ||
| * // Use Heap to dynamically maintain the median | ||
| * class MedianFinder { | ||
| * private low: MaxHeap<number>; // Max heap, stores the smaller half | ||
| * private high: MinHeap<number>; // Min heap, stores the larger half | ||
| * | ||
| * constructor() { | ||
| * this.low = new MaxHeap<number>([]); | ||
| * this.high = new MinHeap<number>([]); | ||
| * } | ||
| * | ||
| * addNum(num: number): void { | ||
| * if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num); | ||
| * else this.high.add(num); | ||
| * | ||
| * // Balance heaps | ||
| * if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!); | ||
| * else if (this.high.size > this.low.size) this.low.add(this.high.poll()!); | ||
| * } | ||
| * | ||
| * findMedian(): number { | ||
| * if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2; | ||
| * return this.low.peek()!; | ||
| * } | ||
| * } | ||
| * | ||
| * const medianFinder = new MedianFinder(); | ||
| * medianFinder.addNum(10); | ||
| * console.log(medianFinder.findMedian()); // 10 | ||
| * medianFinder.addNum(20); | ||
| * console.log(medianFinder.findMedian()); // 15 | ||
| * medianFinder.addNum(30); | ||
| * console.log(medianFinder.findMedian()); // 20 | ||
| * medianFinder.addNum(40); | ||
| * console.log(medianFinder.findMedian()); // 25 | ||
| * medianFinder.addNum(50); | ||
| * console.log(medianFinder.findMedian()); // 30 | ||
| * @example | ||
| * // Use Heap for load balancing | ||
| * function loadBalance(requests: number[], servers: number): number[] { | ||
| * const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap | ||
| * const serverLoads = new Array(servers).fill(0); | ||
| * | ||
| * for (let i = 0; i < servers; i++) { | ||
| * serverHeap.add({ id: i, load: 0 }); | ||
| * } | ||
| * | ||
| * requests.forEach(req => { | ||
| * const server = serverHeap.poll()!; | ||
| * serverLoads[server.id] += req; | ||
| * server.load += req; | ||
| * serverHeap.add(server); // The server after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return serverLoads; | ||
| * } | ||
| * | ||
| * const requests = [5, 2, 8, 3, 7]; | ||
| * console.log(loadBalance(requests, 3)); // [12, 8, 5] | ||
| * @example | ||
| * // Use Heap to schedule tasks | ||
| * type Task = [string, number]; | ||
| * | ||
| * function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> { | ||
| * const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap | ||
| * const allocation = new Map<number, Task[]>(); | ||
| * | ||
| * // Initialize the load on each machine | ||
| * for (let i = 0; i < machines; i++) { | ||
| * machineHeap.add({ id: i, load: 0 }); | ||
| * allocation.set(i, []); | ||
| * } | ||
| * | ||
| * // Assign tasks | ||
| * tasks.forEach(([task, load]) => { | ||
| * const machine = machineHeap.poll()!; | ||
| * allocation.get(machine.id)!.push([task, load]); | ||
| * machine.load += load; | ||
| * machineHeap.add(machine); // The machine after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return allocation; | ||
| * } | ||
| * | ||
| * const tasks: Task[] = [ | ||
| * ['Task1', 3], | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task4', 5], | ||
| * ['Task5', 4] | ||
| * ]; | ||
| * const expectedMap = new Map<number, Task[]>(); | ||
| * expectedMap.set(0, [ | ||
| * ['Task1', 3], | ||
| * ['Task4', 5] | ||
| * ]); | ||
| * expectedMap.set(1, [ | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task5', 4] | ||
| * ]); | ||
| * console.log(scheduleTasks(tasks, 2)); // expectedMap | ||
| */ | ||
@@ -21,0 +186,0 @@ export class Heap extends IterableElementBase { |
@@ -62,2 +62,428 @@ /** | ||
| * 4. High Efficiency in Insertion and Deletion: Adding or removing elements in a linked list does not require moving other elements, making these operations more efficient than in arrays. | ||
| * @example | ||
| * // text editor operation history | ||
| * const actions = [ | ||
| * { type: 'insert', content: 'first line of text' }, | ||
| * { type: 'insert', content: 'second line of text' }, | ||
| * { type: 'delete', content: 'delete the first line' } | ||
| * ]; | ||
| * const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions); | ||
| * | ||
| * console.log(editorHistory.last?.type); // 'delete' | ||
| * console.log(editorHistory.pop()?.content); // 'delete the first line' | ||
| * console.log(editorHistory.last?.type); // 'insert' | ||
| * @example | ||
| * // Browser history | ||
| * const browserHistory = new DoublyLinkedList<string>(); | ||
| * | ||
| * browserHistory.push('home page'); | ||
| * browserHistory.push('search page'); | ||
| * browserHistory.push('details page'); | ||
| * | ||
| * console.log(browserHistory.last); // 'details page' | ||
| * console.log(browserHistory.pop()); // 'details page' | ||
| * console.log(browserHistory.last); // 'search page' | ||
| * @example | ||
| * // Use DoublyLinkedList to implement music player | ||
| * // Define the Song interface | ||
| * interface Song { | ||
| * title: string; | ||
| * artist: string; | ||
| * duration: number; // duration in seconds | ||
| * } | ||
| * | ||
| * class Player { | ||
| * private playlist: DoublyLinkedList<Song>; | ||
| * private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined; | ||
| * | ||
| * constructor(songs: Song[]) { | ||
| * this.playlist = new DoublyLinkedList<Song>(); | ||
| * songs.forEach(song => this.playlist.push(song)); | ||
| * this.currentSong = this.playlist.head; | ||
| * } | ||
| * | ||
| * // Play the next song in the playlist | ||
| * playNext(): Song | undefined { | ||
| * if (!this.currentSong?.next) { | ||
| * this.currentSong = this.playlist.head; // Loop to the first song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.next; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Play the previous song in the playlist | ||
| * playPrevious(): Song | undefined { | ||
| * if (!this.currentSong?.prev) { | ||
| * this.currentSong = this.playlist.tail; // Loop to the last song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.prev; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Get the current song | ||
| * getCurrentSong(): Song | undefined { | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Loop through the playlist twice | ||
| * loopThroughPlaylist(): Song[] { | ||
| * const playedSongs: Song[] = []; | ||
| * const initialNode = this.currentSong; | ||
| * | ||
| * // Loop through the playlist twice | ||
| * for (let i = 0; i < this.playlist.size * 2; i++) { | ||
| * playedSongs.push(this.currentSong!.value); | ||
| * this.currentSong = this.currentSong!.next || this.playlist.head; // Loop back to the start if needed | ||
| * } | ||
| * | ||
| * // Reset the current song to the initial song | ||
| * this.currentSong = initialNode; | ||
| * return playedSongs; | ||
| * } | ||
| * } | ||
| * | ||
| * const songs = [ | ||
| * { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * ]; | ||
| * let player = new Player(songs); | ||
| * // should play the next song | ||
| * player = new Player(songs); | ||
| * const firstSong = player.getCurrentSong(); | ||
| * const nextSong = player.playNext(); | ||
| * | ||
| * // Expect the next song to be "Hotel California by Eagles" | ||
| * console.log(nextSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * console.log(firstSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should play the previous song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * const currentSong = player.getCurrentSong(); | ||
| * const previousSong = player.playPrevious(); | ||
| * | ||
| * // Expect the previous song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(previousSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * console.log(currentSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * | ||
| * // should loop to the first song when playing next from the last song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const nextSongToFirst = player.playNext(); // Should loop to the first song | ||
| * | ||
| * // Expect the next song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(nextSongToFirst); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should loop to the last song when playing previous from the first song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the first song | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const previousToLast = player.playPrevious(); // Should loop to the last song | ||
| * | ||
| * // Expect the previous song to be "Billie Jean by Michael Jackson" | ||
| * console.log(previousToLast); // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * | ||
| * // should loop through the entire playlist | ||
| * player = new Player(songs); | ||
| * const playedSongs = player.loopThroughPlaylist(); | ||
| * | ||
| * // The expected order of songs for two loops | ||
| * console.log(playedSongs); // [ | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }, | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * // ] | ||
| * @example | ||
| * // Use DoublyLinkedList to implement LRU cache | ||
| * interface CacheEntry<K, V> { | ||
| * key: K; | ||
| * value: V; | ||
| * } | ||
| * | ||
| * class LRUCache<K = string, V = any> { | ||
| * private readonly capacity: number; | ||
| * private list: DoublyLinkedList<CacheEntry<K, V>>; | ||
| * private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>; | ||
| * | ||
| * constructor(capacity: number) { | ||
| * if (capacity <= 0) { | ||
| * throw new Error('lru cache capacity must be greater than 0'); | ||
| * } | ||
| * this.capacity = capacity; | ||
| * this.list = new DoublyLinkedList<CacheEntry<K, V>>(); | ||
| * this.map = new Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>(); | ||
| * } | ||
| * | ||
| * // Get cached value | ||
| * get(key: K): V | undefined { | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (!node) return undefined; | ||
| * | ||
| * // Move the visited node to the head of the linked list (most recently used) | ||
| * this.moveToFront(node); | ||
| * | ||
| * return node.value.value; | ||
| * } | ||
| * | ||
| * // Set cache value | ||
| * set(key: K, value: V): void { | ||
| * // Check if it already exists | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (node) { | ||
| * // Update value and move to head | ||
| * node.value.value = value; | ||
| * this.moveToFront(node); | ||
| * return; | ||
| * } | ||
| * | ||
| * // Check capacity | ||
| * if (this.list.size >= this.capacity) { | ||
| * // Delete the least recently used element (the tail of the linked list) | ||
| * const removedNode = this.list.tail; | ||
| * if (removedNode) { | ||
| * this.map.delete(removedNode.value.key); | ||
| * this.list.pop(); | ||
| * } | ||
| * } | ||
| * | ||
| * // Create new node and add to head | ||
| * const newEntry: CacheEntry<K, V> = { key, value }; | ||
| * this.list.unshift(newEntry); | ||
| * | ||
| * // Save node reference in map | ||
| * const newNode = this.list.head; | ||
| * if (newNode) { | ||
| * this.map.set(key, newNode); | ||
| * } | ||
| * } | ||
| * | ||
| * // Move the node to the head of the linked list | ||
| * private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void { | ||
| * this.list.delete(node); | ||
| * this.list.unshift(node.value); | ||
| * } | ||
| * | ||
| * // Delete specific key | ||
| * delete(key: K): boolean { | ||
| * const node = this.map.get(key); | ||
| * if (!node) return false; | ||
| * | ||
| * // Remove from linked list | ||
| * this.list.delete(node); | ||
| * // Remove from map | ||
| * this.map.delete(key); | ||
| * | ||
| * return true; | ||
| * } | ||
| * | ||
| * // Clear cache | ||
| * clear(): void { | ||
| * this.list.clear(); | ||
| * this.map.clear(); | ||
| * } | ||
| * | ||
| * // Get the current cache size | ||
| * get size(): number { | ||
| * return this.list.size; | ||
| * } | ||
| * | ||
| * // Check if it is empty | ||
| * get isEmpty(): boolean { | ||
| * return this.list.isEmpty(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should set and get values correctly | ||
| * const cache = new LRUCache<string, number>(3); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * | ||
| * // The least recently used element should be evicted when capacity is exceeded | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * cache.set('d', 4); // This will eliminate 'a' | ||
| * | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // The priority of an element should be updated when it is accessed | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * cache.get('a'); // access 'a' | ||
| * cache.set('d', 4); // This will eliminate 'b' | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')).toBeUndefined(); | ||
| * expect(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // Should support updating existing keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('a', 10); | ||
| * | ||
| * console.log(cache.get('a')); // 10 | ||
| * | ||
| * // Should support deleting specified keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * | ||
| * console.log(cache.delete('a')); // true | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.size); // 1 | ||
| * | ||
| * // Should support clearing cache | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.clear(); | ||
| * | ||
| * console.log(cache.size); // 0 | ||
| * console.log(cache.isEmpty); // true | ||
| * @example | ||
| * // finding lyrics by timestamp in Coldplay's "Fix You" | ||
| * // Create a DoublyLinkedList to store song lyrics with timestamps | ||
| * const lyricsList = new DoublyLinkedList<{ time: number; text: string }>(); | ||
| * | ||
| * // Detailed lyrics with precise timestamps (in milliseconds) | ||
| * const lyrics = [ | ||
| * { time: 0, text: "When you try your best, but you don't succeed" }, | ||
| * { time: 4000, text: 'When you get what you want, but not what you need' }, | ||
| * { time: 8000, text: "When you feel so tired, but you can't sleep" }, | ||
| * { time: 12000, text: 'Stuck in reverse' }, | ||
| * { time: 16000, text: 'And the tears come streaming down your face' }, | ||
| * { time: 20000, text: "When you lose something you can't replace" }, | ||
| * { time: 24000, text: 'When you love someone, but it goes to waste' }, | ||
| * { time: 28000, text: 'Could it be worse?' }, | ||
| * { time: 32000, text: 'Lights will guide you home' }, | ||
| * { time: 36000, text: 'And ignite your bones' }, | ||
| * { time: 40000, text: 'And I will try to fix you' } | ||
| * ]; | ||
| * | ||
| * // Populate the DoublyLinkedList with lyrics | ||
| * lyrics.forEach(lyric => lyricsList.push(lyric)); | ||
| * | ||
| * // Test different scenarios of lyric synchronization | ||
| * | ||
| * // 1. Find lyric at exact timestamp | ||
| * const exactTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 36000); | ||
| * console.log(exactTimeLyric?.text); // 'And ignite your bones' | ||
| * | ||
| * // 2. Find lyric between timestamps | ||
| * const betweenTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 22000); | ||
| * console.log(betweenTimeLyric?.text); // "When you lose something you can't replace" | ||
| * | ||
| * // 3. Find first lyric when timestamp is less than first entry | ||
| * const earlyTimeLyric = lyricsList.findBackward(lyric => lyric.time <= -1000); | ||
| * console.log(earlyTimeLyric).toBeUndefined(); | ||
| * | ||
| * // 4. Find last lyric when timestamp is after last entry | ||
| * const lateTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 50000); | ||
| * expect(lateTimeLyric?.text); // 'And I will try to fix you' | ||
| * @example | ||
| * // cpu process schedules | ||
| * class Process { | ||
| * constructor( | ||
| * public id: number, | ||
| * public priority: number | ||
| * ) {} | ||
| * | ||
| * execute(): string { | ||
| * return `Process ${this.id} executed.`; | ||
| * } | ||
| * } | ||
| * | ||
| * class Scheduler { | ||
| * private queue: DoublyLinkedList<Process>; | ||
| * | ||
| * constructor() { | ||
| * this.queue = new DoublyLinkedList<Process>(); | ||
| * } | ||
| * | ||
| * addProcess(process: Process): void { | ||
| * // Insert processes into a queue based on priority, keeping priority in descending order | ||
| * let current = this.queue.head; | ||
| * while (current && current.value.priority >= process.priority) { | ||
| * current = current.next; | ||
| * } | ||
| * | ||
| * if (!current) { | ||
| * this.queue.push(process); | ||
| * } else { | ||
| * this.queue.addBefore(current, process); | ||
| * } | ||
| * } | ||
| * | ||
| * executeNext(): string | undefined { | ||
| * // Execute tasks at the head of the queue in order | ||
| * const process = this.queue.shift(); | ||
| * return process ? process.execute() : undefined; | ||
| * } | ||
| * | ||
| * listProcesses(): string[] { | ||
| * return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`); | ||
| * } | ||
| * | ||
| * clear(): void { | ||
| * this.queue.clear(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should add processes based on priority | ||
| * let scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * scheduler.addProcess(new Process(3, 15)); | ||
| * | ||
| * console.log(scheduler.listProcesses()); // [ | ||
| * // 'Process 2 (Priority: 20)', | ||
| * // 'Process 3 (Priority: 15)', | ||
| * // 'Process 1 (Priority: 10)' | ||
| * // ] | ||
| * | ||
| * // should execute the highest priority process | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * console.log(scheduler.executeNext()); // 'Process 2 executed.' | ||
| * console.log(scheduler.listProcesses()); // ['Process 1 (Priority: 10)'] | ||
| * | ||
| * // should clear all processes | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * scheduler.clear(); | ||
| * console.log(scheduler.listProcesses()); // [] | ||
| */ | ||
@@ -64,0 +490,0 @@ export declare class DoublyLinkedList<E = any, R = any> extends IterableElementBase<E, R, DoublyLinkedList<E, R>> { |
@@ -70,2 +70,428 @@ import { IterableElementBase } from '../base'; | ||
| * 4. High Efficiency in Insertion and Deletion: Adding or removing elements in a linked list does not require moving other elements, making these operations more efficient than in arrays. | ||
| * @example | ||
| * // text editor operation history | ||
| * const actions = [ | ||
| * { type: 'insert', content: 'first line of text' }, | ||
| * { type: 'insert', content: 'second line of text' }, | ||
| * { type: 'delete', content: 'delete the first line' } | ||
| * ]; | ||
| * const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions); | ||
| * | ||
| * console.log(editorHistory.last?.type); // 'delete' | ||
| * console.log(editorHistory.pop()?.content); // 'delete the first line' | ||
| * console.log(editorHistory.last?.type); // 'insert' | ||
| * @example | ||
| * // Browser history | ||
| * const browserHistory = new DoublyLinkedList<string>(); | ||
| * | ||
| * browserHistory.push('home page'); | ||
| * browserHistory.push('search page'); | ||
| * browserHistory.push('details page'); | ||
| * | ||
| * console.log(browserHistory.last); // 'details page' | ||
| * console.log(browserHistory.pop()); // 'details page' | ||
| * console.log(browserHistory.last); // 'search page' | ||
| * @example | ||
| * // Use DoublyLinkedList to implement music player | ||
| * // Define the Song interface | ||
| * interface Song { | ||
| * title: string; | ||
| * artist: string; | ||
| * duration: number; // duration in seconds | ||
| * } | ||
| * | ||
| * class Player { | ||
| * private playlist: DoublyLinkedList<Song>; | ||
| * private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined; | ||
| * | ||
| * constructor(songs: Song[]) { | ||
| * this.playlist = new DoublyLinkedList<Song>(); | ||
| * songs.forEach(song => this.playlist.push(song)); | ||
| * this.currentSong = this.playlist.head; | ||
| * } | ||
| * | ||
| * // Play the next song in the playlist | ||
| * playNext(): Song | undefined { | ||
| * if (!this.currentSong?.next) { | ||
| * this.currentSong = this.playlist.head; // Loop to the first song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.next; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Play the previous song in the playlist | ||
| * playPrevious(): Song | undefined { | ||
| * if (!this.currentSong?.prev) { | ||
| * this.currentSong = this.playlist.tail; // Loop to the last song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.prev; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Get the current song | ||
| * getCurrentSong(): Song | undefined { | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Loop through the playlist twice | ||
| * loopThroughPlaylist(): Song[] { | ||
| * const playedSongs: Song[] = []; | ||
| * const initialNode = this.currentSong; | ||
| * | ||
| * // Loop through the playlist twice | ||
| * for (let i = 0; i < this.playlist.size * 2; i++) { | ||
| * playedSongs.push(this.currentSong!.value); | ||
| * this.currentSong = this.currentSong!.next || this.playlist.head; // Loop back to the start if needed | ||
| * } | ||
| * | ||
| * // Reset the current song to the initial song | ||
| * this.currentSong = initialNode; | ||
| * return playedSongs; | ||
| * } | ||
| * } | ||
| * | ||
| * const songs = [ | ||
| * { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * ]; | ||
| * let player = new Player(songs); | ||
| * // should play the next song | ||
| * player = new Player(songs); | ||
| * const firstSong = player.getCurrentSong(); | ||
| * const nextSong = player.playNext(); | ||
| * | ||
| * // Expect the next song to be "Hotel California by Eagles" | ||
| * console.log(nextSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * console.log(firstSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should play the previous song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * const currentSong = player.getCurrentSong(); | ||
| * const previousSong = player.playPrevious(); | ||
| * | ||
| * // Expect the previous song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(previousSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * console.log(currentSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * | ||
| * // should loop to the first song when playing next from the last song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const nextSongToFirst = player.playNext(); // Should loop to the first song | ||
| * | ||
| * // Expect the next song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(nextSongToFirst); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should loop to the last song when playing previous from the first song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the first song | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const previousToLast = player.playPrevious(); // Should loop to the last song | ||
| * | ||
| * // Expect the previous song to be "Billie Jean by Michael Jackson" | ||
| * console.log(previousToLast); // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * | ||
| * // should loop through the entire playlist | ||
| * player = new Player(songs); | ||
| * const playedSongs = player.loopThroughPlaylist(); | ||
| * | ||
| * // The expected order of songs for two loops | ||
| * console.log(playedSongs); // [ | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }, | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * // ] | ||
| * @example | ||
| * // Use DoublyLinkedList to implement LRU cache | ||
| * interface CacheEntry<K, V> { | ||
| * key: K; | ||
| * value: V; | ||
| * } | ||
| * | ||
| * class LRUCache<K = string, V = any> { | ||
| * private readonly capacity: number; | ||
| * private list: DoublyLinkedList<CacheEntry<K, V>>; | ||
| * private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>; | ||
| * | ||
| * constructor(capacity: number) { | ||
| * if (capacity <= 0) { | ||
| * throw new Error('lru cache capacity must be greater than 0'); | ||
| * } | ||
| * this.capacity = capacity; | ||
| * this.list = new DoublyLinkedList<CacheEntry<K, V>>(); | ||
| * this.map = new Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>(); | ||
| * } | ||
| * | ||
| * // Get cached value | ||
| * get(key: K): V | undefined { | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (!node) return undefined; | ||
| * | ||
| * // Move the visited node to the head of the linked list (most recently used) | ||
| * this.moveToFront(node); | ||
| * | ||
| * return node.value.value; | ||
| * } | ||
| * | ||
| * // Set cache value | ||
| * set(key: K, value: V): void { | ||
| * // Check if it already exists | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (node) { | ||
| * // Update value and move to head | ||
| * node.value.value = value; | ||
| * this.moveToFront(node); | ||
| * return; | ||
| * } | ||
| * | ||
| * // Check capacity | ||
| * if (this.list.size >= this.capacity) { | ||
| * // Delete the least recently used element (the tail of the linked list) | ||
| * const removedNode = this.list.tail; | ||
| * if (removedNode) { | ||
| * this.map.delete(removedNode.value.key); | ||
| * this.list.pop(); | ||
| * } | ||
| * } | ||
| * | ||
| * // Create new node and add to head | ||
| * const newEntry: CacheEntry<K, V> = { key, value }; | ||
| * this.list.unshift(newEntry); | ||
| * | ||
| * // Save node reference in map | ||
| * const newNode = this.list.head; | ||
| * if (newNode) { | ||
| * this.map.set(key, newNode); | ||
| * } | ||
| * } | ||
| * | ||
| * // Move the node to the head of the linked list | ||
| * private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void { | ||
| * this.list.delete(node); | ||
| * this.list.unshift(node.value); | ||
| * } | ||
| * | ||
| * // Delete specific key | ||
| * delete(key: K): boolean { | ||
| * const node = this.map.get(key); | ||
| * if (!node) return false; | ||
| * | ||
| * // Remove from linked list | ||
| * this.list.delete(node); | ||
| * // Remove from map | ||
| * this.map.delete(key); | ||
| * | ||
| * return true; | ||
| * } | ||
| * | ||
| * // Clear cache | ||
| * clear(): void { | ||
| * this.list.clear(); | ||
| * this.map.clear(); | ||
| * } | ||
| * | ||
| * // Get the current cache size | ||
| * get size(): number { | ||
| * return this.list.size; | ||
| * } | ||
| * | ||
| * // Check if it is empty | ||
| * get isEmpty(): boolean { | ||
| * return this.list.isEmpty(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should set and get values correctly | ||
| * const cache = new LRUCache<string, number>(3); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * | ||
| * // The least recently used element should be evicted when capacity is exceeded | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * cache.set('d', 4); // This will eliminate 'a' | ||
| * | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // The priority of an element should be updated when it is accessed | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * cache.get('a'); // access 'a' | ||
| * cache.set('d', 4); // This will eliminate 'b' | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')).toBeUndefined(); | ||
| * expect(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // Should support updating existing keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('a', 10); | ||
| * | ||
| * console.log(cache.get('a')); // 10 | ||
| * | ||
| * // Should support deleting specified keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * | ||
| * console.log(cache.delete('a')); // true | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.size); // 1 | ||
| * | ||
| * // Should support clearing cache | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.clear(); | ||
| * | ||
| * console.log(cache.size); // 0 | ||
| * console.log(cache.isEmpty); // true | ||
| * @example | ||
| * // finding lyrics by timestamp in Coldplay's "Fix You" | ||
| * // Create a DoublyLinkedList to store song lyrics with timestamps | ||
| * const lyricsList = new DoublyLinkedList<{ time: number; text: string }>(); | ||
| * | ||
| * // Detailed lyrics with precise timestamps (in milliseconds) | ||
| * const lyrics = [ | ||
| * { time: 0, text: "When you try your best, but you don't succeed" }, | ||
| * { time: 4000, text: 'When you get what you want, but not what you need' }, | ||
| * { time: 8000, text: "When you feel so tired, but you can't sleep" }, | ||
| * { time: 12000, text: 'Stuck in reverse' }, | ||
| * { time: 16000, text: 'And the tears come streaming down your face' }, | ||
| * { time: 20000, text: "When you lose something you can't replace" }, | ||
| * { time: 24000, text: 'When you love someone, but it goes to waste' }, | ||
| * { time: 28000, text: 'Could it be worse?' }, | ||
| * { time: 32000, text: 'Lights will guide you home' }, | ||
| * { time: 36000, text: 'And ignite your bones' }, | ||
| * { time: 40000, text: 'And I will try to fix you' } | ||
| * ]; | ||
| * | ||
| * // Populate the DoublyLinkedList with lyrics | ||
| * lyrics.forEach(lyric => lyricsList.push(lyric)); | ||
| * | ||
| * // Test different scenarios of lyric synchronization | ||
| * | ||
| * // 1. Find lyric at exact timestamp | ||
| * const exactTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 36000); | ||
| * console.log(exactTimeLyric?.text); // 'And ignite your bones' | ||
| * | ||
| * // 2. Find lyric between timestamps | ||
| * const betweenTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 22000); | ||
| * console.log(betweenTimeLyric?.text); // "When you lose something you can't replace" | ||
| * | ||
| * // 3. Find first lyric when timestamp is less than first entry | ||
| * const earlyTimeLyric = lyricsList.findBackward(lyric => lyric.time <= -1000); | ||
| * console.log(earlyTimeLyric).toBeUndefined(); | ||
| * | ||
| * // 4. Find last lyric when timestamp is after last entry | ||
| * const lateTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 50000); | ||
| * expect(lateTimeLyric?.text); // 'And I will try to fix you' | ||
| * @example | ||
| * // cpu process schedules | ||
| * class Process { | ||
| * constructor( | ||
| * public id: number, | ||
| * public priority: number | ||
| * ) {} | ||
| * | ||
| * execute(): string { | ||
| * return `Process ${this.id} executed.`; | ||
| * } | ||
| * } | ||
| * | ||
| * class Scheduler { | ||
| * private queue: DoublyLinkedList<Process>; | ||
| * | ||
| * constructor() { | ||
| * this.queue = new DoublyLinkedList<Process>(); | ||
| * } | ||
| * | ||
| * addProcess(process: Process): void { | ||
| * // Insert processes into a queue based on priority, keeping priority in descending order | ||
| * let current = this.queue.head; | ||
| * while (current && current.value.priority >= process.priority) { | ||
| * current = current.next; | ||
| * } | ||
| * | ||
| * if (!current) { | ||
| * this.queue.push(process); | ||
| * } else { | ||
| * this.queue.addBefore(current, process); | ||
| * } | ||
| * } | ||
| * | ||
| * executeNext(): string | undefined { | ||
| * // Execute tasks at the head of the queue in order | ||
| * const process = this.queue.shift(); | ||
| * return process ? process.execute() : undefined; | ||
| * } | ||
| * | ||
| * listProcesses(): string[] { | ||
| * return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`); | ||
| * } | ||
| * | ||
| * clear(): void { | ||
| * this.queue.clear(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should add processes based on priority | ||
| * let scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * scheduler.addProcess(new Process(3, 15)); | ||
| * | ||
| * console.log(scheduler.listProcesses()); // [ | ||
| * // 'Process 2 (Priority: 20)', | ||
| * // 'Process 3 (Priority: 15)', | ||
| * // 'Process 1 (Priority: 10)' | ||
| * // ] | ||
| * | ||
| * // should execute the highest priority process | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * console.log(scheduler.executeNext()); // 'Process 2 executed.' | ||
| * console.log(scheduler.listProcesses()); // ['Process 1 (Priority: 10)'] | ||
| * | ||
| * // should clear all processes | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * scheduler.clear(); | ||
| * console.log(scheduler.listProcesses()); // [] | ||
| */ | ||
@@ -457,4 +883,6 @@ export class DoublyLinkedList extends IterableElementBase { | ||
| const nextNode = node.next; | ||
| prevNode.next = nextNode; | ||
| nextNode.prev = prevNode; | ||
| if (prevNode) | ||
| prevNode.next = nextNode; | ||
| if (nextNode) | ||
| nextNode.prev = prevNode; | ||
| this._size--; | ||
@@ -461,0 +889,0 @@ } |
| { | ||
| "name": "data-structure-typed", | ||
| "version": "1.53.2", | ||
| "version": "1.53.3", | ||
| "description": "Javascript Data Structure. Heap, Binary Tree, Red Black Tree, Linked List, Deque, Trie, HashMap, Directed Graph, Undirected Graph, Binary Search Tree(BST), AVL Tree, Priority Queue, Graph, Queue, Tree Multiset, Singly Linked List, Doubly Linked List, Max Heap, Max Priority Queue, Min Heap, Min Priority Queue, Stack. Benchmark compared with C++ STL. API aligned with ES6 and Java.util. Usability is comparable to Python", | ||
@@ -21,6 +21,7 @@ "main": "dist/cjs/index.js", | ||
| "build:umd": "tsup", | ||
| "build:docs": "typedoc --out docs ./src", | ||
| "build:docs-class": "typedoc --out docs ./src/data-structures", | ||
| "test:unit": "jest --runInBand", | ||
| "test": "npm run test:unit", | ||
| "build:docs": "npm run gen:examples && typedoc --out docs ./src", | ||
| "build:docs-class": "npm run gen:examples && typedoc --out docs ./src/data-structures", | ||
| "gen:examples": "ts-node testToExample.ts", | ||
| "test:in-band": "jest --runInBand", | ||
| "test": "npm run test:in-band", | ||
| "test:integration": "npm run update:subs && jest --config jest.integration.config.js", | ||
@@ -38,3 +39,3 @@ "test:perf": "npm run build:cjs && npm run build:mjs && ts-node test/performance/reportor.ts", | ||
| "check:exist-latest": "sh scripts/check_exist_remotely.sh", | ||
| "ci": "env && git fetch --tags && npm run update:subs && npm run inspect && npm run lint && npm run build && npm run test:unit && npm run changelog", | ||
| "ci": "env && git fetch --tags && npm run update:subs && npm run inspect && npm run lint && npm run build && npm run test && npm run changelog", | ||
| "update:subs": "npm i avl-tree-typed binary-tree-typed bst-typed heap-typed data-structure-typed --save-dev", | ||
@@ -74,7 +75,7 @@ "install:all-subs": "npm i avl-tree-typed binary-tree-typed bst-typed deque-typed directed-graph-typed doubly-linked-list-typed graph-typed heap-typed linked-list-typed max-heap-typed max-priority-queue-typed min-heap-typed min-priority-queue-typed priority-queue-typed singly-linked-list-typed stack-typed tree-multimap-typed trie-typed undirected-graph-typed queue-typed --save-dev", | ||
| "auto-changelog": "^2.5.0", | ||
| "avl-tree-typed": "^1.53.1", | ||
| "avl-tree-typed": "^1.53.2", | ||
| "benchmark": "^2.1.4", | ||
| "binary-tree-typed": "^1.53.1", | ||
| "bst-typed": "^1.53.1", | ||
| "data-structure-typed": "^1.53.1", | ||
| "binary-tree-typed": "^1.53.2", | ||
| "bst-typed": "^1.53.2", | ||
| "data-structure-typed": "^1.53.2", | ||
| "dependency-cruiser": "^16.5.0", | ||
@@ -88,3 +89,3 @@ "doctoc": "^2.2.1", | ||
| "fast-glob": "^3.3.2", | ||
| "heap-typed": "^1.53.1", | ||
| "heap-typed": "^1.53.2", | ||
| "istanbul-badges-readme": "^1.9.0", | ||
@@ -91,0 +92,0 @@ "jest": "^29.7.0", |
@@ -801,2 +801,8 @@ # data-structure-typed | ||
| [//]: # (No deletion!!! Start of Example Replace Section) | ||
| [//]: # (No deletion!!! End of Example Replace Section) | ||
| ## API docs & Examples | ||
@@ -803,0 +809,0 @@ |
@@ -22,2 +22,167 @@ /** | ||
| * 8. Graph Algorithms: Such as Dijkstra's shortest path algorithm and Prime's minimum-spanning tree algorithm, which use heaps to improve performance. | ||
| * @example | ||
| * // Use Heap to sort an array | ||
| * function heapSort(arr: number[]): number[] { | ||
| * const heap = new Heap<number>(arr, { comparator: (a, b) => a - b }); | ||
| * const sorted: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * sorted.push(heap.poll()!); // Poll minimum element | ||
| * } | ||
| * return sorted; | ||
| * } | ||
| * | ||
| * const array = [5, 3, 8, 4, 1, 2]; | ||
| * console.log(heapSort(array)); // [1, 2, 3, 4, 5, 8] | ||
| * @example | ||
| * // Use Heap to solve top k problems | ||
| * function topKElements(arr: number[], k: number): number[] { | ||
| * const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap | ||
| * arr.forEach(num => { | ||
| * heap.add(num); | ||
| * if (heap.size > k) heap.poll(); // Keep the heap size at K | ||
| * }); | ||
| * return heap.toArray(); | ||
| * } | ||
| * | ||
| * const numbers = [10, 30, 20, 5, 15, 25]; | ||
| * console.log(topKElements(numbers, 3)); // [15, 10, 5] | ||
| * @example | ||
| * // Use Heap to merge sorted sequences | ||
| * function mergeSortedSequences(sequences: number[][]): number[] { | ||
| * const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], { | ||
| * comparator: (a, b) => a.value - b.value // Min heap | ||
| * }); | ||
| * | ||
| * // Initialize heap | ||
| * sequences.forEach((seq, seqIndex) => { | ||
| * if (seq.length) { | ||
| * heap.add({ value: seq[0], seqIndex, itemIndex: 0 }); | ||
| * } | ||
| * }); | ||
| * | ||
| * const merged: number[] = []; | ||
| * while (!heap.isEmpty()) { | ||
| * const { value, seqIndex, itemIndex } = heap.poll()!; | ||
| * merged.push(value); | ||
| * | ||
| * if (itemIndex + 1 < sequences[seqIndex].length) { | ||
| * heap.add({ | ||
| * value: sequences[seqIndex][itemIndex + 1], | ||
| * seqIndex, | ||
| * itemIndex: itemIndex + 1 | ||
| * }); | ||
| * } | ||
| * } | ||
| * | ||
| * return merged; | ||
| * } | ||
| * | ||
| * const sequences = [ | ||
| * [1, 4, 7], | ||
| * [2, 5, 8], | ||
| * [3, 6, 9] | ||
| * ]; | ||
| * console.log(mergeSortedSequences(sequences)); // [1, 2, 3, 4, 5, 6, 7, 8, 9] | ||
| * @example | ||
| * // Use Heap to dynamically maintain the median | ||
| * class MedianFinder { | ||
| * private low: MaxHeap<number>; // Max heap, stores the smaller half | ||
| * private high: MinHeap<number>; // Min heap, stores the larger half | ||
| * | ||
| * constructor() { | ||
| * this.low = new MaxHeap<number>([]); | ||
| * this.high = new MinHeap<number>([]); | ||
| * } | ||
| * | ||
| * addNum(num: number): void { | ||
| * if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num); | ||
| * else this.high.add(num); | ||
| * | ||
| * // Balance heaps | ||
| * if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!); | ||
| * else if (this.high.size > this.low.size) this.low.add(this.high.poll()!); | ||
| * } | ||
| * | ||
| * findMedian(): number { | ||
| * if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2; | ||
| * return this.low.peek()!; | ||
| * } | ||
| * } | ||
| * | ||
| * const medianFinder = new MedianFinder(); | ||
| * medianFinder.addNum(10); | ||
| * console.log(medianFinder.findMedian()); // 10 | ||
| * medianFinder.addNum(20); | ||
| * console.log(medianFinder.findMedian()); // 15 | ||
| * medianFinder.addNum(30); | ||
| * console.log(medianFinder.findMedian()); // 20 | ||
| * medianFinder.addNum(40); | ||
| * console.log(medianFinder.findMedian()); // 25 | ||
| * medianFinder.addNum(50); | ||
| * console.log(medianFinder.findMedian()); // 30 | ||
| * @example | ||
| * // Use Heap for load balancing | ||
| * function loadBalance(requests: number[], servers: number): number[] { | ||
| * const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap | ||
| * const serverLoads = new Array(servers).fill(0); | ||
| * | ||
| * for (let i = 0; i < servers; i++) { | ||
| * serverHeap.add({ id: i, load: 0 }); | ||
| * } | ||
| * | ||
| * requests.forEach(req => { | ||
| * const server = serverHeap.poll()!; | ||
| * serverLoads[server.id] += req; | ||
| * server.load += req; | ||
| * serverHeap.add(server); // The server after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return serverLoads; | ||
| * } | ||
| * | ||
| * const requests = [5, 2, 8, 3, 7]; | ||
| * console.log(loadBalance(requests, 3)); // [12, 8, 5] | ||
| * @example | ||
| * // Use Heap to schedule tasks | ||
| * type Task = [string, number]; | ||
| * | ||
| * function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> { | ||
| * const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap | ||
| * const allocation = new Map<number, Task[]>(); | ||
| * | ||
| * // Initialize the load on each machine | ||
| * for (let i = 0; i < machines; i++) { | ||
| * machineHeap.add({ id: i, load: 0 }); | ||
| * allocation.set(i, []); | ||
| * } | ||
| * | ||
| * // Assign tasks | ||
| * tasks.forEach(([task, load]) => { | ||
| * const machine = machineHeap.poll()!; | ||
| * allocation.get(machine.id)!.push([task, load]); | ||
| * machine.load += load; | ||
| * machineHeap.add(machine); // The machine after updating the load is re-entered into the heap | ||
| * }); | ||
| * | ||
| * return allocation; | ||
| * } | ||
| * | ||
| * const tasks: Task[] = [ | ||
| * ['Task1', 3], | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task4', 5], | ||
| * ['Task5', 4] | ||
| * ]; | ||
| * const expectedMap = new Map<number, Task[]>(); | ||
| * expectedMap.set(0, [ | ||
| * ['Task1', 3], | ||
| * ['Task4', 5] | ||
| * ]); | ||
| * expectedMap.set(1, [ | ||
| * ['Task2', 1], | ||
| * ['Task3', 2], | ||
| * ['Task5', 4] | ||
| * ]); | ||
| * console.log(scheduleTasks(tasks, 2)); // expectedMap | ||
| */ | ||
@@ -24,0 +189,0 @@ export class Heap<E = any, R = any> extends IterableElementBase<E, R, Heap<E, R>> { |
@@ -89,2 +89,428 @@ /** | ||
| * 4. High Efficiency in Insertion and Deletion: Adding or removing elements in a linked list does not require moving other elements, making these operations more efficient than in arrays. | ||
| * @example | ||
| * // text editor operation history | ||
| * const actions = [ | ||
| * { type: 'insert', content: 'first line of text' }, | ||
| * { type: 'insert', content: 'second line of text' }, | ||
| * { type: 'delete', content: 'delete the first line' } | ||
| * ]; | ||
| * const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions); | ||
| * | ||
| * console.log(editorHistory.last?.type); // 'delete' | ||
| * console.log(editorHistory.pop()?.content); // 'delete the first line' | ||
| * console.log(editorHistory.last?.type); // 'insert' | ||
| * @example | ||
| * // Browser history | ||
| * const browserHistory = new DoublyLinkedList<string>(); | ||
| * | ||
| * browserHistory.push('home page'); | ||
| * browserHistory.push('search page'); | ||
| * browserHistory.push('details page'); | ||
| * | ||
| * console.log(browserHistory.last); // 'details page' | ||
| * console.log(browserHistory.pop()); // 'details page' | ||
| * console.log(browserHistory.last); // 'search page' | ||
| * @example | ||
| * // Use DoublyLinkedList to implement music player | ||
| * // Define the Song interface | ||
| * interface Song { | ||
| * title: string; | ||
| * artist: string; | ||
| * duration: number; // duration in seconds | ||
| * } | ||
| * | ||
| * class Player { | ||
| * private playlist: DoublyLinkedList<Song>; | ||
| * private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined; | ||
| * | ||
| * constructor(songs: Song[]) { | ||
| * this.playlist = new DoublyLinkedList<Song>(); | ||
| * songs.forEach(song => this.playlist.push(song)); | ||
| * this.currentSong = this.playlist.head; | ||
| * } | ||
| * | ||
| * // Play the next song in the playlist | ||
| * playNext(): Song | undefined { | ||
| * if (!this.currentSong?.next) { | ||
| * this.currentSong = this.playlist.head; // Loop to the first song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.next; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Play the previous song in the playlist | ||
| * playPrevious(): Song | undefined { | ||
| * if (!this.currentSong?.prev) { | ||
| * this.currentSong = this.playlist.tail; // Loop to the last song | ||
| * } else { | ||
| * this.currentSong = this.currentSong.prev; | ||
| * } | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Get the current song | ||
| * getCurrentSong(): Song | undefined { | ||
| * return this.currentSong?.value; | ||
| * } | ||
| * | ||
| * // Loop through the playlist twice | ||
| * loopThroughPlaylist(): Song[] { | ||
| * const playedSongs: Song[] = []; | ||
| * const initialNode = this.currentSong; | ||
| * | ||
| * // Loop through the playlist twice | ||
| * for (let i = 0; i < this.playlist.size * 2; i++) { | ||
| * playedSongs.push(this.currentSong!.value); | ||
| * this.currentSong = this.currentSong!.next || this.playlist.head; // Loop back to the start if needed | ||
| * } | ||
| * | ||
| * // Reset the current song to the initial song | ||
| * this.currentSong = initialNode; | ||
| * return playedSongs; | ||
| * } | ||
| * } | ||
| * | ||
| * const songs = [ | ||
| * { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * ]; | ||
| * let player = new Player(songs); | ||
| * // should play the next song | ||
| * player = new Player(songs); | ||
| * const firstSong = player.getCurrentSong(); | ||
| * const nextSong = player.playNext(); | ||
| * | ||
| * // Expect the next song to be "Hotel California by Eagles" | ||
| * console.log(nextSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * console.log(firstSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should play the previous song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * const currentSong = player.getCurrentSong(); | ||
| * const previousSong = player.playPrevious(); | ||
| * | ||
| * // Expect the previous song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(previousSong); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * console.log(currentSong); // { title: 'Hotel California', artist: 'Eagles', duration: 391 } | ||
| * | ||
| * // should loop to the first song when playing next from the last song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const nextSongToFirst = player.playNext(); // Should loop to the first song | ||
| * | ||
| * // Expect the next song to be "Bohemian Rhapsody by Queen" | ||
| * console.log(nextSongToFirst); // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 } | ||
| * | ||
| * // should loop to the last song when playing previous from the first song | ||
| * player = new Player(songs); | ||
| * player.playNext(); // Move to the first song | ||
| * player.playNext(); // Move to the second song | ||
| * player.playNext(); // Move to the third song | ||
| * player.playNext(); // Move to the fourth song | ||
| * | ||
| * const previousToLast = player.playPrevious(); // Should loop to the last song | ||
| * | ||
| * // Expect the previous song to be "Billie Jean by Michael Jackson" | ||
| * console.log(previousToLast); // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * | ||
| * // should loop through the entire playlist | ||
| * player = new Player(songs); | ||
| * const playedSongs = player.loopThroughPlaylist(); | ||
| * | ||
| * // The expected order of songs for two loops | ||
| * console.log(playedSongs); // [ | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }, | ||
| * // { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| * // { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| * // { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| * // { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| * // ] | ||
| * @example | ||
| * // Use DoublyLinkedList to implement LRU cache | ||
| * interface CacheEntry<K, V> { | ||
| * key: K; | ||
| * value: V; | ||
| * } | ||
| * | ||
| * class LRUCache<K = string, V = any> { | ||
| * private readonly capacity: number; | ||
| * private list: DoublyLinkedList<CacheEntry<K, V>>; | ||
| * private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>; | ||
| * | ||
| * constructor(capacity: number) { | ||
| * if (capacity <= 0) { | ||
| * throw new Error('lru cache capacity must be greater than 0'); | ||
| * } | ||
| * this.capacity = capacity; | ||
| * this.list = new DoublyLinkedList<CacheEntry<K, V>>(); | ||
| * this.map = new Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>(); | ||
| * } | ||
| * | ||
| * // Get cached value | ||
| * get(key: K): V | undefined { | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (!node) return undefined; | ||
| * | ||
| * // Move the visited node to the head of the linked list (most recently used) | ||
| * this.moveToFront(node); | ||
| * | ||
| * return node.value.value; | ||
| * } | ||
| * | ||
| * // Set cache value | ||
| * set(key: K, value: V): void { | ||
| * // Check if it already exists | ||
| * const node = this.map.get(key); | ||
| * | ||
| * if (node) { | ||
| * // Update value and move to head | ||
| * node.value.value = value; | ||
| * this.moveToFront(node); | ||
| * return; | ||
| * } | ||
| * | ||
| * // Check capacity | ||
| * if (this.list.size >= this.capacity) { | ||
| * // Delete the least recently used element (the tail of the linked list) | ||
| * const removedNode = this.list.tail; | ||
| * if (removedNode) { | ||
| * this.map.delete(removedNode.value.key); | ||
| * this.list.pop(); | ||
| * } | ||
| * } | ||
| * | ||
| * // Create new node and add to head | ||
| * const newEntry: CacheEntry<K, V> = { key, value }; | ||
| * this.list.unshift(newEntry); | ||
| * | ||
| * // Save node reference in map | ||
| * const newNode = this.list.head; | ||
| * if (newNode) { | ||
| * this.map.set(key, newNode); | ||
| * } | ||
| * } | ||
| * | ||
| * // Move the node to the head of the linked list | ||
| * private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void { | ||
| * this.list.delete(node); | ||
| * this.list.unshift(node.value); | ||
| * } | ||
| * | ||
| * // Delete specific key | ||
| * delete(key: K): boolean { | ||
| * const node = this.map.get(key); | ||
| * if (!node) return false; | ||
| * | ||
| * // Remove from linked list | ||
| * this.list.delete(node); | ||
| * // Remove from map | ||
| * this.map.delete(key); | ||
| * | ||
| * return true; | ||
| * } | ||
| * | ||
| * // Clear cache | ||
| * clear(): void { | ||
| * this.list.clear(); | ||
| * this.map.clear(); | ||
| * } | ||
| * | ||
| * // Get the current cache size | ||
| * get size(): number { | ||
| * return this.list.size; | ||
| * } | ||
| * | ||
| * // Check if it is empty | ||
| * get isEmpty(): boolean { | ||
| * return this.list.isEmpty(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should set and get values correctly | ||
| * const cache = new LRUCache<string, number>(3); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * | ||
| * // The least recently used element should be evicted when capacity is exceeded | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * cache.set('d', 4); // This will eliminate 'a' | ||
| * | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.get('b')); // 2 | ||
| * console.log(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // The priority of an element should be updated when it is accessed | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.set('c', 3); | ||
| * | ||
| * cache.get('a'); // access 'a' | ||
| * cache.set('d', 4); // This will eliminate 'b' | ||
| * | ||
| * console.log(cache.get('a')); // 1 | ||
| * console.log(cache.get('b')).toBeUndefined(); | ||
| * expect(cache.get('c')); // 3 | ||
| * console.log(cache.get('d')); // 4 | ||
| * | ||
| * // Should support updating existing keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('a', 10); | ||
| * | ||
| * console.log(cache.get('a')); // 10 | ||
| * | ||
| * // Should support deleting specified keys | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * | ||
| * console.log(cache.delete('a')); // true | ||
| * console.log(cache.get('a')).toBeUndefined(); | ||
| * expect(cache.size); // 1 | ||
| * | ||
| * // Should support clearing cache | ||
| * cache.clear(); | ||
| * cache.set('a', 1); | ||
| * cache.set('b', 2); | ||
| * cache.clear(); | ||
| * | ||
| * console.log(cache.size); // 0 | ||
| * console.log(cache.isEmpty); // true | ||
| * @example | ||
| * // finding lyrics by timestamp in Coldplay's "Fix You" | ||
| * // Create a DoublyLinkedList to store song lyrics with timestamps | ||
| * const lyricsList = new DoublyLinkedList<{ time: number; text: string }>(); | ||
| * | ||
| * // Detailed lyrics with precise timestamps (in milliseconds) | ||
| * const lyrics = [ | ||
| * { time: 0, text: "When you try your best, but you don't succeed" }, | ||
| * { time: 4000, text: 'When you get what you want, but not what you need' }, | ||
| * { time: 8000, text: "When you feel so tired, but you can't sleep" }, | ||
| * { time: 12000, text: 'Stuck in reverse' }, | ||
| * { time: 16000, text: 'And the tears come streaming down your face' }, | ||
| * { time: 20000, text: "When you lose something you can't replace" }, | ||
| * { time: 24000, text: 'When you love someone, but it goes to waste' }, | ||
| * { time: 28000, text: 'Could it be worse?' }, | ||
| * { time: 32000, text: 'Lights will guide you home' }, | ||
| * { time: 36000, text: 'And ignite your bones' }, | ||
| * { time: 40000, text: 'And I will try to fix you' } | ||
| * ]; | ||
| * | ||
| * // Populate the DoublyLinkedList with lyrics | ||
| * lyrics.forEach(lyric => lyricsList.push(lyric)); | ||
| * | ||
| * // Test different scenarios of lyric synchronization | ||
| * | ||
| * // 1. Find lyric at exact timestamp | ||
| * const exactTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 36000); | ||
| * console.log(exactTimeLyric?.text); // 'And ignite your bones' | ||
| * | ||
| * // 2. Find lyric between timestamps | ||
| * const betweenTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 22000); | ||
| * console.log(betweenTimeLyric?.text); // "When you lose something you can't replace" | ||
| * | ||
| * // 3. Find first lyric when timestamp is less than first entry | ||
| * const earlyTimeLyric = lyricsList.findBackward(lyric => lyric.time <= -1000); | ||
| * console.log(earlyTimeLyric).toBeUndefined(); | ||
| * | ||
| * // 4. Find last lyric when timestamp is after last entry | ||
| * const lateTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 50000); | ||
| * expect(lateTimeLyric?.text); // 'And I will try to fix you' | ||
| * @example | ||
| * // cpu process schedules | ||
| * class Process { | ||
| * constructor( | ||
| * public id: number, | ||
| * public priority: number | ||
| * ) {} | ||
| * | ||
| * execute(): string { | ||
| * return `Process ${this.id} executed.`; | ||
| * } | ||
| * } | ||
| * | ||
| * class Scheduler { | ||
| * private queue: DoublyLinkedList<Process>; | ||
| * | ||
| * constructor() { | ||
| * this.queue = new DoublyLinkedList<Process>(); | ||
| * } | ||
| * | ||
| * addProcess(process: Process): void { | ||
| * // Insert processes into a queue based on priority, keeping priority in descending order | ||
| * let current = this.queue.head; | ||
| * while (current && current.value.priority >= process.priority) { | ||
| * current = current.next; | ||
| * } | ||
| * | ||
| * if (!current) { | ||
| * this.queue.push(process); | ||
| * } else { | ||
| * this.queue.addBefore(current, process); | ||
| * } | ||
| * } | ||
| * | ||
| * executeNext(): string | undefined { | ||
| * // Execute tasks at the head of the queue in order | ||
| * const process = this.queue.shift(); | ||
| * return process ? process.execute() : undefined; | ||
| * } | ||
| * | ||
| * listProcesses(): string[] { | ||
| * return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`); | ||
| * } | ||
| * | ||
| * clear(): void { | ||
| * this.queue.clear(); | ||
| * } | ||
| * } | ||
| * | ||
| * // should add processes based on priority | ||
| * let scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * scheduler.addProcess(new Process(3, 15)); | ||
| * | ||
| * console.log(scheduler.listProcesses()); // [ | ||
| * // 'Process 2 (Priority: 20)', | ||
| * // 'Process 3 (Priority: 15)', | ||
| * // 'Process 1 (Priority: 10)' | ||
| * // ] | ||
| * | ||
| * // should execute the highest priority process | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * console.log(scheduler.executeNext()); // 'Process 2 executed.' | ||
| * console.log(scheduler.listProcesses()); // ['Process 1 (Priority: 10)'] | ||
| * | ||
| * // should clear all processes | ||
| * scheduler = new Scheduler(); | ||
| * scheduler.addProcess(new Process(1, 10)); | ||
| * scheduler.addProcess(new Process(2, 20)); | ||
| * | ||
| * scheduler.clear(); | ||
| * console.log(scheduler.listProcesses()); // [] | ||
| */ | ||
@@ -492,4 +918,4 @@ export class DoublyLinkedList<E = any, R = any> extends IterableElementBase<E, R, DoublyLinkedList<E, R>> { | ||
| const nextNode = node.next; | ||
| prevNode!.next = nextNode; | ||
| nextNode!.prev = prevNode; | ||
| if (prevNode) prevNode.next = nextNode; | ||
| if (nextNode) nextNode.prev = prevNode; | ||
| this._size--; | ||
@@ -496,0 +922,0 @@ } |
@@ -460,1 +460,174 @@ import { FibonacciHeap, Heap, MaxHeap, MinHeap } from '../../../../src'; | ||
| }); | ||
| describe('classic use', () => { | ||
| it('@example Use Heap to sort an array', () => { | ||
| function heapSort(arr: number[]): number[] { | ||
| const heap = new Heap<number>(arr, { comparator: (a, b) => a - b }); | ||
| const sorted: number[] = []; | ||
| while (!heap.isEmpty()) { | ||
| sorted.push(heap.poll()!); // Poll minimum element | ||
| } | ||
| return sorted; | ||
| } | ||
| const array = [5, 3, 8, 4, 1, 2]; | ||
| expect(heapSort(array)).toEqual([1, 2, 3, 4, 5, 8]); | ||
| }); | ||
| it('@example Use Heap to solve top k problems', () => { | ||
| function topKElements(arr: number[], k: number): number[] { | ||
| const heap = new Heap<number>([], { comparator: (a, b) => b - a }); // Max heap | ||
| arr.forEach(num => { | ||
| heap.add(num); | ||
| if (heap.size > k) heap.poll(); // Keep the heap size at K | ||
| }); | ||
| return heap.toArray(); | ||
| } | ||
| const numbers = [10, 30, 20, 5, 15, 25]; | ||
| expect(topKElements(numbers, 3)).toEqual([15, 10, 5]); | ||
| }); | ||
| it('@example Use Heap to merge sorted sequences', () => { | ||
| function mergeSortedSequences(sequences: number[][]): number[] { | ||
| const heap = new Heap<{ value: number; seqIndex: number; itemIndex: number }>([], { | ||
| comparator: (a, b) => a.value - b.value // Min heap | ||
| }); | ||
| // Initialize heap | ||
| sequences.forEach((seq, seqIndex) => { | ||
| if (seq.length) { | ||
| heap.add({ value: seq[0], seqIndex, itemIndex: 0 }); | ||
| } | ||
| }); | ||
| const merged: number[] = []; | ||
| while (!heap.isEmpty()) { | ||
| const { value, seqIndex, itemIndex } = heap.poll()!; | ||
| merged.push(value); | ||
| if (itemIndex + 1 < sequences[seqIndex].length) { | ||
| heap.add({ | ||
| value: sequences[seqIndex][itemIndex + 1], | ||
| seqIndex, | ||
| itemIndex: itemIndex + 1 | ||
| }); | ||
| } | ||
| } | ||
| return merged; | ||
| } | ||
| const sequences = [ | ||
| [1, 4, 7], | ||
| [2, 5, 8], | ||
| [3, 6, 9] | ||
| ]; | ||
| expect(mergeSortedSequences(sequences)).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9]); | ||
| }); | ||
| it('@example Use Heap to dynamically maintain the median', () => { | ||
| class MedianFinder { | ||
| private low: MaxHeap<number>; // Max heap, stores the smaller half | ||
| private high: MinHeap<number>; // Min heap, stores the larger half | ||
| constructor() { | ||
| this.low = new MaxHeap<number>([]); | ||
| this.high = new MinHeap<number>([]); | ||
| } | ||
| addNum(num: number): void { | ||
| if (this.low.isEmpty() || num <= this.low.peek()!) this.low.add(num); | ||
| else this.high.add(num); | ||
| // Balance heaps | ||
| if (this.low.size > this.high.size + 1) this.high.add(this.low.poll()!); | ||
| else if (this.high.size > this.low.size) this.low.add(this.high.poll()!); | ||
| } | ||
| findMedian(): number { | ||
| if (this.low.size === this.high.size) return (this.low.peek()! + this.high.peek()!) / 2; | ||
| return this.low.peek()!; | ||
| } | ||
| } | ||
| const medianFinder = new MedianFinder(); | ||
| medianFinder.addNum(10); | ||
| expect(medianFinder.findMedian()).toBe(10); | ||
| medianFinder.addNum(20); | ||
| expect(medianFinder.findMedian()).toBe(15); | ||
| medianFinder.addNum(30); | ||
| expect(medianFinder.findMedian()).toBe(20); | ||
| medianFinder.addNum(40); | ||
| expect(medianFinder.findMedian()).toBe(25); | ||
| medianFinder.addNum(50); | ||
| expect(medianFinder.findMedian()).toBe(30); | ||
| }); | ||
| it('@example Use Heap for load balancing', () => { | ||
| function loadBalance(requests: number[], servers: number): number[] { | ||
| const serverHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // min heap | ||
| const serverLoads = new Array(servers).fill(0); | ||
| for (let i = 0; i < servers; i++) { | ||
| serverHeap.add({ id: i, load: 0 }); | ||
| } | ||
| requests.forEach(req => { | ||
| const server = serverHeap.poll()!; | ||
| serverLoads[server.id] += req; | ||
| server.load += req; | ||
| serverHeap.add(server); // The server after updating the load is re-entered into the heap | ||
| }); | ||
| return serverLoads; | ||
| } | ||
| const requests = [5, 2, 8, 3, 7]; | ||
| expect(loadBalance(requests, 3)).toEqual([12, 8, 5]); | ||
| }); | ||
| it('@example Use Heap to schedule tasks', () => { | ||
| type Task = [string, number]; | ||
| function scheduleTasks(tasks: Task[], machines: number): Map<number, Task[]> { | ||
| const machineHeap = new Heap<{ id: number; load: number }>([], { comparator: (a, b) => a.load - b.load }); // Min heap | ||
| const allocation = new Map<number, Task[]>(); | ||
| // Initialize the load on each machine | ||
| for (let i = 0; i < machines; i++) { | ||
| machineHeap.add({ id: i, load: 0 }); | ||
| allocation.set(i, []); | ||
| } | ||
| // Assign tasks | ||
| tasks.forEach(([task, load]) => { | ||
| const machine = machineHeap.poll()!; | ||
| allocation.get(machine.id)!.push([task, load]); | ||
| machine.load += load; | ||
| machineHeap.add(machine); // The machine after updating the load is re-entered into the heap | ||
| }); | ||
| return allocation; | ||
| } | ||
| const tasks: Task[] = [ | ||
| ['Task1', 3], | ||
| ['Task2', 1], | ||
| ['Task3', 2], | ||
| ['Task4', 5], | ||
| ['Task5', 4] | ||
| ]; | ||
| const expectedMap = new Map<number, Task[]>(); | ||
| expectedMap.set(0, [ | ||
| ['Task1', 3], | ||
| ['Task4', 5] | ||
| ]); | ||
| expectedMap.set(1, [ | ||
| ['Task2', 1], | ||
| ['Task3', 2], | ||
| ['Task5', 4] | ||
| ]); | ||
| expect(scheduleTasks(tasks, 2)).toEqual(expectedMap); | ||
| }); | ||
| }); |
@@ -505,1 +505,435 @@ import { DoublyLinkedList, DoublyLinkedListNode } from '../../../../src'; | ||
| }); | ||
| describe('classic use', () => { | ||
| it('@example text editor operation history', () => { | ||
| const actions = [ | ||
| { type: 'insert', content: 'first line of text' }, | ||
| { type: 'insert', content: 'second line of text' }, | ||
| { type: 'delete', content: 'delete the first line' } | ||
| ]; | ||
| const editorHistory = new DoublyLinkedList<{ type: string; content: string }>(actions); | ||
| expect(editorHistory.last?.type).toBe('delete'); | ||
| expect(editorHistory.pop()?.content).toBe('delete the first line'); | ||
| expect(editorHistory.last?.type).toBe('insert'); | ||
| }); | ||
| it('@example Browser history', () => { | ||
| const browserHistory = new DoublyLinkedList<string>(); | ||
| browserHistory.push('home page'); | ||
| browserHistory.push('search page'); | ||
| browserHistory.push('details page'); | ||
| expect(browserHistory.last).toBe('details page'); | ||
| expect(browserHistory.pop()).toBe('details page'); | ||
| expect(browserHistory.last).toBe('search page'); | ||
| }); | ||
| it('@example Use DoublyLinkedList to implement music player', () => { | ||
| // Define the Song interface | ||
| interface Song { | ||
| title: string; | ||
| artist: string; | ||
| duration: number; // duration in seconds | ||
| } | ||
| class Player { | ||
| private playlist: DoublyLinkedList<Song>; | ||
| private currentSong: ReturnType<typeof this.playlist.getNodeAt> | undefined; | ||
| constructor(songs: Song[]) { | ||
| this.playlist = new DoublyLinkedList<Song>(); | ||
| songs.forEach(song => this.playlist.push(song)); | ||
| this.currentSong = this.playlist.head; | ||
| } | ||
| // Play the next song in the playlist | ||
| playNext(): Song | undefined { | ||
| if (!this.currentSong?.next) { | ||
| this.currentSong = this.playlist.head; // Loop to the first song | ||
| } else { | ||
| this.currentSong = this.currentSong.next; | ||
| } | ||
| return this.currentSong?.value; | ||
| } | ||
| // Play the previous song in the playlist | ||
| playPrevious(): Song | undefined { | ||
| if (!this.currentSong?.prev) { | ||
| this.currentSong = this.playlist.tail; // Loop to the last song | ||
| } else { | ||
| this.currentSong = this.currentSong.prev; | ||
| } | ||
| return this.currentSong?.value; | ||
| } | ||
| // Get the current song | ||
| getCurrentSong(): Song | undefined { | ||
| return this.currentSong?.value; | ||
| } | ||
| // Loop through the playlist twice | ||
| loopThroughPlaylist(): Song[] { | ||
| const playedSongs: Song[] = []; | ||
| const initialNode = this.currentSong; | ||
| // Loop through the playlist twice | ||
| for (let i = 0; i < this.playlist.size * 2; i++) { | ||
| playedSongs.push(this.currentSong!.value); | ||
| this.currentSong = this.currentSong!.next || this.playlist.head; // Loop back to the start if needed | ||
| } | ||
| // Reset the current song to the initial song | ||
| this.currentSong = initialNode; | ||
| return playedSongs; | ||
| } | ||
| } | ||
| const songs = [ | ||
| { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| ]; | ||
| let player = new Player(songs); | ||
| // should play the next song | ||
| player = new Player(songs); | ||
| const firstSong = player.getCurrentSong(); | ||
| const nextSong = player.playNext(); | ||
| // Expect the next song to be "Hotel California by Eagles" | ||
| expect(nextSong).toEqual({ title: 'Hotel California', artist: 'Eagles', duration: 391 }); | ||
| expect(firstSong).toEqual({ title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }); | ||
| // should play the previous song | ||
| player = new Player(songs); | ||
| player.playNext(); // Move to the second song | ||
| const currentSong = player.getCurrentSong(); | ||
| const previousSong = player.playPrevious(); | ||
| // Expect the previous song to be "Bohemian Rhapsody by Queen" | ||
| expect(previousSong).toEqual({ title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }); | ||
| expect(currentSong).toEqual({ title: 'Hotel California', artist: 'Eagles', duration: 391 }); | ||
| // should loop to the first song when playing next from the last song | ||
| player = new Player(songs); | ||
| player.playNext(); // Move to the second song | ||
| player.playNext(); // Move to the third song | ||
| player.playNext(); // Move to the fourth song | ||
| const nextSongToFirst = player.playNext(); // Should loop to the first song | ||
| // Expect the next song to be "Bohemian Rhapsody by Queen" | ||
| expect(nextSongToFirst).toEqual({ title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }); | ||
| // should loop to the last song when playing previous from the first song | ||
| player = new Player(songs); | ||
| player.playNext(); // Move to the first song | ||
| player.playNext(); // Move to the second song | ||
| player.playNext(); // Move to the third song | ||
| player.playNext(); // Move to the fourth song | ||
| const previousToLast = player.playPrevious(); // Should loop to the last song | ||
| // Expect the previous song to be "Billie Jean by Michael Jackson" | ||
| expect(previousToLast).toEqual({ title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }); | ||
| // should loop through the entire playlist | ||
| player = new Player(songs); | ||
| const playedSongs = player.loopThroughPlaylist(); | ||
| // The expected order of songs for two loops | ||
| expect(playedSongs).toEqual([ | ||
| { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 }, | ||
| { title: 'Bohemian Rhapsody', artist: 'Queen', duration: 354 }, | ||
| { title: 'Hotel California', artist: 'Eagles', duration: 391 }, | ||
| { title: 'Shape of You', artist: 'Ed Sheeran', duration: 233 }, | ||
| { title: 'Billie Jean', artist: 'Michael Jackson', duration: 294 } | ||
| ]); | ||
| }); | ||
| it('@example Use DoublyLinkedList to implement LRU cache', () => { | ||
| interface CacheEntry<K, V> { | ||
| key: K; | ||
| value: V; | ||
| } | ||
| class LRUCache<K = string, V = any> { | ||
| private readonly capacity: number; | ||
| private list: DoublyLinkedList<CacheEntry<K, V>>; | ||
| private map: Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>; | ||
| constructor(capacity: number) { | ||
| if (capacity <= 0) { | ||
| throw new Error('lru cache capacity must be greater than 0'); | ||
| } | ||
| this.capacity = capacity; | ||
| this.list = new DoublyLinkedList<CacheEntry<K, V>>(); | ||
| this.map = new Map<K, DoublyLinkedListNode<CacheEntry<K, V>>>(); | ||
| } | ||
| // Get cached value | ||
| get(key: K): V | undefined { | ||
| const node = this.map.get(key); | ||
| if (!node) return undefined; | ||
| // Move the visited node to the head of the linked list (most recently used) | ||
| this.moveToFront(node); | ||
| return node.value.value; | ||
| } | ||
| // Set cache value | ||
| set(key: K, value: V): void { | ||
| // Check if it already exists | ||
| const node = this.map.get(key); | ||
| if (node) { | ||
| // Update value and move to head | ||
| node.value.value = value; | ||
| this.moveToFront(node); | ||
| return; | ||
| } | ||
| // Check capacity | ||
| if (this.list.size >= this.capacity) { | ||
| // Delete the least recently used element (the tail of the linked list) | ||
| const removedNode = this.list.tail; | ||
| if (removedNode) { | ||
| this.map.delete(removedNode.value.key); | ||
| this.list.pop(); | ||
| } | ||
| } | ||
| // Create new node and add to head | ||
| const newEntry: CacheEntry<K, V> = { key, value }; | ||
| this.list.unshift(newEntry); | ||
| // Save node reference in map | ||
| const newNode = this.list.head; | ||
| if (newNode) { | ||
| this.map.set(key, newNode); | ||
| } | ||
| } | ||
| // Move the node to the head of the linked list | ||
| private moveToFront(node: DoublyLinkedListNode<CacheEntry<K, V>>): void { | ||
| this.list.delete(node); | ||
| this.list.unshift(node.value); | ||
| } | ||
| // Delete specific key | ||
| delete(key: K): boolean { | ||
| const node = this.map.get(key); | ||
| if (!node) return false; | ||
| // Remove from linked list | ||
| this.list.delete(node); | ||
| // Remove from map | ||
| this.map.delete(key); | ||
| return true; | ||
| } | ||
| // Clear cache | ||
| clear(): void { | ||
| this.list.clear(); | ||
| this.map.clear(); | ||
| } | ||
| // Get the current cache size | ||
| get size(): number { | ||
| return this.list.size; | ||
| } | ||
| // Check if it is empty | ||
| get isEmpty(): boolean { | ||
| return this.list.isEmpty(); | ||
| } | ||
| } | ||
| // should set and get values correctly | ||
| const cache = new LRUCache<string, number>(3); | ||
| cache.set('a', 1); | ||
| cache.set('b', 2); | ||
| cache.set('c', 3); | ||
| expect(cache.get('a')).toBe(1); | ||
| expect(cache.get('b')).toBe(2); | ||
| expect(cache.get('c')).toBe(3); | ||
| // The least recently used element should be evicted when capacity is exceeded | ||
| cache.clear(); | ||
| cache.set('a', 1); | ||
| cache.set('b', 2); | ||
| cache.set('c', 3); | ||
| cache.set('d', 4); // This will eliminate 'a' | ||
| expect(cache.get('a')).toBeUndefined(); | ||
| expect(cache.get('b')).toBe(2); | ||
| expect(cache.get('c')).toBe(3); | ||
| expect(cache.get('d')).toBe(4); | ||
| // The priority of an element should be updated when it is accessed | ||
| cache.clear(); | ||
| cache.set('a', 1); | ||
| cache.set('b', 2); | ||
| cache.set('c', 3); | ||
| cache.get('a'); // access 'a' | ||
| cache.set('d', 4); // This will eliminate 'b' | ||
| expect(cache.get('a')).toBe(1); | ||
| expect(cache.get('b')).toBeUndefined(); | ||
| expect(cache.get('c')).toBe(3); | ||
| expect(cache.get('d')).toBe(4); | ||
| // Should support updating existing keys | ||
| cache.clear(); | ||
| cache.set('a', 1); | ||
| cache.set('a', 10); | ||
| expect(cache.get('a')).toBe(10); | ||
| // Should support deleting specified keys | ||
| cache.clear(); | ||
| cache.set('a', 1); | ||
| cache.set('b', 2); | ||
| expect(cache.delete('a')).toBe(true); | ||
| expect(cache.get('a')).toBeUndefined(); | ||
| expect(cache.size).toBe(1); | ||
| // Should support clearing cache | ||
| cache.clear(); | ||
| cache.set('a', 1); | ||
| cache.set('b', 2); | ||
| cache.clear(); | ||
| expect(cache.size).toBe(0); | ||
| expect(cache.isEmpty).toBe(true); | ||
| }); | ||
| it('@example finding lyrics by timestamp in Coldplay\'s "Fix You"', () => { | ||
| // Create a DoublyLinkedList to store song lyrics with timestamps | ||
| const lyricsList = new DoublyLinkedList<{ time: number; text: string }>(); | ||
| // Detailed lyrics with precise timestamps (in milliseconds) | ||
| const lyrics = [ | ||
| { time: 0, text: "When you try your best, but you don't succeed" }, | ||
| { time: 4000, text: 'When you get what you want, but not what you need' }, | ||
| { time: 8000, text: "When you feel so tired, but you can't sleep" }, | ||
| { time: 12000, text: 'Stuck in reverse' }, | ||
| { time: 16000, text: 'And the tears come streaming down your face' }, | ||
| { time: 20000, text: "When you lose something you can't replace" }, | ||
| { time: 24000, text: 'When you love someone, but it goes to waste' }, | ||
| { time: 28000, text: 'Could it be worse?' }, | ||
| { time: 32000, text: 'Lights will guide you home' }, | ||
| { time: 36000, text: 'And ignite your bones' }, | ||
| { time: 40000, text: 'And I will try to fix you' } | ||
| ]; | ||
| // Populate the DoublyLinkedList with lyrics | ||
| lyrics.forEach(lyric => lyricsList.push(lyric)); | ||
| // Test different scenarios of lyric synchronization | ||
| // 1. Find lyric at exact timestamp | ||
| const exactTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 36000); | ||
| expect(exactTimeLyric?.text).toBe('And ignite your bones'); | ||
| // 2. Find lyric between timestamps | ||
| const betweenTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 22000); | ||
| expect(betweenTimeLyric?.text).toBe("When you lose something you can't replace"); | ||
| // 3. Find first lyric when timestamp is less than first entry | ||
| const earlyTimeLyric = lyricsList.findBackward(lyric => lyric.time <= -1000); | ||
| expect(earlyTimeLyric).toBeUndefined(); | ||
| // 4. Find last lyric when timestamp is after last entry | ||
| const lateTimeLyric = lyricsList.findBackward(lyric => lyric.time <= 50000); | ||
| expect(lateTimeLyric?.text).toBe('And I will try to fix you'); | ||
| }); | ||
| it('@example cpu process schedules', () => { | ||
| class Process { | ||
| constructor( | ||
| public id: number, | ||
| public priority: number | ||
| ) {} | ||
| execute(): string { | ||
| return `Process ${this.id} executed.`; | ||
| } | ||
| } | ||
| class Scheduler { | ||
| private queue: DoublyLinkedList<Process>; | ||
| constructor() { | ||
| this.queue = new DoublyLinkedList<Process>(); | ||
| } | ||
| addProcess(process: Process): void { | ||
| // Insert processes into a queue based on priority, keeping priority in descending order | ||
| let current = this.queue.head; | ||
| while (current && current.value.priority >= process.priority) { | ||
| current = current.next; | ||
| } | ||
| if (!current) { | ||
| this.queue.push(process); | ||
| } else { | ||
| this.queue.addBefore(current, process); | ||
| } | ||
| } | ||
| executeNext(): string | undefined { | ||
| // Execute tasks at the head of the queue in order | ||
| const process = this.queue.shift(); | ||
| return process ? process.execute() : undefined; | ||
| } | ||
| listProcesses(): string[] { | ||
| return this.queue.toArray().map(process => `Process ${process.id} (Priority: ${process.priority})`); | ||
| } | ||
| clear(): void { | ||
| this.queue.clear(); | ||
| } | ||
| } | ||
| // should add processes based on priority | ||
| let scheduler = new Scheduler(); | ||
| scheduler.addProcess(new Process(1, 10)); | ||
| scheduler.addProcess(new Process(2, 20)); | ||
| scheduler.addProcess(new Process(3, 15)); | ||
| expect(scheduler.listProcesses()).toEqual([ | ||
| 'Process 2 (Priority: 20)', | ||
| 'Process 3 (Priority: 15)', | ||
| 'Process 1 (Priority: 10)' | ||
| ]); | ||
| // should execute the highest priority process | ||
| scheduler = new Scheduler(); | ||
| scheduler.addProcess(new Process(1, 10)); | ||
| scheduler.addProcess(new Process(2, 20)); | ||
| expect(scheduler.executeNext()).toBe('Process 2 executed.'); | ||
| expect(scheduler.listProcesses()).toEqual(['Process 1 (Priority: 10)']); | ||
| // should clear all processes | ||
| scheduler = new Scheduler(); | ||
| scheduler.addProcess(new Process(1, 10)); | ||
| scheduler.addProcess(new Process(2, 20)); | ||
| scheduler.clear(); | ||
| expect(scheduler.listProcesses()).toEqual([]); | ||
| }); | ||
| }); |
@@ -1,1 +0,49 @@ | ||
| export {}; | ||
| /** | ||
| * Convert any string to CamelCase format | ||
| */ | ||
| export function toCamelCase(str: string): string { | ||
| return str.toLowerCase().replace(/[^a-zA-Z0-9]+(.)/g, (_, chr) => chr.toUpperCase()); | ||
| } | ||
| /** | ||
| * Convert any string to SnakeCase format | ||
| */ | ||
| export function toSnakeCase(str: string): string { | ||
| return str | ||
| .replace(/([a-z])([A-Z])/g, '$1_$2') // Add underline between lowercase and uppercase letters | ||
| .toLowerCase() // Convert to lowercase | ||
| .replace(/[^a-z0-9]+/g, '_'); // Replace non-alphanumeric characters with underscores | ||
| } | ||
| /** | ||
| * Convert any string to PascalCase format (first letter capitalized) | ||
| */ | ||
| export function toPascalCase(str: string): string { | ||
| return str | ||
| .replace(/([a-z])([A-Z])/g, '$1 $2') // Add space between lowercase and uppercase letters | ||
| .replace(/[^a-zA-Z0-9]+/g, ' ') // Replace non-alphanumeric characters with spaces | ||
| .split(' ') // Separate strings by spaces | ||
| .map(word => word.charAt(0).toUpperCase() + word.slice(1).toLowerCase()) // The first letter is capitalized, the rest are lowercase | ||
| .join(''); // Combine into a string | ||
| } | ||
| /** | ||
| * Convert CamelCase or SnakeCase string to string format with specified separator | ||
| */ | ||
| export function toSeparatedCase(str: string, separator: string = '_'): string { | ||
| return str | ||
| .replace(/([a-z0-9])([A-Z])/g, '$1' + separator + '$2') | ||
| .replace(/[_\s]+/g, separator) | ||
| .toLowerCase(); | ||
| } | ||
| /** | ||
| * Convert the string to all uppercase and delimit it using the specified delimiter | ||
| */ | ||
| export function toUpperSeparatedCase(str: string, separator: string = '_'): string { | ||
| return str | ||
| .toUpperCase() // Convert all letters to uppercase | ||
| .replace(/([a-z0-9])([A-Z])/g, '$1' + separator + '$2') // Add separator between lowercase letters and uppercase letters | ||
| .replace(/[^A-Z0-9]+/g, separator) // Replace non-alphanumeric characters with separators | ||
| .replace(new RegExp(`^${separator}|${separator}$`, 'g'), ''); // Remove the starting and ending separators | ||
| } |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is too big to display
Sorry, the diff of this file is too big to display
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by2.94%
5597801
- Number of package files
- increased by0.12%
867
- Lines of code
- increased by3.95%
96601
- Number of lines in readme file
- increased by0.49%
1231
No dependency changes