Go4Expert

Go4Expert (http://www.go4expert.com/)
-   Java (http://www.go4expert.com/forums/java/)
-   -   C to Java Coding (http://www.go4expert.com/forums/c-java-coding-t16551/)

Cheatx 16Mar2009 03:28

C to Java Coding
 
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 16Mar2009 04:28

Re: C to Java Coding
 
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;
  }
}



All times are GMT +5.5. The time now is 03:13.