Results 1 to 13 of 13
  1. #1
    kapkong is offline Member
    Join Date
    Apr 2017
    Posts
    7
    Rep Power
    0

    Default Trees - Difficulty with Recursion & Iterators

    Hi everyone,

    First-time poster here, currently struggling with my understanding of recursion & iterators pertaining to a tree.

    Currently, my code successfully constructs a tree when given the nodes to insert, but fails to recursively traverse the tree to find the desired nodes.

    The relevant methods that aren't working are findFileRecursion & (potentially) filesOfTypeRecursion. Based on my debugging thus far, something is amiss with my use of the .getChildren() iterator. Searching for specific files with findFile for example results in an empty string, which indicates the node could not be found (despite the tree successfully adding those nodes).

    Here is what I think is the relevant code:

    TreeNode.java
    Java Code:
    import java.util.Comparator;
    import java.util.Iterator;
    
    /**
     * Definition for nodes of the file tree
     *
     * @param <T> generic type
     */
    public class TreeNode<T> {
    
    	private TreeNode<T> parent;
    	private ListNodes<TreeNode<T>> children;
    	private T data;
    	
    	/**
    	 * generic constructor for TreeNode
    	 */
    	public TreeNode(){
    		parent = null;
    		children = new ListNodes<TreeNode<T>>();
    		data = null;
    	}
    	
    	/**
    	 * param constructor for TreeNode
    	 * @param d : the data (generic type)
    	 * @param p : the parent node
    	 */
    	public TreeNode(T d, TreeNode<T> p){
    		parent = p;
    		children = new ListNodes<TreeNode<T>>();
    		data = d;
    	}
    	
    	/**
    	 * setter method for parent node
    	 * @param p : the parent node
    	 */
    	public void setParent(TreeNode<T> p){
    		parent = p;
    	}
    	
    	/**
    	 * getter method for parent node
    	 * @return the parent node
    	 */
    	public TreeNode<T> getParent(){
    		return parent;
    	}
    	
    	/**
    	 * add given child to the children ListNodes
    	 * @param c : the child node
    	 */
    	public void addChild(TreeNode<T> c){
    		children.add(c);
    	}
    	
    	/**
    	 * get an iterator of all children of the current node
    	 * @return an iterator of the list of child nodes
    	 */
    	public Iterator<TreeNode<T>> getChildren(){
    		return children.getList();
    	}
    	
    	/**
    	 * get a sorted iterator of child nodes
    	 * @param sorter : sorter method
    	 * @return an iterator of a sorted list of child nodes
    	 */
    	public Iterator<TreeNode<T>> getChildren(Comparator<TreeNode<T>> sorter){
    		return children.sortedList(sorter);
    	}
    	
    	/**
    	 * receive data from node
    	 * @return data of generic type
    	 */
    	public T getData(){
    		return data;
    	}
    	
    	/**
    	 * get data of generic type
    	 * @param d : data of generic type
    	 */
    	public void setData(T d){
    		data = d;
    	}
    }
    FileTree.java
    Java Code:
    import java.util.Iterator;
    import java.util.ArrayList;
    
    public class FileTree {
    	
    	private TreeNode<FileObject> root;
    	
    	public FileTree (String fileObjectName) throws FileObjectException{
    		FileObject rootObject = new FileObject(fileObjectName);
    		root = new TreeNode<FileObject>(rootObject, null);
    		treeRecursion(root);
    	}
    	
    	private void treeRecursion(TreeNode<FileObject> parent){
    		if(parent.getData().isFile())
    			return;
    		else if (parent.getData().isDirectory()){
    			Iterator<FileObject> iterator = parent.getData().directoryFiles();
    			while(iterator != null && iterator.hasNext()){
    				FileObject next = iterator.next();
    				TreeNode<FileObject> newNode = new TreeNode<FileObject>(next, parent);
    				newNode.setParent(parent);
    				parent.addChild(newNode);
    				if(next.isDirectory()){
    					treeRecursion(newNode);
    				}
    			}
    		}
    	}
    	
    	public TreeNode<FileObject> getRoot(){
    		return root;
    	}
    	
    	public Iterator<String> filesOfType(String type){
    		ArrayList<String> fileList = new ArrayList<String>();
    		filesOfTypeRecursion(root, type, fileList);
    		return fileList.iterator();
    	}
    	
    	private void filesOfTypeRecursion(TreeNode<FileObject> root, String type, ArrayList<String> fileList){
    		if (root.getData().isFile()){
    			if (root.getData().getName().endsWith(type))
    				fileList.add(root.getData().getLongName());
    		}
    		else if(root.getData().isDirectory()){
    			Iterator<TreeNode<FileObject>> iterator = root.getChildren();
    			while (iterator != null && iterator.hasNext()){
    				filesOfTypeRecursion(iterator.next(), type, fileList);
    			}
    		}
    	}
    	
    	public String findFile(String name){
    		return findFileRecursion(root, name);
    	}
    	
    	private String findFileRecursion(TreeNode<FileObject> root, String name){
    		if (root.getData().isFile()){
    			if (root.getData().getName().equals(name))
    				return root.getData().getLongName();
    		}
    		
    		else if(root.getData().isDirectory()){
    			Iterator<TreeNode<FileObject>> iterator = root.getChildren();
    			while (iterator != null && iterator.hasNext()){
    				findFileRecursion(iterator.next(), name);
    			}
    		}
    		return "";
    	}
    }
    My apologies for the hassle, and thanks again for any assistance! Please let me know if there's anything I can do to fix formatting, or extra code to include.

    Thanks,
    - kapkong

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,001
    Rep Power
    33

    Default Re: Trees - Difficulty with Recursion & Iterators

    Do you have a test driver that creates the tree, adds values and the does the searches that show the error?
    Also can you post some debug output that shows the problem?
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    kapkong is offline Member
    Join Date
    Apr 2017
    Posts
    7
    Rep Power
    0

    Default Re: Trees - Difficulty with Recursion & Iterators

    Hi Norm,

    We do have a tester program here (it's a doozy):

    Java Code:
    import java.util.Iterator;
    
    public class TestFileTree {
    
    	public static void main(String[] args) {
    		String[] data = { "child1", "child5", "child2", "child4", "child3" };
    		int[] sortedIndex = { 0, 2, 4, 3, 1 };
    
    		// Create the root node of a tree that will have 6 nodes
    		TreeNode<String> root = new TreeNode<String>("root", null), node;
    		Iterator<TreeNode<String>> children;
    		boolean testPassed = true;
    		int index = 0;
    
    		// Add 5 children to the root node
    		for (int i = 0; i < 5; ++i)
    			root.addChild(new TreeNode<String>(data[i], root));
    
    	// Test 3. Build a tree for the following file system:
    	// folder2
    	// --file1.java
    	// --file2.txt
    	// --file3.java
    	//
    	// Tests 4 and 5 use the same tree
    	private static void tests3_5() {
    		FileTree tree;
    		TreeNode<FileObject> r;
    		Iterator<TreeNode<FileObject>> child;
    		boolean testPassed = true;
    		String[] childrenNames = { "folder2/file1.java", "folder2/file2.txt", "folder2/file3.java" };
    		String s;
    		try {
    			tree = new FileTree("folder2");
    			if (FileObject.testFailed())
    				System.out.println("Test 3 failed: Inexistent file object name");
    			else {
    				r = tree.getRoot();
    				if (r.getData().isFile())
    					testPassed = false;
    				if (!r.getData().getName().equals("folder2"))
    					testPassed = false;
    				child = r.getChildren();
    				for (int i = 0; i < 3; ++i) {
    					s = child.next().getData().getLongName();
    					if (!s.equals(childrenNames[i]))
    						testPassed = false;
    				}
    				if (testPassed)
    					System.out.println("Test 3 passed");
    				else
    					System.out.println("Test 3 failed");
    			}
    		} catch (Exception e) {
    			System.out.println("Test 3 failed");
    		}
    
    		// Test 4. Test findFile
    		testPassed = true;
    		Iterator<String> listFiles;
    		String s1;
    		try {
    			tree = new FileTree("folder2");
    			s = tree.findFile("file2.txt");
    			if (!s.equals("folder2/file2.txt"))
    				testPassed = false;
    			s = tree.findFile("nonExistent");
    			if (!s.equals(""))
    				testPassed = false;
    
    			if (testPassed)
    				System.out.println("Test 4 passed");
    			else
    				System.out.println("Test 4 failed");
    		} catch (Exception e) {
    			System.out.println("Test 4 failed");
    		}
    
    		// Test 5. Test filesOfType
    		testPassed = true;
    		try {
    			tree = new FileTree("folder2");
    			s = tree.findFile("file2.txt");
    			if (!s.equals("folder2/file2.txt"))
    				testPassed = false;
    			s = tree.findFile("nonExistent");
    			if (!s.equals(""))
    				testPassed = false;
    			listFiles = tree.filesOfType(".java");
    			s = listFiles.next();
    			if (!s.equals("folder2/file1.java") && !s.equals("folder2/file3.java"))
    				testPassed = false;
    			s1 = listFiles.next();
    			if ((!s1.equals("folder2/file1.java") && !s1.equals("folder2/file3.java")) || s.equals(s1))
    				testPassed = false;
    
    			listFiles = tree.filesOfType(".docx");
    			if (listFiles.hasNext())
    				testPassed = false;
    
    			if (testPassed)
    				System.out.println("Test 5 passed");
    			else
    				System.out.println("Test 5 failed");
    		} catch (Exception e) {
    			System.out.println("Test 5 failed");
    		}
    	}
    
    	// Returns the short form of a file name
    	private static String getShortName(String name) {
    		int i = name.length() -1;
    		
    		// short name starts after character '/' or at position 0
    		while ((i >= 0) && (name.charAt(i) != '/')) --i;
    		return name.substring(i);
    	}
    
    }
    My program fails at line 149, " if (!s.equals("folder2/file2.txt")) ".

    Currently, s = "", an empty string that returns if the file is not found.

    Please let me know what debugger output to include, I'm not that familiar with the use of it in my IDE (Eclipse) aside from stepping through & looking at variables.
    Last edited by kapkong; 04-05-2017 at 06:15 PM.

  4. #4
    kapkong is offline Member
    Join Date
    Apr 2017
    Posts
    7
    Rep Power
    0

    Default Re: Trees - Difficulty with Recursion & Iterators

    Using print statements of iterator.next().getData().getName() to debug, my current issue appears to be that my iterator.next() tests file1.java, folder2/file2.txt, then file1.java again in the recursion.

    It should be file1.java, file2.txt, and file3.java, though the program should return upon finding file2.txt. I'm unsure why the getName() is returning the pathname of the file, when a separate method (.getLongName()) should be doing that instead.

  5. #5
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,001
    Rep Power
    33

    Default Re: Trees - Difficulty with Recursion & Iterators

    (it's a doozy):
    You are right there. Not too many people like to work with such large hunks of code.

    Can you strip it to the smallest size (<100 lines) that will show the problem?
    If you don't understand my response, don't ignore it, ask a question.

  6. #6
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Trees - Difficulty with Recursion & Iterators

    First, what kind of tree is it? Binary? n-ary? From my quick perusal it looks more like a linked list. Can you describe it?
    And to traverse a binary tree or even a linked list is trivial. Should only require 10 to 20 lines of code.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  7. #7
    kapkong is offline Member
    Join Date
    Apr 2017
    Posts
    7
    Rep Power
    0

    Default Re: Trees - Difficulty with Recursion & Iterators

    Done, removed the test cases I've passed / not focusing on yet. Thanks Norm :)

  8. #8
    kapkong is offline Member
    Join Date
    Apr 2017
    Posts
    7
    Rep Power
    0

    Default Re: Trees - Difficulty with Recursion & Iterators

    @jim829

    It's an n-ary tree? It can have (theoretically) an infinite number of nodes due to it representing a file system of directories & files within those directories.

    And yeah, the traversal isn't too long, my main issue is my use of the .getChildren() iterator in my recursion, which appears to be faulty.

  9. #9
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Trees - Difficulty with Recursion & Iterators

    Perhaps I missed something but the ListNodes<> class does not seem to be present in your listing. And since that class must implement an iterator that may be where the problem lies. It looks like it implements Iterable too since you are calling iterator().

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  10. #10
    kapkong is offline Member
    Join Date
    Apr 2017
    Posts
    7
    Rep Power
    0

    Default Re: Trees - Difficulty with Recursion & Iterators

    @jim829

    My apologies, ListNodes.java was given to us.

    ListNodes.java
    Java Code:
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Iterator;
    import java.util.Comparator;
    
    public class ListNodes<T> {
    
    	ArrayList<T> list;
    	
    	public ListNodes() {
    		list = new ArrayList<T>();
    	}
    	
    	public void add(T element) {
    		list.add(element);
    	}
    	
    	public Iterator<T> sortedList(Comparator<T> sort) {
    		if (list.size() == 0) return null;
    		Collections.sort(list,sort);
    		return list.iterator();
    	}
    	
    	public Iterator<T> getList() {
    		return list.iterator();
    	}
    }

  11. #11
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,001
    Rep Power
    33

    Default Re: Trees - Difficulty with Recursion & Iterators

    In post#3, the code on line 26 starts a new method inside of the main method.
    If you don't understand my response, don't ignore it, ask a question.

  12. #12
    kapkong is offline Member
    Join Date
    Apr 2017
    Posts
    7
    Rep Power
    0

    Default Re: Trees - Difficulty with Recursion & Iterators

    Sorry Norm, I accidentally deleted the closing } when editing my code. Will fix.

  13. #13
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Trees - Difficulty with Recursion & Iterators

    I gave up on trying to run your code. You have too many errors which I didn't want to fix since it wouldn't help you. So I simply recommend you try to create the test cases and then print them out to ensure that 1) they were built correctly, and 2) your can traverse the data structure.

    And you said that the ListNodes class was provided to you. I find that bothersome because that implies to me it was provided by your teacher. And s/he misnamed the methods. For example, neither getList() nor getSortedList() return a list. They return an iterator. And in general, the class doesn't really serve a purpose. It simply wraps an ArrayList. So I would have just used TreeNode<List> and specified an ArrayList as the implementation.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Similar Threads

  1. Replies: 3
    Last Post: 12-11-2013, 07:17 PM
  2. Binary Search Trees - Weighting and Recursion
    By CeciliaP in forum New To Java
    Replies: 1
    Last Post: 03-28-2012, 09:32 AM
  3. Multi-iterators
    By philwei in forum New To Java
    Replies: 4
    Last Post: 10-04-2011, 10:58 PM
  4. Iterators
    By Archer in forum New To Java
    Replies: 5
    Last Post: 04-09-2011, 12:13 PM
  5. Understanding Iterators
    By Domo230 in forum New To Java
    Replies: 2
    Last Post: 02-12-2011, 12:03 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •