[jdom-interest] Suggestion for adding breadthFirstEnumeration and
deapthFirstEnumeration in the Element class
Chandra Patni
patnicp at techemail.com
Sun Aug 13 17:45:33 PDT 2000
hi Elliott,
Sorry, for posting first message in jdom-commits list. yeah! we can experiment in a separate class in the contrib package. I have written a class file which facilitates the breadth-first iteration of an org.jdom.Element. The class also has a main method for testing purpose (which either takes a xml file as command line input or it looks for test.xml in the current dir).
Let me know your comments. We can work on other iterations as well.
Regards,
Chandra Patni
/////// start of java source
/*
* Liscence agreement: This class is written as a contribution to JDOM project.
* Copyright © 2000 Chandra Patni. All Rights Reserved.
* This source is free for use, modification, and or distribution.
*/
import java.util.*;
import org.jdom.*;
// [[CPP]] Shoudn't we make make this class packagae private????
/// XXXX
/*
I guess there are two ways this class (and serveral others) can be deployed
1) We can make this class and including other classes for getting iterators
to be package-private and Element class then may have methods like.
public Iterator breadthFirstEnumeration();
2) The other kind of possible implemetation can be through a use of static
methods of this class and this class may be included in contrib package.
Currently, I have provided a static method for this purpose.
comments to patnicp at techemail.com
*/
/**
* A class which implements <code>Iterator</code> for traversing a JDOM
* <code>Element</code> subtree (including the root of the tree) rooted
* at the constructing <code>Element</code> in breadth-first order.
*
* <p>
* @author Chandra Patni
* @version 1.0
* </p>
*/
class BreadthFirstIterator implements Iterator {
/**
* A queue of <code>Iterator</code>s used for traversing in breadth-first
* fashtion
*/
private IteratorQueue queue;
/**
* To encapsulate an <code>Element</code> instance.
* @param element the element which will be traversed
*/
// we may want to widen this access depending on the implemetation
private BreadthFirstIterator(Element element) {
// Element needs to wrap up in the list so that it's Iterator can be
// queued.
List list = new LinkedList();
list.add(element);
queue = new IteratorQueue();
queue.enqueue(list.iterator());
}
/**
* Returns an <code>Iterator</code> which allows the <code>Element</code>
* subtree (including the specified <code>Element</code>) rooted at this
* <code>Element</code> to be traversed in breadth-first manner.
* @param <code>element</code> the <code>Element</code> which will be traversed
* in the entirity of the returned <code>Iterator</code>
* @return An instance of <code>Iterator</code>
*/
public static Iterator getBreadthFirstIterator(Element element) {
// If this class has to go into contrib package then this method may
// be used and the constructor may be made private...
// ??? any suggestions ???
return new BreadthFirstIterator(element);
}
/**
* Returns true if the iteration has more <code>Element</code>
* @return <code>true</code> if the iteration has more <code>
* Element</code>; <code>false</code> otherwise
*/
public boolean hasNext() {
return (!queue.isEmpty() && (queue.peek().hasNext()));
}
/**
* Returns the next <code>Element<code> in iteration
* @return an instance of <code>Element</code> casted in <code>Object</code>
* @exception <code>NoSuchElementException</code> if the iteration has no
* more elements to return.
*/
public Object next() {
Iterator iterator = queue.peek();
if(iterator == null) {
throw new NoSuchElementException("Iterator has no more elements");
}
// we will be always sure that the iterator has an element if it is enqueued.
Element element = (Element) iterator.next();
// if the iterator has no more element dequeue it.
if(! iterator.hasNext()) {
queue.dequeue();
}
// enqueue all its children if they exist
Iterator children = element.getChildren().iterator();
if(children.hasNext()) {
queue.enqueue(children);
}
return element;
}
/**
* Removes the the next <code>Element<code> in iteration
* @exception <code>NoSuchElementException</code> if the iteration has no
* more elements to remove.
* <b> Not implemented yet </b>
*/
public void remove() {
throw new UnsupportedOperationException("The remove operation is not supported yet!");
}
/**
* A simple queue of <code>Iterator</code>s to facilitate iteration. The
* queue is implemented as linked list data structure. The <code>enqueue()
* </code> operation on the <code>IteratorQueue</code> adds an <code>
* Iterator</code> at the end of the queue and the <code>dequeue()</code>
* operation on the <code>IteratorQueue</code> removes an <code>Iterator
* </code> at the start of the queue. The class also provides <code>peek()
* </code> operation which returns an <code>Iterator</code> without
* dequeuing it.
*/
private class IteratorQueue {
/**
* start of the queue. <code>null</code> if queue is empty
*/
QueueItem head;
/**
* end of the queue.
*/
QueueItem tail;
/**
* Check to see if the queue is empty.
* @return <code>true</code> if the queue is empty, <code>false</code> otherwise
*/
public boolean isEmpty() {
return head == null;
}
/**
* Adds an <codeIterator</code> at the end of the queue.
* @param <code>newIterator Iterator</code> to be queued.
*/
public void enqueue(Iterator newIterator) {
QueueItem itemToAdd = new QueueItem(newIterator, null);
if(head == null) {
head = tail = itemToAdd;
}
else {
tail.nextItem = itemToAdd;
tail = itemToAdd;
}
}
/**
* Removes an <codeIterator</code> from the start of the queue.
* @return <code>Iterator</code> to be dequeued.
*/
public Iterator dequeue() {
// check for empty list
if(head == null) {
new NoSuchElementException("Trying to dequeue from and empty list");
}
Iterator iteratorToReturn = head.iterator;
// now head shoule point to the head.nextItem.
head = head.nextItem;
// case of when list is empty after dequeueing
if(head == null) {
tail = null;
}
return iteratorToReturn;
}
/**
* Returns an <codeIterator</code> from the start of the queue without
* removing it.
* @return <code>Iterator</code> at the begining of the queue.
*/
public Iterator peek() {
if(head != null) {
return head.iterator;
}
else {
return null;
}
}
/**
* Class which is provides a linked-list data structure for the
* facilitation of queue.
*/
private class QueueItem {
/**
* The <code>Iterator</code> which makes the content of each link
* of the linked list
*/
Iterator iterator;
/**
* The next Item of the linked list which is <code>null</code> to indicate
* the end of the list
*/
QueueItem nextItem;
/**
* Constructor to create a link of the linked-list.
* @param <code>iterator</code> The content of the link
* @param <code>nextItem</code> the next item which can be
* accessed from this
*/
QueueItem(Iterator iterator, QueueItem nextItem) {
this.iterator = iterator;
this.nextItem = nextItem;
}
} // end of class QueueItem
} // end of class IteratorQueue
// method for testing purpose
public static void main(String args[]) throws JDOMException {
String fileName = "test.xml"; // set a defualt file name
if(args.length == 1) {
fileName = args[0];
}
Element rootElement = new org.jdom.input.SAXBuilder().build(fileName).getRootElement();
Iterator breadthFirstIterator = BreadthFirstIterator.getBreadthFirstIterator(rootElement);
while(breadthFirstIterator.hasNext()) {
Element e = (Element) breadthFirstIterator.next();
System.out.println(e);
}
}
} // End of class BreadthFirstEnumeration
////// end of java source
From: Elliotte Rusty Harold <elharo at metalab.unc.edu> Save Address
Print View
Show Headers
Report Junk Mail
Date: Thu, 10 Aug 2000 07:47:56 -0400
To: Chandra Patni <javaguru at pcgeek.net>, jdom-interest at jdom.org
Subject: Re: [jdom-commits] Suggestion for adding breadthFirstEnumeration and deapthFirstEnumeration in the Element class
--------------------------------------------------------------------------------At 4:12 PM -0700 8/9/00, > It will be really useful to have breadthFirstEnumeration,
>deapthFirstEnumeration and other traversals of a given element. I
>suggest the inclusion of these two methods in the Element class.
>
>Iterator breadthFirstIterator();
>Iterator depthFirstIterator();
>Iterator inOrderIterator();
>Iterator postOrderIterator();
>Iterator preOrderIterator();
>
>I will be willing to contribute to this effort if desired.
>
These could be useful but I see no reason to clutter the Element API
with them. How about experimenting with them in a separate class
somewhere off in the contrib package?
+-----------------------+------------------------+-------------------+
| Elliotte Rusty Harold | elharo at metalab.unc.edu | Writer/Programmer |
+-----------------------+------------------------+-------------------+
| The XML Bible (IDG Books, 1999) |
| http://metalab.unc.edu/xml/books/bible/ |
| http://www.amazon.com/exec/obidos/ISBN=0764532367/cafeaulaitA/ |
+----------------------------------+---------------------------------+
| Read Cafe au Lait for Java News: http://metalab.unc.edu/javafaq/ |
| Read Cafe con Leche for XML News: http://metalab.unc.edu/xml/ |
+----------------------------------+---------------------------------+
_______________________________________________________
Are you a Techie? Get Your Free Tech Email Address Now!
Many to choose from! Visit http://www.TechEmail.com
-------------- next part --------------
/*
* Liscence agreement: This class is written as a contribution to JDOM project.
* Copyright © 2000 Chandra Patni. All Rights Reserved.
* This source is free for use, modification, and or distribution.
*/
import java.util.*;
import org.jdom.*;
// [[CPP]] Shoudn't we make make this class packagae private????
/// XXXX
/*
I guess there are two ways this class (and serveral others) can be deployed
1) We can make this class and including other classes for getting iterators
to be package-private and Element class then may have methods like.
public Iterator breadthFirstEnumeration();
2) The other kind of possible implemetation can be through a use of static
methods of this class and this class may be included in contrib package.
Currently, I have provided a static method for this purpose.
comments to patnicp at techemail.com
*/
/**
* A class which implements <code>Iterator</code> for traversing a JDOM
* <code>Element</code> subtree (including the root of the tree) rooted
* at the constructing <code>Element</code> in breadth-first order.
*
* <p>
* @author Chandra Patni
* @version 1.0
* </p>
*/
class BreadthFirstIterator implements Iterator {
/**
* A queue of <code>Iterator</code>s used for traversing in breadth-first
* fashtion
*/
private IteratorQueue queue;
/**
* To encapsulate an <code>Element</code> instance.
* @param element the element which will be traversed
*/
// we may want to widen this access depending on the implemetation
private BreadthFirstIterator(Element element) {
// Element needs to wrap up in the list so that it's Iterator can be
// queued.
List list = new LinkedList();
list.add(element);
queue = new IteratorQueue();
queue.enqueue(list.iterator());
}
/**
* Returns an <code>Iterator</code> which allows the <code>Element</code>
* subtree (including the specified <code>Element</code>) rooted at this
* <code>Element</code> to be traversed in breadth-first manner.
* @param <code>element</code> the <code>Element</code> which will be traversed
* in the entirity of the returned <code>Iterator</code>
* @return An instance of <code>Iterator</code>
*/
public static Iterator getBreadthFirstIterator(Element element) {
// If this class has to go into contrib package then this method may
// be used and the constructor may be made private...
// ??? any suggestions ???
return new BreadthFirstIterator(element);
}
/**
* Returns true if the iteration has more <code>Element</code>
* @return <code>true</code> if the iteration has more <code>
* Element</code>; <code>false</code> otherwise
*/
public boolean hasNext() {
return (!queue.isEmpty() && (queue.peek().hasNext()));
}
/**
* Returns the next <code>Element<code> in iteration
* @return an instance of <code>Element</code> casted in <code>Object</code>
* @exception <code>NoSuchElementException</code> if the iteration has no
* more elements to return.
*/
public Object next() {
Iterator iterator = queue.peek();
if(iterator == null) {
throw new NoSuchElementException("Iterator has no more elements");
}
// we will be always sure that the iterator has an element if it is enqueued.
Element element = (Element) iterator.next();
// if the iterator has no more element dequeue it.
if(! iterator.hasNext()) {
queue.dequeue();
}
// enqueue all its children if they exist
Iterator children = element.getChildren().iterator();
if(children.hasNext()) {
queue.enqueue(children);
}
return element;
}
/**
* Removes the the next <code>Element<code> in iteration
* @exception <code>NoSuchElementException</code> if the iteration has no
* more elements to remove.
* <b> Not implemented yet </b>
*/
public void remove() {
throw new UnsupportedOperationException("The remove operation is not supported yet!");
}
/**
* A simple queue of <code>Iterator</code>s to facilitate iteration. The
* queue is implemented as linked list data structure. The <code>enqueue()
* </code> operation on the <code>IteratorQueue</code> adds an <code>
* Iterator</code> at the end of the queue and the <code>dequeue()</code>
* operation on the <code>IteratorQueue</code> removes an <code>Iterator
* </code> at the start of the queue. The class also provides <code>peek()
* </code> operation which returns an <code>Iterator</code> without
* dequeuing it.
*/
private class IteratorQueue {
/**
* start of the queue. <code>null</code> if queue is empty
*/
QueueItem head;
/**
* end of the queue.
*/
QueueItem tail;
/**
* Check to see if the queue is empty.
* @return <code>true</code> if the queue is empty, <code>false</code> otherwise
*/
public boolean isEmpty() {
return head == null;
}
/**
* Adds an <codeIterator</code> at the end of the queue.
* @param <code>newIterator Iterator</code> to be queued.
*/
public void enqueue(Iterator newIterator) {
QueueItem itemToAdd = new QueueItem(newIterator, null);
if(head == null) {
head = tail = itemToAdd;
}
else {
tail.nextItem = itemToAdd;
tail = itemToAdd;
}
}
/**
* Removes an <codeIterator</code> from the start of the queue.
* @return <code>Iterator</code> to be dequeued.
*/
public Iterator dequeue() {
// check for empty list
if(head == null) {
new NoSuchElementException("Trying to dequeue from and empty list");
}
Iterator iteratorToReturn = head.iterator;
// now head shoule point to the head.nextItem.
head = head.nextItem;
// case of when list is empty after dequeueing
if(head == null) {
tail = null;
}
return iteratorToReturn;
}
/**
* Returns an <codeIterator</code> from the start of the queue without
* removing it.
* @return <code>Iterator</code> at the begining of the queue.
*/
public Iterator peek() {
if(head != null) {
return head.iterator;
}
else {
return null;
}
}
/**
* Class which is provides a linked-list data structure for the
* facilitation of queue.
*/
private class QueueItem {
/**
* The <code>Iterator</code> which makes the content of each link
* of the linked list
*/
Iterator iterator;
/**
* The next Item of the linked list which is <code>null</code> to indicate
* the end of the list
*/
QueueItem nextItem;
/**
* Constructor to create a link of the linked-list.
* @param <code>iterator</code> The content of the link
* @param <code>nextItem</code> the next item which can be
* accessed from this
*/
QueueItem(Iterator iterator, QueueItem nextItem) {
this.iterator = iterator;
this.nextItem = nextItem;
}
} // end of class QueueItem
} // end of class IteratorQueue
// method for testing purpose
public static void main(String args[]) throws JDOMException {
String fileName = "test.xml"; // set a defualt file name
if(args.length == 1) {
fileName = args[0];
}
Element rootElement = new org.jdom.input.SAXBuilder().build(fileName).getRootElement();
Iterator breadthFirstIterator = BreadthFirstIterator.getBreadthFirstIterator(rootElement);
while(breadthFirstIterator.hasNext()) {
Element e = (Element) breadthFirstIterator.next();
System.out.println(e);
}
}
} // End of class BreadthFirstEnumeration
More information about the jdom-interest
mailing list