DefaultWildcardMap


1   package org.jacorb.notification.util;
2   
3   /*
4    *        JacORB - a free Java ORB
5    *
6    *   Copyright (C) 1999-2004 Gerald Brose
7    *
8    *   This library is free software; you can redistribute it and/or
9    *   modify it under the terms of the GNU Library General Public
10   *   License as published by the Free Software Foundation; either
11   *   version 2 of the License, or (at your option) any later version.
12   *
13   *   This library is distributed in the hope that it will be useful,
14   *   but WITHOUT ANY WARRANTY; without even the implied warranty of
15   *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16   *   Library General Public License for more details.
17   *
18   *   You should have received a copy of the GNU Library General Public
19   *   License along with this library; if not, write to the Free
20   *   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21   *
22   */
23  
24  import java.util.ArrayList  ;
25  import java.util.List  ;
26  
27  /**
28   * @author Alphonse Bendt
29   * @version $Id: DefaultWildcardMap.java,v 1.1 2005/02/14 00:13:05 alphonse.bendt Exp $
30   */
31  
32  public class DefaultWildcardMap implements WildcardMap
33  {
34      public static final int DEFAULT_TOPLEVEL_SIZE = 4;
35  
36      private final EntryList topLevel_;
37  
38      ////////////////////////////////////////
39  
40      public DefaultWildcardMap(int topLevelSize)
41      {
42          super();
43  
44          topLevel_ = new EntryList(topLevelSize);
45      }
46  
47      public DefaultWildcardMap()
48      {
49          this(DEFAULT_TOPLEVEL_SIZE);
50      }
51  
52      ////////////////////////////////////////
53      
54      public void clear()
55      {
56          topLevel_.clear();
57      }
58  
59      public Object   remove(Object   key)
60      {
61          char[] _key = key.toString().toCharArray();
62  
63          return topLevel_.remove(_key, 0, _key.length);
64      }
65  
66      
67      public Object   put(Object   key, Object   value)
68      {
69          char[] _key = key.toString().toCharArray();
70  
71          return topLevel_.put(_key, 0, _key.length, value);
72      }
73  
74      
75      public Object   getNoExpansion(Object   key)
76      {
77          char[] _key = key.toString().toCharArray();
78  
79          return topLevel_.getSingle(_key, 0, _key.length);
80      }
81  
82     
83      public Object  [] getWithExpansion(Object   key)
84      {
85          char[] _key = key.toString().toCharArray();
86  
87          return topLevel_.getMultiple(_key, 0, _key.length);
88      }
89  
90      
91      public String   toString()
92      {
93          return topLevel_.toString();
94      }
95  }
96  
97  /**
98   * the idea for this implementation is based on extensible hashing and trie's. an EntryList maps
99   * Strings to values. common prefixes of Strings are only stored once. <br>
100  * See section 4.1.10 and section 4.2.5 in my masters thesis available at
101  * http://www.jacorb.org/docs/DAbendt-web.pdf (in german) for a broader description of what has been
102  * implemented here.
103  */
104 
105 class EntryList
106 {
107     private static final char WILDCARD_CHAR = '*';
108     private static final int DEFAULT_INITIAL_SIZE = 2;
109 
110     private PatternWrapper myPattern_;
111 
112     private final char[] key_;
113 
114     private final int start_;
115 
116     private int end_;
117 
118     private final int depth_;
119 
120     private int splitted = 0;
121 
122     private MapEntry myEntry_;
123 
124     private EntryList[] entries_;
125 
126     ////////////////////////////////////////
127     // Constructors
128 
129     EntryList(int size)
130     {
131         this(null, 0, 0, 0, null, size);
132     }
133 
134     private EntryList(char[] key, int start, int end, int depth, MapEntry value)
135     {
136         this(key, start, end, depth, value, DEFAULT_INITIAL_SIZE);
137     }
138 
139     private EntryList(char[] key, int start, int end, int depth, MapEntry entry, int size)
140     {
141         myEntry_ = entry;
142         key_ = key;
143         end_ = end;
144         start_ = start;
145         depth_ = depth;
146         entries_ = new EntryList[size];
147         initPattern(key_, start_, end_);
148     }
149 
150     ////////////////////////////////////////
151 
152     /**
153      * check if this EntryList has an Entry associated
154      */
155     private boolean hasEntry()
156     {
157         return myEntry_ != null;
158     }
159 
160     void clear()
161     {
162         entries_ = new EntryList[DEFAULT_INITIAL_SIZE];
163     }
164 
165     Object   put(char[] key, int start, int length, Object   value)
166     {
167         return put(new MapEntry(key, start, length, value));
168     }
169 
170     /**
171      * add an Entry to this List.
172      */
173     private Object   put(MapEntry entry)
174     {
175         char _first = entry.key_[0];
176 
177         ensureIndexIsAvailable(_first);
178 
179         int _idx = computeHashIndex(_first);
180 
181         if (entries_[_idx] == null)
182         {
183             entries_[_idx] = new EntryList(entry.key_, 0, entry.key_.length, 0, entry);
184             return null;
185         }
186 
187         return entries_[_idx].put(entry.key_, 0, entry.key_.length, 0, entry, false);
188     }
189 
190     Object   put(char[] key, int start, int stop, int depth, MapEntry value, boolean addLeadingStar)
191     {
192         int _insertKeyLength = stop - start;
193         int _myKeyLength = end_ - start_;
194 
195         int _prefixLength = findCommonPrefix(key, start, stop);
196 
197         if (_prefixLength == _insertKeyLength)
198         {
199             if (endsWithStar())
200             {
201                 splitEntryList(this, _prefixLength);
202             }
203 
204             Object   _old = null;
205             // overwrite
206 
207             if (myEntry_ != null)
208             {
209                 _old = myEntry_.value_;
210             }
211 
212             myEntry_ = value;
213 
214             return _old;
215         }
216         else if (_prefixLength < _myKeyLength)
217         {
218             splitEntryList(this, _prefixLength);
219 
220             boolean _addStar = false;
221 
222             if (endsWithStar())
223             {
224                 _addStar = true;
225             }
226 
227             put(key, start, stop, depth + _prefixLength, value, _addStar);
228         }
229         else
230         // (_prefixLength > _myKeyLength)
231         {
232             char _firstRemainingChar = key[start + _prefixLength];
233             ensureIndexIsAvailable(_firstRemainingChar);
234 
235             int idx = computeHashIndex(_firstRemainingChar);
236 
237             if (entries_[idx] == null)
238             {
239                 entries_[idx] = new EntryList(key, start + _prefixLength, stop, depth_
240                         + _prefixLength, value);
241 
242                 if (addLeadingStar)
243                 {
244                     entries_[idx].addLeadingStar();
245                 }
246             }
247             else
248             {
249                 entries_[idx].put(key, start + _prefixLength, stop, depth + _prefixLength, value,
250                         false);
251             }
252         }
253 
254         return null;
255     }
256 
257     Object   getSingle(char[] key, int start, int stop)
258     {
259         EntryList _entryList = lookup(key[start]);
260         int _position = start;
261 
262         while (_entryList != null)
263         {
264             int _remainingKeyLength = stop - _position;
265 
266             int _devoured = _entryList.compare(key, start + _entryList.depth_, start
267                     + _entryList.depth_ + _remainingKeyLength, false);
268 
269             if (_devoured == _remainingKeyLength)
270             {
271                 return _entryList.myEntry_.value_;
272             }
273             else if (_devoured > 0)
274             {
275                 char _firstRemainingChar = key[start + _entryList.depth_ + _devoured];
276                 int _oldDepth = _entryList.depth_;
277 
278                 _entryList = _entryList.lookup(_firstRemainingChar);
279 
280                 if (_entryList != null)
281                 {
282                     _position += _entryList.depth_ - _oldDepth;
283                 }
284             }
285         }
286 
287         return null;
288     }
289 
290     /**
291      * check if the Key for this List ends with a star.
292      */
293     private boolean endsWithStar()
294     {
295         return key_[end_ - 1] == WILDCARD_CHAR;
296     }
297 
298     /**
299      * lookup a key in this list. thereby perform Wildcard expansion.
300      */
301     Object  [] getMultiple(char[] key, int start, int stop)
302     {
303         final List   _toBeProcessed = new ArrayList  ();
304 
305         final List   _resultList = new ArrayList  ();
306 
307         Cursor _startCursor;
308 
309         // first try exact match
310 
311         EntryList _list = lookup(key[start]);
312 
313         if (_list != null)
314         {
315             // add EntryList to nodes to be processed
316 
317             _toBeProcessed.add(new Cursor(start, _list));
318         }
319 
320         // next try '*'
321 
322         if ((_list = lookup(WILDCARD_CHAR)) != null)
323         {
324             // add EntryList to nodes to be processed
325 
326             _startCursor = new Cursor(start, _list);
327 
328             _toBeProcessed.add(_startCursor);
329         }
330 
331         // process all found nodes
332 
333         while (!_toBeProcessed.isEmpty())
334         {
335             Cursor _currentCursor = (Cursor) _toBeProcessed.get(0);
336 
337             int _remainingKeyLength = stop - _currentCursor.cursor_;
338 
339             // try to match the search key to the part of key which is
340             // associated with the current node
341             int _devoured = _currentCursor.list_.compare(key, start + _currentCursor.list_.depth_,
342                     start + _currentCursor.list_.depth_ + _remainingKeyLength, true);
343 
344             if (_devoured >= _remainingKeyLength)
345             {
346                 // the whole key could be matched
347 
348                 if (_currentCursor.list_.hasEntry())
349                 {
350                     // if the current node has a result add it to the
351                     // result set.
352                     _resultList.add(_currentCursor.list_.myEntry_.value_);
353                 }
354 
355                 if ((_remainingKeyLength > 0) && _currentCursor.list_.endsWithStar())
356                 {
357                     // current key ends with '*'
358                     // this means the last compare matched everything
359                     // nontheless there still might be outgoing edges
360                     // which must be checked if we have some more chars in
361                     // the key left.
362 
363                     for (int x = 0; x < _currentCursor.list_.entries_.length; ++x)
364                     {
365                         if (_currentCursor.list_.entries_[x] != null)
366                         {
367                             _toBeProcessed.add(new Cursor(_currentCursor.list_.depth_ + 1,
368                                     _currentCursor.list_.entries_[x]));
369                         }
370                     }
371                 }
372 
373                 if (_currentCursor.list_.lookup(WILDCARD_CHAR) != null)
374                 {
375                     // if there is a outgoing '*' visit it
376                     // because it might match the end of a key
377 
378                     _currentCursor.list_ = _currentCursor.list_.lookup(WILDCARD_CHAR);
379                     _currentCursor.cursor_ += _devoured;
380                 }
381                 else
382                 {
383                     _toBeProcessed.remove(0);
384                 }
385             }
386             else if (_devoured > 0)
387             {
388                 // a part could be matched
389                 char _firstRemainingChar = key[start + _currentCursor.list_.depth_ + _devoured];
390 
391                 int _oldDepth = _currentCursor.list_.depth_;
392 
393                 // '*' always matches
394 
395                 if (_currentCursor.list_.lookup(WILDCARD_CHAR) != null)
396                 {
397                     EntryList _entryList = _currentCursor.list_.lookup(WILDCARD_CHAR);
398 
399                     _toBeProcessed.add(new Cursor(_currentCursor.cursor_ + _entryList.depth_
400                             - _oldDepth, _entryList));
401                 }
402 
403                 if ((_currentCursor.list_ = _currentCursor.list_.lookup(_firstRemainingChar)) != null)
404                 {
405                     // instead of removing the old and adding a new
406                     // cursor we reuse the old cursor
407                     _currentCursor.cursor_ += _currentCursor.list_.depth_ - _oldDepth;
408                 }
409                 else
410                 {
411                     _toBeProcessed.remove(0);
412                 }
413             }
414             else
415             {
416                 // no part of the search key could be matched
417                 _toBeProcessed.remove(0);
418             }
419         }
420 
421         return _resultList.toArray();
422     }
423 
424     Object   remove(char[] key, int start, int stop)
425     {
426         return remove(this, key, start, stop);
427     }
428 
429     private static Object   remove(EntryList l, char[] key, int start, int stop)
430     {
431         int _cursor = start;
432         EntryList _current = l;
433 
434         while (true)
435         {
436             int _devoured = findCommonPrefix(key, _cursor, stop, _current.key_, _current.start_,
437                     _current.end_);
438 
439             _cursor += _devoured;
440 
441             if (_cursor == stop)
442             {
443                 Object   _old = null;
444 
445                 if (_current.myEntry_ != null)
446                 {
447                     _old = _current.myEntry_.value_;
448                     _current.myEntry_ = null;
449                 }
450 
451                 return _old;
452             }
453 
454             char _firstNext = key[start + _devoured];
455             _current = _current.lookup(_firstNext);
456 
457             if (_current == null)
458             {
459                 return null;
460             }
461         }
462     }
463 
464     ////////////////////////////////////////
465     // private methods
466 
467     private static class Cursor
468     {
469         int cursor_;
470 
471         EntryList list_;
472 
473         Cursor(int cursor, EntryList list)
474         {
475             cursor_ = cursor;
476             list_ = list;
477         }
478 
479         public String   toString()
480         {
481             String   _rest = new String  (list_.key_, cursor_, list_.end_ - cursor_);
482 
483             return "Cursor: " + _rest;
484         }
485     }
486 
487     private void addLeadingStar()
488     {
489         int _newLength = end_ - start_ + 1;
490 
491         char[] _newKey = new char[_newLength];
492         System.arraycopy(key_, start_, _newKey, 1, end_ - start_);
493         _newKey[0] = WILDCARD_CHAR;
494 
495         initPattern(_newKey, 0, _newLength);
496     }
497 
498     private void initPattern()
499     {
500         initPattern(key_, start_, end_);
501     }
502 
503     private void initPattern(char[] key, int start, int stop)
504     {
505         myPattern_ = null;
506 
507         int _starCount = countStarsInKey(key, start, stop);
508 
509         if (_starCount > 0)
510         {
511             char[] _pattern = new char[stop - start + _starCount + 1];
512             _pattern[0] = '^'; // regexp to match begin of line
513             int x = 0;
514             int _offset = 1;
515 
516             while (x < (stop - start))
517             {
518                 char _x = key[start + x];
519                 _pattern[x + _offset] = _x;
520 
521                 // replace '*' with '.*'
522                 if (_pattern[x + _offset] == WILDCARD_CHAR)
523                 {
524                     _pattern[x + _offset] = '.';
525                     _pattern[x + _offset + 1] = WILDCARD_CHAR;
526                     ++_offset;
527                 }
528 
529                 ++x;
530             }
531 
532             String   _patternString = new String  (_pattern, 0, stop - start + _starCount + 1);
533             myPattern_ = PatternWrapper.init(_patternString);
534         }
535     }
536 
537     private char key()
538     {
539         return key_[start_];
540     }
541 
542     private EntryList lookup(char key)
543     {
544         int idx = computeHashIndex(key);
545 
546         if (entries_[idx] != null && entries_[idx].key() == key)
547         {
548             return entries_[idx];
549         }
550 
551         return null;
552     }
553 
554     /**
555      * ensure that the index returned by computeHashIndex for a specified key is available. That
556      * means
557      * <ol>
558      * <li>The Index is empty
559      * <li>The Index contains an EntryList with the same Key as the specified one
560      * </ol>
561      */
562     private void ensureIndexIsAvailable(char key)
563     {
564         int idx = computeHashIndex(key);
565 
566         while (true)
567         {
568             // assert (idx < entries_.length);
569 
570             if (entries_[idx] == null || entries_[idx].key() == key)
571             {
572                 return;
573             }
574 
575             doubleCapacity();
576 
577             idx = computeHashIndex(key);
578         }
579     }
580 
581     /**
582      * double the capacity for our entries. copy entries from old list into the new one.
583      */
584     private void doubleCapacity()
585     {
586         int _newSize = entries_.length * 2;
587 
588         EntryList[] _newList = new EntryList[_newSize];
589 
590         for (int x = 0; x < entries_.length; ++x)
591         {
592             if (entries_[x] != null)
593             {
594                 int _arrayPos = computeHashIndex(entries_[x].key(), _newSize);
595                 _newList[_arrayPos] = entries_[x];
596             }
597         }
598 
599         entries_ = _newList;
600     }
601 
602     private int compare(char[] a, int start, int stop, boolean wildcard)
603     {
604         if (wildcard && myPattern_ != null)
605         {
606             return compareKeyToPattern(a, start, stop, myPattern_);
607         }
608 
609         return compareKeyToKey(a, start, stop, key_, start_, end_);
610     }
611 
612     private int findCommonPrefix(char[] key, int start, int stop)
613     {
614         return findCommonPrefix(key, start, stop, key_, start_, end_);
615     }
616 
617     private void printToStringBuffer(StringBuffer   sb, String   offset)
618     {
619         if (key_ != null)
620         {
621             sb.append(" --");
622             sb.append(key());
623             sb.append("-->\n");
624             sb.append(offset);
625             sb.append("depth: ");
626             sb.append(depth_);
627             sb.append("\n");
628             sb.append(offset);
629             sb.append("key: ");
630             sb.append(new String  (key_, start_, end_ - start_));
631             sb.append("\n");
632         }
633 
634         if (myEntry_ != null)
635         {
636             sb.append(offset + myEntry_);
637             sb.append("\n");
638         }
639 
640         for (int x = 0; x < entries_.length; x++)
641         {
642             sb.append(offset + x);
643             sb.append(":");
644 
645             if (entries_[x] == null)
646             {
647                 sb.append("empty");
648             }
649             else
650             {
651                 entries_[x].printToStringBuffer(sb, offset + "   ");
652             }
653 
654             sb.append("\n");
655         }
656     }
657 
658     public String   toString()
659     {
660         StringBuffer   _b = new StringBuffer  ();
661         printToStringBuffer(_b, "");
662         return _b.toString();
663     }
664 
665     ////////////////////////////////////////
666     // static methods
667 
668     private static void splitEntryList(EntryList list, int offset)
669     {
670 
671         EntryList _ret = new EntryList(list.key_, list.start_ + offset, list.end_, list.depth_
672                 + offset, list.myEntry_, list.entries_.length);
673 
674         System.arraycopy(list.entries_, 0, _ret.entries_, 0, list.entries_.length);
675 
676         list.entries_ = new EntryList[DEFAULT_INITIAL_SIZE];
677 
678         char _key = list.key_[list.start_ + offset];
679 
680         int _idx = computeHashIndex(_key, list.entries_.length);
681 
682         list.entries_[_idx] = _ret;
683         list.myEntry_ = null;
684         list.splitted++;
685         list.end_ = list.start_ + offset;
686 
687         if (list.endsWithStar())
688         {
689             _ret.addLeadingStar();
690         }
691 
692         list.initPattern();
693     }
694 
695     private static int computeHashIndex(char c, int size)
696     {
697         return c % size;
698     }
699 
700     private int computeHashIndex(char c)
701     {
702         return computeHashIndex(c, entries_.length);
703     }
704 
705     static int compareKeyToKey(char[] firstKeyArray, int start1, int stop1, char[] secondKeyArray,
706             int start2, int stop2)
707     {
708         int length1 = stop1 - start1;
709         int length2 = stop2 - start2;
710         int _guard = (length1 > length2) ? length2 : length1;
711 
712         int _ret = 0;
713 
714         while (_ret < _guard)
715         {
716             if (firstKeyArray[start1 + _ret] != secondKeyArray[start2 + _ret])
717             {
718                 return _ret;
719             }
720 
721             ++_ret;
722         }
723 
724         return _ret;
725     }
726 
727     private static int compareKeyToPattern(char[] string1, int start1, int stop1, PatternWrapper p)
728     {
729         String   _other = new String  (string1, start1, stop1 - start1);
730 
731         return p.match(_other);
732     }
733 
734     private static int findCommonPrefix(char[] key1, int start1, int stop1, char[] key2,
735             int start2, int stop2)
736     {
737         int _x = 0;
738         int _length1 = stop1 - start1;
739         int _length2 = stop2 - start2;
740 
741         int _guard = (_length1 >= _length2) ? _length2 : _length1;
742 
743         while ((_x < _guard) && (key1[start1] == key2[start2]))
744         {
745             ++start1;
746             ++start2;
747             ++_x;
748         }
749 
750         return _x;
751     }
752 
753     static int countStarsInKey(char[] key, int start, int end)
754     {
755         int _starCount = 0;
756         int x = start;
757 
758         while (x < end)
759         {
760             if (key[x] == WILDCARD_CHAR)
761             {
762                 ++_starCount;
763             }
764 
765             ++x;
766         }
767         return _starCount;
768     }
769 
770     /**
771      * This Class represents a Entry within a WildcardMap. Each Entry is identified by a key and has
772      * a value associated.
773      */
774     private static class MapEntry
775     {
776         /**
777          * start index of key within key_ array
778          */
779         private final int start_;
780 
781         /**
782          * stop index of key within key_ array
783          */
784         private final int stop_;
785 
786         /**
787          * this array contains the key. start and stop index of the key are denoted by start_ and
788          * stop_
789          */
790         final char[] key_;
791 
792         /**
793          * value associated to this Entry
794          */
795         final Object   value_;
796 
797         ////////////////////////////////////////
798 
799         /**
800          * Creates a new <code>WCEntry</code> instance.
801          * 
802          * @param key
803          *            a <code>char[]</code> value
804          * @param start
805          *            an <code>int</code> value
806          * @param stop
807          *            an <code>int</code> value
808          * @param value
809          *            an <code>Object</code> value
810          */
811         MapEntry(char[] key, int start, int stop, Object   value)
812         {
813             key_ = key;
814             start_ = start;
815             stop_ = stop;
816             value_ = value;
817         }
818 
819         ////////////////////////////////////////
820 
821         public int hashCode()
822         {
823             return key_[start_];
824 
825         }
826 
827         public boolean equals(Object   o)
828         {
829             try
830             {
831                 MapEntry _other = (MapEntry) o;
832 
833                 return (EntryList.compareKeyToKey(key_, start_, stop_, _other.key_, _other.start_,
834                         _other.stop_) > 0);
835             } catch (ClassCastException   e)
836             {
837                 return super.equals(o);
838             } catch (NullPointerException   e)
839             {
840                 return false;
841             }
842         }
843 
844         public String   toString()
845         {
846             StringBuffer   _b = new StringBuffer  ();
847 
848             _b.append("['");
849             _b.append(new String  (key_, start_, stop_ - start_));
850             _b.append("' => ");
851             _b.append(value_);
852             _b.append("]");
853 
854             return _b.toString();
855         }
856     }
857 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags