Thread: Dictionary using Distributed Hash Table and BST Tree

Hello. I have a problem with my code.
I have implemented BST Tree as well as DHT but my code doesn't work.
Here it is:

import java.util.Scanner;
 
public class JavaApplication18 
{
    public static Scanner scan = new Scanner(System.in);
 
    public static void main(String[] args) 
    {
            int n = scan.nextInt();
            DHT dictionary = new DHT(n);
 
            String s = scan.next();
 
            int m = 0;
            while(!"#".equals(s))
            {
                int p = hash(s, n);
                dictionary.insert(s, p);
                m++;
            }
 
            System.out.println(m);
            int k = scan.nextInt();
            String function;
            for(int j = 0; j < k; j++)
            {
                function = scan.next();
 
                if(function.charAt(0) == 'S')
                {
                    String info = s.substring(7);
                    int y = hash(info, n) - 1;
                    System.out.println(info + ": " + dictionary.search(info, y));
                } else if(function.charAt(0) == 'I') {
                    String info = s.substring(7);
                    int y = hash(info, n) - 1;
                    System.out.println(info + ": " + dictionary.insert(info, y));
                } else {
                    String info = s.substring(7);
                    int y = hash(info, n) - 1;
                    System.out.println(info + ": " + dictionary.delete(info, y));
                }
            }
    }
 
    public static class Word
    {
        public String info;
        public Word left;
        public Word right;
        public int hMany;
        public int val;
 
        Word(String value, int k) 
        {
            info = value;
            left = right = null;
            hMany = 1;
            val = k;
        }
    }
 
    public static class BST
    {
        protected Word root;
 
        public BST() 
        {
            root = null;
        }
 
        protected int insert(String x, int k)
        {
            System.out.print("kkk");
            Word s, p = root, prev;
            s = new Word(x, k);
            boolean t = false;
 
            if(root == null)
            {
                root = s;
            } else {
                prev = null;
                while(p != null)
                {
                    prev = p;
 
                    if(s.val == p.val && x.equals(p.info))
                    {
                        p.hMany++;
                        t = true;
                        break;
                    } else if(s.val < p.val) {
                        p = p.left;
                    } else {
                        p = p.right;
                    }
                }
 
                if(t == false && s.val < p.val)
                {
                    prev.left = s;
                } else if(t == false) {
                    prev.right = s;
                }
            }
 
            if(t)
            {
                return p.hMany;
            } else {
                return s.hMany;
            }
        }
 
        protected int remove(String x, int t) 
        {
            Word p = root;
            Word ds = null;
            int lp = 0;
 
            while(p != null) // finding parent
            {
                if(t < p.left.val)
                {
                    p = p.left;
                } else if(p.right.val == t && p.right.info.equals(x)) {
                    ds = p.right;
                    lp = 1;
                    break;
                } else if(p.left.val == t && p.left.info.equals(x)) {
                    ds = p.left;
                    lp = 2;
                    break;
                } else {
                    p = p.right;
                }
            }
 
            boolean g = false;
 
            if(ds.hMany > 1) // deleting
            {
                ds.hMany--;
            } else {
                g = true;
 
                if(lp == 2)
                {   
                    while(true)
                    {
                        if(ds.left == null && ds.right == null)
                        {
                            p.left = null;
                            break;
                        } else if(ds.left != null && ds.right == null) {
                            p.left = ds.left;
                            break;
                        } else if(ds.right != null && ds.left == null) {
                            p.left = ds.right;
                            break;
                        } else {
                            Word temp = ds.right;
 
                            while(temp.left != null && temp.left.left != null)
                            {
                                temp = temp.left;
                            }
 
                            ds.info = temp.left.info;
                            p = temp;
                            ds = temp.left;
                        }
                    }
                } else {
                    while(true)
                    {
                        if(ds.left == null && ds.right == null)
                        {
                            p.right = null;
                            break;
                        } else if(ds.left != null && ds.right == null) {
                            p.right = ds.left;
                            break;
                        } else if(ds.right != null && ds.left == null) {
                            p.right = ds.right;
                            break;
                        } else {
                            Word temp = ds.right;
 
                            while(temp.left != null && temp.left.left != null)
                            {
                                temp = temp.left;
                            }
 
                            ds.info = temp.left.info;
                            p = temp;
                            ds = temp.left;
                        }
                    }
                }
            }
 
            if(g)
            {
                return 0 ;
            } else {
                return ds.hMany;
            }
        }
 
        private int find(String x, int t) 
        {
            Word p = root;
 
            while(p != null && t != p.val)
            {
                if(t < p.val)
                {
                    p = p.left;
                } else if(t == p.val && x.equals(p.info)) {
                    break;
                } else {
                    p = p.right;
                }
            }
 
            return p.hMany;
        }
    }
 
    public static class DHT 
    {
        public BST[] bst;
 
