从 [parentid, name] 目录字典到完整路径字典

Question

我有一个目录字典 [parentid, name] 是这样的：

D = {0: [-1, 'C:'],
     1: [0, 'BLAH'], 
     2: [0, 'TEMP'], 
     3: [1, 'BOOO'], 
     4: [1, 'AZAZ'], 
     5: [2, 'ABCD']}

我想从这里转到完整路径：

FULLPATHS = {}
for key, path in D.iteritems():
    newpath = path[1]
    if path[0] != -1:
         newpath = FULLPATHS[path[0]] + '\' + newpath
    FULLPATHS[key] = newpath

有效：

 {0: 'C:', 1: 'C:\BLAH', 2: 'C:\TEMP', 3: 'C:\BLAH\BOOO', 4: 'C:\BLAH\AZAZ', 5: 'C:\TEMP\ABCD'}

但是如果键是非递增的目录 ID，那么棘手的部分就来了：

 D = {0: [-1, 'C:'],
     7: [0, 'TEMP'], 
     3: [122, 'BOOO'], 
     4: [122, 'AZAZ'], 
     5: [7, 'ABCD'],
     122: [0, 'BLAH']}

在 NTFS MasterFileTable（我正在阅读）中它经常是这样的。

想法可以是："When arriving on 3: [122, 'BOOO'], let's wait and postpone this one for later, once dir #122 will be processed later"。但这将需要许多连续的循环以确保一切都正确完成。

如何从 [parentid, name] 目录方案到完整路径？

注意：这个问题不是 Python 特有的，所以我不是在寻找 os.path 解决方案，而是一个普遍的问题。

Answer 1

一种可能性：对于每个元素都沿着链向上移动，直到到达根。

FULLPATHS=dict()
for k in D:
    parent = D[k][0]
    chain = [ D[k][1] ]
    while parent != -1: # here I assume root's parent is always -1
        chain.append(D[parent][1])
        parent = D[parent][0]
    FULLPATHS[k] = '\'.join(reversed(chain))

甚至，利用已经创建的前缀路径：

FULLPATHS = { 0: 'C:' }
for k in D:
    i = k
    chain = []
    while i not in FULLPATHS:
        chain.append(D[i][1])
            i = D[i][0]
    FULLPATHS[k] = '\'.join([FULLPATHS[i]] + list(reversed(chain)))

print(FULLPATHS)

Answer 2

我正在尝试这样的解决方案：如果 parent 尚未 "full-path-ed"，请先执行一次，一劳永逸！

FULLPATHS = {0: 'C:'}

def do(id):
    parentid = D[id][0]
    name = D[id][1]
    if id not in FULLPATHS:
        if parentid not in FULLPATHS:
            do(parentid)
        FULLPATHS[id] = FULLPATHS[parentid] + '\' + name

for k, v in D.iteritems():
    do(k)

print FULLPATHS  

#{0: 'C:', 3: 'C:\BLAH\BOOO', 4: 'C:\BLAH\AZAZ', 5: 'C:\TEMP\ABCD', 7: 'C:\TEMP', 122: 'C:\BLAH'}

从 [parentid, name] 目录字典到完整路径字典

From [parentid, name] directory dict to full paths dict

python

filesystems

dictionary

path