01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package algs33;
import stdlib.*;
import java.util.TreeMap;
import algs32.BST;
import com.javamex.classmexer.MemoryUtil;

/* ***********************************************************************
 *  Compilation:  javac -cp .:classmexer.jar XMemoryOfBSTs.java
 *  Execution:    java  -cp .:classmexer.jar -javaagent:classmexer.jar XMemoryOfBSTs N
 *  Dependencies: StdOut.java classmexer.jar
 *
 *
 *************************************************************************/

public class XMemoryOfBSTs {

  public static void main(String[] args) {

    int N = Integer.parseInt(args[0]);
    //int START = 1000000;

    StdOut.println("size of Integer");
    Integer x = new Integer(123456);
    StdOut.println(MemoryUtil.memoryUsageOf(x));
    StdOut.println();
    long SIZEOFINTEGER = MemoryUtil.memoryUsageOf(x);

    TreeMap<Integer, Integer> st1 = new TreeMap<>();
    StdOut.println("size of TreeMap<Integer, Integer> of given length");
    for (int i = 0; i < 8; i++) {
      Integer key = new Integer(i);
      st1.put(key, key);
      StdOut.println(i + ": " + (MemoryUtil.deepMemoryUsageOf(st1) - SIZEOFINTEGER*i));
    }
    for (int i = 8; i < N; i++) {
      Integer key = new Integer(i);
      st1.put(key, key);
    }
    StdOut.println(N + ": " + (MemoryUtil.deepMemoryUsageOf(st1) - SIZEOFINTEGER*N));
    StdOut.println();

    BST<Integer, Integer> st2 = new BST<>();
    StdOut.println("size of BST<Integer, Integer> of given length");
    for (int i = 0; i < 8; i++) {
      Integer key = new Integer(i);
      st2.put(key, key);
      StdOut.println(i + ": " + (MemoryUtil.deepMemoryUsageOf(st2) - SIZEOFINTEGER*i));
    }
    for (int i = 8; i < N; i++) {
      Integer key = new Integer(i);
      st2.put(key, key);
    }
    StdOut.println(N + ": " + (MemoryUtil.deepMemoryUsageOf(st2) - SIZEOFINTEGER*N));
    StdOut.println();


    RedBlackBST<Integer, Integer> st3 = new RedBlackBST<>();
    StdOut.println("size of RedBlackBST<Integer, Integer> of given length");
    for (int i = 0; i < 8; i++) {
      Integer key = new Integer(i);
      st3.put(key, key);
      StdOut.println(i + ": " + (MemoryUtil.deepMemoryUsageOf(st3) - SIZEOFINTEGER*i));
    }
    for (int i = 8; i < N; i++) {
      Integer key = new Integer(i);
      st3.put(key, key);
    }
    StdOut.println(N + ": " + (MemoryUtil.deepMemoryUsageOf(st3) - SIZEOFINTEGER*N));
    StdOut.println();

  }

}