"=============================================================================
" File    : autoload/unite/source/outline/modules/tree.vim
" Author  : h1mesuke <himesuke@gmail.com>
" Updated : 2012-01-11
" Version : 0.5.1
" License : MIT license {{{
"
"   Permission is hereby granted, free of charge, to any person obtaining
"   a copy of this software and associated documentation files (the
"   "Software"), to deal in the Software without restriction, including
"   without limitation the rights to use, copy, modify, merge, publish,
"   distribute, sublicense, and/or sell copies of the Software, and to
"   permit persons to whom the Software is furnished to do so, subject to
"   the following conditions:
"   
"   The above copyright notice and this permission notice shall be included
"   in all copies or substantial portions of the Software.
"   
"   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
"   OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
"   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
"   IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
"   CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
"   TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
"   SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
" }}}
"=============================================================================

let s:save_cpo = &cpo
set cpo&vim

function! unite#sources#outline#modules#tree#import() abort
  return s:Tree
endfunction

"-----------------------------------------------------------------------------

function! s:get_SID() abort
  return matchstr(expand('<sfile>'), '<SNR>\d\+_')
endfunction
let s:SID = s:get_SID()
delfunction s:get_SID

" Tree module provides functions to build a tree structure.
" There are two ways to build a Tree:
"
"   A.  Build a Tree from a List of objects with the level attribute using
"       Tree.build(). 
"
"   B.  Build a Tree one node by one node manually using Tree.new() and
"       Tree.append_child().
"
" The following example shows how to build a Tree in the latter way.
"
" == Example
"
"   let s:Tree = unite#sources#outline#import('Tree')
"   
"   let root = s:Tree.new()
"   call s:Tree.append_child(root, heading_A)
"   call s:Tree.append_child(root, heading_B)
"   call s:Tree.append_child(heading_A, heading_1)
"   call s:Tree.append_child(heading_A, heading_2)
"   call s:Tree.append_child(heading_B, heading_3)
"
"     |/
"
"   root
"    |
"    +--heading_A
"    |   +--heading_1
"    |   +--heading_2
"    |
"    +--heading_B
"        +--heading_3
"
let s:Tree = unite#sources#outline#modules#base#new('Tree', s:SID)
let s:Tree.MAX_DEPTH = 20

" Creates a new root node.
"
function! s:Tree_new() abort
  return { '__root__': 1, 'id': 0, 'level': 0, 'children': [] }
endfunction
call s:Tree.function('new')

" Append {child} to a List of children of {node}.
"
function! s:Tree_append_child(node, child) abort
  if !has_key(a:node, 'children')
    let a:node.children = []
  endif
  call add(a:node.children, a:child)
  " Ensure that all nodes have `children'.
  if !has_key(a:child, 'children')
    let a:child.children = []
    " NOTE: While building a Tree, all nodes of the Tree pass through this
    " function as a:child.
  endif
endfunction
call s:Tree.function('append_child')

" Builds a tree structure from a List of elements, which are Dictionaries with
" `level' attribute, and then returns the root node of the built Tree.
"
" NOTE: This function allows discontinuous levels and can build a Tree from such
" a sequence of levels well.
"
"                                root              root
"                                 |                 |
"                                 +--1              +--1
"    [1, 3, 5, 5, 2, ...]   =>    |  +--3      =>   |  +--2
"                                 |  |  +--5        |  |  +--3
"                                 |  |  +--5        |  |  +--3
"                                 |  |              |  |
"                                 :  +--2           :  +--2
"
function! s:Tree_build(elems) abort
  let root = s:Tree_new()
  if empty(a:elems) | return root | endif
  " Build a Tree.
  let stack = [root]
  for elem in a:elems
    " Forget about the current children...
    let elem.children = []
    " Make the top of the stack point to the parent.
    while elem.level <= stack[-1].level
      call remove(stack, -1)
    endwhile
    call s:Tree_append_child(stack[-1], elem)
    call add(stack, elem)
  endfor
  call s:normalize_levels(root)
  return root
endfunction
call s:Tree.function('build')

