1#!/usr/bin/env python3
2
3#******************************************************************************
4# treenode.py, provides a class to store tree node data
5#
6# TreeLine, an information storage program
7# Copyright (C) 2020, Douglas W. Bell
8#
9# This is free software; you can redistribute it and/or modify it under the
10# terms of the GNU General Public License, either Version 2 or any later
11# version.  This program is distributed in the hope that it will be useful,
12# but WITHOUT ANY WARRANTY.  See the included LICENSE file for details.
13#******************************************************************************
14
15import re
16import uuid
17import operator
18import itertools
19import treespot
20import nodeformat
21
22_replaceBackrefRe = (re.compile(r'\\(\d+)'), re.compile(r'\\g<(\d+)>'))
23_origBackrefMatch = None
24
25
26class TreeNode:
27    """Class to store tree node data and the tree's linked structure.
28
29    Stores a data dict, lists of children and a format name string.
30    Provides methods to get info on the structure and the data.
31    """
32    def __init__(self, formatRef, fileData=None):
33        """Initialize a tree node.
34
35        Arguments:
36            formatRef -- a ref to this node's format info
37            fileData -- a dict with uid, data, child refs & parent refs
38        """
39        self.formatRef = formatRef
40        if not fileData:
41            fileData = {}
42        self.uId = fileData.get('uid', uuid.uuid1().hex)
43        self.data = fileData.get('data', {})
44        self.tmpChildRefs = fileData.get('children', [])
45        self.childList = []
46        self.spotRefs = set()
47
48    def assignRefs(self, nodeDict):
49        """Add actual refs to child nodes from data in self.tmpChildRefs.
50
51        Any bad node refs (corrupt file data) are left in self.tmpChildRefs.
52        Arguments:
53            nodeDict -- all nodes stored by uid
54        """
55        try:
56            self.childList = [nodeDict[uid] for uid in self.tmpChildRefs]
57            self.tmpChildRefs = []
58        except KeyError:   # due to corrupt file data
59            badChildRefs = []
60            for uid in self.tmpChildRefs:
61                if uid in nodeDict:
62                    self.childList.append(nodeDict[uid])
63                else:
64                    badChildRefs.append(uid)
65            self.tmpChildRefs = badChildRefs
66
67    def generateSpots(self, parentSpot):
68        """Recursively generate spot references for this branch.
69
70        Arguments:
71            parentSpot -- the parent spot reference
72        """
73        spot = treespot.TreeSpot(self, parentSpot)
74        self.spotRefs.add(spot)
75        for child in self.childList:
76            child.generateSpots(spot)
77
78    def addSpotRef(self, parentNode, includeChildren=True):
79        """Add a spot ref here to the given parent if not already there.
80
81        If changed, propogate to descendant nodes.
82        Arguments:
83            parentNode -- the parent to ref in the new spot
84            includeChildren -- if True, propogate to descendant nodes
85        """
86        changed = False
87        origParentSpots = {spot.parentSpot for spot in self.spotRefs}
88        for parentSpot in parentNode.spotRefs:
89            if parentSpot not in origParentSpots:
90                self.spotRefs.add(treespot.TreeSpot(self, parentSpot))
91                changed = True
92        if changed and includeChildren:
93            for child in self.childList:
94                child.addSpotRef(self)
95
96    def removeInvalidSpotRefs(self, includeChildren=True, forceDesend=False):
97        """Verify existing spot refs and remove any that aren't valid.
98
99        If changed and includeChilderen, propogate to descendant nodes.
100        Arguments:
101            includeChildren -- if True, propogate to descendants if changes
102            forceDesend -- if True, force propogate to descendant nodes
103        """
104        goodSpotRefs = {spot for spot in self.spotRefs if
105                        (self in spot.parentSpot.nodeRef.childList and
106                         spot.parentSpot in spot.parentSpot.nodeRef.spotRefs)}
107        changed = len(self.spotRefs) != len(goodSpotRefs)
108        self.spotRefs = goodSpotRefs
109        if includeChildren and (changed or forceDesend):
110            for child in self.childList:
111                child.removeInvalidSpotRefs(includeChildren)
112
113    def spotByNumber(self, num):
114        """Return the spot at the given rank in the spot sequence.
115
116        Arguments:
117            num -- the rank number to return
118        """
119        spotList = sorted(list(self.spotRefs),
120                          key=operator.methodcaller('sortKey'))
121        return spotList[num]
122
123    def matchedSpot(self, parentSpot):
124        """Return the spot for this node that matches a parent spot.
125
126        Return None if not found.
127        Arguments:
128            parentSpot -- the parent to match
129        """
130        for spot in self.spotRefs:
131            if spot.parentSpot is parentSpot:
132                return spot
133        return None
134
135    def setInitDefaultData(self, overwrite=False):
136        """Add initial default data from fields into internal data.
137
138        Arguments:
139            overwrite -- if true, replace previous data entries
140        """
141        self.formatRef.setInitDefaultData(self.data, overwrite)
142
143    def parents(self):
144        """Return a set of parent nodes for this node.
145
146        Returns an empty set if called from the tree structure.
147        """
148        try:
149            return {spot.parentSpot.nodeRef for spot in self.spotRefs}
150        except AttributeError:
151            return set()
152
153    def numChildren(self):
154        """Return number of children.
155        """
156        return len(self.childList)
157
158    def descendantGen(self):
159        """Return a generator to step through all nodes in this branch.
160
161        Includes self and closed nodes.
162        """
163        yield self
164        for child in self.childList:
165            for node in child.descendantGen():
166                yield node
167
168    def ancestors(self):
169        """Return a set of all ancestor nodes (including self).
170        """
171        spots = set()
172        for spot in self.spotRefs:
173            spots.update(spot.spotChain())
174        return {spot.nodeRef for spot in spots}
175
176    def treeStructureRef(self):
177        """Return the tree structure based on the root spot ref.
178        """
179        return next(iter(self.spotRefs)).rootSpot().nodeRef
180
181    def fileData(self):
182        """Return the file data dict for this node.
183        """
184        children = [node.uId for node in self.childList]
185        fileData = {'format': self.formatRef.name, 'uid': self.uId,
186                    'data': self.data, 'children': children}
187        return fileData
188
189    def title(self, spotRef=None):
190        """Return the title string for this node.
191
192        If spotRef not given, ancestor fields assume first spot.
193        Arguments:
194            spotRef -- optional, used for ancestor field refs
195        """
196        return self.formatRef.formatTitle(self, spotRef)
197
198    def setTitle(self, title):
199        """Change this node's data based on a new title string.
200
201        Return True if successfully changed.
202        """
203        if title == self.title():
204            return False
205        return self.formatRef.extractTitleData(title, self.data)
206
207    def output(self, plainText=False, keepBlanks=False, spotRef=None):
208        """Return a list of formatted text output lines.
209
210        If spotRef not given, ancestor fields assume first spot.
211        Arguments:
212            plainText -- if True, remove HTML markup from fields and formats
213            keepBlanks -- if True, keep lines with empty fields
214            spotRef -- optional, used for ancestor field refs
215        """
216        return self.formatRef.formatOutput(self, plainText, keepBlanks,
217                                           spotRef)
218
219    def changeDataType(self, formatRef):
220        """Change this node's data type to the given name.
221
222        Set init default data and update the title if blank.
223        Arguments:
224            formatRef -- the new tree format type
225        """
226        origTitle = self.title()
227        self.formatRef = formatRef
228        formatRef.setInitDefaultData(self.data)
229        if not formatRef.formatTitle(self):
230            formatRef.extractTitleData(origTitle, self.data)
231
232    def setConditionalType(self, treeStructure):
233        """Set self to type based on auto conditional settings.
234
235        Return True if type is changed.
236        Arguments:
237            treeStructure -- a ref to the tree structure
238        """
239        if self.formatRef not in treeStructure.treeFormats.conditionalTypes:
240            return False
241        if self.formatRef.genericType:
242            genericFormat = treeStructure.treeFormats[self.formatRef.
243                                                      genericType]
244        else:
245            genericFormat = self.formatRef
246        formatList = [genericFormat] + genericFormat.derivedTypes
247        formatList.remove(self.formatRef)
248        formatList.insert(0, self.formatRef)   # reorder to give priority
249        neutralResult = None
250        newType = None
251        for typeFormat in formatList:
252            if typeFormat.conditional:
253                if typeFormat.conditional.evaluate(self):
254                    newType = typeFormat
255                    break
256            elif not neutralResult:
257                neutralResult = typeFormat
258        if not newType and neutralResult:
259            newType = neutralResult
260        if newType and newType is not self.formatRef:
261            self.changeDataType(newType)
262            return True
263        return False
264
265    def setDescendantConditionalTypes(self, treeStructure):
266        """Set auto conditional types for self and all descendants.
267
268        Return number of changes made.
269        Arguments:
270            treeStructure -- a ref to the tree structure
271        """
272        if not treeStructure.treeFormats.conditionalTypes:
273            return 0
274        changes = 0
275        for node in self.descendantGen():
276            if node.setConditionalType(treeStructure):
277                changes += 1
278        return changes
279
280    def setData(self, field, editorText):
281        """Set the data entry for the given field to editorText.
282
283        If the data does not match the format, sets to the raw text and
284        raises a ValueError.
285        Arguments:
286            field-- the field object to be set
287            editorText -- new text data from an editor
288        """
289        try:
290            self.data[field.name] = field.storedText(editorText)
291        except ValueError as err:
292            if len(err.args) >= 2:
293                self.data[field.name] = err.args[1]
294            else:
295                self.data[field.name] = editorText
296            raise ValueError
297
298    def wordSearch(self, wordList, titleOnly=False, spotRef=None):
299        """Return True if all words in wordlist are found in this node's data.
300
301        Arguments:
302            wordList -- a list of words or phrases to find
303            titleOnly -- search only in the title text if True
304            spotRef -- an optional spot reference for ancestor field refs
305        """
306        dataStr = self.title(spotRef).lower()
307        if not titleOnly:
308            # join with null char so phrase matches don't cross borders
309            dataStr = '{0}\0{1}'.format(dataStr,
310                                        '\0'.join(self.data.values()).lower())
311        for word in wordList:
312            if word not in dataStr:
313                return False
314        return True
315
316    def regExpSearch(self, regExpList, titleOnly=False, spotRef=None):
317        """Return True if the regular expression is found in this node's data.
318
319        Arguments:
320            regExpList -- a list of regular expression objects to find
321            titleOnly -- search only in the title text if True
322            spotRef -- an optional spot reference for ancestor field refs
323        """
324        dataStr = self.title(spotRef)
325        if not titleOnly:
326            # join with null char so phrase matches don't cross borders
327            dataStr = '{0}\0{1}'.format(dataStr, '\0'.join(self.data.values()))
328        for regExpObj in regExpList:
329            if not regExpObj.search(dataStr):
330                return False
331        return True
332
333    def searchReplace(self, searchText='', regExpObj=None, skipMatches=0,
334                      typeName='', fieldName='', replaceText=None,
335                      replaceAll=False):
336        """Find the search text in the field data and optionally replace it.
337
338        Returns a tuple of the fieldName where found (empty string if not
339        found), the node match number and the field match number.
340        Returns the last match if skipMatches < 0 (not used with replace).
341        Arguments:
342            searchText -- the text to find if regExpObj is None
343            regExpObj -- the regular expression to find if not None
344            skipMatches -- number of already found matches to skip in this node
345            typeName -- if given, verify that this node matches this type
346            fieldName -- if given, only find matches under this type name
347            replaceText -- if not None, replace a match with this string
348            replaceAll -- if True, replace all matches (returns last fieldName)
349        """
350        if typeName and typeName != self.formatRef.name:
351            return ('', 0, 0)
352        try:
353            fields = ([self.formatRef.fieldDict[fieldName]] if fieldName
354                      else self.formatRef.fields())
355        except KeyError:
356            return ('', 0, 0)   # field not in this type
357        matchedFieldname = ''
358        findCount = 0
359        prevFieldFindCount = 0
360        for field in fields:
361            try:
362                fieldText = field.editorText(self)
363            except ValueError:
364                fieldText = self.data.get(field.name, '')
365            fieldFindCount = 0
366            pos = 0
367            while True:
368                if pos >= len(fieldText) and pos > 0:
369                    break
370                if regExpObj:
371                    match = regExpObj.search(fieldText, pos)
372                    pos = match.start() if match else -1
373                else:
374                    pos = fieldText.lower().find(searchText, pos)
375                    if not searchText and fieldText:
376                        pos = -1  # skip invalid find of empty string
377                if pos < 0:
378                    break
379                findCount += 1
380                fieldFindCount += 1
381                prevFieldFindCount = fieldFindCount
382                matchLen = (len(match.group()) if regExpObj
383                            else len(searchText))
384                if findCount > skipMatches:
385                    matchedFieldname = field.name
386                    if replaceText is not None:
387                        replace = replaceText
388                        if regExpObj:
389                            global _origBackrefMatch
390                            _origBackrefMatch = match
391                            for backrefRe in _replaceBackrefRe:
392                                replace = backrefRe.sub(self.replaceBackref,
393                                                        replace)
394                        fieldText = (fieldText[:pos] + replace +
395                                     fieldText[pos + matchLen:])
396                        try:
397                            self.setData(field, fieldText)
398                        except ValueError:
399                            pass
400                    if not replaceAll and skipMatches >= 0:
401                        return (field.name, findCount, fieldFindCount)
402                pos = pos + matchLen if matchLen else pos + 1
403        if not matchedFieldname:
404            findCount = prevFieldFindCount = 0
405        return (matchedFieldname, findCount, prevFieldFindCount)
406
407    @staticmethod
408    def replaceBackref(match):
409        """Return the re match group from _origBackrefMatch for replacement.
410
411        Used for reg exp backreference replacement.
412        Arguments:
413            match -- the backref match in the replacement string
414        """
415        return _origBackrefMatch.group(int(match.group(1)))
416
417    def addNewChild(self, treeStructure, posRefNode=None, insertBefore=True,
418                    newTitle=_('New')):
419        """Add a new child node with this node as the parent.
420
421        Insert the new node near the posRefNode or at the end if no ref node.
422        Return the new node.
423        Arguments:
424            treeStructure -- a ref to the tree structure
425            posRefNode -- a child reference for the new node's position
426            insertBefore -- insert before the ref node if True, after if False
427        """
428        try:
429            newFormat = treeStructure.treeFormats[self.formatRef.childType]
430        except (KeyError, AttributeError):
431            if posRefNode:
432                newFormat = posRefNode.formatRef
433            elif self.childList:
434                newFormat = self.childList[0].formatRef
435            else:
436                newFormat = self.formatRef
437        newNode = TreeNode(newFormat)
438        pos = len(self.childList)
439        if posRefNode:
440            pos = self.childList.index(posRefNode)
441            if not insertBefore:
442                pos += 1
443        self.childList.insert(pos, newNode)
444        newNode.setInitDefaultData()
445        newNode.addSpotRef(self)
446        if newTitle and not newNode.title():
447            newNode.setTitle(newTitle)
448        treeStructure.addNodeDictRef(newNode)
449        return newNode
450
451    def changeParent(self, oldParentSpot, newParentSpot, newPos=-1):
452        """Move this node from oldParent to newParent.
453
454        Used for indent and unindent commands.
455        Arguments:
456            oldParent -- the original parent spot
457            newParent -- the new parent spot
458            newPos -- the position in the new childList, -1 for append
459        """
460        oldParent = oldParentSpot.nodeRef
461        oldParent.childList.remove(self)
462        newParent = newParentSpot.nodeRef
463        if newPos >= 0:
464            newParent.childList.insert(newPos, self)
465        else:
466            newParent.childList.append(self)
467        # preserve one spot to maintain tree expand state
468        self.matchedSpot(oldParentSpot).parentSpot = newParentSpot
469        self.removeInvalidSpotRefs()
470        self.addSpotRef(newParent)
471
472    def replaceChildren(self, titleList, treeStructure):
473        """Replace child nodes with titles from a text list.
474
475        Nodes with matches in the titleList are kept, others are added or
476        deleted as required.
477        Arguments:
478            titleList -- the list of new child titles
479            treeStructure -- a ref to the tree structure
480        """
481        try:
482            newFormat = treeStructure.treeFormats[self.formatRef.childType]
483        except (KeyError, AttributeError):
484            newFormat = (self.childList[0].formatRef if self.childList
485                         else self.formatRef)
486        matchList = []
487        remainTitles = [child.title() for child in self.childList]
488        for title in titleList:
489            try:
490                match = self.childList.pop(remainTitles.index(title))
491                matchList.append((title, match))
492                remainTitles = [child.title() for child in self.childList]
493            except ValueError:
494                matchList.append((title, None))
495        newChildList = []
496        firstMiss = True
497        for title, node in matchList:
498            if not node:
499                if (firstMiss and remainTitles and
500                    remainTitles[0].startswith(title)):
501                    # accept partial match on first miss for split tiles
502                    node = self.childList.pop(0)
503                    node.setTitle(title)
504                else:
505                    node = TreeNode(newFormat)
506                    node.setTitle(title)
507                    node.setInitDefaultData()
508                    node.addSpotRef(self)
509                    treeStructure.addNodeDictRef(node)
510                firstMiss = False
511            newChildList.append(node)
512        for child in self.childList:
513            for oldNode in child.descendantGen():
514                if len(oldNode.spotRefs) <= 1:
515                    treeStructure.removeNodeDictRef(oldNode)
516                else:
517                    oldNode.removeInvalidSpotRefs(False)
518        self.childList = newChildList
519
520    def replaceClonedBranches(self, origStruct):
521        """Replace any duplicate IDs with clones from the given structure.
522
523        Recursively search for duplicates.
524        Arguments:
525            origStruct -- the tree structure with the cloned nodes
526        """
527        for i in range(len(self.childList)):
528            if self.childList[i].uId in origStruct.nodeDict:
529                self.childList[i] = origStruct.nodeDict[self.childList[i].uId]
530            else:
531                self.childList[i].replaceClonedBranches(origStruct)
532
533    def loadChildNodeLevels(self, nodeList, initLevel=-1):
534        """Recursively add children from a list of nodes and levels.
535
536        Return True on success, False if data levels are not valid.
537        Arguments:
538            nodeList -- list of tuples with node and level
539            initLevel -- the level of this node in the structure
540        """
541        while nodeList:
542            child, level = nodeList[0]
543            if level == initLevel + 1:
544                del nodeList[0]
545                self.childList.append(child)
546                if not child.loadChildNodeLevels(nodeList, level):
547                    return False
548            else:
549                return -1 < level <= initLevel
550        return True
551
552    def fieldSortKey(self, level=0):
553        """Return a key used to sort by key fields.
554
555        Arguments:
556            level -- the sort key depth level for the current sort stage
557        """
558        if len(self.formatRef.sortFields) > level:
559            return self.formatRef.sortFields[level].sortKey(self)
560        return ('',)
561
562    def sortChildrenByField(self, recursive=True, forward=True):
563        """Sort child nodes by predefined field keys.
564
565        Arguments:
566            recursive -- continue to sort recursively if true
567            forward -- reverse the sort if false
568        """
569        formats = set([child.formatRef for child in self.childList])
570        maxDepth = 0
571        directions = []
572        for nodeFormat in formats:
573            if not nodeFormat.sortFields:
574                nodeFormat.loadSortFields()
575            maxDepth = max(maxDepth, len(nodeFormat.sortFields))
576            newDirections = [field.sortKeyForward for field in
577                             nodeFormat.sortFields]
578            directions = [sum(i) for i in itertools.zip_longest(directions,
579                                                                newDirections,
580                                                                fillvalue=
581                                                                False)]
582        if forward:
583            directions = [bool(direct) for direct in directions]
584        else:
585            directions = [not bool(direct) for direct in directions]
586        for level in range(maxDepth, 0, -1):
587            self.childList.sort(key = operator.methodcaller('fieldSortKey',
588                                                            level - 1),
589                                reverse = not directions[level - 1])
590        if recursive:
591            for child in self.childList:
592                child.sortChildrenByField(True, forward)
593
594    def titleSortKey(self):
595        """Return a key used to sort by titles.
596        """
597        return self.title().lower()
598
599    def sortChildrenByTitle(self, recursive=True, forward=True):
600        """Sort child nodes by titles.
601
602        Arguments:
603            recursive -- continue to sort recursively if true
604            forward -- reverse the sort if false
605        """
606        self.childList.sort(key = operator.methodcaller('titleSortKey'),
607                            reverse = not forward)
608        if recursive:
609            for child in self.childList:
610                child.sortChildrenByTitle(True, forward)
611
612    def updateNodeMathFields(self, treeFormats):
613        """Recalculate math fields that depend on this node and so on.
614
615        Return True if any data was changed.
616        Arguments:
617            treeFormats -- a ref to all of the formats
618        """
619        changed = False
620        for field in self.formatRef.fields():
621            for fieldRef in treeFormats.mathFieldRefDict.get(field.name, []):
622                for node in fieldRef.dependentEqnNodes(self):
623                    if node.recalcMathField(fieldRef.eqnFieldName,
624                                            treeFormats):
625                        changed = True
626        return changed
627
628    def recalcMathField(self, eqnFieldName, treeFormats):
629        """Recalculate a math field, if changed, recalc depending math fields.
630
631        Return True if any data was changed.
632        Arguments:
633            eqnFieldName -- the equation field in this node to update
634            treeFormats -- a ref to all of the formats
635        """
636        changed = False
637        oldValue = self.data.get(eqnFieldName, '')
638        newValue = self.formatRef.fieldDict[eqnFieldName].equationValue(self)
639        if newValue != oldValue:
640            self.data[eqnFieldName] = newValue
641            changed = True
642            for fieldRef in treeFormats.mathFieldRefDict.get(eqnFieldName, []):
643                for node in fieldRef.dependentEqnNodes(self):
644                    node.recalcMathField(fieldRef.eqnFieldName, treeFormats)
645        return changed
646
647    def updateNumbering(self, fieldDict, currentSequence, levelLimit,
648                        completedClones, includeRoot=True, reserveNums=True,
649                        restartSetting=False):
650        """Add auto incremented numbering to fields by type in the dict.
651
652        Arguments:
653            fieldDict -- numbering field name lists stored by type name
654            currentSequence -- a list of int for the current numbering sequence
655            levelLimit -- the number of child levels to include
656            completedClones -- set of clone nodes already numbered
657            includeRoot -- if Ture, number the current node
658            reserveNums -- if true, increment number even without num field
659            restartSetting -- if true, restart numbering after a no-field gap
660        """
661        childSequence = currentSequence[:]
662        if includeRoot:
663            for fieldName in fieldDict.get(self.formatRef.name, []):
664                self.data[fieldName] = '.'.join((repr(num) for num in
665                                                 currentSequence))
666            if self.formatRef.name in fieldDict or reserveNums:
667                childSequence += [1]
668                currentSequence[-1] += 1
669            if restartSetting and self.formatRef.name not in fieldDict:
670                currentSequence[-1] = 1
671            if len(self.spotRefs) > 1:
672                completedClones.add(self.uId)
673        if levelLimit > 0:
674            for child in self.childList:
675                if len(child.spotRefs) > 1 and child.uId in completedClones:
676                    return
677                child.updateNumbering(fieldDict, childSequence, levelLimit - 1,
678                                      completedClones, True, reserveNums,
679                                      restartSetting)
680
681    def isIdentical(self, node, checkParents=True):
682        """Return True if node format, data and descendants are identical.
683
684        Also returns False if checkParents & the nodes have parents in common.
685        Arguments:
686            node -- the node to check
687        """
688        if (self.formatRef != node.formatRef or
689            len(self.childList) != len(node.childList) or
690            self.data != node.data or
691            (checkParents and not self.parents().isdisjoint(node.parents()))):
692            return False
693        for thisChild, otherChild in zip(self.childList, node.childList):
694            if not thisChild.isIdentical(otherChild, False):
695                return False
696        return True
697
698    def flatChildCategory(self, origFormats, structure):
699        """Collapse descendant nodes by merging fields.
700
701        Overwrites data in any fields with the same name.
702        Arguments:
703            origFormats -- copy of tree formats before any changes
704            structure -- a ref to the tree structure
705        """
706        thisSpot = self.spotByNumber(0)
707        newChildList = []
708        for spot in thisSpot.spotDescendantOnlyGen():
709            if not spot.nodeRef.childList:
710                oldParentSpot = spot.parentSpot
711                while oldParentSpot != thisSpot:
712                    for field in origFormats[oldParentSpot.nodeRef.formatRef.
713                                             name].fields():
714                        data = oldParentSpot.nodeRef.data.get(field.name, '')
715                        if data:
716                            spot.nodeRef.data[field.name] = data
717                        spot.nodeRef.formatRef.addFieldIfNew(field.name,
718                                                            field.formatData())
719                    oldParentSpot = oldParentSpot.parentSpot
720                spot.parentSpot = thisSpot
721                newChildList.append(spot.nodeRef)
722            else:
723                structure.removeNodeDictRef(spot.nodeRef)
724        self.childList = newChildList
725
726    def addChildCategory(self, catList, structure):
727        """Insert category nodes above children.
728
729        Arguments:
730            catList -- the field names to add to the new level
731            structure -- a ref to the tree structure
732        """
733        newFormat = None
734        catSet = set(catList)
735        similarFormats = [nodeFormat for nodeFormat in
736                          structure.treeFormats.values() if
737                          catSet.issubset(set(nodeFormat.fieldNames()))]
738        if similarFormats:
739            similarFormat = min(similarFormats, key=lambda f: len(f.fieldDict))
740            if len(similarFormat.fieldDict) < len(self.childList[0].
741                                                  formatRef.fieldDict):
742                newFormat = similarFormat
743        if not newFormat:
744            newFormatName = '{0}_TYPE'.format(catList[0].upper())
745            num = 1
746            while newFormatName in structure.treeFormats:
747                newFormatName = '{0}_TYPE_{1}'.format(catList[0].upper(), num)
748                num += 1
749            newFormat = nodeformat.NodeFormat(newFormatName,
750                                              structure.treeFormats)
751            newFormat.addFieldList(catList, True, True)
752            structure.treeFormats[newFormatName] = newFormat
753        newParents = []
754        for child in self.childList:
755            newParent = child.findEqualFields(catList, newParents)
756            if not newParent:
757                newParent = TreeNode(newFormat)
758                for field in catList:
759                    data = child.data.get(field, '')
760                    if data:
761                        newParent.data[field] = data
762                structure.addNodeDictRef(newParent)
763                newParents.append(newParent)
764            newParent.childList.append(child)
765        self.childList = newParents
766        for child in self.childList:
767            child.removeInvalidSpotRefs(True, True)
768            child.addSpotRef(self)
769
770    def findEqualFields(self, fieldNames, nodes):
771        """Return first node in nodes with same data in fieldNames as self.
772
773        Arguments:
774            fieldNames -- the list of fields to check
775            nodes -- the nodes to search for a match
776        """
777        for node in nodes:
778            for field in fieldNames:
779                if self.data.get(field, '') != node.data.get(field, ''):
780                    break
781            else:   # this for loop didn't hit break, so we have a match
782                return node
783
784    def exportTitleText(self, level=0):
785        """Return a list of tabbed title lines for this node and descendants.
786
787        Arguments:
788            level -- indicates the indent level needed
789        """
790        textList = ['\t' * level + self.title()]
791        for child in self.childList:
792            textList.extend(child.exportTitleText(level + 1))
793        return textList
794