Saturday, June 28, 2014

Printing : "CAFEBABE" : The Beginning HEX characters in all Java .class files

So I came across something interesting. All java .class files have "CAFEBABE" as the beginning hex characters.

Code for a test:

Some points to note:

1. If you're wondering what ba[i] & 0xff does:
   I.   ba[i] stores byte values.
   II.  0xFF is an int in hex(to the base 16) representation. Basically it is 0x000000FF
   III. & operator is only applied to ints so ba[i] is promoted to an int
 
Suppose we have
  0x001101FF and we are &nding it with
  0x000000FF then we should get

  0x000000FF

If we had not done the &nding with 0xFF,
we would have gotten the output:

    FFFFFFCAFFFFFFFEFFFFFFBAFFFFFFBE so, &nding with 0x000000FF gives us
    000000FF   000000FF  000000FF  000000FF which equals

    000000CA 000000FE 000000BA 000000BE

[Note that (Hex) F = 1111 (Binary), C(or anything between 0 and 255) & F gives C(or that value)]

0s at the start are not printed in output) so you get the output:

CAFEBABE

import java.io.*;

public class Ex19 {
 
 public static void main(String[] args) throws IOException{
    byte[] ba = read(new File("e:\\directory.class"));
    for(int i=0;i<4;++i)
     System.out.print(Integer.toHexString(ba[i] & 0xff).toUpperCase());
    System.out.println();
 }
 
 public static byte[] read(File bFile) throws IOException{
     BufferedInputStream bf = new BufferedInputStream(
       new FileInputStream(bFile));
     try {
       byte[] data = new byte[bf.available()]; 
       bf.read(data);
       return data;
     } finally {
       bf.close();
     }
   }
}

If you are wondering why "CAFEBABE" shows up:

James Gosling, the father of Java programming language, once explained it as follows:
As far as I know, I'm the guilty party on this one. I was totally unaware of the NeXT connection. The small number of interesting HEX words is probably the source of the match. As for the derivation of the use of CAFEBABE in Java, it's somewhat circuitous:
We used to go to lunch at a place called St Michael's Alley. According to local legend, in the deep dark past, the Grateful Dead used to perform there before they made it big. It was a pretty funky place that was definitely a Grateful Dead Kinda Place. When Jerry died, they even put up a little Buddhist-esque shrine. When we used to go there, we referred to the place as Cafe Dead.
Somewhere along the line it was noticed that this was a HEX number. I was re-vamping some file format code and needed a couple of magic numbers: one for the persistent object file, and one for classes. I used CAFEDEAD for the object file format, and in grepping for 4 character hex words that fit after CAFE (it seemed to be a good theme) I hit on BABE and decided to use it.
At that time, it didn't seem terribly important or destined to go anywhere but the trash-can of history. So CAFEBABE became the class file format, and CAFEDEAD was the persistent object format. But the persistent object facility went away, and along with it went the use of CAFEDEAD - it was eventually replaced by RMI.

Wednesday, June 25, 2014

File Search Program in Java [Search Based on File Name (Regex) + Text Content in files][Multi-directory]

This program takes the input:

1. Directory to look in
2. Name to look for
3. Content to look for in text files

And returns the list of file names that are relevant. Helper classes

1. PPrint is for displaying the Collection (result) with proper formatting.
2. TextFile is used to convert the documents being searched into an ArrayList of String (Words)
3. static List<String> words stores the words to look for in text files. (input by user as command line arguments)
4. Be careful, don't consider File object representing a directory as a Readable file otherwise you'll get a [ FileNotFoundException : Access Denied].
5. Rest of the code should be understandable by itself.

A sample run:

Suppose we have a directory structure:

And we run:

E:\>java Directory e:\SomeFolder .*xyz.* random

We'll get this output:

dirs: [e:\SomeFolder\AnotherFolder]

files: [
  e:\SomeFolder\abc.txt
  e:\SomeFolder\AnotherFolder\xyz.txt
]

//xyz.txt as it matches the pattern
//abc.txt as it has the string "random"

Code:

import java.util.regex.*;
import java.io.*;
import java.util.*;

class PPrint {
 public static String pformat(Collection<?> c) {
  if(c.size() == 0) return "[]";
  StringBuilder result = new StringBuilder("[");
  for(Object elem : c) {
   if(c.size() != 1)
    result.append("\n  ");
   result.append(elem);
  }
  if(c.size() != 1)
   result.append("\n");
  result.append("]");
  return result.toString();
 }
 public static void pprint(Collection<?> c) {
  System.out.println(pformat(c));
 }
 public static void pprint(Object[] c) {
  System.out.println(pformat(Arrays.asList(c)));
 }
} 

class TextFile extends ArrayList<String> {
 // Read a file as a single string:
 public static String read(String fileName) {
  StringBuilder sb = new StringBuilder();
  try {
   BufferedReader in= new BufferedReader(new FileReader(
     new File(fileName).getAbsoluteFile()));
   try {
    String s;
    while((s = in.readLine()) != null) {
     sb.append(s);
     sb.append("\n");
    }
   } finally {
    in.close();
   }
  } catch(IOException e) {
   throw new RuntimeException(e);
  }
  return sb.toString();
 }
 
 // Read a file, split by any regular expression:
 public TextFile(String fileName, String splitter) {
  super(Arrays.asList(read(fileName).split(splitter)));
  // Regular expression split() often leaves an empty
  // String at the first position:
  if(get(0).equals("")) remove(0);
 }
 // Normally read by lines:
 public TextFile(String dir) {
  this(dir, "\n");
 }
 
}
public final class Directory{ 
 public static class TreeInfo implements Iterable<File>{
  public List<File> files = new ArrayList<File>();
  public List<File> dirs = new ArrayList<File>();

  public Iterator<File> iterator(){
   return files.iterator();
  }

  void addAll(TreeInfo other){
   files.addAll(other.files);
   dirs.addAll(other.dirs);
  }

  public String toString(){
   return "dirs: "+PPrint.pformat(dirs) + 
     "\n\nfiles: "+PPrint.pformat(files);
  }
 }

 public static TreeInfo walk(String start, String regex){
  return recurseDirs(new File(start), regex);
 }

 public static TreeInfo walk(File start, String regex){
  return recurseDirs(start, regex);
 }

 public static TreeInfo walk(File start){
  return recurseDirs(start, ".*");
 }

 public static TreeInfo walk(String start){
  return recurseDirs(new File(start), ".*");
 }

 static List<String> words = new ArrayList<String>();
 static TreeInfo recurseDirs(File startDir, String regex){
  TreeInfo result = new TreeInfo();
  for(File item:startDir.listFiles()){
   if(item.isDirectory()){
    result.dirs.add(item);
    result.addAll(recurseDirs(item, regex));
   }else if(item.getName().matches(regex)){
     result.files.add(item);
    }
   
   if(item.isFile()){

    TextFile tf = new TextFile(item.getAbsolutePath(), "\\W+");
    if(!Collections.disjoint(tf, words)){
     if(!result.files.contains(item))
      result.files.add(item);
    }
   }
  }
  return result;
 }

 public static void main(String[] args){
    if(args.length<2){
     System.out.println("Usage: java Directory <dir to search in> <regex pattern to match in file names> <word to look for in files> <more words> <more...>");
    }else{
     for(int i=2;i<args.length;++i){
      words.add(args[i]);
     }
     System.out.println(walk(args[0], args[1]));
    } 
 }
}


File search Program [Java][Search Based on File Name + Text Content]

This program only finds matching file names && (word) content and displays the results to the user. It does NOT search in any sub-directories (to keep it simple). I'll be posting the complete code (with sub-directory search) soon. [Here's the link : post]

import java.util.regex.*;
import java.io.*;
import java.util.*;

public class DirList {
 public static void main(String[] args){
  if(args.length<2){
   System.out.println("Usage: java DirList <directory path> <file names to match (regex)> <word1 to look for in files> <another word> <and so on>");
   return;
  }
  File path = new File(args[0]);
  String[] list; 
  list = path.list(new DirFilter(args));
  Arrays.sort(list, String.CASE_INSENSITIVE_ORDER);
  for(String dirItem : list)
   System.out.println(dirItem);
 }
}

class DirFilter implements FilenameFilter{
 private Pattern pattern;
 private  String[] clWords;

 public DirFilter(String[] args){
  pattern = Pattern.compile(args[1]);
  clWords = new String[args.length-2];
  for(int i=2;i<args.length;i++) clWords[i-2] = args[i];
 }

  /*
    The list() method above tests the "name" of each file 
    in the directory "dir" to match the regex and to check whether 
    the file contains ANY (check the Collections.disjoint() function) 
    words specified by the user
  */
 public boolean accept(File dir, String name){ 
  if(pattern.matcher(name).matches()){ 
   if((new File(dir.getAbsolutePath()+"\\"+name)).isFile()){ 
    TextFile tf = new TextFile(dir.getAbsolutePath()+"\\"+name,"\\W+");
    if(Collections.disjoint(tf, Arrays.asList(clWords)))
     return false;
   }
   return true;
  }
  return false;
 }
}

//Helper (File Reader) class - Reads the words of the specified file into an ArrayList<String>

class TextFile extends ArrayList<String> {
  // Read a file as a single string:
  public static String read(String fileName) {
    StringBuilder sb = new StringBuilder();
    try {
      BufferedReader in= new BufferedReader(new FileReader(
        new File(fileName).getAbsoluteFile()));
      try {
        String s;
        while((s = in.readLine()) != null) {
          sb.append(s);
          sb.append("\n");
        }
      } finally {
        in.close();
      }
    } catch(IOException e) {
      throw new RuntimeException(e);
    }
    return sb.toString();
  }

  // Read a file, split by any regular expression:
  public TextFile(String fileName, String splitter) {
    super(Arrays.asList(read(fileName).split(splitter)));
    // Regular expression split() often leaves an empty
    // String at the first position:
    if(get(0).equals("")) remove(0);
  }
  // Normally read by lines:
  public TextFile(String fileName) {
    this(fileName, "\n");
  }
}

Sunday, June 22, 2014

Codeforces Round #253 (Div. 2) Problem A

(Not very difficult -.-)
A. Anton and Letters
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Recently, Anton has found a set. The set consists of small English letters. Anton carefully wrote out all the letters from the set in one line, separated by a comma. He also added an opening curved bracket at the beginning of the line and a closing curved bracket at the end of the line.
Unfortunately, from time to time Anton would forget writing some letter and write it again. He asks you to count the total number of distinct letters in his set.
Input
The first and the single line contains the set of letters. The length of the line doesn't exceed 1000. It is guaranteed that the line starts from an opening curved bracket and ends with a closing curved bracket. Between them, small English letters are listed, separated by a comma. Each comma is followed by a space.
Output
Print a single number — the number of distinct letters in Anton's set.
Sample test(s)
input
{a, b, c}
output
3
input
{b, a, b, a}
output
2
input
{}
output
0


My Solution: [Java]

→ Source
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;


public class AntonNLetters {
 public static void main(String[] args){
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String input="";
  try{input = br.readLine();}catch(IOException e){System.out.print(e);}
  
  if(input.charAt(1)=='}'){
   System.out.println(0);
   return;
  }
  
  HashSet<Character> set = new HashSet<Character>();
  for(int i=1;i<=input.length()-1;i=i+3){
   set.add(input.charAt(i));
  }
  System.out.println(set.size());
 }
}

Tuesday, June 10, 2014

[Binary Tree] : List construction and operations using a Binary Tree [Array Implementation] [Java]

We'll construct a list of a predefined size using a binary tree with support for delete operation.
To find an element in this list is more efficient that linear search in arrays. The number of operations to be performed is less than or equal to the depth d of the tree plus 1 (d+1).

1. n is the number of leaves i.e. the number of elements to be contained in the list
2. d is the depth of the tree
3. Nodes are numbered starting at 0 for the root of the binary tree.
4. size is the number of nodes (leaves+non leaves) in the binary tree and is given by 2*n-1
    i.e.  

    size = 2 * n - 1
5. The first elements of the list are assigned to nodes numbered 2^d - 1 through 2* n - 2 and
6. the remainder (if any) to nodes numbered n - 1 through 2 ^ d - 2
7. info field contains the content of the node
8. BLANKS in info means that the node is non-leaf node
9. lcount stands for the number of leaves in the left subtree of the node. (left child)
10. lcount = 0 means that the node is a leaf node.
11. buildtree takes user input to build the binary tree structure of the list.
12. findelement is a method that can be used to access the list contents using their indexes with number of           operations less than d+1
13. delete method deletes an element from the list and restructure the binary tree.

                    0
             1             2
     3           4    5          6

if we delete list element 4 i.e. element number 6 in the binary tree structure, the resulting structure will become

                    0
             1             2->this element will store the contents of element #5
     3           4  

