View Javadoc

1   /* Taken 2008 from Limewire -project under the following terms: 
2    *
3    * This program is free software: you can redistribute it and/or modify
4    * it under the terms of the GNU General Public License as published by
5    * the Free Software Foundation, either version 3 of the License, or
6    * (at your option) any later version.
7    *
8    * This program is distributed in the hope that it will be useful,
9    * but WITHOUT ANY WARRANTY; without even the implied warranty of
10   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11   * GNU General Public License for more details.
12   *
13   * You should have received a copy of the GNU General Public License
14   * along with this program.  If not, see <http://www.gnu.org/licenses/>.
15   */
16  package net.sf.eos.trie;
17  
18  import net.sf.eos.trie.PatriciaTrie.KeyAnalyzer;
19  
20  /**
21   * Analyzes <code>CharSequence</code> keys with case sensitivity. With 
22   * <code>CharSequenceKeyAnalyzer</code> you can
23   * compare, check prefix, and determine the index of a bit.
24   * <p>
25   * A typical use case for a <code>CharSequenceKeyAnalyzer</code> is with a 
26   * {@link PatriciaTrie}.
27   * <pre>
28      PatriciaTrie&lt;String, String&gt; trie = new PatriciaTrie&lt;String, String&gt;(new CharSequenceKeyAnalyzer());
29      
30      trie.put("Lime", "Lime");
31      trie.put("LimeWire", "LimeWire");
32      trie.put("LimeRadio", "LimeRadio");
33      trie.put("Lax", "Lax");
34      trie.put("Lake", "Lake");
35      trie.put("Lovely", "Lovely");
36  
37      System.out.println(trie.select("Lo"));
38      System.out.println(trie.select("Lime"));
39  
40      System.out.println(trie.getPrefixedBy("La").toString());            
41  
42      Output:
43          Lovely
44          Lime
45          {Lake=Lake, Lax=Lax}
46  
47   * </pre>
48   * <p><strong>Note:</strong> Taken from 
49   * <a href='http://www.limewire.org/'>Limewire</a> sourcecode and repackaged by
50   * Sascha Kohlmann.</p>
51   */
52  public class CharSequenceKeyAnalyzer implements KeyAnalyzer<CharSequence> {
53      
54      private static final long serialVersionUID = -7032449491269434877L;
55      
56      private static final int[] BITS = createIntBitMask(16);
57      
58      public static final int[] createIntBitMask(int bitCount) {
59          int[] bits = new int[bitCount];
60          for(int i = 0; i < bitCount; i++) {
61              bits[i] = 1 << (bitCount - i - 1);
62          }
63          return bits;
64      } 
65      public int length(CharSequence key) {
66          return (key != null ? key.length() * 16 : 0);
67      }
68      
69      public int bitIndex(CharSequence key,   int keyOff, int keyLength,
70                          CharSequence found, int foundOff, int foundKeyLength) {
71          boolean allNull = true;
72          
73          if(keyOff % 16 != 0 || foundOff % 16 != 0 ||
74             keyLength % 16 != 0 || foundKeyLength % 16 != 0)
75              throw new IllegalArgumentException("offsets & lengths must be at "
76                                                 + "character boundaries");
77          
78          int off1 = keyOff / 16;
79          int off2 = foundOff / 16;
80          int len1 = keyLength / 16 + off1;
81          int len2 = foundKeyLength / 16 + off2;
82          int length = Math.max(len1, len2);
83          
84          // Look at each character, and if they're different
85          // then figure out which bit makes the difference
86          // and return it.
87          char k = 0, f = 0;
88          for(int i = 0; i < length; i++) {
89              int kOff = i + off1;
90              int fOff = i + off2;
91              
92              if(kOff >= len1)
93                  k = 0;
94              else
95                  k = key.charAt(kOff);
96              
97              if(found == null || fOff >= len2)
98                  f = 0;
99              else
100                 f = found.charAt(fOff);
101             
102             if(k != f) {
103                int x = k ^ f;
104                return i * 16 + (Integer.numberOfLeadingZeros(x) - 16);
105             }
106             
107             if(k != 0)
108                 allNull = false;
109             
110         }
111         
112         if (allNull) {
113             return KeyAnalyzer.NULL_BIT_KEY;
114         }
115         
116         return KeyAnalyzer.EQUAL_BIT_KEY;
117     }
118 
119     public boolean isBitSet(CharSequence key, int keyLength, int bitIndex) {
120         if (key == null || bitIndex >= keyLength) {
121             return false;
122         }
123         
124         int index = bitIndex / BITS.length;
125         int bit = bitIndex - index * BITS.length;
126         return (key.charAt(index) & BITS[bit]) != 0;
127     }
128 
129     public int compare(CharSequence o1, CharSequence o2) {
130         return o1.toString().compareTo(o2.toString());
131     }
132 
133     public int bitsPerElement() {
134         return 16;
135     }
136 
137     public boolean isPrefix(CharSequence prefix, int offset, int length, CharSequence key) {
138         if(offset % 16 != 0 || length % 16 != 0)
139             throw new IllegalArgumentException("Cannot determine prefix outside of character boundaries");
140         String s1 = prefix.subSequence(offset / 16, length / 16).toString();
141         String s2 = key.toString();
142         return s2.startsWith(s1);
143     }
144 }
145