Hashtable
and
Bitset
ClassesprintTreeToTerm
methodprintTreeToTerm
method.
printTreeToTerm
method prints a tree out on a terminal. It will look like
a graphical representation of a tree rotated 90 degrees counterclockwise.
printTreeToTerm(root, 0);
// print a tree structure with horizontal indents for each level public static void printTreeToTerm( BinaryNode t, int indent ) { int i = 0; if ( t == null ) return; printTreeToTerm(t.right, indent + 4); for(i=0; i<indent; i++) { System.out.print(" "); } System.out.println("" + t.element); printTreeToTerm(t.left, indent + 4); }
BinarySearchTree
called
bst
in your program:
9 / \ / \ / \ 5 11 / \ / \ / \ / \ 4 7 10 12 / \ / \ 2 15
printTreeToTerm(bst.root, 0)
your program would print this to the terminal:
15 12 11 10 9 7 5 4 2
BitSet
ClassBitSet
object.
BitSet
class (in the java.util
package)
makes it easy to manipulate bit sets.
BitSet
is stored as a boolean value that can be set
or cleared. So if you were to print out a bit, it would print out as
true
or false
.
BitSet
s are dynamic, meaning more bits can be added as needed
and a BitSet
object will grow to accomodate the additional bits.
BitSet
class has two contructors, one which takes no arguments,
and one which specifies the size (number of bits) of the BitSet
.
public BitSet(); public BitSet(int nbits); // nbits - number of bits of the BitSet
BitSet
, all the bits are initialized to false
(i.e. 0).
set( bitnumber )
method. The
following code will set the 5th bit to true
(i.e. 1).
BitSet b = new BitSet( 100 ); // b of size 100 bits b.set( 5 ); // set bit number 5 to true (i.e. 1)
clear( bitnumber )
method:
b.clear( 5 ); // clears bit 5 to false (i.e. 0)
get( bitnumber )
method returns true
if
the bit is on and false
if the bit is off.
and( BitSet )
method performs a bitwise (bit-by-bit) logical
AND between two BitSet
s. So if b1
and b2
are
two BitSet
s:
b1.and( b2 );performs a bitwise AND between
b1
and b2
and stores the
result in b1
.
or( BitSet )
and xor( BitSet )
perform a bitwise
logical OR and bitwise logical XOR respectively.
size()
which returns the size of a
BitSet
. However, do note that the current size returned by this method
is the number of bits currently in use by the BitSet
and not necessarily
equal to the creation size.
BitSet
of size 75, the size
method may not return 75, depending on the implementation of the
BitSet
.
toString()
method converts a BitSet
to a
String
and can be very useful for debugging. If you had a
BitSet b
in which the 1st, 2nd, 4th, and 6th bits were turned on and all
other bits were off, then the following code:
String s = b.toString(); System.out.println(s);would have the following output:
{1, 2, 4, 6}
equals( BitSet )
: compares to BitSet
s for equality.clone()
: clones a BitSet
and returns an Object
reference to the new BitSet
.
BitSet
s:
/* CS3139 - Data Structures & Algorithms * * BitTest.java - test BitSet class for Homework3 */ import java.io.*; import java.util.*; public class BitTest { public static void main(String args[]) { /* * BitSet Tests */ System.out.println("\n*** TESTING BitSet class ***\n\n"); int v = 10; int i = 0; BitSet bits = new BitSet(INT_SIZE); System.out.print("Printing value " + v + " in binary from a BitSet: "); // convert v into binary and store in bits while (v > 0) { if ( (v % 2) == 1 ) bits.set(i); v = v/2; i++; } // print BitSet contents for(i=INT_SIZE-1; i>=0; i--) System.out.print(bits.get(i)? 1 : 0); System.out.println("\n\nSetting all bits to zero ..."); for(i=INT_SIZE; i>=0; i--) bits.clear(i); // print BitSet contents for(i=INT_SIZE-1; i>=0; i--) System.out.print(bits.get(i)? 1 : 0); System.out.println("\n\nSetting all bits to one ... "); for(i=INT_SIZE-1; i>=0; i--) bits.set(i); // print BitSet bits contents for(i=INT_SIZE-1; i>=0; i--) System.out.print(bits.get(i)? 1 : 0); System.out.println("\n\nCreating BitSet of size 75 (bits1) ... "); BitSet bits1 = new BitSet(75); // size in bits of the BitSet System.out.println("\nBitSet bits1 of size 75 uses " + bits1.size() + " bits ...\n"); System.out.println("Setting bits1 to alternating values (0,1), LSB = 0 ..."); for(i=0; i<75; i++) { if ( (i % 2) == 1 ) bits1.set(i); } System.out.println("\nChecking bits values ... "); for(i=74; i>=0; i--) System.out.print(bits1.get(i)? 1 : 0); System.out.println("\n\nCreating BitSet of size 75 (bits2) ... "); BitSet bits2 = new BitSet(75); // size in bits of the BitSet System.out.println("\nBitSet bits of size 75 uses " + bits2.size() + " bits ...\n"); System.out.println("Setting bits2 to alternating values (0,1), LSB = 1 ..."); for(i=0; i<75; i++) { if ( (i % 2) == 0 ) bits2.set(i); } System.out.println("\nChecking bits2 values ... "); for(i=74; i>=0; i--) System.out.print(bits2.get(i)? 1 : 0); /* *Bitwise AND */ System.out.println("\n\nBitwise AND of bits1 and bits2 ..."); bits1.and(bits2); for(i=74; i>=0; i--) System.out.print(bits1.get(i)? 1 : 0); System.out.println("\n\nRe-setting bits1 to alternating value, LSB = 0 ..."); for(i=0; i<75; i++) { if ( (i % 2) == 1 ) bits1.set(i); } System.out.println("ok\n"); /* * Bitwise OR */ System.out.println("Bitwise OR of bits1 and bits2 ..."); bits1.or(bits2); for(i=74; i>=0; i--) System.out.print(bits1.get(i)? 1 : 0); System.out.println("\n\ndone ..."); } // size of an integer private static final int INT_SIZE = 32; }
Hashtable
ClassHashtable
class implements a hashtable, which maps keys to
values.
Hashtable
class implements a hashtable using seperate chaining,
so when a collision occurs, a single bucket stores a linked list of multiple entries,
which must be searched sequentially.
HashTable
class it is defined as the ratio of the number of occupied cells in the
hash table to the size of the hash table.
Hashtable
class has three constructors.
Hashtable
with
a default capacity of 101 elements and a default load factor of .75. This can be
done as follows:
table = new Hashtable();
Hashtable
becomes more
than the capacity times the load factor, the table will automatically grow larger.
Hashtable
class also provides a contructor that takes one
argument specifying the capacity and a constructor that takes two arguments
specifying the capacity and the load factor respectively.
public Hashtable(int initialCapacity);
public Hashtable(int initialCapacity, float loadFactor);
put
method:
public synchronized Object put(Object key, Object value);
(synchronized
means that only one thread may execute in the method for
a given object at a time)
Hashtable
.
Hashtable
for the specified key,
null
is returned.
Hashtable
for the specified key, the
original value in the Hashtable
is returned; this helps the program
manage the cases which it intends to replace the value stored for a given key.
null
, a
NullPointerException
is thrown.
Hashtable
of numbers. It uses the
names of the numbers as keys:
Hashtable numbers = new Hashtable(); numbers.put("one", new Integer(1)); numbers.put("two", new Integer(2)); numbers.put("three", new Integer(3));
Hashtable
.
Hashtable
with
the following method:
public synchronized Object get(Object key);
Object
reference to the value if it is
located; otherwise, null
is returned.
Integer n = (Integer)numbers.get("two"); if (n != null) { System.out.println("two = " + n); }
remove
method:
public synchronized Object remove(Object key);
Object
reference to the removed value, and
null
if there is no value mapped to the specified key.
isEmpty
method returns true
if the Hashtable
is empty, and false
otherwise.
public boolean isEmpty();
containsKey
is as follows:
public synchronized boolean containsKey(Object key);
Hashtable
(i.e., a value is associated with that key).
true
, and false
otherwise.
Hashtable
also provides a method contains
to
determine if the Object
specified as its argument is in the
Hashtable
:
public synchronized boolean contains(Object value);
clear
method that empties the
Hashtable
:
public synchronized void clear();
size
method which returns the number of keys
in the Hashtable
:
public int size();
Hashtable
methods.