multidimensional list remove duplicates only for that level-CodePudding

I am trying to build a treeview of crates from a program called Serato, how they build their crates in their program is by the files in a folder, however the issue is that you can have multiple internal and external hard drives with folders carrying the same names, also sub folders can also have the same name as the previous parent folder.

For example a folder can look like this;

C:/Music%%House.crate
C:/Music%%House%%Chicago.crate
C:/Music%%House%%Garage.crate
C:/Music%%Hip-Hop%%Classic.crate
C:/Music%%Hip-Hop%%Remixes.crate
C:/Music%%Hip-Hop%%New.crate
C:/Music%%House%%Hip-Hop%%House Remixes.crate
C:/Videos%%House.crate
C:/Videos%%House%%Chicago.crate
C:/House%%Unsorted.crate
Hip-Hop%%Unsorted.crate
C:/Hip-Hop%%Wedding.crate

As you can see nested inside are crates with the same name as children. Now I can have another folder on another drive, identical but maybe with another added folder like;

D:/Music%%House.crate
D:/Music%%House%%Chicago.crate
D:/Music%%House%%Garage.crate
D:/Music%%Hip-Hop%%Classic.crate
D:/Music%%Hip-Hop%%Remixes.crate
D:/Music%%Hip-Hop%%New.crate
D:/Music%%Hip-Hop%%Transitions.crate
D:/Music%%House%%Hip-Hop%%House Remixes.crate
D:/Videos%%House.crate
D:/Videos%%House%%Chicago.crate
D:/House%%Unsorted.crate
D:/Hip-Hop%%Unsorted.crate
D:/Hip-Hop%%Wedding.crate

What I need to do is get this in a WPF treeview to look like this;

Hip-Hop
--Unsorted
--Wedding
House
--Unsorted
Music
--House
----Chichago
----Garage
----Hip-Hop
------House Remixes
--Hip-Hop
----Classic
----Remixes
----New
Videos
--House
----Chicago

Path strings look like this:

C:/Music%%House%%Hip-Hop%%House Remixes.crate

Here lies my problem I don't know where to begin to populate the custom list in order to add these avoiding duplicate names in certain levels of children, but retain and add the volume to the custom list.Hopefully I explained this well, I am a beginner at this.

Updated with Bionic Code's Answer, still getting an error.

public class FileSystemItem : IEquatable<FileSystemItem>
{
  public FileSystemItem(string name, FileSystemItem parent)
  {
    this.Name = name;
    this.Parent = parent;
    this.Children = new List<FileSystemItem>();
    this.Volumes = new List<DriveInfo>();
  }

  public string Name { get; }
  public FileSystemItem Parent { get; }
  public IList<FileSystemItem> Children { get; }
  public IList<DriveInfo> Volumes { get; }

  public bool Equals(FileSystemItem? other) => (this.Name, this.Parent).Equals((other.Name, other.Parent));
}





if (patsh.Count > 0)
{


    var treeLevelIndex = new List<Dictionary<string, FileSystemItem>>();

    foreach (string path in paths)
    {
       FileSystemItem parentFileSystemItem = null;
                    int level = 0;

       string pathRoot = Path.GetPathRoot(path);
       DriveInfo drive = new DriveInfo(pathRoot);
       string pathWithoutRoot = path.Substring(drive.Name.Length);

       foreach (string directoryName in pathWithoutRoot.Split(new char[] { '%', '%' }, StringSplitOptions.RemoveEmptyEntries))
       {
            
          if (treeLevelIndex.Count == level)
          {
             treeLevelIndex.Add(new Dictionary<string, FileSystemItem>());
          }

          var levelIndex = treeLevelIndex[level];

          // Check if path segment already exists (merge)
          if (levelIndex.TryGetValue(directoryName, out FileSystemItem indexedParent))
          {
             // Don't add duplicates
             if (!indexedParent.Volumes.Any(volume => volume.Name.Equals(drive.Name, StringComparison.Ordinal)))
             {
                 indexedParent.Volumes.Add(drive);
             }

             parentFileSystemItem = indexedParent;
             level  ;
             continue;
          }

          /* Create index entry for the current level */

          var childFileSystemItem = new FileSystemItem(Path.GetFileNameWithoutExtension(directoryName), parentFileSystemItem);
          childFileSystemItem.Volumes.Add(drive);

          // Tree leaf. Don't add duplicates. 
          // Does not need to be indexed as it will not hold child nodes.
          if (Path.HasExtension(directoryName))
          {
             if (!parentFileSystemItem?.Children.Contains(childFileSystemItem) ?? false)
             {
                parentFileSystemItem.Children.Add(childFileSystemItem);
             }
          }
          else // An unindexed tree node.
          {
              parentFileSystemItem?.Children.Add(childFileSystemItem);
                            
           // THIS IS WHERE THE EXPECTION UNHANDLED breaks at (below)                                
              levelIndex.Add(childFileSystemItem.Name, childFileSystemItem);
              parentFileSystemItem = childFileSystemItem;
          }
          level  ;
      }
  }

  List<FileSystemItem> treeViewSource = treeLevelIndex.First().Values.ToList();
                
               

  TvCrates.ItemsSource = treeViewSource;

}

