Linked list using Sorted Set

AdRock952 · Jan 12, 2008

I am trying to create a linked list that uses the Sorted Set interface but am unclear about what needs to go in certain methods.

I am creating the class and I'll have the app that inserts the data seperate.

What i need is to create the class that uses all the methods that are on the Java site.

Here is what i have so far

Code:

import java.util.*;
import java.util.SortedSet;
import java.util.Set;


public class OrderLinkedList implements SortedSet {

    public OrderLinkedList() {
    
    }
    
    public comparator() {
        
    }
    
    public SortedSet subSet(Object toElement, Object fromElement) {
        
    }
    
    public SortedSet headSet(Object toElement) {
        
    }
    
    public SortedSet tailSet(Object fromElement) {
        
    }
    
    public first() {
        throw new NoSuchElementException();
        return; 
    }
       
    public last() {
        //if (isEmpty())
            throw new NoSuchElementException();
        return;
    }

I understand the first() and last() methods but whati'm not sure about is tailSet(), headSet(), subSet() and comparator()

Could someone please explain what each of them are for and how i would use it as the explanations I found online are no help whatsoever

Diancecht · Jan 16, 2008

What's wrong with the LinkedList provided with JDK?

Cheers,
Dian

AdRock952 · Jan 23, 2008

I have got quite a bit further with this but i am stuck on what to return for the subSet(), headSet() and tailSet()

I looked at the java site and it said to return SortedSet and other code but i don't know what in my code is to be returned.

Here is my code now

Code:

import java.util.*;

public class OrderedLinkedList extends AbstractSet implements SortedSet {
    
    private Node start;
    private Node end;
    private Node current;
  
    private int numberContents;

    public OrderedLinkedList() {
    	
    	numberContents = 0;
    }

    public OrderedLinkedList(Object cargo) {

    	start = new Node(cargo);
    	end = start;
    	numberContents = 1;
    }

    public boolean add(Object cargo) {
        
    	Node newEnd = new Node(cargo);
    	
    	if (numberContents == 0 ) {
    		start = newEnd;
    	}
    	else {
		end.setNext(newEnd);
    		newEnd.setPrevious(end);
    		current = newEnd;
    		end = newEnd; 	
    	}
    	numberContents++;
    }

    public int size() {
        return numberContents;
    }
	
    public boolean isEmpty() {
        return start == null;
    }
	
    public Object first() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        current = start;
        return start.getContents();
    }

    public Object last() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        current = end;
        return end.getContents();
    }
        
    
  	
  	public SortedSet tailSet(Object fromElement) {
  		return;	[red]Don't know what to return here[/red]	
  	}
  	
  	public SortedSet headSet(Object toElement) {
  		return; [red]Don't know what to return here[/red]
  	}
  	
  	public SortedSet subSet(Object fromElement, Object toElement) {
  		return; [red]Don't know what to return here[/red]
  	}  	
  		
    public Iterator iterator() {
    	
        return new Iterator() {
        	
            Object valueReturned;
            private int counter = 0;
            
            public boolean hasNext() {
                if (counter >= numberContents){
                    return false;
                }
                else {
                    counter++;
                    return true;
                }
            }
            
            public Object next() {
                valueReturned = current.getContents();
                current = current.getNext();
                return valueReturned;
            }
            
            public void remove() {
                throw new UnsupportedOperationException();
            }     
        };
    } 
    	
    public Comparator comparator() {
    
    	return new Comparator() {
  	
    		public int compare(Object obj1, Object obj2) {
    			Node node1 = (Node) obj1;
    			Node node2 = (Node) obj2;
 	
 				return node1.compareTo(node2);
    		}	

    		public boolean equals(Object obj) {
        		if (!(obj instanceof Node)) {
            		return false;
        		}

        		Node newNode = (Node) obj;
        		return current.getContents().toString().equals(newNode.getContents().toString());
    		}
    	};
    }       
}

and for the Node class

Code:

import java.util.*;

public class Node {
	Node next;             // Refers to next item in the list.
	Node previous;         // Refers to the previous item.       ***
	Object cargo;               // The item for this Node.

	// Constructor: 
	public Node(Object cargo) {
		this.cargo = cargo;        // Store the item.
		next = null;  // Set next and previous to null.      ***
		previous = null;
  	}

  	// Set the pointer to the next Node:
    public void setNext(Node next) {
        this.next = next;        // Store reference to the next item.
    }
  
    // Additional method to set the pointer to the previous Node:  ***
    public void setPrevious(Node previous) {                                                               
        this.previous = previous; // Store reference to the previous item. 
    }
 
    // Get the next item in the list:
    public Node getNext() {
        return next;
    }

    // Additional method to get the previous item in the list:         ***
    public Node getPrevious() {
        return previous;
    }

    // Get the object for this item:
    public Object getContents() {
        return cargo;
    }

    // Return class name & object:
    public String toString() {
        return ""+ cargo;
    }

    public int compareTo(Object obj) {
        Node newNode = (Node) obj;
        int nodeComp = cargo.toString().compareTo(newNode.getContents().toString());

        return nodeComp;
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof Node)) {
            return false;
        }

        Node newNode = (Node) obj;
        return cargo.toString().equals(newNode.getContents().toString());
    }
}

stefanwagner · Jan 24, 2008

Code:

  public SortedSet tailSet(Object fromElement) {
          return;    Don't know what to return here    
      }

TailSet:
A sorted Set a b c d e f.
From Element: d
Return d e f.

don't visit my homepage:

http://home.arcor.de/hirnstrom/bewerbung

AdRock952 · Jan 24, 2008

I think i have worked that out but it may need checking to see if I have it right but i get this error when compiling

name clash: equals(E) in and equals(java.lang.Object) in java.lang.Object have the same erasure, yet neither overrides the other

Code:

import java.util.*;

public class OrderedLinkedList<E> extends AbstractSet<E> implements SortedSet<E> {
    
    private Node<E> start;
    private Node<E> end;
    private Node<E> current;
  
    private int numberContents;

    public OrderedLinkedList() {
    	
    	numberContents = 0;
    }

    public OrderedLinkedList(E cargo) {

    	start = new Node<E>(cargo);
    	end = start;
    	numberContents = 1;
    }

    public boolean add(E cargo) {
        
    	Node<E> newEnd = new Node<E>(cargo);
    	
    	if (numberContents == 0 ) {
    		start = newEnd;
    	}
    	else {
		end.setNext(newEnd);
    		newEnd.setPrevious(end);
    		current = newEnd;
    		end = newEnd; 	
    	}
    	numberContents++;
    	return true;
    }

    public int size() {
        return numberContents;
    }
	
    public boolean isEmpty() {
        return start == null;
    }
	
    public E first() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        current = start;
        return start.getContents();
    }

    public E last() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        current = end;
        return end.getContents();
    }
          	
    public SortedSet<E> tailSet(E fromElement) {
        
        if (isEmpty()) {
            throw new NullPointerException();
        }

        [red]Is this right[/red]
        OrderedLinkedList oll = new OrderedLinkedList();
        
        SortedSet<E> tail = oll.tailSet(fromElement+"\0");
        return tail;
        
  	//return null;		
    }
  	
    public SortedSet<E> headSet(E toElement) {
        
        if (isEmpty()) {
            throw new NullPointerException();
        }
        OrderedLinkedList oll = new OrderedLinkedList();
        
        SortedSet<E> head = oll.headSet(toElement+"\0");
        return head;
        
  	//return null;
    }
  	
    public SortedSet<E> subSet(E fromElement, E toElement) {
        
        if (isEmpty()) {
            throw new NullPointerException();
        }  
        OrderedLinkedList oll = new OrderedLinkedList();
        	      
        SortedSet<E> sub = oll.subSet(fromElement, toElement+"\0");
        return sub;
        
        //return null;
    }  	
  		
    public Iterator<E> iterator() {
    	
        return new Iterator<E>() {
        	
            E valueReturned;
            private int counter = 0;
            
            public boolean hasNext() {
                if (counter >= numberContents){
                    return false;
                }
                else {
                    counter++;
                    return true;
                }
            }
            
            public E next() {
                valueReturned = current.getContents();
                current = current.getNext();
                return valueReturned;
            }
            
            public void remove() {
                throw new UnsupportedOperationException();
            }     
        };
    } 
    	
    public Comparator<E> comparator(){
    
    	return new Comparator<E>() {
  	
            public int compare(E obj1, E obj2) {
                Node<E> node1 = (Node) obj1;
    			Node<E> node2 = (Node) obj2;
                
     			return node1.compareTo(node2.getContents());            
            }	

            public boolean equals(E obj) {[red]this is the problem[/red]
        	if (!(obj instanceof Node)) {
                    return false;
        	}

        	Node<E> newNode = (Node) obj;
        	return current.getContents().equals(newNode.getContents());
            }
    	};
    }       
}

stefanwagner · Jan 25, 2008

An error or a warning?
Please post the exact message as whole.

Maybe you need an annotation @override to suppress the warning.

don't visit my homepage:

http://home.arcor.de/hirnstrom/bewerbung

AdRock952 · Jan 25, 2008

I posted the error above the code

stefanwagner · Jan 26, 2008

a part of it, yes.

don't visit my homepage:

http://home.arcor.de/hirnstrom/bewerbung

AdRock952 · Jan 26, 2008

That is the whole error message I get when trying to compile

stefanwagner · Jan 26, 2008

I'm talking about filename, line-number and so on.
The ... whole message.

Since we don't know details about Node - maybe it's a prolem in Node?
How is Node defined?

don't visit my homepage:

http://home.arcor.de/hirnstrom/bewerbung

AdRock952 · Jan 26, 2008

OK...here si the code for the Node class

Code:

import java.util.*;

public class Node<E> implements Comparable<E>{
    Node<E> next;             // Refers to next item in the list.
    Node<E> previous;         // Refers to the previous item.       ***
    E cargo;               // The item for this Node.

	// Constructor: 
    public Node(E cargo) {
        this.cargo = cargo;        // Store the item.
        next = null;  // Set next and previous to null.      ***
        previous = null;
    }

  	// Set the pointer to the next Node:
    public void setNext(Node<E> next) {
        this.next = next;        // Store reference to the next item.
    }
  
    // Additional method to set the pointer to the previous Node:  ***
    public void setPrevious(Node previous) {                                                               
        this.previous = previous; // Store reference to the previous item. 
    }
 
    // Get the next item in the list:
    public Node<E> getNext() {
        return next;
    }

    // Additional method to get the previous item in the list:         ***
    public Node<E> getPrevious() {
        return previous;
    }

    // Get the object for this item:
    public E getContents() {
        return cargo;
    }

    // Return class name & object:
    public String toString() {
        return ""+ cargo;
    }

    public int compareTo(E obj) {
    	Node<E> newNode = (Node<E>) obj;
    	int nodeComp = ((Comparable<E>)cargo).compareTo(newNode.getContents());

    	return nodeComp;
    }
}

but this compiles fine...it's just the equals() method in the linked list class that causes the problem

stefanwagner · Jan 26, 2008

Shouldn't that be equals (Object) instead of equals (E)?

Code:

 public Comparator<E> comparator ()
	{
		return new Comparator<E>()
		{
			public int compare (E obj1, E obj2)
			{
				Node<E> node1 = (Node) obj1;
				Node<E> node2 = (Node) obj2;
				return node1.compareTo (node2.getContents ());
			}

			//  Object, not E
			public boolean equals (Object obj)
			{
				if (!(obj instanceof Node))
				{
					return false;
				}
				Node<E> newNode = (Node) obj;
				return current.getContents ().equals (newNode.getContents ());
			}
		};
	}

don't visit my homepage:

http://home.arcor.de/hirnstrom/bewerbung

AdRock952 · Jan 27, 2008

It needs to be generic so everthing Object is replaced with E

AdRock952 · Jan 27, 2008

I tried doing what you said and it compiled.

Would doing this affect the program because it's not using E?

Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Linked list using Sorted Set

AdRock952

Technical User

Diancecht

Programmer

AdRock952

Technical User

stefanwagner

Programmer

AdRock952

Technical User

stefanwagner

Programmer

AdRock952

Technical User

stefanwagner

Programmer

AdRock952

Technical User

stefanwagner

Programmer

AdRock952

Technical User

stefanwagner

Programmer

AdRock952

Technical User

AdRock952

Technical User

Similar threads

Part and Inventory Search

Sponsor