2
\$\begingroup\$

Basic idea (foo and foa are filenames):

enter image description here

using System;
using System.Collections.Generic;
using System.IO;

namespace FileIndexer
{
    class FileIndexTrie
    {
        private class CachablePath
        {
            public string filename;
            public int cachedPath;

            //stolen from: https://stackoverflow.com/a/263416/13687491
            public override int GetHashCode()
            {
                int hash = 13;

                hash = (hash * 7) + filename.GetHashCode();
                hash = (hash * 7) + cachedPath.GetHashCode();

                return hash;
            }
            public override bool Equals(Object obj)
            {
                if (obj == null || !(obj is CachablePath))
                    return false;
                else
                    return filename.Equals(((CachablePath)obj).filename) && cachedPath == ((CachablePath)obj).cachedPath;
            }
        };

        private Dictionary<char, FileIndexTrie> nodes;
        private HashSet<CachablePath> nodeFiles;
        private static Dictionary<int, string> pathCache = new Dictionary<int, string>();

        public FileIndexTrie()
        {
            this.nodes = new Dictionary<char, FileIndexTrie>();
            this.nodeFiles = null;
        }

        public bool insert(string word, string filePath)
        {
            if (word == null || filePath == null)
                return false;

            try
            {
                insert(word, filePath, this);
            }
            catch (Exception ex)
            {
                if (ex is ArgumentException || ex is PathTooLongException)
                    Console.WriteLine("Trie: Invalid path \"" + filePath + "\", insert() failed for word:\"" + word + "\"");

                return false;
            }

            return true;
        }

        private void insert(string word, string filePath, FileIndexTrie currentNode)
        {
            if (word.Length >= 1)
            {
                if (!currentNode.nodes.ContainsKey(word[0]))
                    currentNode.nodes[word[0]] = new FileIndexTrie();

                insert(word.Substring(1), filePath, currentNode.nodes[word[0]]);
            }
            else if (word.Length == 0)
            {
                string path = Path.GetDirectoryName(filePath);
                CachablePath currentPathFilename = new CachablePath();

                if (currentNode.nodeFiles == null)
                    currentNode.nodeFiles = new HashSet<CachablePath>();

                if (!pathCache.ContainsKey(path.GetHashCode()))
                    pathCache[path.GetHashCode()] = path;

                currentPathFilename.cachedPath = path.GetHashCode();
                currentPathFilename.filename = Path.GetFileName(filePath);

                currentNode.nodeFiles.Add(currentPathFilename);
            }
        }

        public List<string> getFilepaths(string word)
        {
            if (word == null)
                return new List<string>();

            return getFilepaths(word, this);
        }

        private List<string> getFilepaths(string word, FileIndexTrie currentNode)
        {
            if (word.Length >= 1)
            {
                if (!currentNode.nodes.ContainsKey(word[0]))
                    return new List<string>();

                return getFilepaths(word.Substring(1), currentNode.nodes[word[0]]);
            }
            else if (word.Length == 0 && currentNode.nodeFiles != null)
            {
                List<string> ret = new List<string>();

                foreach (CachablePath cp in currentNode.nodeFiles)
                    ret.Add(pathCache[cp.cachedPath] + "\\" + cp.filename);

                return ret;
            }

            return new List<string>();
        }

        public List<string> getFilepathsStartsWith(string word)
        {
            List<string> ret = new List<string>();

            if (word == null)
                return ret;

            getFilepathsStartsWith(word, this, ret);

            return ret;
        }
        private void getFilepathsStartsWith(string word, FileIndexTrie currentNode, List<string> foundFilePaths)
        {
            if (word.Length > 1)
            {
                if (!currentNode.nodes.ContainsKey(word[0]))
                    return;

                getFilepathsStartsWith(word.Substring(1), currentNode.nodes[word[0]], foundFilePaths);
            }
            else if (word.Length == 1)
            {
                getAllChildrenPaths(currentNode.nodes[word[0]], foundFilePaths);
            }
        }

        private void getAllChildrenPaths(FileIndexTrie currentNode, List<string> foundFilePaths)
        {
            if (currentNode.nodeFiles != null)
                foreach (CachablePath cp in currentNode.nodeFiles)
                    foundFilePaths.Add(pathCache[cp.cachedPath] + "\\" + cp.filename);
            foreach (KeyValuePair<char, FileIndexTrie> node in currentNode.nodes)
                getAllChildrenPaths(node.Value, foundFilePaths);
        }
    }
}

I tried to create a trie to index and search for files. Every node has a Dictionary<char, FileIndexTrie> nodes which contains all the children, the key is the char which will follow next to the current one (in the string). It also contains a HashSet<CachablePath> nodeFiles which holds all the files with file path associated to the current node. I created a "cache" Dictionary<int, string> pathCache since I expect alot of paths that will repeat.

Brief Usage example:

        static void Main(string[] args)
        {
            FileIndexTrie root = new FileIndexTrie();

            root.insert("foo", @"C:\example\foo");
            root.insert("foa", @"C:\example\foa");
            root.insert("foa", @"C:\example\foa");
            root.insert("foa", @"C:\example\foa2");
            root.insert("foa2", @"C:\example\foa2");
            root.insert("foa3", @"C:\example2\foa3");
            root.insert("doa", @"C:\example3\doa moa");
            root.insert("mao", @"C:\example3\doa moa");
            root.insert("", @"C:\example\foa");
            root.insert("", @"");

            List<string> test = root.getFilepaths("fo");
            List<string> test1 = root.getFilepaths("foa");
            List<string> test2 = root.getFilepathsStartsWith("fo");
            List<string> test3 = root.getFilepathsStartsWith("d");
            List<string> test4 = root.getFilepathsStartsWith("f");
        }

.insert will index the path in the trie. .getFilepaths will look for a exact match and .getFilepathsStartsWith will look for a partial match of the string start.

Concerns:

  1. the model class CachablePath within the FileIndexTrie class. I would seperate it but it feels like this cannot be used outside of this class
  2. Does string.GetHashCode() provide a usable hashcode for this use ?
  3. private List<string> getFilepaths(string word, FileIndexTrie currentNode) method seems messy, I lost track how it works, seems like returning the List everywhere could look better
  4. performance of foreach (KeyValuePair<char, FileIndexTrie> node in currentNode.nodes)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.