Keys tree parser

tree_parser.coffee

'''
Given input

[
    "category:subcategory:item1"
  , "category:subcategory:item2"
  , "category2:item2"
  , "category2:item3"
  , "item3"
]

Expected result

[
  {name: "category", children: [
    {name: "subcategory", children: [
      {name: "item"}, {name: "item2"}
    ]}
  ]},
  {name: "category2", children: [
    {name:"item2"}, {name:"item3"}
  ]},
  {name: "item3"}
]

Algorithm

1. Sort input. This way branches will be aranged. Smaller contained branches will come first (cat1:subcat2 before cat1:subcat2:item3).
2. Add first branch. Store branch nodes.
3. Find common parent between first and second branch. Create only a subbranch based on a common parent. Store last used branch.
4. Do the same for 2nd and 3rd branch.
'''

class TreeParser
  similarity: (str1, str2)->
    _similarity = 0
    for c in str1
      if str2.length > _similarity and c is str2[_similarity]
        _similarity++
      else
        break

    return _similarity

  depthSimilarity: (str1, str2)->
    # denormalise strings
    str1 += ':' if str1[str1.length - 1] isnt ':'
    str2 += ':' if str2[str2.length - 1] isnt ':'

    # count number of column occurences in common string
    str1.substr(0, @similarity(str1, str2)).split('').filter((a)-> return a is ':').length

  treeBreadcrumbs: []
  treeParsed: {name: '__tree__', children: []}

  behead: (key)->
    if key.indexOf(':') isnt -1
      head = key.substr(0, key.indexOf(':'))
      tail = key.substr(key.indexOf(':') + 1)
    else
      head = key
      tail = ''

    return [head, tail]

  attachBranch: (branchDiff, _depthSimilarity, checkForChildren = false)->
    [name, tail] = @behead branchDiff

    # Check for active branch cache
    if _depthSimilarity is 0
      node = @treeParsed
      @treeBreadcrumbs = []
    else if _depthSimilarity is @treeBreadcrumbs.length
      # Last cached node is common parent
      node = @treeBreadcrumbs[@treeBreadcrumbs.length - 1]
      # Create children if necessary
      node.children = [] if checkForChildren and not node.hasOwnProperty('children')
    else if _depthSimilarity < @treeBreadcrumbs.length
      # Cut up to common parent node
      @treeBreadcrumbs.splice(_depthSimilarity)
      # Get last node
      node = @treeBreadcrumbs[@treeBreadcrumbs.length - 1]

    node.children.push
      name: name

    # Cache new node
    @treeBreadcrumbs.push node.children[node.children.length - 1] # last node children

    if tail
      # Create children if there are more nodes to add
      node.children[node.children.length - 1].children = []

      # Process next node
      @attachBranch tail, _depthSimilarity + 1

  keyPrev: ''

  parse: (list)->
    # Reset cache
    @treeBreadcrumbs = []
    @treeParsed = {name: '__tree__', children: []}

    for key in list.sort()
      _depthSimilarity = @depthSimilarity(@keyPrev, key)

      # Find varying subbranch
      branchDiff = key.split(':')[_depthSimilarity..].join(':')

      # Attach subbranch to tree
      @attachBranch branchDiff, _depthSimilarity, true

      # Cache current key
      @keyPrev = key

    @treeParsed.children

treeParser = new TreeParser()
console.log treeParser.parse([
    "cat1:subcat1:item1"
  , "cat1:subcat1:item2"
  , "cat1:subcat2:item1"
  , "cat2:subcat3:item4:prop1"
  , "cat2:subcat3:item4"
  , "cat2:subcat3:item5"
  , "cat2:subcat3:item5:prop2"
  , "cat2:subcat3:item5:prop2:red"
  , "cat2:subcat3:item5:prop2:blue"
  , "cat3"
])