SHARE
TWEET

Untitled

a guest Jul 17th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const assert = require('assert')
  2.  
  3. function TreeNode(val) {
  4.   this.val = val
  5.   this.left = this.right = null
  6. }
  7.  
  8. function TreeLinkNode(val) {
  9.   this.val = val
  10.   this.left = this.right = this.next = null
  11. }
  12.  
  13. function ListNode(val) {
  14.   this.val = val
  15.   this.next = null
  16. }
  17.  
  18. function NestedInteger(xs) {
  19.   this.xs = xs
  20. }
  21.  
  22. function Interval(start, end) {
  23.   this.start = start
  24.   this.end = end
  25. }
  26.  
  27. NestedInteger.prototype.isInteger = function() {
  28.   return !Array.isArray(this.xs)
  29. }
  30.  
  31. NestedInteger.prototype.getInteger = function() {
  32.   return Array.isArray(this.xs) ? null : this.xs
  33. }
  34.  
  35. NestedInteger.prototype.getList = function() {
  36.   return Array.isArray(this.xs) ? this.xs.map(x => new NestedInteger(x)) : null
  37. }
  38.  
  39. function QNode(v) {
  40.   this.v = v
  41.   this.next = null
  42. }
  43.  
  44. const mkTree = xs => {
  45.   if (!Array.isArray(xs) || xs.length === 0)
  46.     return null
  47.  
  48.   let i = 0
  49.   const nextItem = () => {
  50.     if (i >= xs.length)
  51.       return null
  52.     const ret = xs[i]
  53.     ++i
  54.     return ret
  55.   }
  56.  
  57.   const root = new TreeNode(nextItem())
  58.   let qHead = new QNode(root)
  59.   let qTail = qHead
  60.   while (qHead) {
  61.     const cur = qHead.v
  62.     const itemL = nextItem()
  63.     if (itemL !== null) {
  64.       cur.left = new TreeNode(itemL)
  65.       qTail.next = new QNode(cur.left)
  66.       qTail = qTail.next
  67.     }
  68.     const itemR = nextItem()
  69.     if (itemR !== null) {
  70.       cur.right = new TreeNode(itemR)
  71.       qTail.next = new QNode(cur.right)
  72.       qTail = qTail.next
  73.     }
  74.     qHead = qHead.next
  75.   }
  76.   return root
  77. }
  78.  
  79. const treeToStr = t => {
  80.   if (t === null)
  81.     return "-"
  82.   return `(${treeToStr(t.left)}|${t.val}|${treeToStr(t.right)})`
  83. }
  84.  
  85. const printTree = t =>
  86.   console.log(treeToStr(t))
  87.  
  88. // TODO: check printTree(mkTree([3,0,4,null,2,null,null,1]))
  89.  
  90. const isTreeEqual = (t1, t2) => {
  91.   if (t1 === t2)
  92.     return true
  93.   if (t1 === null || t2 === null)
  94.     return false
  95.   // now we have t1 !== null and t2 !== null
  96.   return t1.val === t2.val &&
  97.     isTreeEqual(t1.left, t2.left) &&
  98.     isTreeEqual(t1.right, t2.right)
  99. }
  100.  
  101. const randomIntGenBetween = (min, max) => {
  102.   min = Math.ceil(min), max = Math.floor(max)
  103.   const range = max - min + 1
  104.   return () =>
  105.     Math.floor(Math.random() * range) + min
  106. }
  107.  
  108. /*
  109.    cTestFunc(<func>[, assertEqual = assert.deepStrictEqual])(...input)([expected value])
  110.    you can overwrite assertEqual if you want to customize the way results are compared.
  111.    note that your assertEqual MUST throw an error when the result is unexpected,
  112.    otherwise the result will be ignored
  113.    NOTE: old name is consoleTest, in order not to mess up auto completion of "console.xxxx",
  114.    I figure it's best not to use the same prefix
  115.  */
  116. const cTestFunc = (f, assertEqual = assert.deepStrictEqual) => (...inps) => expected => {
  117.   const timeTag = f.name
  118.   console.time(timeTag)
  119.   const actual = f.apply(null, inps)
  120.   console.timeEnd(timeTag)
  121.   if (typeof expected !== 'undefined') {
  122.     try {
  123.       assertEqual(actual, expected)
  124.     } catch (e) {
  125.       console.error(`[FAILED]`)
  126.       console.error('expected:')
  127.       console.error(expected)
  128.       console.error('actual:')
  129.       console.error(actual)
  130.       if (assertEqual !== assert.deepStrictEqual) {
  131.         console.error(`error:`)
  132.         console.error(e)
  133.       }
  134.     }
  135.   } else {
  136.     console.log(`Result:`)
  137.     console.log(actual)
  138.   }
  139. }
  140.  
  141. // compat
  142. const consoleTest = cTestFunc
  143.  
  144. /*
  145.    cTestImpl(<mkFunc>[, assertEqual = assert.deepStrictEqual])
  146.      (<Array of commands>, <Array of argument list>)
  147.      ([expected value])
  148.  */
  149. const cTestImpl =
  150.   (mkFunc, assertEqual = assert.deepStrictEqual) => (cmds, argLists) => expected => {
  151.   const fName = mkFunc.name
  152.   let obj = null
  153.   const ans = []
  154.  
  155.   console.time(fName)
  156.   for (let i = 0; i < cmds.length; ++i) {
  157.     const cmd = cmds[i]
  158.     if (cmd === fName) {
  159.       obj = new mkFunc(...argLists[i])
  160.       ans.push(null)
  161.     } else {
  162.       const ret = obj[cmd].apply(obj, [...argLists[i]])
  163.       ans.push(ret || null)
  164.     }
  165.   }
  166.   console.timeEnd(fName)
  167.   if (typeof expected !== 'undefined') {
  168.     try {
  169.       assertEqual(ans, expected)
  170.     } catch (e) {
  171.       console.error(`[FAILED]`)
  172.       console.error('expected:')
  173.       console.error(JSON.stringify(expected))
  174.       console.error('actual:')
  175.       console.error(JSON.stringify(ans))
  176.       if (assertEqual !== assert.deepStrictEqual) {
  177.         console.error(`error:`)
  178.         console.error(e)
  179.       }
  180.     }
  181.   } else {
  182.     console.log(`Result:`)
  183.     console.log(JSON.stringify(ans))
  184.   }
  185. }
  186.  
  187. const mkListNode = xs => {
  188.   const pre = {next: null}
  189.   let cur = pre
  190.   for (let i = 0; i < xs.length; ++i) {
  191.     cur.next = new ListNode(xs[i])
  192.     cur = cur.next
  193.   }
  194.   return pre.next
  195. }
  196.  
  197. const listNodeToArray = l => {
  198.   const ret = []
  199.   for (let cur = l; cur; cur = cur.next)
  200.     ret.push(cur.val)
  201.   return ret
  202. }
  203.  
  204. /*
  205.    shorthand for list generation instead of the super verbose randomIntGenBetween.
  206.    - random list of length ranged [1,20], with value being ranged [-10,20]:
  207.      genList({l: 1, r: 20}, {l: -10, r: 20})
  208.    - random list of fixed length 1000, with value being ranged [-10,20]:
  209.      genList(1000, {l: -10, r: 20})
  210.    - (not very) random list of length ranged [1,20], with every value being 10
  211.      genList({l: 1, r: 20}, 10)
  212.    - (not very) random list of fixed length 1000, with every value being 10
  213.      genList(1000, 10)
  214.  */
  215. const genList = (lenRange, valRange) => {
  216.   const gLen =
  217.     typeof lenRange === 'object' ?
  218.       randomIntGenBetween(lenRange.l, lenRange.r) :
  219.       (() => lenRange)
  220.   const g =
  221.     typeof valRange === 'object' ?
  222.       randomIntGenBetween(valRange.l, valRange.r) :
  223.       (() => valRange)
  224.   const sz = gLen()
  225.   const ret = new Array(sz)
  226.   for (let i = 0; i < sz; ++i)
  227.     ret[i] = g()
  228.   return ret
  229. }
  230.  
  231. /*
  232.    shorthand for generating a random integer instead using the super verbose randomIntGenBetween
  233.  */
  234. const genInt = (l, r) => randomIntGenBetween(l,r)()
  235.  
  236. module.exports = {
  237.   TreeNode,
  238.   TreeLinkNode,
  239.   NestedInteger,
  240.   Interval,
  241.   ListNode,
  242.   mkListNode,
  243.   listNodeToArray,
  244.  
  245.   mkTree,
  246.   treeToStr,
  247.   printTree,
  248.   isTreeEqual,
  249.  
  250.   randomIntGenBetween,
  251.  
  252.   consoleTest,
  253.   cTestFunc,
  254.   cTestImpl,
  255.  
  256.   genList,
  257.   genInt,
  258. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top