JavaScript -- 算法

class PrimitiveNumber {
  static [Symbol.hasInstance](num){
    return typeof num === 'number'
  }
}

console.log(11 instanceof PrimitiveNumber) // true
console.log(NaN instanceof PrimitiveNumber) // true
console.log('' instanceof PrimitiveNumber) // **  false  **

class ComplexArray{
  static [Symbol.hasInstance](obj) {
    return Object.prototype.toString.call(obj) === '[object Array]'
  }
}

console.log([] instanceof ComplexArray) // true

function customInstanceOf(leftObj, rightType){
  if (!leftObj || typeof leftObj !== 'object' || !rightType || typeof rightType !== 'function') return false;
  let proto = Object.getPrototypeOf(leftObj);
  while(true) {
    if (proto == null) return false;
    if (proto === rightType.prototype) return true;
    proto = Object.getPrototypeOf(proto);
  }
}

function isTargetType(targetType, data){
  if (typeof targetType !== 'string') throw new Error('targetType 必须为字符串')
  
  return Object.prototype.toString.call(data) === '[object '+targetType+']'
}

console.log(isTargetType("Array", [])); // true
console.log(isTargetType('Number', NaN)); // true
console.log(isTargetType('Date', new Date())); // true
console.log(isTargetType('RegExp', /ss/)); // true
console.log(isTargetType('Function', function(){})); // true
console.log(isTargetType('Object', {})); // true
console.log(isTargetType('Object', '111')); // ** false **

const isType = targetType => data => Object.prototype.toString.call(data) === '[object '+targetType+']'

const isArray = isType('Array')
const isRegExp = isType('RegExp')
const isObject = isType('Object')

console.log(isArray([])) // true
console.log(isRegExp(/aaa/)) // true
console.log(isObject({})) // true
console.log(isObject(null)) // ** false **

Array.prototype.map = function(fn, context){
  const arr = [].slice.call(this);
  const mapArr = [];
  for(let i = 0; i < arr.length; i++){
    if (!arr.hasOwnProperty(i)) continue;
    mapArr[i] = fn.call(context, arr[i], i, this);
  }
  
  return mapArr;
}

var arrSrc = [1,2,3];
arrSrc[4] = 5; // 稀疏数组
var res = arrSrc.map(function (x){return x*x;});
console.log(res, arrSrc) // 原数组不变，产生新的数组

Array.prototype.forEach = function(fn, context){
  const arr = [].slice.call(this);
  for (let i=0; i < arr.length; i++){
    if (!arr.hasOwnProperty(i)) continue;
    fn.call(context, arr[i], i, this);
  }
}

Array.prototype.filter = function(fn,context){
  let arr = [].slice.call(this);
  
  let filterArr = [];
  for(let i=0, len=arr.length; i < len; i++){
    if (fn.call(context, arr[i], i, this)){
      filterArr.push(arr[i])
    }
  }
  
  return filterArr;
}

1. 方法一 （推荐：全部平铺开）
Array.prototype.flatExt = function(){
  let arr = [].slice.call(this);
  let distArr = [];
  let currVal;
  while(arr.length){
    currVal = arr.shift();
    if (Array.isArray(currVal) && arr.unshift(...currVal)) continue;
    
    distArr.push(currVal);
  }
  return distArr
}

