Module "rfn/group-binary"

Const groupBinary

• groupBinary<T>(bits: number, key: Fn<T, number>, branch?: Fn0<IObjectOf<T[]>>, leaf?: Reducer<any, T>, left?: PropertyKey, right?: PropertyKey): Reducer<any, T>

• Creates a bottom-up, unbalanced binary tree of desired depth and choice of data structures. Any value can be indexed, as long as a numeric representation (key) can be obtained. This numeric key is produced by the supplied key function. IMPORTANT: the returned values MUST be unsigned and less than the provided bit length (i.e. 0 .. (2^bits) - 1 range).

  By default the tree is constructed using plain objects for branches, with left branches stored as "l" and right ones as "r". The original values are stored at the lowest tree level using a customizable nested reducer. By default leaves are collected in arrays (using the {@link (push:1)} reducer), but any suitable reducer can be used (e.g. {@link (conj:1)} to collect values into sets).

  Index by lowest 4-bits of ID value:

  example

  tree = reduce(
    groupBinary(4, x => x.id & 0xf),
    [{id: 3}, {id: 8}, {id: 15}, {id: 0}]
  )
  
  tree.l.l.l.l
  // [ { id: 0 } ]
  tree.r.r.r.r
  // [ { id: 15 } ]
  tree.l.l.r.r
  // [ { id: 3 } ]

  Collecting as array:

  example

  tree = reduce(
    groupBinary(4, identity, ()=>[], push(), 0, 1),
    [1,2,3,4,5,6,7]
  )
  
  tree[0][1][0][1] // 0101 == 5 in binary
  // [ 5 ]
  
  tree[0][1][1]    // 011* == branch
  // [ [ 6 ], [ 7 ] ]

  Using {@link (frequencies:1)} as leaf reducer:

  example

  tree = reduce(
    groupBinary(3, (x: string) => x.length, null, frequencies()),
    "aa bbb dddd ccccc bbb eeee fff".split(" ")
  )
  // [ [ undefined,
  //     [ Map { 'aa' => 1 },
  //       Map { 'bbb' => 2, 'fff' => 1 } ] ],
  //   [ [ Map { 'dddd' => 1, 'eeee' => 1 },
  //       Map { 'ccccc' => 1 } ] ] ]
  
  tree[0][1][1]
  // Map { 'bbb' => 2, 'fff' => 1 }

  Type parameters

  • T

  Parameters

  • bits: number

    index range (always from 0)

  • key: Fn<T, number>

    key function

  • Optional branch: Fn0<IObjectOf<T[]>>

    function to create a new branch container (object or array)

  • Optional leaf: Reducer<any, T>

    reducer for leaf collection

  • Default value left: PropertyKey = "l"

    key for storing left branches (e.g. 0 for arrays)

  • Default value right: PropertyKey = "r"

    key for storing right branches (e.g. 1 for arrays)

  Returns Reducer<any, T>