Please help about data structures.

Please help me, I got stuck on this one from yesterday til now. Long story short : I have to build an java apps for doing polynomial : addition, subtraction, derivative .... The data structure chosen is linked list. There are five classes

Term class : hold the exponent and coefficient for each term of the polynomial

Node class : each node have a term in it and a link to the next Node

Orderedsequences class: contains the head of the ordered sequence, the term must be arranged from high exponent to low exponent. orderedsequence also contains a cursor to show the current term, and a count to show how many term in there.

Polynomial class : contains method to manipulate polynomial : add term, subtract two polynomials, derivative...

Test class: to test the method.


Previously, when I use array as the data structure to hold the term, everything is fine, when I change to linked list lost of thing happen. I think I have a trouble with the insert method (insert new terms into orderedsequence) and isCurrent method in the Orderedsequence class. Please help.

Here is the code for the five classes.

Code Java:

---

public class Node
{
private Term data;
private Node link;
 
//constructor
 
public Node(Term t,Node l)
{
data=t;
link=l;
}
 
//add Node after this Node
public void addNodeafter(Term item)
  {
  link =new Node (item,link);
  }
//Accessor  
  public Term getTerm ()
  {
  return data;
  }
  public Node getLink(){
  return link;
  }
//remove Node after this Node  
  public void removeNodeAfter()
  {
  link=link.link;
  }
//Set the term for this Node
  public void setTerm (Term x)
  {
  data=x;
  }
//Set the Link for this Node  
  public void setLink(Node x)
  {
  link=x;
  }
 
//List copy
 
  public static Node listCopy(Node source)
  {
  Node ans=null;
  if(source != null)
  {
  ans=new Node (source.data,null);
  Node cursor=source.link;
  Node tail= ans;
  while(cursor != null)
  {
  tail.link = new Node (cursor.data,null);
  cursor = cursor.link;
  tail = tail.link;
  }
  }
  return ans;
 }
}

---

[CODE]

Code Java:

---

public class Term implements Comparable<Term>
{
  private double coeff;
  private int exp;  
 
  //constructor
  public Term (double x,int y)
  {
    coeff=x;
    exp=y;
 
  }
 
  // Return the value of the coefficient of this term
  public double getCoeff()
  {
    return coeff;
  }
 
  //Return the value of the power of this term
  public int getExp()
  {
    return exp;
  }
 
  //modify the coefficient of a term
  public void setCoeff(double d)
  {
    coeff = d;
  }
 
  //modify the coefficient of a term
  public void setExp(int i)
  {
    exp = i;
  }
 
  //this term and term a has the same power
  //Return a term that is a sum of this term and a
  public Term add(Term a)
  {
    return new Term(coeff+a.coeff,exp);
  }
 
  //this term and term a has the same power
  //Return a term that is a substraction of term a from this term
  public Term subtr(Term a)
  {
    return new Term(coeff-a.coeff,exp);
  }
 
  //Return the differnce of the two terms which has same power
 
  public Term subtract(Term t){
  return new Term(coeff-t.coeff,exp);
  }
 
  //Return a term that is a multiplication of this term and term a
  public Term mult(Term a)
  {
    return new Term(coeff*a.coeff,exp+a.exp);
  }
 
  //Return a term that is the derivative of this term
  public Term derivative()
  {
    return new Term (coeff*exp,exp-1);
  }
 
  //Return a term that is the integral of this term
  public Term integral()
  {
    return new Term(coeff/(exp+1),exp+1);
  }
 
  //Return the value of the definite integral from a to b of this term
 
  public double defintegral(double a,double b){
 
    return (integral().eval(b)-integral().eval(a));}
 
//Compare the exponent of the two terms, return 0 if equals, -1 < , 1 >
  public int compareTo(Term t){
  int ans =0;
  if(exp>t.exp) ans = 1;
  else if (exp<t.exp) ans=-1;
  return ans;
  } 
 
  public boolean equals(Object obj)
  {
    boolean ans = false;
 
    if(obj instanceof Term && compareTo((Term)obj)==0&&coeff==((Term)obj).coeff) ans=true;
  return ans;
  }
 
  //Return value of this term at a particulate value
  public double eval(double x)
  {
    double ans=coeff*Math.pow(x,exp);
    return ans;
  }
 
  //Return a string that describes this term.
  public String toString()
  {
    String ans="";
    if(exp>1&&coeff!=0) ans=ans+coeff+"x^"+exp+" ";
    else if(exp==1&&coeff>1) ans=ans+coeff+"x";
    else if (exp==0&&coeff!=0) ans=ans+coeff;
    else if(exp==1&&coeff==1) ans=ans+"x";
    return ans;
  }
}

---

Code Java:

---

public class OrderedSequence implements Cloneable
{
  private Node head;
  private int count;
  private Node cursor ;
 
  //Constructor with any length
 