var arrSrc = [ 20, 4, 21, [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
arrSrc.flatExt();

2. 方法二（针对纯数字）
var arrSrc = [ 20, 4, 21, [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];

// 纯数字时
Array.prototype.flatExt = function() { 
  let arr = [].slice.call(this)
  return arr.toString().split(',').map(Number);
}

console.log(arrSrc.flatExt())

// 数组平铺：提供平铺深度. depth 平铺深度 
Array.prototype.flatExt = function(depth=0){
  if (depth === 0) return this;
  
  let arr = [].slice.call(this);
  return arr.reduce((acc, curr, i, thisArr) => {
    if (Array.isArray(curr)) {
      return [...acc, ...([].flatExt.call(curr, depth-1))]
    } else {
      return [...acc, curr]
    }
  }, [])
}

Array.prototype.every = function(fn, context){
  const arr = [].slice.call(this);
  const len = arr.length;
  let isEvery = true;
  for(let i =0; i<len; i++){
    if (!fn.call(context, arr[i], i, this)){
      isEvery = false;
      break;
    }
  }
  
  return isEvery;
}

Object.is = function(x, y){
  if (x === y){
    return x !== 0 || y !== 0 || 1/x === 1/y;  // 排除 +0 === -0 为 true 问题
  } else {
    return x !== x && y !== y; // 解决 NaN === NaN 为 false 问题
  }
}

Object.create = function(proto, propertiesObject){
  // prototype 或 __proto__ 必须为 object 或 function
  if (typeof proto !== 'object' && typeof proto !== 'function') 
    throw new TypeError('类型不合理');
  
  function F() {}
  F.prototype = proto; // 初始化新对象的 prototype 
  
  let obj = new F();
  proto === null && (obj.__proto__ = proto); // 避免 null，初始化异常
    
  Object.defineProperties(obj, propertiesObject); // 绑定 对象属性
  
  return obj; // 返回新的 obj
}

Function.prototype.call = function(context, ...args){
  if (context === null || typeof context !== 'object') return this(...args);
  
  const fnCaller = Symbol('caller') // 防止直接设置属性时，覆盖context 上的对应属性
  context[fnCaller] = this; // 执行方法做为context的属性方法，确保方法的执行上下文是 context
 
  let res = context[fnCaller](...args); // this 切换到 context
  
  delete context[fnCaller]; // 移除 context 新增属性，避免内存泄漏
  
  return res;
}

//示例：
function fn(age,sex) {
  return `name = ${this.name}, age = ${age}`;
}

console.log(fn.call({name:'重新指定的name'}, '18', '男'))

Function.prototype.apply = function(context, args){
  if (context === null || typeof context !== 'object') return this(args);
  
  const fnCaller = Symbol('caller')
  context[fnCaller] = this;
  
  let res = context[fnCaller](args);
  
  delete context[fnCaller];
  
  return res;
}

示例：
function fn(args) {
  return `name = ${this.name}, age = ${args[0]}`;
}

console.log(fn.apply({name:'重新指定的name'}, ['18', '男']))

Function.prototype.bind = function(context, ...args) {
  return () => {
    return this.call(context, ...args);
  }
}

function fn(age){
  return `name = ${this.name}, age = ${age}`;
}

let fnRes = fn.bind({name:'重新指定的name'}, '18')
console.log(fnRes())

// ********* 父类 Animal **********
function Animal(name){
  this.name = name;
  this.getName = function(){ // 私用方法
    return 'name = ' + this.name;
  }
}

// 公共方法
Animal.prototype.getCurrentName = function(){ 
  return 'Animal prototype 方法 : ' + this.name;
}

// 静态方法
Animal.AnimalStaticFn = function(){
  return 'Animal static 方法 : StaticName()';
}

// ********* 子类 Cat 继承 Animal **********
function Cat(name, color){
  Animal.call(this, name); // 继承属性
  this.color = color;
  this.getColor = function(){
    return 'color = ' + this.color;
  }
}

Cat.prototype = Object.create(Animal.prototype); // 继承原型方法
Cat.prototype.constructor = Cat; // 重置子类构造函数

// 公共方法
Cat.prototype.getCurrentColor = function(){
  return 'Cat prototype 方法 : ' + this.color;
}

// 静态方法
Cat.CatStaticFn = function(){
  return 'Dog static 方法 StaticColor()';
}


const catObj = new Cat('Mini_Cat', 'red');
console.log(catObj.__proto__ === Cat.prototype) //true
console.log(catObj.__proto__.__proto__ === Animal.prototype) //true
console.log(Cat.prototype) // 
console.log(catObj.getCurrentName())
console.log(catObj.getCurrentColor())
console.log(catObj.getColor())
console.log(catObj.getName())
console.log(Cat.CatStaticFn())

function newFn(constructorFn, ...args){
  if (constructorFn === null || typeof constructorFn !== 'function') return null;
  
  let newObj = Object.create(constructorFn.prototype); // 指定新的对象 __proto__ 指向构造函数原型
  let res = constructorFn.call(newObj, ...args); // constructorFn 执行上下文替换为 newObj
  
  return res;
}

let primitiveObj = newFn(Number, '11') // 简单类型
console.log(primitiveObj)
 
let complexObj = newFn(Object, '11') // 引用类型
console.log(complexObj)

// Promise 状态枚举化
const STATUS_TYPE = {
  PENDING:Symbol('pending'), 
  FULFILLED:Symbol('fulfilled'),
  REJECTED:Symbol('rejected')
}

class PromiseExt{
  status = STATUS_TYPE.PENDING; //【状态】 pending：初始化  fulfilled：完成  rejected：拒绝
  value = undefined; // fulfilled 状态对应的值
  reason = undefined; // rejected 状态对应的原因
  onFulFilledCallbacks = []; // fulfilled 状态对应的所有onFulfilled函数
  onRejectedCallbacks = []; // rejected 状态对应的所有onRejected函数
  
  constructor(handler){
    try{
      handler(this.resolve, this.reject);
    }catch(e){
      this.reject(e)
    }
  }
  
  // 箭头函数，防止在 handler 中执行时，this 的指向异常
  resolve = (value) => {
    if (this.status === STATUS_TYPE.PENDING){
      this.status = STATUS_TYPE.FULFILLED;
      this.value = value;
      while(this.onFulFilledCallbacks.length){
        this.onFulFilledCallbacks.shift()(value)
      }
    }
  }

  reject = (value) => {
    if (this.status === STATUS_TYPE.PENDING){
      this.status = STATUS_TYPE.REJECTED;
      this.reason = value;
      while(this.onRejectedCallbacks.length){
        this.onRejectedCallbacks.shift()(value)
      }
    }
  }

  then(onFulfilled, onRejected) {
    const fnFulfilled = typeof onFulfilled === 'function' ? onFulfilled : value => value;
    const fnRejected = typeof onRejected === 'function' ? onRejected : reason => { throw reason; }
    
    const p2 = new PromiseExt((resolve, reject) =>{
      
      const microtaskFnFulfilled = () => {
        queueMicrotask(() => {
          try{
              let x = fnFulfilled(this.value);
              resolvePromise(p2, x, resolve, reject);
          } catch(e){
              reject(e)
          }
        })
      }
      
      const microtaskFnRejected = () => {
        queueMicrotask(() => {
          try{
              let x = fnRejected(this.reason);
              resolvePromise(p2, x, resolve, reject);
          } catch(e){
              reject(e)
          }
        })
      }
      
      if (this.status === STATUS_TYPE.FULFILLED){
        microtaskFnFulfilled()
      } else if (this.status === STATUS_TYPE.REJECTED) {
        microtaskFnRejected()
      } else {
        this.onFulFilledCallbacks.push(microtaskFnFulfilled);
        this.onRejectedCallbacks.push(microtaskFnRejected);
      }
    })
    
    return p2;
  }

  catch (onRejected){
    this.then(null, onRejected)
  }

  static resolve(value){
    if (value instanceof PromiseExt){
      return value
    } else {
      return new PromiseExt((resolve, reject) =>{ 
        resolve(value)
      })
    }
  }

  static reject(reason) {
    return new PromiseExt((resolve, reject) =>{ 
      reject(reason)
    })
  }
   
}

function resolvePromise(oldPromise, fnRes, resolve, reject){
  
  if (oldPromise === fnRes) { // 返回当前操作的 Promise 时，提示循环执行
    return reject(new TypeError('Chaining cycle detected for promise #<Promise>'))
  }
  
  if (fnRes instanceof PromiseExt){
    fnRes.then(resolve, reject);
  } else {
    resolve(fnRes)
  }
}


// 示例

let promiseExt = new PromiseExt((resolve, reject) =>{
  setTimeout(()=>{
    resolve('AAA');
  }, 1000)
})

promiseExt.then(value=>{
  console.log('延迟返回 value : ' + value)
  return new PromiseExt((resolve, reject)=>{
    resolve('BBB')
  })
}).then(value => {
  console.log('通过Promise 返回 value : ' + value)
  return 'CCC'
}).then(value => {
  console.log('直接返回 value : ' + value)
}).catch(reason=>{
  console.log('reject 03 : ' + reason)
})

function debounce(fn, delay=200){
  let timer;
  return function (...args) {
    if (timer) {
      clearTimeout(timer)
    }
    
    let thisSelf = this;
    timer = setTimeout(() => {
      fn.call(thisSelf, ...args)
    }, delay)
  }
}

function throttle(fn, delay=200){
  let timer;
  return function(...args) {
    if (!timer){
      let thisSelf = this;
      timer = setInterval(() => {
        fn.call(thisSelf, ...args);
        clearInterval(timer);
      }, delay);
    }
  }
}

// Progressive loading images
const imagesToLoad = document.querySelectorAll('img[data-src]');
const loadImages = (image) => {
  image.setAttribute('src', image.getAttribute('data-src'));
  image.onload = () => {
    image.removeAttribute('data-src');
  };
};
if ('IntersectionObserver' in window) {
  const observer = new IntersectionObserver((items) => {
    items.forEach((item) => {
      if (item.isIntersecting) {
        loadImages(item.target);
        observer.unobserve(item.target);
      }
    });
  });
  imagesToLoad.forEach((img) => {
    observer.observe(img);
  });
} else {
  imagesToLoad.forEach((img) => {
    loadImages(img);
  });
}

class EventBus {
  constructor(){
    this.eventCenter = {};
  }
  
  on(name, eventHandler) {
    (this.eventCenter[name] || (this.eventCenter[name] = [])).push(eventHandler);
  }
  
  off(name, eventHandler) {
    let handlers = this.eventCenter[name];
    if (!handlers || Object.prototype.toString.call(handlers) !== '[object Array]') return;
    handlers.indexOf(eventHandler) > -1 && handlers.splice(handlers.indexOf(eventHandler), 1)
  }
  
  once(name, eventHandler) {
    let thisSelf = this;
    let handler = function(){
      eventHandler.call(thisSelf, ...arguments)
      
      thisSelf.off(name, handler);
      // delete thisSelf.eventCenter[name];
    }
    
    thisSelf.on(name, handler)
  }
  
  emit(name, ...args){
    let thisSelf = this;
    let handlers = this.eventCenter[name];
    if (!handlers || Object.prototype.toString.call(handlers) !== '[object Array]') return;
    handlers.forEach(handler => {
      handler.call(thisSelf, ...args)
    })
  }
}

// 示例
let fn1 = function(p1, p2){
  console.log('***** fn1:'+ p1 + ' ' + p2)
}

let fn2 = function(p1){
  console.log('***** fn2:'+ p1 )
}

let fn3 = function(p1, p2, p3){
  console.log('***** fn3: ' + p1 + ' ' + p2 + ' ' + p3)
}

let fn4 = function(){
  console.log('***** fn4')
}
 
let fnOnce = function(p1, p2){
  console.log('***** fnOnce: ' + p1 + ' ' + p2)
}

let eventBus = new EventBus()

eventBus.on('click', fn1)
eventBus.on('click', fn2)
eventBus.on('click', fn3)
eventBus.on('input', fn4)
eventBus.once('clickOnce', fnOnce)

eventBus.emit('click', 'a', 'b', 'c', 'd')

console.log('************* 移除 click 事件的部分监听 ')
eventBus.off('click', fn2)
eventBus.emit('click')

console.log('************* 触发 clickOnce 事件 ')
eventBus.emit('clickOnce', 'A', 'F')
console.log(eventBus)

function curry(fn){
  if (fn.length === 1) return fn;
  
  function fnIteratorCurry(...args){
    if (fn.length === args.length){
      return fn(...args);
    } else {
      return (...nextargs) => {
        return fnIteratorCurry(...nextargs, ...args)
      }
    }
  }
  
  return fnIteratorCurry;
}

let add = curry((x, y, z) => x + y + z);

console.log(add(1)(2)(3));// 6
console.log(add(1)(2, 3)); // 6
console.log(add(1, 2)(3)); // 6
console.log(add(1, 2, 3)); // 6

function fibonacci(n){
  if (n <= 0) return ''
  if (n === 1 || n === 2) return 1
  return fibonacci(n-1) + fibonacci(n-2)
}

//示例：
console.time('fibo40')
let res = fibonacci(40)
console.log(res)         // 102334155
console.timeEnd('fibo40') // 820ms

结果：
// 大概执行时间：20->2.5ms 35->85ms; 40->820ms;

缺点：运行时间长，递归容易造成内存溢出

function fibo_cache(){
  let fnCache = {};
  const fibo_fnCache = function(n){
    if (!fnCache[n]) {
      if (n <= 0) fnCache[n] = '';
      if (n === 1 || n === 2) fnCache[n] = 1;
      else fnCache[n] = fibo_fnCache(n-1) + fibo_fnCache(n-2);
    }
    
    return fnCache[n];
  }
  
  return fibo_fnCache;
}

let fibonacci_cache = fibo_cache()


//示例：
console.time('fibo40')
let res = fibonacci_cache(40)
console.log(res)         // 102334155
console.timeEnd('fibo40') // 1ms

优缺点：利用缓存机制，缩短计算时间，增加内存占用

function fibo_dp(n){
  if (n <= 0) return '';
  let res = 1;
  if (n === 1 || n === 2) return res;
  let pre = 1;
  let curr = 1;
  n = n - 2;
  while(n){
    res = pre + curr;
    pre = curr;
    curr = res;
    n--;
  }
  return res;
}

// 示例：
console.time('fibo40')
let res = fibo_dp(40)
console.log(res)
console.timeEnd('fibo40') // < 1ms

优缺点：计算时间快，占用内存少

function simpleClone(source){
  return JSON.parse(JSON.stringify(source));
}

缺点：只能用于简单的数据拷贝。无法拷贝引用类型、特殊数据类型（函数，Symbol，regExpItem等）、循环引用等情况

function simpleClone(source){
  return Object.assign( source);
}

缺点：拷贝的是可枚举属性值，深层次的对象，只进行引用的拷贝

//  **目前未考虑循环引用，或多次引用单个对象的优化** 
var srcObj = {
  strItem: 'AA',
  numItem: 100,
  boolItem: false,
  objItem: {
    objA:'Obj11A',
    objB:'Obj22B',
    objC: {
      C1: 'objc1',
      C2: 'objc2'
    }
  },
  arrItem: [10, '100', {arrObjA:'arrObjA', arrObjB:'arrObjB'}],
  fnItem: function (paraA, optB){
    console.log('***** normal function *****')
  },
  fnItem1: ()=>{console.log('***** arrow function *****')},
  dateItem: new Date(2021, 1, 7),
  regExpItem: new RegExp('abc', 'i'),
  symbolItem: Symbol('symbolLabel')
}


function deepClone(source){
  if (typeof source !== 'object' || typeof source === null)
    return source;
  
  let target = Array.isArray(source) ? [] : {};
  let dataType = '';
  for(let key in source){
    if (!source.hasOwnProperty(key)) continue; // 过滤掉 __proto__ 上的属性
    
    dataType = Object.prototype.toString.call(source[key]);
    if (dataType === '[object Array]' || dataType === '[object Object]') {
      target[key] = deepClone(source[key])
    } else if (dataType === '[object Function]') {
      let fnString = source[key].toString();
      target[key] = source[key].prototype ? eval('(' + fnString + ')') : eval(fnString);
    } else if (dataType === '[object Date]') {
      target[key] = new Date(source[key]);
    } else if (dataType === '[object RegExp]') {
      target[key] = new RegExp(source[key].source, source[key].flags);
      target[key].lastIndex = source[key].lastIndex;
    } else if (dataType === '[object Symbol]'){
      target[key] = Symbol(source[key].description)
    } else {
      target[key] = source[key];
    }
  }
  
  return target;
}

方法一：
let arrSrc = [1, 3, 4, 1, null, undefined, 4, NaN, undefined, null, NaN, '3', true, false, true, 'true']

Array.prototype.distinct = function(){
  let arr = [].slice.call(this);
  let arrDist = []
  let isExistNaN = false;
  for(let i=0; i<arr.length; i++){
    if (arrDist.indexOf(arr[i]) === -1){
      if (Object.is(arr[i], NaN) && isExistNaN) // 避免 NaN 值再次重复
        continue;
      
      arrDist.push(arr[i])
      Object.is(arr[i], NaN) && (isExistNaN = true);
    }
  }
  
  return arrDist;
}

console.log(arrSrc.distinct());

var a = {
  value: 1,
  valueOf: function(){
    return this.value++;
  }
};

if(a == 1 && a == 2 && a == 3){
  console.log('利用 valueOf 完成目标');
}

var objArr = {1:222, 2:123, 5:888};
objArr.length = 7;

var mapArr = Array.from(objArr).map((value, idx, arr) =>{
  arr[idx] = ((idx !== arr.length -1) && arr[idx+1]) ? arr[idx+1] : null;
  return arr[idx]
})

console.log(mapArr) 

var nums = [1, 11, 7, 15, 6, 8], target = 9;

Array.prototype.findTargetSum = function (targetNum){
  let arr = [].slice.call(this);
  
  let firstVal, secondVal;
  while(arr.length){
    if(arr.length === 1) return [undefined, undefined]
    firstVal = arr.shift();
    secondVal = arr.indexOf(targetNum-firstVal)
    if(secondVal !== -1){
       secondVal = arr[secondVal];
       break;
    }
  }
  
  return [firstVal, secondVal];
}

console.log(nums.findTargetSum(target));

function reverseInt(value){
    if (value.toString().indexOf('-') === -1){
      value += '-'
    }
    if(value.charAt(0) === '-'){
      return value.substr(1);
    }
    
    let arr = value.split('-')
    arr[0] = arr[0].substring(1)
    arr[1] = value.charAt(0)+arr[1]
    return reverseInt(arr.join('-'))
 }