{"_id":"@codescrum/bitmask-set-jsbi","name":"@codescrum/bitmask-set-jsbi","dist-tags":{"latest":"1.0.0"},"versions":{"1.0.0":{"name":"@codescrum/bitmask-set-jsbi","version":"1.0.0","type":"module","description":"Convert arrays to bitmask representations to quickly operate with them through bitwise operations.","main":"index.js","directories":{"lib":"lib","test":"test"},"dependencies":{"jsbi":"^3.1.1"},"devDependencies":{"eslint":"^8.23.0","eslint-config-standard":"^17.0.0","eslint-plugin-import":"^2.26.0","eslint-plugin-n":"^15.2.5","eslint-plugin-promise":"^6.0.1","lodash":"^4.17.21","mocha":"^10.0.0"},"scripts":{"test":"mocha"},"repository":{"type":"git","url":"git+https://github.com/codescrum/bitmask-set-jsbi-js.git"},"keywords":["array optimization","array intersection optimization","bitmask","bitwise","bitmask set","set intersect","set optimization","set intersection"],"author":{"name":"Miguel Diaz @ Codescrum Ltd"},"license":"MIT","homepage":"https://github.com/codescrum/bitmask-set-jsbi-js/","gitHead":"257b035805ae6c09dca43a92c1d88a8033b461c2","bugs":{"url":"https://github.com/codescrum/bitmask-set-jsbi-js/issues"},"_id":"@codescrum/bitmask-set-jsbi@1.0.0","_nodeVersion":"16.17.0","_npmVersion":"8.15.0","dist":{"integrity":"sha512-hCt/qN5ZCZZJ4oJo+xTcerrw8W3iXeRXxkQpKE1nNNOgYdnxvPQb40E58rBQgRPtfzv7KuR0ek6jwa9cnZP/dw==","shasum":"f9cec0e6884e29c33020151135def7557fe1d364","tarball":"https://registry.npmjs.org/@codescrum/bitmask-set-jsbi/-/bitmask-set-jsbi-1.0.0.tgz","fileCount":6,"unpackedSize":24520,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDSVWkUQHXEk+i9qDEVSKJfNEXCguUu4/A7tpfsxafOXgIgO60d2SwuRvpZrkElj1AUZkdxjdfdI+GGgoEZgJt8Arc="}],"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v4.10.10\r\nComment: https://openpgpjs.org\r\n\r\nwsFzBAEBCAAGBQJjFpbSACEJED1NWxICdlZqFiEECWMYAoorWMhJKdjhPU1b\r\nEgJ2Vmo1aw//bigHys2KUSgdOd7ZATplKcmH0okyTjmhDYsLxUlBqPnCdcyA\r\nvAMGcCGhzE1DkZ5Jz2Pg47Ho/7X+yLvqNjrJsQWOzm/7dLQesz0O4/oL1rK7\r\n0bUVkuMuVll2pUbYE+9RebM8UsuEfXm/BYpp0rdmxNYF7nct0/b6Y7vFtbBl\r\nYeqH0SS/kZI4vSDUduuyQdICAxECREeSLqIh+J8LWNFFkFMXacDkrHQOcAOB\r\ne+Tr274KbZkPgYYcJZd9/tZt23+e6Jh4a8YjdIzki3JUqWddXbn8xfix1tX0\r\nIo/aOjQdE64YDTruMilcfH13myyq4ZSfCH4j4DE1mLLEOgv+B+rIQ32L44UR\r\neQN28zQisoOWwDJR4ZEWrFU+/BAcGlHjWdUvD5COpay9IbnfJPwwI/++yciz\r\nTWe/EEbSnzIqotYrurs9jAVDgJaD3+TRxLOmWJcH9skz7S3cedFsD1tNbVxx\r\ntI25XoRmSMbEolj7J9aOMCe5VvRWVBKvyFKN3xZVxdq4owzS7BcsJLJchI7C\r\ntaO3Xc6hVnRwJzI0jnSVbdsscW+4jYAuAnXXS58VlEUPr18yUBzWhgnmq5+M\r\nf/jDBuS1Blk2nhtDvLC+GsA36igrgK6UR0IzZhYS1mM2XDe2KGV+8B6LT8so\r\nm0MDpb4ZRqLb/836OzUKuQxt9sXFY3cU3WA=\r\n=bDco\r\n-----END PGP SIGNATURE-----\r\n"},"_npmUser":{"name":"gato_omega","email":"mdiaz.npm+thor@codescrum.com"},"maintainers":[{"name":"gato_omega","email":"mdiaz.npm+thor@codescrum.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/bitmask-set-jsbi_1.0.0_1662424786669_0.11253146212801246"},"_hasShrinkwrap":false}},"time":{"created":"2022-09-06T00:39:46.615Z","1.0.0":"2022-09-06T00:39:46.848Z","modified":"2022-09-06T00:39:47.020Z"},"maintainers":[{"name":"gato_omega","email":"mdiaz.npm+thor@codescrum.com"}],"description":"Convert arrays to bitmask representations to quickly operate with them through bitwise operations.","homepage":"https://github.com/codescrum/bitmask-set-jsbi-js/","keywords":["array optimization","array intersection optimization","bitmask","bitwise","bitmask set","set intersect","set optimization","set intersection"],"repository":{"type":"git","url":"git+https://github.com/codescrum/bitmask-set-jsbi-js.git"},"author":{"name":"Miguel Diaz @ Codescrum Ltd"},"bugs":{"url":"https://github.com/codescrum/bitmask-set-jsbi-js/issues"},"license":"MIT","readme":"# Bitmask Set (JSBI)\n\n*Convert arrays to bitmask representations to quickly operate with them through bitwise operations.*\n\nIn general, this approach can be applied to whenever you want to:\n\n1. Quickly retrieve the intersection betwen two (or more) arrays of elements.\n2. Quickly add/remove elements of other arrays to/from a particular array.\n\n*Note:* The approach implemented here might work best if you need to operate\nwith many arrays/sets instead of just a couple.\n\n*Important:* This package depends on the JSBI — pure-JavaScript BigInts library for compatibility.\n\nSee https://github.com/GoogleChromeLabs/jsbi, https://www.npmjs.com/package/jsbi\nand https://v8.dev/features/bigint for information on this.\n\nYou can check the state of BigInt adoption here: https://caniuse.com/?search=bigint.\n\n## Usage\n\n```bash\nnpm install @codescrum/bitmask-set-jsbi\n```\n\n```javascript\nimport { BitmaskSet, Bitmask } from \"@codescrum/bitmask-set-jsbi\"\n\n// Given an array that you want to operate on\nlet myArray = [1,2,3,4,5,6,7,8,9]\n\n// We first define the `BitmaskSet` which we will work with.\nlet set = new BitmaskSet(myArray)\n\n// Then we define some bitmasks, representing different sets of elements\n// you pass either their elements, or a strings of 1's and 0's\n\nlet a = set.bitmask([1,3,5,7,9]) // let a = set.bitmask(\"101010101\")\nlet b = set.bitmask([2,4,6,8])   // let b = set.bitmask(\"010101010\")\nlet c = set.bitmask([1,3,5])     // let c = set.bitmask(\"101010000\")\nlet d = set.bitmask([6,8])       // let d = set.bitmask(\"000001010\")\nlet e = set.bitmask([1,2,3,4,5]) // let e = set.bitmask(\"111110000\")\nlet f = set.bitmask([6,7,8,9])   // let e = set.bitmask(\"000001111\")\nlet g = set.bitmask([1,9])       // let g = set.bitmask(\"100000001\")\n\n// For ease of visualization we defined the elements in order when\n// creating the bitmasks, but you can pass the elements in any order, even\n// if they include duplicates when creating the bitmasks.\n//\n// Note that you must use the `BitmaskSet` instance to create the\n// bitmasks based on it, or alternatively instantiate them as:\nlet bitmask = new Bitmask(set, [1,2,3]) // same as set.bitmask([1,3,5])\n\n// Print a bitmask's string representation\nconsole.log(\"bitmask: \" + bitmask) // bitmask: 111000000\n\n//// All the following methods return bitmasks\n\n// These methods are the most basic ones and can only take other\n// bitmasks as arguments\n\na.and(b)              // 000000000 bitwise and\na.or(b)               // 111111111 bitwise or\na.xor(e)              // 010100101 bitwise xor\na.invert()            // 010101010 (like bitwise not)\n\n// These methods can take both bitmasks and elements as arguments\n// Also, they always return a new bitmask (they don't mutate the bitmask\n// you call them on.\n//\n// Note that some are just the same with different names for\n// semantics convenience (expressiveness)\n\na.add([1,2,3,4,5])    // 111110101 you can add an array of elements\na.add(e)              // 111110101 you can add elements from another bitmask too\na.union(e)            // 000000101 same as add (added for convenience)\na.include(e)          // 111110101 same as add (added for convenience)\na.remove([1,2,3,4,5]) // 000000101 you can remove an array of elements\na.remove(e)           // 000000101 you can remove elements from another bitmask too\na.exclude(e)          // 000000101 same as remove (added for convenience)\na.distinct(e)         // 000000101 same as xor (added for convenience)\na.unlike(e)           // 000000101 same as xor (added for convenience)\na.different(e)        // 000000101 same as xor (added for convenience)\na.intersection(e)     // 101010000 return elements in common\na.intersect(e)        // 101010000 same as intersection (added for convenience)\n\na.is_in(b)            // true  - checks if all elements of a are in b.\na.is_not_in(b)        // false - a.is_not_in(b) == !a.is_in(b)\na.is_full()           // false - checks if all elements are present (i.e. \"111111111\")\na.is_empty()          // false - checks if no elements are present (i.e. \"000000000\")\na.is_zero()           // false - same as is_empty (i.e. \"000000000\")\n\n// All bitmask methods are `lazy` in the sense they don't compute any\n// elements while you perform operations on them.\n// As long as you are in \"bitmask space\" you manipulate everything through\n// bitwise operations.\n// Once you are ready to get your final items, just call `elements()`\n\na.invert().elements() // [2,4,6,8] (note: this result will be memoized)\n\n//// Some more examples\n\n// Compare to string representation\nconsole.log(\"a == '101010101': \", (a == '101010101'))       // true\n\n// Equality between bitmasks\nconsole.log(\"a.invert().equals(b): \", a.invert().equals(b)) // true\n\nconsole.log(`${a}.is_in(${b}): `, a.is_in(b)) // false\nconsole.log(`${a}.is_in(${c}): `, a.is_in(c)) // false\nconsole.log(`${c}.is_in(${a}): `, c.is_in(a)) // true\nconsole.log(`${d}.is_in(${f}): `, d.is_in(f)) // true\nconsole.log(`${g}.is_in(${a}): `, g.is_in(a)) // true\nconsole.log(`${g}.is_in(${b}): `, g.is_in(b)) // false\n\n// Note that you can chain methods since they keep returning\n// bitmasks, so a given selection of elements can be expressed\n// as follows:\n\nlet result = a             // Take all elements from `a`\n              .distinct(b) // mutually excluding those from `b`\n              .and(e)      // that are also in `e`\n              .add(f)      // then add the ones in `f`\n              .remove(g)   // then remove those in `g`\n              .invert()    // invert the current selection\n              \nconsole.log(\"result: \" + result)   // result: 100000001\n\n// After manipulations, compute final resulting elements.\n// Elements get computed when you first call `elements()`\n// in your resulting bitmask:\nconsole.debug(result.elements()) // [ 1, 9 ]\n```\n\nA few things to keep in mind:\n\n- The array of elements you pass in to create the `BitmaskSet` is assumed to be of unique values (no duplicates). This _may_ not be an issue, since the internal presentation will remove duplicate elements anyway.\n- The order of the elements you pass in to create the BitmaskSet or the bitmasks\n  is really not important. But the internal operations do rely on this order being preserved.\n- The array of elements cannot be empty, you must check this case before\n  attempting to create the `BitmaskSet`.\n\n## How does it work? What does it do?\n\nThe basic idea is very simple, it does the following:\n\n1. Given an array of unique values, say `[1,2,3,4,5]` we create bitmasks of the\n   same lenght as the numbers of elements (such as `10101`) to represent which\n   elements are present and which are not. Take these examples:\n\n   - `11111` would represent all 5 elements `[1,2,3,4,5]`\n   - `10101` would represent elements `[1,3,5]`\n   - `00000` would represent an empty set `[]`\n\n2. These bitmasks are then encoded as BigInt values which we can operate with\n   bitwise operations. You use these methods instead of looping and comparing\n  in the usual way.\n\nPlease note that althogh here we use the word `set` the actual\nimplementation is based on `arrays` since we need the indexes of elements to\nmaintain the internal consistency of the associated bitmasks.\n\n## Development / testing\n\n1. Clone repo.\n2. ```npm install```\n3. ```npm test```\n\n## Debugging\n\nIf you want to interactively debug the code/tests you might want to invoke mocha as follows:\n\nPlace a `debugger` call anywhere to create a breakpoint for use with the NodeJS built-in debugger.\n\nThen, run:\n\n```\nmocha inspect\n```\n\nand input `c` to continue to your breakpoint.\n\n\nOr, alternatively run with the `NODE_INSPECT_RESUME_ON_START=1` flag to continue on to your breakpoint, without pausing at the high-level imports (which is a bit confusing initially).\n\n```\nNODE_INSPECT_RESUME_ON_START=1 mocha inspect\n```\n\nSee [https://mochajs.org/#-inspect-inspect-brk-inspect](https://mochajs.org/#-inspect-inspect-brk-inspect) and [https://nodejs.org/api/debugger.html](https://nodejs.org/api/debugger.html) for more information.\n\n\n*Note:* If the `mocha` command is not found, you might want to either install globally (npm install -g mocha) or add the specific `<project_root>/node_modules/.bin` to your $PATH.\n\n## Possible upgrades\n\nIt may be possible to add the following features to this implementation:\n\n1. Provide reasonable behaviour and API whenever the set's elements is empty on initialization.\n2. Be able to extend the `BitmaskSet` with more elements dynamically.\n3. Remove JSBI for native BigInt. https://github.com/GoogleChromeLabs/babel-plugin-transform-jsbi-to-bigint. Or perhaps completely use ArrayBuffer.\n\n## Further development\n\n1. Provide benchmarking against some other more \"tradditional\" approaches.\n2. Remove JSBI library.\n\n## Benchmarking\n\nThis package was extracted from a particular implementation we had to create\nsome time ago.\n\nActual performance for this library hasn't been measured yet, but at the time\nthis approach was the one to be easier to reason about and worked very well for\nour use case, which was finding elements in common with many dozens of\nthousand-element arrays quickly in the browser (for UI updates).\n\nThe approach implemented here might work best if you need to operate with many\narrays/sets instead of just a few.\n\nBenchmarking this properly may require hundreds of arrays of thousands of\nelements before computing the final elements, which is closer to the original\nissue we had to solve.\n\n## Alternatives?\n\nYes!, actually, try these ones first:\n\n1. https://lodash.com/\n1. https://github.com/lovasoa/fast_array_intersect\n2. https://github.com/YuJianrong/fast-array-diff\n3. https://github.com/chouguleds/array-operations\n4. https://socket.dev/npm/package/fast-loops\n5. https://npmmirror.com/package/nv-array-fast\n6. https://www.npmjs.com/package/gonfalon\n7. https://www.npmjs.com/package/big-bit-mask\n8. https://www.npmjs.com/package/easy-bits\n9. https://github.com/namuol/bm\n\n_We didn't tested them all, we just put a reasonble list for your reference._\n\n## License\n\nMIT\n\n## Contributors\n\nMiguel Diaz (@gato-omega)[https://github.com/gato-omega]","readmeFilename":"README.md"}