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\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.