6 Replies Latest reply: Nov 15, 2008 11:12 PM by 800308 RSS

    Listing File Hierarchy in console using a Tree structure

    843785
      first off i'm a college student. i'm not that good at java... we got this CA in class and try as i might i just can't get my head around it

      i was wondering if someone who know a bit more about java then i do would point me in the right direction, were i'm going wrong in my code


      i have to list out sub-files and sub-directorys of a folder (i.e. C:/test) to console using tree structure

      like this

      startingdir
      dir1 //subfolder of startingdir
      dir11 //subfolder of dir1
      dir111 //subfolder of dir11
      dir12 //subfolder of dir1
      file1A // document on dir1
      dir2 //subfolder of startingdir



      Tree.java
      import java.util.Iterator;
      import java.util.LinkedList;
      import java.util.ListIterator;
      import java.util.NoSuchElementException;
      import java.util.Deque;
      
      public class Tree<E> {
          // Each Tree object is an unordered tree whose
          // elements are arbitrary objects of type E.
          // This tree is represented by a reference to its root node (root), which
          // is null if the tree is empty. Each tree node contains a link to its 
          // parent and a LinkedList of child nodes
      
          private Node root;
      
          //////////// Constructor ////////////
      
          public Tree () {
          // Construct a tree, initially empty.
              root = null;
          }
      
          //////////// Accessors ////////////
      
          public boolean isEmpty () {
          // Return true is and only if this tree is empty.
               return (root == null);
          }
      
          public Node root () {
          // Return the root node of this tree, or null if this tree is empty.
              return root;
          }
      
          public Node parent (Node node) {
          // Return the parent of node in this tree, or null if node is the root node.
              return node.parent;
          }
      
          
          public void makeRoot (E elem) {
          // Make this tree consist of just a root node containing element elem.
              root = new Node(elem);
          }
      
          public Node addChild (Node node, E elem) {
          // Add a new node containing element elem as a child of node in this
          // tree. The new node has no children of its own. Return the node
          // just added.
              
              Node newChild = new Node(elem);
              newChild.parent = node;
              node.children.addLast(newChild);
              
              return newChild;
          }
      
          public E element (Node node) {
               return node.getElement();
          }
      
          //////////// Iterators ////////////
      
          public Iterator childrenIterator (Node node) {
              return node.children.iterator();
          }
          
          public Iterator nodesPreOrder () {
          // Return an iterator that visits all nodes of this tree, with a pre-order
          // traversal.
              return new Tree.PreOrderIterator();
          }
      
          //////////// Inner classes ////////////
      
          public class Node {
              // Each Tree.Node object is a  node of an
              // unordered tree, and contains a single element.
              // This tree node consists of an element (element), 
              // a link to its parent
              // and a LinkedList of its children
              
              private E element;
              private Node parent;
              private LinkedList<Node> children;
      
              private Node (E elem) {
                  // Construct a tree node, containing element elem, that has no
                  // children and no parent.
                  this.element = elem;
                  this.parent = null;
                  children = new LinkedList<Node>();
              }
      
              public E getElement () {
              // Return the element contained in this node.
                  return this.element;
              }
      
              public String toString () {
              // Convert this tree node and all its children to a string.
                  String children = "";
                  // write code here to add all children 
                  
                  return element.toString() + children;
              }
      
              public void setElement (E elem) {
              // Change the element contained in this node to be elem.
                  this.element = elem;
              }
          }
          
          public class PreOrderIterator implements Iterator {
      
              private Deque<Node> track; //Java recommends using Deque rather 
              // than Stack. This is used to store sequence of nomempty subtrees still 
              //to be visited
              
              private PreOrderIterator () {
                  track = new LinkedList();
                  if (root != null)
                      track.addFirst(root);
              }
      
              public boolean hasNext () {
                  return (! track.isEmpty());
              }
      
              public E next () {
                  Node place = track.removeFirst();
                  
                  //stack the children in reverse order
                  if (!place.children.isEmpty()) {
                      int size = place.children.size(); //number of children
                      ListIterator<Node> lIter =
                              place.children.listIterator(size); //start iterator at last child
                      while (lIter.hasPrevious()) {
                          Node element = lIter.previous();
                          track.addFirst(element);
                      }
                  }
                  return place.element;
              
              }
                  
              public void remove () {
                  throw new UnsupportedOperationException();
              }
          }
      }
          
      FileHierarchy.java
      import java.io.File;
      import java.util.Iterator;
      
      public class FileHierarchy {
          // Each FileHierarchy object describes a hierarchical collection of 
          // documents and folders, in which a folder may contain any number of 
          // documents and other folders. Within a given folder, all documents and 
          // folders have different names.
          // This file hierarchy is represented by a tree, fileTree, whose elements 
          // are Descriptor objects.
          
          private Tree fileTree;
          
          //////////// Constructor ////////////
          public FileHierarchy (String startingDir, int level) {
              // Construct a file hierarchy with level levels, starting at 
              // startingDir
              // Can initially ignore level and construct as many levels as exist
              
              fileTree = new Tree();
              Descriptor descr = new Descriptor(startingDir, true);
              
              fileTree.makeRoot(descr);
              int currentLevel = 0;
              int maxLevel = level;
              
              addSubDirs(fileTree.root(), currentLevel, maxLevel);
              
          }
          //////////// File hierarchy operations ////////////
          private void addSubDirs(Tree.Node currentNode, int currentLevel, 
                  int maxLevel) {
          // get name of directory in currentNode
          // then find its subdirectories (can add files later)
          // for each subdirectory:
          //    add it to children of currentNode - call addChild method of Tree
          //    call this method recursively on each child node representing a subdir
          // can initially ignore currentLevel and maxLevel    
              
              Descriptor descr = (Descriptor) currentNode.getElement();
              File f = new File(descr.name);
              File[] list = f.listFiles();
              for (int i = 0; i < list.length; ++i) {
                  if (list.isDirectory()) {
      File[] listx = null;
      fileTree.addChild(currentNode, i);
      if (list[i].list().length != 0) {
      listx = list[1].listFiles();
      addSubDirs(currentNode,i,1);
      }
      } else if (list[i].isFile()) {
      fileTree.addChild(currentNode, i);
      }
      }



      // The following code is sample code to illustrate how File class is
      // used to get a list of subdirectories from a starting directory
      // list now contains subdirs and files
      // contained in dir descr.name

      }

      ////////// Inner class for document/folder descriptors. //////////
      private static class Descriptor {
      // Each Descriptor object describes a document or folder.
      private String name;
      private boolean isFolder;

      private Descriptor (String name, boolean isFolder) {
      this.name = name;
      this.isFolder = isFolder;
      }
      }

      }
      FileHierarchyTest.java
      public class FileHierarchyTest {

      private static Tree fileTree;

      public static void main(String[] args) {
      FileHierarchy test = new FileHierarchy ("//test", 1);
      System.out.println(test.toString());
      }
      }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          
        • 1. Re: Listing File Hierarchy in console using a Tree structure
          843785
          Must you use that tree structure? If not, here's how I'd do it:
          main {
            processFolder(new File("C:\\Test"), 0); // level 0 means no spaces before the root
          }
          
          processFolder(File f, int level) {
            processFile(f, level); // print out the name just like processFile
            File[] = list f's files
            for each file innerF in f {
              if it's a directory, processFolder(innerF, level + 1);
              else processFile(innerF, level + 1);
            }
          }
          
          processFile(File f, int level) {
            for (int i = 0; i < level; i++)
              System.out.print(' ');
            System.out.println(f.getName());
          }
          Edited by: Looce on Nov 14, 2008 3:06 PM
          forgot my closing (pseudo)code tag
          • 2. Re: Listing File Hierarchy in console using a Tree structure
            843785
            thank for the reply... :) unfortunately it has to be a tree structure.

            i will have another go at it see if i can get it working
            • 3. Re: Listing File Hierarchy in console using a Tree structure
              800308
              Denis,

              Do you have [red hair|http://www.dennisthemenace.com/]? ;-)

              My advise with the tree structure is pretty short and sweet... make each node remember
              1. it's parent
              2. it's children

              That's how the file system (inode) actually works.

              <quote>
              The exact reasoning for designating these as "i" nodes is unsure. When asked, Unix pioneer Dennis Ritchie replied:[citation needed]
              In truth, I don't know either. It was just a term that we started to use. "Index" is my best guess, because of the
              slightly unusual file system structure that stored the access information of files as a flat array on the disk, with all
              the hierarchical directory information living aside from this. Thus the i-number is an index in this array, the
              i-node is the selected element of the array. (The "i-" notation was used in the 1st edition manual; its hyphen
              became gradually dropped).
              </quote>
              • 4. Re: Listing File Hierarchy in console using a Tree structure
                800308
                Doh! I see you've allready done that.
                • 5. Re: Listing File Hierarchy in console using a Tree structure
                  843785
                  i figured it out... thank for help anyway
                  • 6. Re: Listing File Hierarchy in console using a Tree structure
                    800308
                    Dennis... Would you care to please post your latest then... I admit I gave up on it about 2am last night.

                    I can recurse the sooker ok (my "on add" debug prints look fine)... but my resulting tree is totally stuffed... I keep "backtracking" up the tree somehow... and I'm supposed to be "good" at this programming stuff (ergo I do it for a living), but I'll be stuffed if I can figure it out, even with a debugger.

                    Cheers Mate. Keith.