Click here to Skip to main content
15,890,825 members
Home / Discussions / Java
   

Java

 
AnswerRe: call c# function in java Pin
Nagy Vilmos5-May-09 2:37
professionalNagy Vilmos5-May-09 2:37 
GeneralRe: call c# function in java Pin
raesa5-May-09 2:40
raesa5-May-09 2:40 
AnswerRe: call c# function in java Pin
Vitaly Shelest5-May-09 9:32
Vitaly Shelest5-May-09 9:32 
GeneralRe: call c# function in java Pin
raesa5-May-09 17:30
raesa5-May-09 17:30 
Questionconvert integer to 8 bits Pin
lost_in_code5-May-09 1:28
lost_in_code5-May-09 1:28 
AnswerRe: convert integer to 8 bits Pin
harold aptroot5-May-09 1:59
harold aptroot5-May-09 1:59 
QuestionDraw on top of picture Pin
LordLothar5-May-09 1:02
LordLothar5-May-09 1:02 
Questionbinary search tree error compliation error Pin
harshad bhatia3-May-09 23:30
harshad bhatia3-May-09 23:30 
this is the binary search tree class as you can see the class is developed using generics the problem coming is in testing methods when i m passing integer as two parameters i m not sure why the error is coming whereas the cast i feel is correct ....





*
* Variables: root : marks the root of the tree, null if empty
*
* Inner classes:
* Node: implements each linked node. Defined as protected since only
* descendant classes need to access it
* Variables: key: polymorphic comparable key
* item: polymorphic data in the node
* left: reference to the left subtree
* right: reference to the right subtree
* Methods: Node(K thisKey, T thisItem)
* Node(K thisKey, T thisItem, Node l, Node r)
*
* Public methods: boolean isEmpty()
* void clear()
* boolean find(T item)
* void insert(T item)
* void printPreOrder()
* void printInOrder()
* void printPostOrder()
*
* Input: none
*
* Output: only for regression testing
*
* Error handling: none
*
* Regression testing: a private testing method for each public method
* except for find and for insert (since this is
* asked for during the prac).
*/

public class BinarySearchTree<K extends Comparable<K>,T extends Comparable<T>>
{

// Invariants for the class (and all its descendandts):
// (1) the tree is binary: all nodes have at most two children
// (2) for every node n, they key at n is greater than the key of any left
// descendant, and smaller than the key of any right descendant
// (3) Corollary: no key appears twice in the tree

protected Node root;

protected class Node
{ protected K key;
protected SortedLList<T> item;
protected Node left;
protected Node right;
// Creates a new leaf node of the tree with the appropriate data
//
// precondition: none new
// postcondition: a leaf node object is created with key data thisKey
// and item thisItem
// Best and worst case: O(1)
protected Node(K thisKey, SortedLList<T> thisItem)
{ key = thisKey; item = thisItem;
left = null; right = null;}

// Creates a new node of the tree with the appropriate data and pointing
// to the given left and right children nodes
//
// precondition: none new
// postcondition: a node object is created with key data thisKey
// item thisItem, and left and right nodes pointing to l and r, resp.
// Best and worst case: O(1)
protected Node(K thisKey, SortedLList<T> thisItem, Node l, Node r)
{ key = thisKey; item = thisItem;
left = l; right = r;}
} // end of the Node class
public BinarySearchTree()
{ root = null;}

// Used to check whether the tree is empty
//
// postcondition: if true the tree is empty, otherwise it is not
// Best and worst case: O(1)
public boolean isEmpty()
{ return (root == null);}

// Resets the tree to an empty state
//
// precondition: none new
// postcondition: the tree is empty
// Best and worst case: O(1)
public void clear()
{ root = null;}


// Used to check whether a node with the given key appears in the tree
// Achieved by descending through the tree performing binary search
// until the key is found or an empty node is reached.
//
// precondition: none new
// postcondition: if it returns null the key does not apper in the tree,
// otherwise it does
// Complexity: if compareTo is O(M) where M is the size of K, then best
// case O(M) when the key is at the root, worst O(D*M) when
// it does not find it and has traversed the maximum depth
// D of the tree
public boolean find(K thisKey)
{ return find(root,thisKey);}

protected boolean find(Node current, K thisKey)
{ if (current != null)
{ int comp = current.key.compareTo(thisKey);
if (comp > 0) // thisKey is greater than the current root
{return find(current.left, thisKey);}
else if(comp == 0) // found it
{return true;}
else // comp < 0 // thisKey is smaller than the current root
{return find(current.right, thisKey);}
}
else {return false;}
}

// Used to insert a node with the given key and item, giving an error if
// the key already appears in the tree with a different item. Achieved by
// descending through the tree performing binary search, until the
// appropriate empty node is reached, at which point the new leaf node is
// added and linked
//
// precondition: none new
// postcondition: if an error is printed the tree is unchanged and already
// contains a node with the given key and differen item. Otheriwse,
// if the tree is unchanged it already has a node with that key and
// else, the tree has a new leaf node with key thisKey and item newItem
// Complexity: if compareTo is O(M) where M is the size of K and equals
// is O(P) where P is the size of T, then best case is
// O(M)+O(P), when when both the key and the item are at the
// root, worst case O(D*M) occurs when the key does not appear
// in the tree and it has traversed the maximum depth D of the
// tree
public void insert(K thisKey, SortedLList<T> newItem)
{ if (root == null)
{root = new Node(thisKey, newItem);}
else
{insert(root, thisKey, newItem);}
}

protected void insert(Node current, K thisKey, SortedLList<T> newItem)
{ int comp = current.key.compareTo(thisKey);
if (comp > 0)
{if (current.left == null)
{current.left = new Node(thisKey,newItem);}
else {insert(current.left,thisKey,newItem);}}
else if (comp < 0)
{if (current.right == null)
{current.right = new Node(thisKey,newItem);}
else {insert(current.right,thisKey,newItem);}}
else // comp == 0
{if (!current.item.equals(newItem))
{System.out.println("Error: Already in");}}
}

public void printInOrder()
{ printInOrder(root);}
protected void printInOrder(Node current)
{
if (current != null)
{
printInOrder(current.left);
System.out.print("key is "+current.key+" ");
System.out.print("and item is "+current.item+" ");
printInOrder(current.right);
}
}

// Used to print all items following preOrder of the nodes and with a space
// in between each item
//
// precondition: none new
// postcondition: the item of every node is printed in preOrder (first the
// item node, then the items in the left-subtree, then in
// right-subtree
// Complexity: if print is O(M) where M is the max size of an item, best case
// and worst case is O(N*M) where N is the number of elements
// in the tree
public void printPreOrder()
{ printPreOrder(root);}
protected void printPreOrder(Node current)
{ if (current != null)
{ System.out.print(current.item+" ");
printPreOrder(current.left);
printPreOrder(current.right);
}
}

// Used to print all items following postOrder of the nodes and with a space
// in between each item
//
// precondition: none new
// postcondition: the item of every node is printed in postOrder (first the
// item node, then the items in the left-subtree, then in
// right-subtree
// Complexity: if print is O(M) where M is the max size of an item, best case
// and worst case is O(N*M) where N is the number of elements
// in the tree
public void printPostOrder()
{ printPostOrder(root);}
protected void printPostOrder(Node current)
{ if (current != null)
{ printPostOrder(current.left);
printPostOrder(current.right);
System.out.print(current.item+" ");
}
}

/* Two test classes: empty trees and non-empty trees
* Boundary analysis gives four cases: 0 elements, 1, 2, and many (5) */
private static void testIsEmpty()
{
BinarySearchTree<Integer,Integer> tree =
new BinarySearchTree<Integer,Integer>();

tree.clear();
System.out.println("TESTING isEmpty()");
System.out.println("Expected true, got "+tree.isEmpty());
tree.insert(4,4);
System.out.println("Expected false, got "+tree.isEmpty());
tree.insert(2,2);
System.out.println("Expected false, got "+tree.isEmpty());
tree.insert(5,5);
System.out.println("Expected false, got "+tree.isEmpty());
tree.insert(0,0);
tree.insert(12,12);
System.out.println("Expected false, got "+tree.isEmpty());
}

/* Two test classes: those that are already empty, and those that are not
* Boundary analysis gives four cases: 0 elements, 1, 2, and many (5) */
private static void testClear()
{
BinarySearchTree<Integer,Integer> tree =
new BinarySearchTree<Integer,Integer>();
tree.clear();
System.out.println("TESTING clear()");
System.out.println("Expected true, got "+tree.isEmpty());
tree.insert(4,4);
tree.clear();
System.out.println("Expected true, got "+tree.isEmpty());
tree.insert(4,4);
tree.insert(2,2);
tree.clear();
System.out.println("Expected true, got "+tree.isEmpty());
tree.insert(4,4);
tree.insert(2,2);
tree.insert(5,5);
tree.clear();
System.out.println("Expected true, got "+tree.isEmpty());
tree.insert(4,4);
tree.insert(2,2);
tree.insert(5,5);
tree.insert(0,0);
tree.insert(12,12);
tree.clear();
System.out.println("Expected true, got "+tree.isEmpty());
}

/* Not really any classes for traversing. The only test cases are due
* to the structure of the tree: nodes with no children, nodes with
* only a left subtree, only a right subtree, and with both. */
private static void testPrintPreOrder()
{
BinarySearchTree<Integer,Integer> tree =
new BinarySearchTree<Integer,Integer>();
tree.clear();
tree.insert(4,4);
tree.insert(3,3);
tree.insert(2,2);
tree.insert(5,5);
tree.insert(6,6);
System.out.print("TESTING printPreOrder, expected 4 3 2 5 6, got ");
tree.printPreOrder();
System.out.println(" ");
}

/* Not really any classes for traversing. The only test cases are due
* to the structure of the tree: nodes with no children, nodes with
* only a left subtree, only a right subtree, and with both. */
private static void testPrintPostOrder()
{
BinarySearchTree<Integer,Integer> tree =
new BinarySearchTree<Integer,Integer>();
tree.clear();
tree.insert(4,4);
tree.insert(3,3);
tree.insert(2,2);
tree.insert(5,5);
tree.insert(6,6);

System.out.print("TESTING printPostOrder, expected 2 3 6 5 4, got ");
tree.printPostOrder();
System.out.println(" ");
}
private static void testPrintInOrder()
{
BinarySearchTree<Integer,Integer> tree =
new BinarySearchTree<Integer,Integer>();
tree.clear();
tree.insert(4,4);
tree.insert(3,3);
tree.insert(2,2);
tree.insert(5,5);
tree.insert(6,6);
System.out.print("TESTING printInOrder, expected 2 3 4 5 6, got ");
tree.printInOrder();
System.out.println(" ");
}


public static void main(String[] args)
{
BinarySearchTree<Integer,Integer> tree = new BinarySearchTree<Integer,Integer>();
tree.testIsEmpty();
tree.testClear();
tree.testPrintPreOrder();
tree.testPrintInOrder();
tree.testPrintPostOrder();
}

}


now the sortedLList class


/* Class SortedLList<T extends Comparable<T>>
*

public class SortedLList<T extends Comparable<T>>
extends AbstractLList<T>
{
// New invariants for the class:
// (N) if node N points to node N', N.item is less or equal than N'

// Creates an empty object of the class, i.e., an empty list of T items
// Since the list is implemented with nodes, the size is not needed
//
// precondition: none new
// postcondition: an empty list is created
// Best and worst case: O(1)
public SortedLList()
{ head = null; last = null;}

// Inserts a new node with newItem to the list, making sure it is inserted
// before the first node whose item is greater or equal than newItem
//
// precondition: none new
// postcondition: a new node with newItem appears in the list
//
// Best case (should be inserted in first place) O(1)*O_compare where
// O_compare will tipically be O(M) where M is the length of newItem
// Worst case (in last place) O(N)*O_compare, where N is the length of
// the list
public void add(T newItem)
{
Iterator i = this.iterator();
while (i.hasNext() && i.peek().compareTo(newItem)<0)
{i.next();}
Node temp = new Node(newItem,i.current);
if (i.previous == null) // first element
{head = temp;}
else //middle or last element
{i.previous.next = temp;}
if (i.current == null) // last element
{last = temp;}
}

/*********************** REGRESSION TESTING CODE **********************/

