function search(nums: number[], target: number): number {
    if (nums.length == 0) return -1;
    let lastInd = 0;
    let mid = Math.floor(nums.length / 2);
    while (true) {
        if (nums[mid] == target) return mid;
        if (mid <= lastInd) return -1;
        let step = mid - lastInd;
        lastInd = mid;
        if (nums[mid] > target) {
            mid = Math.floor(mid - Math.abs(step / 2));
        } else {
            mid = Math.floor(mid + Math.abs(step / 2) + 1);
        }
        if (mid < 0 || mid >= nums.length) return -1;
    }
}

class MaxStack {
    private stack: number[];
    constructor() {
        this.stack = [];
    }

    push(val: number) {
        this.stack.push(val);
        this.sortFromBottom();
    }

    sortFromBottom() {
        let currentIndex = this.getLastIndex();
        while (true) {
            let parentIndex = this.getParentIndex(currentIndex);
            if (currentIndex < 0 || parentIndex < 0 || this.stack[parentIndex] > this.stack[currentIndex]) {
                break;
            } else {
                this.swap(parentIndex, currentIndex);
                currentIndex = parentIndex;
            }
        }
    }

    pop() {
        this.swap(0, this.getLastIndex());
        const popVal = this.stack.pop();
        this.sortFromTop();
        return popVal;
    }

    sortFromTop() {
        let currentIndex = 0;
        while (true) {
            let leftIndex = this.getLeftIndex(currentIndex);
            if(leftIndex>this.getLastIndex()) break; //如果没有左节点直接退出
            let rightIndex = this.getRightIndex(currentIndex);
            let leftVal = this.stack[leftIndex];
            let rightVal = this.stack[rightIndex];
            let currentVal = this.stack[currentIndex];
            if (currentIndex == this.getLastIndex() || (currentVal > rightVal && currentVal > leftVal)) break;
            let maxInd = leftVal > rightVal ? leftIndex : rightIndex;
            if (leftIndex > this.getLastIndex() || rightIndex > this.getLastIndex() || this.stack[maxInd] <= currentVal) break;
            else {
                this.swap(maxInd, currentIndex);
                currentIndex = maxInd;
            }
        }
    }

    getLastIndex(): number {
        return this.stack.length - 1;
    }

    getParentIndex(i: number): number {
        return Math.floor((i - 1) / 2);
    }

    getLeftIndex(i: number): number {
        return 2 * i + 1;
    }
    getRightIndex(i: number): number {
        return 2 * i + 2;
    }

    swap(index1: number, index2: number) {
        let temp = this.stack[index1];
        this.stack[index1] = this.stack[index2];
        this.stack[index2] = temp;
    }
    peak(): number {
        return this.stack[0];
    }
    print() {
        return [...this.stack];
    }
}


let a = new MaxStack();
a.push(4)
a.push(14)
a.push(8)
a.push(16)
a.push(24)
a.push(9)
a.push(11)
a.push(15)
a.push(34)
a.push(26)
console.log(a.print());

a.pop();
console.log(a.print());

function greet(greeting, punctuation) {
    console.log(`${greeting}, ${this.name}${punctuation}`);
}

const person = { name: "Yun" };

greet.call(person, "Hello", "!");

greet.apply(person, ["Hi", "😊"]); // the same with apply function, but the parameter need to transfer as array

const sayHi = greet.bind(person, "Hey"); // bind will return with a new function which bind with this
sayHi("!!!");

//here is how call works
Function.prototype.call = function(thisArg, ...args) {
  // 1. 将函数作为 thisArg 的属性临时挂载
  const fn = Symbol(); 
  thisArg = thisArg ?? globalThis; // 若传入 null/undefined，则绑定到全局对象
  thisArg[fn] = this; // this 指向当前函数本身

  // 2. 执行函数
  const result = thisArg[fn](...args);

  // 3. 删除临时属性
  delete thisArg[fn];

  // 4. 返回结果
  return result;
}


//here is how apply works
Function.prototype.apply = function(thisArg, argsArray) {
  const fn = Symbol();
  thisArg = thisArg ?? globalThis;
  thisArg[fn] = this;
  
  const result = thisArg[fn](...(argsArray || []));
  
  delete thisArg[fn];
  return result;
}

//here is how bind works
Function.prototype.bind = function(thisArg, ...boundArgs) {
  const targetFn = this; // 原函数
  return function boundFunction(...args) {
    // 当 boundFunction 被调用时，再执行目标函数
    return targetFn.apply(thisArg, [...boundArgs, ...args]);
  }
}