        DHT(int n)
        {
            bst = new BST[n];
 
            for(int i = 0; i < n; i++)
            {
                bst[i] = new BST();
            }
        }
 
        public int insert(String x, int k)
        {
            return bst[k].insert(x, k);
        }
 
        public int search(String x, int k)
        {
            return bst[k].find(x, k);
        }
 
        public int delete(String x, int k)
        {
            return bst[k].remove(x, k);
        }
    }
 
        public static int hash(String key, int l)
        {
            int value = 0;
            int len = key.length() - 1;
 
            for(int j = 0; j < key.length(); j++ ) 
            {
                value += toDig(key.charAt(j)) * Math.pow(53, len);
                len--;
            }
 
            value = value % l;
 
            return value;
        }
 
        private static int toDig(char a)
        {
            int value = 0;
            if(Character.isLowerCase(a))
            {
                value = a - ('a' - 1);
            } else if(Character.isUpperCase(a)) {
                value = a - ('A' - 27);
            } else if(a == ' ') {
                value = 53;
            }
            return value;
        }
 
}

It takes:
1. The length of the DHT
2. Words separated with spaces and finished with #
3. The number of operations on the dictionary
4. Operations (SEARCH, DELETE, INSERT)

While typing:
7
a b c d e f g h i j k a a b w # // this is the place where my program crashes
6
SEARCH a
INSERT z
DELETE a
SEARCH x
DELETE b
DELETE w

A "wild" exception appears:
Exception in thread "main" java.lang.NullPointerException
at javaapplication17.JavaApplication17$DHT.insert(Jav aApplication17.java:249)

It should return:
n= 15
a: 3
z: 1
a: 2
x: 0
b: 1
w: 0

I will appreciate any help.
Thanks.

Exception in thread "main" java.lang.NullPointerException
at javaapplication17.JavaApplication17$DHT.insert(Jav aApplication17.java:249)

Look at line 249 in the code and find which variable has the null value. Then backtrack in the code t see why that variable does not have a valid non-null value.
If you can't tell what variable is null, add a println before line 249 and print out the values of all the variables used on line 249.

Can you post the code that shows what you printed and the statement where the NPE occurs.
It normally takes a variable with a null value to create a NPE. Did you print ALL of the variables?

The code you posted has compiler errors in it.

That was a big waste of time. Posting code with so many errors.

Can you explain what the problem with the code is now?

For testing please put all the answers to the questions the code asks in the Scanner object?
The idea is to have the program have all the answers in it and then execute the part of the program where the problem is.

Change the Scanner definition like this:

 Scanner scan = new Scanner("7\na b c d e f g h i j k a a b w #\n <AND REST HERE>");

The problem is clearly in the insert method of the BST/DHT class. It crashes at the beginning, while passing the variables from DHT insert to BST insert. It doesn't even print anything when I add a line with a System print out(BST insert).

It crashes at the beginning

Please post the full text of the error message.

What variable on line 244 is null? See post#2

Well, i Can't find such a variable. Though when i was trying to debug, i found that the program has some problems with the DHT constructor. This is what it displayed: Not able to submit breakpoint MethodBreakpoint [JavaApplication18$DHT].DHT '(I)Lvoid;', reason: Method 'DHT' with signature '(I)Lvoid;' does not exist in class JavaApplication18$DHT.

Maybe i am declaring the table in a bad way?

What code is on line 244? What variables are used on that line? Which of those variables is null?

declaring the table in a bad way

What variable is the table? Where is it defined?

return bst[k].insert(x, k);

variables: x, k, bst array.
x = a
k = n
bst[1 - n] = null

line 236
public static class DHT
{
public BST[] bst;

DHT(int n)
{
bst = new BST[n];
}
}

If bst[k] is null, where do you assign any values to the elements of the bst array?
There are two steps in using an array of objects:
1) define the array
2) fill the array elements with instances of the class

I have modified the constructor. Trying to fill the array with the instances.
DHT(int n)
{
bst = new BST[n];

for(int i = 0; i < n; i++)
{
bst[i] = new BST();
}
}

Figured it out.

Though now my program works badly and gives a line of "k" instead of some results. The 3 methods in BST must be wrong somewhere.

Make the class static.

Can you explain the problem?

Are you asking if a word needs a different hashcode for each position it goes to in the container where you are storing it? I don't know the specific algorithm that you are trying to code for to be able to say how it should be done.
What is the definition of how words are to be stored in the container you are trying to build?

So the outer layer needs the hash and the inner layer uses the natural lex order?

Yes, that is what lexical means

I think my hash function has some issue.
It should give me numbers 1-7 and for "g" it gives me 0.

public static int hash(String key, int l)
{
int value = 0;

for(int j = 0; j < key.length(); j++ )
{
value = (value * 53 + key.charAt(j) - 96);
}

value = value % l;

return value;
}