Advanced Autocompletion where QCompleter might not cut it

[chezifresh]

I'm looking for some suggestions on how to implement autocomplete on several different datasets. I'm looking to implement something like what Google Chrome has. You type a word into the location bar and it autocompletes on your bookmarks, recently visited sites, and commonly searched for terms. (see the attached image)

autocomplete-chrome.png

The difference is, I'm doing this for a directory browser. So I need to complete on these 3 datasets

1. recently visited directory paths
2. bookmarked directory paths
3. bookmark names

I can figure out the ui side of things, creating a drop down with bold matching text, etc. I was hoping I could find a wise Qt smith to spark some ideas on how to implement matching side of things... even better if it can be done in a bg thread to avoid locking up the rest of the ui. There's nothing more annoying than interrupting the user when they're typing

[wysota]

I guess it all boils down to having some kind of index to search the information in. It seems the datasets you want can easily be indexed. If all you want is static text search then you can build a tree of substrings that point to your items. When the user types a character, you go one step down the tree with all possible matches being stored in the current node. It requires quite much memory to hold such an index and possibly quite some time to build it but then searching through the tree is instantaneous. Other than that, QCompleter does more or less what you want (a simple filter proxy model is also sufficient) Finding matches will be slower though. If you want patterns then you have to search through all possible entries every time the user changes the search string. Since the collection is read-only, you can use threads to traverse the list faster.

[chezifresh]