  public OrderedSequence()
  {
    head=null;
    count=0;cursor=head;
  }
 
//insert a term in the ordered sequence. Ordered from high exponent to low exponent.When the new term has same exponen
//with an existing term, add the two together, if the result exponent is zero, remove the term.  
 
  public void insert(Term t)
  {
    if(head==null)
    {
    head=new Node(t,null);
    }
    else 
 
    {
      if(t.getExp()>head.getTerm().getExp())
    { 
      head=new Node (t,head);
      count++;
    }
    else
 
    {
    start();
    while (cursor != null&&t.getExp()!=cursor.getTerm().getExp())
    {
      advance();
    }
    if(cursor!=null)//the power of t is the same as one of the exp in the os
    {
    cursor.setTerm(new Term(t.getCoeff()+cursor.getTerm().getCoeff(),t.getExp()));
 
    count++;
 
    if(cursor.getTerm().getCoeff()==0) 
    {
      removeCurrent(); 
      count--;     
    }
 
    }
    else //cursor is null, there is no term in os has the same power as t
 
    {
    cursor.addNodeafter(t);count++;  
    } 
 
    }
    }
    } 
 
 
 
 //restart the cursor to the beginning position
  public void start()
  {
    cursor = head;
  }
 
 
// return the number of terms in the array
  public int getCount(){
  return count;
  }
 
 
//return the current position in the sequence
  public Term getCurrent()
  {
    return cursor.getTerm();
  }
 
  //check if cursor is in the current positions in this ordered sequence
  public boolean isCurrent()
  {
    boolean answer = false;
    if(cursor.getTerm()!=null)
      answer = true;
    return answer;
  }
 
  //move the cursor to the next term
  public void advance()
  {
 
    if(isCurrent() == true)
      cursor=cursor.getLink();
  }
 
 
  //remove the term at current 
  public boolean removeCurrent()
  {
    boolean ans=false;
    if(isCurrent() == true)
    {
      cursor.setTerm(cursor.getLink().getTerm());
      cursor.setLink(cursor.getLink().getLink());
      ans=true;
 
    }
    return ans;
  }
//merge two ordered sequence together
  public OrderedSequence merge(OrderedSequence os){
 
    OrderedSequence ans=clone();start();
    while(cursor!=null)
    {
    ans.insert(os.getCurrent());
   advance();           
    }
  return ans;
  } 
 
  public OrderedSequence clone()
  {
  OrderedSequence ans= new OrderedSequence();
  start();
  while(cursor!=null)
  {
  ans.insert(getCurrent());  
  advance();
  }
  return ans;
  }
 
/* public OrderedSequence clone(){
  OrderedSequence ans ;
  try 
  {
  ans=(OrderedSequence)super.clone();
  }
  catch (CloneNotSupportedException e)
  {
    throw new RuntimeException("This class does not implement Cloneable");
  }
  ans.head = head.clone();
  return ans;} */
 
}

---

Code Java:

---

public class Polynomial implements Cloneable
{
  private OrderedSequence os;
 
  //Constructor
  public Polynomial()
  {
    os=new OrderedSequence();
  }
 
 
  public Polynomial (OrderedSequence ost)
  {
  os=ost;
  }
 
  //insert term with specified coefficient and exponent
 
  public void insert(double a,int b)
  {
  os.insert(new Term(a,b));
  }
 
  //get the degree of this polynomial
 
  public int getDegree()
  {
    os.start();
  return os.getCurrent().getExp();
  }
 
  public int numberOfTerms(){
  return os.getCount();
  }
 
  //Evaluate the value of a polynomial
 
  public double evaluate(double x)
  {
  double ans=0;os.start();
  while(os.isCurrent()==true)
  {
  ans=ans+os.getCurrent().eval(x);
  os.advance();
  }
  return ans;
  }
 
 
  //return the sum of this polynimial and polynomial t
  public Polynomial add(Polynomial t)
 {
 return new Polynomial(os.merge(t.os)); 
  }
 
 //return the difference between this polynomial and polynomial a
 public Polynomial sub(Polynomial a)
  {
  Polynomial ans=clone();
    a.os.start();
  while(a.os.isCurrent()==true)
  {
  ans.insert(-1*(a.os.getCurrent().getCoeff()),a.os.getCurrent().getExp());
  a.os.advance();
  }
  return ans;
  } 
 
  // Take derivative 
  public Polynomial derivative()
  {
  Polynomial ans=new Polynomial();
  os.start();
  while(os.isCurrent()==true)
  {
  ans.insert(os.getCurrent().derivative());os.advance();
  }
  return ans;
  }
 
  //Integrate polylinomial 
 
  public Polynomial integrate()
  {
  Polynomial ans=new Polynomial();
  os.start();
  while(os.isCurrent()==true)
  {
  ans.insert(os.getCurrent().integral());os.advance();
  }
  return ans;
  }
 
  //Definite integral from a to b
 
