-
Notifications
You must be signed in to change notification settings - Fork 33
/
SortedList.js
211 lines (179 loc) · 4.49 KB
/
SortedList.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
const Node = require('./Node');
const defineProperty = Object.defineProperty;
/**
* Checks if a parameter is `undefined`
* @private
* @param {*} obj Object to be tested
*/
function isUndefined(obj) {
return typeof obj === 'undefined';
}
/**
* Checks if a parameter is a positive number
* @private
* @param {*} n Object to be tested
*/
function isPositiveNumber(n) {
return Number.isInteger(n) && n >= 0;
}
/**
* Throws an exception if a parameter is not a positive number
* @private
* @param {*} n Object to be tested
* @param {string} parameterName Parameter name to show in the error message.
*/
function validatePositiveNumber(n, parameterName) {
if (!isPositiveNumber(n)) {
throw new Error(`"${parameterName}" should be an Integer greater than or equal to 0. Given: ${n}`);
}
}
/**
* Returns if a node is lexicographically smaller than other node.
* @private
* @param {Node} node1 First node to compare
* @param {Node} node2 Second node to compare
*/
function isLexicographicalSmaller(node1, node2) {
return String(node1) <= String(node2);
}
/**
* Initializes an instance of a SortedList
* @constructs SortedList
*/
function SortedList() {
/**
* First Node in the Sorted List
* @name SortedList#first
* @type {(Node|null)}
* @default null
*/
this.first;
defineProperty(this, 'first', {
writable: true,
value: null /* default */
});
/**
* Length of the Sorted List
* @name SortedList#length
* @type {Number}
* @readonly
*/
this.length;
defineProperty(this, 'length', {
get() {
let currentNode = this.first;
let length = 0;
while (currentNode) {
currentNode = currentNode.getNext();
length++;
}
return length;
}
});
return this;
}
/**
* Checks if the sorted list is empty.
* @function SortedListed#isEmpty
*/
SortedList.prototype.isEmpty = function () {
return this.first === null;
};
/**
* Returns the sorted list as string
* @function SortedList#toString
*/
SortedList.prototype.toString = function () {
if (this.isEmpty()) {
return '[Empty SortedList]';
} else {
let listAsString = '';
let currentNode = this.first;
while (currentNode) {
listAsString += String(currentNode);
listAsString += currentNode.hasNext() ? ',' : '';
currentNode = currentNode.getNext();
}
return listAsString;
}
}
/**
* Returns the node at the `n`th position in the sorted list
* @function SortedList#getNode
* @param {number=} [n = last] position
*/
SortedList.prototype.getNode = function (n) {
if (this.isEmpty()) {
throw new Error('SortedList is empty.');
} else {
if (isUndefined(n)) {
n = this.length - 1;
} else {
validatePositiveNumber(n, 'n');
}
let currentNode = this.first;
let currentPosition = 0;
while (currentNode.hasNext()) {
if (currentPosition === n) break;
currentPosition++;
currentNode = currentNode.getNext();
}
return currentNode;
}
};
/**
* Returns the value of an item at the `n`th position in the sorted list.
* @function SortedList#get
* @param {number} [n = last] Position of the value
*
*/
SortedList.prototype.get = function (n) {
return this.getNode(n).value;
};
/**
* Inserts an element in the corresponding lexical sorted position.
* @function SortedList#insert
* @param {*} value Value to be inserted in order
*/
SortedList.prototype.insert = function (value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.first = newNode;
} else {
if (isLexicographicalSmaller(newNode, this.first)) {
newNode.setNext(this.first);
this.first = newNode;
} else {
let currentNode = this.first;
while (currentNode.hasNext()) {
if (isLexicographicalSmaller(newNode, currentNode.getNext())) {
newNode.setNext(currentNode.getNext());
break;
}
currentNode = currentNode.getNext();
}
currentNode.setNext(newNode);
}
}
return this;
}
/**
* Removes an item from the list and returns its value
* @function SortedList#remove
* @param {number} n Position to remove
*/
SortedList.prototype.remove = function (n) {
const nodeToRemove = this.getNode(n);
const length = this.length;
if (length === 1 || n === 0) {
this.first = this.first.getNext();
} else {
if (isUndefined(n)) {
n = length - 1;
}
let prevNode = this.getNode(n - 1);
prevNode.setNext(nodeToRemove.getNext());
}
return nodeToRemove.value;
}
module.exports = SortedList;