I wrote a pretty dumbed down completer in a bg thread that suits my purposes. The dataset I'm looking through is going to be mighty small so the naiive algorithm I'm using will work fine. If I had a larger dataset I would probably need to do like you said and create an indexed search. It's also possible to take the dataset, break it up into a bunch of smaller pieces and fire it off to other threads to crunch the comparisons. Here's the initial version in all of its glory in PyQt. (the line edit has an instance of the thread and there's plenty of special logic for displaying my own completion popup)

class QdCompletionThread(QtCore.QThread):
    def __init__(self, parent=None):
        QtCore.QThread.__init__(self, parent)
        self.directory = QtCore.QDir.root()
        self._dir_expr = re.compile(unicode("^" + self.directory.path() + ".*"))
 
 
        self.text = ""
        self.directory_history = []
        self.bookmarks = {}
 
 
    def match(self, text):
        self.text = text
        self.start()
 
 
    #
    # Pre-Populating the Gatherer
    #
 
 
    def setDirectoryHistory(self, directories):
        """Sets the history the completer can pull from"""
        self.directory_history = set(directories)
 
 
    def setBookmarks(self, bookmark_dict):
        """Sets the bookmarks the completer can pull from, names and directories"""
        self.bookmarks = bookmark_dict.copy()
 
 
    #
    # Synchronous Matching Methods
    #
 
 
    def getDirectoryMatches(self, text):
        """Returns the directory matches based on text"""
        text = unicode(text)
        if text.endswith(os.sep):
            clean_path = text
            parent_dir = text
            match_name = ""
        else:
            clean_path = unicode(QtCore.QDir.cleanPath(text))
            parent_dir = os.path.dirname(clean_path)
            match_name = os.path.basename(clean_path)
 
 
        # check that the directory exists or is readable
        if not self.directory.cd(parent_dir):
            return []
 
 
        matches = self.directory.entryList([match_name + "*"],
                                           QtCore.QDir.Dirs | QtCore.QDir.NoDotAndDotDot)
        return [os.path.join(parent_dir, unicode(match)) for match in matches]
 
 
    def getMatches(self, text):
        """Returns all of the matches based on the history, bookmarks and directories"""
        matches = set()
 
 
        # check if it matches any directories
        if self._dir_expr.match(text):
            matches.update(self.getDirectoryMatches(text))
 
 
        directories = self.directory_history.copy()
        directories.update(self.bookmarks.values())
 
 
        # check known directory names and parts
        for directory in directories:
            if text in directory:
                matches.add(directory)
 
 
        # check bookmark names
        for bookmark_name in self.bookmarks:
            if text in bookmark_name:
                matches.add(bookmark_name)
 
 
        return list(sorted(matches))
 
 
    #
    # Overloaded Qt Methods
    #
 
 
    def run(self):
        text = unicode(self.text)
        matches = self.getMatches(text)
 
 
        if text != self.text:
            # the text has changed since the thread has started
            self.run()
            return
 
 
        self.emit(SIGNAL("matched(QString, QStringList)"), text, matches)

class QdCompletionThread(QtCore.QThread):
    def __init__(self, parent=None):
        QtCore.QThread.__init__(self, parent)
        self.directory = QtCore.QDir.root()
        self._dir_expr = re.compile(unicode("^" + self.directory.path() + ".*"))


        self.text = ""
        self.directory_history = []
        self.bookmarks = {}


    def match(self, text):
        self.text = text
        self.start()


    #
    # Pre-Populating the Gatherer
    #


    def setDirectoryHistory(self, directories):
        """Sets the history the completer can pull from"""
        self.directory_history = set(directories)


    def setBookmarks(self, bookmark_dict):
        """Sets the bookmarks the completer can pull from, names and directories"""
        self.bookmarks = bookmark_dict.copy()


    #
    # Synchronous Matching Methods
    #


    def getDirectoryMatches(self, text):
        """Returns the directory matches based on text"""
        text = unicode(text)
        if text.endswith(os.sep):
            clean_path = text
            parent_dir = text
            match_name = ""
        else:
            clean_path = unicode(QtCore.QDir.cleanPath(text))
            parent_dir = os.path.dirname(clean_path)
            match_name = os.path.basename(clean_path)


        # check that the directory exists or is readable
        if not self.directory.cd(parent_dir):
            return []


        matches = self.directory.entryList([match_name + "*"],
                                           QtCore.QDir.Dirs | QtCore.QDir.NoDotAndDotDot)
        return [os.path.join(parent_dir, unicode(match)) for match in matches]


    def getMatches(self, text):
        """Returns all of the matches based on the history, bookmarks and directories"""
        matches = set()


        # check if it matches any directories
        if self._dir_expr.match(text):
            matches.update(self.getDirectoryMatches(text))


        directories = self.directory_history.copy()
        directories.update(self.bookmarks.values())


        # check known directory names and parts
        for directory in directories:
            if text in directory:
                matches.add(directory)


        # check bookmark names
        for bookmark_name in self.bookmarks:
            if text in bookmark_name:
                matches.add(bookmark_name)


        return list(sorted(matches))


    #
    # Overloaded Qt Methods
    #


    def run(self):
        text = unicode(self.text)
        matches = self.getMatches(text)


        if text != self.text:
            # the text has changed since the thread has started
            self.run()
            return


        self.emit(SIGNAL("matched(QString, QStringList)"), text, matches)

To copy to clipboard, switch view to plain text mode 

[chezifresh]

Here's a shot in the dark... I'm trying to see if I can do the following with a QCompleter

if I type 'Desktop', I want the completer to display whatever I found in my thread from my last post... ie

/home/foo/Desktop/
/home/foo/Desktop/photos/
/home/foo/Desktop/photos/vacation/
/home/bar/Desktop/notes/

A stock QCompleter seems to only recognize those results if I type "/home/foo/Desktop". The entire completion prefix needs to be in place. If there's no way to get a QCompleter to do this, it means I have to essentially copy a bunch of functionality from QCompleter, like the event filter it does. And man would that stink. Any ideas on how to tell the QCompleter to display what I tell it to?

---

Added after 4 minutes:

Answering my own question 5 mins later:

completer.setCompletionMode(QtGui.QCompleter.UnfilteredPopupCompletion)

completer.setCompletionMode(QtGui.QCompleter.UnfilteredPopupCompletion)

To copy to clipboard, switch view to plain text mode 

This will show everything in the completion model and still do all the event filtering for me. There's probably still some details, like selecting the best match or at least the first one in the list while the user is typing. But this will do