" Normalize the level of nodes in accordance with the given Tree's structure.
"
"   root             root
"    |                |
"    +--1             +--1
"    |  +--3          |  +--2
"    |  |  +--5  =>   |  |  +--3
"    |  |  +--5       |  |  +--3
"    |  |             |  |
"    :  +--2          :  +--2
"
function! s:normalize_levels(node) abort
  for child in a:node.children
    let child.level = a:node.level + 1
    call s:normalize_levels(child)
  endfor
endfunction

" Flattens a Tree into a List with setting the levels of nodes.
"
function! s:Tree_flatten(node) abort
  let elems = []
  for child in a:node.children
    let child.level = a:node.level + 1
    call add(elems, child)
    let elems += s:Tree_flatten(child)
  endfor
  return elems
endfunction
call s:Tree.function('flatten')

"-----------------------------------------------------------------------------
" Tree.List

" Tree.List module provides functions to process a List of objects with the
" level attribute in tree-aware way. 
"
let s:List = unite#sources#outline#modules#base#new('List', s:SID)
let s:Tree.List = s:List

" Normalize the levels of {objs}.
"
function! s:List_normalize_levels(objs) abort
  let tree = s:Tree_build(a:objs)
  let objs = s:fast_flatten(tree)
  return objs
endfunction
call s:List.function('normalize_levels')

" Flattens a Tree into a List without setting the levels of nodes.
"
function! s:fast_flatten(node) abort
  let objs = []
  " Push toplevel nodes.
  let stack = reverse(copy(a:node.children))
  while !empty(stack)
    " Pop a node.
    let node = remove(stack, -1)
    call add(objs, node)
    " Push the node's children.
    let stack += reverse(copy(node.children))
  endwhile
  return objs
endfunction

" Resets the matched-marks of the candidates.
"
function! s:List_reset_marks(candidates) abort
  if empty(a:candidates) | return a:candidates | endif
  let prev_cand = {
        \ 'is_matched': 1, 'source__is_marked': 1,
        \ 'source__heading_level': 0,
        \ }
  for cand in a:candidates
    let cand.is_matched = 1
    let cand.source__is_marked = 1
    let prev_cand.source__has_marked_child =
          \ prev_cand.source__heading_level < cand.source__heading_level
    let prev_cand = cand
  endfor
  let cand.source__has_marked_child = 0
endfunction
call s:List.function('reset_marks')

" Marks the matched candidates and their ancestors.
"
" * A candidate is MATCHED for which eval({pred}) returns True.
" * A candidate is MARKED when any its child has been marked.
"
" NOTE: unite-outline's matcher and formatter see these flags to accomplish
" their tree-aware filtering and formatting tasks.
"
function! s:List_mark(candidates, pred, ...) abort
  let pred = substitute(a:pred, '\<v:val\>', 'cand', 'g')
  let mark_reserved = map(range(0, s:Tree.MAX_DEPTH), 0)
  for cand in reverse(copy(a:candidates))
    if !cand.source__is_marked
      continue
    endif
    let cand.is_matched = cand.is_matched && eval(pred)
    if cand.is_matched
      let matched_level = cand.source__heading_level
      if 1 < matched_level
        let mark_reserved[1 : matched_level - 1] = map(range(matched_level - 1), 1)
      endif
    endif
    let cand.source__is_marked = cand.is_matched
    if mark_reserved[cand.source__heading_level]
      let cand.source__is_marked = 1
      let cand.source__has_marked_child = 1
      let mark_reserved[cand.source__heading_level] = 0
    else
      let cand.source__has_marked_child = 0
    endif
  endfor
endfunction
call s:List.function('mark')

" Remove the matched headings and their descendants.
"
function! s:List_remove(headings, pred) abort
  let pred = substitute(a:pred, '\<v:val\>', 'head', 'g')
  let matched_level = s:Tree.MAX_DEPTH + 1
  let headings = []
  for head in a:headings
    if head.level <= matched_level
      if eval(pred)
        let matched_level = head.level
      else
        let matched_level = s:Tree.MAX_DEPTH + 1
        call add(headings, head)
      endif
    endif
  endfor
  return headings
endfunction
call s:List.function('remove')

unlet s:List

let &cpo = s:save_cpo
unlet s:save_cpo