scan4dups.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#!/bin/py 
 
import sys
import re
 
class node(dict):
    name=""
    parent=None
 
# Top of tree: 
top=node()
 
def name2leaf(ending):
    rv=""
    p=ending
    while p is not None:
        rv=p.name+" "+rv
        p=p.parent
    return rv
 
try:
    while True:
        line=sys.stdin.next()
        # print "((%s))"%line 
        startpos=0
        ptr=top
        dupsfound=[]
        lastAdded=None
        while True:
            m=re.match("\s*<(\w+)>",line[startpos:])
            if not m:
                break
            word=m.group(1)
            # print "found word: %s"%word 
            # Now, there is a prefix conflict if: (a) I am about to add an 
            # element to an otherwise empty (i.e. terminal) directory (a 
            # leaf), or (b) At the end of this element, the dictionary I 
            # end on is *not* empty (i.e. NOT a leaf).  We check (a) here, 
            # and (b) after the loop. 
            # 
            # Waitasec, it's okay if I'm adding to a leaf *if I just added 
            # that leaf*! 
            if not ptr.keys() and ptr!=lastAdded and ptr!=top:
                dupsfound.append(name2leaf(ptr))
            try:
                next=ptr[word]
            except KeyError:
                next=node()
                next.parent=ptr
                next.name=word
                lastAdded=next
                ptr[word]=next
            ptr=next
            startpos+=m.end()
        if startpos!=0:                 # Skip if the line had nothing. 
            if ptr.keys():              # Dup if the end is NOT a leaf. 
                # By rights I should follow each other key all the way 
                # down to all its possible ends.  Too much work.  But 
                # I will go one more down, OK? 
                for other in ptr.keys():
                    dupsfound.append(name2leaf(ptr[other])+"(+?)")
                    # The (+?) is because there might be more after that. 
            mystring=name2leaf(ptr)
            # print "processed: (%s)"%mystring 
            for i in dupsfound:
                print "Prefix conflict found: (%s) vs (%s)"%(mystring, i)
except StopIteration:
    print "hit end"
    pass
print "Done."