14. Display method displays the list content starting from element number 1 in the list.

Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class TreeArray {

    private static int MAXELTS = 100;
    private static int NUMNODES = 2 * MAXELTS - 1;
    private static String BLANKS = "          ";

    static class nodetype {

        String info;
        int lcount;
        boolean used;
    }

    static nodetype[] node = new nodetype[NUMNODES];

    static {
        for (int i = 0; i < NUMNODES; ++i) {
            node[i] = new nodetype();
        }
    }

    static int findelement(int k) {
        int p, r;

        r = k;
        p = 0;
        while (node[p].info.matches(BLANKS)) {
            if (r <= node[p].lcount) {
                p = p * 2 + 1;
            } else {
                r -= node[p].lcount;
                p = p * 2 + 2;
            }
        }
        return p;
    }

    static void delete(int p) {
        int b, f, q;

        if (p == 0) {
            node[p].used = false;
        } else {
            f = (p - 1) / 2;
            if (p % 2 != 0) {
                b = 2 * f + 2;
                --node[f].lcount;
            } else {
                b = 2 * f + 1;
            }

            if (!node[b].info.matches(BLANKS)) {
                node[f].info = node[b].info;
                node[b].used = false;
            }

            node[p].used = false;
            q = f;

            while (q != 0) {
                f = (q - 1) / 2;
                if (q % 2 != 0) {
                    --node[f].lcount;
                    b = 2 * f + 2;
                } else {
                    b = 2 * f + 1;
                }
                if (!node[b].used && !node[q].info.matches(BLANKS)) {
                    node[f].info = node[q].info;
                    node[q].used = false;
                }
                q = f;
            }
        }
    }

    static int size, n; //n is the number of leaves

    static void buildtree(int n) {
        int d, f, i, p, power;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        d = 0;
        power = 1;
        while (power < n) {
            ++d;
            power *= 2;
        }
        size = 2 * n - 1;
        int index = 0;
        for (i = power - 1; i < size; i++, index++) {
            try {
                System.out.println("Enter element #" + index + " info: ");
                node[i].info = br.readLine();
                node[i].used = true;
            } catch (IOException e) {
                System.out.println("Error reading input");
            }
        }
        for (i = n - 1; i < power - 1; i++, index++) {
            try {
                System.out.println("Enter element #" + index + " info: ");
                node[i].info = br.readLine();
                node[i].used = true;
            } catch (IOException e) {
                System.out.println("Error reading input");
            }
        }
        for (i = 0; i < n - 1; ++i) {
            node[i].used = true;
            node[i].lcount = 0;
            node[i].info = BLANKS;
        }

        for (i = n - 1; i < size; ++i) {
            p = i;
            while (p != 0) {
                f = (p - 1) / 2;
                if (p % 2 != 0) {
                    ++node[f].lcount;
                }
                p = f;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Enter the size of the list: ");
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();

        buildtree(n);
        System.out.println("\nTree List contructed successfully!");

        System.out.println("\n\nIndex of element to display contents of: ");
        System.out.println("Contents: " + node[findelement(scan.nextInt())].info);

        System.out.println("Index of Element to delete: ");
        delete(findelement(scan.nextInt()));

        System.out.println();
        display(0);
    }

    static void display(int elementNo) {
        if ((elementNo * 2 + 1) < size && node[elementNo * 2 + 1].used == true) {
            if (!node[elementNo * 2 + 1].info.matches(BLANKS)) {
                System.out.println(node[elementNo * 2 + 1].info + " ");
            }
            display(elementNo * 2 + 1);
        }
        if ((elementNo * 2 + 2) < size && node[elementNo * 2 + 2].used == true) {
            if (!node[elementNo * 2 + 2].info.matches(BLANKS)) {
                System.out.println(node[elementNo * 2 + 2].info + " ");
            }
            display(elementNo * 2 + 2);
        }
    }
}

A sample run:

Enter the size of the list: 
4
Enter element #0 info: 
11
Enter element #1 info: 
22
Enter element #2 info: 
33
Enter element #3 info: 
44

Tree List contructed successfully!


Index of element to display contents of: 
4
Contents: 44
Index of Element to delete: 
4

11 
22 
33 

Saturday, June 7, 2014

Threaded Binary Tree : Construction and Inorder Traversal [Java]

Threaded Binary Trees: Instead of containing a null pointer in its right field, a node with an empty right subtree points to its inorder successor. Such a pointer is called a thread. Note that the rightmost node in each tree still has a null right pointer, since it has no inorder successor. Such trees are called right in--threaded binary trees. A threaded binary tree eliminates the need for a stack in a nonrecursive traversal even if a father field is not available.

To implement a right in-threaded binary tree under the dynamic node implementation of a binary tree, and extra logical field, rthread, is included within each node to indicate whether or not its right pointer is a thread. For consistency, the rthread field of the rightmost node of a tree (i.e. the last node in the tree's inorder traversal) is also set to true, although its right field remains null.


The inorder traversal of a binary tree gives its elements in ascending order. So if the user inputs (-999 is end marker for input):

1 2 5 2 3 4 6 7 4 5 7 7 -999

the output will be

1 2 2 3 4 4 5 5 6 7 7 7

which is in ascending order, as expected.

Important sections of the code are italicized. They should be understood carefully.

import java.util.Scanner;

class nodetype {

    int info;
    nodetype left;  /*reference to left son*/

    nodetype right; /*reference to right son*/

    boolean rthread; /*
     rhtread is TRUE if right is
     null or non-null THREAD 
     */

}

public class ThreadedBinaryTrees {

    static nodetype maketree(int x) {
        nodetype p;

        p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        p.rthread = true;
        return p;
    }

    static nodetype getnode() {
        return new nodetype();
    }

    static void setleft(nodetype p, int x) {
        nodetype q;

        if (p == null) {
            System.out.println("Void insertion\n");
        } else if (p.left != null) {
            System.out.println("Invalid insertion\n");
        } else {
            q = getnode();
            q.info = x;
            p.left = q;
            q.left = null;
            /* The inorder successor of node(q) is node(p) */
            q.right = p;
            q.rthread = true;
        }/*end if*/

    }/*end setleft*/


    static void setright(nodetype p, int x) {
        nodetype q, r;

        if (p == null) {
            System.out.println("Void insertion\n");
        } else if (!p.rthread) {
            System.out.println("Invalid insertion\n");
        } else {
            q = getnode();
            q.info = x;
            /* save the inorder successor of node(p) */
            r = p.right;
            p.right = q;
            p.rthread = false;
            q.left = null;
            /*the inorder successor of node(q) is the previous suuccessor of node(p)*/
            q.right = r;
            q.rthread = true;
        } /* end else */

    }     /* end setright */


    static void intrav3(nodetype tree) {
        nodetype p, q;
        p = tree;
        do {
            q = null;
            while (p != null) { /* Traverse left branch */

                q = p;
                p = p.left;
            }/*end while*/

            if (q != null) {
                System.out.print(q.info + " ");
                p = q.right;
                while (q.rthread && p != null) {
                    System.out.print(p.info + " ");
                    q = p;
                    p = p.right;
                }/* end while */

            }/* end if */

        } while (q != null);
    }
    
    public static void main(String[] args){
        nodetype ptree;
        nodetype p = null, q;
        int number;
        
        System.out.println("Binary Tree Traversal\n\n");
        System.out.println("Enter numbers :");
        Scanner scan = new Scanner(System.in);
        number = scan.nextInt();
        
        ptree = maketree(number);
        
        while((number=scan.nextInt())!=-999){
            p = q = ptree;
            while(q!=null){
               p=q;
            if(number<p.info)
                q = p.left;
            else if(number>=p.info){
                if(!p.rthread){
                q = p.right;
                }
                if(p.rthread){
                    setright(p, number);
                    break;
                }                  
            }
        }
    
         if (number<p.info)
            setleft(p, number); 
        }
        
        System.out.println("\nInorder traversal : ");
        intrav3(ptree);
    }
}

Binary Tree Traversal using Recursive and Non-Recursive Methods [Java]

This program takes user input into a binary tree and the traverses the tress displaying the values using recursive and non recursive functions (Non recursive function for Inorder traversal):

Suppose the user inputs (-999 is taken as an end marker for input):
14 15 4 9 7 18 3 5 16 4 20 17 9 14 5 -999

The output of the program using both methods is (for Inorder traversal):
3 4 4 5 5 7 9 9 14 14 15 16 17 18 20 
Java Code:

import java.util.Scanner;

class nodetype{
    public int info;
    public nodetype left;
    public nodetype right;
}

public class NonRecursiveInorderTreeTraversal {
    
    //General tree construction code
    static nodetype getnode(){
        return new nodetype();
    }
    
    static nodetype maketree(int x){
        nodetype p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        return p;
    }
    
    static void setleft(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.left != null)
            System.out.println("invalid insertion\n");
        else p.left = maketree(x);
    }
    
    static void setright(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.right != null)
            System.out.println("invalid insertion\n");
        else
         p.right = maketree(x);
    }
    
    /* Traversal in preorder, inorder and postorder */
    static void pretrav(nodetype tree){
        if(tree!=null){
            System.out.print(tree.info+" ");
            pretrav(tree.left);
            pretrav(tree.right);
        }
    }
    
    static void intrav(nodetype tree){
        if(tree!=null){
            intrav(tree.left);
            System.out.print(tree.info+" ");
            intrav(tree.right);
        }
    }
    
    static void posttrav(nodetype tree){
        if(tree!=null){
            posttrav(tree.left);
            posttrav(tree.right);
            System.out.print(tree.info+" ");
        }
    }
    /***   ***/

    
     private static int MAXSTACK = 100;
    
     //Code for the stack used
     static class stack{
         int top;
         nodetype[] item = new nodetype[MAXSTACK];
        
        {
            top = 0;
            item = new nodetype[MAXSTACK];
        }
        
         void push(nodetype it){
            if(top<MAXSTACK)
            item[top++] = it;
            else
                System.out.println("Stack Overflow!");
        }
         nodetype pop(){
            if(top!=0)
                return item[--top];
            else
                System.out.println("Nothing to pop!");
            return null;
        }
         boolean empty(){
            if(top==0){
                return true;
            }
            return false;
        }
    }
    
    //Non Recursive traversal method (inorder) using stack
static void intrav2(nodetype tree){ stack s = new stack(); s.top = 0; nodetype p = tree; do{ /*                 travel down left branches as far as possible                 saving pointers to nodes passed             */ while(p!=null){ s.push(p); p = p.left; } /*end while*/ /*check if finished */ if(!s.empty()){ /* at this point the left subtree is empty */ p = s.pop(); System.out.print(p.info+" "); /*visit the root*/ p = p.right; /*traverse right subtree*/ } /*end if*/ }while(!s.empty() || p!= null); }/* end funtion */ public static void main(String[] args){ nodetype ptree; nodetype p = null, q; int number; System.out.println("Binary Tree Traversal\n\n"); System.out.println("Enter numbers :"); Scanner scan = new Scanner(System.in); number = scan.nextInt(); ptree = maketree(number); while((number=scan.nextInt())!=-999){ p = q = ptree; while(q!=null){ p=q; if(number<p.info) q = p.left; else if(number>=p.info) q = p.right; } if (number<p.info) setleft(p, number); else if(number>=p.info) setright(p, number); } System.out.println("\nUsing recursive function intrav: "); intrav(ptree); System.out.println("\nUsing non recursive function intrav2: "); intrav2(ptree); } }

Duplicate Finder [Tree Implementation][Array implementation of nodes] in Java

The program finds duplicate numbers as the users enters them. This is the array implementation using Java.

The array implementation is beneficial when we have to work with a fixed number of almost complete binary trees. This is more space efficient if the tree has more number of leaves so that all the array positions are occupied. If array positions are not being occupied efficiently, consider using the dynamic allocation. If more flexibility of access is needed, dynamically allocated nodes can be used.

The array implementation here uses MAXNODES = 500.
So that we can store a max of 16 numbers in the almost complete binary tree as explained:

As an example let us suppose that the user inputs:

1 2 3 4 5 6 7 8 9 

The numbers up to 8 are stored in array locations: 0 2 6 14 30 62 126 254 according to 2*(p)+2
So that when 9 is entered the next location will be 2*254+2 = 508+2 = 510 >500 (Overflow!)

Now the user can only enter numbers less than 1. So that when the user enters new sequence:

-1 -2 -3 -4 -5 -6 -7 -8  -9

The array location would be: 1 3 7 15 31 63 127 255 according to 2*(p)+1
So that when -9 is encountered the next calculated location is 2*255+1 = 511 > 500 = Overflow!

So that the total number of insertions becomes 8+8 = 16. It is clear that a dynamic allocated implementation would have stored 500 numbers but it would have also included overhead of left and right fields along with the info field for each node in the tree.

Code for the array implementation in Java: 

import java.util.Scanner;

class nodetype{
    int info;
    boolean used;
}

public class arrayDuplicateFinder {

    static int NUMNODES = 500;
    static nodetype[] node = new nodetype[NUMNODES];
       
    static{
        for(int i=0; i<node.length;++i){
            node[i] = new nodetype();
        }
    }
    
    static void maketree(int x){
        
       node[0].info = x;
       node[0].used = true;
       
       for(int i =1;i<NUMNODES;++i){
           node[i].used = false;
       }
   }
   
   static void setleft(int p, int x){
       int q = 2*p+1;
       if(q>=NUMNODES)
            System.out.println("Array overflow!");
       else if(node[q].used)
           System.out.println("Invalid insertion");
       else{
           node[q].info = x;
           node[q].used = true;
       }
   }
   
   static void setright(int p, int x){
       int q = 2*p+2;
       if(q>=NUMNODES)
           System.out.println("Array overflow!");
       else if(node[q].used)
           System.out.println("Invalid insertion");
       else{
           node[q].info = x;
           node[q].used = true;
       }
   }
   
   public static void main(String[] args){
      
       int p = 0,q = 0,number;
       Scanner scan = new Scanner(System.in);
       
       System.out.println("Enter numbers: ");
       number = scan.nextInt();
       maketree(number);
       
       while((number=scan.nextInt())!=-999){
           p = q = 0;
           while(q< NUMNODES && node[q].used && number!=node[p].info){
               p=q;
               if(number<node[p].info)
                   q = 2*p+1;
               else
                   q = 2*p+2;
           }
       
       if(number == node[p].info)
           System.out.println(number+" is a duplicate");
       else if(number<node[p].info)
           setleft(p, number);
       else
           setright(p, number);
     }
   }
}

Friday, June 6, 2014

Duplicate Finder [Tree Implementation][Dynamically allocated nodes] in C++ and Java

The program finds duplicate numbers as the user enters a list of numbers:

                                                                   C++

#include <iostream>

using namespace std;
 
struct nodetype{
 int info;
 struct nodetype *left;
 struct nodetype *right; 
};

typedef struct nodetype *NODEPTR;

NODEPTR getnode(){
 return new nodetype;
}

NODEPTR maketree(int x){
 NODEPTR p = getnode();
 p->info = x;
 p->left = NULL;
 p->right = NULL;
 return p;
}

void setleft(NODEPTR p, int x){
 if (p == NULL)
  printf("void insertion\n");
 else if (p->left != NULL)
  printf("invalid insertion\n");
 else p->left = maketree(x);
}

void setright(NODEPTR p, int x){
 if (p == NULL)
  printf("void insertion\n");
 else if (p->right != NULL)
  printf("invalid insertion\n");
 else p->right = maketree(x);
}


int main(){
 NODEPTR ptree;
 NODEPTR p, q;
 int number;

 cout << "Enter a number from the list: ";
 cin >> number;
 ptree = maketree(number);
 while ((cout<<"\nEnter number: ")&&cin >> number){
  p = q = ptree;
  while (number != p->info && q != NULL){
   p = q;
   if (number < p->info)
    q = p->left;
   else
    q = p->right;
  }
  if (number == p->info)
   cout << endl << "*** " << number << " is a duplicate *** \n";
  else if (number < p->info)
   setleft(p, number);
  else
   setright(p, number);
 }
}



                               [JAVA]

import java.util.Scanner;


class nodetype{
    public int info;
    public nodetype left;
    public nodetype right;
}


public class Tree {
    static nodetype getnode(){
        return new nodetype();
    }
    
    static nodetype maketree(int x){
        nodetype p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        return p;
    }
    
    static void setleft(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.left != null)
            System.out.println("invalid insertion\n");
        else p.left = maketree(x);
    }
    
    static void setright(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.right != null)
            System.out.println("invalid insertion\n");
        else p.right = maketree(x);
    }
    
    public static void main(String[] args){
        nodetype ptree;
        nodetype p = null, q;
        int number;
        
        System.out.println("Duplicate finder\n\n");
        System.out.println("Enter numbers :");
        Scanner scan = new Scanner(System.in);
        number = scan.nextInt();
        
        ptree = maketree(number);
        
        while((number=scan.nextInt())!=-999){
            p = q = ptree;
            while(number != p.info && q!=null){
                p=q;
            if(number<p.info)
                q = p.left;
            else
                q = p.right;
        }
        
        if(number == p.info)
            System.out.println("*** "+number+" is a duplicate ***\n");
        else if (number<p.info)
            setleft(p, number);
        else
            setright(p, number);
        }
    }
}