Summary of notes + links to samples for CSC 365

• Review some of the material covered at the tail-end of CSC241 relevant to the project #0. Set interface, Comparable interfaces are going to be discussed along with some of the methods in the Tree class implementation of it. Set.java, Tree.java, and treeNode.java should be reviewed. Also review the Writing Applications with Sets section of the Lecture set #14 from csc241.
• Consider the StringTokenizer class for identifying and grabbing the words in a line of input for project zero.
• Employee Application will be discussed. This application initially loads employee records into a Set object from employee file; it provides the user with a menu of options that let him perform add/update/remove operations on individual employees or perform wholesale operations on them like give pay raises to all of them. This program regenerates the employee file before exiting. Keep in mind that the import statement at the top for the Set package needs to be different in your case (i.e. your Set package is expected to be in a different location).

• The following two examples JustQuits and JustQuits 2 demonstrate two ways of handling events. justQuits defines a quitsHandler class that implements ActionListener; This version requires a number of extra steps to establish the relationship between the button in the justquits class and the quitHandler class as the listener for it. The justQuits2 avoids those steps by using the anonymous class concept in creating the action listener.
• Use the Swing Tutorial to get acquainted with the Swing classes. Download Swing Application and compile/run it.
• The SolarSystem demonstrates the use of some Swing components including JTree, JTable, JScrollPane, and JSplitPane. Additionally, this example introduces Hash, HashMap, and DefaultMutableTreeNode. a snapshot of the application window.
• The Demo Swing is a more complex example for Swing with multiple components that needed to be placed on the frame associated with the application. Here is an snapshot of the application window.

• Container interfaces Map and Set are introduced.
• The Set interface allows for storage and retrieval of objects. It is most useful when objects implement Comparable and kept as unique entities in a Set.
• The implementation of Sets are discussed: TreeSet. TreeSet objects maintain the elements in their natural order, red-black tree is the internal implementation for this class. dictionary.java show how word/meaning can be stored in a set object. dicElement that implements Comparable and holds word and meanings. For every word/meaning read from an input file, an object is created and added to the set in the dictionary application. Use of other methods from the Set interface are also demonstrated.
• The Map interface allows for storage and retrieval of objects like Set did, except it is better suited when a mapping between a key and "value" associated with that key needs to be maintained.
• The implementation of Map is discussed: TreeMap.
• dictionary2.java displays the same exact functionality as the dictionary application, except that it uses a Map to hold words as keys and meanings as values mapped to via the words.
• The Swing Version of the Employee Application demonstrates the use of Maps and Sets and, of course, Swing. Here is an snapshot of the application window.

• File systems and their relationship with the operating system was mentioned; its role in managing files and interacting with external storage media was also introduced. We also talked about how disk and tape drives operate.
• The smallest unit of data read from or written to disk is a sector. We address a sector using the cylinder#, Track#, and Sector#. The disk drives in response to a read or write request, first, seeks the appropriate location on disk by getting the RW-head to the correct address first and then performing the requested operation and transmitting the data to an input buffer in memory (read) or storing the data sent to it on to the disk (write).
• We discussed bitMaps and Extents as File Allocation Tables (FAT).
• Basic File System are introduced. BFS knows files as a sequence of blocks and doesn't much care about the content of each block. It also knows devices (disk, tape, etc) and how it should communicate with them. The basic operations of BFS: CreateFile, OpenFile, ExtendFile, CloseFile, DeleteFile, ReadBlock, and WriteBlock are discussed.
• Access methods, such as, Sequential, and Random access are introduced. In discussing Sequential files, single-buffering and multi-buffering techniques for reading and writing records were discussed.
• Files are clearly a reasonable source for providing persistence for information. Java allows us to perform sequential file read/write operations on objects. We'll discuss ObjectInputStream files.
  1. A class must be Serializable in order write its objects to an objectFile. Serializability of a class is enabled by the class implementing the java.io.Serializable interface. Classes that do not implement this interface will not have any of their state serialized or deserialized. All subtypes of a serializable class are themselves serializable. The serialization interface has no methods or fields and serves only to identify the semantics of being serializable.
  2. As an example, dicElement class is serializable. This class was used previously in our dictionary.java example to keep word/meanings, its serializablity was not used in that example. The programs, readObjectFile.java reads objects of dicElement from a file that contained them and displays word/meanings that they hold. createObjectFile.java opens a text file with words/meanings in it and creates the object file with dicElement objects.
• In discussing Random access files, we'll look at Random Access File in Java. With this access method, we could seek the correct location of the file and read/write there. To start with, we'll introduce a filter for this class fixedLengthRecordRW class that allow for reading and writing of fixed length record based on a record number. A Fixed-Length-Record file is treated like an array with the ability to access records based on their record number. Two important differences: as we use RAF to implement this class, this file can be extended (enlarged) implicitly by adding records beyond its EOF. Also, the most obvious difference is that changes made to the records are permanent. testRAF program show you how such files are created and read from.
• Project #2 will be discussed.

Red-Black Tree was defines as a BST that...

• Root is always Black.
• No red Node may have a red child.
• Black-depth of all external nodes is the same.

Insertion starts just like a BST insertion. All new nodes are added as red in a Red-Black tree; obviously, if the node is inserted to the left or the right of a node that is red; we end up with a double-red problem right away. The problem is resolved with a recoloring or restructuring. When we recolor, we may propagate the problem up the tree causing further recoloring or restructing. We do a trinode-restructuring when the sibling of the red parent in a double-red context is black; we recolor when the sibling is red.

Deletion starts just like a BST deletion. If the node that we delete is red; there is no impact on the black-depth of the tree; thus, we are already done. If the node we are deleting is black but has one red child; then the red child takes the place of the deleted node and gets colored black; again, the black depth is not affected. We run into the double-black problem when we delete a black node with a black child. Three cases are identified: 1. Root of the sibling side is black; but, it has a red child. 2. Root if the sibling side is black but has no red child. 3. Root of the sibling is red. Case 1. is solved by restructuring. Case 2. is solved by recoloring. Case 3. is solved through adjustment that turns the problem into case 1. or case 2.

Coding RBtree was discussed and the example RBtree.java was examined.

AVL Tree

An AVL tree is another balanced binary search tree named after the inventors, Adelson-Velskii and Landis. AVLs were the first dynamically balanced trees to be proposed, like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(log n) time.

Definition of an AVL tree:

• An AVL tree is a Binary Search Tree which has the following properties:
  1. The sub-trees of every node differ in height by at most one.
  2. Every sub-tree is an AVL tree.

BTREE: