Mailing-List: contact java-dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: java-dev@lucene.apache.org
Received-SPF: pass (hermes.apache.org: domain of jak-lucene-dev@m.gmane.org
 designates 80.91.229.2 as permitted sender)
To: java-dev@lucene.apache.org
From: Chris Nokleberg <chris@sixlegs.com>
Subject: Re: svn-commit: 168449 FSDirectory
Date: Tue, 07 Jun 2005 11:52:43 -0700
Lines: 90
Message-ID: <pan.2005.06.07.18.52.39.530143@sixlegs.com>
References: <42A486EB.1070803@apache.org> <42A499CB.2090209@apache.org>
 <42A54906.5050103@apache.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
User-Agent: Pan/0.14.2 (This is not a psychotic episode. It's a cleansing
 moment of clarity.)
Sender: news <news@sea.gmane.org>

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