As shown in remarks above the error occurs in this area;

else // An unindexed tree node.
{
    parentFileSystemItem?.Children.Add(childFileSystemItem);
                                         
    levelIndex.Add(childFileSystemItem.Name, childFileSystemItem);
    parentFileSystemItem = childFileSystemItem;
}
level  ;

levelIndex.Add(childFileSystemItem.Name, childFileSystemItem);

With the error:

System.ArgumentException: 'An item with the same key has already been added.'

Here is an actual listing of the paths: https://textdoc.co/FeDXHjp5d73ayThg

CodePudding user response：

You just have to build the tree level by level, starting from the root (and not the leaf). You must start from the drive name. Then use Dictionary as lookup table to efficiently identify and merge duplicates.

To identify the duplicates, it is essential to let the data model implement IEquatable. Alternatively implement a custom IEqualityComparer:

public class FileSystemItem : IEquatable<FileSystemItem>
{
  public FileSystemItem(string name, FileSystemItem parent)
  {
    this.Name = name;
    this.Parent = parent;
    this.Children = new List<FileSystemItem>();
    this.Volumes = new List<DriveInfo>();
  }

  public string Name { get; }
  public FileSystemItem Parent { get; }
  public IList<FileSystemItem> Children { get; }
  public IList<DriveInfo> Volumes { get; }

  public bool Equals(FileSystemItem? other) => (this.Name, this.Parent).Equals((other.Name, other.Parent));
}

The algorithm to build the tree is also very simple. This is a free example:

private const string NodeSeparator = "%%";

// Your input 
var paths = new List<string>();

// The list of lookup tables which is also the flattened tree structure. 
// Each tree level is equivalent to a path segment (directory).
// Each level has its own lookup table to allow the same name on each level.       
var treeLevelIndex = new List<Dictionary<string, FileSystemItem>>();
      
foreach (string path in paths)
{
  FileSystemItem parentFileSystemItem = null;
  int level = 0;

  string pathRoot = Path.GetPathRoot(path);
  DriveInfo drive = new DriveInfo(pathRoot);
  string pathWithoutRoot = path.Substring(drive.Name.Length);

  foreach (string directoryName in pathWithoutRoot.Split(NodeSeparator, StringSplitOptions.RemoveEmptyEntries))
  {
    if (treeLevelIndex.Count == level)
    {
      treeLevelIndex.Add(new Dictionary<string, FileSystemItem>());
    }

    var levelIndex = treeLevelIndex[level];

    // Check if path segment already exists (merge)
    if (levelIndex.TryGetValue(directoryName, out FileSystemItem indexedParent))
    {
      // Don't add duplicates
      if (!indexedParent.Volumes.Any(volume => volume.Name.Equals(drive.Name, StringComparison.Ordinal)))
      {
        indexedParent.Volumes.Add(drive);
      }

      parentFileSystemItem = indexedParent;
      level  ;
      continue;
    }

    /* Create index entry for the current level */

    var pathWithoutExtension = Path.GetFileNameWithoutExtension(directoryName);
    var childFileSystemItem = new FileSystemItem(pathWithoutExtension, parentFileSystemItem);
    childFileSystemItem.Volumes.Add(drive);

    // Tree leaf. Don't add duplicates. 
    // Does not need to be indexed as it will not hold child nodes.
    if (Path.HasExtension(directoryName))
    {
      if (!parentFileSystemItem?.Children.Contains(childFileSystemItem) ?? false)
      {
        parentFileSystemItem.Children.Add(childFileSystemItem);
      }
    }
    else // An unindexed tree node.
    {
      parentFileSystemItem?.Children.Add(childFileSystemItem);
      levelIndex.Add(directoryName, childFileSystemItem);
      parentFileSystemItem = childFileSystemItem;
    }
    level  ;
  }
}

List<FileSystemItem> treeViewSource = treeLevelIndex.First().Values.ToList();

MainWindow.xaml

<TreeView>
  <TreeView.ItemTemplate>
    <HierarchicalDataTemplate DataType="{x:Type local:FileSystemItem}"
                              ItemsSource="{Binding Children}">
      <TextBlcok Text="{Binding Name}" />
    </HierarchicalDataTemplate>
  </TreeView.ItemTemplate>
</TreeView>