Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@bumbu
Last active August 29, 2015 13:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bumbu/9209560 to your computer and use it in GitHub Desktop.
Save bumbu/9209560 to your computer and use it in GitHub Desktop.
Keys tree parser
'''
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"
])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment