Universidad Carlos III de Madrid

public interface BTree<E> {
    // Each non-empty tree has two children, left and right.  This
    // constants will be used to tell one from the other, for example,
    // when inserting or extracting. Thanks to this we don't need to
    // duplicate the insert and extract methods into insertLeft,
    // insertRight, extractLeft and extractRight.
    //
    // The proper way to do this is by using an enum instead of static
    // final ints.
    static final int LEFT = 0;
    static final int RIGHT = 1;

    // Returns if the tree is empty.
    boolean isEmpty();

    // Return the info stored in the root of the tree, its left child
    // and its right child.
    //
    // BTreeExceptions are thrown if the tree is empty.
    E getInfo() throws BTreeException;
    BTree<E> getLeft() throws BTreeException;
    BTree<E> getRight() throws BTreeException;

    // Insert a tree at the specified child (LEFT or RIGHT).
    //
    // A BTreeException is thrown if the side is not LEFT or RIGHT or if
    // the tree where the insertion is to be made is empty
    void insert(BTree<E> tree, int side) throws BTreeException;

    // Returns and extract the specified child (LEFT or RIGHT)
    //
    // A BTreeException is thrown if the side is not LEFT or RIGHT or if
    // the tree where the extraction is to be made is empty
    BTree<E> extract(int side) throws BTreeException;

    // Generates a textual representation of the tree.
    //
    // toString defaults to pre-order.
    String toStringPreOrder();
    String toStringInOrder();
    String toStringPostOrder();
    String toString(); // pre-order

    // Returns the size of the tree (its number of nodes).
    // 0 for empty trees
    int size();
    // Returns the height of the tree (number of jumps between the root
    // and its deepest leaf).
    // -1 for empty trees.
    int height();

    // Returns if this tree is equal to another tree.
    //
    // Two trees are equal if their nodes hold equal information and if
    // they are distributed in the same way.
    boolean equals(BTree<E> tree);
    // Tells if a subtree equal to "tree" is stored in this tree.
    boolean find(BTree<E> tree);
}

public class Cities {

    public static void main(String[] args) {

        BTree<String> madrid = new LBTree<String>("Madrid");
        BTree<String> paris = new LBTree<String>("Paris");
        BTree<String> berlin = new LBTree<String>("Berlin");
        BTree<String> brussels = new LBTree<String>("Brussels");
        BTree<String> lima = new LBTree<String>("Lima");
        BTree<String> moscow = new LBTree<String>("Moscow");
        BTree<String> hanoi = new LBTree<String>("Hanoi");
        BTree<String> prague = new LBTree<String>("Prague");
        BTree<String> kiev = new LBTree<String>("Kiev");
        BTree<String> seoul = new LBTree<String>("Seoul");
        BTree<String> taipei = new LBTree<String>("Taipei");

        try {
            prague.insert(seoul, BTree.LEFT);
            prague.insert(taipei, BTree.RIGHT);
            moscow.insert(prague, BTree.LEFT);
            berlin.insert(lima, BTree.LEFT);
            berlin.insert(moscow, BTree.RIGHT);
            hanoi.insert(kiev, BTree.RIGHT);
            brussels.insert(hanoi, BTree.LEFT);
            paris.insert(brussels, BTree.LEFT);
            madrid.insert(paris, BTree.LEFT);
            madrid.insert(berlin, BTree.RIGHT);
        } catch (BTreeException e) {
            System.err.println("ERROR: " + e);
            return;
        }

        System.out.println("Madrid tree size = " + madrid.size());
        System.out.println("Madrid tree = " + madrid);
        System.out.println("Moscow tree size = " + moscow.size());
        System.out.println("Moscow tree = " + moscow.toStringPostOrder());
    }
}

public class BTreeException extends Exception {
    public BTreeException(String msg) {
        super(msg);
    }
}

class LBNode<E> {
    private E info;
    private BTree<E> left;
    private BTree<E> right;

    LBNode(E info, BTree<E> left, BTree<E> right) {
        this.left = left;
        this.right = right;
        this.info = info;
    }

    E getInfo() {
        return info;
    }

    void setInfo(E info) {
        this.info = info;
    }

    BTree<E> getLeft() {
        return left;
    }

