Problem

Registraation form

2009-05-24T20:05:00.001-07:00

JSP Page

Online Book Shop

My Account Information

Dog

2009-05-14T19:45:00.001-07:00

Create a new class called Dog that is derived from the Pet class given in Listing 6.1 of Chapter 6 on pages 347 - 349. The new class has the additional attributes of breed (type String) and boosterShot (type boolean), which is true if the pet has had its booster shot, and false if not. Be sure your classes have a reasonable complement of constructors and accessor methods.

You will need all three Java programs for execution: Pet.java, Dog.java, DogDemo.java. .

1. Add two instance variables: String breed and boolean boosterShot; (10)

2. Your derived class name is Dog, therefore your file name is Dog.java.

3. You need to define three constructors: (30)

· Without any parameters, codes given below:

public Dog()

{

super();

breed = "None";

boosterShot = false; // Default: presume no shot

· With five parameters name, age, weight, breed, and boosterShot;

· With four parameters name, age, weight, and breed.

4. Give a new definition of writeOutput() (30)

· This is an overridden method.

· The original output from the base class (don’t forget the super keyword).

· Output breed

· Output the dog has (or has not) had a booster shot.

5. Write three mutator methods: (30)

· To reset name, age, weight, breed, and boosterShot status. The instance variables in the base class can be accessed through base class’s set method. Again don’t forget the super keyword here.

· To reset the breed only.

· To reset boosterShot value.

6. Write two accessor methods: (20)

· To get breed info.

· To get info on boosterShot status.

7. You need to document both programs follow my previous suggestions. (10)

· Your code should be written in a way that is easy to read.

· Add comments on what software/IDE you used in developing your program.

· Add compilation instructions. E.g., javac Dog.java. and javac DogDemo.java

· Add executing instructions. E.g., java DogDemo

· Programmer’s name.

· Preconditions and postconditions.

Write a test (demo or driver) program (file name: DogDemo.java) that reads in five pets of type Dog from the keyboard and at the end of the input the program prints out the name and breed of all dogs that are over two years old and have not had their booster shots. Note that your writeOutput() methods in the Pet class and Dog class determine the output format.

· You will use an array to hold all dogs info (check your StudentRecord class).

· Declare the array size to be 5.

· Use a looping method to enter info for 5 dogs.

· Be sure to check your index during your input loop so you don’t get an array index out of bound exception during run time.

· After each loop, echo all info to the screen as shown here:

Enter first dog’s name:

Freddie

Enter dog’s age in years:

Enter dog’s weight in pounds:

10.5

Enter breed:

Dachshund

Has the dog had a booster shot within 2 years?

Enter y (or Y) for yes and anything else for no.

You have entered the following dog info:

Name: Freddie

Age: 5 years

Weight: 10.5 pounds

Bread: Dachshund

Has NOT had a booster shot.

Enter second dog’s name:

………and so forth……

· At the end of the program, print all the dogs’ information to the screen in ascending order by their ages.

· Sample screen output listed below.

Name Age Weight Breed Boostershot

. Freddie 2 10.5 Dachshund false

yy 8 20.0 B2 true

zz 10 15.0 B4 true

aa 12 10.0 B5 true

dd 16 30.0 B2 true

· A sorting method that sorts an array of type Dog for your reference:

public static void insertionSort(int numberDogs, Dog a[] )

{

int in, out;

Dog temp = null;

for(out=1; out // out is dividing line

{

temp = a[out]; // remove marked person

in = out; //index of the end of sorted region

while(in>0 && a[in-1].getAge() > temp.getAge() ) { // until smaller one found

a[in] = a[in-1]; // shift item to the right

--in; // go left one position

}

a[in] = temp; // insert marked item

} // end for

} // end insertionSort()

Note: the numberDogs is the number of element of the Dog array have actually filled with data. The Dog array a[] can be a size of 5 if you initially created 5 elements with the following Java statement:

Dog a[] = new Dog[5];

The length of the a[] array is 5, and all 5 elements at this point are all null. If you try to sort this array, you will get a null pointer exception! You have to use the keyword ‘new’ to instantiate each element of the Dog array. For example the 1^st element of the a[] array:

a[i] = new Dog(…);

/**
Class for basic pet data: name, age, and weight.
*/
public class Pet
{
private String name;
private int age; //in years
private double weight;//in pounds

public Pet(String initialName, int initialAge,
double initialWeight)
{
name = initialName;
if ((initialAge < 0) || (initialWeight < 0))
{
System.out.println("Error: Negative age or weight.");
System.exit(0);
}
else
{
age = initialAge;
weight = initialWeight;
}
}

public void setPet(String newName, int newAge, double newWeight)
{
name = newName;
if ((newAge < 0) || (newWeight < 0))
{
System.out.println("Error: Negative age or weight.");
System.exit(0);
}
else
{
age = newAge;
weight = newWeight;
}
}

public Pet(String initialName)
{
name = initialName;
age = 0;
weight = 0;
}

public void setName(String newName)
{
name = newName; //age and weight are unchanged.
}

public Pet(int initialAge)
{
name = "No name yet.";
weight = 0;
if (initialAge < 0)
{
System.out.println("Error: Negative age.");
System.exit(0);
}
else
age = initialAge;
}

public void setAge(int newAge)
{
if (newAge < 0)
{
System.out.println("Error: Negative age.");
System.exit(0);
}
else
age = newAge;
//name and weight are unchanged.
}

public Pet(double initialWeight)
{
name = "No name yet";
age = 0;
if (initialWeight < 0)
{
System.out.println("Error: Negative weight.");
System.exit(0);
}
else
weight = initialWeight;
}

public void setWeight(double newWeight)
{
if (newWeight < 0)
{
System.out.println("Error: Negative weight.");
System.exit(0);
}
else
weight = newWeight; //name and age are unchanged.
}

public Pet( )
{
name = "No name yet.";
age = 0;
weight = 0;
}

public String getName( )
{
return name;
}

public int getAge( )
{
return age;
}

public double getWeight( )
{
return weight;
}

public void writeOutput( )
{
System.out.println("Name: " + name);
System.out.println("Age: " + age + " years");
System.out.println("Weight: " + weight + " pounds");
}
}

Algorithm-1

2009-05-04T20:05:00.001-07:00

01234 567

Sample Exam 2

EE 322C - University of Texas at Austin - Spring ,2009

Name ____________________________________

Test taking instructions. No calculators, laptops or other assisting devices are allowed. Write your
answers on these sheets. If you need scratch paper then use the backside of the last page. Wherever
code is required, write JAVA statements in the blank areas provided, or by modifying the given code
in place. You are not required to follow the coding style guidelines when writing code on the exam, but
be as neat as possible. If you are unsure of the meaning of a specific test question, then write down
your assumptions and proceed to answer the question on that basis. If you see a typo or syntax error,
fix it, circle it, and if you are right you will get a bonus point for each one fixed. In your programming
solutions on this test you may use any of the classes/methods that you know from the library, or
collections.

Questions about the exam questions will not be answered during the test.

For the binary tree related questions on this exam you may assume that this generic class has been
defined for your use and is included. When the term Btnode is used on the exam it is referring to
this generic class.

class Btnode

{ /* this generic class models a node of a binary tree */

/* here are the private data members of the binary tree node */

private T element;

private Btnode left;

private Btnode right;

/* the constructor given an Object,left child,and right child. */

Btnode(T theElement, Btnode lt, Btnode rt )

{ element = theElement;

left = lt;

right = rt;

}

/* here are the public get/set methods for the data members */

public T getElement( ){ return element;}

public Btnode getLeft( ) {return left;}

public Btnode getRight( ){return right;}

public void setElement( T x ){element = x;}

public void setLeft( Btnode t ) {left = t;}

public void setRight( Btnode t ){right = t;}

}

Page 2

Question 0 -Terminology. [19 pts.] Answer each of the following questions; choose
the best answer from the numbered list below.

A. ___ a sorting technique using a series of queues as intermediate structures
B. _____The level of the lowest leaf of a tree is the same as the tree’s what?
C.
____A binary operation which takes two given sets and yields a set made up of all the items in the first
set that are not in the second set
D. ____A collection of key-value pairs that associate a key with a value.
E. ____A hierarchical structure that place elements in nodes along branches that originate from a root.
F.
____A tree structure in which each node can have at most two children, and in which a unique path
exists from the root to every other node.
G.
____A type of tree in which the key value of each node is less than every key value in its right subtree,
and greater than every key value in its left subtree.
H. ____ A type of binary tree in which the height of each node’s subtrees differs by no more than one.
I.
____A binary tree in which all of the leaves are on the same level and every nonleaf node has exactly
two children
J.
____A binary tree that is either full or full through the next-to-last level, with the leaves on the last level
as far to the left as possible
K.
____A complete binary tree in which each node has a value stored in it that is greater than or equal to
the value in each of its children.
L. ____Nodes in a binary tree that have only NULL children
M. ____A node in a binary tree that does not have a parent
N. ____A data structure that consists of a set of nodes and a set of edges that relate the nodes to each other
O. ____A graph in which each edge is directed from one vertex to another (or the same) vertex
P. ____A graph in which every vertex is directly connected to every other vertex
Q. ____A graph in which each edge carries a value
R.
____A sequential structure that is divided into table elements. The address of an identifier X in the
structure is gotten by computing some arithmetic function
S. ____This occurs when 2 different identifiers are hashed into the same location
T. ____ A method for finding the shortest path from one vertex to another in a weighted digraph
1) 2-3-4 tree 14) device miniaturization27) Prim’s algorithm2) array 15) forking28) queue3) AVL tree 16) functional29) Radix4) binary tree 17) full30) root
5) binary search tree 18) graph31) set
6) black box testing 19) hash table32) set difference
7) breadth first search 20) heap33) set intersection
8) collision 21) infix34) stack
9) complete22) leaf35) synchronization
10) depth23) map 36) ttree
11) depth first search24) matrix 37) weighted graph12) Dijkstra’s algorithm25) overflow 38) White box
13) digraph 26) partially filled array

Page 3
Question 1 -Multiple Choice. [2 pts. each -18 pts total] For each of the following
subparts, circle the best or all correct answers as indicated.

A. The linear probe method for hash tables suffers from the phenomenon known as
i. fatal collisions
ii. sparse distribution
iii. clustering
iv. broken chains
v. none of the above
B. Which of the following sorting algorithms have a worst case performance that is better than O(n*n)?
i) selection
ii) bubble
iii) insertion
iv) shell
v) merge
vi) heapsort
vii)quicksort

C. Which tree below corresponds to the vector v created by the code below?
int arr[ 8 ] = {3, 15, 12, 4, 67, 6, 55, 9};
Vector v = new Vector (8);
for (int i=0; i< 8; i++) { v.addElement(arr[i]); }

341215667955124153667955(i)(ii)
(iii)
(iv)
341512667955367151264955

Page 4

D. Which of the following are true of sets?
i. A set with no elements in it is called an empty set
ii. Each element (ie, value) in a set is distinct
iii. The universal set is that which contains all the values of the base type
iv. The cardinality of a set denotes the number of elements in a set
v. New sets can be created by the union, intersection and difference operations
vi. The elements of a set are not ordered
E. Which of the following are true of heaps ?
i. It is a binary tree
ii. In terms of its shape, it must be complete
iii. It can be either a maximal or a minimal heap
iv. The value of the root has no relationship to the value of any other nodes
v. Is useful for implementing a stack
vi. Is the most efficient representation for a priority queue
F. Hashing is an ______ search algorithm.
(i) O(log2n) (ii) O(n2) (iii) O(n) (iv) O(1)
G. What is the value of the postfix expression 6 3 4 5 + * +
i) 10
ii) 0
iii) 25
iv) 33
v) none of the above

H. Given three arrays with L, M and N elements respectively,
estimate the running time for the
following algorithm in terms of the number of times that the pairwise comparison step is executed:
repeat the following for i from 1 to L for array1
repeat the following for j from 1 to M for array2
repeat the following for k from 1 to N for array3

pairwise compare array1[i], array2 [j] and array3 [k] and based on the result do one the following
case 1: if array1[i] and array2 [j] are equal then { do something 1}
case 2: if array1[i] and array3 [k] are equal then { do something 2}
case 3: if array3[k] and array2 [j] are equal then { do something 3}

end repeat
end repeat
end repeat

i. O ( log 2 (L+M+N) )
ii. O ( N 3 )
iii. O ( L * M * N )
iv. None of the above

Page 5

I. If the characters ‘A’, ‘D’, ‘C’, ‘B’ are put into a queue (in that order), and then retrieved one by one,
what will be the order in which they are removed?
i) ABCD
ii) DCBA
iii) BCDA
iv) ADCB

Question 2. Evaluation. (2 points each = 6 pts. total) For each of the following code segments,
write in the value of the variable x after the Java statements are executed. You may assume that the
proper import statements have already appeared.

A.
______________ Vector alist = new Vector ( );
alist.add (40);
alist.add (10);
alist.add (20);
alist.add (8);
int x = alist.get(0 ) * alist.get( 3) ;
B.
______________ Stack intStack = new Stack ( );
intStack.push (6);
intStack.push (5);
intStack.push (11 + intStack.peek ( ));
int y = intStack.peek ( ) ;
intStack.pop ( ) ;
int x = y + intStack.peek ( ) ;
C.
______________ int array [ ] = {0,1,2,3,4,5,6,7,8,9};
Queue s = new LinkedList ( );
for (int i = 0; i < 10; i++) s.add (array [ i ]);
s.remove ( );
int x = s.peek ( ) + array [7];
// hint: from the ADT for queue: add is enqueue, remove is dequeue, peek is front

Page 6

3. Tree questions (20 pts)
A.(7 pts) For each subpart (a) – (g), use the following tree.

691215721231453201118
(a) What is the parent of node 5? ___________________
(b) What is the depth of this tree? ____________________
(c) List the nodes in subtree 12. ___________________________
(d) List all of the non leaf nodes. ______________________________
(e) Give the order that the nodes are visited in a preorder traversal of the tree.
(f) Give the order that the nodes are visited in an inorder traversal of the tree.
(g) List all of the nodes at level 2 in the tree. _______________________________
B. (2 pts) Draw the tree created by the following statements. Btnode is defined on page 1.
Btnode root, a, b, c, d;
d = new Btnode (6, NULL, NULL);
c = new Btnode (9, d, NULL);
b = new Btnode (4, NULL, c);
a = new Btnode (12, NULL, NULL);
root = new Btnode (10, a, b);

C. (3 pts) Trace the method count() below and describe what it does
public static int count (Btnode t)

{ int ctLeft, ctRight, ct;

if (t == NULL)

ct = 0;

else

{ ctLeft = count(t.getLeft());

ctRight= count(t.getRight());

boolean flag = (t.getLeft()!= NULL && t.getRight()!= NULL);

ct = ctLeft + ctRight + (int)flag;

}

return ct;

}

Page 7

D. (3 pts) Use the following tree traversal function.
Assuming m is initially 0, what is the resultant value of m when
calling this method as f ( Btnode root, m) where root is the base of the tree in Question 3A?
public static void f(Btnode t, int n)
{ if (t != NULL)

{
n++;
f(t.getLeft(), n);
f(t.getRight(), n);

}
return;

}

E. (5 pts) Consider the following binary search tree.
Use the original tree below when answering each subpart (a)
through (e).
506875654515907035208025301852395100150
(a)
If the value 46 is inserted into this tree, which node becomes its parent? __________________
(b) If the value 64 is inserted into this tree, which node becomes its parent? ___________________
(c)
If we delete node 65, which node should be its replacement node? ___________________
(d) If we delete node 90, which node should be its replacement node? __________________
(e)
If we delete the root node 50, which node should be selected as its replacement node so that the fewest number
of changes are made to the tree? ______________________

Page 8

4. Heaps and Graphs (19 pts)
A. (3 pts) A heap can be represented by a vector. Start with the following heap and list the elements after each operation.
Execute the operations sequentially, using the result of the previous operation. The initial vector values for the heap
are {50, 35, 15, 12, 3, 5}.
5012153553
(a) Insert 23: The vector values are now {____________________________}.
(b) Erase an element from the heap:The vector values are now {__________________}.
B. (3 pts) Start with following tree and "heapify" it to create a maximum heap. Draw the resulting tree.
259813292218553533
C. (3 pts) Start with following tree and create a minimum heap. Draw the resulting tree.
75205540304590151035
D. (3 pts) Show the minimum cost path from node B to node E in the following digraph G.

Page 9

ADCBE12532117

Page 10

E..(3 pts) Draw the adjacency list representation for the following digraph G.

ADCBE12532117
F (4 pts) Draw the minimal spanning tree for the following graph G.

B
A
H
E
G
F
D
C
50 25
46
25
23
55
32
98
35
67

Page 11

5. Hash Tables (6 pts) The following hash table is used to store integer values. Assume that we
use the following hashing function to store values in the table.
h(x) = x % tableSize (tableSize is equal to the size of the hash table below -which is 20)

Show the resultant hash table after inserting the values: 52, 12, 11, 2, 7, 10, 21, 121, 23, 33, 71, 90 in
that order. Use the linear probing technique for collision resolution. That is, if the initial hash location
yields a collision then probe forward until an empty slot can be found. The table is used in a circular
manner for that purpose.

Index Value
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Page 12

6. Maps (6 points)
Complete the program below whose purpose is to count and record the number of occurrences of each
character found in a given text file (“in.txt”). You are to use the hash map m to store the number of
occurrences of each character. You can use the default hashcode method for Character. After all
characters in the file are processed, output a table to the screen that contains 2 columns with each
character in column 1 and its total number of occurrences in column 2. Note: all legal characters are to
be counted.

import java.io.*;
public class CountingChars
{ public static void main(String[ ] args) throws IOException

{
Map m = new HashMap ( );
FileReader infile = new FileReader("in.txt");
BufferedReader in = new BufferedReader(infile);

// process all the characters in the file, one at a time
char c = (char) in.read( ); // read the first char from the file
while ( )
{

c = (char) in.read(); // read the next char in the file
}
// output the table of (char, count) pairs

}

Page 13

}

7. Design [6 points] Consider the dictionary of 5-lettered words that you used in Assignment 5, and
suppose that you were given the list of words but they were not in order. To put them into alphabetical
order, describe the sorting method that you would use to put them into order in the fastest way possible.
You may assume that there is plenty of space available for your chosen method. Describe your
method’s worst case Big O performance and approximately how much space is required.

Algorithm

2009-05-04T18:10:00.000-07:00

Questions about the exam questions will not be answered during the test.
For the binary tree related questions on this exam you may assume that this generic class has been
defined for your use and is included. When the term Btnode is used on the exam it is referring to
this generic class.
class Btnode
{ /* this generic class models a node of a binary tree */
/* here are the private data members of the binary tree node */
private T element;
private Btnode left;
private Btnode right;
/* the constructor given an Object,left child,and right child. */
Btnode(T theElement, Btnode lt, Btnode rt )
{ element = theElement;
left = lt;
right = rt;
}
/* here are the public get/set methods for the data members */
public T getElement( ){ return element;}
public Btnode getLeft( ) {return left;}
public Btnode getRight( ){return right;}
public void setElement( T x ){element = x;}
public void setLeft( Btnode t ) {left = t;}
public void setRight( Btnode t ){right = t;}
}

Question 1 - Multiple Choice. [2 pts. each - 18 pts total] For each of the following
subparts, circle the best or all correct answers as indicated.
A. The linear probe method for hash tables suffers from the phenomenon known as
i. fatal collisions
ii. sparse distribution
iii. clustering
iv. broken chains
v. none of the above
B. Which of the following sorting algorithms have a worst case performance that is better than O(n*n)?
i) selection
ii) bubble
iii) insertion
iv) shell
v) merge
vi) heapsort
vii) quicksort
C. Which tree below corresponds to the vector v created by the code below?
int arr[ 8 ] = {3, 15, 12, 4, 67, 6, 55, 9};
Vector v = new Vector (8);
for (int i=0; i< 8; i++) { v.addElement(arr[i]); }

D. Which of the following are true of sets?
i. A set with no elements in it is called an empty set
ii. Each element (ie, value) in a set is distinct
iii. The universal set is that which contains all the values of the base type
iv. The cardinality of a set denotes the number of elements in a set
v. New sets can be created by the union, intersection and difference operations
vi. The elements of a set are not ordered
E. Which of the following are true of heaps ?
i. It is a binary tree
ii. In terms of its shape, it must be complete
iii. It can be either a maximal or a minimal heap
iv. The value of the root has no relationship to the value of any other nodes
v. Is useful for implementing a stack
vi. Is the most efficient representation for a priority queue
F. Hashing is an ______ search algorithm.
(i) O(log2n) (ii) O(n2) (iii) O(n) (iv) O(1)
G. What is the value of the postfix expression 6 3 4 5 + * +
i) 10
ii) 0
iii) 25
iv) 33
v) none of the above
H. Given three arrays with L, M and N elements respectively, estimate the running time for the
following algorithm in terms of the number of times that the pairwise comparison step is executed:
repeat the following for i from 1 to L for array1
repeat the following for j from 1 to M for array2
repeat the following for k from 1 to N for array3
pairwise compare array1[i], array2 [j] and array3 [k] and based on the result do one the following
case 1: if array1[i] and array2 [j] are equal then { do something 1}
case 2: if array1[i] and array3 [k] are equal then { do something 2}
case 3: if array3[k] and array2 [j] are equal then { do something 3}
end repeat
end repeat
end repeat
i. O ( log 2 (L+M+N) )
ii. O ( N 3 )
iii. O ( L * M * N )
iv. None of the above

I. If the characters ‘A’, ‘D’, ‘C’, ‘B’ are put into a queue (in that order), and then retrieved one by one,
what will be the order in which they are removed?
i) ABCD
ii) DCBA
iii) BCDA
iv) ADCB
Question 2. Evaluation. (2 points each = 6 pts. total) For each of the following code segments,
write in the value of the variable x after the Java statements are executed. You may assume that the
proper import statements have already appeared.
A. ______________ Vector alist = new Vector ( );
alist.add (40);
alist.add (10);
alist.add (20);
alist.add (8);
int x = alist.get(0 ) * alist.get( 3) ;
B. ______________ Stack intStack = new Stack ( );
intStack.push (6);
intStack.push (5);
intStack.push (11 + intStack.peek ( ));
int y = intStack.peek ( ) ;
intStack.pop ( ) ;
int x = y + intStack.peek ( ) ;
C. ______________ int array [ ] = {0,1,2,3,4,5,6,7,8,9};
Queue s = new LinkedList ( );
for (int i = 0; i < 10; i++) s.add (array [ i ]);
s.remove ( );
int x = s.peek ( ) + array [7];
// hint: from the ADT for queue: add is enqueue, remove is dequeue, peek is front

3. Tree questions (20 pts)
A.(7 pts) For each subpart (a) – (g), use the following tree.

(a) What is the parent of node 5? ___________________
(b) What is the depth of this tree? ____________________
(c) List the nodes in subtree 12. ___________________________
(d) List all of the non leaf nodes. ______________________________
(e) Give the order that the nodes are visited in a preorder traversal of the tree.
____________________________________________________________
(f) Give the order that the nodes are visited in an inorder traversal of the tree.
____________________________________________________________
(g) List all of the nodes at level 2 in the tree. _______________________________
B. (2 pts) Draw the tree created by the following statements. Btnode is defined on page 1.
Btnode root, a, b, c, d;
d = new Btnode (6, NULL, NULL);
c = new Btnode (9, d, NULL);
b = new Btnode (4, NULL, c);
a = new Btnode (12, NULL, NULL);
root = new Btnode (10, a, b);
C. (3 pts) Trace the method count() below and describe what it does
public static int count (Btnode t)
{ int ctLeft, ctRight, ct;
if (t == NULL)
ct = 0;
else
{ ctLeft = count(t.getLeft());
ctRight= count(t.getRight());
boolean flag = (t.getLeft()!= NULL && t.getRight()!= NULL);
ct = ctLeft + ctRight + (int)flag;
}
return ct;
}

D. (3 pts) Use the following tree traversal function. Assuming m is initially 0, what is the resultant value of m when
calling this method as f ( Btnode root, m) where root is the base of the tree in Question 3A?
_____________________________
public static void f(Btnode t, int n)
{ if (t != NULL)
{ n++;
f(t.getLeft(), n);
f(t.getRight(), n);
}
return;
}
E. (5 pts) Consider the following binary search tree. Use the original tree below when answering each subpart (a)
through (e).

(a) If the value 46 is inserted into this tree, which node becomes its parent? __________________
(b) If the value 64 is inserted into this tree, which node becomes its parent? ___________________
(c) If we delete node 65, which node should be its replacement node? ___________________
(d) If we delete node 90, which node should be its replacement node? __________________
(e) If we delete the root node 50, which node should be selected as its replacement node so that the fewest number
of changes are made to the tree? ______________________

4. Heaps and Graphs (19 pts)
A. (3 pts) A heap can be represented by a vector. Start with the following heap and list the elements after each operation.
Execute the operations sequentially, using the result of the previous operation. The initial vector values for the heap
are {50, 35, 15, 12, 3, 5}.

GUI

2009-04-27T19:59:00.000-07:00

School
? Catchment area of school defines the area of houses influenced by the presence of the school.
? Catchment area for schools is 3km.
? The degree to which a school is considered good or bad is its influence level.
? Influence level is randomly assigned to each school in neighbourhood.
? Influence level: -10 being the worst (negatively influenced), 10 being the best (positively influenced).
? Houses within the 3km proximity radius will show an increase in price of 15%
? However “bad” schools will have no negative effect on house price.

Industrial Estates
? Catchment area of industrial estates defines the area of houses influence by its presence.
? Catchment area for industrial estates is 0.5km
? Industrial estate agents will group together to from an “industrial estate.”
? Industrial estates will have an influence level of -6.

Topography
? Topography defined as scenic areas, countryside, lakes, parks.
? Catchment area of topography defines the area of houses influence by its presence.
? Catchment area for topography 0.5km.
? Influence level for topography range from +5 to +10

Pubs
? Catchment area for pubs ranges from 0.5km to 4km
? Houses within 0.5km of the pub will negatively influence house prices by 8%
? Houses within 0.5km of pubs will carry the negative influence level of
? Houses outside 0.5km of the pub will positively influence house prices by 3%
? Houses outside 0.5km of pubs will carry the positive influence level of
? Influence level for topography range from +5 to +10

Town Centre
? Catchment area for town centre is 1.5km
? Houses prices within this catchment area will be positively influenced by 20%

Interest rates
? When interest rates increase, demand for housing decreases, therefore decrease in price.
? Interest rate ranges from 0 to 15.
? Demand for housing will be measured as a percentage change of the interest rate.
? E.g. if interest rate increases from 4.0 to 4.6 (change being +0.6) then demand decreases by 15% as does house price.

Policing Level
? If level of policing is 0-30% reduce all agents influence level by 5.
? If level of policing is 30-60% reduce all agents influence level by 3.
? If level of policing is 60-100% reduce all agents influence level by 1.

Inputs
Before the simulation is run the user will be able to set up the neighbourhood.

Interest rates
? Interest rates will range from 0 to 15.
? User will have the option to set default value for simulation (5)

Population
? Users will also be able to set the population density for the neighbourhood.
? Population density will range from 0 to 100%
? And will directly effect demand e.g. when population is at 100%, demand is at its highest (therefore price will be equally as high).
? User will have the option to set default value for simulation (75%)
?
Level of policing

General Inputs
? Users will be able to set default values for everything to allow the system run a controlled simulation.
? Users can set the catchment area and influence level for each amenity
? All houses start off with a default price of £100,000

Outputs
The outputs will be shown on a GUI that will help analyse the simulation as a whole.
Each agent will have its own colour, for example houses will be in blue, topography in green and so on.
To represent the difference in house price within the actual simulation, differeing house prices will be represented by different shades of blue. For example houses prices between 0 and 50,000 will show as a light blue, 50,000 to 100,000 a darker shade, 100,000 to 150,000 an even darker shade, until it reaches its maximum category 300,000+.

