Mercurial > hg > digilib-old

comparison servlet/src/digilib/auth/HashTree.java @ 205:6221d688eab6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Servlet version 1.18b9 -- cleanup and bugfixes - fixed bug with slow color JPEGs - better pathname handling - better filehandle cleanup (hopefully)
author robcast
date Fri, 12 Mar 2004 19:52:06 +0100
parents afe7ff98bb71
children 6e6bf5aa7ad2
comparison
equal deleted inserted replaced
204:37a697fd8ec6 205:6221d688eab6
1 /* HashTree -- Tree in a Hashtable 1 /* HashTree -- Tree in a Hashtable
2 2
3 Digital Image Library servlet components 3 Digital Image Library servlet components
4 4
5 Copyright (C) 2001, 2002 Robert Casties (robcast@mail.berlios.de) 5 Copyright (C) 2001, 2002 Robert Casties (robcast@mail.berlios.de)
6 6
7 This program is free software; you can redistribute it and/or modify it 7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the 8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2 of the License, or (at your 9 Free Software Foundation; either version 2 of the License, or (at your
10 option) any later version. 10 option) any later version.
11 11
12 Please read license.txt for the full details. A copy of the GPL 12 Please read license.txt for the full details. A copy of the GPL
13 may be found at http://www.gnu.org/copyleft/lgpl.html 13 may be found at http://www.gnu.org/copyleft/lgpl.html
14 14
15 You should have received a copy of the GNU General Public License 15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software 16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 18
19 */ 19 */
20 20
21 package digilib.auth; 21 package digilib.auth;
22 22
23 import java.util.*; 23 import java.util.*;
24 24
25 /**
26 * Tree representation wrapper for a HashMap.
27 *
28 * The HashTree is constructed from a HashMap filled with 'branches' with
29 * 'leaves'. The branches are stored as String keys in the HashMap. The String
30 * values are leaves.
31 *
32 * Branches are matched in 'twigs' separated by 'twig separator' Strings. The
33 * return values for a match are leaf values separated by 'leaf separator'
34 * Strings.
35 *
36 * @author casties
37 */
25 public class HashTree { 38 public class HashTree {
26 39
27 private HashMap table; 40 private HashMap table;
28 private String twigSep = "/";
29 private String leafSep = ",";
30 41
31 public HashTree() { 42 private String twigSep = "/";
32 table = new HashMap();
33 }
34 43
35 public HashTree(HashMap t, String twig_separator, String leaf_separator) { 44 private String leafSep = ",";
36 table = t;
37 twigSep = twig_separator;
38 leafSep = leaf_separator;
39 optimizeTable();
40 }
41 45
42 void optimizeTable() { 46 /**
43 } 47 * Constructor of a HashTree.
48 *
49 * Creates a HashTree wrapper around a given HashMap, using the given twig
50 * separator and leaf separator.
51 *
52 * @param t
53 * @param twig_separator
54 * @param leaf_separator
55 */
56 public HashTree(HashMap t, String twig_separator, String leaf_separator) {
57 table = t;
58 twigSep = twig_separator;
59 leafSep = leaf_separator;
60 optimizeTable();
61 }
44 62
45 List match(String branch) { 63 void optimizeTable() {
46 String b = ""; 64 }
47 String m;
48 LinkedList matches = new LinkedList();
49 65
50 // split branch 66 /**
51 StringTokenizer twig = new StringTokenizer(branch, twigSep); 67 * Matches the given branch against the HashTree.
52 // walk branch and check with tree 68 *
53 while (twig.hasMoreTokens()) { 69 * Returns a LinkedList of all leaves on all matching branches in the tree.
54 if (b.length() == 0) { 70 * Branches in the tree match if they are substrings starting at the same
55 b = twig.nextToken(); 71 * root.
56 } else { 72 *
57 b += twigSep + twig.nextToken(); 73 * @param branch
58 } 74 * @return
59 m = (String)table.get(b); 75 */
60 if (m != null) { 76 List match(String branch) {
61 if (m.indexOf(leafSep) < 0) { 77 String b = "";
62 // single leaf 78 String m;
63 matches.add(m); 79 LinkedList matches = new LinkedList();
80
81 // split branch
82 StringTokenizer twig = new StringTokenizer(branch, twigSep);
83 // walk branch and check with tree
84 while (twig.hasMoreTokens()) {
85 if (b.length() == 0) {
86 b = twig.nextToken();
87 } else {
88 b += twigSep + twig.nextToken();
89 }
90 m = (String) table.get(b);
91 if (m != null) {
92 if (m.indexOf(leafSep) < 0) {
93 // single leaf
94 matches.add(m);
95 } else {
96 // split leaves
97 StringTokenizer leaf = new StringTokenizer(m, leafSep);
98 while (leaf.hasMoreTokens()) {
99 matches.add(leaf.nextToken());
100 }
101 }
102 }
103 }
104 if (matches.size() > 0) {
105 return matches;
64 } else { 106 } else {
65 // split leaves 107 return null;
66 StringTokenizer leaf = new StringTokenizer(m, leafSep);
67 while (leaf.hasMoreTokens()) {
68 matches.add(leaf.nextToken());
69 }
70 } 108 }
71 }
72 } 109 }
73 if (matches.size() > 0) {
74 return matches;
75 } else {
76 return null;
77 }
78 }
79 } 110 }