[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Need help debugging; linked list-type structure

Posted on 2004-11-21
11
Medium Priority
?
168 Views
Last Modified: 2013-11-20
Hello Experts!

I have been fighting with one problem for the past three weeks and I haven't been able to solve it for the life of me. After spending the past four hours and then finally giving up, I am here to beg for help! I will paste all of the classes involved, as I have extracted the fundamentals to pinpoint the problem. The program is to be eventually used for filling a polygon manually (without the built-in goodies). The code is pasted below:

0
Comment
Question by:TZRick
  • 8
9 Comments
 
LVL 1

Author Comment

by:TZRick
ID: 12641241
import java.awt.*;
import java.awt.event.*;
import java.util.*;

class Temp2 extends Frame {
   
    EdgeTable et = new EdgeTable ();
    ActiveEdgeTable aet = new ActiveEdgeTable ();
      
      private void code () {
            
            ArrayList points = new ArrayList ();
            points.add (new Point (20, 30));
            points.add (new Point (70, 40));
            points.add (new Point (65, 100));
            points.add (new Point (15, 105));
                points.add (new Point (20, 40));
                Edge edge = new Edge (20, 30, 70, 40);
                Edge edge2 = new Edge (70, 40, 65, 100);
                               
            et.populateTable (points);
                Edge edge4 = et.getRow (40).getTableObject().getEdgeAt(1);
                //aet.addToRear (edge4);                                       // This line works
                Edge edge5 = et.getRow (40).getTableObject ().getEdgeAt (0);
                //aet.addToFront (edge5);                                      // This line works
                //aet.printTable ();                                                // The results are printed here fine
            //et.printTable ();                                                // This line works also
                processPoints (this.getGraphics(), Color.BLUE);
            
            return;
      }
       
       private void processPoints (Graphics g, Color chosencolor) {
            
            int count = 0;
            boolean inside = false;
                                    
            for (int i = 0; i < 1000; i++) { //y-coordinates
                  
                  if (aet.size () == 0 && count == et.size () - 1) {
                           
                            break;
                        }
               
                  if (et.getRow (i) != null){
                        System.out.println ("Y-Value: " + i);
                        aet.preDrawUpdate (et.getRow (i));
                        
                  } }/*
                        
                  aet.sortOnX ();
                  
                  for (int j = 0; j < 1000; j++) {
                        
                        for (int k = 0; k < aet.size (); k++) {
                              
                              if (aet.getEdgeAt (k).getx0 () == j) {
                                    
                                    inside = !inside;
                              }
                              
                              if (inside)
                                    putPixel (g, j, i, chosencolor);
                        }                                    
                  }
                  
                  
                  //aet.postDrawUpdate (i);
                  aet.printTable();                  
                  
            }
            System.out.println ("Painter.processPoints complete.");*/
            
                  
            return;
      }
      
      public Temp2() {
            addWindowListener(new WindowAdapter() {
                  public void windowClosing(WindowEvent e) {
                        dispose();
                        System.exit(0);
                  }
            });
            code ();
            
            return;
      }

      public static void main(String args[]) {
            System.out.println("Starting Temp2...");
            Temp2 mainFrame = new Temp2();
            mainFrame.setSize(400, 400);
            mainFrame.setTitle("Temp2");
            mainFrame.setVisible(false);
      }
}
0
 
LVL 1

Author Comment

by:TZRick
ID: 12641243
import java.awt.*;
import java.io.*;

class Edge {
      
      public Edge () {
            
            this.setx0 (0);
            this.setYMin (0);
            this.setYMax (0);
            this.setMInv (1);
            this.setB (0);
            this.setNext (null);
            this.setPrevious (null);
            
            return;
      }
      
      public Edge (int x0, int y0, int x1, int y1) {
            
            Point p0 = new Point (x0, y0);
            Point p1 = new Point (x1, y1);
            this.setNext (null);
            this.setPrevious (null);
                        
            makeEdge (p0, p1);
            
            return;
      }
      
      public Edge (Point p0, Point p1) {
            
            makeEdge (p0, p1);
            this.setNext (null);
            this.setPrevious (null);
            
            return;
      }
      
      public boolean includesPoint (Point pt) {
            
            boolean decision = false;
            
            int x = Math.round ((float)(getMInv () * pt.getY () + b));
            decision = (x == pt.getX ()? true:false);
                        
            return decision;
      }
      
      private void makeEdge (Point p0, Point p1) {
            
            Point temp;
            
            if (p0.getY() > p1.getY()) {
                  
                  temp = p0;
                  p0 = p1;
                  p1 = temp;
            }            
            
            double dx, dy, m;
            
            dy = p1.getY () - p0.getY ();
            dx = p1.getX () - p0.getX ();
            
            m = dy/dx;
                        
            setMInv (1/m);
            setx0 (p0.getX ());
            setYMax (p1.getY ());
            setB (p0.getX () - p0.getY ()/m);
                              
            return;
      }
      
      public void printEdge () {
            
            FileOutputStream out; // declare a file output object
            PrintStream p; // declare a print stream object
            
            try {
                  // Create a new file output stream
                  // connected to "myfile.txt"
                  //out = new FileOutputStream("edgeOutput.txt", true);

                  // Connect print stream to the output stream
                  //p = new PrintStream (out);
                  //p.println ("Ymax: " + getYMax () + " x0: " + getx0 () +
                  //" MInv: " + getMInv () + " b: " + b);
                        System.out.println ("Ymax: " + getYMax () + " x0: " + getx0 () +
                  " MInv: " + getMInv () + " b: " + b);
                  //p.close ();
            }
            catch (Exception e) {
                  
                  System.err.println ("Error writing to file");
            }
            
            //System.out.println ("Ymax: " + getYMax () + " x0: " + getx0 () +
            //      " MInv: " + getMInv () + " b: " + b);
            
            return;
      }
      
      public void setTo (Edge value) {
            
            this.setx0 (value.getx0 ());
            this.setYMin (value.getYMin ());
            this.setYMax (value.getYMax ());
            this.setMInv (value.getMInv ());
            this.setB (value.getB ());
            
            return;
      }
      
      public Point getInitialPoint () {
            
            int y = (int) ((1/getMInv ()) * getx0 () + getB ());
            int x = (int) getx0 ();
            Point value = new Point (x, y);
            
            return value;
      }
      
      public double getB () {
            
            return b;
      }
      
      public void setB (double value) {
            
            b = value;
            
            return;
      }
      
      public double getMInv () {
            
            return m_inv;
      }
      
      public void setMInv (double value) {
            
            m_inv = value;
            
            return;
      }
      
      public double getx0 () {
            
            return x_min;
      }
      
      public void setx0 (double value) {
            
            x_min = value;
            
            return;
      }
      
      public double getYMin () {
            
            return y_min;
      }
      
      public void setYMin (double value) {
            
            y_min = value;
            
            return;
      }
      
      public double getYMax () {
            
            return y_max;
      }
      
      public void setYMax (double value) {
            
            y_max = value;
            
            return;
      }
      
      public Edge getNext () {
            
            return next;
      }
      
      public Edge getPrevious () {
            
            return previous;
      }
      
      public void setNext (Edge edge) {
            
            next = edge;
            
            return;
      }
      
      public void setPrevious (Edge edge) {
            
            previous = edge;
            
            return;
      }
      
      private double y_max, y_min, x_min;
      private double m_inv, b;
      private Edge next = null;
      private Edge previous = null;
}
0
 
LVL 1

Author Comment

by:TZRick
ID: 12641248
class TableObject {
      
      public TableObject () {
           
               head = new Edge ();
               head.setPrevious (null);
               head.setNext (null);
               tail = head;
            
            return;
      }
       
             public void addToRear (Edge edge) {
            
            if (head.getNext () == null) {
                   
                    head.setNext (edge);
                    head.getNext ().setPrevious (head);
                    head.getNext ().setNext (null);
                    tail = head.getNext ();
                }
                else {
                   
                    edge.setNext (null);
                    edge.setPrevious (tail);
                    tail = edge;
                    tail.getPrevious ().setNext (tail);
                }
                iSize++;
                   
            return;
      }
      
      public void addToFront (Edge value) {
            
            if (head.getNext () == null) {
               
                value.setNext (null);
                value.setPrevious (head);
                head.setNext (value);
               
            }
            else {
           
                head.getNext ().setPrevious (value);
                value.setNext (head.getNext ());
                head.setNext (value);
                value.setPrevious (head);
            }
            iSize++;

            return;
      }
      
      public void insertEdgeAt (int index, Edge value) {
            
            if (index == 0) {
                  
                  addToFront (value);
                        iSize++;
                       
                  return;
            }
            
            Edge temp = this.getEdgeAt (index);
            
            temp.getPrevious ().setNext (value);
            value.setPrevious (temp.getPrevious ());
            value.setNext (temp);
            temp.setPrevious (value);
                iSize++;
                  
            return;      
      }
      
      public Edge getEdgeAt (int index) {
            
            Edge temp = head.getNext ();
            
            for (int counter = 0; counter <= index; counter++) {
            
                  if (counter == index) return temp;
                  
                  if (temp.getNext () == null) return null;
                  
                  temp = temp.getNext ();
            }
            
            return null;            
      }
      
      public void printTable () {
            
            Edge temp = head.getNext ();
                System.out.println ("Empty head");
                        
            for (;;) {
            
                  if (temp == null) {
                  
                        return;
                  }
            
                  temp.printEdge ();
                  if (temp == tail) break;
                  temp = temp.getNext ();
            }
            
            return;
      }
      
      public void removeLast () {
            
            if (tail == null) {iSize = 0; /*No edges detected*/}
            else {
                tail = tail.getPrevious ();
                tail.getNext ().setPrevious (null);
                tail.setNext (null);
                iSize--;
            }
            
            return;      
      }
      
      public void removeEdgeAt (int index) {
            
            if (index == 0) {
                  
                  removeFirst ();
                  return;
            }
            
            if (index == this.size () - 1) {
                  
                  removeLast ();
                  return;
            }
            
            if (index > this.size () - 1) {
                  
                  return;
            }
            
            Edge current = this.getEdgeAt (index);
            Edge previous = current.getPrevious ();
            Edge next = current.getNext ();
            
            previous.setNext (next);
            next.setPrevious (previous);
            current.setPrevious (null);
            current.setNext (null);
                iSize--;
            
            return;
      }
      
      private void removeFirst () {
            
            if (head.getNext () != null) {
                   
                    Edge temp = head.getNext ().getNext ();
                    head.getNext ().setPrevious (null);
                    head.getNext ().setNext (null);
                    head.setNext (temp);
                    temp.setPrevious (head);
                }
                else { iSize = 0; }
                iSize--;

                return;
      }
      
      public void setEdgeAt (int index, Edge value) {
            
            Edge temp = this.getEdgeAt (index);
            temp.setTo (value);            
            
            return;
      }
      
      public int size () {
            
            return iSize;
      }
      
      public Edge getHead () {
            
            return head;
      }
      
      public double getXIncrement () {
            
            return xincrement;
      }
      
      public void setXIncrement (double value) {
            
            xincrement = value;
            
            return;
      }
      
      public double getNumerator () {
            
            return numerator;
      }
      
      public void setNumerator (double value) {
            
            numerator = value;
            
            return;
      }
      
      public double getDenominator () {
            
            return denominator;
      }
      
      public void setDenominator (double value) {
            
            denominator = value;
            
            return;
      }
      
      private Edge head = null;
        private Edge tail = null;
      private int iSize = 0;
        private double xincrement = 0;            // Used only in AET printing
      private double numerator = 0;            // Used only in AET printing
      private double denominator = 0;            // Used only in AET printing
}
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 1

Author Comment

by:TZRick
ID: 12641250
import java.awt.*;
import java.util.*;

class EdgeTable extends ArrayList {
      
      public EdgeTable () {
           
            return;
      }
       
        public row getRow (int index) {
           
            row temp = new row ();
           
            for (int counter = 0; counter < this.size (); counter++) {
               
                temp = (row) this.get (counter);
               
                if (temp.getRowIndex() == index) return temp;
            }
           
            return null;
        }
      
      public void populateTable (ArrayList points) {
            
            Point a, b;
            Edge temp;
            int index = 0;
            
            // points does not include redundant last point
            for (int counter = 0; counter < points.size () - 1; counter++) {
                  
                  a = (Point) points.get (counter);
                  b = (Point) points.get (counter + 1);
                  
                  if (a.getY () == b.getY ()) {/*Horizontal edge detected*/}
                  else {
                        
                        temp = new Edge (a, b);
                        index = (int)(a.getY () > b.getY ()? b.getY ():a.getY ());
                                                
                        if (this.getRow (index) == null) {
                              
                              this.add(new row (index));
                        }
                                                      
                        this.getRow (index).getTableObject ().addToRear (temp);
                        }                  
            }
                        
            return;
      }
      
      public void printTable () {
           
            row temp;
            
            for (int counter = 0; counter < this.size (); counter++) {
                  
                if (this.get (counter) != null) {
                        
                    temp = (row)this.get (counter);
                    temp.printRow ();
                }                  
            }
            
            return;
      }
}

class row {
      
      public row () {
            
            return;
      }
       
        public row (int index) {
           
            setRowIndex (index);
           
            return;
        }
      
      public TableObject getTableObject () {
            
            return to;
      }
      
      public double getRowIndex () {
            
            return rowindex;
      }
      
      public void printRow () {
            
            try {
                  System.out.print ("Row: " + rowindex + "\n");
                  to.printTable ();
            }
            catch (Exception e) {
                  System.err.println (e);
            }
            
            return;
      }
      
      public void setRowIndex (double value) {
            
            rowindex = value;
            
            return;
      }
      
      public void setTableObject (TableObject value) {
            
            to = value;
            
            return;
      }
      
      private TableObject to = new TableObject ();
      private double rowindex = 0;
}
0
 
LVL 1

Author Comment

by:TZRick
ID: 12641257
class ActiveEdgeTable extends TableObject {
      
      public ActiveEdgeTable () {
            
            return;
      }
      
      public void sortOnX () {
                  
              int i, j;
              Edge temp = new Edge ();

              for (i = (this.size () - 1); i >= 0; i--)
              {
                for (j = 1; j <= i; j++)
                {
                        if (this.getEdgeAt (j - 1).getx0 () > this.getEdgeAt (j).getx0 ())
                        {
                          temp.setTo (this.getEdgeAt (j - 1));
                          this.setEdgeAt (j - 1, this.getEdgeAt (j));
                          this.getEdgeAt (j).setTo (temp);
                        }
                }
              }
            
            return;
      }
      
      /*      
       *      Purpose of Method: Perform addition of new edges from EdgeTable to this
       *      AET.
       */
      public void preDrawUpdate (row currentrow) {
           
            Edge edge = null;
            int rowsize = currentrow.getTableObject ().size ();
           
            for (int counter = 0; counter < rowsize; counter++) {
               
                edge = currentrow.getTableObject ().getEdgeAt (counter);         // Why is edge null when counter=0
                //edge.getNext ().printEdge();                                                  // and the currentrow index is 40?
                this.addToRear (edge);                                                           // Null pointer exception
                edge = null;
            }            

            return;
      }
      
      public void postDrawUpdate (int index) {
            
            Edge currentedge;
            
            for (int counter = 0; counter < this.size (); counter++) {
                  
                  currentedge = this.getEdgeAt (counter);
                  
                  if (currentedge.getYMax() == index)
                        this.removeEdgeAt (counter);
                  else
                        currentedge.setx0 (currentedge.getx0 () + currentedge.getMInv());
            }
                  
            return;
      }      
}
0
 
LVL 1

Author Comment

by:TZRick
ID: 12641285
Okay... the big problem is with ActiveEdgeTable's preDrawUpdate method. I cannot understand why the code there returns null, while the exact same situation in the Temp2 class works perfectly?

The goal here is to debug the program and to ensure that IT WORKS!!! The program should basically add all edges from the EdgeTable to the ActiveEdgeTable using the same basic logic I have used. Any errors populating the EdgeTable (I believe there are none, but just in case) should be fixed as well, as it relates to the problem. No radically different changes will be accepted (unless I indicate otherwise).

Thank you very much for your help!
0
 
LVL 1

Author Comment

by:TZRick
ID: 12641326
P.S. Suggestions for improving my programming style are always welcomeQ! :-)
0
 