    void setLeft(BTree<E> left) {
        this.left = left;
    }

    BTree<E> getRight() {
        return right;
    }

    void setRight(BTree<E> right) {
        this.right = right;
    }
}

public class LBTree<E> implements BTree<E> {
    private LBNode<E> root;

    public LBTree() {
        root = null;
    }

    public LBTree(E info) {
        root = new LBNode<E>(info, new LBTree<E>(), new LBTree<E>());
    }

    public boolean isEmpty() {
        return (root == null);
    }

    public E getInfo() throws BTreeException {
        if (isEmpty()) {
            throw new BTreeException("empty trees do not have info");
        }
        return root.getInfo();
    }

    public BTree<E> getLeft() throws BTreeException {
        if (isEmpty()) {
            throw new BTreeException("empty trees do not have a left child");
        }
        return root.getLeft();
    }

    public BTree<E> getRight() throws BTreeException {
        if (isEmpty()) {
            throw new BTreeException("empty trees do not have a right child");
        }
        return root.getRight();
    }

    public void insert(BTree<E> tree, int side) throws BTreeException {
        if (isEmpty()) {
            throw new BTreeException("cannot insert on an empty tree");
        }
        if (side == BTree.LEFT) {
            root.setLeft(tree);
        } else if (side == BTree.RIGHT) {
            root.setRight(tree);
        } else {
            throw new BTreeException("Invalid side argument");
        }
    }

    public BTree<E> extract(int side) throws BTreeException {
        BTree<E> retval;
        try {
            if (side == BTree.LEFT) {
                retval = getLeft();
                root.setLeft(new LBTree<E>());
            } else if (side == BTree.RIGHT) {
                retval = getRight();
                root.setRight(new LBTree<E>());
            } else {
                throw new BTreeException("Invalid side argument");
            }
        } catch (BTreeException e) {
            throw new BTreeException("cannot extract from an empty tree");
        }
        return retval;
    }

    public int size() {
        try {
            return 1 + getLeft().size() + getRight().size();
        } catch (BTreeException e) {
            return 0;
        }
    }

    public String toStringPreOrder() {
        try {
            return getInfo().toString() + " " +
                getLeft().toStringPreOrder() +
                getRight().toStringPreOrder();
        } catch (BTreeException e) {
            return "";
        }
    }

    public String toStringInOrder() {
        try {
            return getLeft().toStringInOrder() +
                getInfo().toString() + " " +
                getRight().toStringInOrder();
        } catch (BTreeException e) {
            return "";
        }
    }

    public String toStringPostOrder() {
        try {
            return getLeft().toStringPostOrder() +
                getRight().toStringPostOrder() +
                getInfo().toString() + " ";
        } catch (BTreeException e) {
            return "";
        }
    }

    public String toString() {
        return toStringPreOrder();
    }

    public int height() {
        try {
            int leftHeight = getLeft().height();
            int rightHeight = getRight().height();
            return 1 + Math.max(leftHeight, rightHeight);
        } catch (BTreeException e) {
            return -1;
        }
    }

    public boolean equals(BTree<E> tree) {
        try {
            return (getInfo().equals(tree.getInfo()) &&
                    getLeft().equals(tree.getLeft()) &&
                    getRight().equals(tree.getRight()));
        } catch (BTreeException e) {
            if (this.isEmpty() && tree.isEmpty()) {
                return true;
            } else {
                return false;
            }
        }
    }

    public boolean find(BTree<E> tree) {
        if (this.equals(tree)) {
            return true;
        } else {
            try {
                if (getLeft().find(tree)) {
                    return true;
                } else {
                    return (getRight().find(tree));
                }
            } catch (BTreeException e) {
                return false;
            }
        }
    }
}

The answer to both questions is yes. That's because our LBTree class inserts, extracts and searches generic trees that comply with BTree, without any hypothesis on how the trees are internally organized.

This is not a merit of our implementation. The merit comes from the BTree interface itself, which , for instance, makes us return generic BTree trees as a result of an extraction, instead of returning our own LBTree.

import java.util.ArrayList;

/**
 * Class representing a folder.
 * 
 * @author Dpt. of Telematic Engineering, University Carlos III of Madrid
 * 
 */
public class Folder {

    /** Name of the folder */
    private String name;

