Flatten a Dingo dictionary representation of into a list
        of fact-term/value pairs and associated information about tree structure (in node_id)
        and a dictionary mapping XML attributes to node identifiers.

        This all is best explained by example (see below).

        Note that attributes are also represented in the flattened representation. There
        are cases in which attributes should not lead to an entry in the flattened representation.
        This can be configured by passing the flatten method a predicate function 'attr_ignore_predicate'.
        The function takes a dictionary and returns True (ignore) or False (do not ignore). It
        is passed the dictionary representing an entry in the flat representation, such as follows::

              { 'node_id': 'N001:L000:N000:A000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'condition',
              'value': u'Equals'},

        By default, the following predicate is used::

             (lambda x : '@' in x['attribute'])

        This is because during import, DINGO adds certain annotations to the import dictionary
        as attributes with a second leading '@'.

        Input Example (CybOx)::

            {'File_Name': {'@condition': 'Equals',  '_value': u'UNITED NATIONS COMPENSATION SCHEME...pdf'},
              'Hashes': {'Hash': [{'Simple_Hash_Value':
                                    {'@condition': 'Equals',
                                     '@datatype': 'hexBinary',
                                      '_value': u'576fea79dd23a352a14c3f8bf3dbc9eb732e1d54f804a29160894aec55df4bd5'},
                                   'Type': {'_value': 'SHA256'}},
                                  {'Simple_Hash_Value': {'@condition': 'Equals',
                                                         '@datatype': 'hexBinary',
                                                         '_value': u'491809c2092cecd633e43d465409a78c'},
                                   'Type': {'_value': 'MD5'}}]
                        }
            }

        Output Example::

          [ { 'node_id': 'N000',
              'term': 'File_Name',
              'attribute': False,
              'value': u'UNITED NATIONS COMPENSATION SCHEME...pdf'},
              { 'node_id': 'N000:A000',
              'term': 'File_Name',
              'attribute': 'condition',
              'value': u'Equals'},
            { 'node_id': 'N001:L000:N000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': False,
              'value': u'576fea79dd23a352a14c3f8bf3dbc9eb732e1d54f804a29160894aec55df4bd5'},
            { 'node_id': 'N001:L000:N000:A000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'condition',
              'value': u'Equals'},
            { 'node_id': 'N001:L000:N000:A001',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'datatype',
              'value': u'hexBinary'},
            { 'node_id': 'N001:L000:N001',
              'term': 'Hashes/Hash/Type',
              'attribute': False,
              'value': 'SHA256'},
            { 'node_id': 'N001:L001:N000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': False,
              'value': u'491809c2092cecd633e43d465409a78c'},
            { 'node_id': 'N001:L001:N000:A000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'condition',
              'value': u'Equals'},
            { 'node_id': 'N001:L001:N000:A001',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'datatype',
              'value': u'hexBinary'},
            { 'node_id': 'N001:L001:N001',
              'term': 'Hashes/Hash/Type',
              'attribute': False,
              'value': 'MD5'}
          ]

          { 'N000': { 'condition': 'Equals'},
            'N001:L000:N000': { 'condition': 'Equals', 'datatype': 'hexBinary'},
            'N001:L001:N000': { 'condition': 'Equals', 'datatype': 'hexBinary'},
          }

