*项目地址:awesome-coding-javascript.
出发点
在日常开发中为了提高开发效率,我们一般是直接调用封装好的函数方法。但是作为工程师仅知道这些方法如何调用肯定是不够的,还需要了解这些方法背后的实现原理,以便之后更好地运用这些方法,并可以基于此改进或者写出自己觉得不错的方法。
这方面社区里也有很多关于原理介绍和代码实现的文章,可以从中学到很多。参照着文章里的描述,自己也可以实现这些方法,用 console.log
打印一下输出结果检查看有没有问题,但是这样写起来比较零碎分散不方便代码逻辑的持续改进。
例如:每次要验证代码逻辑的时候,都需要把代码拷到控制台或者一个文件里去运行;测试的数据需要临时构造或者也需要一个一个复制过去;测试用例都需要自己手动执行,不够自动化;正是由于测试不方便,所以写的测试用例也比较粗略;有代码修改时要保证逻辑正确,需要重新手动执行所以测试用例,繁琐重复;没有数据来评估代码质量。
持续构建的思路
如何解决?其实可以从开源的库和插件中找到答案,那就是为这些实现代码加上单元测试,并保证代码覆盖率。
加上单元测试后的优势有:
- 单元测试就是一个命令式的运行环境,即可以在开发时调试,也可以在开发完成后验证。
- 执行写好的单元测试用例,自动化地帮我们验证逻辑的正确性。
- 代码有改动,重新执行所有测试用例,保证改动的代码没有问题。
- 单元测试即文档,开发者可以从一个一个的单元测试中看到都实现了哪些功能,实现功能的描述,调用方式和调用的数据,最后调用的结果是什么。所以说单元测试也是一个很直观的用户文档。
- 体验 TDD 编程,先写好单元测试用例整理思路,然后实现满足这些测试用例的逻辑。
- 提交代码前全量跑一遍单元测试,保证所有逻辑没有问题之后才能提交。
保证代码覆盖率的意义有:
- 检测出程序中的无用代码,逆向反推在代码设计中思维未考虑到的点,提升代码质量。
- 分析未覆盖部分的代码,反推在前期单元测试设计是否充分,改进测试用例。
所以加上单元测试和保证代码覆盖率之后,能解决掉最开始提到的问题,让我们即方便又有保障地持续构建我们的源码库。接下来就是列出一些我们认为需要实现的源码库。
待构建源码列表
它包括 JavaScript 原生和常用方法的代码实现、常用库和插件的代码实现以及使用 JavaScript 实现的数据结构和常用算法。由于涉及的内容比较多,不可能短时间内全部集齐,这里先把大体的框架搭起来,之后再持续地构建自己的源码库。
- JavaScript 原生和常用方法的代码实现
- bind/apply/call 的实现
- new 的实现
- 深拷贝
- 防抖/节流的实现
- Promise 原理实现
- async/await 原理实现
- 柯里化
- 模板字符串
- 订阅发布机制
- URL 参数解析
- 常用的库和插件的代码实现
- Webpack 的模拟实现
- Webpack Plugin 的实现
- Babel 的模拟实现
- Babel Plugin 的实现
- React 的模拟实现
- Redux 的模拟实现
- Router 的模拟实现
- Egg.js 的模拟实现
- JavaScript 实现的数据结构和常用算法
- 数据结构
- 栈、队列、链表、集合
- 堆、散列表、数组、树
- 算法
- 排序、分治、递归
- 深度优先/广度优先、双指针
- 动态规划、回溯算法、贪心算法
- 其他
- 字符串
- 数字
- 数据结构
源码及单测展示(部分)
为了让大家有个直观的影响,这里贴出一些比较有代表性的代码实现和单元测试,供大家参考。完整的代码展示请见 Repo : awesome-coding-javascript。
call 的实现
实现代码:
export default function (...args) {
// 使用 Symbol 创建一个全局唯一的函数名
const func = Symbol('func');
let context = args.shift();
// 非严格模式下,传 null 或者 undeinfed,context 等于 window 对象
if (context == null) {
context = window;
}
else {
context = Object(context);
}
// 赋予函数属性
context[func] = this;
// 函数执行
const result = context[func](...args);
// 删除临时的函数属性
Reflect.deleteProperty(context, func);
return result;
}
单元测试用例:
import call from './call';
describe('Function.prototype.call', () => {
Function.prototype._call = call;
it('change the direction of this', () => {
const foo = {
value: 1,
};
function bar() {
return this.value;
}
// 和原生的 call 操作进行比较验证
expect(bar._call(foo)).toBe(bar.call(foo));
});
it('change the direction of this, use in constructor', () => {
function Product(name, price) {
this.name = name;
this.price = price;
}
function Food(name, price) {
Product.call(this, name, price);
this.category = 'food';
}
function Food2(name, price) {
Product._call(this, name, price);
this.category = 'food';
}
// 和原生的 call 操作进行比较验证
expect(new Food2('cheese', 5).name).toBe(new Food('cheese', 5).name);
});
it('when \'this\' argument is null or undefined', () => {
window.value = 2;
function bar() {
return this.value;
}
// 这是非严格模式下的结果,严格模式下会报错
expect(bar._call(null)).toBe(bar.call(null));
expect(bar._call(undefined)).toBe(bar.call(undefined));
});
it('when \'this\' is other primitive value', () => {
function bar() {
return this.length;
}
// 和原生的 call 操作进行比较验证
expect(bar._call('123')).toBe(bar.call('123'));
});
});
执行单元测试用例:
PASS src/javascript/call/call.test.js
Function.prototype.call
✓ change the direction of this (4ms)
✓ change the direction of this, use in constructor (1ms)
✓ when 'this' argument is null or undefined (1ms)
✓ when 'this' is other primitive value
bind 的实现
实现代码:
export default function (...bindArgs) {
// 函数自身
const self = this;
// 传进来的 this 对象
let context = bindArgs.shift();
// 非严格模式下,传 null 或者 undeinfed,context 等于 window 对象
if (context == null) {
context = window;
}
else {
context = Object(context);
}
// 返回的新函数
const fBound = function (...args) {
// 当返回的新函数作为构造函数使用时,之前指定的 this 对象会失效,此时 this 是指向实例对象
if (this instanceof fBound) {
context = this;
}
// 函数运行并返回结果
return self.apply(context, [...bindArgs, ...args]);
};
// 修改返回函数的原型对象,实例对象就可以从原函数的原型对象上继承属性和方法
fBound.prototype = Object.create(self.prototype);
return fBound;
}
单元测试用例:
import bind from './bind';
describe('Function.prototype.bind', () => {
Function.prototype._bind = bind;
it('change the direction of this, return a function', () => {
const foo = {
value: 1,
};
function bar(age1, age2) {
age1 = age1 || 0;
age2 = age2 || 0;
return this.value + age1 + age2;
}
const newBar = bar._bind(foo, 3);
expect(typeof newBar).toBe('function');
// 和原生 bind 操作进行比较验证
expect(newBar(2)).toBe((bar.bind(foo, 3))(2));
});
it('when return function as a constructor, \'this\' points to the instance object', () => {
const foo = { value: 1 };
function bar(name, age) {
this.name = name;
this.age = age;
}
bar.prototype.friend = 'kevin';
const bindFoo = bar.bind(foo); // 原生 bind 操作生成的实例对象
const bindFoo2 = bar._bind(foo);
bindFoo2.prototype.address = 1; // 修改返回函数的原型对象
// 验证返回的函数作为构造函数,实例对象会从原函数的原型对象上继承属性
expect(new bindFoo2().friend).toBe(new bindFoo().friend);
// 验证返回的函数作为构造函数,之前绑定的 this 对象会失效,this 会指向实例对象
expect(new bindFoo2().value).toBe(undefined);
expect(new bindFoo2().value).toBe(new bindFoo().value);
// 验证修改返回函数的原型对象,不会引起原始函数 bar 原型对象的修改
expect(bar.prototype.address).toBe(undefined);
});
it('when rebind \'this\', cannot change the direction of this', () => {
const foo = {
value: 1,
};
function bar(age1, age2) {
age1 = age1 || 0;
age2 = age2 || 0;
return this.value + age1 + age2;
}
const bindFoo = bar.bind(foo); // 原生 bind 操作生成的实例对象
const bindFoo2 = bar._bind(foo);
// 对返回的函数用 call 或者 apply 重新绑定 this 对象时,this 对象不会发生改变
expect(bindFoo2.call({ value: 2 })).toBe(1);
expect(bindFoo2.call({ value: 2 })).toBe(bindFoo.call({ value: 2 }));
});
it('when \'this\' argument is null or undefined', () => {
window.value = 2;
function bar(age1, age2) {
age1 = age1 || 0;
age2 = age2 || 0;
return this.value + age1 + age2;
}
// 这是非严格模式下的结果,严格模式下会报错
expect(bar._bind(null, 3)(1)).toBe(6);
expect(bar._bind(undefined, 3)(1)).toBe(6);
});
});
执行单元测试用例:
PASS src/javascript/bind/bind.test.js
Function.prototype.bind
✓ change the direction of this, return a function (3ms)
✓ when return function as a constructor, 'this' points to the instance object (1ms)
✓ when rebind 'this', cannot change the direction of this (1ms)
✓ when 'this' argument is null or undefined
new 的实现
实现代码:
import { isArrowFunction } from './../../shared/is';
export function objectFactory(Factory, ...args) {
if (typeof Factory !== 'function') {
throw new Error('need be a function argument');
}
if (isArrowFunction(Factory)) {
throw new Error('arrow function is not allowed');
}
const instance = Object.create(Factory.prototype); // 创建实例对象
const result = Factory.apply(instance, args); // 执行构造函数
return result instanceof Object ? result : instance;
}
单元测试用例:
import { objectFactory } from './new';
describe('new', () => {
it('take a function as an argument', () => {
const Factory = 123;
function excute() {
objectFactory(Factory);
}
expect(excute).toThrowError('need be a function argument');
});
it('cannot be an arrow function', () => {
const Factory = (name, age) => {
this.name = name;
this.age = age;
return 233;
};
function excute() {
objectFactory(Factory);
}
expect(excute).toThrowError('arrow function is not allowed');
});
it('create a instance', () => {
function Factory(name, age) {
this.name = name;
this.age = age;
}
Factory.prototype.getName = function () {
return this.name;
};
const f = objectFactory(Factory, 'jack', 12);
const nf = new Factory('jack', 12); // 原生的 new 操作生成的实例对象
expect(f.name).toBe(nf.name);
expect(f.age).toBe(nf.age);
expect(f.getName()).toBe(nf.getName());
});
it('if return a primitive value, return the newly instance', () => {
const Factory = function (name, age) {
this.name = name;
this.age = age;
return 233;
};
Factory.prototype.getName = function () {
return this.name;
};
const f = objectFactory(Factory, 'jack', 12);
const nf = new Factory('jack', 12); // 原生的 new 操作生成的实例对象
expect(f.name).toBe(nf.name);
expect(f.age).toBe(nf.age);
expect(f.getName()).toBe(nf.getName());
});
it('if return a object, return the object', () => {
const Factory = function (name, age) {
this.name = name;
this.age = age;
return {
name: 'john',
};
};
Factory.prototype.getName = function () {
return this.name;
};
const f = objectFactory(Factory, 'jack', 12);
const nf = new Factory('jack', 12); // 原生的 new 操作生成的实例对象
expect(f.name).toBe(nf.name);
expect(f.age).toBe(nf.age);
expect(f.getName).toBe(nf.getName);
});
});
执行单元测试用例:
PASS src/javascript/new/new.test.js
new
✓ take a function as an argument (5ms)
✓ cannot be an arrow function (1ms)
✓ create a instance (1ms)
✓ if return a primitive value, return the newly instance (1ms)
✓ if return a object, return the object (1ms)
Throttle 节流实现
实现代码:
export default function throttle(func, interval) {
let startTime = new Date();
return function (...args) {
const curTime = new Date();
// 大于间隔时才执行函数的逻辑
if (curTime - startTime > interval) {
// 重设开始时间
startTime = curTime;
// 执行函数
func.apply(this, args);
}
};
}
单元测试用例:
import throttle from './throttle';
import sleep from './../../shared/sleep';
describe('throttle', () => {
it('when less than interval, will throttle', async () => {
let count = 0;
const addCount = () => {
count += 1;
};
const timer = setInterval(throttle(addCount, 400), 200);
/**
* 400 -> 1
* 800 -> 2
*/
setTimeout(() => {
clearInterval(timer);
}, 1000);
await sleep(1500);
expect(count).toBe(2);
});
it('when greate than interval, normally call', async () => {
let count = 0;
const addCount = () => {
count += 1;
};
const timer = setInterval(throttle(addCount, 200), 300);
/**
* 300 -> 1
* 600 -> 2
* 900 -> 3
*/
setTimeout(() => {
clearInterval(timer);
}, 1000);
await sleep(1500);
expect(count).toBe(3);
});
});
执行单元测试用例:
PASS src/javascript/throttle/throttle.test.js
throttle
✓ when less than interval, will throttle (1506ms)
✓ when greate than interval, normally call (1505ms)
Promise 原理实现
实现代码:
export default class Promise {
constructor(fn) {
// 记录 promise 的状态,根据状态来操作 callbacks 队列
this.state = 'pending';
// 记录 resolve 或 reject 时的值
this.value = null;
// 里面维护了一个队列,是 resolve 时要执行的代码
this.callbacks = [];
fn(this.resolve, this.reject);
}
static resolve = val => {
return new Promise(function (resolve) {
resolve(val);
});
}
static reject = reason => {
return new Promise(function (resolve, reject) {
reject(reason);
});
}
static stop = () => {
return new Promise(function () {});
}
// 注册 onFulfilled 和 onRejected 函数
then = (onFulfilled, onRejected) => {
return new Promise((resolve, reject) => {
this.handle({
onFulfilled: onFulfilled || null,
onRejected: onRejected || null,
resolve,
reject,
});
});
}
catch = onRejected => {
return this.then(null, onRejected);
}
finally = onFinally => {
onFinally = typeof onFinally === 'function' ? onFinally : function noop() {};
return this.then(
val => Promise.resolve(onFinally()).then(() => val),
reason => Promise.resolve(onFinally()).then(() => {
throw reason;
})
);
}
// 更改状态,调用执行 callbacks 的方法
resolve = val => {
// 状态只能更改一次
if (this.state !== 'pending') {
return;
}
// resolve 的值是 Promise 的情况
if (val && (typeof val === 'function' || typeof val === 'object')) {
const then = val.then;
if (typeof then === 'function') {
then.call(val, this.resolve, this.reject);
return;
}
}
this.state = 'fulfilled';
this.value = val;
this.execute();
}
reject = reason => {
// 状态只能更改一次
if (this.state !== 'pending') {
return;
}
this.state = 'rejected';
this.value = reason;
this.execute();
}
// 执行 callbacks
execute = () => {
setTimeout(() => {
this.callbacks.forEach(callback => {
this.handle(callback);
});
}, 0);
}
// 负责处理单个 callback
handle = callback => {
if (this.state === 'pending') {
this.callbacks.push(callback);
return;
}
if (this.state === 'fulfilled') {
// 如果 then 中没有传递任何东西
if (!callback.onFulfilled) {
// 直接执行下一个 promise
callback.resolve(this.value);
return;
}
try {
// 执行当前的 promise
const ret = callback.onFulfilled(this.value);
// 执行下一个 promise
callback.resolve(ret);
}
catch (err) {
callback.reject(err);
}
return;
}
if (this.state === 'rejected') {
// 如果没有指定 callback.onRejected
if (!callback.onRejected) {
callback.reject(this.value);
return;
}
try {
const ret = callback.onRejected(this.value);
callback.resolve(ret);
}
catch (err) {
callback.reject(err);
}
return;
}
}
}
单元测试用例:
import Promise from './promise';
import sleep from './../../shared/sleep';
// ref: https://github.com/promises-aplus/promises-tests
describe('Promise', () => {
const time = 500;
it('take a function as an argument', () => {
expect(() => {
new Promise(1);
}).toThrowError('is not a function');
});
it('return a promise instace, exposes the public API', () => {
const promise = new Promise(function (resolve, reject) {
+new Date() % 2 === 0 ? resolve() : reject();
});
expect(promise).toHaveProperty('then');
expect(promise).toHaveProperty('catch');
expect(promise).toHaveProperty('finally');
});
it('promise.then, onFulfilled', done => {
const promise = new Promise(function (resolve) {
setTimeout(function () {
resolve(time);
}, time);
});
promise.then(ms => {
expect(ms).toBe(time);
done();
});
});
it('promise.then, onRejected', done => {
const promise = new Promise(function (resolve, reject) {
setTimeout(function () {
reject(time);
}, time);
});
promise.then(() => {
// onFulfilled
}, reason => {
// onRejected
expect(reason).toBe(time);
done();
});
});
it('promise.catch', done => {
const promise = new Promise(function (resolve, reject) {
setTimeout(function () {
reject(time);
}, time);
});
promise.then(() => {
// onFulfilled
}).catch(reason => {
expect(reason).toBe(time);
done();
});
});
it('promise.finally', done => {
const promise = new Promise(function (resolve, reject) {
setTimeout(function () {
reject(time);
}, time);
});
promise.then(() => {
// onFulfilled
}).catch(() => {
// onRejected
}).finally(() => {
// Finally
expect(true).toBe(true);
done();
});
});
it('promise chain call, onFulfilled', done => {
new Promise(function (resolve) {
setTimeout(function () {
resolve(time);
}, time);
}).then(ms => {
return new Promise(function (resolve) {
setTimeout(function () {
resolve(ms + time);
}, time);
});
}).then(total => {
expect(total).toBe(time * 2);
done();
});
});
it('promise chain call, onRejected', done => {
new Promise(function (resolve, reject) {
setTimeout(function () {
reject(time);
}, time);
}).then(ms => {
return new Promise(function (resolve) {
setTimeout(function () {
resolve(ms + time);
}, time);
});
}).then(total => {
return new Promise(function (resolve) {
setTimeout(function () {
resolve(total + time);
}, time);
});
}).catch(reason => {
expect(reason).toBe(time);
done();
});
});
it('can only change status once, cannot from fulfilled to rejected', async () => {
let result = '';
const promise = new Promise(function (resolve, reject) {
setTimeout(function () {
resolve(time);
setTimeout(function () { // 设定之后再 reject 一次
reject(time);
}, 0);
}, time);
});
promise.then(() => {
result += '=fulfilled=';
}).catch(() => {
result += '=rejected=';
});
await sleep(2000);
// 不等于 'fulfilled rejected'
expect(result).not.toBe('=fulfilled==rejected=');
// 等于 'fulfilled'
expect(result).toBe('=fulfilled=');
});
it('can only change status once, cannot from rejected to fulfilled', async () => {
let result = '';
const promise = new Promise(function (resolve, reject) {
setTimeout(function () {
reject(time);
setTimeout(function () { // 设定之后再 resolve 一次
resolve(time);
}, 0);
}, time);
});
promise.then(() => {
result += '=fulfilled=';
}).catch(() => {
result += '=rejected=';
});
await sleep(2000);
// 不等于 'fulfilled rejected'
expect(result).not.toBe('=rejected==fulfilled=');
// 等于 'rejected'
expect(result).toBe('=rejected=');
});
it('Promise.resolve', done => {
Promise.resolve(1).then(num => {
expect(num).toBe(1);
done();
});
});
it('Promise.reject', done => {
Promise.reject(1).catch(num => {
expect(num).toBe(1);
done();
});
});
});
执行单元测试用例:
PASS src/javascript/promise/promise.test.js (8.328s)
Promise
✓ take a function as an argument (13ms)
✓ return a promise instace, exposes the public API (2ms)
✓ promise.then, onFulfilled (507ms)
✓ promise.then, onRejected (505ms)
✓ promise.catch (506ms)
✓ promise.finally (509ms)
✓ chain call, onFulfilled (1007ms)
✓ chain call, onRejected (505ms)
✓ can only change status once, cannot from fulfilled to rejected (2002ms)
✓ can only change status once, cannot from rejected to fulfilled (2002ms)
✓ Promise.resolve
✓ Promise.reject (1ms)
async/await 原理实现
实现代码:
export function asyncGenerator(fn) {
return function () {
const gen = fn.apply(this, arguments);
return new Promise(function(resolve, reject) {
function step(result) {
try {
// 执行结束
if (result.done) {
return resolve(result.value);
}
// 继续往下执行
Promise.resolve(result.value)
.then(val => step(gen.next(val)))
.catch(err => reject(err));
}
catch(e) {
return reject(e);
}
}
// 递归地一步一步执行 gen.next()
step(gen.next());
});
};
}
单元测试用例:
import { asyncGenerator } from './async';
describe('async generator', () => {
it('auto excute generator', done => {
const asyncFunc = asyncGenerator(function*() {
const a = yield new Promise(resolve => {
setTimeout(() => {
resolve('a');
}, 1000);
});
const b = yield Promise.resolve('b');
const c = yield 'c';
const d = yield Promise.resolve('d');
return [a, b, c, d];
});
asyncFunc().then(res => {
expect(res).toEqual(['a', 'b', 'c', 'd']);
done();
});
});
it('auto excute generator, when get reject', done => {
const errorMsg = 'error';
const asyncFunc = asyncGenerator(function*() {
const s = yield 's';
yield Promise.reject(errorMsg);
return s;
});
asyncFunc()
.catch(res => {
expect(res).toBe(errorMsg);
done();
});
});
});
执行单元测试用例:
PASS src/javascript/async/async.test.js
async generator
✓ auto excute generator (1012ms)
订阅发布机制
实现代码:
export default class EventEmitter {
constructor() {
this.listeners = {};
}
on = (event, listener) => {
this.bindEvent(event, listener, false);
}
once = (event, listener) => {
this.bindEvent(event, listener, true);
}
emit = (event, ...args) => {
if (!this.hasBind(event)) {
console.warn(`this event: ${event} don't has bind listener.`);
return;
}
const { listeners, isOnce } = this.listeners[event];
listeners.forEach(listener => listener.call(this, ...args));
if (isOnce) {
this.off(event);
}
}
off = (event, listener) => {
if (!this.hasBind(event)) {
console.warn(`this event: ${event} don't exist.`);
return;
}
// remove all listener
if (!listener) {
delete this.listeners[event];
return;
}
// remove specific listener
const listeners = this.listeners[event].listeners;
listeners.forEach(listener => {
const index = listeners.indexOf(listener);
if (index !== -1) {
listeners.splice(index, 1);
}
});
}
hasBind = event => {
return this.listeners[event]
&& this.listeners[event].listeners
&& this.listeners[event].listeners.length;
}
bindEvent = (event, listener, isOnce = false) => {
if (!event || !listener) {
return;
}
this.listeners[event] = this.listeners[event] || {
isOnce: false,
listeners: []
};
this.listeners[event].isOnce = isOnce;
if (isOnce) {
this.listeners[event].listeners = [listener];
}
else {
this.listeners[event].listeners.push(listener);
}
}
}
单元测试用例:
import EventEmitter from './event-emitter';
describe('EventEmitter', () => {
let emitter;
beforeEach(() => {
emitter = new EventEmitter();
});
it('exposes the public API', () => {
expect(emitter).toHaveProperty('on');
expect(emitter).toHaveProperty('emit');
expect(emitter).toHaveProperty('once');
expect(emitter).toHaveProperty('off');
});
it('emitter.on', () => {
const foo = jest.fn();
const bar = jest.fn();
emitter.on('foo', foo);
expect(emitter.listeners['foo'].listeners).toEqual([foo]);
emitter.on('foo', bar);
expect(emitter.listeners['foo'].listeners).toEqual([foo, bar]);
});
it('emitter.once', () => {
const foo = jest.fn();
const bar = jest.fn();
emitter.once('foo', foo);
expect(emitter.listeners['foo'].listeners).toEqual([foo]);
emitter.once('foo', bar);
expect(emitter.listeners['foo'].listeners).toEqual([bar]);
});
it('emitter.emit', () => {
// emitter.on
const foo = jest.fn();
emitter.on('foo', foo);
emitter.emit('foo', 'x');
expect(foo).toHaveBeenNthCalledWith(1, 'x');
emitter.emit('foo', 'x');
expect(foo).toHaveBeenCalledTimes(2);
// emitter.once
const bar = jest.fn();
emitter.once('bar', bar);
emitter.emit('bar', 'x');
expect(bar).toHaveBeenNthCalledWith(1, 'x');
emitter.emit('bar', 'x');
expect(bar).toHaveBeenCalledTimes(1);
});
it('emitter.off, remove all listener', () => {
const foo = jest.fn();
emitter.on('foo', foo);
emitter.emit('foo', 'x');
emitter.off('foo');
emitter.emit('foo', 'x');
expect(foo).toHaveBeenCalledTimes(1);
});
it('emitter.off, remove specific listener', () => {
const foo = jest.fn();
const bar = jest.fn();
emitter.on('foo', foo);
emitter.on('foo', bar);
emitter.emit('foo', 'x');
expect(foo).toHaveBeenCalledTimes(1);
expect(bar).toHaveBeenCalledTimes(1);
emitter.off('foo', foo);
emitter.emit('foo', 'x');
expect(foo).toHaveBeenCalledTimes(1);
expect(bar).toHaveBeenCalledTimes(2);
});
});
执行单元测试用例:
PASS src/javascript/event-emitter/event-emitter.test.js
EventEmitter
✓ exposes the public API (4ms)
✓ emitter.on (2ms)
✓ emitter.once (1ms)
✓ emitter.emit (14ms)
✓ emitter.off, remove all listener (2ms)
✓ emitter.off, remove specific listener (1ms)
数据结构:堆
实现代码:
/**
* 堆(Heap)是计算机科学中的一种特别的树状数据结构,若是满足一下特性,即可成为堆:给定堆中任意节点 P 和 C,
* 若 P 是 C 的母节点,那么 P 的值会小于等于(或大于等于)C 的值。若母节点的值恒小于等于子节点的值,此堆成为最小堆。
* 若母节点恒小于等于子节点的值,此堆成为最小堆(min heap)
* 若母节点恒大于等于子节点的值,此堆成为堆大堆(max heap)
* 在堆中最顶端的那一个节点,称作根节点(root node),根节点本身没有母节点(parent node)
*
* 在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些事件较短的任务将等待很长事件才能结束。
* 或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
* 也就是优先队列:一种特殊的队列,队列中元素出栈的顺序是按照元素的优先权大小,而不是元素入队的先后顺序。
*
* 堆的特性:
* - 堆是一棵完全二叉树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
* - 任意节点小于(或大于)它的所有子节点。
* - 可以用数组来存储二叉堆。
*/
/**
* 实现堆(最大堆、最小堆)
*/
export default class Heap {
constructor(type, nums) {
this.type = type || 'max'; // 默认为最大堆
this.items = [];
if (Array.isArray(nums) && nums.length) {
nums.forEach(n => this.add(n));
}
}
isMaxHeap = () => {
return this.type === 'max';
}
isMinHeap = () => {
return this.type === 'min';
}
size = () => {
return this.items.length;
}
getParentIndex = i => {
return Math.floor((i - 1) / 2);
}
getLeftChildIndex = i => {
return i * 2 + 1;
}
getRightChildIndex = i => {
return i * 2 + 2;
}
swap = (i, j) => {
const temp = this.items[i];
this.items[i] = this.items[j];
this.items[j] = temp;
}
// 向堆底插入元素
add = el => {
this.items.push(el);
this.siftUP(this.size() - 1);
}
siftUP = index => {
// 递归终止条件
if (index <= 0) {
return;
}
// 找到父元素的索引和值
const item = this.items[index];
const parentIndex = this.getParentIndex(index);
const parent = this.items[parentIndex];
// 如果是最大堆
if (this.isMaxHeap()) {
// 如果母节点的值小于子节点,则该节点需要上浮,即需要交换位置
if (item > parent) {
this.swap(index, parentIndex);
// 再递归对 parent 做上浮操作
this.siftUP(parentIndex);
}
}
else if (this.isMinHeap()) {
// 如果母节点的值大于子节点,则该节点需要上浮,即需要交换位置
if (item < parent) {
this.swap(index, parentIndex);
// 再递归对 parent 做上浮操作
this.siftUP(parentIndex);
}
}
}
// 取出栈顶元素,并重新构建完全二叉树
extract = () => {
// 获取堆顶元素
const item = this.items.shift();
// 如果当前堆的元素个数小于 2 时,可以直接返回,不需要重新构建完全二叉树
if (this.size() < 2) {
return item;
}
// 现在分离成了两个完全二叉树,需要重新构建成一颗完全二叉树
// 获取最后一个元素,并把它放到堆顶
this.items.unshift(this.items.pop());
// 进行 siftDown 操作,重新构建一颗完全二叉树
this.siftDown(0);
// 返回堆顶元素
return item;
}
siftDown = index => {
const leftChildIndex = this.getLeftChildIndex(index);
// 当没有左子树(也就没有右子树)时,递归终止
if (leftChildIndex >= this.size()) {
return;
}
const leftChild = this.items[leftChildIndex];
const rightChildIndex = this.getRightChildIndex(index);
const rightChild = this.items[rightChildIndex];
let nextIndex = leftChildIndex;
if (this.isMaxHeap()) {
// 找到左右子树的最大值
if (typeof rightChild !== undefined && rightChild > leftChild) {
nextIndex = rightChildIndex;
}
}
else if (this.isMinHeap()) {
// 找到左右子树的最小值
if (typeof rightChild !== undefined && rightChild < leftChild) {
nextIndex = rightChildIndex;
}
}
const parent = this.items[index];
const next = this.items[nextIndex];
if (this.isMaxHeap()) {
// 如果左右子树的最大值大于母节点的值,则母节点需要下沉,即需要交换位置
if (next > parent) {
this.swap(index, nextIndex);
// 再递归对母节点进行下沉
this.siftDown(nextIndex);
}
}
else if (this.isMinHeap()) {
// 如果左右子树的最小值小于母节点的值,则母节点需要下沉,即需要交换位置
if (next < parent) {
this.swap(index, nextIndex);
// 再递归对母节点进行下沉
this.siftDown(nextIndex);
}
}
}
toString = connector => {
return this.items.join(connector);
}
}
单元测试用例:
import Heap from './heap';
describe('Heap', () => {
let heap;
beforeEach(() => {
heap = new Heap();
});
it('exposes the public API', () => {
expect(heap).toHaveProperty('add');
expect(heap).toHaveProperty('extract');
expect(heap).toHaveProperty('toString');
});
});
describe('Max Heap', () => {
let heap;
beforeEach(() => {
heap = new Heap();
});
it('maxHeap.add', () => {
// 乱序加入
heap.add(3);
heap.add(1);
heap.add(5);
heap.add(2);
heap.add(4);
heap.add(6);
expect(heap.toString()).toBe('6,4,5,1,2,3');
});
it('maxHeap.extract', () => {
// 乱序加入
heap.add(1);
heap.add(4);
heap.add(2);
heap.add(5);
heap.add(3);
heap.add(6);
expect(heap.extract()).toBe(6);
expect(heap.toString()).toBe('5,4,2,1,3');
});
});
describe('Min Heap', () => {
let heap;
beforeEach(() => {
heap = new Heap('min');
});
it('minHeap.add', () => {
// 乱序加入
heap.add(3);
heap.add(1);
heap.add(5);
heap.add(2);
heap.add(4);
heap.add(6);
expect(heap.toString()).toBe('1,2,5,3,4,6');
});
it('minHeap.extract', () => {
// 乱序加入
heap.add(1);
heap.add(4);
heap.add(2);
heap.add(5);
heap.add(3);
heap.add(6);
expect(heap.extract()).toBe(1);
expect(heap.toString()).toBe('2,3,6,5,4');
});
});
执行单元测试用例:
PASS src/dsa/heap/heap.test.js
Heap
✓ exposes the public API (4ms)
Max Heap
✓ maxHeap.add (1ms)
✓ maxHeap.extract (1ms)
Min Heap
✓ minHeap.add
✓ minHeap.extract (1ms)
算法:双指针
实现代码:
/**
* 输入一个链表,输出该链表中倒数第 k 个结点。
*/
export default function findKthToTail(head, k) {
if (!head || !k) {
return null;
}
// 双指针
let first = head;
let second = head;
let index = 1;
while (first.next) {
first = first.next;
// 当 first 和 second 相距 k 时,second 开始逐渐前进
if (index >= k) {
second = second.next;
}
index++;
}
// 循环结束后, k 如果大于 index 则说明倒数第 k 个节点不存在
if (k > index) {
return null;
}
return second;
}
单元测试用例:
import { LinkedList } from './../linked-list/linkedList';
import findKthToTail from './findKthToTail';
describe('find Kth to tail', () => {
it('when k is less or equal than linked list size', () => {
const sourceArr = [1, 2, 3, 4, 5];
const linkedList = LinkedList.from(sourceArr);
expect(findKthToTail(linkedList.head, 3).val).toEqual(3);
expect(findKthToTail(linkedList.head, 5).val).toEqual(1);
});
it('when k is greate than linked list size', () => {
const sourceArr = [1, 2, 3, 4, 5];
const linkedList = LinkedList.from(sourceArr);
expect(findKthToTail(linkedList.head, 6)).toEqual(null);
});
});
执行单元测试用例:
PASS src/dsa/doublePointer/findKthToTail.test.js
find Kth to tail
✓ when k is less or equal than linked list size (4ms)
✓ when k is greate than linked list size (9ms)
可以看出来,写单测并不复杂,测试框架的接口简单易用,写单测用例也比较容易。目前的代码覆盖率在 90% 以上。