Convert a simplified directory structure (tree) to a set of clustered documents. Parameterised to control cluster sizes.

output.txt

{ id: 'A',
  chn: 
   [ { id: 'B', chn: [ { id: 'D', chn: [] } ] },
     { id: 'C',
       chn: 
        [ { id: 'E', chn: [] },
          { id: 'F', chn: [] },
          { id: 'G',
            chn: 
             [ { id: 'H', chn: [ { id: 'I', chn: [] }, { id: 'J', chn: [] } ] } ] } ] } ] } 
             
             
[ { id: 'B', chn: [ { id: 'D', chn: [] } ] },
  { id: 'H', chn: [ { id: 'I', chn: [] }, { id: 'J', chn: [] } ] },
  { id: 'C',
    chn: 
     [ { id: 'E', chn: [] },
       { id: 'F', chn: [] },
       { id: 'G', chn: [ 'H' ] } ] },
  { id: 'A', chn: [ 'B', 'C' ] } ] 
  
  
{ id: 'A',
  chn: 
   [ { id: 'B', chn: [ { id: 'D', chn: [] } ] },
     { id: 'C',
       chn: 
        [ { id: 'E', chn: [] },
          { id: 'F', chn: [] },
          { id: 'G',
            chn: 
             [ { id: 'H', chn: [ { id: 'I', chn: [] }, { id: 'J', chn: [] } ] } ] } ] } ] }

tree_docs_cluster.js

const util = require('util')

// simplified verion of tree for easier interpretation

// tree = {
//     A: {
//         B: {
//             D: {}
//         },
//         C: {
//             E: {},
//             F: {},
//             G: {
//                 H: {
//                     I: {},
//                     J: {}
//                 }
//             }
//         }
//     }
// };

const tree = {
    id: 'A',
    chn: [
        {
            id: 'B', chn: [
                { id: 'D', chn: [] }
            ]
        },
        {
            id: 'C',
            chn: [
                { id: 'E', chn: [] },
                { id: 'F', chn: [] },
                {
                    id: 'G',
                    chn: [
                        {
                            id: 'H', chn: [
                                { id: 'I', chn: [] },
                                { id: 'J', chn: [] }
                            ]
                        }
                    ]
                }
            ]
        }
    ]
}



/* Next two functions map a tree to a set of documents */



// recursive function - effects happen as we recur back up the stack.
// count own children and notify callee (parent node).
// callee decides whether to keep as direct child or create new document.
const split = (tree, docs, limit) => {
    let count = 1

    for (let i = 0; i < tree.chn.length; i++) {
        let res = split(tree.chn[i], docs, limit)

        if (res < limit) {
            count += res
        } else {
            docs.push(tree.chn[i])
            tree.chn[i] = tree.chn[i].id // change from object to reference
        }
    }

    return count
}

// wrapper for split function.
const treeToDocs = (tree, limit) => {
    let docs = []
    split(tree, docs, limit)
    docs.push(tree)
    return docs
}



/* Next three functions map a set of documents to a tree */



// for each child of node, check if it's a reference or object.
// if a reference, fetch from docs and replace element in array (string to object).
// recur for each child.
const mapChildren = (tree, docs) => {
    for (let i = 0; i < tree.chn.length; i++) {
        if (typeof tree.chn[i] === 'string') {
            let child = docs.find(c => c.id === tree.chn[i])
            tree.chn[i] = child
        }
        mapChildren(tree.chn[i], docs)
    }
}

// wrapper for mapChildren function.
const docsToTree = (docs, start) => {
    let tree = docs.find(d => d.id === start)
    docs.splice(docs.indexOf(tree), 1)
    mapChildren(tree, docs)
    return tree
}



/* Call functions and display data  */
console.log(util.inspect(tree, false, null), '\n\n')

let documents = treeToDocs(tree, 2)
console.log(util.inspect(documents, false, null), '\n\n')

let remapped = docsToTree(documents, 'A')
console.log(util.inspect(remapped, false, null), '\n\n')