type State = "pending" | "fulfilled" | "rejected";
class PromiseI {
    private state: State;
    private fnList: Function[];
    private val: any;
    constructor(executer: (acc, rej) => void) {
        this.state = "pending";
        this.fnList = [];
        executer(this.resolve.bind(this), this.reject.bind(this))
    }

    resolve(val: string) {
        if (this.state == "pending") {
            this.val = val;
            this.state = "fulfilled";
            console.log("this is resolve:", val);
            if (this.fnList.length > 0) {
                for (const fn of this.fnList) {
                    queueMicrotask(() => fn());
                }
            }
        } else {
            console.error("can't update the state");
        }
    }

    reject(val: string) {
        if (this.state == "pending") {
            this.state = "rejected";
            this.val = val;
            console.log("this is reject:", val);
            if (this.fnList.length > 0) {
                for (const fn of this.fnList) {
                    queueMicrotask(() => fn());
                }
            }
        } else {
            console.error("can't update the state");
        }
    }

    then(onFulfilled: Function, onRejected?: Function) {
        return new PromiseI((resolve, reject) => {
            const run = () => {
                queueMicrotask(() => {
                    if (this.state == 'fulfilled') {
                        try {
                            const x = onFulfilled(this.val);
                            resolve(x);
                        }
                        catch (e) {
                            reject(e);
                        }
                    }
                    else if (this.state == 'rejected' && onRejected) {
                        try {
                            const x = onRejected(this.val);
                            resolve(x);
                        } catch (e) {
                            reject(e)
                        }
                    }
                })
            }
            if (this.state == "pending") {
                this.fnList.push(run);
            } else {
                run();
            }
        });
    }

    // static resolve(fn: Function): {

    // }

    static all(fnList: PromiseI[]) {
        return new PromiseI((resolve, reject) => {
            let resultList: any = [];
            fnList.forEach((fn, i) => {
                fn.then(//使用异步来获取
                    (val) => {
                        if (val) {
                            resultList[i] = val;
                        }
                        if (resultList.length == fnList.length) {//根据长度判断
                            resolve(resultList);
                        }
                    },
                    (err) => {
                        reject(err);
                    })
            })

        })
    }
    static race(promisList: PromiseI[]) {
        let flag = false;
        return new PromiseI(
            (resolve, reject) => {
                for (const pro of promisList) {
                    pro.then(
                        (val) => {
                            if (flag) return; //注意promise本身的逻辑，需要在任何一个promise settle的时候立刻返回，所以需要用标志位控制
                            resolve(val);
                            flag = true;
                        }, err => {
                            reject(err);
                        }
                    )
                }
            }

        )
    }

}
//test case

// let promise = new PromiseI((resolve, reject) => {
//     resolve("success");
// });
// promise.then((res) => {
//     console.log("then", res);
//     return "yes"
// });
// promise.then((res) => {
//     console.log("then", res);
//     return "lala"
// });
// setTimeout(() => console.log("timeout 0"), 0);

PromiseI.race([
    new PromiseI((resolve) => setTimeout(() => { resolve(111) }, 1000)),
    new PromiseI((resolve) => resolve(222))
]
).then(
    (arg) => { console.log("success", arg) },
    erro => console.log("failed")
)

type State = "pending" | "fulfilled" | "rejected";
class PromiseI {
    private state: State;
    private fnList: Function[];
    private val: any;
    constructor(executer: (acc, rej) => void) {
        this.state = "pending";
        this.fnList = [];
        executer(this.resolve.bind(this), this.reject.bind(this))
    }

    resolve(val: string) {
        if (this.state == "pending") {
            this.val = val;
            this.state = "fulfilled";
            console.log("this is resolve:", val);
            if (this.fnList.length > 0) {
                for (const fn of this.fnList) {
                    queueMicrotask(() => fn());
                }
            }
        } else {
            console.error("can't update the state");
        }
    }

    reject(val: string) {
        if (this.state == "pending") {
            this.state = "rejected";
            this.val = val;
            console.log("this is reject:", val);
            if (this.fnList.length > 0) {
                for (const fn of this.fnList) {
                    queueMicrotask(() => fn());
                }
            }
        } else {
            console.error("can't update the state");
        }
    }

    then(onFulfilled: Function, onRejected?: Function) {
        return new PromiseI((resolve, reject) => {
            const run = () => {
                queueMicrotask(() => {
                    if (this.state == 'fulfilled') {
                        try {
                            const x = onFulfilled(this.val);
                            resolve(x);
                        }
                        catch (e) {
                            reject(e);
                        }
                    }
                    else if (this.state == 'rejected' && onRejected) {
                        try {
                            const x = onRejected(this.val);
                            resolve(x);
                        } catch (e) {
                            reject(e)
                        }
                    }
                })
            }
            if (this.state == "pending") {
                this.fnList.push(run);
            } else {
                run();
            }
        });
    }
}

