001: /*
002: * @(#)PathRegistry.java 0.9.0 04/26/2000 - 13:39:11
003: *
004: * Copyright (C) 2000,,2003 2002 Matt Albrecht
005: * groboclown@users.sourceforge.net
006: * http://groboutils.sourceforge.net
007: *
008: * Permission is hereby granted, free of charge, to any person obtaining a
009: * copy of this software and associated documentation files (the "Software"),
010: * to deal in the Software without restriction, including without limitation
011: * the rights to use, copy, modify, merge, publish, distribute, sublicense,
012: * and/or sell copies of the Software, and to permit persons to whom the
013: * Software is furnished to do so, subject to the following conditions:
014: *
015: * The above copyright notice and this permission notice shall be included in
016: * all copies or substantial portions of the Software.
017: *
018: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
019: * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
020: * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
021: * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
022: * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
023: * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
024: * DEALINGS IN THE SOFTWARE.
025: */
026:
027: package net.sourceforge.groboutils.util.datastruct.v1;
028:
029: import java.util.Vector;
030: import java.util.Enumeration;
031:
032: /**
033: * A path-tree registry for storing and retrieving objects. Objects can
034: * be registered at any point along the tree, but no more than one object
035: * may be at each node. A <code>null</code> entry at a point indicates
036: * a non-registered node.
037: * <P>
038: * Synchronization needs to be hauled-over to increase speed and minimize
039: * read interference with writes.
040: *
041: * @author Matt Albrecht <a href="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
042: * @since April 26, 2000 (0.9.0 Alpha)
043: * @version $Date: 2003/02/10 22:52:44 $
044: */
045: public class PathRegistry {
046: //----------------------------
047: // Public data
048:
049: //----------------------------
050: // Private data
051:
052: class TreeNode {
053: Object value;
054: boolean isRecursive; // true = no children, but uses children
055: boolean isCaseSensitive;
056: String nodeName;
057: TreeNode nextSibling;
058: TreeNode firstChild;
059: }
060:
061: private char m_separator;
062: private boolean m_ignoreDuplicateSeparators;
063: private TreeNode m_root; // doesn't contain anything in value, and has no name
064:
065: //----------------------------
066: // constructors
067:
068: /**
069: * Users must specify all variables without corresponding defaults. This
070: * prevents the class from implementing defaults, which have a habit of
071: * randomly changing.
072: */
073: public PathRegistry(char separator,
074: boolean ignoreDuplicateSeparators) {
075: this .m_separator = separator;
076: this .m_ignoreDuplicateSeparators = ignoreDuplicateSeparators;
077:
078: // root tree node:
079: m_root = new TreeNode();
080: // ALWAYS:
081: // null nodename, not recursive, no siblings, empty fullname
082: m_root.nodeName = null;
083: m_root.nextSibling = null;
084: m_root.isRecursive = false;
085: m_root.isCaseSensitive = true;
086:
087: // INITIALLY:
088: // no children
089: m_root.firstChild = null;
090: }
091:
092: //----------------------------
093: // Public methods
094:
095: /**
096: * Register the given object at the given path. If the nodes leading
097: * up to this end node do not exist, then they will be created.
098: * <P>
099: * For future use, we will need to re-do synchronization, so that
100: * we synch on the tree node parent being worked on.
101: *
102: * @param path the path under which the given value will be registered.
103: * @param value the object to store under the given path.
104: * @param isRecursive set to <code>true</code> to notify the tree that
105: * this particular node also covers any sub-paths. If this is
106: * <code>false</code>, then queries will only retrieve this
107: * node if the exact path is given.
108: * @param isCaseSensitive set to <code>true</code> if the given node is
109: * to be case sensitive in searches. If the nodes leading to this
110: * new node do not exist, then the newly created nodes will have the
111: * same case sensitivity as this end node.
112: * @exception IllegalArgumentException thrown if the value is
113: * <code>null</code>, or the given path is not well formed.
114: * @exception PathAlreadyRegisteredException thrown if the given path
115: * has already been registered to another object.
116: */
117: public synchronized void register( String path, Object value,
118: boolean isRecursive, boolean isCaseSensitive )
119: throws PathAlreadyRegisteredException
120: {
121: if (path == null || value == null)
122: {
123: throw new IllegalArgumentException(
124: "nulls are not allowed for insertion");
125: }
126:
127: Enumeration enum = parsePath( path );
128: if (!enum.hasMoreElements())
129: {
130: throw new IllegalArgumentException(
131: "path must have at least one element");
132: }
133:
134: TreeNode parent = this .m_root;
135:
136: String current = (String)enum.nextElement();
137://System.out.println("Full path = "+path);
138: boolean addedNode = false;
139:
140: while (true)
141: {
142: addedNode = false;
143://System.out.println("Path part = "+current);
144: TreeNode nextNode = findSibling( parent, current );
145: if (nextNode == null)
146: {
147://System.out.println(" -- needs to be added");
148: // add the node
149: nextNode = new TreeNode();
150: nextNode.value = null;
151: nextNode.nodeName = current;
152: nextNode.isCaseSensitive = isCaseSensitive;
153: nextNode.isRecursive = false;
154: nextNode.nextSibling = null;
155: nextNode.firstChild = null;
156: addChildNode( parent, nextNode );
157: addedNode = true;
158: }
159: else
160: if (nextNode.isRecursive)
161: {
162://System.out.println("Node "+current+" is recursive - can't add under it");
163: // can't add to a recursive path
164: throw new PathAlreadyRegisteredException( path );
165: }
166:
167: if (enum.hasMoreElements())
168: {
169: current = (String)enum.nextElement();
170: }
171: else
172: {
173://System.out.println(" -- On the last node, and it matches node "+nextNode.nodeName );
174: // last node
175: if (!addedNode)
176: {
177: throw new PathAlreadyRegisteredException( path );
178: }
179: nextNode.value = value;
180: nextNode.isRecursive = isRecursive;
181:
182: return;
183: }
184:
185: parent = nextNode;
186: }
187: }
188:
189: /**
190: * Remove the object at the given path. It only removes nodes
191: * if the node no longer has any children. The siblings
192: * are automatically compressed.
193: * <P>
194: * For future use, we will need to re-do synchronization, so that
195: * we synch on the tree node parent being worked on.
196: *
197: * @param path the tree path specifying which node to remove. If the
198: * given node does not exist, or has not been registered, then a
199: * NotRegisteredException is thrown.
200: * @exception IllegalArgumentException thrown if the value is
201: * <code>null</code>, or the given path is not well formed.
202: * @exception NoRegisteredComponentException thrown if the given path node
203: * has not yet been registered.
204: */
205: public synchronized void remove( String path )
206: throws NoRegisteredComponentException
207: {
208: if (path.charAt( path.length()-1 ) != this .m_separator)
209: {
210: path += this .m_separator;
211: }
212: Enumeration enum = parsePath( path );
213: if (!enum.hasMoreElements())
214: {
215: throw new IllegalArgumentException(
216: "path must have at least one element");
217: }
218:
219: TreeNode parent = this .m_root;
220: String current = (String)enum.nextElement();
221:
222: while (true)
223: {
224: TreeNode nextNode = findSibling( parent, current );
225: if (nextNode == null)
226: {
227: // node doesn't exist
228: throw new NoRegisteredComponentException( path );
229: }
230:
231: if (enum.hasMoreElements())
232: {
233: current = (String)enum.nextElement();
234: }
235: else
236: {
237: // last node
238: if (nextNode.value == null)
239: {
240: // node doesn't exist
241: throw new NoRegisteredComponentException( path );
242: }
243:
244: nextNode.value = null;
245: if (nextNode.isRecursive || nextNode.firstChild == null)
246: {
247: removeChild( parent, nextNode );
248: }
249:
250: return;
251: }
252:
253: parent = nextNode;
254: }
255: }
256:
257: /**
258: * Retrieve the object stored at the given path.
259: * <P>
260: * Need to synchronize better so that reads don't collide with writes,
261: * but reads can be done asynchronously.
262: *
263: * @param path the path which specifies the object to retrieve.
264: * @return the object which was registered at the given path, or
265: * <code>null</code> if nothing is registered there.
266: */
267: public synchronized Object get(String path) {
268: TreeNode node = findNode(path);
269: if (node == null)
270: return null;
271:
272: return node.value;
273: }
274:
275: //----------------------------
276: // Protected methods
277:
278: /**
279: * Parses the given path into node elements. The last item in the list is
280: * ignored, unless the path ends with the path separator character.
281: */
282: protected Enumeration parsePath(String path) {
283: if (path == null)
284: return null;
285:
286: if (path.charAt(path.length() - 1) != this .m_separator) {
287: path += this .m_separator;
288: }
289:
290: char cpath[] = path.toCharArray();
291: int len = cpath.length;
292: Vector v = new Vector(len >> 2);
293: int start = 0, next, count;
294:
295: while (start < len) {
296: count = 0;
297: for (next = start; next < len
298: && cpath[next] != this .m_separator; next++) {
299: count++;
300: }
301: // ignore last element in list
302: if (next < len) {
303: v.addElement(new String(cpath, start, count));
304: }
305: start = next + 1;
306: if (this .m_ignoreDuplicateSeparators) {
307: for (; start < len && cpath[start] == this .m_separator; start++) {
308: // do nothing
309: }
310: }
311: }
312:
313: return v.elements();
314: }
315:
316: /**
317: * Find the sibling with the given node name part.
318: */
319: protected TreeNode findSibling(TreeNode parent, String namePart) {
320: //System.out.println("findSibling: name to find = "+namePart);
321: if (parent == null || namePart == null)
322: return null;
323: TreeNode child = parent.firstChild;
324: while (child != null) {
325: //System.out.println(" - child name = "+child.nodeName+"; is case sensitive? "+
326: //child.isCaseSensitive);
327: if (child.isCaseSensitive) {
328: if (namePart.equals(child.nodeName)) {
329: return child;
330: }
331: } else {
332: if (namePart.equalsIgnoreCase(child.nodeName)) {
333: return child;
334: }
335: }
336: child = child.nextSibling;
337: }
338: return null;
339: }
340:
341: /**
342: * Find the node with the given name.
343: */
344: protected TreeNode findNode( String name )
345: {
346://System.out.println("findNode( "+name+" )");
347: Enumeration enum = parsePath( name );
348:
349: TreeNode parent = this .m_root;
350: while (parent != null)
351: {
352: if (parent.isRecursive || !enum.hasMoreElements())
353: {
354://System.out.println(" -- found node");
355: return parent;
356: }
357: String partName = (String)enum.nextElement();
358://System.out.println(" -- checking part "+partName);
359: parent = findSibling( parent, partName );
360://System.out.println(" -- parent = "+parent);
361: }
362: return null;
363: }
364:
365: /**
366: * Find the sibling with the given node name part.
367: */
368: protected void removeChild(TreeNode parent, TreeNode child) {
369: if (parent == null || child == null)
370: return;
371: TreeNode sibling = parent.firstChild;
372: if (child.isCaseSensitive) {
373: if (child.nodeName.equals(sibling.nodeName)) {
374: parent.firstChild = child.nextSibling;
375: return;
376: }
377: } else {
378: if (child.nodeName.equalsIgnoreCase(child.nodeName)) {
379: parent.firstChild = child.nextSibling;
380: return;
381: }
382: }
383:
384: while (sibling.nextSibling != null) {
385: if (child.isCaseSensitive) {
386: if (child.nodeName.equals(sibling.nextSibling.nodeName)) {
387: sibling.nextSibling = child.nextSibling;
388: return;
389: }
390: } else {
391: if (child.nodeName
392: .equalsIgnoreCase(sibling.nextSibling.nodeName)) {
393: sibling.nextSibling = child.nextSibling;
394: return;
395: }
396: }
397: sibling = sibling.nextSibling;
398: }
399:
400: // couldn't find child
401: return;
402: }
403:
404: /**
405: * Child must already be initialized correctly.
406: */
407: protected void addChildNode(TreeNode parent, TreeNode child)
408: throws PathAlreadyRegisteredException {
409: if (parent == null || child == null) {
410: throw new IllegalArgumentException(
411: "parent or child is null");
412: }
413:
414: TreeNode sibling = parent.firstChild;
415:
416: if (sibling == null) {
417: parent.firstChild = child;
418: return;
419: }
420:
421: // loop through all siblings, checking if we can insert the child
422: // for each member, then when the end of the list is found, we
423: // add the child to it.
424: while (true) {
425: // check if we can insert new child
426: if (sibling.isCaseSensitive || child.isCaseSensitive) {
427: if (sibling.nodeName.equals(child.nodeName)) {
428: throw new PathAlreadyRegisteredException();
429: }
430: }
431: if (sibling.nextSibling == null) {
432: sibling.nextSibling = child;
433: return;
434: }
435: sibling = sibling.nextSibling;
436: }
437:
438: // this point should never be reached.
439: // throw new IllegalStateException( "point never reached" );
440: }
441:
442: //----------------------------
443: // Private methods
444: }
|