当前位置: 动力学知识库 > 问答 > 编程问答 >

java - How to find duplicate child nodes having more than one parent in a file system?

问题描述:

In a custom made, in memory file system my files and directories are in the form of a tree where the directories have references to the child nodes which can be either a directory or a file.

I can do add , remove, delete , move operation over the files and directories. Now due to a bug somehow whenever a file is moved from a parent node to another parent node its reference is not removed from the earlier parent node.

Example

D1 (parent ) C1 ( child )

after move

D1 (parent ) C1 (child)

D2 (parent ) C1 (child)

Question:

Now the question is what is the most optimal way to find out all such files , which have duplicate parents ? Right now I am keeping all the file references in a global hashset , which guess will be a pain if I have a huge set of files ?

Note: : Parent is aware of all its children but a child is not aware of its parent.

Approach taken so far: The approach I am thinking of is to first traverse though the whole directory structure and then keep all the file references in a hashset and before inserting any value to the hashset I will check if it already exists, if yes then this is a corrupt file having duplicate parent nodes .

import java.io.File;

import java.util.HashSet;

import java.util.Set;

public class RecursiveFiles {

private static Set<File> set = new HashSet<File>();

public static void main(String[] args) {

File root = new File("C:\\Windows\\Help");

showFiles(root);

}

private static void showFiles(File root) {

if(root.isDirectory()){

File[] children = root.listFiles();

for(File child : children){

showFiles(child);

}

}else {

if(set.contains(root)){

System.out.println("Duplicate File " + root);

}else {

set.add(root);

}

}

}

}

网友答案:

If think of files as nodes and parenthood as edges then you can use bfs/dfs algorithms but with a little change, instead of a boolean visited state, use a list of visited for each node, and in the list keep all the parent address that visited this node. Also consider that your graph is a direct graph so no one can visit his parent.

分享给朋友:
您可能感兴趣的文章:
随机阅读: