1/*
2 * Copyright (c) 2023-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
16// This contains the initial implementation of the generic ArrayAsList
17// class. After development into the stdlib, this test can be removed.
18
19interface Listt <T>  {
20    pushFront(e: T): void;
21    popFront(): T;
22    pushBack(e: T): void;
23    popBack(): T;
24
25    size(): int;
26    at(index: int): T;
27    has(e: T): boolean;
28
29    forEach(fn: (e: T) => T): Listt<T> | null;
30    map<U>(fn: (e: T) => U): Listt<U>;
31    fold(combine: (lhs: T, rhs: T) => T): T | null;
32    foldWith<U>(combine: (lhs: U, rhs: T) => U, initVal: U): U;
33    filter(filterCond: (e: T) => boolean) : Listt<T> | null;
34    sort(comparator: (lhs: T, rhs: T) => boolean) : Listt<T> | null;
35}
36
37class ArrayAsListt<T> implements Listt<T> {
38
39    private init(capacity: int, val: T | null): void {
40        this.data = new T[capacity];
41        for (let i = 0; i < this.data.length; ++i) {
42        }
43        this.curSize = capacity;
44    }
45
46    constructor(capacity: int, val: T) {
47        this.init(capacity, val);
48    }
49
50    constructor() {
51        this.init(0, null);
52    }
53
54    constructor(capacity: int) {
55        this.init(capacity, null);
56    }
57
58    public reserve(capacity: int): void {
59        if (this.data.length < capacity) {
60            let newData = new T[capacity];
61            for (let i = 0; i < this.curSize; ++i) {
62               newData[i] = this.data[i];
63            }
64            this.data = newData;
65        }
66    }
67
68    private getNewCapacity(currentCapacity: int): int {
69        const fastGrowThreshold = 8192;
70        const multiplier = 2;
71        if (currentCapacity < fastGrowThreshold) {
72            // Adding 4 to jump over 0
73            return (currentCapacity + 4) * multiplier * 2;
74        } else {
75            return currentCapacity * multiplier;
76        }
77    }
78
79    public override pushFront(e: T): void {
80        let dst = this.data;
81        if (this.curSize == this.data.length) {
82            dst = new T[this.getNewCapacity(this.data.length)];
83        }
84        for (let i = this.curSize; i != 0; --i) {
85            dst[i] = this.data[i-1];
86        }
87        this.data = dst;
88        this.data[0] = e;
89        ++this.curSize;
90    }
91
92    public override popFront(): T {
93        assert (this.curSize > 0): "No data to popFront from ArrayAsList!"
94        let res: T = this.data[0];
95        for (let i = 1; i < this.curSize; ++i) {
96            this.data[i-1] = this.data[i];
97        }
98        --this.curSize;
99        return res;
100    }
101
102    public override pushBack(e: T): void {
103        if (this.curSize == this.data.length) {
104            let newData = new T[this.getNewCapacity(this.data.length)];
105            for (let i = 0; i < this.curSize; ++i) {
106                newData[i] = this.data[i];
107            }
108            this.data = newData;
109        }
110        this.data[this.curSize] = e;
111        ++this.curSize;
112    }
113
114    public override popBack(): T {
115        assert (this.curSize > 0): "No data to popBack in ArrayAsList!"
116        --this.curSize;
117        return this.data[this.curSize];
118    }
119
120    public override size(): int {
121        return this.curSize;
122    }
123
124    public override at(index: int): T {
125        return this.data[index];
126    }
127
128    public override has(e: T): boolean {
129        assert false: "Not implemented: internal issue with calling equals";
130
131        for (let i = 0; i < this.curSize; ++i) {
132            if (__runtimeEquals(this.data[i], e)) {
133                return true;
134            }
135        }
136
137        return false;
138    }
139
140
141    public override forEach(fn: (e: T) => T): Listt<T> | null {
142        for (let i = 0; i < this.curSize; ++i) {
143            this.data[i] = fn(this.data[i]);
144        }
145        return null;
146    }
147
148    public override map<U>(fn: (e: T) => U): Listt<U> {
149        let res = new ArrayAsListt<U>();
150        for (let i = 0; i < this.curSize; ++i) {
151            res.pushBack(fn(this.data[i]));
152        }
153        return res;
154    }
155
156    public override fold(combine: (lhs: T, rhs: T) => T): T | null {
157        if (this.curSize > 0) {
158            let res = this.data[0];
159            for (let i = 1; i < this.curSize; ++i) {
160                res = combine(res, this.data[i]);
161            }
162            return res;
163        }
164        try{
165        throw new NoDataException();
166        } catch (a){}
167        return null;
168    }
169
170    public override foldWith<U>(combine: (lhs: U, rhs: T) => U, initVal: U): U {
171        let res = initVal;
172        for (let i = 0; i < this.curSize; ++i) {
173            res = combine(res, this.data[i]);
174        }
175        return res;
176    }
177
178    public override filter(filterCond: (e: T) => boolean): ArrayAsListt<T> | null {
179        let indicators = new boolean[this.data.length];
180        let resAmount = 0;
181        for (let i = 0; i < this.curSize; ++i) {
182            indicators[i] = filterCond(this.data[i]);
183            if (indicators[i]) {
184                ++resAmount;
185            }
186        }
187        let res = new T[resAmount];
188        for (let i = 0, j = 0; i < this.curSize; ++i) {
189            if (indicators[i]) {
190                res[j] = this.data[i];
191                ++j;
192            }
193        }
194        this.data = res;
195        return null;
196    }
197
198    public override sort(comparator: (lhs: T, rhs: T) => boolean): ArrayAsListt<T> | null {
199        this.sortPart(this.data, 0, this.curSize, comparator);
200        return null;
201    }
202
203    private sortPart(arr: T[], l: int, r: int, comparator: (lhs: T, rhs: T) => boolean): void {
204
205    }
206
207    private static partition(arr: T[], l: int, r: int, comparator: (lhs: T, rhs: T) => boolean): int {
208        let last = r - 1;
209        let pivot = arr[last];
210        let lessInd = l - 1;
211        for (let i = l; i < last; ++i) {
212            if (comparator(arr[i], pivot)) {
213                ++lessInd;
214                let tmp = arr[i];
215                arr[i] = arr[lessInd];
216                arr[lessInd] = tmp;
217            }
218        }
219        let tmp = arr[lessInd + 1];
220        arr[lessInd + 1] = arr[last];
221        arr[last] = tmp;
222        return lessInd + 1;
223    }
224
225    private static bubbleSort(arr: T[], l: int, r: int, comparator: (lhs: T, rhs: T) => boolean): void {
226        for (let i = l; i < r; ++i) {
227            for (let j = i; j < r - i; ++j) {
228                if (comparator(arr[j + 1], arr[j])) {
229                    let tmp = arr[j + 1];
230                    arr[j + 1] = arr[j];
231                    arr[j] = tmp;
232                }
233            }
234        }
235    }
236
237
238    private data: T[] = [];
239    private curSize: int;
240}
241