// Two test classes: empty lists and non-empty lists
// Boundary analysis gives four cases: 0 elements, 1, 2, and many (5)
private static void testIsEmpty()
{ SortedLList<Integer> myList = new SortedLList<Integer>();
System.out.println("TESTING isEmpty()");
System.out.println("Expected true, got "+myList.isEmpty());
myList.add(9);
System.out.println("Expected false, got "+myList.isEmpty());
myList.add(0);
System.out.println("Expected false, got "+myList.isEmpty());
myList.add(1);
myList.add(2);
myList.add(14);
System.out.println("Expected false, got "+myList.isEmpty());
}

// Two test classes: full lists and non-full lists
// Boundary analysis gives three cases: 0 elements, 1, and many (5)
private static void testIsFull()
{ SortedLList<Integer> myList = new SortedLList<Integer>();
System.out.println("TESTING isFull()");
System.out.println("Expected false, got "+myList.isFull());
myList.add(9);
System.out.println("Expected false, got "+myList.isFull());
myList.add(0);
myList.add(1);
myList.add(2);
myList.add(14);
System.out.println("Expected false, got "+myList.isFull());
}

// One test class: adding to a list of any length
// Boundary analysis gives three cases: 0 elements, 1, and many (5)
private static void testAdd()
{ SortedLList<Integer> myList = new SortedLList<Integer>();
System.out.println("TESTING add()");
myList.add(0);
System.out.println("Expected 0, got "+myList);
myList.add(9);
System.out.println("Expected 0 9, got "+myList);
myList.add(1);
myList.add(14);
myList.add(20);
System.out.println("Expected 0 1 9 14 20, got "+myList);
}

// Two test classes: the item is not in the list and it is in it
// Subclasses for the class in which the item is in: is the first slot
// the last, or in the middle
// Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot
// used-1, and some slot in the middle
private static void testDeleteItem() throws Exception
{ SortedLList<Integer> myList = new SortedLList<Integer>();
myList.add(8);
myList.add(7);
myList.add(5);
myList.add(5);
myList.add(4);
myList.add(3);
myList.add(2);
myList.add(1);
myList.add(0);
System.out.println("TESTING deleteItem()");
System.out.println("Expected true, got "+ myList.deleteItem(5));
System.out.println(" with list 0 1 2 3 4 5 7 8, got "+myList);
System.out.println("Expected true, got "+ myList.deleteItem(1));
System.out.println(" with list 0 2 3 4 5 7 8, got "+myList);
System.out.println("Expected true, got "+ myList.deleteItem(0));
System.out.println(" with list 2 3 4 5 7 8, got "+myList);
System.out.println("Expected true, got "+ myList.deleteItem(7));
System.out.println(" with list 2 3 4 5 8, got "+myList);
System.out.println("Expected true, got "+ myList.deleteItem(8));
System.out.println(" with list 2 3 4 5, got "+myList);
System.out.println("Expected false, got "+ myList.deleteItem(8));
System.out.println(" with list 2 3 4 5, got "+myList);
}

// Two test classes: the list is empty and it is not
// Boundary analysis gives four cases: 0 elements, 1, 2, and many (5)
private static void testDeleteFirst() throws Exception
{ SortedLList<Integer> myList = new SortedLList<Integer>();
myList.add(4);
myList.add(3);
myList.add(2);
myList.add(1);
myList.add(0);
System.out.println("TESTING deleteFirst()");
System.out.println("Expected 0, got "+ myList.deleteFirst());
System.out.println(" with list 1 2 3 4, got "+myList);
myList.deleteFirst();
myList.deleteFirst();
System.out.println("Expected 3, got "+ myList.deleteFirst());
System.out.println(" with list 4, got "+myList);
System.out.println("Expected 4, got "+ myList.deleteFirst());
System.out.println(" with list , got "+myList);
System.out.print("Expected exception ");
try{myList.deleteFirst();}
catch(Exception e)
{ System.out.println(e);
return;}
System.out.println("but no exception thrown");
}

