htdocs/Utils/HelpTreeBuilder.js

// Copyright (c) 2000-2019 Ericsson Telecom AB Telecom AB                                                       //
// All rights reserved. This program and the accompanying materials are made available under the     //
// terms of the Eclipse Public License v2.0 which accompanies this distribution, and is available at //
// https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html                                                         //
///////////////////////////////////////////////////////////////////////////////////////////////////////
function HelpTreeBuilder(p_flatHelp) {
    "use strict";
    
    var v_flatHelp = p_flatHelp;
    
    this.getHelpTree = function(toSort) {
        var help = {"sources": []};
        
        for (var i = 0; i < v_flatHelp.sources.length; ++i) {
            var source = v_flatHelp.sources[i].source;
            var dataElements = v_flatHelp.sources[i].dataElements;
            
            var tree = [];
            help.sources.push({
                "source": source,
                "dataElements": tree
            });
            
            collectRemaining(dataElements, tree, false);
            if (toSort === true) {
                sortChildren(tree);
            }
        }

        return help;
    };
    
    function sortChildren(dataElements) {
        dataElements.sort(dataElementSort);
        for (var i = 0; i < dataElements.length; ++i) {
            traverseTree(dataElements[i], [dataElements[i]], function(path) {
                var dataElement = path[path.length - 1];
                if (dataElement.children != undefined && dataElement.children.length != 0) {
                    dataElement.children.sort(dataElementSort);
                }
            });
        }
    }
    
    function dataElementSort(a, b) {
        if (hasChildren(a)) {
            if (hasChildren(b)) {
                return dataElementNameCompare(a,b);
            } else {
                return -1;
            }
        } else if (hasChildren(b)) {
            return 1;
        } else {
            return dataElementNameCompare(a,b);
        }
    }
    
    function hasChildren(dataElement) {
        return dataElement.children != undefined && dataElement.children.length != 0
    }
    
    function dataElementNameCompare(a, b) {
        if (a.dataElement.name < b.dataElement.name) {
            return -1;
        } else if (a.dataElement.name > b.dataElement.name) {
            return 1;
        } else {
            return 0;
        }
    }
    
    function collectRemaining(dataElements, tree, force) {
        var originalLength = dataElements.length;
        
        var inserted = true;
        while (inserted) {
            var i = 0;
            inserted = false;
            while (i < dataElements.length) {
                if (insert(dataElements[i], tree, force)) {
                    inserted = true;
                    dataElements.splice(i, 1);
                } else {
                    ++i;
                }
            }
        }
        
        // if we did not insert anything but should have
        if (dataElements.length == originalLength && dataElements.length != 0) {
            if (window["console"] != undefined && console.log != undefined) {
                console.log("Failed to insert some elements into the help tree");
                console.log(dataElements);
            }
            // insert the remaining to the root
            for (var i = 0; i < dataElements.length; ++i) {
                tree.push(dataElements[i]);
            }
        // if there are still some elements left, force insert them
        } else if (dataElements.length != 0) {
            // TODO: we could make this not recursive, but it is unlikely to cause problems
            collectRemaining(dataElements, tree, true);
        }
    }
    
    function insert(dataElement, tree, force) {
        var references = getReferencedTypes(dataElement);
        if (references.length == 0) {
            // we can insert it into the root
            tree.push(dataElement);
            return true;
        } else {
            return insertIntoBestMatch(dataElement, references, tree, force);
        }
    }
    
    function insertIntoBestMatch(dataElement, references, tree, force) {
        // we give a score to every possible location and choose those that have a maximum score
        var bestScore = 0;
        var bestObjects = [];
        var allReferencesFound = false;
        
        for (var i = 0; i < tree.length; ++i) {
            traverseTree(tree[i], [tree[i]], function(path) {
                var scoreObj = getScore(path, mcopy(references));
                scoreObj["bestMatch"] = path[path.length - 1];
                var score = scoreObj.score;
                if (score > bestScore) {
                    bestScore = score;
                    bestObjects = [scoreObj];
                    allReferencesFound = scoreObj.allReferencesFound
                } else if (score == bestScore && allReferencesFound == scoreObj.allReferencesFound) {
                    bestObjects.push(scoreObj);
                }
            });
        }
        
        if (allReferencesFound) {
            // we can insert the element, since we found all references
            for (var i = 0; i < bestObjects.length; ++i) {
                if (bestObjects[i].bestMatch.children != undefined) {
                    bestObjects[i].bestMatch.children.push(dataElement);
                } else {
                    bestObjects[i].bestMatch.children = [dataElement];
                }
            }
            return true;
        } else if (force) {
            // we must insert the missing references too, but it is possible that we cannot insert it this way either.
            return insertMissingReferences(dataElement, bestObjects, tree);
        } else {
            // we could not insert the element
            return false;
        }
    }
    
    function findAllReferences(references, tree) {
        for (var i = 0; i < tree.length && references.length > 0; ++i) {
            traverseTree(tree[i], [tree[i]], function(path) {
                var type = getTypeName(path[path.length - 1]);
                var index = references.indexOf(type);
                if (index != -1) {
                    references.splice(index, 1);
                }
            });
        }
        return references.length == 0;
    }
    
    function traverseTree(dateElement, path, process) {
        process(path);
        if (dateElement.children != undefined) {
            var tree = dateElement.children;
            for (var i = 0; i < tree.length; ++i) {
                path.push(tree[i]);
                traverseTree(tree[i], path, process);
                path.pop();
            }
        }
    }
    
    function getScore(path, references) {
        var ref = mcopy(references);
        
        var score = 0;
        var types = [];
        for (var i = 0; i < path.length; ++i) {
            var type = getTypeName(path[i]);
            var referencesIndex = references.indexOf(type);
            if (types.indexOf(type) == -1) {
                types.push(type);
                if (referencesIndex != -1) {
                    references.splice(referencesIndex, 1);
                    // if we find a reference, increase the score by 1
                    ++score;
                }
            }
        }
        
        // the larger the depth, the larger the value we decrease the score with
        score -= path.length / 20;
        var allReferencesFound = references.length == 0;
        if (allReferencesFound) {
            // if we find all references the score will be large
            score += 100;
        }
        
        return {
            "score": score,
            "allReferencesFound": allReferencesFound,
            "missingReferences": references,
        };
    }
    
    function insertMissingReferences(dataElement, bestMatches, tree) {
        // the less elements we have to insert additionally, the higher the score
        var maxScore = 0;
        var maxObjects = [];
        
        for (var i = 0; i < bestMatches.length; ++i) {
            var bestMatch = bestMatches[i].bestMatch;
            var missingReferences = bestMatches[i].missingReferences;
            
            if (!findAllReferences(mcopy(missingReferences), tree)) {
                // we could not find every reference in the whole tree, maybe later
                continue;
            }
            
            var bestScore = 0;
            var bestPath;
            var stillMissing;
            
            for (var i = 0; i < tree.length; ++i) {
                traverseTree(tree[i], [tree[i]], function(path) {
                    var scoreObj = getScore(path, mcopy(missingReferences));
                    if (scoreObj.score > bestScore) {
                        bestScore = scoreObj.score;
                        bestPath = mcopy(path);
                        stillMissing = scoreObj.missingReferences;
                    }
                });
            }
            
            if (bestScore > maxScore) {
                maxScore = bestScore;
                maxObjects = [{
                    "bestMatch": bestMatch,
                    "bestPath": bestPath,
                    "missingReferences": stillMissing
                }];
            } else if (bestScore == maxScore) {
                maxObjects.push({
                    "bestMatch": bestMatch,
                    "bestPath": bestPath,
                    "missingReferences": stillMissing
                });
            }
        }
        
        if (maxObjects.length == 0) {
            // we could not find any element in the tree that would allow us to insert the current element
            return false;
        }
        
        for (var i = 0; i < maxObjects.length; ++i) {
            // we insert the whole path to the missing reference to be sure
            var newBestMatch = insertPath(maxObjects[i].bestMatch, maxObjects[i].bestPath);
            if (maxObjects[i].missingReferences.length != 0) {
                insertMissingReferences(dataElement, [maxObjects[i]], tree);
            } else {
                if (newBestMatch.children != undefined) {
                    newBestMatch.children.push(dataElement);
                } else {
                    newBestMatch.children = [dataElement];
                }
            }
        }
        
        return true;
    }
    
    function insertPath(insertInto, path) {
        for (var i = 0; i < path.length; ++i) {
            var obj = shallowcopy(path[i]);
            obj.children = undefined;
            if (insertInto.children != undefined) {
                insertInto.children.push(obj);
            } else {
                insertInto.children = [obj];
            }
            insertInto = obj;
        }
        return insertInto;
    }
    
    function getTypeName(p_dataElement) {
        var dataElement = p_dataElement.dataElement;
        if (dataElement.typeDescriptor != undefined && dataElement.typeDescriptor.typeName != undefined) {
            return dataElement.typeDescriptor.typeName
        } else {
            return undefined;
        }
    }
    
    function getReferencedTypes(p_dataElement) {
        var dataElement = p_dataElement.dataElement;
        var references = [];
        if (dataElement.parameters != undefined) {
            for (var i = 0; i < dataElement.parameters.length; ++i) {
                if (dataElement.parameters[i].typeDescriptor != undefined && dataElement.parameters[i].typeDescriptor.reference != undefined && dataElement.parameters[i].typeDescriptor.reference.typeName != undefined) {
                    references.push(dataElement.parameters[i].typeDescriptor.reference.typeName);
                }
            }
        }
        return references;
    }
}