? Display all input values including interest rate, population
? The number of houses in the simulation
? The number of houses in each price category
? The average house price will be calculated
? The highest and lowest house price will be displayed
? Display the number of each amenity-school pubs topography etc

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Component;
import java.awt.Container;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.GridLayout;
import java.awt.Image;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Rectangle2D.Double;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;
import java.awt.Graphics;
import java.awt.Color;
public class HouseMarketGUI extends JFrame implements ActionListener{

int population ;
int interestRate ;
int policingLevel ;

static HouseMarketGUI gui;
//Page1 GUI Variables
private JLabel p1labelt;
private JLabel p1labeltSub;
private JFrame p1frame;
private JLabel p1popLable;
private JLabel p1intLable;
private JLabel p1poliLable;
private JTextField p1popValue;
private JTextField p1intValue;
private JTextField p1poliValue;

private JButton p1button;
//end

public HouseMarketGUI(){

// size = new Dimension(0, 0);
// stats = new FieldStats();
// JPanel cp = new JPanel(new GridLayout(1, 1));
// JPanel cp1 = new JPanel();
//Page1 Create Object
p1frame= new JFrame(" Housing Market Simulation ");
p1frame.getContentPane().setLayout(null);

p1labelt = new JLabel("Housing Market Simulation");
p1labelt.setFont(new Font("Serif", Font.BOLD, 20));
p1labelt.setBounds(150,0,350,70);

p1labeltSub = new JLabel("Setup Environment");
p1labeltSub.setFont(new Font("Serif", Font.BOLD, 18));
p1labeltSub.setBounds(50,40,350,70);

p1popLable = new JLabel("Population(0-100)%");
p1popValue = new JTextField(35);
p1popValue.setText("75");
p1intLable = new JLabel("Interest Rate(0-15)");
p1intValue = new JTextField(35);
p1intValue.setText("5");

p1poliLable = new JLabel("Policing Level(0-100)%");
p1poliValue = new JTextField(35);
p1poliValue.setText("50");

p1button = new JButton("NEXT");
//end

//Page1 Position
p1popLable.setBounds(50,100,150,70);
p1intLable.setBounds(50,150,150,70);

p1popValue.setBounds(220,120,50,30);
p1intValue.setBounds(220,170,50,30);

p1poliLable.setBounds(50,200,150,70);
p1poliValue.setBounds(220,220,50,30);

p1button.setBounds(370,330,80,27);
//end

//page1 add contentPanel
p1frame.getContentPane().add(p1labelt);
p1frame.getContentPane().add(p1labeltSub);

p1frame.getContentPane().add(p1popLable);
p1frame.getContentPane().add(p1popValue);
p1frame.getContentPane().add(p1intLable);
p1frame.getContentPane().add(p1intValue);

p1frame.getContentPane().add(p1poliLable);
p1frame.getContentPane().add(p1poliValue);

p1frame.getContentPane().add(p1button);
//end

//page1 actionListener
p1button.addActionListener(this);
p1frame.setSize(550,550);
p1frame.setVisible(true);
//end

}

public void actionPerformed(ActionEvent event){

if(event.getSource() == p1button){
p1frame.setVisible(false);
p2frame.setVisible(true);
p3frame.setVisible(false);

p2namevalue.setText("0.5");
p2numberValue.setText("0.5");
p2salaryValue.setText("1.5");
p2pubValue.setText("0.5");
p2schoolValue.setText("3.0");

p2namevalue.setEditable(false);
p2numberValue.setEditable(false);
p2salaryValue.setEditable(false);
p2pubValue.setEditable(false);
p2schoolValue.setEditable(false);

population = Integer.parseInt(p1popValue.getText());
interestRate = Integer.parseInt(p1intValue.getText());
policingLevel = Integer.parseInt(p1poliValue.getText());

}

}

public static void main(String arg[]){

gui = new HouseMarketGUI();

}

}

Sports

2009-04-19T20:22:00.001-07:00

http://www.eng.auburn.edu/~cross/comp1210/lab/projects/Project8.pdf

http://www.eng.auburn.edu/~cross/comp1210/lab/projects/Project9.pdf

import java.io.*;
import java.io.FileNotFoundException;
import java.util.*;
abstract class Competitor {
String name, birthplace, gender;
int age, bestfinish;

public Competitor(){
name = "";
birthplace = "";
gender = "";
age = 0;
bestfinish = 0;
}

public Competitor( String name, String birthplace, String gender, int age, int bestfinish ){

this.name = name;
this.birthplace = birthplace;
this.gender = gender;
this.age = age;
this.bestfinish = bestfinish;
}

public void ReadInputFromFile(Scanner scan){
name = scan.nextLine();
birthplace = scan.nextLine();
gender = scan.nextLine();
age = Integer.parseInt(scan.nextLine());
bestfinish = Integer.parseInt(scan.nextLine());
}

public String toString()
{
String result = "Name: " + name + "\n";
result += "Born in: " + birthplace + "\n";
result += "Gender: " + gender + "\n";
result += "Age: " + age + "\n";
result += "Best Competition Finish: " + bestfinish + "\n";

return result;
}
public static void main(String[] args) throws FileNotFoundException {
String inputFileName = args[0];
}
}

//** try {
//File inFile = new File(fileName);
//BufferedReader br = new BufferedReader(new InputStreamReader(
//new FileInputStream(inFile)));

//DataLine = br.readLine();
//br.close();
//}
//catch (FileNotFoundException ex) {
//return (null);
//}
//catch (IOException ex) {
//return (null);
//}
//return (DataLine);
//

5
1
John Smith
New York, NY
Male
16
4
3
638
12
yes
no
2
Pat Jones
Los Angeles, CA
Female
14
33
19
Washington High School
3
Gina Toms
Dallas, TX
Female
22
1
20 - 25
112
Discus
156.7
4
Logan James
Fort Worth, TX
Male
17
3
15 - 18
334
1500
00:04:22
5
6

import java.io.*;
import java.util.Scanner;

public final class Project8_Driver {
static int numCompetitors = 0;
String temp;

public static void main(String[] args) throws IOException,FileNotFoundException
{

String temp;
String inputFileName = args[0];

Competitor[] comp = new Competitor[20];

int choice = -1;

BufferedReader br = new BufferedReader(
new InputStreamReader(
new FileInputStream(inputFileName)));

temp = br.readLine();
choice = Integer.parseInt( temp );
menuSwitch( choice, comp );
menu();

while ((temp = br.readLine()) != null) {
choice = Integer.parseInt( temp );
menuSwitch( choice, comp );

}
}

public static void menuSwitch( int choice, Competitor[] comp ) throws FileNotFoundException
{
File file = new File("P8input.txt");
Scanner scan = new Scanner(file);
scan.nextLine();
scan.nextLine();
switch( choice )
{

case 1:
//add Stacker
comp[numCompetitors] = new Stacker();
Stacker stk = new Stacker();
stk.ReadInputFromFile(scan);
stk.toString();
System.out.print(stk.toString());
numCompetitors++;
break;

case 2:
//add Speller
comp[numCompetitors] = new Speller();
Speller spl = new Speller();
spl.toString();
System.out.print(spl.toString());
numCompetitors++;
break;

case 3:
//add Thrower
comp[numCompetitors] = new Thrower();
Thrower thr = new Thrower();
thr.toString();
System.out.print(thr.toString());
numCompetitors++;
break;

case 4:
//add Runner
comp[numCompetitors] = new Runner();
Runner run = new Runner();
run.toString();
System.out.print(run.toString());
numCompetitors++;
break;

case 5:
//print out Competitors Info
System.out.println("(Option 5) - Print Competitor Information");
System.out.println("Competitors");
System.out.println("*************");
for(int i = 0; i < numCompetitors; i++)
System.out.println("\n" + comp[ i ]);

break;

case 6:
System.out.println("Goodbye.");
break;
}
}

public static void menu()
{
System.out.println("*************");
System.out.println("(Option 1) - Create new Sport Stacker\n");
System.out.println("(Option 2) - Create new Speller\n");
System.out.println("(Option 3) - Create new Thrower\n");
System.out.println("(Option 4) - Create new Runner\n");
System.out.println("(Option 5) - Print Competitor Information");
System.out.println("Competitors");
System.out.println("*************");

}

}

import java.text.DateFormat;
import java.util.Date;
import java.sql.Time;
import java.util.Scanner;
class Runner extends TrackAthlete {
int primaryeventdistance;
Time besteventtime;

public Runner(){
primaryeventdistance = 0;
}

public Runner( String name, String birthplace, String gender, int age, int bestfinish, int bibnum, String agegroup, int primaryeventdistance, Time besteventtime )
{
super(name,birthplace,gender,age,bestfinish,bibnum,agegroup);
this.primaryeventdistance = primaryeventdistance;
this.besteventtime = besteventtime;
}
public String toString(){
String result = "Type: Runner\n";
result += super.toString();
result += "Primary Event Distance: " + primaryeventdistance + "\n";
result += "Best Time: " + besteventtime + "\n";
return result;
}
public void ReadFromInputFile(){
//ValueOf(besteventtime);
}
}

import java.util.Scanner;
class Speller extends Competitor {
int spellerregnum;
String school;

public Speller()
{
spellerregnum = 0;
school = "";
}

public Speller( String name, String birthplace, String gender, int age, int bestfinish, int stackerregnum, String school )
{
super(name,birthplace,gender,age,bestfinish);
this.spellerregnum = spellerregnum;
this.school = school;
}

public void ReadInputFromFile() {

}

public String toString(){
String result = "Type: Speller\n";
result += super.toString();
result += "Region: " + spellerregnum + "\n";
result += "School: " + school + "\n";
return result;
}
}

import java.util.Scanner;
class Stacker extends Competitor {
int stackerregnum, stackerID, stackernumtimes;
boolean event333,event363;
String event333line,event363line;

public Stacker()
{
stackerregnum = 0;
stackerID = 0;
stackernumtimes = 0;
event333 = false;
event363 = false;
}

public Stacker( String name, String birthplace, String gender, int age, int bestfinish, int stackerregnum, boolean event333, boolean event363, int stackerID, int stackernumtimes )
{
super(name,birthplace,gender,age,bestfinish);
this.stackerregnum = stackerregnum;
this.event333 = event333;
this.event363 = event363;
this.stackerID = stackerID;
this.stackernumtimes = stackernumtimes;
}

public String toString(){
String result = "Type: Sport Stacker\n";
result += super.toString();
result += "ID: " + stackerID + "\n";
result += "Times: " + stackernumtimes + "\n";
result += "Region: " + stackerregnum + "\n";
result += "Event 3-3-3: " + event333 + "\n";
result += "Event 3-6-3: " + event363 + "\n";
return result;
}
public void ReadInputFromFile(Scanner scan) {
super.ReadInputFromFile(scan);
stackernumtimes = Integer.parseInt(scan.nextLine());
stackerID = Integer.parseInt(scan.nextLine());
stackerregnum = Integer.parseInt(scan.nextLine());
event333line = scan.nextLine();
if (event333line == "yes") {
event333 = true;}

}

}

import java.util.Scanner;
class Thrower extends TrackAthlete {
String primaryevent;
int bestdistance;

public Thrower()
{
primaryevent = "";
bestdistance = 0;
}

public void ReadInputFromFile() {

}

public Thrower( String name, String birthplace, String gender, int age, int bestfinish, int bibnum, String agegroup, int bestdistance, String primaryevent )
{
super(name,birthplace,gender,age,bestfinish,bibnum,agegroup);
this.primaryevent = primaryevent;
this.bestdistance = bestdistance;
}
public String toString(){
String result = "Type: Thrower\n";
result += super.toString();
result += "Primary Throwing Event: " + primaryevent + "\n";
result += "Best Distance: " + bestdistance + "\n";
return result;
}

}

import java.util.Scanner;
class TrackAthlete extends Competitor {
int bibnum;
String agegroup;

public TrackAthlete()
{
bibnum = 0;
agegroup = "";
}

public TrackAthlete( String name, String birthplace, String gender, int age, int bestfinish, int bibnum, String agegroup )
{
super(name,birthplace,gender,age,bestfinish);
this.bibnum = bibnum;
this.agegroup = agegroup;
}

public void ReadInputFromFile() {

}

public String toString(){
String result = super.toString();
result += "Age Group: " + agegroup + "\n";
result += "Bib Number: " + bibnum + "\n";
return result;
}
}

Query

2009-04-12T19:02:00.000-07:00

CREATE TABLE SCRIPT

CREATE TABLE tbl_customers
(
custssn VARCHAR2(11) CONSTRAINT customers_custssn_nn NOT NULL,
lname VARCHAR2(14) CONSTRAINT customers_lname_nn NOT NULL,
fname VARCHAR2(14) CONSTRAINT customers_fname_nn NOT NULL,
street VARCHAR2 (30) CONSTRAINT customers_street_nn NOT NULL,
city VARCHAR2(14) CONSTRAINT customers_city_nn NOT NULL,
state VARCHAR2(2) CONSTRAINT customers_state_nn NOT NULL,
zip VARCHAR2(5) CONSTRAINT customers_zip_nn NOT NULL,
phone CHAR(12) CONSTRAINT customers_phone_nn NOT NULL,
CONSTRAINT customers_custssn_pk PRIMARY KEY (custssn)
);

CREATE TABLE SailBoats
(
BoatName VARCHAR2(25),
BoatLength NUMBER (10,2),
CONSTRAINT SailBoats_Boatname_pk PRIMARY KEY (BoatName)
);

CREATE TABLE Charters
(
BoatName VARCHAR2(25) ,
PlannedDepart DATE,
CustSSN VARCHAR2(12) ,
ActualDepart DATE,
PlannedReturn DATE,
AcutalReturn DATE,
RentalFee NUMBER(7,2),
LateFee NUMBER(10,2) ,
CONSTRAINT Charters_BoatName_pk PRIMARY KEY (BoatName, PlannedDepart),
CONSTRAINT Charters_BoatName_fk FOREIGN KEY (BoatName) REFERENCES Sailboats(BoatName) ,
CONSTRAINT Charters_CustSSN_fk FOREIGN KEY (CustSSN) REFERENCES Customers(CustSSN),
CONSTRAINT Charters_Date_cc CHECK ((PlannedReturn >= PlannedDepart) AND (ActualDepart >= PlannedDepart) AND (AcutalReturn >= PlannedReturn)),
CONSTRAINT Charters_MinFee_cc CHECK (RentalFee >= 500)
);

CREATE TABLE Crew
(
CrewSSN VARCHAR2(11),
LName VARCHAR2(14),
FName VARCHAR2 (14),
Street VARCHAR2 (30),
City VARCHAR2(14),
State VARCHAR2(2),
Zip VARCHAR2(5),
CONSTRAINT Charters_CrewSSN_pk PRIMARY KEY (CrewSSN)
);

CREATE TABLE Role
(Role_Desc VARCHAR2(20) ,
MinCommision NUMBER (10,2),
MaxCommision NUMBER (10,2),
CONSTRAINT Role_Role_pk PRIMARY KEY (Role_Desc)
);

CREATE TABLE CrewAssignment
(
BoatName VARCHAR2(25) ,
PlannedDepart DATE,
CrewSSN VARCHAR2(11) ,
Role_Desc VARCHAR2(20),
Commission NUMBER(10,2),
CONSTRAINT CrewAssignment_BoatName_pk PRIMARY KEY (BoatName, PlannedDepart, CrewSSN),
CONSTRAINT CrewAssignment_BoatName_fk FOREIGN KEY (BoatName, PlannedDepart) REFERENCES Charters(BoatName, PlannedDepart) ,
CONSTRAINT Charters_CrewSSN_fk FOREIGN KEY (CrewSSN) REFERENCES Crew(CrewSSN),
CONSTRAINT Charters_Role_fk FOREIGN KEY (Role_Desc) REFERENCES
Role(Role_Desc)
);

INSERT DATA SCRIPT

INSERT INTO TBL_CUSTOMERS ( CUSTSSN, LNAME, FNAME, STREET, CITY, STATE, ZIP,
PHONE ) VALUES (
'778-989-654', 'VEN', 'SARA', 'LAKE VIEW STREET', 'CALICORNIA', 'CA', '1111', '92581898988 ');
INSERT INTO TBL_CUSTOMERS ( CUSTSSN, LNAME, FNAME, STREET, CITY, STATE, ZIP,
PHONE ) VALUES (
'987-987-089', 'TIMOTHY', 'BARAK', 'W.H WASHINGTON', 'WASHINGTON', 'DC', '9098', '090977686 ');
commit;

INSERT INTO TBL_SAILBOATS ( BOATNAME, BOATLENGTH ) VALUES (
'FANTASTIC', 5.77);
INSERT INTO TBL_SAILBOATS ( BOATNAME, BOATLENGTH ) VALUES (
'SUPER SPEED', 6);
INSERT INTO TBL_SAILBOATS ( BOATNAME, BOATLENGTH ) VALUES (
'FLY TALKER', 7.9);
commit;

INSERT INTO TBL_CHARTERS ( BOATNAME, PLANNEDDEPART, CUSTSSN, ACTUALDEPART, PLANNEDRETURN,
ACUTALRETURN, RENTALFEE, LATEFEE ) VALUES (
'FANTASTIC', TO_Date( '03/01/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), '778-989-654'
, TO_Date( '03/01/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), TO_Date( '03/01/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM')
, TO_Date( '03/01/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), 500, NULL);
INSERT INTO CHARTERS ( BOATNAME, PLANNEDDEPART, CUSTSSN, ACTUALDEPART, PLANNEDRETURN,
ACUTALRETURN, RENTALFEE, LATEFEE ) VALUES (
'Super Speed', TO_Date( '03/09/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), '123-456-7890'
, TO_Date( '03/09/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), TO_Date( '03/10/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM')
, TO_Date( '03/10/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), 1000, NULL);
commit;

INSERT INTO CREW ( CREWSSN, LNAME, FNAME, STREET, CITY, STATE,
ZIP ) VALUES (
'111-565-9983', 'Halsteeder', 'Dylan', '45 East Franklin', 'San Diego', 'CA', '11111');
INSERT INTO CREW ( CREWSSN, LNAME, FNAME, STREET, CITY, STATE,
ZIP ) VALUES (
'990-000-8893', 'Headley', 'Michael', 'XYZ STREET', 'WASHINGTON', 'DC', '67665');
commit;

INSERT INTO ROLE ( ROLE_DESC, MINCOMMISION, MAXCOMMISION ) VALUES (
'CAPTAIN', 350, 500);
INSERT INTO ROLE ( ROLE_DESC, MINCOMMISION, MAXCOMMISION ) VALUES (
'FIRST MATE', 200, 350);
INSERT INTO ROLE ( ROLE_DESC, MINCOMMISION, MAXCOMMISION ) VALUES (
'SEAMAN', 100, 200);
commit;

INSERT INTO CrewAssignment ( BoatName, PlannedDepart, CrewSSN, Role_Desc,
Commission ) VALUES (
'Captains Choice', TO_Date( '03/01/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), '990-000-8893'
, 'Captain', 415);
INSERT INTO TBL_CREWASSIGNMENT ( BOATNAME, PLANNEDDEPART, CREWSSN, ROLE_DESC,
COMMISSION ) VALUES (
'SUPER SPEED', TO_Date( '03/01/2009 12:00:00 AM', 'MM/DD/YYYY HH:MI:SS AM'), '111-565-998'
, 'FIRST MATE', 150);
commit;

SELECT DATA SCRIPT

SELECT * FROM TBL_CUSTOMERS;
SELECT * FROM TBL_SAILBOATS;
SELECT * FROM TBL_CHARTERS;
SELECT * FROM TBL_CREW;
SELECT * FROM TBL_ROLE;
SELECT * FROM TBL_CREWASSIGNMENT;

Refer back to the description and ERD for homework 7. Create two triggers as follows:

A trigger that restricts the commission field in the CrewAssignments table to appropriate values as specified in the roles table. Your trigger should fire on both “insert” and “update” events on the CrewAssignments table.

A trigger that automatically generates a late fee when the ActualReturn date field is updated in the Charters table. The fee should be computed as $100 times the number of days late a boat is returned.

Scrabble

2009-04-09T20:08:00.000-07:00

Homework 8 (100 points) Due 4/14/2009 3:45pm

This is a programming assignment. You may choose to work in group of size One or Two. Like all
previous homework, you are required to have a write up to explain your project's design and class
structure. You should put every group member's name, user id, section number in the write up.
Everyone in the same group should submit a copy but the write up and source file should be identical
for all members in the same group. One of the copies will be randomly chosen to be graded for both
members.

In particular in your write up, explain why you chose one of the two protocols (TCP/UDP) for the
network game.

Simplified Scrabble

In this homework, we will implement a scrabble game over the network. Scrabble is a word game. It
contains a 15x15 board and 100 tiles with letters. And each player takes turn to place a word with the
tiles in their hand to form a word on the board, except for the very first word played on the board, all
words must be somewhat connected with the existing words on the board. Each letter that forms the
word contains certain value points. And after each play, we will tally all points from newly formed
words on the board. When the game ends, the player with the highest points wins.

The detailed rules of the Scrabble game is as follows:

1.
The letter tiles. There will be 100 tiles. Two are blank and 98 have a letter on each. The point
value and the letter distribution of the tiles are as follows:
•
2 blank tiles (scoring 0 points)
•
1 point: E
×12, A×9, I
×9, O
×8, N
×6, R
×6, T
×6, L×4, S
×4, U
×4
•
2 points: D
×4, G
×3
•
3 points: B
×2, C
×2, M
×2, P×2
•
4 points: F×2, H
×2, V
×2, W
×2, Y×2
•
5 points: K
×1
•
8 points: J
×1, X
×1
•
10 points: Q
×1, Z
×1
2.
The board. The board will be 15X15 cells. For simplicity, we don't have special cells in our
board (like triple word or double letter etc.)
3.
The play.
(a) Starting the game. We choose one player randomly to start the game. And once the game
started, the player takes turns in clockwise fashion. At the beginning of the game, every
player draws 7 tiles from the bag of tiles (randomly). The first player plays a word on the
board, one of the tile must be on the center cell.
(b) Each turn. At each turn, the player can place tiles on the board or choose to pass his turn. A
proper play uses any number of the player's tiles to form a single continuous word ("main
word") on the board, reading either left-to-right or top-to-bottom. The main word must
either use the letters of one or more previously played words, or else have at least one of its
tiles horizontally or vertically adjacent to an already played word. If words other than the
main word are newly formed by the play, they are scored as well, and are subject to the

same criteria for acceptability. Along with the homework, we provided a word list that you
should use to check each newly formed word against. If there are any invalid words, the
player will take all the tiles back and lose his turn (and of course will get no point for this
turn). If all the words are valid, the player will retrieve new tiles from the tile bag until
either he has 7 tiles again or the bag is empty. The points for the player from this turn is the
total points of all the newly formed word, where each word's point is the sum of all letter
points that form this word regardless of the letter being placed before or during the play. If
the player managed to use up all his 7 tiles in the turn, he also gets 50 bonus point.

(c) Ending the game. The game ends when there is no more tiles to draw from the bag and one
of the players finished using all his tiles in a play. When the game ends this way, the person
who finished all his tiles get points from all the remaining tiles from the other players. And
all other players will have to deduct the sum of points of his/her own remaining tiles. The
game also ends if there are continuous passes from all players where the number of
continuous passes is twice the number of players. When the game ends this way, every
player will have to deduct the sum of points of his/her own remaining tiles.
(d) Winning the game. After the game is over, the player with the highest points wins.
Implementation requirement:

There is a Scrabble server that can serve multiple scrabble games. Each game can have 2 – 4 players.

A client can choose to create a game or join an existing game (by giving a game number or game name)
that hasn't started yet and has less than 4 players. Anyone that joined a game can start the game when
there are at least 2 players in that game. The players will be sitting clockwise in the order that they
joined the game. For example, A created a game “Game #12”, and then B joined, and then C joined. B
chose to start the game. So they will be sitting like this around the board:

player B

player A player C

You may choose to do the calculation of newly formed words/gained points/validation of the points on
the server side or on the client side.

GUI requirement:

Again, there is no need of a GUI for the server.

For the client, the GUI should provide the following functionalities.

1.
Displaying the 15x15 board, the board is updated after each successful play with the newly
placed tiles.
2.
Showing all the players around the board, and for each player, their current points, and the
number of tiles they have left, and identify whose turn it is to play.
3.
For the player that started the client, display the current tiles he has, his current total points. And
when it is this player's turn, activate the control, so that he can place the tiles on the board and
send out his play to the server and subsequently all other players.
4.
To make it easy for the player, please display both the letter and its point value on the tile and
on the board for placed tiles.

a
aardvark
abandon
abandoned
abandoning
abandons
abbreviate
abbreviated
abbreviates
abbreviating
abbreviation
abbreviations
abide
abilities
ability
able
abnormal
abnormally
abolish
abolished
abolishes
abolishing
abolition
abort
aborted
aborting
abortion
aborts
about
above
abroad
absence
absent
absolute
absolutely
absorb
absorbed
absorbing
absorbs
abstract
abstraction
absurd
abuse
abused
abuses
abusing
abusive
abysmal
academic
academics
accelerate
accent
accents
accept
acceptable
acceptance
accepted
accepting
accepts
access
accessed
accesses
accessible
accessing
accident
accidental
accidentally
accidents
accommodate
accommodation
accompanied
accompanies
accompany
accompanying
accomplish
accomplished
accomplishes
accomplishing
accord
accordance
accorded
according
accordingly
accords
account
accountant
accountants
accounted
accounting
accounts
accumulate
accumulated
accumulates
accumulating
accuracy
accurate
accurately
accusation
accusations
accuse
accused
accuses
accusing
accustom
accustomed
accustoming
accustoms
ace
achieve
achieved
achievement
achievements
achieves
achieving
acid
acknowledge
acknowledged
acknowledges
acknowledging
acorn
acoustic
acquaintance
acquire
acquired
acquires
acquiring
acquisition
acronym
acronyms
across
act
acted
acting
action
actions
activate
activated
activates
activating
active
actively
activities
activity
actor
actors
acts
actual
actually
acute
adapt
adaptation
adapted
adapting
adapts
add
added
addict
addicted
addicting
addictive
addicts
adding
addition
additional
additionally
additions
address
addressed
addresses
addressing
adds
adequate
adequately
adhere
adhered
adheres
adhering
adjacent
adjective
adjust
adjusted
adjusting
adjustment
adjustments
adjusts
administer
administered
administering
administers
administration
administrative
admirable
admiration
admire
admission
admit
admits
admitted
admittedly
admitting
adopt
adopted
adopting
adoption
adopts
adult
adults
advance
advanced
advances
advancing
advantage
advantageous
advantages
advent
adventure
adventures
adventurous
adverse
adversely
advert
advertise
advertised
advertisement
advertisements
advertises
advertising
adverts
advice
advisable
advise
advised
adviser
advisers
advises
advising
advisory
advocate
advocated
advocates
advocating
aerial
aesthetic
aesthetically
affair
affairs
affect
affected
affecting
affection
affects
afford
aforementioned
afraid
after
afternoon
afternoons
again
against
age
aged
agency
agenda
agent
agents
ages
aggressive
ago
agony
agree
agreed
agreeing
agreement
agreements
agrees
agricultural
ahead
aid
aided
aiding
aids
aim
aimed
aiming
aims
air
aircraft
airport
akin
alarm
alarmed
alarming
alarms
alas
albeit
album
albums
alcohol
alcoholic
alert
algebra
algebraic
algorithm
algorithms
alias
aliases
alien
aliens
align
aligned
aligning
alignment
aligns
alike
alive
all
allegation
allegations
allege
alleged
allegedly
alleges
alleging
allergic
alleviate
alliance
allies
allocate
allocated
allocates
allocating
allocation
allocations
allow
allowable
allowance
allowances
allowed
allowing
allows
ally
almost
alone
along
alongside
aloud
alpha
alphabet
alphabetic
alphabetical
already
also
alter
alteration
alterations
altered
altering
alternate
alternative
alternatively
alternatives
alters
although
altogether
always
am
amateur
amaze
amazed
amazes
amazing
amazingly
ambassador
amber
ambient
ambiguities
ambiguity
ambiguous
ambitious
amend
amended
amending
amendment
amends
among
amongst
amount
amounts
amp
ample
amplifier
amuse
amused
amusement
amuses
amusing
an
anagram
analogous
analogue
analogy
analysis
analyst
anarchy
anatomy
ancestor
ancestors
ancient
and
anecdote
anecdotes
angel
angels
anger
angle
angles
angry
anguish
animal
animals
anniversary
announce
announced
announcement
announcements
announces
announcing
annoy
annoyance
annoyed
annoying
annoys
annual
annually
anomalies
anomaly
anonymous
anorak
anoraks
another
answer
answered
answering
answers
anthology
anticipate
anticipated
anticipates
anticipating
anticipation
antidote
antique
antisocial
anxious
any
anybody
anyhow
anyone
anyplace
anything
anyway
anywhere
apart
apathetic
apathy
apologies
apology
apostrophe
appalled
appalling
appallingly
apparatus
apparatuses
apparent
apparently
appeal
appealed
appealing
appeals
appear
appearance
appearances
appeared
appearing
appears
append
appended
appending
appendix
appends
applause
apple
applicable
applicant
applicants
application
applications
applied
applies
apply
applying
appoint
appointed
appointing
appointment
appointments
appoints
appraisal
appreciate
appreciated
appreciates
appreciating
appreciation
approach
approached
approaches
approaching
appropriate
appropriately
approval
approve
approved
approves
approving
approximate
approximately
approximation
apt
arbitrarily
arbitrary
arc
arcade
arcane
arch
archaic
architecture
archive
archived
archives
archiving
are
area
areas
arena
arguable
arguably
argue
argued
argues
arguing
argument
arguments
arise
arisen
arises
arising
arithmetic
arm
armed
arming
arms
army
arose
around
arrange
arranged
arrangement
arrangements
arranges
arranging
array
arrays
arrest
arrested
arresting
arrests
arrival
arrive
arrived
arrives
arriving
arrogance
arrogant
arrow
arrows
art
article
articles
artificial
artificially
artist
artistic
artists
arts
as
ascend
ascended
ascending
ascends
ash
ashamed
ashcan
ashes
aside
ask
asked
asking
asks
asleep
aspect
aspects
assault
assemble
assembled
assembler
assembles
assembling
assembly
assert
asserted
asserting
assertion
asserts
assess
assessed
assesses
assessing
assessment
asset
assets
assign
assigned
assigning
assignment
assignments
assigns
assist
assistance
assistant
assisted
assisting
assists
associate
associated
associates
associating
association
associations
assort
assorted
assorting
assorts
assume
assumed
assumes
assuming
assumption
assumptions
assure
assured
assures
assuring
asterisk
asterisks
astronomer
astronomers
astronomy
asynchronous
at
ate
atheism
atheist
atheists
atlas
atmosphere
atmospheric
atom
atomic
atoms
atrocities
atrocity
attach
attached
attaching
attachment
attach s
attack
attacked
attacking
attacks
attain
attempt
attempted
attempting
attempts
attend
attendance
attendant
attended
attending
attends
attention
attentions
attitude
attitudes
attorney
attorneys
attract
attracted
attracting
attraction
attractive
attracts
attribute
attributed
attributes
attributing
audible
audience
audiences
audio
aunt
authentic
author
authorities
authority
authors
autobiography
automate
automated
automates
automatic
automatically
automating
automobile
automobiles
autumn
availability
available
average
avoid
avoided
avoiding
avoids
await
awaited
awaiting
awaits
awake
award
awarded
awarding
awards
aware
awareness
away
awful
awfully
awkward
axes
axiom
axioms
axis
babies
baby
back
backbone
backed
background
backgrounds
backing
backlog
backs
backspace
backward
backwards
bacteria
bacterium
bad
badge
badly
baffle
baffled
baffles
baffling
bag
baggage
bags
bake
baked
bakes
baking
balance
balanced
balances
balancing
ball
ballet
ballot
balls
ban
banal
banana
bananas
band
bands
bandwagon
bandwidth
bang
bank
bankrupt
banks
banned
banner
banning
bans
bar
bare
barely
bargain
bark
barked
barking
barks
baroque
barred
barrel
barrier
barriers
barring
barrister
barristers
bars
base
based
basement
bases
bash
bashed
bashes
bashing
basic
basically
basics
basing
basis
basket
bass
basses
bastard
bastards
bat
batch
bath
bathroom
baths
batteries
battery
battle
baud
bay
be
beach
beam
bean
beans
bear
beard
bearded
bearding
beards
bearing
bears
beast
beasts
beat
beaten
beating
beats
beautiful
beautifully
beauty
became
because
become
becomes
becoming
bed
bedroom
beds
beef
been
beer
beers
before
beforehand
beg
began
begin
beginner
beginners
beginning
begins
begun
behalf
behave
behaved
behaves
behaving
behind
being
beings
belief
beliefs
believable
believe
believed
believer
believers
believes
believing
bell
bells
belong
belonged
belonging
belongs
beloved
below
belt
bench
bend
bending
bends
beneath
beneficial
benefit
benefits
bent
beside
besides
best
bet
beta
bets
better
betting
between
beware
beyond
bias
biased
biases
biasing
bible
biblical
bicycle
bicycles
bid
bidding
bids
big
bigger
biggest
bigot
bigoted
bigotry
bill
billfold
billion
billions
bills
bin
binary
bind
binding
binds
biochemistry
biography
biological
biologist
biologists
biology
bird
birds
birth
birthday
biscuit
biscuits
bishop
bit
bite
bites
biting
bitmap
bits
bitten
bitter
bizarre
black
blackboard
blackmail
blacks
blade
blades
blame
blamed
blames
blaming
blank
blanket
blanks
blast
blasted
blasting
blasts
blatant
blatantly
bless
blessed
blesses
blessing
blew
blind
blindly
blink
bliss
blob
block
blocked
blocking
blocks
blood
bloody
blow
blowing
blown
blows
blue
blues
blurb
board
boards
boat
boats
bob
bobs
bodies
body
bog
bogged
bogging
boggle
boggles
bogs
bogus
boil
boiled
boiling
boils
bold
bolt
bomb
bombed
bombing
bombs
bond
bone
bones
bonus
book
booked
booking
booklet
books
bookshop
bookshops
bookstore
boom
boost
boot
boots
border
borderline
bore
bored
boredom
bores
boring
born
borne
borrow
borrowed
borrowing
borrows
boss
both
bother
bothered
bothering
bothers
bottle
bottles
bottom
bought
bounce
bound
boundaries
boundary
bounds
bout
bow
bowl
box
boxes
boy
boys
bracket
bracketed
bracketing
brackets
brain
brains
brake
brakes
branch
branches
brand
branded
branding
brands
brass
brave
breach
bread
break
breakdown
breakfast
breaking
breaks
breath
breathe
breathed
breathes
breathing
bred
breed
breeding
breeds
breeze
brethren
brick
bricks
bridge
bridges
brief
briefly
brigade
bright
brighter
brightest
brightly
brightness
brilliant
brilliantly
bring
bringing
brings
broad
broadcast
broadcasting
broadcasts
broadly
broke
broken
brother
brothers
brought
brown
browse
browsed
browses
browsing
brush
brutal
bubble
buck
bucket
bucks
budget
buffer
buffered
buffering
buffers
bug
bugger
buggers
bugs
build
building
buildings
builds
built
bulb
bulbs
bulk
bull
bullet
bulletin
bullets
bump
bunch
bundle
burden
bureaucracy
buried
buries
burn
burned
burning
burns
burnt
burst
bursting
bursts
bury
burying
bus
buses
bush
business
businesses
buss
bust
busy
but
butter
button
buttons
buy
buyer
buyers
buying
buys
by
bye
bypass
byte
bytes
cabbage
cabinet
cable
cabled
cables
cabling
caffeine
caf
cage
cake
cakes
calculate
calculated
calculates
calculating
calculation
calculations
calculator
calculus
calendar
call
called
caller
calling
calls
calm
cam
came
camera
cameras
camp
campaign
campaigned
campaigning
campaigns
camps
campus
can
cancel
cancels
cancer
candidate
candidates
cannot
canonical
cans
cant
cap
capabilities
capability
capable
capacity
capital
capitalism
capitalist
capitals
caps
captain
capture
captured
captures
capturing
car
carbon
card
cardboard
cards
care
cared
career
careers
careful
carefully
careless
cares
caring
carpet
carriage
carried
carrier
carries
carrot
carrots
carry
carrying
cars
cartoon
cartoons
cartridge
cartridges
case
cased
cases
cash
casing
cassette
cassettes
cast
casting
castle
casts
casual
cat
catastrophic
catch
catches
catching
categorically
categories
category
cater
catered
catering
caters
cathedral
catholic
cats
cattle
caught
causal
causality
cause
caused
causes
causing
caution
cave
caveat
cease
ceased
ceases
ceasing
ceiling
celebrate
celebrated
celebrates
celebrating
celebration
cell
cells
cellular
censor
censored
censoring
censors
censorship
cent
central
centrally
centuries
century
ceremony
certain
certainly
certainty
certificate
chain
chains
chair
chairman
chairs
chalk
challenge
challenged
challenges
challenging
chamber
champagne
champion
chance
chancellor
chances
change
changed
changeover
changes
changing
channel
channels
chaos
chaotic
chap
chapel
chaps
chapter
chapters
char
character
characteristic
characteristics
characters
charge
charged
charges
charging
charitable
charities
charity
charm
charmed
charming
charms
chars
chart
charter
charts
chase
chased
chases
chasing
chat
chats
chatted
chatting
cheap
cheaper
cheapest
cheaply
cheat
cheated
cheating
cheats
checked
checking
cheek
cheer
cheerful
cheers
cheese
chemical
chemicals
chemist
chemistry
chemists
chess
chest
chestnut
chew
chewed
chewing
chews
chicken
chickens
chief
child
childhood
childish
children
chip
chips
chocolate
choice
choices
choir
choose
chooses
choosing
chop
chopped
chopping
chops
choral
chord
chorus
chose
chosen
chuck
chucked
chucking
chucks
chunk
chunks
church
churches
cider
cigarette
cinema
circa
circle
circles
circuit
circuitry
circuits
circular
circulate
circulated
circulates
circulating
circulation
circumstance
circumstances
cite
cited
cites
cities
citing
citizen
citizens
city
civil
civilian
claim
claimed
claiming
claims
clarification
clarified
clarifies
clarify
clarifying
clarity
clash
clashes
class
classed
classes
classic
classical
classics
classification
classified
classifies
classify
classifying
classing
clause
clauses
clean
cleaned
cleaner
cleaners
cleanest
cleaning
cleanly
cleans
clear
clearance
cleared
clearer
clearest
clearing
clearly
clears
clever
cleverer
cleverest
clich
click
client
clients
cliff
climate
climb
climbed
climbing
climbs
clinic
clinical
clip
clipped
clipping
clips
clique
clock
clocks
clog
clone
clones
close
closed
closely
closer
closes
closest
closet
closing
closure
cloth
clothe
clothed
clothes
clothing
cloud
clouds
club
clubs
clue
clues
clumsy
cluster
clusters
coach
coal
coarse
coast
coat
coats
cobbler
cobblers
code
coded
codes
coding
coffee
coherent
coin
coincide
coincidence
coined
coining
coins
coke
cold
collaboration
collapse
collapsed
collapses
collapsing
collar
collate
collated
collates
collating
colleague
colleagues
collect
collected
collecting
collection
collections
collective
collects
college
colleges
colon
colony
column
columns
combat
combination
combinations
combine
combined
combines
combining
come
comedy
comes
comfort
comfortable
comfortably
comic
comics
coming
comma
command
commandment
commandments
commands
commas
commence
comment
commentary
commentator
commentators
commented
commenting
comments
commercial
commercially
commission
commissioned
commissioning
commissions
commit
commitment
commitments
commits
committed
committee
committees
committing
commodity
common
commonly
commons
communal
communicate
communicated
communicates
communicating
communication
communications
communism
communist
communists
communities
community
compact
companies
companion
company
comparable
comparative
comparatively
compare
compared
compares
comparing
comparison
comparisons
compassion
compatibility
compatible
compel
compelled
compelling
compels
compensate
compensation
compete
competed
competence
competent
competes
competing
competition
competitive
competitor
competitors
compilation
compile
compiled
compiler
compilers
compiles
compiling
complacent
complain
complained
complaining
complains
complaint
complaints
complement
complementary
complete
completed
completely
completeness
completes
completing
completion
complex
complexity
complicate
complicated
complicates
complicating
complication
complications
compliment
comply
component
components
compose
composed
composer
composers
composes
composing
composite
composition
compound
comprehend
comprehensible
comprehension
comprehensive
compress
compressed
compresses
compressing
compression
comprise
comprised
comprises
comprising
compromise
compulsion
compulsory
computation
computational
compute
computed
computer
computers
computes
computing
con
concatenate
concatenated
concatenates
concatenating
conceal
concealed
concealing
conceals
concede
conceivable
conceivably
conceive
conceived
conceives
conceiving
concentrate
concentrated
concentrates
concentrating
concentration
concept
conception
concepts
conceptual
concern
concerned
concerning
concerns
concert
concerto
concerts
concise
conclude
concluded
concludes
concluding
conclusion
conclusions
concrete
concur
concurrently
condemn
condemnation
condemned
condemning
condemns
condense
condensed
condenses
condensing
condition
conditional
conditioned
conditioning
conditions
condom
condone
conduct
conducted
conducting
conductor
conducts
conference
conferences
confess
confidence
confident
confidential
confidentiality
configuration
configurations
configure
configured
configures
configuring
confine
confined
confines
confining
confirm
confirmation
confirmed
confirming
confirms
conflict
conflicted
conflicting
conflicts
conform
confront
confronted
confronting
confronts
confuse
confused
confuses
confusing
confusion
congest
congested
congesting
congestion
congests
congratulate
congratulations
conjecture
conjunction
connect
connected
connecting
connection
connections
connector
connects
connotation
connotations
conscience
conscious
consciously
consciousness
consecutive
consensus
consent
consented
consenting
consents
consequence
consequences
consequent
consequently
conservation
conservative
conservatives
consider
considerable
considerably
considerate
consideration
considerations
considered
considering
considers
consist
consisted
consistency
consistent
consistently
consisting
consists
consolation
console
conspicuous
conspiracy
constant
constantly
constants
constituency
constituent
constituents
constitute
constitutes
constitution
constitutional
constrain
constrained
constraining
constrains
constraint
constraints
construct
constructed
constructing
construction
constructions
constructive
constructs
consult
consultancy
consultant
consultants
consultation
consulted
consulting
consults
consume
consumed
consumer
consumes
consuming
consumption
contact
contacted
contacting
contacts
contain
contained
container
containing
contains
contemplate
contemplated
contemplates
contemplating
contemporary
contempt
contend
content
contention
contentious
contents
contest
context
contexts
continent
continental
continual
continually
continuation
continuations
continue
continued
continues
continuing
continuity
continuous
continuously
continuum
contour
contraception
contract
contracted
contracting
contracts
contradict
contradicted
contradicting
contradiction
contradictory
contradicts
contrary
contrast
contravention
contribute
contributed
contributes
contributing
contribution
contributions
contributor
contributors
contrive
contrived
contrives
contriving
control
controlled
controller
controllers
controlling
controls
controversial
controversy
convenience
convenient
conveniently
convention
conventional
conventions
conversation
conversations
converse
conversely
conversion
conversions
convert
converted
converter
converting
converts
convey
convict
convicted
convicting
conviction
convictions
convicts
convince
convinced
convinces
convincing
convincingly
cook
cooked
cookie
cookies
cooking
cooks
cool
cooled
cooling
cools
cooperate
cooperation
coordinate
coordinates
coordination
cope
coped
copes
copied
copies
coping
copper
copy
copying
copyright
core
corn
corner
corners
corporate
corporation
corpse
corpses
correct
corrected
correcting
correction
corrections
correctly
corrects
correlate
correlation
correspond
corresponded
correspondence
correspondent
corresponding
corresponds
corridor
corrupt
corrupted
corrupting
corruption
corrupts
cosmic
cosmology
cost
costing
costly
costs
cotton
cough
could
council
councils
counsel
counsels
count
counted
counter
counterexample
counterpart
counterparts
counting
countless
countries
country
countryside
counts
county
couple
coupled
couples
coupling
courage
courier
course
courses
court
courtesy
courts
cousin
cover
coverage
covered
covering
covers
cow
cows
crack
cracked
cracking
cracks
craft
cramp
cramped
cramping
cramps
crap
crash
crashed
crashes
crashing
crass
crawl
crawled
crawling
crawls
crazy
cream
create
created
creates
creating
creation
creative
creator
creature
creatures
credibility
credible
credit
credits
creed
creep
crew
cricket
cried
cries
crime
crimes
criminal
criminals
crisis
crisp
crisps
criteria
criterion
critic
critical
criticism
criticisms
critics
crop
crops
cross
crossed
crosses
crossing
crossroad
crossroads
crossword
crowd
crowded
crowding
crowds
crown
crucial
crude
cruel
cruelty
cruise
cruised
cruises
cruising
crunch
crunched
crunches
crunching
crush
crushed
crushes
crushing
cry
crying
cryptic
crystal
crystals
cs
cube
cubic
cuckoo
cuddly
cue
culprit
cult
cultural
culture
cultures
cumbersome
cumming
cums
cumulative
cunning
cup
cupboard
cups
cure
cured
cures
curing
curiosity
curious
curiously
curly
currency
current
currently
curriculum
curry
curse
cursor
curtain
curtains
curve
curves
custard
custom
customary
customer
customers
customs
cut
cute
cuts
cutting
cycle
cycled
cycles
cycling
cyclist
cyclists
cylinder
cynic
cynical
daft
daily
damage
damaged
damages
damaging
damn
damnation
damned
damning
damns
damp
dance
danced
dances
dancing
danger
dangerous
dangerously
dangers
dare
dared
dares
daring
dark
darkness
darling
dash
dashed
dashes
dashing
data
database
databases
date
dated
dates
dating
datum
daughter
dawn
day
daylight
days
daytime
dead
deadline
deadly
deaf
deal
dealer
dealers
dealing
deals
dealt
dear
death
deaths
debatable
debate
debated
debates
debating
debt
debug
debugged
debugger
debugging
debugs
decade
decades
decay
decent
decide
decided
decides
deciding
decimal
decision
decisions
deck
declaration
declarations
declare
declared
declares
declaring
decline
declined
declines
declining
decode
decoded
decodes
decoding
decrease
decreased
decreases
decreasing
dedicate
dedicated
dedicates
dedicating
deduce
deduced
deduces
deducing
deduction
deductions
deed
deeds
deem
deemed
deeming
deems
deep
deeper
deepest
deeply
default
defaults
defeat
defeated
defeating
defeats
defect
defective
defects
defend
defended
defending
defends
deficiencies
deficiency
define
defined
defines
defining
definite
definitely
definition
definitions
definitive
defy
degenerate
degradation
degrade
degraded
degrades
degrading
degree
degrees
deity
delay
delayed
delaying
delays
delete
deleted
deletes
deleting
deletion
deliberate
deliberately
delicate
delicious
delight
delighted
delightful
delighting
delights
delimiters
deliver
delivered
delivering
delivers
delivery
delta
delusion
demand
demanded
demanding
demands
demented
demise
democracy
democratic
democratically
demolish
demolished
demolishes
demolishing
demonstrate
demonstrated
demonstrates
demonstrating
demonstration
demonstrations
denied
denies
denominator
denote
denotes
dense
density
dentist
deny
denying
department
departmental
departments
departure
depend
depended
dependence
depending
depends
deposit
depress
depressed
depresses
depressing
depression
deprive
deprived
deprives
depriving
depth
depths
deputy
derange
deranged
deranges
deranging
derivative
derive
derived
derives
deriving
derogatory
descend
descended
descending
descends
describe
described
describes
describing
description
descriptions
descriptive
desert
deserted
deserting
deserts
deserve
deserved
deserves
deserving
design
designate
designated
designates
designating
designed
designer
designers
designing
designs
desirable
desire
desired
desires
desiring
desk
desktop
despair
desperate
desperately
despise
despite
destination
destine
destined
destines
destining
destroy
destroyed
destroying
destroys
destruction
destructive
detach
detached
detaches
detaching
detail
detailed
detailing
details
detect
detectable
detected
detecting
detection
detective
detector
detects
deter
determination
determine
determined
determines
determining
deterrent
detract
devastate
devastated
devastates
devastating
develop
developed
developer
developers
developing
development
developments
develops
deviation
device
devices
devil
devious
devise
devised
devises
devising
devoid
devote
devoted
devotes
devoting
diagnosis
diagnostic
diagnostics
diagonal
diagram
diagrams
dial
dialect
dialects
dials
diameter
diary
dice
dictate
dictator
dictatorship
dictionaries
dictionary
did
die
died
dies
diesel
diet
differ
differed
difference
differences
different
differential
differentiate
differently
differing
differs
difficult
difficulties
difficulty
dig
digest
digging
digit
digital
digits
dignity
digs
dilemma
dim
dimension
dimensional
dimensions
dine
dined
diner
dines
dining
dinner
dip
diplomatic
dire
direct
directed
directing
direction
directions
directive
directives
directly
director
directories
directors
directory
directs
dirt
dirty
disable
disabled
disables
disabling
disadvantage
disadvantages
disagree
disagreed
disagreeing
disagreement
disagrees
disappear
disappeared
disappearing
disappears
disappoint
disappointed
disappointing
disappointment
disappoints
disaster
disasters
disastrous
disc
discard
discarded
discarding
discards
discharge
disciplinary
discipline
disclaimer
disco
disconnect
disconnected
disconnecting
disconnects
discontinue
discontinued
discontinues
discontinuing
discount
discounts
discourage
discouraged
discourages
discouraging
discover
discovered
discoveries
discovering
discovers
discovery
discrepancy
discrete
discretion
discriminate
discriminated
discriminates
discriminating
discrimination
discs
discuss
discussed
discusses
discussing
discussion
discussions
disease
diseases
disguise
disguised
disguises
disguising
disgust
disgusted
disgusting
disgusts
dish
dishes
dishonest
disk
dislike
disliked
dislikes
disliking
dismal
dismiss
dismissed
dismisses
dismissing
disorder
display
displayed
displaying
displays
disposable
disposal
dispose
disposed
disposes
disposing
disposition
dispute
disregard
disrupt
disruption
dissertation
dissimilar
distance
distances
distant
distasteful
distinct
distinction
distinctions
distinctive
distinctly
distinguish
distinguished
distinguishes
distinguishing
distort
distorted
distorting
distortion
distorts
distract
distracted
distracting
distracts
distress
distressed
distresses
distressing
distribute
distributed
distributes
distributing
distribution
district
disturb
disturbance
disturbed
disturbing
disturbs
ditch
ditto
dive
dived
diverse
diversity
divert
diverted
diverting
diverts
dives
divide
divided
divides
dividing
divine
diving
division
divisions
divorce
do
doctor
doctors
doctrine
document
documentary
documentation
documented
documenting
documents
dodge
doe
does
dog
dogma
dogs
doing
dole
dollar
dollars
domain
domestic
dominant
dominate
dominated
dominates
dominating
don
donate
donated
donates
donating
donation
donations
done
dons
doom
doomed
dooming
dooms
door
doors
dose
doses
dot
dots
dotted
dotting
double
doubled
doubles
doubling
doubt
doubtful
doubtless
doubts
down
downhill
downright
downstairs
downwards
dozen
dozens
drag
dragged
dragging
dragon
drags
drain
drained
draining
drains
drama
dramatic
dramatically
drank
drastic
drastically
draw
drawback
drawbacks
drawing
drawings
drawn
draws
dread
dreaded
dreadful
dreading
dreads
dream
dreaming
dreams
dreary
dress
dressed
dresses
dressing
drew
dried
dries
drift
drill
drink
drinking
drinks
drip
dripped
dripping
drips
drive
drivel
driven
driver
drivers
drives
driving
drop
dropped
dropping
drops
drove
drown
drowned
drowning
drowns
drug
drugs
drum
drums
drunk
drunken
dry
drying
dual
dubious
duck
ducks
due
duff
dug
dull
duly
dumb
dummy
dump
dumped
dumping
dumps
dumpster
duplicate
duplicated
duplicates
duplicating
duplication
duration
during
dust
dustbin
dusty
duties
duty
dying
dynamic
dynamically
dynamics
each
eager
eagerly
eagle
ear
earlier
earliest
early
earn
earned
earning
earns
ears
earth
ease
easier
easiest
easily
east
eastern
easy
eat
eaten
eater
eating
eats
eccentric
echo
echoed
echoes
echoing
ecological
ecology
economic
economical
economically
economics
economies
economy
edge
edges
edit
edited
editing
edition
editions
editor
editorial
editors
edits
educate
educated
educates
educating
education
educational
effect
effective
effectively
effectiveness
effects
efficiency
efficient
efficiently
effort
efforts
egg
eggs
ego
egos
eh
eight
eighteen
eighth
either
elaborate
elderly
elect
elected
electing
election
elections
electoral
electorate
electric
electrical
electricity
electron
electronic
electronically
electronics
elects
elegant
element
elementary
elements
elephant
elephants
elevator
elevators
eleven
eligible
eliminate
eliminated
eliminates
eliminating
elite
elitist
else
elsewhere
em
embarrass
embarrassed
embarrasses
embarrassing
embarrassment
embed
embedded
embedding
embeds
emerge
emerged
emergency
emerges
emerging
eminent
eminently
emit
emotion
emotional
emotionally
emotions
emphasis
empire
empirical
employ
employed
employee
employees
employer
employers
employing
employment
employs
emptied
empties
empty
emptying
emulate
emulation
emulator
emulators
enable
enabled
enables
enabling
enclose
enclosed
encloses
enclosing
encode
encoded
encodes
encoding
encounter
encountered
encountering
encounters
encourage
encouraged
encouragement
encourages
encouraging
end
ended
ending
endings
endless
endlessly
ends
enemies
enemy
energy
enforce
enforced
enforces
enforcing
engage
engaged
engages
engaging
engine
engineer
engineered
engineering
engineers
engines
enhance
enhanced
enhancement
enhances
enhancing
enjoy
enjoyable
enjoyed
enjoying
enjoyment
enjoys
enlarge
enlarged
enlarges
enlarging
enlighten
enlightened
enlightening
enlightenment
enlightens
enormous
enormously
enough
ensure
ensured
ensures
ensuring
entail
entails
enter
entered
entering
enterprise
enters
entertain
entertained
entertaining
entertainment
entertains
enthusiasm
enthusiastic
entire
entirely
entirety
entities
entitle
entitled
entitles
entitling
entity
entrance
entries
entry
envelope
envelopes
environment
environmental
environments
envisage
envisaged
envisages
envisaging
envy
epic
episode
episodes
equal
equality
equally
equals
equate
equation
equations
equilibrium
equip
equipment
equipped
equipping
equips
equivalent
equivalents
era
erase
erased
eraser
erases
erasing
ergo
err
erroneous
error
errors
escape
escaped
escapes
escaping
esoteric
especially
essay
essays
essence
essential
essentially
establish
established
establishes
establishing
establishment
establishments
estate
estimate
estimated
estimates
estimating
estimation
eternal
eternity
ethic
ethical
ethics
ethnic
etymology
evaluate
evaluated
evaluates
evaluating
evaluation
even
evened
evening
evenings
evenly
evens
event
events
eventual
eventually
ever
every
everybody
everyday
everyone
everything
everywhere
evidence
evident
evidently
evil
evils
evolution
evolutionary
evolve
evolved
evolves
evolving
exact
exactly
exaggerate
exaggerated
exaggerates
exaggerating
exam
examination
examine
examined
examiner
examines
examining
example
examples
exams
exceed
exceeded
exceeding
exceedingly
exceeds
excellent
except
excepted
excepting
exception
exceptional
exceptionally
exceptions
excepts
excess
excessive
excessively
exchange
exchanged
exchanges
exchanging
excite
excited
excitement
excites
exciting
exclamation
exclude
excluded
excludes
excluding
exclusion
exclusive
exclusively
excuse
excuses
executable
execute
executed
executes
executing
execution
executive
exempt
exercise
exercised
exercises
exercising
exhaust
exhausted
exhausting
exhaustive
exhausts
exhibit
exhibition
exist
existed
existence
existing
exists
exit
exited
exiting
exits
exotic
expand
expanded
expanding
expands
expansion
expect
expectation
expectations
expected
expecting
expects
expedition
expenditure
expense
expenses
expensive
experience
experienced
experiences
experiencing
experiment
experimental
experimentally
experimentation
experimented
experimenting
experiments
expert
expertise
experts
expire
expired
expires
expiring
expiry
explain
explained
explaining
explains
explanation
explanations
explanatory
explicit
explicitly
explode
exploded
explodes
exploding
exploit
exploitation
exploited
exploiting
exploits
exploration
explore
explored
explores
exploring
explosion
explosions
explosive
exponential
export
expose
exposed
exposes
exposing
exposure
express
expressed
expresses
expressing
expression
expressions
expressway
expressways
extant
extend
extended
extending
extends
extension
extensions
extensive
extensively
extent
extents
external
externally
extinction
extra
extract
extracted
extracting
extraction
extracts
extraneous
extraordinarily
extraordinary
extras
extreme
extremely
extremes
extremist
eye
eyes
eyesight
fabric
face
faced
faces
facilitate
facilities
facility
facing
fact
factor
factories
factors
factory
facts
factual
factually
faculties
faculty
fail
failed
failing
fails
failure
failures
faint
fainter
faintest
fair
fairer
fairest
fairly
fairness
fairy
faith
faithful
fake
fall
fallacious
fallacy
fallen
falling
falls
false
fame
familiar
familiarity
families
family
famine
famous
fan
fancy
fans
fantasies
fantastic
fantasy
far
farce
fare
farewell
farm
farmer
farmers
farther
farthest
fascinate
fascinated
fascinates
fascinating
fascist
fashion
fashionable
fashioned
fashioning
fashions
fast
faster
fastest
fat
fatal
fate
father
fathers
fatuous
faucet
fault
faults
faulty
fear
feared
fearing
fears
feasibility
feasible
feat
feature
featured
features
featuring
fed
federal
fee
feeble
feed
feedback
feeding
feeds
feel
feeling
feelings
feels
fees
feet
fell
fellow
fellows
felt
female
females
feminist
feminists
fence
fender
fenders
festival
fetch
fever
few
fewer
fewest
fiction
fictional
fiddle
fiddled
fiddles
fiddling
field
fields
fierce
fifteen
fifth
fifty
fight
fighter
fighting
fights
figure
figured
figures
figuring
file
filed
files
filing
fill
filled
filling
fills
film
filmed
filming
films
filter
filtered
filtering
filters
filthy
final
finally
finals
finance
finances
financial
financially
find
finding
findings
finds
fine
fined
finer
fines
finest
finger
fingers
fining
finish
finished
finishes
finishing
finite
fire
fired
fires
firework
fireworks
firing
firm
firmly
firms
first
firstly
fiscal
fish
fished
fishes
fishing
fit
fits
fitted
fitting
five
fiver
fix
fixed
fixes
fixing
fizzy
flag
flagged
flagging
flags
flame
flames
flash
flashed
flashes
flashing
flat
flaw
flawed
flawing
flaws
fleet
flesh
flew
flexibility
flexible
flied
flies
flight
flip
flipped
flipping
flips
float
floated
floating
floats
flood
flooded
flooding
floods
floor
floors
floppy
flour
flow
flowed
flower
flowers
flowing
flown
flows
fluctuation
fluctuations
fluent
fluffy
fluid
flush
flushed
flushes
flushing
flute
fly
flying
foam
focus
fog
fold
folded
folder
folders
folding
folds
folk
folks
follow
followed
follower
followers
following
follows
fond
font
fonts
food
foods
fool
fooled
fooling
foolish
fools
foot
football
footnote
footnotes
for
forbade
forbid
forbidden
forbidding
forbids
force
forced
forces
forcibly
forcing
forecast
forecasting
forecasts
foreign
foreigner
foreigners
foreseeable
forest
forests
forever
forgave
forget
forgets
forgetting
forgive
forgiven
forgives
forgiving
forgot
forgotten
fork
form
formal
formally
format
formation
formats
formatted
formatting
formed
former
formerly
forming
forms
formula
formulation
forth
forthcoming
fortnight
fortunate
fortunately
fortune
forty
forum
forward
forwarded
forwarding
forwards
fossil
fought
foul
found
foundation
foundations
founded
founding
founds
fountain
four
fourteen
fourth
fraction
fractions
fragile
fragment
fragments
frame
frames
framework
frank
frankly
frantic
fraud
freak
freaks
free
freed
freedom
freeing
freely
frees
freeway
freeways
freeze
freezes
freezing
french
frequencies
frequency
frequent
frequently
fresh
friction
fried
friend
friendly
friends
friendship
fries
frighten
frightened
frightening
frightens
fringe
frivolous
frog
frogs
from
front
frown
frowned
frowning
frowns
froze
frozen
fruit
fruits
frustrate
frustrated
frustrates
frustrating
frustration
fry
frying
fudge
fuel
fulfilled
fulfilling
full
fuller
fullest
fully
fume
fumes
fun
function
functional
functionality
functioned
functioning
functions
fund
fundamental
fundamentalist
fundamentally
funded
funding
funds
funeral
funnier
funniest
funny
fur
furniture
furry
further
furthermore
furthest
fuse
fusion
fuss
fussy
futile
future
fuzzy
gain
gained
gaining
gains
galactic
galaxy
game
games
gang
gap
gaps
garage
garbage
garble
garbled
garbles
garbling
garden
gardens
gas
gasoline
gasp
gate
gates
gateway
gather
gathered
gathering
gathers
gave
gay
gear
geared
gearing
gears
gender
gene
general
generally
generate
generated
generates
generating
generation
generations
generator
generators
generic
generous
genes
genetic
genetically
genetics
genius
genocide
genre
gentle
gentleman
gentlemen
gently
genuine
genuinely
geographical
geography
geology
geometry
gesture
get
gets
getting
ghastly
ghost
giant
gibberish
gift
gifts
gig
gin
girl
girlfriend
girls
give
given
gives
giving
glad
gladly
glance
glass
glasses
glean
gleaned
gleaning
gleans
global
globally
glorious
glory
glossy
glove
gloves
glow
glowed
glowing
glows
glue
gnome
go
goal
goals
goat
god
gods
goes
going
gold
golden
goldfish
goldfishes
golf
gone
good
goodbye
goodies
goodness
goods
goody
gorgeous
gospel
gossip
got
gotten
govern
governed
governing
government
governments
governor
governs
gown
grab
grabbed
grabbing
grabs
grace
grade
grades
gradual
gradually
graduate
graduated
graduates
graduating
graduation
graffiti
graffito
grain
grammar
grammatical
grand
grandfather
grandmother
grands
grant
granted
granting
grants
graph
graphic
graphical
graphics
graphs
grasp
grass
grateful
gratefully
gratuitous
gratuitously
grave
gravitational
gravity
greasy
great
greater
greatest
greatly
greed
greedy
green
grew
grid
grief
grim
grind
grinding
grinds
grip
grips
groan
gross
grosses
grossly
ground
grounds
group
grouped
grouping
groups
grow
growing
grown
grows
growth
guarantee
guaranteed
guaranteeing
guarantees
guard
guarded
guarding
guards
guess
guessed
guesses
guessing
guest
guests
guidance
guide
guided
guideline
guidelines
guides
guiding
guilt
guilty
guinea
guitar
gulf
gullible
gum
gun
guns
gut
guts
gutter
guy
guys
ha
habit
habits
hack
hacked
hacker
hackers
hacking
hacks
had
hail
hair
haircut
hairs
hairy
half
hall
halls
halt
halted
halting
halts
halve
halves
ham
hammer
hand
handbook
handed
handful
handicap
handing
handle
handled
handler
handles
handling
hands
handy
hang
hanged
hanging
hangover
hangs
happen
happened
happening
happens
happier
happiest
happily
happiness
happy
hard
hardback
harden
hardened
hardening
hardens
harder
hardest
hardly
hardship
hardware
hardy
harm
harmful
harmless
harmony
harsh
has
hash
hassle
hasten
hasty
hat
hate
hated
hates
hating
hatred
hats
have
having
havoc
hay
hazard
hazards
hazy
he
head
headache
headed
header
headers
heading
headline
headlines
heads
health
healthy
heap
hear
heard
hearing
hears
heart
heartily
hearts
heat
heated
heating
heats
heaven
heavens
heavier
heaviest
heavily
heavy
heel
heels
height
heights
held
helicopter
hell
hello
helmet
help
helped
helpful
helping
helpless
helps
hence
henceforth
her
herd
here
hereby
heresy
heritage
hero
heroes
heroic
heroin
herring
herrings
herself
hesitate
heterosexual
hexadecimal
hey
hid
hidden
hide
hided
hideous
hideously
hides
hiding
hierarchical
hierarchy
high
higher
highest
highlight
highlighted
highlighting
highlights
highly
highway
highways
hilarious
hill
hills
him
himself
hindsight
hint
hinted
hinting
hints
hip
hire
hired
hires
hiring
his
historian
historians
historic
historical
historically
history
hit
hitherto
hits
hitting
ho
hobby
hog
hold
holder
holders
holding
holds
hole
holes
holiday
holidays
hollow
holy
home
homes
homosexual
homosexuality
honest
honestly
honesty
honey
honorary
hook
hooked
hooking
hooks
hope
hoped
hopeful
hopefully
hopeless
hopelessly
hopes
hoping
horde
hordes
horizon
horizontal
horizontally
horn
horrendous
horrendously
horrible
horribly
horrid
horrific
horrified
horrifies
horrify
horrifying
horror
horse
horses
hospital
hospitals
host
hostile
hosts
hot
hotel
hour
hours
house
housed
household
houses
housing
how
however
huge
hugely
huh
hum
human
humane
humanity
humans
humble
humbly
humorous
hundred
hundreds
hung
hungry
hunt
hunted
hunting
hunts
hurry
hurt
hurting
hurts
husband
hut
hydrogen
hyphen
hypocrisy
hypocrite
hypocritical
hypothesis
hypothetical
hysterical
ice
icon
icons
id
idea
ideal
idealistic
ideally
ideals
ideas
identical
identically
identification
identified
identifier
identifiers
identifies
identify
identifying
identity
ideological
ideology
idiom
idiosyncratic
idiot
idiotic
idiots
idle
if
ignorance
ignorant
ignore
ignored
ignores
ignoring
ill
illegal
illegally
illiterate
illness
illogical
illusion
illustrate
illustrated
illustrates
illustrating
illustration
illustrations
image
images
imaginary
imagination
imaginative
imagine
imagined
imagines
imagining
imbalance
immature
immediate
immediately
immense
immensely
imminent
immoral
immortal
immune
impact
impair
impaired
impairing
impairs
impend
impended
impending
impends
imperative
imperfect
imperial
impersonal
implausible
implement
implementation
implementations
implemented
implementing
implements
implication
implications
implicit
implicitly
implied
implies
imply
implying
import
importance
important
importantly
imported
importing
imports
impose
imposed
imposes
imposing
impossible
impractical
impress
impressed
impresses
impressing
impression
impressions
impressive
imprison
imprisoned
imprisoning
imprisons
improbable
improve
improved
improvement
improvements
improves
improving
impulse
in
inability
inaccessible
inaccuracies
inaccuracy
inaccurate
inadequate
inadvertently
inane
inappropriate
incapable
incarnation
incentive
inch
inches
incidence
incident
incidental
incidentally
incidents
inclination
incline
inclined
inclines
inclining
include
included
includes
including
inclusion
inclusive
incoherent
income
incoming
incompatible
incompetence
incompetent
incomplete
incomprehensible
inconsistencies
inconsistency
inconsistent
inconvenience
inconvenienced
inconveniences
inconveniencing
inconvenient
incorporate
incorporated
incorporates
incorporating
incorrect
incorrectly
increase
increased
increases
increasing
increasingly
incredible
incredibly
increment
incur
incurred
incurring
incurs
indeed
indefensible
indefinite
indefinitely
indent
independence
independent
independently
indeterminate
index
indexed
indexes
indexing
indicate
indicated
indicates
indicating
indication
indications
indicative
indicator
indicators
indictment
indirect
indirection
indirectly
indistinguishable
individual
individually
individuals
induce
induced
induces
inducing
induction
indulge
indulged
indulges
indulging
industrial
industries
industry
ineffective
inefficiency
inefficient
inequality
inertia
inevitable
inevitably
inexperienced
infallible
infamous
infant
infantile
infect
infected
infecting
infection
infects
infelicity
infer
inference
inferior
inferiority
infinite
infinitely
infinity
inflation
inflexible
inflict
influence
influenced
influences
influencing
influential
info
inform
informal
informally
information
informative
informed
informing
informs
infrastructure
infrequent
infringement
ingenious
ingredient
ingredients
inhabit
inhabitant
inhabitants
inhabited
inhabiting
inhabits
inherent
inherently
inherit
inheritance
inherited
inheriting
inherits
inhibit
inhibited
inhibiting
inhibition
inhibits
initial
initially
initials
initiate
initiated
initiates
initiating
initiative
inject
injure
injured
injures
injuries
injuring
injury
injustice
ink
inner
innocence
innocent
innovation
innovative
input
inputs
inputted
inputting
insane
insect
insects
insecure
insensitive
insert
inserted
inserting
insertion
inserts
inside
insidious
insight
insignificant
insist
insisted
insistence
insisting
insists
insofar
inspect
inspected
inspecting
inspection
inspects
inspiration
inspire
inspired
inspires
inspiring
install
installation
installations
installed
installing
installs
instance
instances
instant
instantly
instead
instinct
institute
institution
institutions
instruct
instructed
instructing
instruction
instructions
instructs
instrument
instrumental
instruments
insufficient
insult
insulted
insulting
insults
insurance
intact
intake
integer
integers
integral
integrate
integrated
integrates
integrating
integration
integrity
intellect
intellectual
intelligence
intelligent
intend
intended
intending
intends
intense
intensely
intensity
intensive
intent
intention
intentional
intentionally
intentions
inter
interact
interacted
interacting
interaction
interactions
interactive
interactively
interacts
intercourse
interest
interested
interesting
interestingly
interests
interface
interfaced
interfaces
interfacing
interfere
interfered
interference
interferes
interfering
interim
interior
intermediate
intermittent
internal
internally
internals
international
interpret
interpretation
interpretations
interpreted
interpreter
interpreting
interprets
interrogate
interrupt
interrupted
interrupting
interruption
interruptions
interrupts
intersection
intersections
interval
intervals
intervene
intervened
intervenes
intervening
intervention
interview
interviewed
interviewing
interviews
intimate
into
intolerance
intrinsic
intrinsically
introduce
introduced
introduces
introducing
introduction
introductory
intuitive
invade
invaded
invades
invading
invalid
invalidate
invaluable
invariably
invasion
invent
invented
inventing
invention
inventions
inventor
invents
inverse
invert
inverted
inverting
inverts
invest
investigate
investigated
investigates
investigating
investigation
investigations
investment
invisible
invitation
invite
invited
invites
inviting
invoke
invoked
invokes
invoking
involve
involved
involvement
involves
involving
ion
irate
iron
ironic
irony
irrational
irrelevant
irrespective
irresponsible
irritate
irritated
irritates
irritating
irritation
is
island
islands
isolate
isolated
isolates
isolating
isolation
issue
issued
issues
issuing
it
item
items
its
itself
jack
jacket
jackets
jail
jam
jammed
jamming
jams
jargon
jazz
jealous
jeans
jellies
jelly
jerk
jest
jet
job
jobs
join
joined
joining
joins
joint
jointly
joints
joke
joked
jokes
joking
jolly
journal
journalist
journalists
journals
journey
joy
judge
judged
judges
judging
juice
jump
jumped
jumping
jumps
junction
jungle
junior
junk
jury
just
justice
justifiable
justifiably
justification
justified
justifies
justify
justifying
juvenile
keen
keep
keeper
keeping
keeps
ken
kept
kernel
kettle
key
keyboard
keyboards
keyed
keying
keys
keystroke
keystrokes
keyword
keywords
kick
kicked
kicking
kicks
kid
kidded
kidding
kidnap
kidnapped
kidnapping
kidnaps
kidney
kids
kill
killed
killer
killing
kills
kind
kindly
kindness
kinds
king
kingdom
kings
kiss
kit
kitchen
kits
knee
knees
knew
knife
knight
knock
knocked
knocking
knocks
know
knowing
knowledge
known
knows
lab
label
labels
laboratory
labs
lack
lacked
lacking
lacks
lad
ladder
ladies
lady
lag
lager
laid
lain
lake
lamp
land
landed
landing
landlord
lands
landscape
lane
language
languages
large
largely
larger
largest
lark
laser
lasers
last
lasted
lasting
lasts
late
lately
later
latest
latter
laugh
laughed
laughing
laughs
laughter
launch
launched
launches
launching
lavatory
law
lawn
laws
lawyer
lawyers
lay
layer
layers
laying
layout
lays
laziness
lazy
leach
lead
leaded
leader
leaders
leadership
leading
leads
leaf
leaflet
leaflets
league
leak
lean
leaned
leaning
leans
leap
learn
learning
learns
least
leather
leave
leaved
leaves
leaving
lecture
lectured
lecturer
lecturers
lectures
lecturing
led
left
leg
legal
legally
legend
legendary
legible
legislation
legitimate
legitimately
legs
leisure
lemon
lend
lending
lends
length
lengths
lengthy
lenient
lens
lenses
lent
lesbian
less
lesser
lesson
lessons
lest
let
lethal
lets
letter
letters
letting
level
levels
liability
liable
liaison
libel
liberal
liberties
liberty
librarian
libraries
library
lid
lie
lied
lies
life
lifestyle
lifetime
lift
lifted
lifting
lifts
light
lighted
lighter
lightest
lighting
lightly
lightning
lightninged
lightnings
lights
like
liked
likelihood
likely
likes
likewise
liking
limb
limbs
limit
limitation
limitations
limited
limiting
limits
line
linear
lined
lines
linguistic
lining
link
linkage
linked
linking
links
lion
lip
lips
liquid
liquor
lisp
list
listed
listen
listened
listener
listening
listens
listing
listings
lists
lit
literal
literally
literary
literate
literature
litter
little
live
lived
lively
liver
lives
livest
living
load
loaded
loader
loading
loads
loan
loans
lobby
local
locally
locals
locate
located
locates
locating
location
locations
lock
locked
locking
locks
lodge
log
logged
logging
logic
logical
logically
logo
logs
lonely
long
longer
longest
look
looked
looking
looks
loop
loophole
loops
loose
loosely
lord
lords
lorries
lorry
lose
loses
losing
loss
losses
lost
lot
lots
loud
louder
loudest
loudly
lousy
love
loved
lovely
lover
lovers
loves
loving
low
lower
lowered
lowering
lowers
lowest
loyal
luck
luckily
lucky
ludicrous
ludicrously
luggage
lump
lumps
lunatic
lunch
lunchtime
lung
lungs
lurk
lurked
lurking
lurks
lust
luxury
lying
lyric
lyrics
machine
machinery
machines
mad
made
madness
magazine
magazines
magic
magical
magnetic
magnificent
magnitude
mail
mailbox
mailed
mailing
mails
main
mainframe
mainframes
mainly
mains
mainstream
maintain
maintained
maintaining
maintains
maintenance
maize
major
majority
make
maker
makers
makes
making
male
males
malfunction
malicious
man
manage
managed
management
manager
managers
manages
managing
mandate
mandatory
mangle
mangled
mangles
mangling
mania
manifestation
manifestly
manifesto
manipulate
manipulated
manipulates
manipulating
manipulation
mankind
manned
manner
manning
manpower
mans
manual
manually
manuals
manufacture
manufactured
manufacturer
manufacturers
manufactures
manufacturing
many
map
mapped
mapping
maps
march
margin
marginal
marginally
margins
marital
mark
marked
marker
markers
market
marketed
marketing
markets
marking
marks
marriage
married
marries
marry
marrying
mask
mass
masses
massive
massively
master
masters
match
matched
matches
matching
mate
material
materials
mathematical
mathematically
mathematician
mathematicians
mathematics
matrices
matrix
matter
matters
mature
maximum
may
maybe
mayor
maze
me
meal
meals
mean
meaning
meaningful
meaningless
meanings
means
meant
meantime
meanwhile
measure
measured
measurement
measurements
measures
measuring
meat
mechanic
mechanical
mechanics
mechanism
mechanisms
media
medical
medicine
medieval
medium
mediums
meet
meeting
meetings
meets
megabyte
megabytes
melody
melt
member
members
membership
memorable
memories
memory
men
mend
mended
mending
mends
mental
mentality
mentally
mention
mentioned
mentioning
mentions
menu
menus
mercury
mercy
mere
merely
merge
merged
merges
merging
merit
merits
merry
mess
message
messages
messed
messes
messing
messy
met
metal
metaphor
method
methods
metric
metro
metros
mice
microcomputer
microcomputers
microprocessor
microwave
midday
middle
midnight
might
mighty
migrate
migrated
migrates
migrating
migration
mild
mildly
mile
mileage
miles
military
milk
mill
million
millions
mimic
mind
minded
minding
mindless
minds
mine
mined
mines
minimal
minimalist
minimum
mining
minister
ministers
minor
minorities
minority
mint
minus
minute
minutes
miracle
miracles
miraculous
mirror
mirrors
miscellaneous
misdirect
misdirected
misdirecting
misdirects
miserable
miserably
misery
misfortune
misguide
misguided
misguides
misguiding
misinterpret
misinterpreted
misinterpreting
misinterprets
mislead
misleading
misleads
misled
misplace
misplaced
misplaces
misplacing
misprint
misread
misreading
misreads
misrepresent
misrepresented
misrepresenting
misrepresents
miss
missed
misses
missile
missiles
missing
mission
mist
mistake
mistaken
mistakenly
mistakes
mistaking
mistook
mists
misunderstand
misunderstanding
misunderstands
misunderstood
misuse
mix
mixed
mixes
mixing
mixture
mnemonic
moan
moaned
moaning
moans
mob
mobile
mock
mod
mode
model
models
moderate
moderately
moderation
modern
modes
modest
modification
modifications
modified
modifies
modify
modifying
module
modules
mole
molecular
molecule
molecules
moment
momentarily
moments
momentum
monarch
money
monitor
monitored
monitoring
monitors
monkey
monkeys
monochrome
monopoly
monster
monsters
month
monthly
months
mood
moon
moons
moral
morality
morally
morals
more
moreover
morning
mornings
moron
morons
mortal
mortality
mortals
most
mostly
mother
mothers
motion
motions
motivate
motivated
motivates
motivating
motivation
motive
motives
motor
motors
motorway
motorways
motto
mount
mountain
mountains
mounted
mounting
mounts
mouse
mouth
move
moved
movement
movements
moves
movie
movies
moving
much
muck
mucked
mucking
mucks
mud
muddle
muddled
muddles
muddling
mug
mugs
multiple
multiples
multiplication
multiplied
multiplies
multiply
multiplying
mum
mumble
mummy
mundane
murder
murdered
murderer
murdering
murders
muscle
muscles
museum
museums
music
musical
musician
musicians
must
mutter
muttered
muttering
mutters
mutual
mutually
my
myself
mysteries
mysterious
mysteriously
mystery
mystic
myth
mythical
mythology
myths
nail
nailed
nailing
nails
naive
naked
name
named
nameless
namely
names
naming
narrative
narrow
narrower
narrowest
nastier
nastiest
nasty
nation
national
nationally
nations
native
natives
natural
naturally
nature
naughty
nay
near
nearby
nearer
nearest
nearly
neat
neatly
necessarily
necessary
necessity
neck
need
needed
needing
needle
needles
needless
needlessly
needs
negate
negative
neglect
neglected
neglecting
neglects
negligible
negotiable
negotiate
negotiated
negotiates
negotiating
negotiation
negotiations
neither
nerve
nerves
nervous
nest
nested
nesting
nests
net
nets
network
networked
networking
networks
neural
neutral
never
nevertheless
new
newcomer
newcomers
newer
newest
newly
news
newsletter
newsletters
newspaper
newspapers
next
nice
nicely
nicer
nicest
nick
nicked
nicking
nickname
nicknames
nicks
night
nightmare
nights
nil
nine
no
noble
nobody
node
nodes
noise
noises
noisy
nominal
nominally
nominate
nominated
nominates
nominating
none
nonetheless
nonsense
noon
nor
norm
normal
normality
normally
north
northern
nose
noses
nostalgia
not
notable
notably
notation
note
noted
notes
nothing
notice
noticeable
noticeably
noticed
notices
noticing
notification
notified
notifies
notify
notifying
noting
notion
notions
notorious
notwithstanding
noun
nouns
novel
novels
novelty
novice
novices
now
nowadays
nowhere
nuclear
nuisance
null
numb
number
numbered
numbering
numbers
numbest
numeral
numerals
numeric
numerical
numerous
nun
nuns
nurse
nurses
nut
nuts
oar
obey
obeyed
obeying
obeys
object
objected
objecting
objection
objectionable
objections
objective
objects
obligation
obligatory
oblige
obliged
obliges
obliging
obnoxious
obscene
obscure
obscured
obscures
obscuring
obscurity
observation
observations
observe
observed
observer
observers
observes
observing
obsess
obsessed
obsesses
obsessing
obsession
obsolete
obstruct
obstructed
obstructing
obstructs
obtain
obtainable
obtained
obtaining
obtains
obvious
obviously
occasion
occasional
occasionally
occasions
occupation
occupied
occupies
occupy
occupying
occur
occurred
occurrence
occurrences
occurring
occurs
ocean
odd
oddly
odds
of
off
offend
offended
offender
offenders
offending
offends
offer
offered
offering
offerings
offers
offhand
office
officer
officers
offices
official
officially
officials
offset
offsets
offsetting
offspring
often
oh
oil
old
older
oldest
omission
omissions
omit
omits
omitted
omitting
on
once
one
ones
oneself
ongoing
onion
only
onto
onus
onwards
open
opened
opening
openly
opens
opera
operas
operate
operated
operates
operating
operation
operational
operations
operator
operators
opinion
opinions
opponent
opponents
opportunities
opportunity
oppose
opposed
opposes
opposing
opposite
opposition
oppress
oppressed
oppresses
oppressing
oppression
opt
opted
optic
optical
optimal
optimistic
optimum
opting
option
optional
optionally
options
opts
opus
opuses
or
oral
orange
orbit
orbital
orchestra
orchestral
order
ordered
ordering
orders
ordinary
organ
organic
organs
orient
oriental
orientate
orientated
orientates
orientating
orientation
oriented
orienting
orients
origin
original
originally
originals
originate
originated
originates
originating
originator
origins
orthodox
other
others
otherwise
ought
our
ours
ourselves
out
outcome
outcomes
outcry
outdated
outer
outgoing
outline
outlined
outlines
outlining
outlook
output
outputs
outrage
outraged
outrageous
outrages
outraging
outright
outset
outside
outstanding
outweigh
outweighs
over
overall
overcame
overcome
overcomes
overcoming
overdraft
overdue
overflow
overhead
overheads
overlap
overload
overloaded
overloading
overloads
overlong
overlook
overlooked
overlooking
overlooks
overly
overnight
overprice
overpriced
overprices
overpricing
overridden
override
overrides
overriding
overrode
overseas
overtime
overtone
overtones
overview
overwhelm
overwhelmed
overwhelming
overwhelms
overwriting
overwritten
owe
owed
owes
owing
own
owned
owner
owners
ownership
owning
owns
oxygen
ozone
pace
pacifier
pack
package
packaged
packages
packaging
packed
packet
packets
packing
packs
pad
padded
padding
pads
page
paged
pages
paging
paid
pain
painful
painfully
painless
pains
paint
painted
painting
paintings
paints
pair
pairs
palace
pale
pan
panel
panels
panic
pant
pants
paper
paperback
papers
par
parade
paradise
paradox
paragraph
paragraphs
parallel
parallels
parameter
parameters
paranoia
paranoid
paraphrase
pardon
parent
parentheses
parenthesis
parents
parity
park
parked
parking
parks
parliament
parochial
parody
parrot
parse
parsed
parses
parsing
part
partial
partially
participant
participants
participate
participated
participates
participating
particle
particles
particular
particularly
parties
partition
partitioned
partitioning
partitions
partly
partner
partners
parts
party
pass
passage
passages
passed
passenger
passengers
passes
passing
passion
passionate
passive
passport
password
passwords
past
paste
pat
patch
patched
patches
patching
patent
path
pathetic
paths
patience
patient
patients
pattern
patterns
pause
paused
pauses
pausing
pavement
pay
payed
paying
payment
payments
pays
peace
peaceful
peak
peaks
peanut
peanuts
peasant
peasants
peculiar
pedal
pedant
pedantic
pedantry
pedants
pedestrian
pedestrians
peer
peers
pen
penalties
penalty
pence
pencil
pended
pending
pends
penguin
pennies
penny
pens
people
peoples
per
perceive
perceived
perceives
perceiving
percent
percentage
percents
perception
perfect
perfection
perfectly
perform
performance
performances
performed
performing
performs
perhaps
period
periodic
periodically
periods
peripheral
peripherals
permanent
permanently
permissible
permission
permit
permits
permitted
permitting
perpetual
persecute
persecuted
persecutes
persecuting
persist
persistent
person
personal
personalities
personality
personally
personnel
persons
perspective
persuade
persuaded
persuades
persuading
persuasion
perverse
pet
petrol
petty
pharmacies
pharmacy
phase
phased
phases
phasing
phenomena
phenomenon
phenomenons
philosopher
philosophers
philosophical
philosophies
philosophy
phoenix
phone
phoned
phones
phoning
photo
photocopy
photograph
photographic
photographs
photos
phrase
phrased
phrases
phrasing
physic
physical
physically
physicist
physicists
physics
physiology
pi
piano
pick
picked
picking
picks
picture
pictures
pie
piece
pieces
pig
pigeon
pigs
pile
piles
pill
pills
pilot
pin
pinch
pinched
pinches
pinching
pink
pins
pint
pints
pipe
pipeline
pipes
pit
pitch
pitfall
pitfalls
pity
pizza
pizzas
place
placed
places
placing
plague
plagued
plagues
plaguing
plain
plainly
plan
plane
planes
planet
planetary
planets
planned
planning
plans
plant
planted
planting
plants
plaster
plastered
plastering
plasters
plastic
plate
plates
platform
plausible
play
played
player
players
playground
playing
plays
plea
pleasant
pleasantly
please
pleased
pleases
pleasing
pleasure
plenty
plot
plots
plotted
plotter
plotting
ploy
plug
plugged
plugging
plugs
plural
plus
pocket
pockets
poem
poems
poet
poetic
poetry
poets
point
pointed
pointer
pointers
pointing
pointless
points
poison
poisoned
poisoning
poisons
poke
polar
pole
police
policeman
policies
policy
polish
polished
polishes
polishing
polite
politeness
political
politically
politician
politicians
politics
poll
polls
pollution
polynomial
pompous
pool
poor
poorer
poorest
poorly
pop
pope
popped
popping
pops
populace
popular
popularity
populate
populated
populates
populating
population
populations
pork
pornography
port
portability
portable
ported
porter
porters
porting
portion
portions
portray
portrayed
portraying
portrays
ports
pose
posed
poses
posing
position
positioned
positioning
positions
positive
positively
possess
possessed
possesses
possessing
possession
possibilities
possibility
possible
possibly
post
postage
postal
postcard
posted
poster
posters
posting
postmaster
postpone
postponed
postpones
postponing
posts
postscript
postulate
pot
potato
potatoes
potential
potentially
pound
pounds
pour
poured
pouring
pours
poverty
powder
power
powered
powerful
powering
powers
practicable
practical
practically
practicals
pragmatic
praise
pray
prayed
prayer
prayers
praying
prays
preach
preached
preaches
preaching
precaution
precautions
precede
preceded
precedence
precedent
precedes
preceding
precious
precise
precisely
precision
predecessor
predecessors
predict
predictable
predicted
predicting
prediction
predictions
predicts
predominantly
preface
prefer
preferable
preferably
preference
preferences
preferred
preferring
prefers
prefix
prefixed
prefixes
prefixing
pregnancy
pregnant
prejudice
prejudiced
prejudices
prejudicing
preliminary
premature
prematurely
premise
premises
premium
preparation
prepare
prepared
prepares
preparing
prerequisite
prescribe
prescribed
prescribes
prescribing
prescription
presence
present
presentation
presented
presenting
presently
presents
preserve
preserved
preserves
preserving
president
press
pressed
presses
pressing
pressure
pressures
presumably
presume
presumed
presumes
presuming
pretend
pretended
pretending
pretends
pretentious
pretty
prevail
prevalent
prevent
prevented
preventing
prevention
prevents
preview
previewer
previous
previously
price
priced
prices
pricing
pride
priest
priests
primarily
primary
prime
primes
primitive
primitives
prince
principal
principally
principle
principles
print
printed
printer
printers
printing
printout
printouts
prints
prior
priorities
priority
prison
prisoner
prisoners
privacy
private
privately
privilege
privileged
privileges
privileging
pro
probabilities
probability
probable
probably
problem
problems
procedure
procedures
proceed
proceeded
proceeding
proceedings
proceeds
process
processed
processes
processing
processor
processors
proclaim
produce
produced
producer
producers
produces
producing
product
production
productive
productivity
products
profession
professional
professionals
professor
profile
profiles
profit
profitable
profits
profound
programmable
programmer
programmers
progress
progressed
progresses
progressing
prohibit
prohibited
prohibiting
prohibits
project
projected
projecting
projection
projects
proliferation
prolong
prolonged
prolonging
prolongs
prominent
promise
promised
promises
promising
promote
promoted
promotes
promoting
promotion
prompt
prompted
prompting
promptly
prompts
prone
pronoun
pronounce
pronounced
pronounces
pronouncing
pronunciation
proof
proofs
propaganda
proper
properly
properties
property
prophet
proportion
proportional
proportions
proposal
proposals
propose
proposed
proposes
proposing
proposition
proprietary
prose
prosecute
prosecuted
prosecutes
prosecuting
prosecution
prospect
prospective
prospects
prostitute
prostitutes
protect
protected
protecting
protection
protects
protein
protest
protocol
protocols
prototype
proud
prove
proved
proves
provide
provided
provides
providing
proving
provision
provisional
provisions
provocative
provoke
provoked
provokes
provoking
proximity
pseudo
psychological
psychologist
psychologists
psychology
pub
public
publication
publications
publicity
publicly
publish
published
publisher
publishers
publishes
publishing
pudding
pull
pulled
pulling
pulls
pulp
pulse
pulses
pump
pumped
pumping
pumps
pun
punch
punched
punches
punching
punctuation
puncture
punish
punished
punishes
punishing
punishment
puns
punt
punts
pupil
pupils
purchase
purchased
purchases
purchasing
pure
purely
purge
purity
purple
purpose
purposes
pursue
pursued
pursues
pursuing
pursuit
push
pushed
pushes
pushing
put
puts
putt
putted
putting
putts
puzzle
puzzled
puzzles
puzzling
python
qualification
qualifications
qualified
qualifier
qualifiers
qualifies
qualify
qualifying
qualities
quality
quantities
quantity
quantum
quarter
quarters
queen
queens
queries
query
quest
question
questionable
questioned
questioning
questionnaire
questions
queue
queued
queues
quibble
quick
quicker
quickest
quickly
quiet
quieter
quietest
quietly
quit
quite
quits
quitting
quiz
quota
quotas
quotation
quotations
quote
quoted
quotes
quoting
rabbit
rabbits
rabid
race
raced
races
racial
racing
racism
racist
rack
racket
racks
radar
radiation
radical
radically
radio
radios
radius
rag
rage
raid
raids
rail
railroad
rails
railway
rain
rainbow
rained
raining
rains
raise
raised
raises
raising
ram
rampant
ran
random
randomly
rang
range
ranged
ranges
ranging
rank
ranks
rant
ranted
ranting
rants
rape
rapid
rapidly
rare
rarely
rarer
rarest
rash
rat
rate
rated
rates
rather
rating
ratio
rational
rationale
rationally
ratios
rats
rattle
rattled
rattles
rattling
rave
raved
raves
raving
raw
ray
razor
re
reach
reached
reaches
reaching
react
reacted
reacting
reaction
reactionary
reactions
reactor
reacts
read
readable
reader
readers
readership
readily
reading
readings
reads
ready
real
realistic
reality
really
realm
realms
rear
rearrange
rearranged
rearranges
rearranging
reason
reasonable
reasonably
reasoned
reasoning
reasons
reassure
reassured
reassures
reassuring
rebuild
rebuilding
rebuilds
rebuilt
recall
recalled
recalling
recalls
receipt
receive
received
receiver
receives
receiving
recent
recently
reception
recipe
recipes
recipient
recipients
reckless
reckon
reckoned
reckoning
reckons
reclaim
recognition
recollection
recommend
recommendation
recommendations
recommended
recommending
recommends
reconcile
reconsider
record
recorded
recorder
recording
recordings
records
recover
recovered
recovering
recovers
recovery
recreational
recruit
recruited
recruiting
recruitment
recruits
rectangle
rectangular
rectified
rectifies
rectify
rectifying
recursion
recursive
recycle
recycled
recycles
recycling
red
redefine
redefined
redefines
redefining
redirect
reduce
reduced
reduces
reducing
reduction
reductions
redundancy
redundant
refer
reference
referenced
references
referencing
referendum
referred
referring
refers
refine
refined
refines
refining
reflect
reflected
reflecting
reflection
reflects
reflex
reform
reformat
reformed
reforming
reforms
refrain
refresh
refreshed
refreshes
refreshing
refund
refusal
refuse
refused
refuses
refusing
refute
regain
regard
regarded
regarding
regardless
regards
regime
region
regional
regions
register
registered
registering
registers
registration
regret
regrets
regrettably
regretted
regretting
regular
regularly
regulation
regulations
reign
reinstate
reinstated
reinstates
reinstating
reiterate
reject
rejected
rejecting
rejection
rejects
relate
related
relates
relating
relation
relations
relationship
relationships
relative
relatively
relatives
relativity
relax
relaxed
relaxes
relaxing
relay
release
released
releases
releasing
relevance
relevant
reliability
reliable
reliably
relied
relief
relies
relieve
relieved
relieves
relieving
religion
religions
religious
relocation
reluctance
reluctant
reluctantly
rely
relying
remain
remainder
remained
remaining
remains
remark
remarkable
remarkably
remarked
remarking
remarks
remedy
remember
remembered
remembering
remembers
remind
reminded
reminder
reminding
reminds
reminiscent
remote
remotely
removal
remove
removed
removes
removing
rename
renamed
renames
renaming
rend
render
rendered
rendering
renders
rending
rendition
rends
renew
renewed
renewing
renews
rent
repair
repaired
repairing
repairs
repeat
repeatable
repeated
repeatedly
repeating
repeats
repent
repertoire
repetition
repetitive
rephrase
replace
replaced
replacement
replacements
replaces
replacing
replied
replies
reply
replying
report
reported
reporter
reporting
reports
represent
representation
representations
representative
representatives
represented
representing
represents
reproduce
reproduced
reproduces
reproducing
reproduction
repulsive
reputation
request
requested
requesting
requests
require
required
requirement
requirements
requires
requiring
requisite
reread
rereading
rereads
rescue
research
researcher
researchers
resemblance
resemble
resembled
resembles
resembling
resent
reservation
reservations
reserve
reserved
reserves
reserving
reset
resets
resetting
reside
residence
resident
residents
resides
resign
resignation
resigned
resigning
resigns
resist
resistance
resolution
resolve
resolved
resolves
resolving
resort
resorted
resorting
resorts
resource
resourced
resources
resourcing
respect
respectable
respected
respecting
respective
respectively
respects
respond
responded
responding
responds
response
responses
responsibilities
responsibility
responsible
rest
restart
restarted
restarting
restarts
restaurant
restaurants
rested
resting
restore
restored
restores
restoring
restrain
restrained
restraining
restrains
restrict
restricted
restricting
restriction
restrictions
restrictive
restricts
rests
result
resulted
resulting
results
resume
resumed
resumes
resuming
resurrection
retail
retain
retained
retaining
retains
retire
retired
retirement
retires
retiring
retract
retrieval
retrieve
retrieved
retrieves
retrieving
return
returned
returning
returns
reuse
reveal
revealed
revealing
reveals
revelation
revenge
revenue
reverse
reversed
reverses
reversing
revert
review
reviewed
reviewing
reviews
revise
revised
revises
revising
revision
revolt
revolted
revolting
revolts
revolution
revolutionary
reward
rewards
rewrite
rewrites
rewriting
rewritten
rewrote
rhetorical
rhyme
rhythm
ribbon
rice
rich
richer
richest
rid
ridden
ridding
ride
rides
ridiculous
ridiculously
riding
rids
right
rightly
rights
rigid
rigorous
ring
ringed
ringing
rings
riot
rip
ripped
ripping
rips
rise
risen
rises
rising
risk
risked
risking
risks
risky
ritual
rituals
rival
rivals
river
rivers
road
roads
robot
robots
robust
rock
rocket
rocks
rod
rode
role
roles
roll
rolled
rolling
rolls
roman
romance
romantic
roof
room
rooms
root
roots
rope
rose
rot
rotate
rotated
rotates
rotating
rotation
rotten
rough
roughly
round
roundabout
rounded
rounding
rounds
rout
route
routed
routes
routine
routinely
routines
routing
routs
row
rows
royal
royalties
rub
rubber
rubbish
rude
ruin
ruined
ruining
ruins
rule
ruled
ruler
rulers
rules
ruling
run
rung
running
runs
rural
rush
rushed
rushes
rushing
rusty
sabotage
sack
sacked
sacking
sacks
sacred
sacrifice
sacrificed
sacrifices
sacrificing
sad
sadden
saddened
saddening
saddens
sadly
safe
safeguard
safeguards
safely
safer
safest
safety
saga
said
sail
sailed
sailing
sails
saint
sake
salaries
salary
sale
sales
salesman
salt
salvation
same
sample
sampled
samples
sampling
sand
sandwich
sandwiches
sane
sang
sanity
sank
sarcasm
sarcastic
sat
satellite
satellites
satire
satisfaction
satisfactorily
satisfactory
satisfied
satisfies
satisfy
satisfying
sauce
save
saved
saves
saving
savings
saw
say
saying
says
scale
scaled
scales
scaling
scan
scandal
scanned
scanner
scanning
scans
scarce
scarcely
scare
scared
scares
scarf
scaring
scarlet
scatter
scattered
scattering
scatters
scenario
scenarios
scene
scenery
scenes
schedule
scheduled
scheduler
schedules
scheduling
scheme
schemes
scholar
scholars
school
schools
science
sciences
scientific
scientifically
scientist
scientists
scope
score
scored
scores
scoring
scotch
scrap
scrapped
scrapping
scraps
scratch
scratched
scratches
scratching
scream
screamed
screaming
screams
screen
screens
screw
screwed
screwing
screws
script
scripts
scroll
scrolled
scrolling
scrolls
scum
sea
seal
sealed
sealing
seals
search
searched
searches
searching
season
seat
seats
second
secondary
seconded
seconding
secondly
seconds
secret
secretaries
secretary
secretly
secrets
sect
section
sections
sector
sects
secular
secure
security
see
seed
seeing
seek
seeking
seeks
seem
seemed
seeming
seemingly
seems
seen
sees
segment
segments
seldom
select
selected
selecting
selection
selective
selectively
selects
self
selfish
sell
selling
sells
semantic
semantics
seminar
seminars
send
sender
sending
sends
senior
sensation
sense
senses
sensible
sensibly
sensitive
sensitivity
sent
sentence
sentenced
sentences
sentencing
sentient
sentiment
sentimental
sentiments
separate
separated
separately
separates
separating
separation
separator
separators
sequel
sequence
sequences
sequential
serial
series
serious
seriously
seriousness
sermon
servant
servants
serve
served
server
servers
serves
service
services
serving
session
sessions
set
sets
setting
settings
settle
settled
settles
settling
seven
seventh
several
severe
severely
severity
sex
sexes
sexist
sexual
sexuality
sexually
sexy
shade
shades
shadow
shake
shaken
shakes
shaking
shaky
shall
shallow
shame
shape
shaped
shapes
shaping
share
shared
shareholder
shareholders
shares
sharing
sharp
sharply
she
shed
shedding
sheds
sheep
sheer
sheet
sheets
shelf
shell
shells
shelter
shelve
shelves
shift
shifted
shifting
shifts
shine
shined
shines
shining
shiny
ship
shipped
shipping
ships
shirt
shock
shocked
shocking
shocks
shoe
shoes
shone
shook
shoot
shooting
shoots
shop
shopped
shopping
shops
short
shortage
shorten
shortened
shortening
shortens
shorter
shortest
shorthand
shortly
shorts
shot
shots
should
shoulder
shoulders
shout
shouted
shouting
shouts
shove
show
showed
shower
showers
showing
shown
shows
shut
shutdown
shuts
shutting
shy
sic
sick
sicken
sickened
sickening
sickens
side
sided
sides
sideways
siding
sigh
sight
sighted
sighting
sights
sigma
sign
signal
signals
signature
signatures
signed
significance
significant
significantly
signing
signs
silence
silent
silicon
sillier
silliest
silly
silver
similar
similarities
similarity
similarly
simple
simpler
simplest
simplicity
simplified
simplifies
simplify
simplifying
simplistic
simply
simulate
simulated
simulates
simulating
simulation
simultaneous
simultaneously
sin
since
sincere
sincerely
sine
sinful
sing
singer
singers
singing
single
singles
sings
singular
singularly
sinister
sink
sinking
sinks
sins
sir
sister
sit
site
sites
sits
sitting
situate
situated
situates
situating
situation
situations
six
sixteen
sixth
sixties
sixty
size
sized
sizes
sizing
skeleton
sketch
sketches
skill
skilled
skills
skin
skip
skipped
skipping
skips
skirt
skull
sky
slag
slang
slash
slave
slaves
sleep
sleeping
sleeps
slept
slice
sliced
slices
slicing
slid
slide
slides
sliding
slight
slighter
slightest
slightly
slim
slip
slipped
slippery
slipping
slips
slogan
slope
sloppy
slot
slots
slow
slowed
slower
slowest
slowing
slowly
slows
small
smaller
smallest
smallish
smart
smash
smashed
smashes
smashing
smell
smells
smelly
smile
smiled
smiles
smiling
smith
smoke
smoked
smoker
smokers
smokes
smoking
smooth
smoothly
smug
snack
snag
snail
sneak
sneaked
sneaking
sneaks
sneaky
sniff
snobbery
snow
so
soap
sober
social
socialism
socialist
socially
societies
society
sock
socket
sockets
socks
sod
soft
software
soil
solar
sold
soldier
soldiers
sole
solely
soles
solicitor
solicitors
solid
solo
solution
solutions
solve
solved
solves
solving
some
somebody
somehow
someone
someplace
something
sometime
sometimes
somewhat
somewhere
son
song
songs
sons
soon
sooner
soonest
sophisticate
sophisticated
sophisticates
sophisticating
sordid
sore
sorry
sort
sorted
sorting
sorts
sought
soul
souls
sound
sounded
sounding
sounds
soundtrack
soup
source
sources
south
southern
space
spaced
spaces
spacing
span
spare
spares
spatial
speak
speaker
speakers
speaking
speaks
special
specialist
specially
species
specific
specifically
specification
specifications
specified
specifies
specify
specifying
specimen
spectacular
spectrum
speculate
speculation
sped
speech
speeches
speed
speeding
speeds
spell
spelling
spellings
spells
spend
spending
spends
spent
sphere
spies
spigot
spike
spill
spin
spiral
spirit
spirits
spiritual
spit
spite
spits
spitted
spitting
splendid
split
splits
splitting
spoil
spoiling
spoils
spoke
spoken
spokesman
sponsor
sponsored
sponsoring
sponsors
spontaneous
spontaneously
spoof
spool
sport
sports
spot
spots
spotted
spotting
spout
sprang
spray
spread
spreading
spreads
spring
springing
springs
sprung
spur
spurious
spy
squad
square
squared
squares
squaring
squash
squashed
squashes
squashing
squeeze
squeezed
squeezes
squeezing
stability
stable
stack
stacks
staff
stage
stages
stagger
staggered
staggering
staggers
stair
staircase
stairs
stake
stale
stall
stamp
stamped
stamping
stamps
stance
stand
standard
standards
standing
standpoint
stands
star
stare
stared
stares
staring
stark
starred
starring
stars
start
started
starter
starters
starting
startle
startled
startles
startling
starts
starve
starved
starves
starving
state
stated
statement
statements
states
static
stating
station
stationary
stations
statistic
statistical
statistics
status
stay
stayed
staying
stays
steadily
steady
steal
stealing
steals
steam
steel
steep
steer
steered
steering
steers
stem
stems
step
stepped
stepping
steps
stereo
stereotype
stereotypes
sterile
sterling
stick
sticking
sticks
sticky
stiff
still
stimulate
stimulated
stimulates
stimulating
stimulation
stir
stirred
stirring
stirs
stock
stocks
stole
stolen
stomach
stone
stones
stood
stop
stopped
stopping
stops
storage
store
stored
stores
storing
storm
storms
straight
straightforward
strain
strains
strange
strangely
stranger
strangest
strategic
strategies
strategy
straw
stray
stream
streams
street
streets
strength
strengthen
stress
stressed
stresses
stressing
stretch
stretched
stretches
stretching
strict
strictly
strike
strikes
striking
string
stringent
strings
strip
stripped
stripping
strips
strive
stroke
strong
stronger
strongest
strongly
struck
structural
structure
structured
structures
structuring
struggle
struggled
struggles
struggling
stuck
student
students
studied
studies
studio
study
studying
stuff
stuffed
stuffing
stuffs
stumble
stumbled
stumbles
stumbling
stun
stunned
stunning
stuns
stunt
stupid
stupidity
style
styles
subject
subjected
subjecting
subjective
subjects
submission
submit
submits
submitted
submitting
subroutine
subroutines
subscribe
subscription
subsequent
subsequently
subset
subsidiary
substance
substances
substantial
substantially
substitute
substituted
substitutes
substituting
substitution
subtle
subtleties
subtlety
subtly
subway
subways
succeed
succeeded
succeeding
succeeds
success
successful
successfully
succession
successive
successor
such
sudden
suddenly
sue
sued
sues
suffer
suffered
sufferer
sufferers
suffering
suffers
suffice
sufficient
sufficiently
suffix
sugar
suggest
suggested
suggesting
suggestion
suggestions
suggests
suicidal
suicide
suing
suit
suitability
suitable
suitably
suite
suited
suiting
suits
sum
summaries
summary
summed
summer
summing
sums
sun
sundry
sung
sunk
sunlight
sunny
sunrise
sunshine
super
superb
superficial
superficially
superfluous
superior
superiority
supermarket
supernatural
supervise
supervised
supervises
supervising
supervision
supervisions
supervisor
supervisors
supplement
supplementary
supplied
supplier
suppliers
supplies
supply
supplying
support
supported
supporter
supporters
supporting
supports
suppose
supposed
supposedly
supposes
supposing
suppress
suppressed
suppresses
suppressing
suppression
supreme
sure
surely
surface
surfaces
surgery
surname
surplus
surprise
surprised
surprises
surprising
surprisingly
surround
surrounded
surrounding
surroundings
surrounds
survey
surveys
survival
survive
survived
survives
surviving
susceptible
suspect
suspected
suspecting
suspects
suspend
suspended
suspending
suspends
suspension
suspicion
suspicious
suspiciously
sustain
sustained
sustaining
sustains
swallow
swallowed
swallowing
swallows
swam
swamp
swamped
swamping
swamps
swap
swapped
swapping
swaps
swear
swearing
swears
sweat
sweating
sweats
sweep
sweeping
sweeps
sweet
swept
swim
swimming
swims
swing
switch
switched
switches
switching
sword
swore
sworn
swum
symbol
symbolic
symbols
symmetric
symmetry
sympathetic
sympathies
sympathy
symphonies
symphony
symptom
symptoms
syndicate
syndrome
synonym
synonymous
synonyms
syntactic
syntactically
syntax
synthesis
system
systematic
systems
tab
table
tables
tabs
tack
tacked
tacking
tackle
tackled
tackles
tackling
tacks
tactic
tactical
tactics
tactless
tag
tail
tailor
tailored
tailoring
tailors
tails
take
taken
taker
takers
takes
taking
tale
talent
talented
talents
tales
talk
talked
talking
talks
tall
tame
tangent
tank
tanks
tap
tape
tapes
target
targets
task
tasks
taste
tasted
tasteless
tastes
tasting
taught
tax
taxation
taxes
taxi
taxpayer
taxpayers
tea
teach
teacher
teachers
teaches
teaching
team
teams
teapot
tear
teared
tearing
tears
technical
technically
technique
techniques
technological
technology
tedious
teenage
teenager
teenagers
teeth
telephone
telephones
telescope
television
tell
telling
tells
temper
temperature
temperatures
temple
temporarily
temporary
tempt
temptation
tempted
tempting
tempts
ten
tend
tended
tendencies
tendency
tender
tending
tends
tennis
tens
tense
tension
tentative
tentatively
tenth
term
termed
terminal
terminally
terminals
terminate
terminated
terminates
terminating
termination
terminator
terming
terminology
terms
terrible
terribly
terrified
terrifies
terrify
terrifying
territory
terror
terrorism
terrorist
terrorists
terse
test
tested
testing
tests
text
textbook
textbooks
texts
textual
than
thank
thanked
thankful
thankfully
thanking
thanks
that
the
thee
theft
their
theirs
them
theme
themes
themselves
then
theological
theology
theorem
theorems
theoretical
theoretically
theories
theory
therapy
there
thereabouts
thereafter
thereby
therefore
therein
thereof
these
theses
thesis
they
thick
thickness
thief
thieve
thieves
thin
thing
things
think
thinking
thinks
third
thirst
thirty
this
thorough
thoroughfare
thoroughfares
thoroughly
those
thou
though
thought
thoughts
thous
thousand
thousands
thread
threat
threaten
threatened
threatening
threatens
threats
three
threshold
threw
throat
throats
through
throughout
throughput
throw
throwing
thrown
throws
thrust
thrusting
thrusts
thumb
thus
thy
tick
ticket
tickets
tidied
tidies
tidy
tidying
tie
tied
ties
tiger
tight
tightly
tile
tiles
till
time
timed
timer
times
timescale
timetable
timing
tin
tins
tiny
tip
tips
tiresome
title
titles
to
toad
toast
tobacco
today
toe
toes
together
toggle
toilet
toilets
token
tokens
told
tolerance
tolerant
tolerate
tolerated
tolerates
tolerating
toll
tomato
tomatoes
tome
tomorrow
ton
tone
tones
tongue
tonight
tons
too
took
tool
tools
tooth
top
topic
topical
topics
tops
tore
torn
torture
toss
total
totally
touch
touched
touches
touching
tough
tour
tourist
tourists
toward
towards
tower
towers
town
towns
toy
toys
trace
traced
traces
tracing
track
tracked
tracking
tracks
trade
traded
trades
trading
tradition
traditional
traditionally
traditions
traffic
tragedy
tragic
trail
trailed
trailing
trails
train
trained
training
trains
transaction
transactions
transcript
transfer
transferred
transferring
transfers
transform
transformation
transformed
transforming
transforms
transient
transit
transition
translate
translated
translates
translating
translation
translations
translator
transmission
transmissions
transmit
transmits
transmitted
transmitter
transmitters
transmitting
transparent
transport
transported
transporting
transports
trap
trapped
trapping
traps
trash
trashcan
travel
travels
tray
tread
treasure
treat
treated
treating
treatment
treats
treaty
tree
trees
trek
tremendous
tremendously
trend
trends
trendy
trial
trials
triangle
triangles
tribe
tribes
trick
tricks
tricky
tried
tries
trifle
trigger
triggered
triggering
triggers
trilogy
trinity
trip
triple
tripos
trips
triumph
trivia
trivial
trivially
trolley
troop
troops
trouble
troubles
trouser
trousers
truck
trucks
true
truly
trumpet
truncate
truncated
truncates
truncating
trunk
trunks
trust
trusted
trusting
trusts
trusty
truth
truths
try
trying
tube
tubes
tune
tuned
tunes
tuning
tunnel
tunnels
turn
turned
turning
turnround
turns
turntable
tutor
tutorial
twelve
twentieth
twenty
twice
twin
twins
twist
twisted
twisting
twists
two
tying
type
typed
types
typeset
typesets
typesetting
typewriter
typical
typically
typing
ugh
ugly
ultimate
ultimately
umbrella
unable
unacceptable
unaffected
unambiguous
unattended
unavailable
unavoidable
unaware
unbalanced
unbearable
unbelievable
unbelievably
unbiased
uncertain
uncertainty
unchanged
uncle
unclear
uncomfortable
uncommon
unconnected
unconscious
unconvincing
undefined
under
underestimate
undergo
undergoes
undergoing
undergone
undergraduate
undergraduates
underground
undergrounds
underlain
underlay
underlie
underlies
underline
underlined
underlines
underlining
underlying
underneath
understand
understandable
understanding
understands
understood
undertake
undertaken
undertakes
undertaking
undertook
underwent
undesirable
undid
undo
undocumented
undoes
undoing
undone
undoubtedly
unduly
uneasy
unemployed
unemployment
unexpected
unexpectedly
unexplained
unfair
unfamiliar
unfinished
unfortunate
unfortunately
unfounded
unfriendly
unhappy
unhealthy
unhelpful
unified
unifies
uniform
uniformly
unify
unifying
unimportant
uninteresting
union
unions
unique
uniquely
unit
unite
united
unites
uniting
units
unity
universal
universally
universe
universities
university
unjustified
unknown
unless
unlike
unlikely
unlimited
unload
unlock
unlocked
unlocking
unlocks
unlucky
unnatural
unnecessarily
unnecessary
unobtainable
unofficial
unpleasant
unpopular
unpredictable
unread
unreadable
unrealistic
unreasonable
unrelated
unreliable
unsafe
unsatisfactory
unseen
unset
unsolicited
unsound
unspecified
unstable
unsuccessful
unsuitable
unsupported
unsure
unsuspecting
untidy
until
unto
untrue
unusable
unused
unusual
unusually
unwanted
unwelcome
unwilling
unwise
unworkable
up
upbringing
update
updated
updates
updating
upgrade
upgraded
upgrades
upgrading
upon
upper
upright
ups
upset
upsets
upsetting
upside
upstairs
upward
upwards
urban
urge
urged
urgency
urgent
urgently
urges
urging
us
usable
usage
use
used
useful
usefully
usefulness
useless
user
users
uses
using
usual
usually
utilities
utility
utter
utterly
vacancies
vacancy
vacation
vacations
vacuum
vague
vaguely
vain
valid
validity
valley
valuable
value
valued
values
valuing
valve
valves
van
vandalism
vanish
vanished
vanishes
vanishing
vans
variable
variables
variance
variant
variants
variation
variations
varied
varies
varieties
variety
various
vary
varying
vast
vastly
vat
vector
vectors
vegetable
vegetables
vegetarian
vehicle
vehicles
vein
velocity
vend
vended
vending
vendor
vends
venture
venue
venues
verb
verbal
verbally
verbatim
verbose
verbs
verdict
verification
verified
verifies
verify
verifying
versatile
verse
verses
version
versions
versus
vertical
vertically
very
vessel
vet
via
viable
vicar
vice
vicinity
vicious
victim
victims
victory
video
view
viewed
viewer
viewing
viewpoint
viewpoints
views
vigorously
vile
village
villages
vintage
vinyl
violate
violation
violence
violent
violently
violin
virgin
virtual
virtually
virtue
virtues
virus
viruses
visible
vision
visit
visited
visiting
visitor
visitors
visits
visual
visually
vital
vocabulary
vocal
voice
voices
void
voltage
volume
volumes
voluntarily
voluntary
volunteer
volunteered
volunteering
volunteers
vomit
vote
voted
voter
voters
votes
voting
vouch
vowel
vulnerable
wade
waded
wades
wading
waffle
wage
wages
wait
waited
waiting
waits
wake
waked
wakes
waking
walk
walked
walking
walks
wall
wallet
walls
wander
wandered
wandering
wanders
want
wanted
wanting
wants
war
ward
warehouse
warm
warmed
warming
warms
warn
warned
warning
warnings
warns
warp
warped
warping
warps
warrant
warranty
wars
wartime
wary
was
wash
washed
washes
washing
waste
wasted
wasteful
wastes
wasting
watch
watched
watches
watching
water
waters
wave
waved
waves
waving
way
ways
we
weak
weakness
weaknesses
wealth
wealthy
weapon
weapons
wear
wearing
wears
weary
weasel
weasels
weather
wed
wedded
wedding
weds
wee
week
weekday
weekend
weekends
weekly
weeks
weigh
weight
weird
welcome
welcomed
welcomes
welcoming
welfare
well
went
were
west
western
wet
wets
wetting
whale
whales
what
whatever
whatsoever
wheel
wheels
when
whence
whenever
where
whereas
whereby
whereupon
wherever
whether
which
whichever
while
whilst
whim
whistle
whistles
white
whites
who
whoever
whole
wholeheartedly
wholly
whom
whoop
whoops
whose
why
wicked
wide
widely
wider
widespread
widest
width
wife
wild
wildly
will
willed
willing
willingly
wills
win
wind
winded
winding
window
windowing
windows
winds
wine
wines
wing
wings
winner
winners
winning
wins
winter
wipe
wiped
wipes
wiping
wire
wired
wires
wiring
wisdom
wise
wiser
wisest
wish
wished
wishes
wishing
wit
witch
with
withdraw
withdrawal
withdrawing
withdrawn
withdraws
withdrew
within
without
witness
witnessed
witnesses
witnessing
witty
wive
wives
wizard
woke
woken
wolf
woman
wombat
women
won
wonder
wondered
wonderful
wonderfully
wondering
wonders
wondrous
wont
wood
wooden
woods
word
worded
wording
words
wore
work
workable
worked
worker
workers
working
workings
workload
works
workshop
workstation
workstations
world
worlds
worldwide
worm
worms
worn
worried
worries
worry
worrying
worse
worship
worst
worth
worthless
worthwhile
worthy
would
wound
wow
wrap
wrapped
wrapper
wrappers
wrapping
wraps
wrath
wreck
wrecked
wrecker
wrecking
wrecks
wren
wretched
wrist
write
writer
writers
writes
writing
writings
written
wrong
wrongly
wrongs
wrote
yard
yards
yawn
year
yearly
years
yellow
yes
yesterday
yet
yeti
yield
yields
you
young
younger
youngest
your
yours
yourself
yourselves
youth
zero
zeros
zone
zones
zoom

GUI tree

2009-03-29T19:34:00.000-07:00

/*
* Attribute.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

import java.io.*;

abstract class Attribute{
/* the name of the attributes */
String name;
/* the database of the attributes */
Database db;
/* attribute index in the database */
int index;
/* the lastbestscore of this attribute */
double lastbestscore;

public Object Value(Obj o) {
return o.attributesvalues.elementAt(index);
}
abstract void SetAttValue(Obj o,Object s);
public String toString() {
return name;
}
abstract String describe();
abstract String describeBestTest();
abstract int ReadAttValue(Obj o,StreamTokenizer stt);
// compute the best score we can obtain with this attribute
abstract double bestscore(ObjectSet os, SymbAtt goal);
// effectively compute the partition resulting from this best score
abstract Partition bestpartition(ObjectSet os, SymbAtt goal);
}
----------------------

/*
* BuildDt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

import java.util.*;
import java.net.*;

/**
* examples:
* java buildDt database/omib.db security 700
* java buildDt database/iris.db class 100
* java buildDt database/color.db color 1500
*/
public class BuildDt {
public static void main(String args[]){
if (args.length<3) {
System.out.println("usage : database goal learning_set_size [entthres stopthres]");
return;
}
/* creation of a database */
Database db = new Database();

System.out.println("Database loading:");
try {
db.loadDb(new URL(args[0]));
} catch (Exception e) {
System.out.println("database file not found");
return;
}
if (db.objects.size==0) {
System.out.println("no object");
return;
}
ObjectSet ls=db.objects.selectRandom(Integer.parseInt(args[2]));
ObjectSet ts=db.objects.selectNotIn(ls);

// select the goal attribute
Attribute goal=db.findAttribute(args[1]);
if (goal==null) {
System.out.println("goal attribute not found");
return;
}

// select all candidate attributes
Vector ca=db.getCandidateAttributes(args[1]);
if (ca.size()==0) {
System.out.println("no candidate attributes");
return;
}

double entthres=0.0;
double stopthres=2.0;
if (args.length>=4) {
entthres=(new Double(args[3])).doubleValue();
}
if (args.length>=5) {
stopthres=(new Double(args[4])).doubleValue();
}
DecisionTree dt=new DecisionTree(db, ls, ca, (SymbAtt)goal,entthres,stopthres);
dt.buildDt();
dt.printDt();
System.out.println("ls errors : " + 100.0*dt.testDt(ls) + "%");
System.out.println("ts errors : " + 100.0*dt.testDt(ts) + "%");
}
}

---------------------------

/*
* 1.1 version.
*/

import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;

/*
* This displays a framed area. When the user clicks within
* the area, this program displays a dot and a string indicating
* the coordinates where the click occurred.
*/

public class CoordinatesDemo extends Applet {
FramedArea framedArea;
Label label;

public void init() {
GridBagLayout gridBag = new GridBagLayout();
GridBagConstraints c = new GridBagConstraints();

setLayout(gridBag);

framedArea = new FramedArea(this);
c.fill = GridBagConstraints.BOTH;
c.weighty = 1.0;
c.gridwidth = GridBagConstraints.REMAINDER; //end row
gridBag.setConstraints(framedArea, c);
add(framedArea);

label = new Label("Click within the framed area.");
c.fill = GridBagConstraints.HORIZONTAL;
c.weightx = 1.0;
c.weighty = 0.0;
gridBag.setConstraints(label, c);
add(label);
}

public void updateLabel(Point point) {
label.setText("Click occurred at coordinate ("
+ point.x + ", " + point.y + ").");
}
}

/* This class exists solely to put a frame around the coordinate area. */
class FramedArea extends Panel {
public FramedArea(CoordinatesDemo controller) {
super();

//Set layout to one that makes its contents as big as possible.
setLayout(new GridLayout(1,0));

add(new CoordinateArea(controller));
}

public Insets getInsets() {
return new Insets(4,4,5,5);
}

public void paint(Graphics g) {
Dimension d = getSize();
Color bg = getBackground();

g.setColor(bg);
g.draw3DRect(0, 0, d.width - 1, d.height - 1, true);
g.draw3DRect(3, 3, d.width - 7, d.height - 7, false);
}
}

class CoordinateArea extends Canvas {
Point point = null;
CoordinatesDemo controller;

public CoordinateArea(CoordinatesDemo controller) {
super();
this.controller = controller;

addMouseListener(new MouseAdapter() {
public void mousePressed(MouseEvent e) {
int x = e.getX();
int y = e.getY();
if (point == null) {
point = new Point(x, y);
} else {
point.x = x;
point.y = y;
}
repaint();
}
});
}

public void paint(Graphics g) {
//If user has chosen a point, paint a tiny rectangle on top.
if (point != null) {
controller.updateLabel(point);
g.fillRect(point.x - 1, point.y - 1, 2, 2);
}
}
}
-----------------------------------------

/*
* Database.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

import java.util.*;
import java.io.*;
import java.net.*;

public class Database{
/* the name of the database */
String name;
/* the filename from which the database has been loaded */
String filename;
/* the set of objects */
ObjectSet objects=new ObjectSet();
/* the vector of atttributes */
Vector attributes=new Vector();

/* method to add an object */
public int addObjToDb(Obj o) {
objects.addElement(o);
return objects.size-1;
}

/* method to add an attribute */
public int addAttToDb(Attribute att){
attributes.addElement(att);
return attributes.size()-1;
}

/* a short description of the database */
public String toString(){
StringBuffer s=new StringBuffer();
s.append(name);
s.append(" o(");
s.append(objects.size);
s.append(") a(");
s.append(attributes.size());
s.append(")");
return s.toString();
}

/* to "pretty" print the content of the database */
public void printDb() {
System.out.println(toString());
System.out.print("Object ");

for (int i=0;
ii++) {
System.out.print(((Attribute)attributes.
elementAt(i)).
toString() + " ");
}

System.out.println("");
for (int i=0; i Obj o=(Obj)objects.elementAt(i);
System.out.print(o.toString() + " ");
for (int j=0; j System.out.print(o.attributesvalues.elementAt(j).toString());
System.out.print(" ");
}
System.out.println("");
}
}

/* utilities /
private static void skipBlankLines(StreamTokenizer stt) throws IOException {
while (stt.ttype==stt.TT_EOL)
stt.nextToken();
}

/ loading of a database from a file /
/ return 1 if there is an error, 0 otherwise /
public int loadDb (URL u) {
boolean objectname=false;
int objectnameindex=0;
filename=u.toString();
try {
// URL u=new URL(fn);
URLConnection urlConnection=u.openConnection();
urlConnection.connect();

InputStream in=urlConnection.getInputStream();
BufferedReader r=new BufferedReader(new InputStreamReader(in));
StreamTokenizer stt=new StreamTokenizer(r);
/ some streamtokenizer inititialisations/
stt.lowerCaseMode(false);
stt.parseNumbers();
stt.eolIsSignificant(true);
stt.commentChar(';');
stt.wordChars('$','$');
stt.wordChars('_','_');
/ file reading */
stt.nextToken();
skipBlankLines(stt);

/**************************
* read the database name *
/
if (stt.ttype==stt.TT_WORD)
name=stt.sval;
else {
System.out.println("the database name must be a symbol");
return 1;
}
stt.nextToken();
skipBlankLines(stt);

/*****
* read attributes declaration *
*****/
int nreadvalue=0;
int natt=0;
while (stt.ttype!=stt.TT_EOL) {
String attname;
String atttype;
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
attname=stt.sval;
stt.nextToken();
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
atttype=stt.sval;
if (atttype.equals("name") || atttype.equals("NAME")) {
if (!objectname) {
objectname=true;
objectnameindex=nreadvalue;
} else {
System.out.println("error in attribute declaration");
return 1;
}
} else {
if (atttype.equals("symbolic") || atttype.equals("SYMBOLIC"))
new SymbAtt(attname,this);
else if (atttype.equals("numerical") || atttype.equals("NUMERICAL"))
new NumAtt(attname,this);
else {
System.out.println("not recognised attribute type");
return 1;
}
natt++;
}
nreadvalue++;
stt.nextToken();
}
System.out.println("" + natt + " attributes have been read");
System.out.println(attributes.toString());

/
* read objects definitions *
**************************/

int exactnatt=natt;
int nobject=1;
while(stt.ttype!=stt.TT_EOF) {
skipBlankLines(stt);
/* number of readed values/
nreadvalue=0;
/ number of readed attributes (as nreadvalue but
without the object name) /
natt=0;
Obj o;
if (objectname)
o=new Obj("",this);
else
o=new Obj("O" + nobject,this);
nobject++;

/ read attributes values /
while(stt.ttype!=stt.TT_EOL && stt.ttype!=stt.TT_EOF) {
if (objectname==true &&
objectnameindex==nreadvalue &&
nreadvalue==objectnameindex) {
if (stt.ttype==stt.TT_WORD) {
o.name=stt.sval;
nreadvalue++;
} else {
System.out.println("Object name must be a string");
return 1;
}
} else {
if (((Attribute)attributes.elementAt(natt)).ReadAttValue(o,stt)
==1) {
System.out.println("objet " + nobject + " value " + nreadvalue);
return 1;
}
natt++;
nreadvalue++;
}
stt.nextToken();
}
if (natt System.out.println("Attribute values are missing");
return 1;
}
skipBlankLines(stt);
}
System.out.println("" + (nobject-1) + " objects have been read");
// System.out.println(objects.toString());
in.close();
}
catch (Exception e){
System.err.println(e);
}
return 0;
}

/ a method to find an attribute by its name /
public Attribute findAttribute(String name) {
int as=attributes.size();
for (int i=0; i Attribute a=(Attribute)attributes.elementAt(i);
if (name.equals(a.name))
return a;
}
return null;
}

/ a method to find all attributes except one /
public Vector getCandidateAttributes(String goal) {
int as=attributes.size();
Attribute a;
Vector result=new Vector();
for (int i=0; i a=(Attribute)attributes.elementAt(i);
if (!goal.equals(a.name)) {
result.addElement(a);
}
}
return result;
}

/ a method to find a object by its name /
public Obj findObject(String name) {
int os=objects.size;
for (int i=0; i Obj o=(Obj)objects.elementAt(i);
if (name.equals(o.name))
return o;
}
return null;
}
}
----------------------------

/
* DbReader.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.io.;

public class DbReader {
private static void skipBlankLines(StreamTokenizer stt) throws IOException {
while (stt.ttype==stt.TT_EOL)
stt.nextToken();
}
/* return 1 if there is an error, 0 otherwise /
public static int loadDb (Database db, String filename) {
boolean objectname=false;
int objectnameindex=0;
try {
File f=new File(filename);
Reader in=new FileReader(f);
StreamTokenizer stt=new StreamTokenizer(in);
/ some streamtokenizer initialisations/
stt.lowerCaseMode(true);
stt.parseNumbers();
stt.eolIsSignificant(true);
stt.commentChar(';');
/ file reading */
stt.nextToken();
skipBlankLines(stt);

/*******************************
* read attributes declaration *
*****/
int nreadvalue=0;
int natt=0;
while (stt.ttype!=stt.TT_EOL) {
String attname;
String atttype;
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
attname=stt.sval;
stt.nextToken();
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
atttype=stt.sval;
if (attname.equals("object")) {
if (!objectname) {
objectname=true;
objectnameindex=nreadvalue;
} else {
System.out.println("error in attribute declaration");
return 1;
}
} else {
if (atttype.equals("symbolic"))
new SymbAtt(attname,db);
else if (atttype.equals("numerical"))
new NumAtt(attname,db);
else {
System.out.println("not recognised attribute type");
return 1;
}
natt++;
}
nreadvalue++;
stt.nextToken();
}
System.out.println("" + natt + " attributes have been read");
System.out.println(db.attributes.toString());

/
* read objects definitions *
**************************/

int exactnatt=natt;
int nobject=1;
while(stt.ttype!=stt.TT_EOF) {
skipBlankLines(stt);
/* number of readed values/
nreadvalue=0;
/ number of readed attributes (as nreadvalue but
without the object name) /
natt=0;
Obj o;
if (objectname)
o=new Obj("",db);
else
o=new Obj("O" + nobject,db);
nobject++;

/ read attributes values /
while(stt.ttype!=stt.TT_EOL && stt.ttype!=stt.TT_EOF) {
if (objectname==true &&
objectnameindex==nreadvalue &&
nreadvalue==objectnameindex) {
if (stt.ttype==stt.TT_WORD) {
o.name=stt.sval;
nreadvalue++;
} else {
System.out.println("Object name must be a string");
return 1;
}
} else {
if (((Attribute)db.attributes.elementAt(natt)).ReadAttValue(o,stt)
==1) {
return 1;
}
natt++;
nreadvalue++;
}
stt.nextToken();
}
if (natt System.out.println("Attribute values are missing");
return 1;
}
skipBlankLines(stt);
}
System.out.println("" + nobject + " objects have been read");
System.out.println(db.objects.toString());
in.close();
}
catch (IOException e){
System.err.println(e);
}
return 0;
}
}

----------------------------------

/
* DecisionTree.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

public class DecisionTree {
/* problem definition /
Database db;
ObjectSet LearningSet;
Vector CandAttributes;
SymbAtt goal;

/ parameter /
double EntropyThres=0;
double ScoreThres=0;

/ root node /
DtNode root;

/ stack of open node /
Stack openNodes=new Stack();

/ Ordered attributes list for the current node */
Vector CurrentNodeAtt;

/**
* create a trivial tree with the default parameters values
*/
DecisionTree(Database d, ObjectSet ls, Vector CandAtt, SymbAtt g) {
db=d;
LearningSet=ls;
CandAttributes=CandAtt;
goal=g;
DtNode.nbnodes=0;
root=new DtNode(LearningSet, g);
root.graphnode=new WNode("open", null, null, null, null, 0, 0, 0, root);
root.graphnode.selected=true;
// openNodes.push(root);
}

/**
* create a trivial tree with the user's parameter values
*/
DecisionTree(Database d, ObjectSet ls, Vector CandAtt, SymbAtt g,
double et, double st) {
EntropyThres=et;
ScoreThres=st;
db=d;
LearningSet=ls;
CandAttributes=CandAtt;
goal=g;
DtNode.nbnodes=0;
root=new DtNode(LearningSet, g);
root.graphnode=new WNode("open", null, null, null, null, 0, 0, 0, root);
root.graphnode.selected=true;
// openNodes.push(root);
}

/**
* build completely the decision tree
*/
public void buildDt() {
// we search this tree for all the remaining open nodes
getOpenNodes();
// then we build the tree
while(!openNodes.empty()) {
expandTopNode();
}
}

/**
* expand the node on the top of stack always with the best choice
*/
public void expandTopNode() {
DtNode topnode=(DtNode)openNodes.pop();
scanNode(topnode);
Vector result=topnode.split(CurrentNodeAtt,0,goal);
//-- we put the successors on the top of the stack (in reverse order)
if (result!=null) {
for (int i=result.size()-1; i>=0; i--) {
openNodes.push(result.elementAt(i));
}
}
}

/**
* scan the attributes for the top node
/
public Vector scanNode(DtNode topnode) {
CurrentNodeAtt=topnode.scanAttributes(CandAttributes, goal, EntropyThres, ScoreThres);
/ build a vector of textual description of candidate tests */
Vector result=new Vector();
for (int i=0; i result.addElement(((Attribute)CurrentNodeAtt.elementAt(i)).describeBestTest());
result.addElement(CurrentNodeAtt.lastElement());
return result;
}

/**
* split the top node according to the choice in the CurrentNodeAtt
* Vector
*/
public DtNode splitNode(DtNode topnode, int choice) {
Vector result=topnode.split(CurrentNodeAtt,choice,goal);
if (result!=null) {
// we return the first successor
return (DtNode)result.elementAt(0);
} else {
// otherwise, we return the leftmost open node
return getLeftMostOpenNode();
}
}

/**
* get all the open nodes of the tree (needed because the user can
* now open the node by himself)
*/
public void getOpenNodes() {
openNodes.removeAllElements();
root.getOpenNodes(openNodes);
}

/**
* look for the leftmost open node in the tree
* (this is used after splitting to find the next node to split)
*/

public DtNode getLeftMostOpenNode() {
return root.getLeftMostOpenNode();
}

/**
* get a description of the current open node
*/
public String getNodeDescription(DtNode node) {
return node.getNodeDescription(goal);
}

/**
* propagate this object across the tree and get the associated class
*/
public String Propagate(Obj o) {
return root.getClass(o);
}

/**
* test the dt on an objectset
/
public double testDt(ObjectSet ts) {
String treeclass, trueclass;
int nberrors=0;
for (int i=0; i treeclass=Propagate(ts.elementAt(i));
trueclass=(String)goal.Value(ts.elementAt(i));
if (!trueclass.equals(treeclass))
nberrors++;
}
System.out.println("nb of errors : " + nberrors + " out of " + ts.size);
return 1.0nberrors/ts.size;
}

/**
* test the tree using cross-validation
* argument - the number of subsets into which
* the data base must be divided
/
public double testDtCrossvalidation(int tssize) {
DecisionTree dt;
int n=LearningSet.size/tssize;
Vector tsvector=new Vector();
ObjectSet remainingobjects=LearningSet;
System.out.println("");
System.out.println("Cross validation : " + n + ", LS : "
+ (LearningSet.size-tssize) + " , TS: " +
tssize);
System.out.println("");

// we construct the set of test sets
for (int i=0; i ObjectSet os=remainingobjects.selectRandom(tssize);
tsvector.addElement(os);
remainingobjects=remainingobjects.selectNotIn(os);
}

// we construct the trees
double result=0;
for (int i=0; i System.out.println("");
System.out.println("Tree number " + (i+1));
System.out.println("");
ObjectSet ts=(ObjectSet)tsvector.elementAt(i);
dt=new DecisionTree(db, LearningSet.selectNotIn(ts),
CandAttributes, goal,
EntropyThres, ScoreThres);
dt.buildDt();
result+=dt.testDt(ts);
}

// we return the average
return result/n;
}

public void printDt() {
System.out.println(root.printNode(0));
}
}
----------------------------

/
* DecisionTreeApplet.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.applet.Applet;
import java.awt.;
import java.awt.event.;
import java.util.;
import java.net.;
import java.io.;

/**
* Displays the tree building process
/
public class DecisionTreeApplet extends Applet
implements ActionListener,ItemListener, Runnable
{
/ Following are workarounds for font size calculations, as Netscape
* reports unappealing font height/ascents on varying platforms. /
static final int FIXED_FONT_HEIGHT = 10;
static final int FIXED_FONT_ASCENT = 3;

boolean running;
Thread t;
WNode root;
WalTreeCanvas tc;
SimpleNodeDrawer snd;
DetailedNodeDrawer dnd;

/ decision tree data */
Database db;
DecisionTree CurrentDt;
DtNode CurrentDtn;
ObjectSet ls;
ObjectSet ts;

Button btn_scan; // scan the attribute
Button btn_split; // split one node (if it is still possible)
Button btn_build; // build the tree
Button btn_refresh; // refresh the graph (actually not useful)
Label lbl_zoom=new Label("Zoom", Label.RIGHT);
Button btn_zoominc;
Button btn_zoomdec;
Choice AttChoice; // selection list for the best attribute
String messagechoice="Click 'Scan Attributes' to see the choices";

TextField tf_opennode=new TextField(); // description of the current node

// input parameters
Panel top=new Panel();
Label lbl_database=new Label("Database url : ", Label.RIGHT);
TextField tf_database= new TextField(65); // to enter the file name
Button btn_loaddb=new Button("Load Database");
// to restart with a new database
Label lbl_goal=new Label("Goal Attribute : ", Label.RIGHT); // goal attribute
Choice GoalAttributeChoice; // a choice list for the goal attribute (only the symbolic)
// (at the same time, it displays all the attribute)
Label lbl_candatt=new Label("Candidate attributes : ");
java.awt.List lst_candatt; // a selection list for the candidate attributes

// learning set selection
Label lbl_learningset=new Label("Learning set :", Label.RIGHT);
Label lbl_lssize=new Label("size :", Label.RIGHT);
TextField tf_lssize=new TextField(5);
Label lbl_lsmode=new Label("Selection mode:", Label.RIGHT);
Choice SelectionChoiceLs;

// tree parameters
Label lbl_entthres=new Label("Entropy Threshold : ", Label.RIGHT);
TextField tf_entthres=new TextField(4);
Label lbl_scorethres=new Label("Inf X LS size Threshold : ", Label.RIGHT);
TextField tf_scorethres= new TextField(4);
double default_scorethres=0.0;
double default_entthres=0.0;

// start tree button
Button btn_starttree=new Button("New Tree");

// test parameters
Label lbl_testset=new Label("Test set :", Label.RIGHT);
Label lbl_tssize=new Label("size :", Label.RIGHT);
TextField tf_tssize=new TextField(5);
Label lbl_tsmode=new Label("Selection mode:", Label.RIGHT);
Choice SelectionChoiceTs;
TextField tf_testresult=new TextField(20);
Button btn_testtree;
Button btn_crossvalidation;

// panels
Panel t_p0=new Panel(new GridLayout(3,1,0,0));
Panel t_loaddb=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p1=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p2=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p3=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p4=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p5=new Panel(new BorderLayout());

Panel b_p1=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p2=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p3=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p4=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel bottom=new Panel();
ScrollPane sp=new ScrollPane();
CheckboxGroup treedrawer=new CheckboxGroup();
Checkbox chk_simple=new Checkbox("Simple",treedrawer,true);
Checkbox chk_detailed=new Checkbox("Detailed",treedrawer,false);

/**
* Initialize the applet.
/
public void init ()
{
super.init();
String str;

setLayout(new BorderLayout());

t_loaddb.add(lbl_database);
t_loaddb.add(tf_database);
t_loaddb.add(btn_loaddb);
t_p1.add(lbl_goal);
t_p1.add(GoalAttributeChoice=new Choice());
t_p2.add(lbl_entthres);
t_p2.add(tf_entthres);
t_p3.add(lbl_scorethres);
t_p3.add(tf_scorethres);
t_p4.add(lbl_learningset);
t_p4.add(lbl_lssize);
t_p4.add(tf_lssize);
t_p4.add(lbl_lsmode);
t_p4.add(SelectionChoiceLs=new Choice());
t_p4.add(btn_starttree);
SelectionChoiceLs.add("Random");
SelectionChoiceLs.add("First");
SelectionChoiceLs.add("Last");
t_p5.add(lbl_candatt,"North");
t_p5.add(lst_candatt=new java.awt.List(5,true),"Center");
t_p0.add(t_p1) ; t_p0.add(t_p2) ; t_p0.add(t_p3);
top.setLayout(new BorderLayout());
top.add(t_loaddb, "North");
top.add(t_p0, "West");
top.add(t_p5,"Center");
top.add(t_p4,"South");

// center : the tree canvas
sp.add(tc=new WalTreeCanvas());

// bottom : control of the building process
bottom.setLayout(new GridLayout(4,1,0,0));
b_p1.add(tf_opennode=new TextField(100));
tf_opennode.setEditable(false);
bottom.add(b_p1);
b_p3.add(AttChoice=new Choice());
bottom.add(b_p3);
b_p2.add(btn_scan=new Button("Scan attributes"));
b_p2.add(btn_split=new Button("Split"));
b_p2.add(btn_build=new Button("Build"));
b_p2.add(chk_simple);
b_p2.add(chk_detailed);
b_p2.add(btn_refresh=new Button("Refresh"));
b_p2.add(lbl_zoom);
b_p2.add(btn_zoominc=new Button("+"));
b_p2.add(btn_zoomdec=new Button("-"));
bottom.add(b_p2);

b_p4.add(lbl_testset);
b_p4.add(lbl_tssize);
b_p4.add(tf_tssize);
b_p4.add(lbl_tsmode);
b_p4.add(SelectionChoiceTs=new Choice());
SelectionChoiceTs.add("Not in ls");
SelectionChoiceTs.add("Random");
SelectionChoiceTs.add("First");
SelectionChoiceTs.add("Last");
SelectionChoiceTs.add("Learning set");
b_p4.add(btn_testtree=new Button("Test tree"));
b_p4.add(btn_crossvalidation=new Button("Cross Validation"));
b_p4.add(tf_testresult);
tf_testresult.setEditable(false);
bottom.add(b_p4);

add(top, "North");
add(bottom, "South");
add(sp, "Center");

snd=new SimpleNodeDrawer(tc);
dnd=new DetailedNodeDrawer(tc);
tc.nd=snd;

tc.setParentDistance(30);

// load the database
if (getParameter("DBFILE")!=null) {
URL u;
try {
u=new URL(getDocumentBase(), getParameter("DBFILE"));
initDb(u);
} catch (MalformedURLException e) {
System.out.println("-- database file not found");
showStatus("Bad url");
}

}

// different actions binding
// buttons
btn_split.addActionListener(this);
btn_refresh.addActionListener(this);
btn_scan.addActionListener(this);
btn_starttree.addActionListener(this);
btn_testtree.addActionListener(this);
btn_crossvalidation.addActionListener(this);
btn_build.addActionListener(this);
btn_loaddb.addActionListener(this);
btn_zoominc.addActionListener(this);
btn_zoomdec.addActionListener(this);
// check button
chk_simple.addItemListener(this);
chk_detailed.addItemListener(this);
// selection list
SelectionChoiceTs.addItemListener(this);
// mouse
MyMouseListener ml=new MyMouseListener();
tc.addMouseListener(ml);
}

public void loadDb() {
URL u;
try {
u=new URL(tf_database.getText());
initDb(u);
tc.setTree(root);
tc.repaint();
} catch (MalformedURLException e) {
System.out.println("-- database file not found");
showStatus("Bad url");
}
}

public void initDb(URL u) {
db = new Database();
System.out.println("Database loading:");
showStatus("Loading database");

if (db.loadDb(u)==1) {
showStatus("Loading failed : bad file format");
return;
}

tf_database.setText(u.toString());

if (db.objects.size==0) {
System.out.println("no object");
}

//-- fill candidate attribute selection list
lst_candatt.removeAll();
GoalAttributeChoice.removeAll();

int last_symb=0;
for (int i=0; i Attribute att=(Attribute)db.attributes.elementAt(i);
lst_candatt.add(att.describe());
lst_candatt.select(i);
if (att instanceof SymbAtt) {
GoalAttributeChoice.add(att.toString());
last_symb=i;
}
}
GoalAttributeChoice.select(GoalAttributeChoice.getItemCount()-1);
lst_candatt.deselect(last_symb);

//-- initialise score and entropy threshold
tf_entthres.setText("" + default_entthres);
tf_scorethres.setText("" + default_scorethres);

//-- initialise ls size and type
tf_lssize.setText("" + (int)(2db.objects.size/3));
SelectionChoiceLs.select(0);
tf_tssize.setText("" + (int)(db.objects.size/3));
SelectionChoiceTs.select(0);
AttChoice.add(messagechoice);
AttChoice.select(0);

//-- initialise the tree
root=null;

//-- garbage collecting after this (to remove the previous database)
System.gc();

showStatus("done");
setComment("");
}

public void NewTree() {
//-- learning set selection
int lssize=GetLsSize();
int lsmode=GetLsMode();
if (lsmode==0)
ls=db.objects.selectRandom(lssize);
else if (lsmode==1)
ls=db.objects.selectFirst(lssize);
else if (lsmode==2)
ls=db.objects.selectLast(lssize);

//-- we build a trivial tree
CurrentDt=new DecisionTree(db, ls, GetCandAtt(), GetGoalAttribute(),
GetEntThres(), GetScoreThres());
CurrentDtn=CurrentDt.root;
root=CurrentDt.root.graphnode;

//-- we initialise the graphical interface
setComment(CurrentDt.getNodeDescription(CurrentDtn));
AttChoice.removeAll();
AttChoice.add(messagechoice);
AttChoice.select(0);
refreshcurrenttree();
}

/**
* some functions to get the parameters value
*/
public Vector GetCandAtt() {
int[] index=lst_candatt.getSelectedIndexes();
if (index.length==0)
return new Vector();
Vector result=new Vector();
for (int i=0; i result.addElement(db.attributes.elementAt(index[i]));
}
return result;
}

public SymbAtt GetGoalAttribute() {
return (SymbAtt)db.findAttribute(GoalAttributeChoice.getSelectedItem());
}

public double GetEntThres() {
return (new Double(tf_entthres.getText())).doubleValue();
}

public double GetScoreThres() {
return (new Double(tf_scorethres.getText())).doubleValue();
}

public int GetLsSize() {
if (tf_lssize.getText()=="")
return 0;
else
return Integer.parseInt(tf_lssize.getText());
}

public int GetLsMode() {
return SelectionChoiceLs.getSelectedIndex();
}

public int GetTsSize() {
if (tf_lssize.getText()=="")
return 0;
else
return Integer.parseInt(tf_tssize.getText());
}

public int GetTsMode() {
return SelectionChoiceTs.getSelectedIndex();
}

public void setComment(String t) {
tf_opennode.setText(t);
}

/**
* Start the main applet thread.
*/
public void start ()
{
running = true;
t = new Thread(this);
t.start();
}

/**
* Stop the applet.
*/
public void stop ()
{
running = false;
}

/**
* Main event loop.
*/
public void run () { }

/**
* scan all the attributes at the top node for the best attribute.
* display the result into the choice list.
*/
public void Scanatt() {

if (CurrentDtn==null)
return;

Vector choices=CurrentDt.scanNode(CurrentDtn);
AttChoice.removeAll();
for (int i=0; i AttChoice.add((String)choices.elementAt(i));
}

/**
* Split the current node
*
/
public void SplitMore() {

if (CurrentDtn==null)
return;

if (CurrentDtn.type!="open") {
// if the node is not open, we open it
CurrentDtn.open();
}

if (AttChoice.getItem(0)==messagechoice) {
//-- the user has not asked for attributes scanning
CurrentDt.scanNode(CurrentDtn);
changeSelectedNode(CurrentDt.splitNode(CurrentDtn,0));
} else {
//-- we take into account the user's choice
changeSelectedNode(CurrentDt.splitNode(CurrentDtn,AttChoice.getSelectedIndex()));
}
refreshcurrenttree();
}

public void changeSelectedNode(DtNode dtn) {
if (CurrentDtn!=null)
CurrentDtn.graphnode.selected=false;
if (AttChoice.getItem(0)!=messagechoice) {
AttChoice.removeAll();
AttChoice.add(messagechoice);
AttChoice.select(0);
}
CurrentDtn=dtn;
if (CurrentDtn!=null) {
CurrentDtn.graphnode.selected=true;
setComment(CurrentDt.getNodeDescription(CurrentDtn));
} else {
setComment("");
}
}

public void buildalltree() {
showStatus("Building the tree...");
CurrentDt.buildDt();
changeSelectedNode(null);
refreshcurrenttree();
CurrentDt.printDt();
showStatus("done");
}

public void testtree() {
//-- learning set selection
showStatus("Testing the tree...");
int tssize=GetTsSize();
int tsmode=GetTsMode();
if (tsmode==0)
ts=db.objects.selectNotIn(ls);
else if (tsmode==1)
ts=db.objects.selectRandom(tssize);
else if (tsmode==2)
ts=db.objects.selectFirst(tssize);
else if (tsmode==3)
ts=db.objects.selectLast(tssize);
else if (tsmode==4)
ts=ls;
String result="" + CurrentDt.testDt(ts)100;
if (result.length()<5)
tf_testresult.setText("" + result + "%");
else
tf_testresult.setText("" + result.substring(0,5) + "%");
showStatus("done");
}

public void CrossValidation() {
showStatus("Cross validation...please wait");
double result=CurrentDt.testDtCrossvalidation(GetTsSize());
String sr="" + result100;
if (sr.length()<5)
tf_testresult.setText(sr + "%");
else
tf_testresult.setText(sr.substring(0,5) + "%");
showStatus("done");
}

public void actionPerformed(ActionEvent event) {
String command=event.getActionCommand();

if (command=="Split" && root!=null) {
SplitMore();
} else if (command=="Build" && root!=null) {
buildalltree();
} else if (command=="Scan attributes" && root!=null) {
Scanatt();
} else if (command=="Refresh" && root!=null) {
refreshcurrenttree();
} else if (command=="Test tree" && root!=null) {
testtree();
} else if (command=="New Tree") {
NewTree();
} else if (command=="Load Database") {
loadDb();
} else if (command=="Cross Validation" && root!=null) {
CrossValidation();
} else if (command=="+") {
snd.increaseZoom();
dnd.increaseZoom();
tc.repaint();
} else if (command=="-") {
snd.decreaseZoom();
dnd.decreaseZoom();
tc.repaint();
}
}

public void refreshcurrenttree() {
if (root==null)
return;
tc.nd.computeNodeSize(root);
tc.setTree(root);
tc.repaint();
}

public void itemStateChanged(ItemEvent event) {
String command=(String)event.getItem();

if (command == "Simple") {
tc.nd=snd;
refreshcurrenttree();
} else if (command == "Detailed") {
tc.nd=dnd;
if (root!=null) {
dnd.initWidth(root);
refreshcurrenttree();
}
} else if (command == "Not in ls") {
tf_tssize.setText("" + (db.objects.size - Integer.parseInt(tf_lssize.getText())));
} else if (command == "Learning set") {
tf_tssize.setText(tf_lssize.getText());
}
}

/ gestion de la souris /
class MyMouseListener extends MouseAdapter {
public void mousePressed(MouseEvent e) {
int x=e.getX();
int y=e.getY();
if (root!=null) {
DtNode dtn=root.getPointedNode((int)(x/tc.nd.zoom),(int)(y/tc.nd.zoom));
if (dtn!=null) {
// select this node
changeSelectedNode(dtn);
// retrace the graph (there must exist a better way to do this)
tc.repaint();
}
}
}
}
}
-------------------------

/
* DetailedNodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.awt.;
import java.util.*;

/**
* a abstract class to allow many representation for
* a node
/

public class DetailedNodeDrawer extends NodeDrawer {

FontMetrics metrics_small,metrics_big, metrics_current;
Font smallfont, bigfont;
int SMALL_FIXED_FONT_HEIGHT=8;
int BIG_FIXED_FONT_HEIGHT=14;
int current_font_height;
int default_border=10;
Vector colours=new Vector();
int max_width=60;
int max_height=40;
int max_ls_size=1;
double coef;
Canvas cv;

DetailedNodeDrawer(Canvas c) {
cv=c;
bigfont=new Font("Helvetica", Font.PLAIN, BIG_FIXED_FONT_HEIGHT);
c.setFont(bigfont);
metrics_big=c.getFontMetrics(c.getFont());

smallfont=new Font("Helvetica", Font.PLAIN, SMALL_FIXED_FONT_HEIGHT);
c.setFont(smallfont);
metrics_small=c.getFontMetrics(c.getFont());

metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;

coef=Math.exp(1)20;
colours.addElement(Color.black);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
}

public void initWidth(WNode t) {
t.width=0;
if (t.sibling!=null) {
initWidth(t.sibling);
}
if (t.child!=null) {
initWidth(t.child);
}
}

public void computeNodeSize(WNode t) {
max_ls_size=t.dtnode.subset.size;
computeSize(t);
}

public void computeSize(WNode t) {
if (t.width==0) { //-- we compute the size only once
double correction;
if (t.dtnode.subset.size!=0)
correction=Math.log(coef)/Math.log(coefmax_ls_size/t.dtnode.subset.size);
else
correction=Math.log(coef)/Math.log(coefmax_ls_size);
t.height=(int)(max_widthcorrection);
t.width=(int)(max_heightcorrection);
}

t.border=default_border;

if (t.sibling!=null) {
computeSize(t.sibling);
}

if (t.child!=null) {
computeSize(t.child);
}
}

public void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel) {
g.setColor(Color.black);
g.drawLine((int)(x1zoom), (int)(y1zoom), (int)(x2zoom),(int)(y2zoom));
g.drawString(arclabel,
(int)(((x1 + x2)zoom - metrics_current.stringWidth(arclabel)) / 2),
(int)((y1 + y2)zoom/2));
}

public void drawNode(Graphics g, WNode t) {
int tposx=(int)(t.pos.xzoom);
int tposy=(int)(t.pos.yzoom);
int tw=(int)(t.widthzoom);
int th=(int)(t.heightzoom);

int current_x=tposyt.dtnode.subset.size;
int incr_x;
int y=tposx;

//-- draw the box
if (t.dtnode.subset.size!=0) {
for (int i=0; i if (t.dtnode.subset.summary[i]!=0) {
incr_x=tht.dtnode.subset.summary[i];
g.setColor((Color)colours.elementAt(i+1));
g.fillRect((int)(current_x/t.dtnode.subset.size),y,
(int)(incr_x/t.dtnode.subset.size)+1,tw);
current_x+=incr_x;
}
}
}

g.setColor(Color.black);
g.drawRect(tposy, tposx, th, tw);

//-- we highlight the current open node
if (t.selected) {
g.setColor(Color.pink);
g.drawRect(tposy-current_font_height, tposx-current_font_height,
th+2current_font_height, tw+2current_font_height);
}

//-- we put information beneath the box ...
String bottomtext;
if (t.dtnode.type.equals("test"))
bottomtext=t.label;
else if (t.dtnode.type.equals("open"))
bottomtext="open";
else if (t.dtnode.type.equals("open"))
bottomtext="leaf : " + t.dtnode.majclass;
else
bottomtext="error";

g.setColor(Color.black);
g.drawString(t.label,
tposy + (th - metrics_current.stringWidth(t.label)) / 2,
tposx + tw + current_font_height);

//-- ... and on top of the box
g.drawString(t.dtnode.name, tposy, tposx+1);

}

// increase the zoom
public void increaseZoom() {
if (zoom==0.5)
zoom=0.7;
else if (zoom==0.7)
zoom=1.0;
else if (zoom==1.0)
zoom=1.2;
else if (zoom==1.2) {
zoom=1.5;
metrics_current=metrics_big;
current_font_height=BIG_FIXED_FONT_HEIGHT;
cv.setFont(bigfont);
} else if (zoom==1.5)
zoom=2.0;
else if (zoom==2.0)
zoom=2.5;
else if (zoom==2.5)
zoom=3.0;
}

// decrease the zoom
public void decreaseZoom() {
if (zoom==3.0)
zoom=2.5;
else if (zoom==2.5)
zoom=2.0;
else if (zoom==2.0)
zoom=1.5;
else if (zoom==1.5) {
zoom=1.2;
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
cv.setFont(smallfont);
} else if (zoom==1.2)
zoom=1.0;
else if (zoom==1.0)
zoom=0.7;
else if (zoom==0.7)
zoom=0.5;
}
}
----------------------------------

/*
* DtNode.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

public class DtNode {
static int nbnodes;
ObjectSet subset;
String type="open"; // leaf, test or open
String majclass="default"; // the majority class in this node
String name;
WNode graphnode; // for the tree visualisation

Test test;
Vector successors;

DtNode(ObjectSet s, SymbAtt goal) {
subset=s;
name="node" + nbnodes++;
ComputeInfoNode(goal);
}

/**
* Compute some information about this node (entropy, subset summary
* and class maj). This should be call when the node is created.
*/
public void ComputeInfoNode(SymbAtt goal) {
subset.computeEntropy(goal);
majclass=subset.getMajClass(goal);
}

/**
* Scan all the cancidate attributes, compute the information gain of the
* best score. Return a vector of attributes ordered by decreasing values
* of information.
/
public Vector scanAttributes(Vector ca, SymbAtt goal, double entthres, double scorethres) {
Vector result=new Vector();

System.out.println("expanding " + getNodeDescription(goal));

//-- no object in this node (this should never happen)
if (subset.size==0) {
result.addElement("No object in this node -> a leaf");
return result;
}

//-- entropy is low enough, we can stop splitting this node
if (subset.entropy<=entthres) {
result.addElement("Entropy low enough (threshold=" +
entthres + ") -> a leaf");
return result;
}

//-- in the other case, we scan the attributes
// System.out.println("number of candidate attributes : " + ca.size());
System.out.print("[");
double score;
int i=0,j=0;
Attribute att;
for (; i System.out.print("."); // on point per attribute
att=(Attribute)ca.elementAt(i);
score=att.bestscore(subset,goal);
// System.out.println(att.name + " " + score);
//-- the score must be greater than the threshold (forward pruning)
if ((scoresubset.size)>scorethres) {
j=0;
while (j score<=((Attribute)result.elementAt(j)).lastbestscore)
j++;
if (j==result.size())
result.addElement(att);
else
result.insertElementAt(att,j);
}
}
System.out.println("]");

//-- we always let the possibility to user to make this node a leaf
result.addElement("make this node a leaf");
return result;
}

public Vector split(Vector scanresult, int choice, SymbAtt goal) {

//-- make this node a leaf
if (choice==scanresult.size()-1) {
System.out.println((String)scanresult.elementAt(choice));
type="leaf";
buildGraphLeafNode(goal);
return null;
}

//-- we take the attribute and construct the partition
Attribute selectedatt=(Attribute)scanresult.elementAt(choice);
Partition partition=selectedatt.bestpartition(subset,goal);
test=partition.test;
successors=new Vector();
type="test";
System.out.println("-> a test node (score : " + selectedatt.lastbestscore +
" , test : " + test.TestDescription + ")");

//-- we create the successor nodes
for (int i=0; i successors.addElement(new DtNode((ObjectSet)partition.sets.elementAt(i),
goal));
}

//-- we create the graphnodes
buildGraphTestNodes();

//- we return the successors (open nodes)
return successors;
}

/**
* expand this node and return a vector of open nodes resulting from
* the expansion
/
public Vector expand(Vector ca, SymbAtt goal, double entthres, double scorethres) {

//-- if the subset is empty, this is a leaf and the class is default
if (subset.size==0) {
System.out.println("-> a leaf (no objects)");
majclass="default";
type="leaf";
buildGraphLeafNode(goal);
return null;
}

System.out.println("expanding " + getNodeDescription(goal));

//-- if the entropy is lower than the threshold, then we stop the splitting
if (subset.entropy<=entthres) { // a new leaf
System.out.println("-> a leaf (entropy low, " + subset.entropy
+ "<=" + entthres + ")");
type="leaf";
buildGraphLeafNode(goal);
return null;
}

//-- otherwise, we screen all the attributes
double bestscore=0,score;
Attribute bestatt=null,att;
System.out.print("[");
for (int i=0; i System.out.print(".");
att=(Attribute)ca.elementAt(i);
score=att.bestscore(subset,goal);
if (score>bestscore) {
bestscore=score;
bestatt=att;
}
}
System.out.println("]");

//-- the best score must be greater than the threshold (stop-splitting rule)
if ((bestscoresubset.size)<=scorethres) {
System.out.println("-> a leaf (score too low, "
+ (bestscore*subset.size) + "<=" +
scorethres + ")");
type="leaf";
buildGraphLeafNode(goal);
return null;
}

//-- we construct the partition of the learning set
Partition partition=bestatt.bestpartition(subset,goal);
test=partition.test;
successors=new Vector();
type="test";
System.out.println("-> a test node (score : " + bestscore +
" , test : " + test.TestDescription + ")");

//-- we create the successor nodes
for (int i=0; i successors.addElement(new DtNode((ObjectSet)partition.sets.elementAt(i),
goal));
}

//-- we create the graphnodes
buildGraphTestNodes();

//-- we return the successors (open node)
return successors;
}

/**
* complete the graphnode for a leaf
*/
public void buildGraphLeafNode(SymbAtt goal) {
graphnode.label=majclass;
if (majclass.equals("default")) {
graphnode.colour=0;
} else {
graphnode.colour=goal.values.indexOf(majclass)+1;
}
}

/**
* build the graphnodes for the successors of this node
*/
public void buildGraphTestNodes() {
//-- first we put the label of this node (the size will be computed afterwards)
graphnode.label=test.TestDescription;

//-- then the first successor
DtNode dtchild=(DtNode)successors.elementAt(0);
dtchild.graphnode=new WNode("open", (String)test.valuesIssues.elementAt(0),
graphnode, null, null,0,0,0,dtchild);
graphnode.child=dtchild.graphnode;
WNode previousgchild=dtchild.graphnode;
DtNode nextdtchild;

//-- and finally the others
for (int i=1; i nextdtchild=(DtNode)successors.elementAt(i);
nextdtchild.graphnode=new WNode("open", (String)test.valuesIssues.elementAt(i),
graphnode,null,null,0,0,0,nextdtchild);
previousgchild.sibling=nextdtchild.graphnode;
previousgchild=nextdtchild.graphnode;
}
}

/**
* open a node (destroy all his successors and tests)
*/
public void open() {
test=null;
type="open";
graphnode.child=null;
graphnode.colour=0;
graphnode.label="open";
}

/**
* get all the open nodes of this subtree (in a depth first way but
* in the oposite direction (right to left and bottom to top)
*/
public void getOpenNodes(Stack opennodes) {
if (type.equals("open"))
opennodes.push(this);
else if (successors!=null) {
for (int i=successors.size()-1; i>=0; i--) {
((DtNode)successors.elementAt(i)).getOpenNodes(opennodes);
}
}
}

/**
* get the leftmost open node
*/
public DtNode getLeftMostOpenNode() {
if (type.equals("open"))
return this;
else if (successors!=null) {
for (int i=0; i DtNode dtn=((DtNode)successors.elementAt(i)).getLeftMostOpenNode();
if (dtn!=null)
return dtn;
}
return null;
} else
return null;
}

/**
* return the class associated to this object by the subtree corresponding
* to this node
*/
public String getClass(Obj o) {
if (type.equals("leaf") || type.equals("open"))
return majclass;
else
return ((DtNode)successors.elementAt(test.TestIndex(o))).getClass(o);
}

/**
* give a textual description of this node
*/
public String getNodeDescription(SymbAtt goal) {
String s="";
s+=name;
s+=" - LS : " + subset.getSummaryString(goal);
s+=" - ENTROPY : " + subset.entropy;
return s;
}

/**
* print n spaces (to pretty print the decision tree)
*/
private String printNtab(int n) {
String result="";
for (int i=0; i result+=" ";
}
return result;
}

/**
* print a textual description of the subtree corresponding
* to this node.
/
public String printNode(int depth) {
String result="";
if (type.equals("leaf") || type.equals("open")) {
result+=printNtab(depth);
result+="return \"" + majclass + "\";\n";
} else if (type.equals("test")) {
for (int i=0; i result+=printNtab(depth);
if (i!=0)
result+="} else ";
result+="if (" + test.testDescription(i) + ") {\n";
result+=((DtNode)successors.elementAt(i)).printNode(depth+1);
}
result+=printNtab(depth) + "}\n";
} else {
System.out.println("printNode - bad node type");
return "";
}
return result;
}
}

-------------------------------

/
* Entropy.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.io.;

/* this class contains some functions to calculate
* entropy values
/
public class Entropy{
static double entropy(int freq[], int size, int sum) {
// when we don't have example then the entropy is zero
if (sum==0)
return 0.0;
double result=sumjava.lang.Math.log(sum);
for (int i=0; i if (freq[i]!=0)
result-=freq[i]java.lang.Math.log(freq[i]);
}
result/=java.lang.Math.log((double)2.0);
result/=sum;
return result;
}
}
-------------------------

/
* NodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.awt.;
import java.util.*;

/**
* a abstract class to allow many representation for
* a node
/

public abstract class NodeDrawer {
double zoom=1.0;

abstract void computeNodeSize(WNode t);
abstract void drawNode(Graphics g, WNode t);
abstract void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel);
abstract void increaseZoom();
abstract void decreaseZoom();
}
--------------------------

/
* NumAtt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.io.;
import java.util.;

public class NumAtt extends Attribute{
/ le domaine de l'attribut dans la bd /
float rangemin=(float)1.0, rangemax=(float)0.0;
/ le meilleur score precedemment obtenu par cet attribut /
float bestthreshold;

NumAtt(String s, Database dab) {
name=s;
db=dab;
index=db.addAttToDb(this);
}
public void SetAttValue(Obj o,Object f) {
float fl=((Float)f).floatValue();
if (rangemin>rangemax) {
rangemin=fl;
rangemax=fl;
} else {
if (fl rangemin=fl;
else if (fl>rangemax)
rangemax=fl;
}
o.attributesvalues.setElementAt(f,index);
}
public int ReadAttValue(Obj o, StreamTokenizer stt) {
if (stt.ttype==stt.TT_NUMBER) {
SetAttValue(o,new Float(stt.nval));
return 0;
} else {
System.out.println("A numerical value was expected");
return 1;
}
}

public String describe() {
return toString()+ " - numerical - range : [" + rangemin + "," + rangemax + "]";
}

public String describeBestTest() {
return toString() + " - threshold : " + bestthreshold + " - Information gain : " +
lastbestscore;
}

/ return the best partition for a numerical attribute
* we assume that the best threshold is already computed (by
* using bestscore
/
public Partition bestpartition(ObjectSet os, SymbAtt goal) {
TestNum t=new TestNum(this,bestthreshold);
Vector v=os.splitOn(t);
return new Partition(t,v);
}

/ searches the best threshold value for a numerical attribute
* assumes that the objectset size is greater than 0
/
public double bestscore(ObjectSet os, SymbAtt goal) {
// first, the set is ordered by increasing attribute values
os.orderOn(this);

// then prepare the data, we suppose that we have already
// computed the entropy value
int gvs=goal.values.size();
int freqyes[]=new int[gvs+1];
int freqno[]=new int[gvs+1];
// in the beginning, the test is false for all objects
for (int i=0; i freqno[i]=os.summary[i];
}
freqno[gvs]=os.size;
float currentthreshold=rangemin;
double bestscore=0,actualscore=os.entropy;
double entyes,entno;
int ico;
int iconext=goal.values.indexOf(goal.Value((Obj)os.elementAt(0)));
float av;
float avnext=((Float)Value((Obj)os.elementAt(0))).floatValue();

for (int i=0; i // index of the class for this object
ico=iconext;
iconext=goal.values.indexOf(goal.Value((Obj)os.elementAt(i+1)));
av=avnext;
avnext=((Float)Value((Obj)os.elementAt(i+1))).floatValue();
freqno[ico]--;freqno[gvs]--;
freqyes[ico]++;freqyes[gvs]++;
if (
// ico!=iconext && // i'm not sure of this -> skip it
av!=avnext
) {
// only if the class of this point is different from the next point
// class and if its attribute value if also different from the next
// point attribute value
entno=Entropy.entropy(freqno,gvs,freqno[gvs]);
entyes=Entropy.entropy(freqyes,gvs,freqyes[gvs]);
actualscore=os.entropy-(freqno[gvs]entno+freqyes[gvs]entyes)/os.size;
if (actualscore>bestscore) {
bestscore=actualscore;
currentthreshold=(float)((av+avnext)/2.0);
}
}
}
bestthreshold=currentthreshold;
lastbestscore=bestscore;
return bestscore;
}
}
--------------------------

/
* Obj.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

public class Obj {
/* the name of the object /
String name;
/ the database it belongs to /
Database db;
/ the vector of attributes values /
Vector attributesvalues=new Vector();

Obj(String s, Database db) {
this.db=db;
name=s;
db.addObjToDb(this);
/ it allocates place for the attribute values /
attributesvalues.setSize(db.attributes.size());
}
public String toString() {
return name;
}
}

----------------------

/
* ObjectSet.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

/* simplement un vecteur d'object, on verra apres si on garde
ce niveau d'abstraction ou pas
/

public class ObjectSet {
/ objects list/
Vector objectslist;
/ a cache value for the entropy in this set /
double entropy;
/ the size of the learning set /
int size;
/ summary, the frequence of each class in this set /
int summary[];

ObjectSet(Vector vo) {
objectslist=vo;
size=vo.size();
}

ObjectSet() {
objectslist=new Vector();
size=0;
}

/ only for compatibility (primary an objectset was simply a vector) /
public int size() {
return size;
}

public Obj elementAt(int index) {
return (Obj)objectslist.elementAt(index);
}
public void addElement(Obj o) {
objectslist.addElement(o);
size++;
}
public void setElementAt(Obj o, int index) {
objectslist.setElementAt(o, index);
}

public int indexOf(Obj o) {
return objectslist.indexOf(o);
}

public String toString() {
return objectslist.toString();
}

/ split a set according to the given test /
public Vector splitOn(Test t) {
int index;
Vector v=new Vector();
Obj o;
for (int i=0; i v.addElement(new ObjectSet());
}
for (int i=0; i o=(Obj)objectslist.elementAt(i);
index=t.TestIndex(o);
((ObjectSet)v.elementAt(index)).addElement(o);
}
return v;
}
/ methods to select subset of objects from the database /

/ select the first n objects from this subset /
public ObjectSet selectFirst(int n) {
ObjectSet os=new ObjectSet();
for (int i=0;i os.addElement((Obj)objectslist.elementAt(i));
}
return os;
}

/ select the last n objects from this subset /
public ObjectSet selectLast(int n) {
ObjectSet os=new ObjectSet();
int i;
if (n>size)
i=0;
else
i=size-n;
for (;i os.addElement((Obj)objectslist.elementAt(i));
}
return os;
}

/ select randomly n objects from this set (very stupid) /
public ObjectSet selectRandom(int n) {
ObjectSet os=new ObjectSet();
Vector v=(Vector)objectslist.clone();
int sv=size;
int pos;
if (n>size)
n=size;
for (int i=0;i pos=(int)(svjava.lang.Math.random());
os.addElement((Obj)v.elementAt(pos));
v.removeElementAt(pos);
sv--;
}
return os;
}

/* select objects which are not in a given subset /
public ObjectSet selectNotIn(ObjectSet oset) {
ObjectSet os=new ObjectSet();
Obj o;
for (int i=0;i o=(Obj)objectslist.elementAt(i);
if (oset.indexOf(o)==-1)
os.addElement(o);
}
return os;
}

/ method to compute the entropy of an symbolic attribute in this subset
* it computes also the subset summary
/
public double computeEntropy(SymbAtt goal) {
int sum=size;
int i,x,gvs=goal.values.size();
summary=new int[gvs];
for (i=0; i x=goal.values.indexOf(goal.Value((Obj)objectslist.elementAt(i)));
summary[x]++;
}
entropy=Entropy.entropy(summary, gvs, sum);
return entropy;
}

/ give a textual description of the subset summary /
public String getSummaryString(SymbAtt goal) {
String s="";
for (int i=0; i s+=(String)goal.values.elementAt(i);
s+=":" + summary[i]+ " ";
}
s+="total:" + size;
return s;
}

/ method that gives the majority class in this subset (using the summary) /
public String getMajClass(SymbAtt goal) {
int imax=0;
int maxfreq=summary[0];
for (int i=1; i if (summary[i]>maxfreq) {
maxfreq=summary[i];
imax=i;
}
}
return (String)goal.values.elementAt(imax);
}

/ order a subset on numerical attribute values
* use quicksort algorithm
/
public void orderOn(NumAtt att) {
orderOn(att,0,size-1);
}

public void orderOn(NumAtt att, int lo0, int hi0) {
int lo=lo0;
int hi=hi0;
float mid;

if (hi0>lo0) {
mid = ((Float)att.Value((Obj)objectslist.elementAt((lo0+hi0)/2))).floatValue();
while (lo<= hi) {
while((lo (((Float)att.Value((Obj)objectslist.elementAt(lo))).floatValue() ++lo;
while((hi>lo0) &&
(((Float)att.Value((Obj)objectslist.elementAt(hi))).floatValue()>mid))
--hi;
if(lo<=hi) {
Object tmp=objectslist.elementAt(lo);
objectslist.setElementAt(objectslist.elementAt(hi),lo);
objectslist.setElementAt(tmp,hi);
++lo;
--hi;
}
}
if(lo0 orderOn(att,lo0,hi);
if (lo orderOn(att,lo,hi0);
}
}
}
---------------------------

/
* Partition.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

public class Partition{
/* a test /
Test test;
/ a vector of ObjectSet */
Vector sets;

Partition(Test t, Vector oss) {
test=t;
sets=oss;
}
}
------------------------

/**
* Represents a polygon area for use in spacing/positioning calculations.
*/
class Polygon {
PolyLine lower_head, lower_tail;
PolyLine upper_head, upper_tail;
};

------------------------

/**
* Used to build Polygons.
/
class PolyLine {
int dx, dy;
PolyLine link;

PolyLine(int dx, int dy, PolyLine link) {
this.dx = dx;
this.dy = dy;
this.link = link;
}
};

--------------------------

/
* 1.1 version.
/

import java.awt.;
import java.awt.event.;
import java.applet.Applet;

/
* This displays a framed area. When the user clicks within
* the area, this program displays a dot and a string indicating
* the coordinates where the click occurred.
/

public class RectangleDemo extends Applet {
RFramedArea framedArea;
Label label;

public void init() {
GridBagLayout gridBag = new GridBagLayout();
GridBagConstraints c = new GridBagConstraints();

setLayout(gridBag);

framedArea = new RFramedArea(this);
c.fill = GridBagConstraints.BOTH;
c.weighty = 1.0;
c.gridwidth = GridBagConstraints.REMAINDER; //end row
gridBag.setConstraints(framedArea, c);
add(framedArea);

label = new Label("Drag within the framed area.");
c.fill = GridBagConstraints.HORIZONTAL;
c.weightx = 1.0;
c.weighty = 0.0;
gridBag.setConstraints(label, c);
add(label);
}

public void updateLabel(Rectangle rect) {
label.setText("Rectangle goes from ("
+ rect.x + ", " + rect.y + ") to ("
+ (rect.x + rect.width - 1) + ", "
+ (rect.y + rect.height - 1) + ").");
}
}

/ This class exists solely to put a frame around the coordinate area. /
class RFramedArea extends Panel {
public RFramedArea(RectangleDemo controller) {
super();

//Set layout to one that makes its contents as big as possible.
setLayout(new GridLayout(1,0));

add(new SelectionArea(controller));
}

public Insets getInsets() {
return new Insets(4,4,5,5);
}

public void paint(Graphics g) {
Dimension d = getSize();
Color bg = getBackground();

g.setColor(bg);
g.draw3DRect(0, 0, d.width - 1, d.height - 1, true);
g.draw3DRect(3, 3, d.width - 7, d.height - 7, false);
}
}

class SelectionArea extends Canvas {
Rectangle currentRect = null;
RectangleDemo controller;

public SelectionArea(RectangleDemo controller) {
super();
this.controller = controller;

MyListener myListener = new MyListener();
addMouseListener(myListener);
addMouseMotionListener(myListener);
}

class MyListener extends MouseAdapter
implements MouseMotionListener {
public void mousePressed(MouseEvent e) {
int x = e.getX();
int y = e.getY();
currentRect = new Rectangle(x, y, 0, 0);
repaint();
}

public void mouseDragged(MouseEvent e) {
updateSize(e);
}

public void mouseMoved(MouseEvent e) {
}

public void mouseReleased(MouseEvent e) {
updateSize(e);
}

void updateSize(MouseEvent e) {
int x = e.getX();
int y = e.getY();
currentRect.setSize(x - currentRect.x,
y - currentRect.y);
repaint();
}
}

public void paint(Graphics g) {
//update has already cleared the previous rectangle,
//so we dn't need to here.

//If currentRect exists, paint a rectangle on top.
if (currentRect != null) {
Dimension d = getSize();
Rectangle box = getDrawableRect(currentRect, d);
controller.updateLabel(box);

//Draw the box outline.
g.drawRect(box.x, box.y,
box.width - 1, box.height - 1);
}
}

Rectangle getDrawableRect(Rectangle originalRect,
Dimension drawingArea) {
int x = originalRect.x;
int y = originalRect.y;
int width = originalRect.width;
int height = originalRect.height;

//Make sure rectangle width and height are positive.
if (width < 0) {
width = 0 - width;
x = x - width + 1;
if (x < 0) {
width += x;
x = 0;
}
}
if (height < 0) {
height = 0 - height;
y = y - height + 1;
if (y < 0) {
height += y;
y = 0;
}
}

//The rectangle shouldn't extend past the drawing area.
if ((x + width) > drawingArea.width) {
width = drawingArea.width - x;
}
if ((y + height) > drawingArea.height) {
height = drawingArea.height - y;
}

//If the width or height is 0, make it 1
//so that the box is visible.
if (width == 0) {
width = 1;
}
if (height == 0) {
height = 1;
}

return new Rectangle(x, y, width, height);
}
}
----------------------

/
* SimpleNodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.awt.;
import java.util.*;

/**
* a abstract class to allow many representation for
* a node
/

public class SimpleNodeDrawer extends NodeDrawer {

FontMetrics metrics_small,metrics_big,metrics_current;
Font smallfont, bigfont;
int SMALL_FIXED_FONT_HEIGHT=8;
int BIG_FIXED_FONT_HEIGHT=14;
int current_font_height;
int default_border=5;
Vector colours=new Vector();
Canvas cv;

SimpleNodeDrawer(Canvas c) {
cv=c;
bigfont=new Font("Helvetica", Font.PLAIN, BIG_FIXED_FONT_HEIGHT);
c.setFont(bigfont);
metrics_big=c.getFontMetrics(c.getFont());

smallfont=new Font("Helvetica", Font.PLAIN, SMALL_FIXED_FONT_HEIGHT);
c.setFont(smallfont);
metrics_small=c.getFontMetrics(c.getFont());

metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;

colours.addElement(Color.black);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
}

public void computeNodeSize(WNode t) {
t.width=2 current_font_height;
t.height=metrics_current.stringWidth(t.label) + 10;
t.border=default_border;

if (t.sibling !=null) {
computeNodeSize(t.sibling);
}

if (t.child != null) {
computeNodeSize(t.child);
}
}

public void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel) {
g.setColor(Color.black);
g.drawLine((int)(x1zoom), (int)(y1zoom), (int)(x2zoom),(int)(y2zoom));
g.drawString(arclabel,
(int)(((x1 + x2)zoom - metrics_current.stringWidth(arclabel)) / 2),
(int)((y1 + y2)zoom/2));
}

public void drawNode(Graphics g, WNode t) {
int tposx=(int)(t.pos.xzoom);
int tposy=(int)(t.pos.yzoom);
int tw=(int)(t.widthzoom);
int th=(int)(t.heightzoom);

// Draw highlights
g.setColor(Color.lightGray);
g.drawLine(tposy + 2, tposx + tw + 1, tposy + th,
tposx + tw + 1);
g.drawLine(tposy + th + 1, tposx + tw + 1,
tposy + th + 1, tposx + 2);

// we draw the box corresponding to this node
if (t.colour>=colours.size())
g.setColor(Color.black);
else
g.setColor((Color)colours.elementAt(t.colour));

g.drawRect(tposy, tposx, th, tw);

// we draw the node label
g.drawString(t.label,
tposy + (th - metrics_current.stringWidth(t.label)) / 2,
tposx + tw - (tw - current_font_height) / 2);

if (t.selected) {
int border=(int)(3zoom);
g.setColor(Color.pink);
g.drawRect(tposy-border, tposx-border, th+2border, tw+2border);
}

}

// increase the zoom
public void increaseZoom() {
if (zoom==0.5)
zoom=0.7;
else if (zoom==0.7)
zoom=1.0;
else if (zoom==1.0)
zoom=1.2;
else if (zoom==1.2) {
zoom=1.5;
metrics_current=metrics_big;
current_font_height=BIG_FIXED_FONT_HEIGHT;
cv.setFont(bigfont);
} else if (zoom==1.5)
zoom=2.0;
else if (zoom==2.0)
zoom=2.5;
else if (zoom==2.5)
zoom=3.0;
}

// decrease the zoom
public void decreaseZoom() {
if (zoom==3.0)
zoom=2.5;
else if (zoom==2.5)
zoom=2.0;
else if (zoom==2.0)
zoom=1.5;
else if (zoom==1.5) {
zoom=1.2;
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
cv.setFont(smallfont);
} else if (zoom==1.2)
zoom=1.0;
else if (zoom==1.0)
zoom=0.7;
else if (zoom==0.7)
zoom=0.5;
}
}
-----------------------

/
* SymbAtt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

/ recherche de la meilleure partition binaire de l'ensemble des valeurs de
l'attribut /

import java.util.;
import java.io.;

public class SymbAtt extends Attribute{
Vector values=new Vector();
/ la valeur de l'attribut symbolique qui donne le meilleur score /
Vector bestsubset;

SymbAtt(String s, Database dab) {
name=s;
db=dab;
index=db.addAttToDb(this);
}
public void SetAttValue(Obj o,Object s) {
int i;
for (i=0; i if (s.equals(values.elementAt(i)))
break;
if (i o.attributesvalues.setElementAt(values.elementAt(i),index);
else {
o.attributesvalues.setElementAt(s,index);
values.addElement(s);
}
}
public int ReadAttValue(Obj o, StreamTokenizer stt) {
if (stt.ttype==stt.TT_WORD) {
SetAttValue(o,stt.sval);
return 0;
} else if (stt.ttype==stt.TT_NUMBER) {
// we transform number to a string
SetAttValue(o,"" + stt.nval);
return 0;
} else {
System.out.println("A symbolic value was expected");
return 1;
}
}

public String describe() {
return toString()+ " - symbolic - values : " + values.toString();
}

public String describeBestTest() {
return toString() + " - values : " + bestsubset.toString() + " - Information gain : " + lastbestscore;
}

public double bestscore(ObjectSet os, SymbAtt goal) {
/ attention cette partie est tres tres mal ecrite /

double result;
double tmpresult;
double currentbestscore=-1;
int currentbestvalue=0;
int pbv;
int i,j,x,y;

/ liste des index/
Vector remainingvalues=new Vector();
for (i=0; i remainingvalues.addElement(new Integer(i));
}

/ les valeurs dans l'ordre dans lequel elles sont selectionnees /
Vector ordervalues=new Vector();
/ les valeurs de score /
Vector scores=new Vector();

int gvs=goal.values.size();
int sum=os.size;

/ pour chaque valeur de l'attribut, on conserve la matrice des frequences /
int tabfreq[][][]=new int[values.size()][2][gvs+1];

/ calcul des matrices de frequences /
for (j=0; j
for (i=0; i x=values.indexOf(this.Value((Obj)os.elementAt(i)));
y=goal.values.indexOf(goal.Value((Obj)os.elementAt(i)));

if (x==j) { / la valeur est la valeur testee /
tabfreq[j][0][y]++;
tabfreq[j][0][gvs]++;
} else {
tabfreq[j][1][y]++;
tabfreq[j][1][gvs]++;
}
}
/ calcul de l'entropie /
result=os.entropy;
result-=tabfreq[j][0][gvs]Entropy.entropy(tabfreq[j][0], gvs,tabfreq[j][0][gvs])/sum;
result-=tabfreq[j][1][gvs]Entropy.entropy(tabfreq[j][1], gvs,tabfreq[j][1][gvs])/sum;

if (result>currentbestscore) {
currentbestscore=result;
currentbestvalue=j;
}
}

/ on va maintenant regrouper les attributs de maniere recursive /
int currenttabfreq[][]=new int[2][gvs+1];
for (i=0;i currenttabfreq[0][i]=0;
currenttabfreq[1][i]=tabfreq[currentbestvalue][0][i]
+ tabfreq[currentbestvalue][1][i];
}
// printtab(currenttabfreq,gvs+1);

/ on ajoute cet element dans la liste /
Integer cbv=new Integer(currentbestvalue);
ordervalues.addElement(cbv);
scores.addElement(new Double(currentbestscore));
i=0;
while (i ((Integer)remainingvalues.elementAt(i)).intValue()!=currentbestvalue)
i++;
remainingvalues.removeElementAt(i);

while (remainingvalues.size()!=1) {
/ copier le tableau courant dans la valeur correspondant
a l'element precedent /
for (i=0;i currenttabfreq[0][i]+=tabfreq[currentbestvalue][0][i];
currenttabfreq[1][i]-=tabfreq[currentbestvalue][0][i];
}
// printtab(currenttabfreq,gvs+1);
/ on va utiliser la matrice correspondant a la precedente
valeur comme moyen de stockage temporaire
/

pbv=currentbestvalue;

/ recherche de la meilleure valeur a ajouter au sous-ensemble /
currentbestscore=-1;

for (j=0; j int cv=((Integer)remainingvalues.elementAt(j)).intValue();
for (i=0; i tabfreq[pbv][0][i]=tabfreq[cv][0][i]+currenttabfreq[0][i];
tabfreq[pbv][1][i]=currenttabfreq[1][i]-tabfreq[cv][0][i];
}

result=os.entropy;
result-=tabfreq[pbv][0][gvs]
Entropy.entropy(tabfreq[pbv][0], gvs, tabfreq[pbv][0][gvs])/sum;
result-=tabfreq[pbv][1][gvs]*
Entropy.entropy(tabfreq[pbv][1], gvs, tabfreq[pbv][1][gvs])/sum;
if (result>currentbestscore) {
currentbestscore=result;
currentbestvalue=cv;
}
}
cbv=new Integer(currentbestvalue);
ordervalues.addElement(cbv);
scores.addElement(new Double(currentbestscore));
i=0;
while (i ((Integer)remainingvalues.elementAt(i)).intValue()!=currentbestvalue)
i++;
remainingvalues.removeElementAt(i);
}

/* recherche du meilleur score /
currentbestscore=((Double)scores.elementAt(0)).doubleValue();
currentbestvalue=0;
for (i=1; i double sc=((Double)scores.elementAt(i)).doubleValue();
if (sc>currentbestscore) {
currentbestscore=sc;
currentbestvalue=i;
}
}

/ on garde uniquement les elements de l'ensemble /
ordervalues.setSize(currentbestvalue+1);
bestsubset=new Vector();
for (i=0; i bestsubset.addElement(values.elementAt(((Integer)ordervalues.elementAt(i)).intValue()));

// System.out.println(name + " " + values.toString() + " " + bestsubset.toString());

lastbestscore=currentbestscore;
return currentbestscore;
}

public Partition bestpartition(ObjectSet os, SymbAtt goal) {
TestSymb t=new TestSymb(this, bestsubset);
Vector v=os.splitOn(t);
return new Partition(t,v);
}

/
public static void printtab(int[][] tab,int size) {
System.out.print("[[");
for (int i=0; i System.out.print("" + tab[0][i] + ", ");
}
System.out.println("]");
System.out.print("[");
for (int i=0; i System.out.print("" + tab[1][i] + ", ");
}
System.out.println("]]");
}
/

}
-------------------

/
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
/
abstract class Test {
/ a description of the test /
String TestDescription;
/ the attribute /
Attribute Att;
/ the number of issues of this test /
int nbIssues;
/ the vector of the values corresponding to each issues /
Vector valuesIssues;
/ TestObject gives the value associated to this object /
abstract String TestObject(Obj o);
/ return a description of the nth value of this test /
abstract String testDescription(int value);
/ TestIndex gives the index of this values in valuesissues /
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}

----------------------------

/
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
/
abstract class Test {
/ a description of the test /
String TestDescription;
/ the attribute /
Attribute Att;
/ the number of issues of this test /
int nbIssues;
/ the vector of the values corresponding to each issues /
Vector valuesIssues;
/ TestObject gives the value associated to this object /
abstract String TestObject(Obj o);
/ return a description of the nth value of this test /
abstract String testDescription(int value);
/ TestIndex gives the index of this values in valuesissues /
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}

----------------------
/
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/

import java.util.;

/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
/
abstract class Test {
/ a description of the test /
String TestDescription;
/ the attribute /
Attribute Att;
/ the number of issues of this test /
int nbIssues;
/ the vector of the values corresponding to each issues /
Vector valuesIssues;
/ TestObject gives the value associated to this object /
abstract String TestObject(Obj o);
/ return a description of the nth value of this test /
abstract String testDescription(int value);
/ TestIndex gives the index of this values in valuesissues /
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}

--------------------

import java.awt.;

/**
* "There flowered a White Tree, and that was for Gondor; but Seven Stars
* were about it, and a high crown above it, the signs of Elendil that no
* lord had borne for years beyond count. And the stars flamed in the
* sunlight, for they were wrought of gems by Arwen daughter of Elrond;
* and the crown was bright in the morning, for it was wrought of mithril
* and gold." - J. R. R. Tolkien, _The Return of the King_
*
* Basic canvas for creating and displaying a WalTree.
*/
public class WalTreeCanvas extends Canvas {
int default_border;

WTFactory wt_factory; // contain functions to draw a tree
NodeDrawer nd; // contain functions to draw a node
WNode t;
boolean dirty; // tell us if the node positions should be computed again
int root_x;

/**
* Constructs new WalTreeCanvas, an associated WTFactory, and inits state.
*/
public WalTreeCanvas() {
super();

wt_factory = new WTFactory();
t = null;
default_border = 5;
root_x = 8;
dirty = false;
}

public Dimension getPreferredSize() {
return new Dimension(2000, 2000);
}

public Dimension getMiminimumSize() {
return new Dimension(40, 40);
}

/**
* Set the tree to be displayed by this canvas.
*/
public void setTree(WNode t) {
this.t = t;
dirty = true;
}

/**
* Set the default border size for nodes
*/
public void setDefaultBorder(int b) {
default_border = b;
}

/**
* Set the distance between parent nodes.
*/
public void setParentDistance(int val) {
wt_factory.setParentDistance(val);
}

/**
* Set the horizontal offset between edge of canvas and root node.
*/
public void setRootOffset(int val) {
root_x = val;
}

/**
* Draw the tree associated with this canvas.
/
public void paint(Graphics g) {
super.paint(g);

Dimension d = getSize();

/ Wipe background /
g.setColor(Color.white);
g.fillRect(0, 0, d.width, d.height);

if(t == null) {
return;
}

if(dirty == true) {
/ Calculate node offsets /
wt_factory.layout(t);

/ Calculate absolute node positions /

wt_factory.plantTree(t, root_x, root_x-wt_factory.computeMaxOffset(t,0));

dirty = false;
}

/ Paint the beastie */
wt_factory.paintFullTree(g, t, nd);
}
};
------------------------

import java.awt.Point;

/**
* Represents a node (or tree) in the WalTree.
*/
public class WNode {
String label; // the label of the node (test)
String arclabel; // the label of the arc leading to this node
WNode parent, child, sibling;
int width, height, border; // the width, height and border of this node
Point pos, offset;
Polygon contour;
int colour=0; // a colour number
DtNode dtnode; // the associated DtNode
boolean selected=false; // tell us if this node is the current node

public WNode(String l, String a, WNode p, WNode c, WNode s, int w, int h, int b, DtNode dtn) {
label = l;
arclabel=a;
parent = p;
child = c;
sibling = s;
width = w;
height = h;
border = b;
pos = new Point(0, 0);
offset = new Point(0, 0);
contour = new Polygon();
dtnode=dtn;
}

public boolean containsPoint(int x, int y) {
return (((y>=pos.x) && (y<=pos.x+width)) && ((x>=pos.y) && (x<=pos.y+height)));
}

public DtNode getPointedNode(int x,int y) {
if (containsPoint(x,y))
return dtnode;
if (child!=null && y>pos.x) {
// not worth going further down if y DtNode dtchild=child.getPointedNode(x,y);
if (dtchild!=null)
return dtchild;
}
if (sibling!=null)
return sibling.getPointedNode(x,y);
return null;
}
}
-------------------------

/**
* A direct port from Sven Moen's "Drawing Dynamic Trees" article in
* IEEE Software, July 1990. Thanks to Allan Brighton for commenting the
* Brighton Tree Widget source code with the aforementioned reference.
*
* mai 1999 : modified by Pierre Geurts to display decision trees
*
/

import java.awt.;
import java.util.*;

/**
* Encapsulates all operations performed on a WalTree.
*/
public class WTFactory {

int parent_dist = 30;

/**
* Allows setting of the distance between levels in the tree.
*/
public void setParentDistance(int val) {
parent_dist = val;
}

/**
* Lays out the tree node spacing in typical tidy fashion.
*/
void layout(WNode t) {
WNode c;

if(t == null) {
return;
}

c = t.child;
while(c != null) {
layout(c);
c = c.sibling;
}

if(t.child != null) {
attachParent(t, join(t));
} else {
layoutLeaf(t);
}
}

/**
* Attaches the specified node to its children, setting offsets.
/
void attachParent(WNode t, int h) {
int x, y1, y2;

x = t.border + parent_dist;
y2 = (h - t.height) / 2 - t.border;
y1 = y2 + t.height + 2 t.border - h;
t.child.offset.x = x + t.width;
t.child.offset.y = y1;
t.contour.upper_head = new PolyLine(t.width, 0, new PolyLine(x, y1,
t.contour.upper_head));
t.contour.lower_head = new PolyLine(t.width, 0, new PolyLine(x, y2,
t.contour.lower_head));
}

/**
* Arranges contour for leaf node appropriately.
/
void layoutLeaf(WNode t) {
t.contour.upper_tail = new PolyLine(t.width + 2 t.border, 0, null);
t.contour.upper_head = t.contour.upper_tail;
t.contour.lower_tail = new PolyLine(0, -t.height - 2 * t.border, null);
t.contour.lower_head = new PolyLine(t.width + 2 * t.border, 0,
t.contour.lower_tail);
}

/**
* Joins children/siblings together, merging contours.
/
int join(WNode t) {
WNode c;
int d, h, sum;

c = t.child;
t.contour = c.contour;
sum = h = c.height + 2 c.border;
c = c.sibling;
while(c != null) {
d = merge(t.contour, c.contour);
c.offset.y = d + h;
c.offset.x = 0;
h = c.height + 2 * c.border;
sum += d + h;
c = c.sibling;
}

return sum;
}

/**
* Merges two polygons together. Returns total height of final polygon.
/
int merge(Polygon c1, Polygon c2) {
int x, y, total, d;
PolyLine lower, upper, b;

x = y = total = 0;
upper = c1.lower_head;
lower = c2.upper_head;

while(lower != null && upper != null) { / compute offset total /

d = offset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
y += d;
total += d;

if(x + lower.dx <= upper.dx) {
y += lower.dy;
x += lower.dx;
lower = lower.link;
} else {
y -= upper.dy;
x -= upper.dx;
upper = upper.link;
}
}

/ store result in c1 /

if(lower != null) {
b = bridge(c1.upper_tail, 0, 0, lower, x, y);
c1.upper_tail = (b.link != null) ? c2.upper_tail : b;
c1.lower_tail = c2.lower_tail;
} else { / (upper) */
b = bridge(c2.lower_tail, x, y, upper, 0, 0);
if(b.link == null) {
c1.lower_tail = b;
}
}

c1.lower_head = c2.lower_head;

return total;
}

/**
* Calculates the offset for specified points.
/
int offset(int p1, int p2, int a1, int a2, int b1, int b2) {
int d, s, t;

if(b1 <= p1 || p1 + a1 <= 0) {
return 0;
}

t = b1 a2 - a1 * b2;
if(t > 0) {
if(p1 < 0) {
s = p1 * a2;
d = s / a1 - p2;
} else if(p1 > 0) {
s = p1 * b2;
d = s / b1 - p2;
} else {
d = -p2;
}
} else if(b1 < p1 + a1) {
s = (b1 - p1) * a2;
d = b2 - (p2 + s / a1);
} else if(b1 > p1 + a1) {
s = (a1 + p1) * b2;
d = s / b1 - (p2 + a2);
} else {
d = b2 - (p2 + a2);
}

if(d > 0) {
return d;
} else {
return 0;
}
}

/**
* bridge
/
PolyLine bridge(PolyLine line1, int x1, int y1, PolyLine line2, int x2,
int y2) {
int dy, dx, s;
PolyLine r;

dx = x2 + line2.dx - x1;
if(line2.dx == 0) {
dy = line2.dy;
} else {
s = dx line2.dy;
dy = s / line2.dx;
}

r = new PolyLine(dx, dy, line2.link);
line1.link = new PolyLine(0, y2 + line2.dy - dy - y1, r);

return r;
}

void plantTree(WNode t, int off_x, int off_y) {
WNode c, s;
int cur_y;

t.pos.x = off_x + t.offset.x;
t.pos.y = off_y + t.offset.y;

/* Plant child node /
c = t.child;
if(c != null) {
plantTree(c, t.pos.x, t.pos.y);

/ Plant sibling nodes */
s = c.sibling;
cur_y = t.pos.y + c.offset.y;
while(s != null) {
plantTree(s, t.pos.x + c.offset.x, cur_y);
cur_y += s.offset.y;
s = s.sibling;
}
}
}

/**
* PG 05/1999 : compute the maximum y offset to the right (or bottom)
* of the tree (to put the tree at the most left part (we go down
* along the first branch).
/
int computeMaxOffset(WNode t, int y) {
WNode c, s;
int cur_y;
int current_pos_y;

current_pos_y = y + t.offset.y;

c = t.child;
if(c != null) {
int min=computeMaxOffset(c, current_pos_y), newmin=min;

/ Plant sibling nodes /
s = c.sibling;
cur_y = current_pos_y + c.offset.y;
while(s != null) {
newmin=computeMaxOffset(s, cur_y);
if (newmin min=newmin;
cur_y += s.offset.y;
s = s.sibling;
}
return min;
} else
return current_pos_y;
}

void paintFullTree(Graphics g, WNode t, NodeDrawer nd) {
if(t == null) {
System.out.println("paintFullTree::null tree.");
return;
}

g.setColor(Color.black);

paintTree(g, t, nd);
}

void paintTree(Graphics g, WNode t, NodeDrawer nd) {
nd.drawNode(g,t);

if(t.parent != null) {
int x1 = t.pos.y + t.height / 2;
int y1 = t.pos.x;
int x2 = t.parent.pos.y + t.parent.height / 2;
int y2 = t.parent.pos.x + t.parent.width;
nd.drawArc(g,x1,y1,x2,y2,t.arclabel);
}

/ Draw siblings, using the main child's x-offset. /
if(t.sibling != null) {
paintTree(g, t.sibling, nd);
}

/ Draw children */
if(t.child != null) {
paintTree(g, t.child, nd);
}
}
}

-------------

Usre ID
Password
Gender
Name
Address
Zip Code
E-mail
Telephone Number