// Two test classes: the list is empty and it is not
// Boundary analysis gives four cases: 0 elements, 1, 2, and many (5)
private static void testDeleteLast() throws Exception
{ SortedLList<Integer> myList = new SortedLList<Integer>();
myList.add(4);
myList.add(3);
myList.add(2);
myList.add(1);
myList.add(0);
System.out.println("TESTING deleteLast()");
System.out.println("Expected 4, got "+ myList.deleteLast());
System.out.println(" with list 0 1 2 3, got "+myList);
myList.deleteLast();
myList.deleteLast();
System.out.println("Expected 1, got "+ myList.deleteLast());
System.out.println(" with list 0, got "+myList);
System.out.println("Expected 0, got "+ myList.deleteLast());
System.out.println(" with list , got "+myList);
System.out.print("Expected exception ");
try{myList.deleteLast();}
catch(Exception e)
{ System.out.println(e);
return;}
System.out.println("but no exception thrown");
}

// Two test classes: the item is not in the list and it is in it
// Subclasses for the class in which the item is in: is the first slot
// the last, or in the middle
// Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot
// used-1, and some slot in the middle
private static void testFind()
{ SortedLList<Integer> myList = new SortedLList<Integer>();
myList.add(0);
myList.add(1);
myList.add(2);
myList.add(14);
myList.add(20);
myList.add(30);
myList.add(40);
myList.add(50);
System.out.println("TESTING find()");
System.out.println("Expected false, got "+ myList.find(9));
System.out.println("Expected true, got "+ myList.find(0));
System.out.println("Expected true, got "+ myList.find(1));
System.out.println("Expected true, got "+ myList.find(14));
System.out.println("Expected true, got "+ myList.find(40));
System.out.println("Expected true, got "+ myList.find(50));
}
public static void main(String[] args) throws Exception
{

try{ testIsEmpty();
testIsFull();
testAdd();
testDeleteItem();
testDeleteFirst();
testDeleteLast();
testFind();
}
catch(Exception e)
{ System.out.println(" Error, unexpected exception: "+e);}

}
}
AnswerRe: binary search tree error compliation error Pin
I am BATMAN4-May-09 5:43
I am BATMAN4-May-09 5:43 
Questionis there any decryption algorithm that uses a dictionary to decrypt an encrypted file? Pin
Ha lee3-May-09 14:47
Ha lee3-May-09 14:47 
AnswerRe: is there any decryption algorithm that uses a dictionary to decrypt an encrypted file? Pin
I am BATMAN4-May-09 5:47
I am BATMAN4-May-09 5:47 
AnswerRe: is there any decryption algorithm that uses a dictionary to decrypt an encrypted file? Pin
Ha lee4-May-09 10:39
Ha lee4-May-09 10:39 
QuestionHow to get/create Image from the given file name? Pin
Flying_Doc1-May-09 14:09
Flying_Doc1-May-09 14:09 
QuestionJ2EE on Server 2003 Standard Pin
SimonRigby30-Apr-09 1:20
SimonRigby30-Apr-09 1:20 
AnswerRe: J2EE on Server 2003 Standard Pin
adatapost3-May-09 17:37
adatapost3-May-09 17:37 
QuestionHow to do zigzag scanning in java Pin
Flying_Doc29-Apr-09 18:57
Flying_Doc29-Apr-09 18:57 
Questionmoving a graphic Pin
jonig1928-Apr-09 16:13
jonig1928-Apr-09 16:13 
AnswerRe: moving a graphic Pin
Nagy Vilmos28-Apr-09 23:01
professionalNagy Vilmos28-Apr-09 23:01 
Question[Message Deleted] Pin
jonig1928-Apr-09 10:46
jonig1928-Apr-09 10:46 
AnswerRe: move() graphics Pin
fly90428-Apr-09 11:37
fly90428-Apr-09 11:37 
Questionsaving files with current date and time as their names Pin
nicks1128528-Apr-09 2:01
nicks1128528-Apr-09 2:01 
AnswerRe: saving files with current date and time as their names Pin
Jimmanuel28-Apr-09 3:09
Jimmanuel28-Apr-09 3:09 
Questionsending an e-mail Pin
prasadbuddhika26-Apr-09 20:25
prasadbuddhika26-Apr-09 20:25 
AnswerRe: sending an e-mail Pin
Gil Messerman27-Apr-09 6:03
Gil Messerman27-Apr-09 6:03 
GeneralRe: sending an e-mail Pin
shrims4u17-May-09 6:48
shrims4u17-May-09 6:48 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.