Wow, that's extremely helpful!! I happen to particularly enjoy tries, so the suffix trie sounds like a great idea. The trie class example is really helpful too, because this will be my first time programming in Python, and it's a bit easier to figure out what's going on syntax-wise in that simple trie class than in the middle of the portage source code!
Seriously, thanks again :] On Sun, Nov 23, 2008 at 11:56 AM, Lucian Poston <[EMAIL PROTECTED]>wrote: > > Thanks for the replies! I know there are a couple programs out there that > > basically already do what I'm looking to do... Unfortunately I wasn't > aware > > of these pre-existing utilities until after I submitted my project > proposal > > to my professor. So, I'm looking to implement a better search myself. > > Preferably by editing the existing portage code, not writing a separate > > program. So if anyone can offer any help regarding the actual > implementation > > of search in portage, I would greatly appreciate it! > > Most of the search implementation is in > /usr/lib/portage/pym/_emerge/__init__.py in class search. The class's > execute() method simply iterates over all packages (and descriptions > and package sets) and matches against the searchkey. You might need > to look into pym/portage/dbapi/porttree.py for portdbapi as well. > > If you intend to index and support fast regex lookup, then you need to > do some fancy indexing, which I'm not terribly familiar with. You > could follow in the steps of eix[1] or other indexed search utilities > and design some sort of index layout, which is easier than the > following thought. You might consider implementing a suffix trie or > similar that has sublinear regexp lookup and marshalling the structure > for the index. I couldn't find a python implementation for something > like this, but here is a general trie class[2] that you might start > with if you go that route. There is a perl module[3], > Tie::Hash::Regex, that does that, but properly implementing that in > python would be a chore. :) > > That project sounds interesting and fun. Good luck! > > Lucian Poston > > [1] https://projects.gentooexperimental.org/eix/wiki/IndexFileLayout > [2] > http://www.koders.com/python/fid7B6BC1651A9E8BBA547552FE3F039479A4DECC45.aspx > [3] > http://search.cpan.org/~davecross/Tie-Hash-Regex-1.02/lib/Tie/Hash/Regex.pm<http://search.cpan.org/%7Edavecross/Tie-Hash-Regex-1.02/lib/Tie/Hash/Regex.pm> > >
