C to Java Coding

Cheatx's Avatar, Join Date: Mar 2009
Newbie Member
Hi I'm really new to Java, and I'm trying to make a switch right now. I have the following code in C, and I was just wondering what differences I would have to change to make the code work in Java. The code is a Dictionary library ADT and it's based on a Binary Search Tree. Thanks a lot!

Code:
/*
*    Dictionary.c
*    Binary Search Tree implementation of the Dictionary ADT
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include"Dictionary.h"

/********************************* Private types and functions ***********************/

/*
*  Node
*/
typedef struct Node{
   int key;
   int value;
   struct Node* left;
   struct Node* right;
} Node;

/*
*  NodeRef
*/
typedef Node* NodeRef;

/*
*  Dictionary
*/
typedef struct Dictionary{
   NodeRef root;
   int numPairs;
} Dictionary;

/*
*  newNode
*  Constructor for the private Node type
*/
NodeRef newNode(int k, int v) {
   NodeRef N = malloc(sizeof(Node));
   assert(N!=NULL);
   N->key = k;
   N->value = v;
   N->left = N->right = NULL;
   return(N);
}

/*
*  freeNode
*  Destructor for the private Node type
*/
void freeNode(NodeRef* pN){
   if( pN!=NULL && *pN!=NULL ){
      free(*pN);
      *pN = NULL;
   }
}

/*
*  findKey
*  returns a reference to the Node containing key k in the subtree rooted at R,
*  or NULL if no such Node exists
*/
NodeRef findKey(NodeRef R, int k){
   if(R==NULL || k==R->key) return R;
   if( k<R->key ) return findKey(R->left, k);
   else return findKey(R->right, k);
}

/*
*  findParent
*  returns a reference to the Node which is the parent of N in the subtree rooted
*  at R, or returns NULL if N is equal to R.
*/
NodeRef findParent(NodeRef N, NodeRef R){
   NodeRef P=NULL;
   if( N!=R ){
      P = R;
      for( ; P->left!=N && P->right!=N; P=(N->key<P->key?P->left:P->right) );
   }
   return P;
}

/*
*  findLeftmost
*  returns the leftmost Node in the subtree rooted at R, or NULL if R is NULL.
*/
NodeRef findLeftmost(NodeRef R){
   NodeRef L = R;
   if( L!=NULL) for( ; L->left!=NULL; L=L->left) ;
   return L;
}

/*
*  printInOrder
*  prints the (key, value) pairs belonging to the subtree rooted at R in order
*  of increasing keys to file pointed to by out.
*/
void printInOrder(NodeRef R, FILE* out){
   if( R!=NULL ){
      printInOrder(R->left, out);
      fprintf(out, "%d %d\n", R->key, R->value);
      printInOrder(R->right, out);
   }
}

/*
*  deleteAll
*  deletes all Nodes in the subtree rooted at N.
*/
void deleteAll(NodeRef N){
   if( N!=NULL ){
      deleteAll(N->left);
      deleteAll(N->right);
      freeNode(&N);
   }
}

/********************************* Public functions ******************************/

/*
*  newDictionary
*  Allocates and initializes a struct representing an empty Dictionary.  Returns a
*  pointer to new memory if successful, terminates if not successful.
*/
DictionaryRef newDictionary(void){
   DictionaryRef D = malloc(sizeof(Dictionary));
   assert(D!=NULL);
   D->root = NULL;
   D->numPairs = 0;
   return D;
}

/*
*  freeDictionary
*  Frees all heap memory associated with *pD and sets the reference *pD to NULL
*/
void freeDictionary(DictionaryRef* pD){
   if( pD!=NULL && *pD!=NULL ){
      makeEmpty(*pD);
      free(*pD);
      *pD = NULL;
   }
}

/*
*  isEmpty
*  pre: none
*  post: returns 1 (true) if D is empty, 0 (false) otherwise
*/
int isEmpty(DictionaryRef D){
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling isEmpty() on NULL DictionaryRef\n");
      exit(EXIT_FAILURE);
   }
   return(D->numPairs==0);
}

/*
*  size
*  pre: none
*  post: returns the number of entries in D
*/
int size(DictionaryRef D){
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling size() on NULL DictionaryRef\n");
      exit(EXIT_FAILURE);
   }
   return(D->numPairs);
}

/*
*  lookup
*  pre: none
*  post: returns value associated key k, or UNDEF if no such key exists
*/
int lookup(DictionaryRef D, int k){
   NodeRef N;
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling lookup() on NULL DictionaryRef\n");
      exit(EXIT_FAILURE);
   }
   N = findKey(D->root, k);
   if( N!=NULL ) return N->value;
   else return UNDEF;
}

