Created
May 2, 2024 08:18
-
-
Save lovetingyuan/1c0676fb37c94373e0241f5fd15e2d79 to your computer and use it in GitHub Desktop.
SimpleJSPriorityArray
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 简单的顺序队列,只能添加和迭代,并且只能支持五位数以内,数组的长度最好不要超过四位数 | |
// 利用的是js的对象,如果key是正整数,那么在添加时可以保持大小顺序 | |
class SimpleJSPriorityArray { | |
constructor() { | |
this.valcountmap = {} | |
this.posmap = {} | |
this.negmap = {} | |
this.size = 0 | |
} | |
get length() { | |
return this.size | |
} | |
push(key, value = key) { | |
this.valcountmap[key] ??= 0 | |
const count = this.valcountmap[key]++ | |
if (key >= 0) { | |
const mapkey = '1' + key.toString().padStart(5, '0') + count.toString().padStart(4, '0') | |
this.posmap[mapkey] = value | |
} else { | |
const mapkey = '1' + (-key).toString().padStart(5, '0') + count.toString().padStart(4, '0') | |
this.negmap[mapkey] = value | |
} | |
this.size++ | |
} | |
[Symbol.iterator]() { | |
let poslist = null | |
const neglist = Object.values(this.negmap) | |
let posindex = 0 | |
let negindex = neglist.length - 1 | |
return { | |
next: () => { | |
if (negindex >= 0) { | |
return { | |
value: neglist[negindex--], | |
done: false, | |
} | |
} | |
if (!poslist) { | |
poslist = Object.values(this.posmap) | |
} | |
if (posindex < poslist.length) { | |
return { | |
value: poslist[posindex++], | |
done: false, | |
} | |
} | |
return { | |
value: undefined, | |
done: true, | |
} | |
}, | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment