Member Avatar for gheorghe gardu
gheorghe gardu 0 Newbie Poster

Hello, I would like to ask if you can give me some help.
I have to implement a slicing tree that represent a slicing floorplan(slicing floorplan divides a rectangle with horizontal and vertical cuts, and can be represented by a binary tree, called slicing tree. Its internal nodes are the cuts, and external nodes are the basic rectangles into which the floorplan is decomposed by the cuts.)
And I should solve the compaction problem, i.e. to find the smallest possible height and width for each rectangle of the slicing floorplan that is compatible with the minimum dimensions of the basic rectangles.
(this problem is similar with Goodrich and Tamassia Data Structures and algorithmts book, 4th edition, page 444-445).

w(v) = w -if v is an external node whose basic rectangle has minimum weight w.
w(v)= max(w(w),w(z)) if v is an internal node associated with a horizontal cut with left child w and right child z.
w(v) = w(w) + w(z) -if v is an internal node associated with a vertical cut with left child w and right child z.

h(v) = h -if v is an external node whose basic rectangle has minimum height h.
h(v) =h(w) + h(z) -if v is an internal node associated with a horizontal cut with left child w and right child z.
h(v) = max(h(w), h(z)) if v is an internal node associated with a vertical cut with left child w and right child z.

So, I have written a driver program (FileRead.java), which creates an instance of a SlicingTree class, and gradually constructs the tree as follows. It reads directives from the file test.txt, and each line indicate an operation to be performed on the tree. There is one directive per line. Each directive consists of the name of the directive followed by 0 or more arguments, separated by tab. Here are the possible directives and their meanings


create-root L //create the root of the tree and label it as L
cut-h L LC LR //divide the node labeled L into two by a horizontal cut,
//label bottom(left) child as LC, label top(right) child as LR
cut-v L LC LR //divide the node labeled L into two by a vertical
//cut, label the left child as LC, label the right child as LR
assign-w L x //set the width of the node labeled as L to x
assign-h L x //set the height of the node labeled as L to x compact
//Perform the compaction algorithm on the tree display Display the tree as described above
quit //this is the last directive

Also, I have written the SlicingTree.java, where I defined the class for slicing tree. It compiles without errors.
When I compile FileRead.java, I have errors like: cannot find symbol; symbol class STNode, location class FileRead and "cut_horizontal (STNode) in FileRead cannot be applied to () cut_horizontal();"

//FileRead.java for hw4 slicing tree

import java.io.*;
import java.util.*;

class FileRead
{
public static int create_root()
{

	return 0;
}

public static int cut_horizontal(STNode v)
{

	return 0;
}

public static int cut_vertical(STNode v)
{

	return 0;
}

public static int assign_width(STNode v, int width)
{

	return 0;
}

public static int assign_height(STNode v, int height)
{

	return 0;
}

public static int assign_label(STNode v, char label)
{

	return 0;
}


public static int compact()
{

	return 0;
}

public static int display()
{

	return 0;
}

public static void main(String[] args)
{
//Open the file that is the first command line parameter
FileInputStream fstream = new FileInputStream("test.txt");

//get the object of DataInpjutStream
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String strLine;

//read file line by line
while((strLine = br.readLine()) != null)
{
//print the content on the console
System.out.println(strLine);

if(strLine == "create-root L ")
	{
	create_root();
	}

if(strLine == "create-root L ")
	{
	create_root();
	}

if(strLine == "cut-h L LC LR ")
	{
	cut_horizontal();
	}

if(strLine == "cut-v L LC LR")
	{
	cut_vertical();
	}

if(strLine == "assign-w L X")
	{
	assign_width();
	}

if(strLine == "assign-h L X")
	{
	assign_height();
	}

if(strLine == "compact")
	{
	compact();
	}

if(strLine == "display")
	{
	display();
	}

if(strLine == "quit")
	{
	quit();
	}


//close the input stream	
in.close();
	}
   }
}
//SlicingTree.java

