1
/*
2
 * Copyright 2017-2017 Amazon.com, Inc. or its affiliates. All Rights Reserved.
3
 *
4
 * Licensed under the Apache License, Version 2.0 (the "License"). You may not use this file except in compliance with
5
 * the License. A copy of the License is located at
6
 *
7
 *     http://aws.amazon.com/apache2.0/
8
 *
9
 * or in the "license" file accompanying this file. This file is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
10
 * CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions
11
 * and limitations under the License.
12
 */
13

14 1
class DoubleLinkedNode {
15
	key: string;
16
	prevNode: DoubleLinkedNode | null;
17
	nextNode: DoubleLinkedNode | null;
18

19
	constructor(keyVal?: string) {
20 1
		this.key = keyVal ? keyVal : '';
21 1
		this.prevNode = null;
22 1
		this.nextNode = null;
23
	}
24 1
}
25

26
/**
27
 * double linked list plus a hash table inside
28
 * each key in the cache stored as a node in the list
29
 * recently visited node will be rotated to the head
30
 * so the Last Recently Visited node will be at the tail
31
 *
32
 * @member head - dummy head of the linked list
33
 * @member tail - dummy tail of the linked list
34
 * @member hashtable - the hashtable which maps cache key to list node
35
 * @member length - length of the list
36
 */
37 1
export default class CacheList {
38
	private head: DoubleLinkedNode;
39
	private tail: DoubleLinkedNode;
40
	private hashtable: object;
41
	private length: number;
42

43
	/**
44
	 * initialization
45
	 */
46
	constructor() {
47 1
		this.head = new DoubleLinkedNode();
48 1
		this.tail = new DoubleLinkedNode();
49 1
		this.hashtable = {};
50 1
		this.length = 0;
51

52 1
		this.head.nextNode = this.tail;
53 1
		this.tail.prevNode = this.head;
54
	}
55

56
	/**
57
	 * insert node to the head of the list
58
	 *
59
	 * @param node
60
	 */
61 1
	private insertNodeToHead(node: DoubleLinkedNode) {
62 1
		const tmp: DoubleLinkedNode = this.head.nextNode;
63 1
		this.head.nextNode = node;
64 1
		node.nextNode = tmp;
65 1
		node.prevNode = this.head;
66 1
		tmp.prevNode = node;
67

68 1
		this.length = this.length + 1;
69
	}
70

71
	/**
72
	 * remove node
73
	 *
74
	 * @param node
75
	 */
76 1
	private removeNode(node: DoubleLinkedNode): void {
77 1
		node.prevNode.nextNode = node.nextNode;
78 1
		node.nextNode.prevNode = node.prevNode;
79

80 1
		node.prevNode = null;
81 1
		node.nextNode = null;
82

83 1
		this.length = this.length - 1;
84
	}
85

86
	/**
87
	 * @return true if list is empty
88
	 */
89 1
	public isEmpty(): boolean {
90 1
		return this.length === 0;
91
	}
92

93
	/**
94
	 * refresh node so it is rotated to the head
95
	 *
96
	 * @param key - key of the node
97
	 */
98 1
	public refresh(key: string): void {
99 1
		const node: DoubleLinkedNode = this.hashtable[key];
100 1
		this.removeNode(node);
101 1
		this.insertNodeToHead(node);
102
	}
103

104
	/**
105
	 * insert new node to the head and add it in the hashtable
106
	 *
107
	 * @param key - the key of the node
108
	 */
109 1
	public insertItem(key: string): void {
110 1
		const node: DoubleLinkedNode = new DoubleLinkedNode(key);
111 1
		this.hashtable[key] = node;
112 1
		this.insertNodeToHead(node);
113
	}
114

115
	/**
116
	 * @return the LAST Recently Visited key
117
	 */
118 1
	public getLastItem(): string {
119 1
		return this.tail.prevNode.key;
120
	}
121

122
	/**
123
	 * remove the cache key from the list and hashtable
124
	 * @param key - the key of the node
125
	 */
126 1
	public removeItem(key: string): void {
127 1
		const removedItem: DoubleLinkedNode = this.hashtable[key];
128 1
		this.removeNode(removedItem);
129 1
		delete this.hashtable[key];
130
	}
131

132
	/**
133
	 * @return length of the list
134
	 */
135 1
	public getSize(): number {
136 1
		return this.length;
137
	}
138

139
	/**
140
	 * @return true if the key is in the hashtable
141
	 * @param key
142
	 */
143 1
	public containsKey(key: string): boolean {
144 1
		return key in this.hashtable;
145
	}
146

147
	/**
148
	 * clean up the list and hashtable
149
	 */
150 1
	public clearList(): void {
151 1
		for (const key of Object.keys(this.hashtable)) {
152 1
			if (this.hashtable.hasOwnProperty(key)) {
153 1
				delete this.hashtable[key];
154
			}
155
		}
156 1
		this.head.nextNode = this.tail;
157 1
		this.tail.prevNode = this.head;
158 1
		this.length = 0;
159
	}
160

161
	/**
162
	 * @return all keys in the hashtable
163
	 */
164 1
	public getKeys(): string[] {
165 1
		return Object.keys(this.hashtable);
166
	}
167

168
	/**
169
	 * mainly for test
170
	 *
171
	 * @param key
172
	 * @return true if key is the head node
173
	 */
174 1
	public isHeadNode(key: string): boolean {
175 1
		const node = this.hashtable[key];
176 1
		return node.prevNode === this.head;
177
	}
178

179
	/**
180
	 * mainly for test
181
	 *
182
	 * @param key
183
	 * @return true if key is the tail node
184
	 */
185 1
	public isTailNode(key: string): boolean {
186 1
		const node = this.hashtable[key];
187 1
		return node.nextNode === this.tail;
188
	}
189 1
}

Read our documentation on viewing source code .

Loading