Improve primary grouping algorithm

Closes #358; see that issue for motivation.

I'd also like to squash merge this, since we don't need the commit history on master, and I'm fine keeping this branch on my remote.

Testing

Paste this into a .vim file and run it:

function! s:MakeTuple(x, ...)
  return [a:x, a:x]
endfunction

function! s:MakeTestTargets(n)
  return map(range(a:n), function('s:MakeTuple'))
endfunction

function! s:GetChildrenCountsForKeys(n_keys, targets_rem)
    " returns a list corresponding to s:jump_tokens; each
    " count represents how many hits are in the subtree
    " rooted at the corresponding jump token
    let counts = repeat([0], a:n_keys)
    let targets_rem = a:targets_rem

    let is_first_lvl = 1
    while targets_rem > 0
        " if we can't fit all the hits in the first lvl,
        " fit the remainder starting from the last jump token
        let n_children = is_first_lvl
                    \ ? 1
                    \ : a:n_keys - 1
        for j in range(a:n_keys)
            let counts[j] += n_children
            let targets_rem -= n_children
            if targets_rem <= 0
                let counts[j] += targets_rem
                break
            endif
        endfor
        let is_first_lvl = 0
    endwhile

    return reverse(counts)
endfunction

" -- Single-key/closest target priority tree {{{
function! s:GroupingAlgorithmSCTree(targets, keys)
    " returns a tree where non-leaf nodes are keys and leaves are targets, which
    " are tuples [lineno, colno].
    "
    " each level of the tree is filled such that the average path depth of the tree
    " is minimized and the closest targets come first.
    let tree = {}

    " i: index into targets
    " j: index into keys
    let i = 0
    let j = 0
    for key_count in s:GetChildrenCountsForKeys(len(a:keys), len(a:targets))
        let node = a:keys[j]
        if key_count == 1
            let tree[node] = a:targets[i]
        elseif key_count > 1
            let tree[node] = s:GroupingAlgorithmSCTree(a:targets[i:i + key_count - 1], a:keys)
        else
            continue
        endif
        let j += 1
        let i += key_count
    endfor

    return tree
endfunction

let g:EasyMotion_keys = 'abcd'

echom string(s:GroupingAlgorithmSCTree(s:MakeTestTargets(3), split(g:EasyMotion_keys, '\zs')))
echom string(s:GroupingAlgorithmSCTree(s:MakeTestTargets(4), split(g:EasyMotion_keys, '\zs')))
echom string(s:GroupingAlgorithmSCTree(s:MakeTestTargets(5), split(g:EasyMotion_keys, '\zs')))
echom string(s:GroupingAlgorithmSCTree(s:MakeTestTargets(6), split(g:EasyMotion_keys, '\zs')))
echom string(s:GroupingAlgorithmSCTree(s:MakeTestTargets(7), split(g:EasyMotion_keys, '\zs')))
echom string(s:GroupingAlgorithmSCTree(s:MakeTestTargets(8), split(g:EasyMotion_keys, '\zs')))
echom string(s:GroupingAlgorithmSCTree(s:MakeTestTargets(18), split(g:EasyMotion_keys, '\zs')))

Output (prettified):

{'a': [0, 0], 'b': [1, 1], 'c': [2, 2]}
{'a': [0, 0], 'b': [1, 1], 'c': [2, 2], 'd': [3, 3]}
{
    'a': [0, 0],
    'b': [1, 1],
    'c': [2, 2],
    'd': {'a': [3, 3], 'b': [4, 4]}
}
{
    'a': [0, 0],
    'b': [1, 1],
    'c': [2, 2],
    'd': {'a': [3, 3], 'b': [4, 4], 'c': [5, 5]}
}
{
    'a': [0, 0],
    'b': [1, 1],
    'c': [2, 2],
    'd': {'a': [3, 3], 'b': [4, 4], 'c': [5, 5], 'd': [6, 6]}
}
{
    'a': [0, 0],
    'b': [1, 1],
    'c': {'a': [2, 2], 'b': [3, 3]},
    'd': {'a': [4, 4], 'b': [5, 5], 'c': [6, 6], 'd': [7, 7]}
}
{
  'a': {'a': [0, 0], 'b': [1, 1], 'c': [2, 2], 'd': [3, 3]}, 
  'b': {'a': [4, 4], 'b': [5, 5], 'c': [6, 6], 'd': [7, 7]},
  'c': {'a': [8, 8], 'b': [9, 9], 'c': [10, 10], 'd': [11, 11]} , 
  'd': {
      'a': [12, 12],
      'b': [13, 13],
      'c': [14, 14],
      'd': {'a': [15, 15], 'b': [16, 16], 'c': [17, 17]}
  }
}

which we know is correct.

I also installed the plugin from my branch

Plug 'yangmillstheory/vim-easymotion', { 'branch': 'hygiene/grouping-algo' }

and verified everything still worked.

easymotion / vim-easymotion

Improve primary grouping algorithm #359

Testing