Need help debugging; linked list-type structure

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:

LVL 1
TZRickAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

TZRickAuthor Commented:
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
TZRickAuthor Commented:
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
TZRickAuthor Commented:
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
Cloud Class® Course: MCSA MCSE Windows Server 2012

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

TZRickAuthor Commented:
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
TZRickAuthor Commented:
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
TZRickAuthor Commented:
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
TZRickAuthor Commented:
P.S. Suggestions for improving my programming style are always welcomeQ! :-)
0
MogalManicCommented:
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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
TZRickAuthor Commented:
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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
System Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.