14 Replies - 587 Views - Last Post: 06 April 2013 - 01:04 PM Rate Topic: -----

#1 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

AVL Dictionary problem

Posted 05 April 2013 - 02:18 PM

hey was wondering what i should use to implement this i created a LinkedBinaryTree in this same assignment so its probably related to that just thought id see what everyone else suggests
/**
 * 
 */
package cs2321;

import net.datastructures.*;

/**
 * @author cdbrown
 *
 */
public class AVLDictionary<K, V> implements Dictionary<K, V> {
	/**
	 * 
	 */
	int size;
	public AVLDictionary() {
		size=0;
		
	}

    /**
     * Return an iterable collection of all Entries with keys within
     * the given range (inclusive).
     *
     * @param start Starting key value
     * @param stop Ending key value
     * @return Iterable collection of matching entries. If no matches
     *         are found the returned Iterable is empty.
     */
    public Iterable<Entry<K,V>> getRange(K start, K stop) {
		// TODO Auto-generated method stub
		return null;
    }
	
	/* (non-Javadoc)
	 * @see net.datastructures.Map#entries()
	 */
	public Iterable<Entry<K, V>> entries() {
		// TODO Auto-generated method stub
		return null;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Map#get(java.lang.Object)
	 */
	public Entry<K,V> find(K key) throws InvalidKeyException {
		// TODO Auto-generated method stub
		return null;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Map#isEmpty()
	 */
	public boolean isEmpty() {
		if(size==0){
			return true;
		}
		return false;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Map#keys()
	 */
	public Iterable<K> keys() {
		// TODO Auto-generated method stub
		return null;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Map#put(java.lang.Object, java.lang.Object)
	 */
	public Entry<K,V> insert(K key, V value) throws InvalidKeyException {
		// TODO Auto-generated method stub
		size++;
		return null;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Map#remove(java.lang.Object)
	 */
	public Entry<K,V> remove(Entry<K,V> e) throws InvalidEntryException {
		// TODO Auto-generated method stub
		size--;
		return null;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Map#size()
	 */
	public int size() {
		
		return size;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Map#values()
	 */
	public Iterable<V> values() {
		// TODO Auto-generated method stub
		return null;
	}
	
	  public Iterable<Entry<K,V>> findAll(K key) throws InvalidKeyException {
		  return null;
	  }



}



the code for the linked binary tree i made is here
/**
 * 
 */
package cs2321;
import java.util.Iterator;
import net.datastructures.BTNode;
import net.datastructures.BTPosition;
import net.datastructures.BinaryTree;
import net.datastructures.BoundaryViolationException;
import net.datastructures.EmptyTreeException;
import net.datastructures.InvalidPositionException;
import net.datastructures.LinkTree;
import net.datastructures.NonEmptyTreeException;
import net.datastructures.Position;
import net.datastructures.PositionList;

/**
 * @author joshua droptiny
 *
 */
public class LinkedBinaryTree<E> implements LinkTree<E> {
	protected BTPosition<E> root=null;	// reference to the root
	int size=0;
	/* (non-Javadoc)
	 * @see net.datastructures.LinkTree#addRoot(java.lang.Object)
	 */
	public Position<E> addRoot(E e) throws NonEmptyTreeException {
		if(!isEmpty())
			throw new NonEmptyTreeException("Tree already has a root");
		size = 1;
		root = createNode(e,null,null,null);
		return root;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.LinkTree#attach(net.datastructures.Position, net.datastructures.BinaryTree, net.datastructures.BinaryTree)
	 */
	public void attach(Position<E> v, BinaryTree<E> T1, BinaryTree<E> T2)
			throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		if (isInternal(v))
			throw new InvalidPositionException("Cannot attach from internal node");
		if (!T1.isEmpty()) {
			BTPosition<E> r1 = checkPosition(T1.root());
			vv.setLeft(r1);
			r1.setParent(vv);		// T1 should be invalidated
		}
		if (!T2.isEmpty()) {
			BTPosition<E> r2 = checkPosition(T2.root());
			vv.setRight(r2);
			r2.setParent(vv);		// T2 should be invalidated
		}
	}

	/* (non-Javadoc)
	 * @see net.datastructures.LinkTree#insertLeft(net.datastructures.Position, java.lang.Object)
	 */
	public Position<E> insertLeft(Position<E> v, E e)
			throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> leftPos = vv.getLeft();
		if (leftPos != null)
			throw new InvalidPositionException("Node already has a left child");
		BTPosition<E> ww = createNode(e, vv, null, null);
		vv.setLeft(ww);
		size++;
		return ww;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.LinkTree#insertRight(net.datastructures.Position, java.lang.Object)
	 */
	public Position<E> insertRight(Position<E> v, E e)
			throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> rightPos = vv.getRight();
		if (rightPos != null)
			throw new InvalidPositionException("Node already has a right child");
		BTPosition<E> w = createNode(e, vv, null, null);
		vv.setRight(w);
		size++;
		return w;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.LinkTree#remove(net.datastructures.Position)
	 */
	public E remove(Position<E> v) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		BTPosition<E> leftPos = vv.getLeft();
		BTPosition<E> rightPos = vv.getRight();
		if (leftPos != null && rightPos != null)
			throw new InvalidPositionException("Cannot remove node with two children");
		BTPosition<E> ww; 	// the only child of v, if any
		if (leftPos != null)
			ww = leftPos;
		else if (rightPos != null)
			ww = rightPos;
		else 		// v is a leaf
			ww = null;
		if (vv == root) { 	// v is the root
			if (ww != null)
				ww.setParent(null);
			root = ww;
		}
		else { 		// v is not the root
			BTPosition<E> uu = vv.getParent();
			if (vv == uu.getLeft())
				uu.setLeft(ww);
			else
				uu.setRight(ww);
			if(ww != null)
				ww.setParent(uu);
		}
		size--;
		return v.element();
	}

	/* (non-Javadoc)
	 * @see net.datastructures.BinaryTree#hasLeft(net.datastructures.Position)
	 */
	public boolean hasLeft(Position<E> v) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		return (vv.getLeft() != null);
	}

	/* (non-Javadoc)
	 * @see net.datastructures.BinaryTree#hasRight(net.datastructures.Position)
	 */
	public boolean hasRight(Position<E> v) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		return (vv.getRight() != null);
	}

	/* (non-Javadoc)
	 * @see net.datastructures.BinaryTree#left(net.datastructures.Position)
	 */
	public Position<E> left(Position<E> v) throws InvalidPositionException,
	BoundaryViolationException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> leftPos = vv.getLeft();
		if (leftPos == null)
			throw new BoundaryViolationException("No left child");
		return leftPos;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.BinaryTree#right(net.datastructures.Position)
	 */
	public Position<E> right(Position<E> v) throws InvalidPositionException,
	BoundaryViolationException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> rightPos = vv.getRight();
		if (rightPos == null)
			throw new BoundaryViolationException("No right child");
		return rightPos;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#children(net.datastructures.Position)
	 */
	public Iterable<Position<E>> children(Position<E> v)
			throws InvalidPositionException {
		PositionList<Position<E>> children = new NodePositionList<Position<E>>();
		if (hasLeft(v))
			children.addLast(left(v));
		if (hasRight(v))
			children.addLast(right(v));
		return children;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#isEmpty()
	 */
	public boolean isEmpty() {
		if(size==0){
			return true;
		}
		return false;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#isExternal(net.datastructures.Position)
	 */
	public boolean isExternal(Position<E> v) throws InvalidPositionException {

		return !isInternal(v);
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#isInternal(net.datastructures.Position)
	 */
	public boolean isInternal(Position<E> v) throws InvalidPositionException {
		checkPosition(v);		// auxiliary method
		return (hasLeft(v) || hasRight(v));
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#isRoot(net.datastructures.Position)
	 */
	public boolean isRoot(Position<E> v) throws InvalidPositionException {
		checkPosition(v);
		return (v == root()); 
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#iterator()
	 */
	public Iterator<E> iterator() {
		Iterable<Position<E>> positions = positions();
		PositionList<E> elements = new NodePositionList<E>();
		for (Position<E> pos: positions) 
			elements.addLast(pos.element());
		return elements.iterator();  // An iterator of elements
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#parent(net.datastructures.Position)
	 */
	public Position<E> parent(Position<E> v) throws InvalidPositionException,
	BoundaryViolationException {
		BTPosition<E> vv = checkPosition(v);
		Position<E> parentPos = vv.getParent();
		if (parentPos == null)
			throw new BoundaryViolationException("No parent");
		return parentPos; 
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#positions()
	 */
	public Iterable<Position<E>> positions() {
		PositionList<Position<E>> positions = new NodePositionList<Position<E>>();
		if(size != 0)
			preorderPositions(root(), positions);  // assign positions in preorder
		return positions;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#replace(net.datastructures.Position, java.lang.Object)
	 */
	public E replace(Position<E> v, E e) throws InvalidPositionException {
		BTPosition<E> vv = checkPosition(v);
		E temp = v.element();
		vv.setElement(e);
		return temp;
	}

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#root()
	 */
	public Position<E> root() throws EmptyTreeException {
		if (root == null)
			throw new EmptyTreeException("The tree is empty");
		return root;
	} 

	/* (non-Javadoc)
	 * @see net.datastructures.Tree#size()
	 */
	public int size() {

		return size;
	}
	public BTPosition<E> checkPosition(Position<E> v) throws InvalidPositionException {
		if (v == null || !(v instanceof BTPosition))
			throw new InvalidPositionException("The position is invalid");
		return (BTPosition<E>) v;
	}
	protected BTPosition<E> createNode(E element, BTPosition<E> parent, 
			BTPosition<E> left, BTPosition<E> right) {
		return new BTNode(element,parent,left,right); }
	/** Creates a list storing the the nodes in the subtree of a node,
	 * ordered according to the preorder traversal of the subtree. */
	protected void preorderPositions(Position<E> v, PositionList<Position<E>> pos) 
			throws InvalidPositionException {
		pos.addLast(v);
		if (hasLeft(v))
			preorderPositions(left(v), pos);	// recurse on left child
		if (hasRight(v))
			preorderPositions(right(v), pos);	// recurse on right child
	}
}




Is This A Good Question/Topic? 0
  • +

Replies To: AVL Dictionary problem

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2194
  • View blog
  • Posts: 5,222
  • Joined: 10-September 10

Re: AVL Dictionary problem

Posted 05 April 2013 - 02:26 PM

What you should use to implement what?
Was This Post Helpful? 0
  • +
  • -

#3 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

Re: AVL Dictionary problem

Posted 05 April 2013 - 03:37 PM

i guess what I'm asking is what should i use to store my information like i used that int size to solve the size() and isEmpty() methods so what would i use to solve the insert(), find(), and all the others really
Was This Post Helpful? 0
  • +
  • -

#4 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2194
  • View blog
  • Posts: 5,222
  • Joined: 10-September 10

Re: AVL Dictionary problem

Posted 05 April 2013 - 03:55 PM

You're kind of mixing things up - at least that's how I read your post. Methods (or functions in some other languages) DO things. Variables specify locations to STORE things. You have two methods, size() and isEmpty() that return values. You need to write insert() and find() methods that DO the desired functions.

The typical List.insert() method takes an item of the appropriate type and adds it to the list at a specified location. insert() may return a boolean to indicate success or failure, but doesn't need to return anything.

And find() would normally return either the location in the List, the index, where the specified item was found or another value that indicates the item was not found. Since indices can't be negative, -1 is a common return value for an item that was not found.

An aside, your isEmpty() method could be simplified to:
public boolean isEmpty()
{
        return size == 0;
}

Was This Post Helpful? 1
  • +
  • -

#5 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

Re: AVL Dictionary problem

Posted 05 April 2013 - 05:52 PM

so what type of variable should i use to store the keys and values I'm being given?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: AVL Dictionary problem

Posted 05 April 2013 - 05:53 PM

A class is a good idea. The standard Java library Map containers have an inner Entry class to store a K and V value. Then the table stores an Entry[].
Was This Post Helpful? 0
  • +
  • -

#7 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

Re: AVL Dictionary problem

Posted 05 April 2013 - 05:58 PM

its like i was trying to create a new dictionary variable to store everything but i wont let me am i making it wrong? i am putting Dictionary<K, V> list = new Dictionary<K, V>(); and i get this error Cannot instantiate the type Dictionary<K,V>, so than i thought make a binary linked tree of the type Dictionary<K,V> and i can do that but than how can i do the insert for the class AVLDictionary properly if i have to insert left or right in the binary linked tree

View Posttwinblades-josh, on 05 April 2013 - 05:57 PM, said:

its like i was trying to create a new dictionary variable to store everything but i wont let me am i making it wrong? i am putting Dictionary<K, V> list = new Dictionary<K, V>(); and i get this error Cannot instantiate the type Dictionary<K,V>, so than i thought make a binary linked tree of the type Dictionary<K,V> and i can do that but than how can i do the insert for the class AVLDictionary properly if i have to insert left or right in the binary linked tree

i also get the same error if i try to just make Entry<K,V> list= new Entry<K,V>();
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: AVL Dictionary problem

Posted 05 April 2013 - 06:01 PM

Dictionary is an interface. You cannot instantiate it. Also, K and V are type parameters. You use actual Object types when instantiating the AVLDictionary rather than K and V.

I don't mean to be rude, but I would talk with your instructor if you have no idea on how to start with a Dictionary backed by an AVL Tree. The Wikipedia page is also a good place to get started.
Was This Post Helpful? 0
  • +
  • -

#9 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

Re: AVL Dictionary problem

Posted 05 April 2013 - 06:09 PM

View Postmacosxnerd101, on 05 April 2013 - 06:01 PM, said:

Dictionary is an interface. You cannot instantiate it. Also, K and V are type parameters. You use actual Object types when instantiating the AVLDictionary rather than K and V.

I don't mean to be rude, but I would talk with your instructor if you have no idea on how to start with a Dictionary backed by an AVL Tree. The Wikipedia page is also a good place to get started.

not being rude at all i really appreciate your help
Was This Post Helpful? 0
  • +
  • -

#10 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

Re: AVL Dictionary problem

Posted 06 April 2013 - 12:41 PM

ok, so i made a linksequence for entry<K,V> and it seems to be working but for the get range when i need to compare the K i dont know how i thought it was if

if(list.get(i).getKey().compareto(start)>=0||list.get(i).getKey().compareto(stop)<=0){

}

but i get the error The method compareto(K) is undefined for the type K so i guess i dont know how to check if its in between that range any ideas?
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: AVL Dictionary problem

Posted 06 April 2013 - 12:49 PM

First, Java is case sensitive. So the method is compareTo(), not compareto(). Second, if you want the keys to be Comparable, you have to define them to be so with the generic header:
class AVLDictionary<K extends Comparable<? super K>, V> implements Dictionary<K extends Comparable<? super K>, V>{

}


Was This Post Helpful? 0
  • +
  • -

#12 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

Re: AVL Dictionary problem

Posted 06 April 2013 - 12:57 PM

this is my code so far other that the get range i have no errors was hoping if anyone saw any other issues though they could point them out
/**
 * 
 */
package cs2321;
import net.datastructures.*;

import java.util.Map;
/**
 * @author cdbrown
 *
 */
public class AVLDictionary<K, V> implements Dictionary<K, V> {
	/**
	 * 
	 */
	int size;

	LinkedSequence<Entry<K, V>> list= new LinkedSequence<Entry<K, V>>();
	public AVLDictionary() {
		size=0;
	}
	/**
	 * Return an iterable collection of all Entries with keys within
	 * the given range (inclusive).
	 *
	 * @param start Starting key value
	 * @param stop Ending key value
	 * @return Iterable collection of matching entries. If no matches
	 *         are found the returned Iterable is empty.
	 */
	public Iterable<Entry<K,V>> getRange(K start, K stop) {
		LinkedSequence<Entry<K, V>> temp= new LinkedSequence<Entry<K, V>>();
		for(int i=0;i<size;i++){
			if(list.get(i).getKey().compareto(start)>=0||list.get(i).getKey().compareto(stop)<=0){
				temp.addLast(list.get(i));
			}
		}
		return temp;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#entries()
	 */
	public Iterable<Entry<K, V>> entries() {
		return list;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#get(java.lang.Object)
	 */
	public Entry<K,V> find(K key) throws InvalidKeyException {
		for(int i=0;i<size;i++){
			if(list.get(i).getKey().equals(key)){
				return list.get(i);
			}
		}
		return null;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#isEmpty()
	 */
	public boolean isEmpty() {
		if(size==0){
			return true;
		}
		return false;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#keys()
	 */
	public Iterable<K> keys() {
		LinkedSequence<K> temp= new LinkedSequence<K>();
		for(int i=0;i<size;i++){
			temp.addLast(list.get(i).getKey());
		}
		return temp;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#put(java.lang.Object, java.lang.Object)
	 */
	public Entry<K,V> insert(K key, V value) throws InvalidKeyException {
		size++;
		return null;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#remove(java.lang.Object)
	 */
	public Entry<K,V> remove(Entry<K,V> e) throws InvalidEntryException {
		for(int i=0;i<size;i++){
			if(list.get(i).equals(e)){
				return list.remove(i);
			}
		}
		size--;
		return null;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#size()
	 */
	public int size() {

		return size;
	}
	/* (non-Javadoc)
	 * @see net.datastructures.Map#values()
	 */
	public Iterable<V> values() {
		LinkedSequence<V> temp= new LinkedSequence<V>();
		for(int i=0;i<size;i++){
			temp.addLast(list.get(i).getValue());
		}
		return temp;
	}
	public Iterable<Entry<K,V>> findAll(K key) throws InvalidKeyException {
		return null;
	}
}


Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: AVL Dictionary problem

Posted 06 April 2013 - 12:59 PM

I just told you how to fix your problems regarding the range... So you should be able to fix them now.
Was This Post Helpful? 0
  • +
  • -

#14 twinblades-josh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 21
  • Joined: 04-April 13

Re: AVL Dictionary problem

Posted 06 April 2013 - 12:59 PM

View Postmacosxnerd101, on 06 April 2013 - 12:49 PM, said:

First, Java is case sensitive. So the method is compareTo(), not compareto(). Second, if you want the keys to be Comparable, you have to define them to be so with the generic header:
class AVLDictionary<K extends Comparable<? super K>, V> implements Dictionary<K extends Comparable<? super K>, V>{

}



thanks, if i change that it should still compile for my teacher the same right?
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10186
  • View blog
  • Posts: 37,613
  • Joined: 27-December 08

Re: AVL Dictionary problem

Posted 06 April 2013 - 01:04 PM

If your code compiles for you, it will compile for your teacher as long as he is using a modern version of Java.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1