//test case
let promise = new PromiseI((resolve, reject) => {
    resolve("success");
});
promise.then((res) => {
    console.log("then", res);
    return "yes"
});
promise.then((res) => {
    console.log("then", res);
    return "lala"
});

type State = "pending" | "fulfilled" | "rejected";
class PromiseI {
    private state: State;
    private fnList: Map<string, Function>;
    constructor(executer: (acc, rej) => void) {
        executer(this.resolve.bind(this), this.reject.bind(this))
    }

    resolve(val: string) {
        this.state = "fulfilled";
        console.log("this is resolve:",val);
    }

    reject(val: string) {
        this.state = "rejected";
        console.log("this is reject:",val);
    }

    then(fn:Function) {
        fn();
    }
}
let p = new PromiseI(
    (resolve,reject)=>{
        resolve("test");
    }
)

p.then(()=>{
    console.log("here is callback then")
})

class Subscriber {
    private bus: Bus;
    constructor(bus: Bus) {
        this.bus = bus;
    }
    subscribe(event: string, fn: Function) {
        this.bus.subscribe(event, fn);
    }
}

class Publisher {
    private bus: Bus;
    constructor(bus: Bus) {
        this.bus = bus;
    }
    publish(event: string, info: string) {
        this.bus.publish(event, info, info)
    }
}

class Bus {
    private channels: Map<string, Function[]>
    constructor() {
        this.channels = new Map();
    }
    publish(event: string, ...args: any[]) {
        const channel = this.channels.get(event);
        if (!channel) this.channels.set(event, []);
        else {
            channel.forEach(
                fn => fn.apply(this, args)
            );
        }
    }
    subscribe(event: string, fn: Function) {
        const channel = this.channels.get(event);
        if (!channel) this.channels.set(event, [fn]);
        else {
            channel.push(fn);
        }
    }
}

let bus = new Bus();
let pub1 = new Publisher(bus);
let subscribe1 = new Subscriber(bus);
let pub2 = new Publisher(bus);
let subscribe2 = new Subscriber(bus);
let subscribe3 = new Subscriber(bus);
pub1.publish("hit", "hithit")
pub2.publish("touch", "touchtouch")

subscribe1.subscribe("hit", (...info) => console.log('this is subscribe1 got info: ', info));
subscribe2.subscribe('touch', (...info) => console.log('this is subscribe2 got info: ', info));

subscribe3.subscribe("hit", (...info) => console.log('this is subscribe3 got info: ', info));
subscribe3.subscribe('touch', (...info) => console.log('this is subscribe3 got info: ', info));

pub1.publish("hit", "hithit2")
pub2.publish("touch", "touchtouch2")

class SubscriberV2 {
    private bus: BusV2;
    constructor(bus: BusV2) {
        this.bus = bus;
    }
    subscribe(event: string, fn: Function) {
        this.bus.subscribe(event, fn);
    }
}

class PublisherV2 {
    private bus: BusV2;
    constructor(bus: BusV2) {
        this.bus = bus;
    }
    publish(event: string, info: string) {
        this.bus.publish(event, info)
    }
}

class BusV2 {
    private channels: Map<string, Function[]>
    private stores: Map<string, string[]> // create a new store to store the value for Behavior/Replay
    constructor() {
        this.channels = new Map();
        this.stores = new Map();
    }
    publish(event: string, ...args: any[]) {
        const channel = this.channels.get(event);
        if (!channel) this.channels.set(event, []);
        else {
            channel.forEach(
                fn => fn.apply(this, args)
            );
        }
        const store = this.stores.get(event);// Check whethere we need already created
        if (!store) this.stores.set(event, [...args]);
        else {
            store.push(...args);
        }
    }
    subscribe(event: string, fn: Function) {
        const channel = this.channels.get(event);
        if (!channel) this.channels.set(event, [fn]);
        else {
            channel.push(fn);
        }
        const store = this.stores.get(event);// check whether need to replay
        if (store) {
            store.forEach(
                (info) => {
                    fn(info);
                }
            )
        }
    }
}

console.log("*".repeat(40));
let busv2 = new BusV2();
let pubV2 = new PublisherV2(busv2);
pubV2.publish("click", 'hi 1');
pubV2.publish("click", 'hi 2');
let subV2 = new SubscriberV2(busv2);
subV2.subscribe("click",(info)=>{console.log("received click info and say: ", info)});