Generate a dict of OrderedDicts, using the URIs of the Pale endpoints as the structure for the tree.
    Each level of the tree will contain a "path" property and an "endpoint" property.
    The "path" will contain further nested endpoints, sorted alphabetically.
    The "endpoint" will contain the documentation on the endpoint that ends at that level.

def generate_raml_tree(flat_resources, api_root):
    """Generate a dict of OrderedDicts, using the URIs of the Pale endpoints as the structure for the tree.
    Each level of the tree will contain a "path" property and an "endpoint" property.
    The "path" will contain further nested endpoints, sorted alphabetically.
    The "endpoint" will contain the documentation on the endpoint that ends at that level.
    """

    def clean_angle_brackets(string):
        """Remove the angle brackets from a string and return the cleaned string"""
        if string == None:
            result = None
        elif ":" in string:
            path = re.search("(\w+/<\w+)", string).group(0)
            result = re.sub(r'[<]','{', path)
            result += "}"
        else:
            result = re.sub(r'[>]','}', re.sub(r'[<]','{', string))
        return result

    def add_or_find_path(input, tree):
        """Recursively add or find a path to an input dict.
        The tree is a list of directories in nested order.
        Returns a list, containing 1) the innermost node's "endpoint" dict
        and 2) True if it was added as an empty dict, or False if not."""

        # if this is the last branch, return or add and return it
        if len(tree) == 1:
            if input.get(tree[0]) != None \
                and input.get(tree[0]).get("endpoint") != None \
                and len(input.get(tree[0]).get("endpoint")) > 0:
                return [input[tree[0]], False]
            else:
                input[tree[0]] = {}
                input[tree[0]]["path"] = {}
                input[tree[0]]["endpoint"] = {}
                return [input[tree[0]], True]

        # if this is not the last branch, check if it exists and add if necessary
        # then recurse on the next one
        else:
            if input.get(tree[0]) == None:
                input[tree[0]] = {}
                input[tree[0]]["path"] = {}
            return add_or_find_path(input[tree[0]]["path"], tree[+1:])

    def sort_tree_alphabetically(tree):
        """Recursively sort a tree by the keys in each "path" dict.
        Each "path" dict will be converted to an OrderedDict that is sorted alphabetically.
        """

        if tree.get("path") != None and len(tree["path"]) > 0:
            sorted_path = OrderedDict(sorted(tree["path"].items(), key=lambda t: t[0]))
            tree["path"] = sorted_path
            for branch in tree["path"]:
                sort_tree_alphabetically(tree["path"][branch])


    # use a combination of three regex patterns to find all the components of the path
    # these will be used to generate the nested dict that we will convert to RAML

    # pattern #1: matches "path/<id:specialchars>"
    re_dir_nested = "(\w+/[<>\w]+:.*>)"
    # pattern #2: matches "path/<id>""
    re_dir_unique = "(\w+/<[\w\(\)\?\!\.\+]+>)"
    # pattern #3: matches "path" or "<id>" not appearing before "<"
    re_dir_either = "([<>\w\(\)\?\!\.\+]+)(?!<)"
    # combine the patterns
    uri_re_pattern = re_dir_nested + "|" + re_dir_unique + "|" + re_dir_either


    resource_tree = {}
    resource_tree["path"] = {}

    for doc in flat_resources:

        if flat_resources[doc].get("uri") != None:
            this_uri = flat_resources[doc]["uri"]
            uri_matches = re.findall(uri_re_pattern, flat_resources[doc]["uri"])
            uri_tree = []

            # treat the 'uri' string as a nested path, parsing out each directory and adding
            # to the 'uri_tree' list from left to right
            # leftmost element in list is root of path
            for match in uri_matches:
                for directory in match:
                    if directory != "" and directory != api_root:
                        branch = directory
                        matched_group = re.search('([\w+/]?[<:!\?\+\(\.\*\)>\w]+>)', directory)
                        if matched_group:
                            nested_prefix = clean_angle_brackets(directory)
                            if nested_prefix != None:
                                branch = nested_prefix
                        elif "<" in directory:
                            branch = clean_angle_brackets(directory)
                        uri_tree.append(branch)

            # find the path within the tree
            target = add_or_find_path(resource_tree["path"], uri_tree)
            # add the endpoint to the tree
            target[0]["endpoint"] = flat_resources[doc]

    sort_tree_alphabetically(resource_tree)
    return resource_tree