def flatten(self, attr_ignore_predicate=None,force_nonleaf_fact_predicate=None,namespace_dict=None):
        """
        Flatten a Dingo dictionary representation of into a list
        of fact-term/value pairs and associated information about tree structure (in node_id)
        and a dictionary mapping XML attributes to node identifiers.

        This all is best explained by example (see below).

        Note that attributes are also represented in the flattened representation. There
        are cases in which attributes should not lead to an entry in the flattened representation.
        This can be configured by passing the flatten method a predicate function 'attr_ignore_predicate'.
        The function takes a dictionary and returns True (ignore) or False (do not ignore). It
        is passed the dictionary representing an entry in the flat representation, such as follows::

              { 'node_id': 'N001:L000:N000:A000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'condition',
              'value': u'Equals'},

        By default, the following predicate is used::

             (lambda x : '@' in x['attribute'])

        This is because during import, DINGO adds certain annotations to the import dictionary
        as attributes with a second leading '@'.

        Input Example (CybOx)::

            {'File_Name': {'@condition': 'Equals',  '_value': u'UNITED NATIONS COMPENSATION SCHEME...pdf'},
              'Hashes': {'Hash': [{'Simple_Hash_Value':
                                    {'@condition': 'Equals',
                                     '@datatype': 'hexBinary',
                                      '_value': u'576fea79dd23a352a14c3f8bf3dbc9eb732e1d54f804a29160894aec55df4bd5'},
                                   'Type': {'_value': 'SHA256'}},
                                  {'Simple_Hash_Value': {'@condition': 'Equals',
                                                         '@datatype': 'hexBinary',
                                                         '_value': u'491809c2092cecd633e43d465409a78c'},
                                   'Type': {'_value': 'MD5'}}]
                        }
            }

        Output Example::

          [ { 'node_id': 'N000',
              'term': 'File_Name',
              'attribute': False,
              'value': u'UNITED NATIONS COMPENSATION SCHEME...pdf'},
              { 'node_id': 'N000:A000',
              'term': 'File_Name',
              'attribute': 'condition',
              'value': u'Equals'},
            { 'node_id': 'N001:L000:N000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': False,
              'value': u'576fea79dd23a352a14c3f8bf3dbc9eb732e1d54f804a29160894aec55df4bd5'},
            { 'node_id': 'N001:L000:N000:A000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'condition',
              'value': u'Equals'},
            { 'node_id': 'N001:L000:N000:A001',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'datatype',
              'value': u'hexBinary'},
            { 'node_id': 'N001:L000:N001',
              'term': 'Hashes/Hash/Type',
              'attribute': False,
              'value': 'SHA256'},
            { 'node_id': 'N001:L001:N000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': False,
              'value': u'491809c2092cecd633e43d465409a78c'},
            { 'node_id': 'N001:L001:N000:A000',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'condition',
              'value': u'Equals'},
            { 'node_id': 'N001:L001:N000:A001',
              'term': 'Hashes/Hash/Simple_Hash_Value',
              'attribute': 'datatype',
              'value': u'hexBinary'},
            { 'node_id': 'N001:L001:N001',
              'term': 'Hashes/Hash/Type',
              'attribute': False,
              'value': 'MD5'}
          ]

          { 'N000': { 'condition': 'Equals'},
            'N001:L000:N000': { 'condition': 'Equals', 'datatype': 'hexBinary'},
            'N001:L001:N000': { 'condition': 'Equals', 'datatype': 'hexBinary'},
          }

        """

        if not namespace_dict:
            namespace_dict = {}



        def node_id_gen(n):
            """
            Given an integer, generate a fixed-length representation.

            This is used for coding tree-node representations such
            as N001:N005:N009 (9th child of 5th child of 1st child).

            Currently, we use three digits, i.e., we get problems
            if we import stuff with more than 1000 children in a node.

            """

            return "%s%04d" % (n[0], n[1])



        RE_ELEMENT_MATCHER = re.compile(r"[^@_].*")


        def _flatten(self, result_list, attr_dict, elt_names, prefix):
            """
            Flatten a Dingo dictionary representation of an infomration object into a list
            of fact-term/value pairs and associated information about tree structure (in node_id)
            and XML attributes.

            Internal function for recursive calls.

            """

            if '@@ns' in self.keys():
                current_namespace = (namespace_dict.get(self.get('@@ns'),None),self.get('@@ns'))
            else:
                current_namespace = (None,None)

            attributes = filter(lambda x: x[0] == '@', self.keys())

            node_id = ':'.join(map(node_id_gen, prefix))
            for attribute in attributes:
                if node_id not in attr_dict.keys():
                    attr_dict[node_id] = {attribute[1:]: self[attribute]}
                else:
                    attr_dict[node_id][attribute[1:]] = self[attribute]

            elements = filter(lambda x: RE_ELEMENT_MATCHER.match(x), self)

            fact_data = {'term': '/'.join(elt_names),
                         'namespaces' : map(lambda x: x[2],prefix),
                         'value': self.get('_value', ''),
                         'attribute': False,
                         'node_id': node_id}

            if elements == [] or force_nonleaf_fact_predicate(fact_data,attributes):
                logger.debug("Entered _VALUE branch for %s" % self)
                if '_value' in self.keys() or attributes != []:
                    fact_data = {'term': '/'.join(elt_names),
                                 'namespaces' : map(lambda x: x[2],prefix),
                                 'value': self.get('_value', ''),
                                 'attribute': False,
                                 'node_id': node_id}
                    result_list.append(fact_data)
                    logger.debug("Appended fact %s" % fact_data)
            if elements != []:

                counter = 0
                for element in elements:
                    logger.debug("Processing element %s" % element)
                    if type(self[element]) == type([]):
                        logger.debug("Entered list branch for %s " % self[element])

                        for sub_elt in self[element]:
                            current_namespace = (namespace_dict.get(sub_elt.get('@@ns'),None),sub_elt.get('@@ns'))

                            (result_list, attr_dict) = _flatten(sub_elt,
                                                                result_list=result_list,
                                                                attr_dict=attr_dict,
                                                                elt_names=elt_names + [element],
                                                                prefix=prefix + [('L', counter,current_namespace)])


                            counter += 1
                    elif isinstance(self[element],basestring):
                        logger.debug("Entered value branch for %s" % self[element])
                        # added this branch to deal with abbreviated dictionaries
                        # that provide value directly rather then via '_value' key in dictionary

                        # temporarily append namespace
                        elt_names.append(element)

                        fact_data = {'term': '/'.join(elt_names),
                                     'namespaces' : map(lambda x: x[2],prefix + [('N',counter,current_namespace)]),
                                     'value': self[element],
                                     'attribute': False,
                                     'node_id': "%s" % ':'.join(map(node_id_gen, prefix + [('N', counter,current_namespace)]))}
                        logger.debug("Appended fact %s" % fact_data)
                        result_list.append(fact_data)
                        # clean up namespace
                        elt_names = elt_names[:-1]
                        counter += 1
                    else:
                        logger.debug("Recursing for %s" % self[element])
                        current_namespace = (namespace_dict.get(self[element].get('@@ns'),None),self[element].get('@@ns'))

                        (result_list, attr_dict) = _flatten(self[element],
                                                            result_list=result_list,
                                                            attr_dict=attr_dict,
                                                            elt_names=elt_names + [element],
                                                            prefix=prefix + [('N', counter,current_namespace)])
                        counter += 1

            attr_counter = 0
            for attribute in attributes:
                if node_id == '':
                    attr_node_id = node_id_gen(('A', attr_counter,(None,None)))
                else:
                    attr_node_id = "%s:%s" % (node_id, node_id_gen(('A', attr_counter,(None,None))))
                fact = {'term': "%s" % ('/'.join(elt_names)),
                        'namespaces' : map(lambda x: x[2],prefix),
                        'value': self[attribute],
                        'node_id': attr_node_id,
                        'attribute': attribute[1:],
                        'number_of_attributed_elements': len(elements)}
                if not attr_ignore_predicate(fact):
                    del(fact['number_of_attributed_elements'])
                    result_list.append(fact)
                    logger.debug("Appended fact %s" % fact)
                    attr_counter += 1
                else:
                    logger.debug("Ignoring fact %s because of attr_ignore_list" % fact)
            result_list.sort(key=lambda x: x['node_id'])

            return (result_list, attr_dict)

        if not attr_ignore_predicate:
            attr_ignore_predicate = (lambda x: '@' in x['attribute'])

        if not force_nonleaf_fact_predicate:
            force_nonleaf_fact_predicate = (lambda x,y: False)

        return _flatten(self,result_list=[], attr_dict={}, elt_names=[], prefix=[])