/*
*  insert
*  inserts new (key,value) pair into D
*  pre: key k currently does not exist in D, i.e. lookup(D, k)==UNDEF
*  post: !isEmpty(D), size(D) is increased by one
*/
void insert(DictionaryRef D, int k, int v){
   NodeRef N, A, B;
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling insert() on NULL DictionaryRef\n");
      exit(EXIT_FAILURE);
   }
   if( findKey(D->root, k)!=NULL ){
      fprintf(stderr, "Dictionary Error: cannot insert() duplicate keys\n");
      exit(EXIT_FAILURE);
   }
   N = newNode(k, v);
   B = NULL;
   A = D->root;
   while( A!=NULL ){
      B = A;
      if( k<A->key ) A = A->left;
      else A = A->right;
   }
   if( B==NULL ) D->root = N;
   else if( k<B->key ) B->left = N;
   else B->right = N;
   D->numPairs++;
}

/*
*  delete
*  deletes pair with the key k
*  pre: key k currently exists in D, i.e. lookup(D, k)!=UNDEF
*  post: size(D) is decreased by one
*/
void delete(DictionaryRef D, int k){
   NodeRef N, P, S;
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling delete() on NULL DictionaryRef\n");
      exit(EXIT_FAILURE);
   }
   N = findKey(D->root, k);
   if( N==NULL ){
      fprintf(stderr, "Dictionary Error: cannot delete() non-existent key\n");
      exit(EXIT_FAILURE);
   }
   if( N->left==NULL && N->right==NULL ){
      if( N==D->root ){
         D->root = NULL;
         freeNode(&N);
      }else{
         P = findParent(N, D->root);
         if( P->right==N ) P->right = NULL;
         else P->left = NULL;
         freeNode(&N);
      }
   }else if( N->right==NULL ){
      if( N==D->root ){
         D->root = N->left;
         freeNode(&N);
      }else{
         P = findParent(N, D->root);
         if( P->right==N ) P->right = N->left;
         else P->left = N->left;
         freeNode(&N);
      }
   }else if( N->left==NULL ){
      if( N==D->root ){
         D->root = N->right;
         freeNode(&N);
      }else{
         P = findParent(N, D->root);
         if( P->right==N ) P->right = N->right;
         else P->left = N->right;
         freeNode(&N);
      }
   }else{
      S = findLeftmost(N->right);
      N->key = S->key;
      N->value = S->value;
      P = findParent(S, N);
      if( P->right==S ) P->right = S->right;
      else P->left = S->right;
      freeNode(&S);
   }
   D->numPairs--;
}

/*
*  makeEmpty
*  pre: none
*  post: isEmpty(D)
*/
void makeEmpty(DictionaryRef D){
   deleteAll(D->root);
   D->root = NULL;
   D->numPairs = 0;
}

/*
*  printDictionary
*  pre: none
*  post: prints a text representation of D to file pointed to by out.
*/
void printDictionary(DictionaryRef D, FILE* out){
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling printDictionary() on NULL DictionaryRef\n");
      exit(EXIT_FAILURE);
   }
   printInOrder(D->root, out);
}
Cheatx's Avatar, Join Date: Mar 2009
Newbie Member
This is what I have so far: (any help is appreciated )

Code:
// Dictionary.java
// Binary Search Tree implementation of the Dictionary ADT

public class Dictionary implements DictionaryInterface {
  
  // private inner Node class
  private class Node {
      int key;
      int value;
      Node left;
      Node right;

      Node(int k, int v){
         key = k;
         value = v;
         left = null;
         right = null;
      }
   }

  // Fields for the IntegerList class
   private Node root;     // reference to root Node in List
   private int numItems;  // number of items in this IntegerList

   // Dictionary()
   // constructor for the Dictionary class
   public Dictionary(){
      root = null;
      numItems = 0;
   }

    // findKey
    // returns a reference to the Node containing key k in the subtree rooted at R,
    // or NULL if no such Node exists

   private Node findKey(int index){
     Node N = root;
     if(index < N.key ) return findKey(index-1);
     else return findKey(index+1);
   }

   // isEmpty()
   // pre: none
   // post: returns true if this Dictionary is empty, false otherwise
   public boolean isEmpty(){
     return (numItems == 0);
   }

   // size()
   // pre: none
   // post: returns the number of entries in this Dictionary
   public int size(){
     return numItems;
   }

   // lookup()
   // pre: none
   // post: returns value associated key k, or UNDEF if no such key exists
   public int lookup(int k){
     
     return 0;
   }

   // insert()
   // inserts new (key,value) pair into this Dictionary
   // pre: key k does not exist in this Dictionary, i.e. lookup(k)==UNDEF
   // post: !isEmpty(), size() is increased by one
   public void insert(int k, int v) throws KeyCollisionException{
     
   }

   // delete
   // deletes the pair with the key k
   // pre: key k currently exists in this Dictionary, i.e. lookup(k)!=UNDEF
   // post: size() is decreased by one
   public void delete(int k) throws KeyNotFoundException{
     
   }

   // makeEmpty()
   // pre: none
   // post: isEmpty()
   public void makeEmpty(){
     root = 0;
     numPairs = 0;
   }

   // toString()
   // overrides Object's toString() method
   // pre: none
   // post: returns a String representation of this Dictionary ordered
   // by ascending keys
   public String toString(){
     String s = "";
     for(Node N=root; N!=null; N=N.left){
       s += N.key + ", " + N.value + " ";
     }
     return s;
   }
}