import java.io.IOException;
import java.io.BufferedReader;
import java.io.*;
import java.util.*;

//Class for a slicing tree that stores Object objects.

public class SlicingTree
{

  /** Class to encapsulate a tree node. */
  protected static class STNode 
  {
    // Data Fields
    /** The information stored in this node. */
    protected Object data;
    /** Reference to the left child. */
    protected STNode left;
    /** Reference to the right child. */
    protected STNode right;

// Constructors
//Construct a node with given data and no children.
//param data The data to store in this node
public STNode(Object data) 
	 {
      this.data = data;
      left = null;
      right = null;
    }

    // Methods
    /** Return a string representation of the node.
        @return A string representation of the data fields
     */
    public String toString() 
	 {
      return data.toString();
    }
  }

  // Data Field
  /** The root of the slicing tree */
  protected STNode root;

  public SlicingTree() 
  {
    root = null;
  }

  protected SlicingTree(STNode root) 
  {
    this.root = root;
  }

  /** Constructs a new slicing tree with data in its root,
      leftTree as its left subtree and rightTree as its
      right subtree.
   */
  public SlicingTree(Object data, SlicingTree leftTree, SlicingTree rightTree) 
  {
    root = new STNode(data);
    if (leftTree != null) {
      root.left = leftTree.root;
    }
    else {
      root.left = null;
    }
    if (rightTree != null) {
      root.right = rightTree.root;
    }
    else {
      root.right = null;
    }
  }

//Return the left subtree.
//return The left subtree or
//             null if either the root or the
//             left subtree is null
public SlicingTree getLeftSubtree() 
  {
    if (root != null && root.left != null) 
	 {
      return new SlicingTree(root.left);
    }
    else 
	 {
      return null;
    }
  }

//Return the right sub-tree
//return the right sub-tree or
//        null if either the root or the
//        right subtree is null.
public SlicingTree getRightSubtree() 
  {
    if (root != null && root.right != null) 
	 {
      return new SlicingTree(root.right);
    }
    else {
      return null;
    }
  }

//Determine whether this tree is a leaf.
//return true if the root has no children
boolean isLeaf() 
  {
    return (root.left == null && root.right == null);
  }

  public String toString() 
  {
    StringBuffer sb = new StringBuffer();
    preOrderTraverse(root, 0, sb);
    return sb.toString();
  }

//Perform a preorder traversal.
//    @param node The local root
//    @param depth The depth
//    @param sb The string buffer to save the output
private void preOrderTraverse(STNode node, int depth, StringBuffer sb) 
  {
    for (int i = 0; i < depth; i++) 
	 {
      sb.append("  ");
    }
    if (node == null) 
	 {
      sb.append("null\n");
    }
    else 
	 {
      sb.append(node.toString());
      sb.append("\n");
      preOrderTraverse(node.left, depth + 1, sb);
      preOrderTraverse(node.right, depth + 1, sb);
    }
  }

//Method to read a slicing tree.
//pre: The input consists of a preorder traversal
//      of the slicing tree. The line "null" indicates a null tree.
//     @param bR The input file
//      @return The binary tree
//      @throws IOException If there is an input error
public static SlicingTree readSlicingTree (BufferedReader bR) throws IOException {
    // Read a line and trim leading and trailing spaces.
    String data =bR.readLine().trim();
    if (data.equals("null")) 
	 {
      return null;
    }
    else 
	 {
      SlicingTree left = readSlicingTree(bR);
      SlicingTree right = readSlicingTree(bR);
      return new SlicingTree(data, left, right);
    }
  }

//Return the data field of the root
//        @return the data field of the root
//        or null if the root is null
  public Object getData() 
  {
    if (root != null) 
	 {
      return root.data;
    }
    else 
	 {
      return null;
    }
  }
}
  • 1 Contributor
  • 0 Replies
  • 58 Views
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.