LVL 21

Accepted Solution

by:
MogalManic earned 200 total points
ID: 12643246
Is there any reason why you cannot use java.util.LinkedList?

I cannot see anything, either you have a coding problem (ie head gets repointed or mistakinly using x=y instead of x==y), or there is a flaw in your logic.  Here are some suggestions (Some are coding style):

1) Download Junit(www.junit.org)  and test each class individually.  That way you know that each class works as you designed them
2) Your javadoc comments are missing (they will help you to remember what each function is SUPPOSED to do)
     Without a clear contract for each method, it is easy for later incarnations of the method to digress into doing 2 (or 3) things at once.
3) Checkout some of the advanced features of your IDE.  You might be able to set a breakpoint on a specific variable and stop when it changes.
4) Based on your descriptions(I'm assuming they are correct).  Something is changing the size of the linked list between these two statments:
               Edge edge5 = et.getRow (40).getTableObject ().getEdgeAt (0);
...
                edge = currentrow.getTableObject ().getEdgeAt (counter);  //where counter==0 & currentRow is et.getRow(40)
     Set a breakpoint on these two lines and set a watchpoint on et.getRow(40).  Is something setting the size to 0?
0
 
LVL 1

Author Comment

by:TZRick
ID: 12649511
MogalManic: Your advice is well-founded. Thank you for the tips. I have found the error and I admit is was very stupid.

The error was in preDrawUpdate in the ActiveEdgeTable class:

public void preDrawUpdate (row currentrow) {
           
            int rowsize = currentrow.getTableObject ().size ();
           
            for (int counter = 0; counter < rowsize; counter++) {

                Edge edge = null;
                edge.setTo (currentrow.getTableObject ().getEdgeAt (counter)); // setTo is a function that basically copies
                this.addToRear (edge);                                                           //  the original edge's properties
                edge = null;
            }          

            return;
     }

Thank you for your help.
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction: Hints for the grid button.  Nested classes, templated collections.  Squash that darned bug! Continuing from the sixth article about sudoku.   Open the project in visual studio. First we will finish with the SUD_SETVALUE messa…
Introduction: The undo support, implementing a stack. Continuing from the eigth article about sudoku.   We need a mechanism to keep track of the digits entered so as to implement an undo mechanism.  This should be a ‘Last In First Out’ collec…
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
In a question here at Experts Exchange (https://www.experts-exchange.com/questions/29062564/Adobe-acrobat-reader-DC.html), a member asked how to create a signature in Adobe Acrobat Reader DC (the free Reader product, not the paid, full Acrobat produ…
Suggested Courses
Course of the Month18 days, 12 hours left to enroll

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question