    /**
     * ArrayList containing the subdirectories stored by this folder
     */
    private ArrayList<Folder> subdirectories;

    /**
     * Constructor
     */
    public Folder() {
        this("default folder");
    }

    /**
     * Constructor
     * 
     * @param name
     *          Name of the folder.
     */
    public Folder(String name) {
        this.name = name;
        this.subdirectories = new ArrayList<Folder>();
    }

    /**
     * Get the name of the folder.
     * 
     * @return a String reference to the name of the folder.
     */
    public String getName() {
        return this.name;
    }

    /**
     * Set the name of the folder.
     * 
     * @param name
     *          New name of the folder.
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * Get the vector of subdirectories.
     * 
     * @return a reference to the vector containing the subdirectories.
     */
    public ArrayList<Folder> getSubdirectories() {
        return this.subdirectories;
    }

    /**
     * Add a new folder as subdirectory of this folder.
     * 
     * @param folderName
     *          Name of the new folder.
     * @return a reference to the new folder.
     */
    public Folder addSubdirectory(String folderName) {
        Folder newFolder = new Folder(folderName);
        subdirectories.add(newFolder);
        return newFolder;
    }

    /**
     * Print in screen the subdirectories of the folder with the format:
     * subdirectory1 subdirectory2 ... subdirectoryN
     */
    public void printSubdirectories() {
        for (int i = 0; i < subdirectories.size(); i++) {
            System.out.print(subdirectories.get(i).getName() + " ");
        }
        System.out.println();
    }
}

/**
 * Class representing the file system.
 * 
 * @author Dpt. of Telematic Engineering, University Carlos III of Madrid
 * 
 */
public class FileSystem {

    /** File system (tree) root */
    private Folder root;

    /**
     * Constructor.
     */
    public FileSystem() {
        this("default");
    }// end constructor

    /**
     * Constructor.
     * 
     * @param rootFolderName
     *          Name of the root folder
     */
    public FileSystem(String rootFolderName) {
        root = new Folder(rootFolderName);
    }// end constructor

    /**
     * Search the folder specified as parameter in the file system, and return a
     * reference to the folder if it exists or null otherwise.
     * 
     * @param folderName
     *          Name of the folder to search.
     * @return a reference to the folder if it is in the file system, or null
     *         otherwise.
     */
    public Folder searchFolder(String folderName) {
        // It calls the auxiliary search method
        return searchFolder(root, folderName);
    }// end searchFolder

    /**
     * Search the folder specified as parameter in the file system, and return a
     * reference to the folder if it exists or null otherwise. This method is
     * recursive and is applied over each subtree by specifying the root of that
     * subtree in each case.
     * 
     * @param rootFolder
     *          Root of each subtree over which the search method is applied.
     * @param folderName
     *          Name of the folder to be searched.
     * @return a reference to the folder being searched if it is in the file
     *         system, or null otherwise.
     */
    private Folder searchFolder(Folder rootFolder, String folderName) {
        // Reference to the folder we are searching for
        Folder searchedFolder = null;
        // Boolean to indicate that we have found the folder
        boolean found = false;

        if (rootFolder != null) { // Check if the tree is not empty
            if (rootFolder.getName().equals(folderName)) {
                // If the current folder is the one being searched,
                // save it in the variable searchedFolder...
                searchedFolder = rootFolder;
            } else {
                // ...else, apply the search method over each subtree
                // which root is each of the subdirectories of the
                // current folder, until it is found
                for (int i = 0; i < rootFolder.getSubdirectories().size() && !found; i++) {
                    searchedFolder = searchFolder(rootFolder.getSubdirectories().get(i),
                                                  folderName);
                    if (searchedFolder != null) {
                        // if we have found the folder, we stop searching
                        found = true;
                    }
                }
            }
        }
        return searchedFolder;
    }// end searchFolder

    /**
     * Add a new folder of the specified name, as a subdirectory of the folder
     * specified in the first parameter. If there exists a folder with name
     * newFolderName in the file system, or if parentFolderName does not exist,
     * the method does nothing and returns null. Otherwise it returns a reference
     * to the new folder.
     * 
     * @param parentFolderName
     *          Name of the parent folder.
     * @param newFolderName
     *          Name of the new folder.
     * @return a reference to the new folder, or null if there exists a folder
     *         with newFolderName in the file system of if the parent folder does
     *         not exist.
     */
    public Folder addNewFolder(String parentFolderName, String newFolderName) {
        // Search the parent folder
        Folder parentFolder = searchFolder(parentFolderName);
        // Search if there exists a folder with newFolderName name
        Folder newFolder = searchFolder(newFolderName);

        // If the parent folder exists and no newFolderName exists in the file
        // system...
        if (parentFolder != null && newFolder == null) {
            // ...then add the directory...
            newFolder = parentFolder.addSubdirectory(newFolderName);
        } else { // ...otherwise...
            // ...return null and show some message in screen.
            newFolder = null;
            if (parentFolder == null) {
                System.out.println("The folder cannot be added because "
                                   + "the parent folder \"" + parentFolderName + "\" does not exist.");
            } else {
                System.out.println("The folder cannot be added because "
                                   + "there is already another folder with the same name");
            }
        }
        return newFolder;
    }// end addNewFolder

    /**
     * Print the file system structure in screen.
     */
    public void printFileSystem() {
        // Call an auxiliary recursive method.
        printFileSystem(0, root);
    }// end printFileSystem

    /**
     * Print the file system structure in screen. This method is recursive, and is
     * called over each subtree by specifying the root of the corresponding
     * subtree.
     * 
     * @param level
     *          Tree level where the root of the subtree is.
     * @param root
     *          Root folder of the subtree over which the method is applied.
     */
    private void printFileSystem(int level, Folder root) {
        // Check if the current root is not null
        if (root != null) {
            if (level > 0) {
                // If level is greater than 0 (the root is not
                // the root of whole file system)...
                for (int i = 0; i < level; i++) {
                    // ...print as many white spaces as levels...
                    System.out.print("  ");
                }
                // ...and print the symbol representing the directory...
                System.out.print("|_");
            }
            // ...print the name of the folder
            System.out.println(root.getName());
            for (int j = 0; j < root.getSubdirectories().size(); j++) {
                // Take each subdirectory as root of a subtree, and
                // apply the method over that subtree
                printFileSystem(level + 1, root.getSubdirectories().get(j));
            }
        }
    }// end printFileSystem
}

/**
 * Class for testing purposes.
 * 
 * @author Dpt. of Telematic Engineering, University Carlos III of Madrid
 * 
 */
public class FileSystemTest {

    /**
     * Testing main.
     */
    public static void main(String[] args) {
        /*
         * First, we check the proper working of Folder class
         */
        // Create several folder objects representing
        // different folders
        Folder folderC = new Folder("C");

        // Check the getName method
        System.out.println(folderC.getName());

        // Check the setName method
        folderC.setName("C:");
        System.out.println(folderC.getName());

        // Check the printSubdirectories when there are
        // no subdirectories added
        folderC.printSubdirectories();

        // Add one subdirectory
        folderC.addSubdirectory("Program Files");

        // Check the printSubdirectories when there is
        // only one subdirectory added
        folderC.printSubdirectories();

        // Add some more subdirectories
        folderC.addSubdirectory("My Documents");
        folderC.addSubdirectory("Windows");

        // Check the printSubdirectories when there are
        // several subdirectories added
        folderC.printSubdirectories();

        /*
         * Once we have checked the proper working of the Folder class, we test the
         * FileSystem class.
         */
        // Create the file system
        FileSystem fs = new FileSystem("C:");
        fs.printFileSystem();

        // Add a new folder not contained in the file system
        fs.addNewFolder("C:", "Program Files");
        fs.printFileSystem();

        // Add a new folder
        fs.addNewFolder("Program Files", "Java");
        fs.printFileSystem();

        // Add a new folder as subdirectory of a folder
        // which is not in the file system
        fs.addNewFolder("Windows", "MyFolder");

        // Add several folder, and see if they are
        // printed as expected
        fs.addNewFolder("C:", "My Documents");
        fs.addNewFolder("My Documents", "Images");
        fs.addNewFolder("My Documents", "Video");
        fs.addNewFolder("My Documents", "Music");
        fs.addNewFolder("My Documents", "Text Documents");
        fs.addNewFolder("Music", "Old Music");
        fs.printFileSystem();
    }
}