  public double definiteIntegral(double a,double b)
  {
  Polynomial inte=integrate();
  return (inte.evaluate(b)-inte.evaluate(a));
  }
 
  //Multiplication of this polynomial and polinomial a
 
  public Polynomial multiply(Polynomial a)
 
  {
  Polynomial ans =new Polynomial();
  os.start();
  while(os.isCurrent()==true)
  {
  a.os.start();
  while(a.os.isCurrent()==true)
  {
  ans.insert(os.getCurrent().mult(a.os.getCurrent()));
  a.os.advance();
  }
  os.advance();
  }
  return ans;
  }
 
  //Clone method for polynomial
  public Polynomial clone(){
  Polynomial ans=new Polynomial(os.clone()) ;
 
  return ans;}
 
  //Compares the whole term of this polynomial and polynomial a
  public boolean equals(Object obj)
  {
    boolean ans = false;
    if(obj instanceof Polynomial&&os.getCount() == ((Polynomial)obj).os.getCount())
    {
      os.start();((Polynomial)obj).os.start();
      while(os.isCurrent()==true&&os.getCurrent().equals(((Polynomial)obj).os.getCurrent())==true)
      {
      os.advance();((Polynomial)obj).os.advance();
      }
      if(os.isCurrent()==false) ans=true;
    }
    return ans;
  }
 
 
 
  //Insert a term into this polynomial
  public void insert (Term a)
  {
    os.insert(a);
  }
 
  //display the polynomial
  public String toString()
  {
    os.start();
    String ans="";
    while(os.isCurrent()==true)
    {
      ans=ans+os.getCurrent().toString();
      os.advance();
      if(os.isCurrent()==true&&os.getCurrent().getCoeff()!=0) ans=ans+" + "; 
    }
 
    return ans;
  }
}

---

Code Java:

---

public class TestLab2x{
  public static void main (String arg[]){
 
  //Make a new term 3.5x^4
 
  Term t1=new Term(2,4);
  Term tt=new Term(2,4);
  Term t2=new Term(2.5,4);
  Term t3=t1.add(t2);
  Term t4=new Term(1,1);Term t5=new Term(2,2);Term t6=new Term(3,3);Term t7=new Term(5,5);Term t8=new Term(10,0);
 
   System.out.println("This is the term t1 "+t1);
  //Compare term t1 and tt
 
  System.out.println("Compare t1 and tt "+t1.equals(tt));
  System.out.println("Compare t1 and t2 "+t1.equals(t2));
  System.out.println("Compare t1 and 1000 "+t1.equals(1000));
 
 //Extract the coefficient of t1
  System.out.println("The coefficient of t1 is "+t1.getCoeff());
 //Extract the exponent of t1
  System.out.println("The exponent of t1 is "+t1.getExp()); 
 
   System.out.println("This is the term t3 "+t3);
 
 //Extract the coefficient of t1
  System.out.println("The coefficient of t3 is "+t3.getCoeff());
 //Extract the exponent of t1
  System.out.println("The exponent of t3 is "+t3.getExp()); 
  //Derivative of a term
  Term t9=t1.derivative();System.out.println("Display t9 "+t9.toString());
  Term t10=t8.derivative();System.out.println("Display t10 "+t10.toString());
 
  //Evaluate t1 at x=2
  System.out.println("Value of t1 at x=2 is " + t1.eval(2));
 
   System.out.println("Display t8 "+t8.toString()+"\n");
 
   Polynomial p1=new Polynomial();
   p1.insert(t1);p1.insert(t5);
 
    System.out.println("Polynomial p1 is : " +p1.toString());
 
  }}

---

Quote:

---

I think I have a trouble with the insert method (insert new terms into orderedsequence) and isCurrent method in the Orderedsequence class.

---

Have you tried debugging the code by adding println statements to print out the values of variables as the code executes so you can see what the code is doing?

Do you have print outs from the code that shows the problem? Can you post them and add comments to them that describes the problem and show what the output should be.

This is what I got from running those codes:

Quote:

---

java.lang.NullPointerException
at OrderedSequence.insert(OrderedSequence.java:56)
at Polynomial.insert(Polynomial.java:149)
at TestLab2x.main(TestLab2x.java:40)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Nativ e Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(Unknow n Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Un known Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at edu.rice.cs.drjava.model.compiler.JavacCompiler.ru nCommand(JavacCompiler.java:272)

---

Quote:

---

ava.lang.NullPointerException
at OrderedSequence.insert(OrderedSequence.java:56)

---

Look at line 56 and find the variable with the null value. Then backtrack in the code to see why that variable does not have a valid non-null value.

The posted code is poorly formatted which makes it very hard to read and understand.
For example:

Code :

---

  } 
 
    }
    }
    }

---

}s should NOT be in a column. They should be inline vertically with the line with their pairing {

@Norm : thanks, I am trying to add the System.out.println to each section to see what is going on.

Edit: I think I figure out the error. Thanks again Norm, your trick works.:cool: