lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Chris Nokleberg <ch...@sixlegs.com>
Subject Re: svn-commit: 168449 FSDirectory
Date Tue, 07 Jun 2005 18:52:43 GMT
On Tue, 07 Jun 2005 09:13:10 +0200, Bernhard Messer wrote:
> exactly, that's what i had in mind. I know that we have to allocate a 
> new string object for every call, but this must be much cheaper than the 
> current implementation which has to walk thru the whole array every time 
> the method is called.

If you're still concerned about performance you can use a "trie" data
structure, which takes a little effort to build but can match very quickly
(with no allocations). I've attached an example implementation that works
for filename extensions which only use the letters 'a'-'z' (minimally
tested):

  private static final ExtensionMatcher MATCHER = 
    new ExtensionMatcher(new String[]{
      "cfs", "fnm", "fdx", "fdt", "tii",
      "tis", "frq", "prx", "del", "tvx",
      "tvd", "tvf", "tvp",
    });

  MATCHER.match("foo.cfs"); // returns true

BTW, I think it is a bad idea to have FILENAME_EXTENSIONS as a public
array. It being final does not prevent code from changing the contents of
the array. If the extensions must be public I would recommend either an
accessor that returns a copy of the array, or an unmodifiable
collection/set/list.

Chris

////////////////////////////////////////////////////////////////////////

import java.util.*;

public class ExtensionMatcher
{
    private Object[] tree;
    
    public ExtensionMatcher(String[] exts)
    {
        tree = create(Arrays.asList(exts), 0);
    }

    private static Object[] create(List exts, int index)
    {
        Object[] array = new Object[27];
        Map byLetter = new HashMap();
        for (Iterator it = exts.iterator(); it.hasNext();) {
            String ext = (String)it.next();
            int length = ext.length();
            if (length > index) {
                Character c = new Character(ext.charAt(length - 1 - index));
                List list = (List)byLetter.get(c);
                if (list == null)
                    byLetter.put(c, list = new ArrayList());
                list.add(ext);
            } else if (length == index) {
                array[26] = Boolean.TRUE;
            }
        }
        for (Iterator it = byLetter.keySet().iterator(); it.hasNext();) {
            Character c = (Character)it.next();
            char val = c.charValue();
            if (val < 'a' || val > 'z')
                throw new IllegalArgumentException("Extension must be between 'a' and 'z'");
            array[val - 'a'] = create((List)byLetter.get(c), index + 1);
        }
        return array;
    }

    public boolean match(String file)
    {
        int index = 0;
        int length = file.length();
        Object[] array = tree;
        for (;;) {
            if (index >= length)
                return false;
            char val = file.charAt(length - 1 - index);
            if (val == '.' && array[26] != null)
                return true;
            if (val < 'a' || val > 'z')
                return false;
            array = (Object[])array[val - 'a'];
            if (array == null)
                return false;
            index++;
        }
    }
}



---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message