1/* 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16package std.containers; 17 18export class ArrayAsListObject implements ListObject { 19 20 private init(capacity: int, val: Object): void { 21 this.data = new Object[capacity]; 22 for (let i = 0; i < this.data.length; ++i) { 23 this.data[i] = val; 24 } 25 this.curSize = capacity; 26 } 27 28 /** 29 * Constructs new ArrayAsList with respect to capacity and initial value 30 * 31 * @param capacity 32 * 33 * @param val 34 */ 35 constructor(capacity: int, val: Object) { 36 this.init(capacity, val); 37 } 38 39 /** 40 * Constructs new empty ArrayAsList 41 */ 42 constructor() { 43 this.init(0, new Object()); 44 } 45 46 /** 47 * Constructs new ArrayAsList with required capacity 48 * 49 * @param capacity 50 */ 51 constructor(capacity: int) { 52 this.init(capacity, new Object()); 53 } 54 55 /** 56 * Increases capacity if passed argument is greater than current capacity 57 * 58 * @param capacity 59 */ 60 public reserve(capacity: int): void { 61 if (this.data.length < capacity) { 62 let newData = new Object[capacity]; 63 for (let i = 0; i < this.curSize; ++i) { 64 newData[i] = this.data[i]; 65 } 66 this.data = newData; 67 } 68 } 69 70 /** 71 * Gets a shallow-copy of the underlying array 72 * 73 * @returns a shallow-copy of the underlying array 74 */ 75 public toArray(): Object[] { 76 let data = new Object[this.curSize]; 77 for (let i = 0; i < this.curSize; ++i) { 78 data[i] = this.data[i]; 79 } 80 return data; 81 } 82 83 private static getNewCapacity(currentCapacity: int): int { 84 // TODO(ivan-tyulyandin): select proper capacity increasing strategy 85 const fastGrowThreshold = 8192; 86 const multiplier = 2; 87 if (currentCapacity < fastGrowThreshold) { 88 // Adding 4 to jump over 0 89 return (currentCapacity + 4) * multiplier * 2; 90 } else { 91 return currentCapacity * multiplier; 92 } 93 } 94 95 /** 96 * Pushes a value to the begin of the List 97 * 98 * @param e value to push 99 */ 100 public override pushFront(e: Object): void { 101 let dst = this.data; 102 if (this.curSize == this.data.length) { 103 dst = new Object[ArrayAsListObject.getNewCapacity(this.data.length)]; 104 } 105 for (let i = this.curSize; i != 0; --i) { 106 dst[i] = this.data[i-1]; 107 } 108 this.data = dst; 109 this.data[0] = e; 110 ++this.curSize; 111 } 112 113 /** 114 * Pops a value from the begin of the List 115 * 116 * @returns popped value 117 */ 118 public override popFront(): Object { 119 assert (this.curSize > 0): "No data to popFront from ArrayAsList!" 120 let res: Object = this.data[0]; 121 for (let i = 1; i < this.curSize; ++i) { 122 this.data[i-1] = this.data[i]; 123 } 124 --this.curSize; 125 return res; 126 } 127 128 /** 129 * Pushes a value to the end of the List 130 * 131 * @param e value to push 132 */ 133 public override pushBack(e: Object): void { 134 if (this.curSize == this.data.length) { 135 let newData = new Object[ArrayAsListObject.getNewCapacity(this.data.length)]; 136 for (let i = 0; i < this.curSize; ++i) { 137 newData[i] = this.data[i]; 138 } 139 this.data = newData; 140 } 141 this.data[this.curSize] = e; 142 ++this.curSize; 143 } 144 145 /** 146 * Pops a value from the end of the List 147 * 148 * @returns popped value 149 */ 150 public override popBack(): Object { 151 assert (this.curSize > 0): "No data to popBack in ArrayAsList!" 152 --this.curSize; 153 return this.data[this.curSize]; 154 } 155 156 /** 157 * Returns number of elements in the List 158 */ 159 public override size(): int { 160 return this.curSize; 161 } 162 163 /** 164 * Returns an element at the specified index 165 * 166 * @param index element position 167 * 168 * @returns an element 169 */ 170 public override at(index: int): Object { 171 return this.data[index]; 172 } 173 174 /** 175 * Sets an element at the specified index 176 * 177 * @param index element position 178 * 179 * @param e new value 180 */ 181 public override set(index: int, e: Object): void { 182 this.data[index] = e; 183 } 184 185 /** 186 * Checks if an element is in the List 187 * 188 * @param e value to find 189 * 190 * @returns true if value present, false otherwise 191 */ 192 public override has(e: Object): boolean { 193 assert false: "Not implemented: internal issue with calling equals #10056"; 194 /* 195 for (let i = 0; i < this.curSize; ++i) { 196 if (this.data[i].equals(e)) { 197 return true; 198 } 199 } 200 */ 201 return false; 202 } 203 204/* Code below is blocked by internal issue with lambdas #9994 205 public forEach(fn: (e: Object): Object): ListObject { 206 for (let i = 0; i < this.curSize; ++i) { 207 this.data[i] = fn(this.data[i]); 208 } 209 } 210 211 // public map<U, LU implements List<U>>(fn: (e: T): U): LU { 212 public map(fn: (e: Object): ): { 213 let res = new (); 214 for (let i = 0; i < this.curSize; ++i) { 215 res.push_back(fn(this.data[i])); 216 } 217 return res; 218 } 219 220 public fold(combine: (lhs: Object, rhs: Object): Object): Object { 221 if (this.curSize > 0) { 222 let res = this.data[0]; 223 for (let i = 1; i < this.curSize; ++i) { 224 res = combine(res, this.data[i]); 225 } 226 return res; 227 } 228 throw new NoDataException(); 229 } 230 231 public foldWith(combine: (lhs: , rhs: Object): , initVal: ): { 232 let res = initVal; 233 for (let i = 0; i < this.curSize; ++i) { 234 res = combine(res, this.data[i]); 235 } 236 return res; 237 } 238 239 public filter(filterCond: (e: Object): boolean): ArrayAsListObject { 240 let indicators = new boolean[data.length]; 241 let resAmount = 0; 242 for (let i = 0; i < this.curSize; ++i) { 243 indicators[i] = filterCond(this.data[i]); 244 if (indicators[i]) { 245 ++resAmount; 246 } 247 } 248 let res = new Object[resAmount]; 249 for (let i = 0, j = 0; i < this.curSize; ++i) { 250 if (indicators[i]) { 251 res[j] = this.data[i]; 252 ++j; 253 } 254 } 255 this.data = res; 256 return this; 257 } 258 259 public sort(comparator: (lhs: Object, rhs: Object): boolean): ArrayAsListObject { 260 sortPart(this.data, 0, this.curSize, comparator); 261 return this; 262 } 263 264 private static sortPart(arr: Object[], l: int, r: int, comparator: (lhs: Object, rhs: Object): boolean): void { 265 if (l < r) { 266 // TODO(ivan-tyulyandin): select a proper constant to fall into bubbleSort instead of quickSort 267 if (r - l <= 4) { 268 bubbleSort(arr, l, r); 269 return; 270 } 271 let part = partition(arr, l, r, comparator); 272 273 sortPart(arr, l, mid, comparator); 274 sortPart(arr, mid, r, comparator); 275 } 276 } 277 278 private static partition(arr: Object[], l: int, r: int, comparator: (lhs: Object, rhs: Object): boolean): int { 279 let last = r - 1; 280 let pivot = arr[last]; 281 let lessInd = l - 1; 282 for (let i = l; i < last; ++i) { 283 if (comparator(arr[i], pivot)) { 284 ++lessInd; 285 let tmp = arr[i]; 286 arr[i] = arr[lessInd]; 287 arr[lessInd] = tmp; 288 } 289 } 290 let tmp = arr[lessInd + 1]; 291 arr[lessInd + 1] = arr[last]; 292 arr[last] = tmp; 293 return lessInd + 1; 294 } 295 296 private static bubbleSort(arr: Object[], l: int, r: int, comparator: (lhs: Object, rhs: Object): boolean): void { 297 for (let i = l; i < r; ++i) { 298 for (let j = i; j < r - i; ++j) { 299 if (comparator(arr[j + 1], arr[j])) { 300 let tmp = arr[j + 1]; 301 arr[j + 1] = arr[j]; 302 arr[j] = tmp; 303 } 304 } 305 } 306 } 307 308*/ 309 private data: Object[]; 310 private curSize: int; 311} 312