Wednesday, March 26, 2008

Project 3c

Due Date: Monday, 28 April (firm!)

Team project

Objectives

An understanding of

Description

In this project, you will refactor your implementation of the simple API for drawing graphical shapes from project 3b. Then you will describe your experience in a brief report.

Refactoring part (60%)

Your job is to perform the following refactorings on your (possibly revised) project 3b submission:
  • Encapsulate the Shapes classes with/inside an Abstract Factory.
  • Replace instance methods with a Visitor:
    • Introduce a ShapesVisitor interface with visitation methods for all Shape variants.
    • Replace the size, getBoundingBox, draw, and fill methods in the Shape interface and all implementing classes with an accept method for the visitor.
    • Create visitor implementations that provide the functionality of these four methods.

You should proceed in very well thought-out, small steps in such a way that you preserve the correctness of your code with respect to the unit tests. At some points in this process, however, you will have to refactor the tests themselves to keep them consistent with your code.

Writing part (40%)

  • Study the references provided above for code smells and refactorings.
  • (10%) Describe the refactoring steps you performed in detail.
  • (5%) Compare the code before and after the refactorings (which is easier to understand? easier to modify?)
  • (5%) Discuss briefly whether or not the Eclipse refactoring tools helped with this activity.
  • (5%) Evaluate your experience with this refactoring activity, including the team experience and the process of refactoring existing functionality.
  • (5%) Identify any other code smells that are still present in project 3c and suggest specific refactorings that should be applied to remove the smells.
  • (5%) Discuss whether there is any tension between the two refactorings, given that the visitor pattern enables a client to add its own operations on a composite.
  • (5%) Be sure to write effectively, following the general guidelines and the theoretical or practice article form from this resource. Your work is evaluated based not on length, but on accuracy, conciseness, and style. You should aim for a total of two to three pages.

How to submit

Please refer to the online submission procedure. Each team is to make exactly one submission. The written paper must be submitted either as a PDF document or through Google Docs.

Project 3b

Due Date: Monday, 14 April (firm!)

Team project

Objectives

An understanding of
  • Requirements analysis
    • functional requirements
    • nonfunctional requirements
    • constraints/goals
  • Modeling
    • UML class diagrams
    • UML sequence diagrams
  • Design patterns
    • Designing to an interface
    • Composite pattern
    • Decorator pattern
  • Java coding
    • final-correctness
    • anonymous inner classes
    • basic Java AWT graphics

Description

In this project, you will complete the implementation of the simple API for drawing graphical shapes. The API design is based on the requirements from project 3a, with some minor modifications. See also the practice midterm and its solutions, on which this project is based.

As discussed in class, I will send the code skeleton for this project directly to your team as soon as you notify my of your submission of project 3a.

Functional requirements

The functional requirements are embodied in the JUnit tests in the test folder. If your code passes all the tests, you will have fulfilled the functional requirements for grading purposes. If some of the tests do not pass, you will receive partial credit.

Specifically, complete the code in the various Java source files within the src folder. Look in the Eclipse Tasks view for sections marked as "your job" and use the test cases as your guide. Besides other minor tasks, the main implementation tasks are:
  • Implementing the int size() method in the Shape interface and all implementing classes
  • Implementing the missing classes Outline, Point, and Polygon
    • The Outline decorator does the opposite of the Fill decorator: it indicates that its shape should be drawn in outline (default) mode.
    • A Point is a location without a shape. You should implement it using a Circle with radius 0 as its shape and override any methods as needed.
    • A (closed) Polygon is a shape defined by a list of points. Implement it as a special case of Group.
As usual, you must not make any other changes to the code skeleton or the test cases.

Sequence diagrams

Using a modeling tool or general drawing tool of your choice, draw sequence diagrams representing the following method invocations:
  • s.size() in TestSize.testGroupSimple
  • s.draw() in TestDraw.testSimple (be sure to include the Graphics object in the diagram)

Grading

  • 10% code skeleton
  • 10% inline and Javadoc comments (be sure to run Javadoc)
  • 60% functional requirements
  • 20% sequence diagrams

How to submit

Please refer to the online submission procedure. Each team is to make exactly one submission.

Project 3a

Due Date: Friday, 4 April (firm!)

Team project

Objectives

An understanding of
  • Requirements analysis
    • functional requirements
    • nonfunctional requirements
    • constraints/goals
  • Modeling
    • UML class diagrams
    • UML sequence diagrams
  • Design patterns
    • Designing to an interface
    • Composite pattern
    • Decorator pattern
  • Technical writing: form, style

Description

In this project, you will analyze the requirements for a simple API (application programming interface) for drawing graphical shapes and produce an analysis model in the form of a class diagram. There is no coding in this project, but you will implement the resulting API in the next project.

Functional requirements

The API allows you to create circles and rectangles of different sizes, foreground colors, and background (fill) colors at different locations on a coordinate system. In addition, the API allows you to group multiple shapes together and treat them (in terms of specifying location or color) as if they were a single shape.

The shapes created using this API (including groups or shapes and shapes with specific colors or at specific locations) have the following capabilities (responsibilities):
  • drawing the shape to a visual drawing area
  • computing the shape's bounding box, defined as the smallest enclosing rectangle

Nonfunctional requirements

The API implementation must avoid duplication of features or responsibilities across classes and provide high flexibility by using suitable design patterns.

In particular, you can apply any combination of the following additional structural elements to any shape (simple or grouped):
  • location information
  • foreground color
  • fill color
  • grouping with other shapes
Furthermore, any resulting shape structure uniformly supports the draw and boundingBox operations described above.

Constraints/Goals

The analysis model should translate readily into a set of Java types (classes and interfaces).

Examples

The following code snippets illustrate the vision for how the API will be used.

Shape s = new Group(
new Foreground(Color.BLUE, new Rectangle(20, 10)),
new Location(100, 0, new Group(
new Background(Color.RED, new Circle(5)),
new Circle(10),
new Circle(15)
));
Graphics g = ...
s.draw(g);

The resulting shape (see screenshot at the top, which also includes the bounding box) will consist of
  • an unfilled rectangle of width 20 and height 10 and a blue outline with the top left corner at the origin (in Java, the y-axis extends downward)
  • three concentric circles of radii 5, 10, and 15, respectively, 100 units to the right of the origin, where the two outer circles are unfilled and the inner one is filled with red color

Deliverables

There are two deliverables for this project:
  • (50%) A detailed UML class diagram showing your analysis model. The diagram should show any relationships among classes (in some cases, there is more than one relationship between two classes). Furthermore, the classes in the diagram should include the following elements where applicable:
    • operations (methods)
    • attributes (instance variables)
  • (50%) A brief paper describing the analysis and modeling process you went through, including:
    • (15%) Your rationale for identifying/choosing exactly those classes shown in your diagram.
    • (15%) For each design pattern you choose to apply, a brief explanation of the problem this pattern solves in the particular context of the shape drawing API.
    • (10%) Any other comments, reflections, questions, doubts, or other thoughts you have at the end of this process.
    • (10%) Be sure to write effectively, following the general guidelines and the theoretical or practice article form from this resource. Your work is evaluated based not on length, but on accuracy, conciseness, and style. You should aim for a total of two to three pages.

Modeling software

You may produce your class diagram in any one of the following ways:
  • Draw by hand and scan to some image format or PDF.
  • Draw using a general drawing program such as Microsoft Visio.
  • Draw using a modeling tool such as ArgoUML (free).

How to submit

Please refer to the online submission procedure. Each team is to make exactly one submission. The written paper must be submitted either as a PDF document or through Google Docs. The class diagram must be submitted both in the tool-specific format and a general image format or PDF.

Friday, March 14, 2008

Basics of Object-Oriented Programming in Java

Reference semantics vs. value semantics

  • Value semantics: variables directly contain values.
  • Reference semantics: variables contain addresses that refer (point) to objects.

Equality vs. identity

  • Equality: are two (possibly) different objects equivalent?
  • Identity: do two references refer to the same objects?
  • How are equality and identity related?

Inheriting from java.lang.Object

Implementing classes are usually required to provide the following methods:

  • toString
  • equals
  • hashCode
  • clone (if the objects are mutable and cloning is required)
  • compareTo (if a default ordering is required)

Packages

  • Mechanism for grouping related or collaborating classes (cf. default package-level member access).
  • Implemented as mapping from fully qualified class names to file system.

Member access

  • public
  • protected
  • default (package)
  • private

Subtyping vs. subclassing/inheritance

  • Subtyping allows substituting a more specific object for a more general one.
  • Inheritance is a mechanism for a subclass to reuse code from a superclass.
  • Inheritance usually enables subtyping. But it is not the only way to enable subtyping; implementing or extending an interface are other ways.

Static vs. dynamic type

  • Static type: declared type of a variable.
  • Dynamic type: actual type of the object to which the variable refers.
  • How are static and dynamic type of a variable related?
  • Casting: treat an object as if it had a different static type. Three different situations: downcast, upcast, crosscast.

Class-interface continuum

  • Concrete class: can be instantiated. All specified methods are fully implemented.
  • Abstract class: cannot be instantiated. Some or all of the specified methods are not implemented.
  • Interface: limit case of a fully abstract class for specification purposes only. None of the specified methods are implemented, and there are no instance variables (only class-level constants).

Relationships between classes

  • is-a: subtyping
  • has-a: aggregation, composition
  • uses-a: dependency

Clone in the context of the Composite pattern

In general, cloning allows you to make a copy of an object. The clone method in Java is similar to the copy constructor in C++, but it is an ordinary method, unlike the copy constructor. Once you have the original object and its clone, then you can modify each one independently.

Cloning models the real-life situation where you build a prototype of something, say a car or a piece of furniture, and once you like it, you clone it as many times as you want. These things are composites, and the need to be cloned deeply (recursively).

As another example, imagine a parking garage with a list of cars that have access to it. To build another garage to handle the growing demand, you can clone the garage and the access list. But the cars should not get cloned. That's because the garage is not composed of the cars.

As we can see, the conceptual distinction between aggregation and composition has significant consequences for the implementation of the relationship. True, both relationships are represented as references in Java. However, composites usually require a deep clone (if cloning is supported): each parent is responsible for cloning its children.

Note also that you don't need to clone at all if your objects are not mutable because you wouldn't be able to distinguish the original from the clone anyway.

Saturday, March 8, 2008

Project 2b

Due Date: Monday, 24 March

Team project

Objectives

  • Design patterns
    • Builder pattern (simple version)
    • Iterator pattern
    • Adapter pattern
    • Decorator pattern
  • Refactoring
  • Effective Java, items 4, 7, 8, 9, 12, 13, 14, 15, 23, 25, 27, 28, 29, 30, 34, 37
  • Technical writing: form, style

Description

In this project, you have the opportunity to perform a refactoring of your project 2 submission. Since this one is a team project, you should pick the better of your two submissions or combine them in some way as a starting point. The other starting point is the project WordOccurrencesRefactored from the CVS example repository.

This project consists of a coding part and a writing part. Specifically, your coding job is as follows:
  • (15%) Fit the functionality from the DefaultIndexImpl class in your project 2 into the right places of DefaultIndexImpl in the new skeleton. Because the new version of DefaultIndexImpl is not allowed to inherit from Map anymore, you will have to add one or more suitable instance variables to the class. You are done as soon as all tests in TestDefaultIndexImpl pass.
  • (10%) Then copy all remaining classes from your project 2 into the corresponding places in the new skeleton. The only change you should have to make to make everything work is changing the test fixtures s7index and s8index from type Map to type Index; this can be achieved by a relatively minor conversion from Map to Index at the end of getS7Index and getS8Index, respectively. You are done as soon as all tests pass (to the extent they passed in your project 2 submission).
  • (5%) Correct the (unintentional!) typo in the word "occurences" in the package name. Use Eclipse's refactoring capabilities to make this step completely painless.
  • (5%) Make sure you keep the proper skeleton structure.
  • (5%) Generate the javadoc.
Your writing job is as follows:
  • Study the references provided above for code smells and refactorings.
  • (10%) Identify which major code smell was present in the project 2 skeleton and which refactoring was used to get from project 2 to project 2b. (one detailed paragraph)
  • (5%) Identify any other code smells that are still present in project 2b and suggest specific refactorings that should be applied to remove the smells. (one or more brief paragraphs)
  • (5%) Identify any code smells that were removed in the transition to project 2b, along with the refactorings used to remove the smells. (one or more brief paragraphs)
  • (20%) For each of the Effective Java items listed above, give a brief example from project 2b (referring to specific methods or other elements in your code); in each case, indicate whether the examples satisfies the item or fails to satisfy the item. (one very brief paragraph for each item)
  • (5%) Indicate where you used Decorator pattern in project 2b and explain what problem it solves.
  • (10%) Describe your experience with the coding part of this project, including the team experience and the process of refactoring existing functionality.
  • (5%) Be sure to write effectively, following the general guidelines and the theoretical or practice article form from this resource. Your work is evaluated based not on length, but on accuracy, conciseness, and style. You should aim for a total of two to three pages.

How to submit

Please refer to the online submission procedure. Each team is to make exactly one submission. The written paper must be submitted either as a PDF document or through Google Docs.

Wednesday, February 20, 2008

Project 2

Due Date: Thursday, 13 March

Individual project

Objectives

Description

Code Skeleton/Architecture (10%)

A code skeleton has been set up for you. Check out the project WordOccurrences from the CVS example repository. This will create a project WordOccurrences in your workspace with the following folders:

  • doc : documentation generated by javadoc
  • src : Java sources for the packages
  • test : Java sources for the JUnit tests
  • bin : compiled Java byte code

You are required to retain the structure of this skeleton. In particular:

  • You must not change the given folder hierarchy, nor the public specifications of the interfaces and classes used by the test drivers. You must not change the test drivers either, but you are welcome (and in some cases required) to add your own test drivers.
  • You must not print any output from any of the classes (other than during your own testing).

Documentation (10%)

Your project must be documented using javadoc and using inline comments where appropriate.
Document only the code that you added or modified, including any fields you added, then rerun the javadoc wizard from the Eclipse Java perspective as follows:

  Project > Generate Javadoc...
types: [x] WordOccurrences
visibility: (x) private
destination: .../WordOccurrences/doc

Functionality (50%)

You are required to complete the functionality of the skeleton.

  • Complete the code in the various Java source files within the src folder. Look in the Eclipse Tasks view for sections (methods or entire classes) marked as:
      TODO your job

    You are done with this part when your code passes all tests (please see also below on testing).

  • Do not make any other changes (other than adding more tests). In particular, you are not allowed to change the various top-level interfaces.

Testing (30%)

In this project, we are using JUnit for unit testing and overall system testing. In the test-first approach we are using here, you focus on one class at a time until it passes all the tests.

For example, while you are working on edu.luc.cs.laufer.cs313.occurrences.DefaultIndexImpl, you will repeatedly run edu.luc.cs.laufer.cs313.occurrences.TestDefaultIndexImpl.

You can run the tests using Eclipse's built-in support for JUnit testing. In the Eclipse Package Explorer, right-click on a test class (basically any class in the test folder) or an ancestor node of a test class and choose from the resulting context menu:

  Run > Run As > JUnit Test

The test will now run in a special runner you can access through the JUnit tab. The JUnit runner has two tabs: failures and hierarchy. You can make changes to your code and rerun the test by pressing the button with the runner figure again.

In addition, you are required to complete those tests marked as:

  TODO your job

(If you are not using Eclipse or any other IDE with support for JUnit, you will have to write your own driver with a main method. The JUnit FAQ explains how to do that; look in this section.)

How to submit

Please refer to the online submission procedure.

Sunday, January 27, 2008

Project 1

Due Date: Thursday, 14 February

Individual project

Objectives

Project Description

The starting point for this project is the generic java.util.Map interface. Your job is as follows:
  • (10%) create a Java project in Eclipse
  • (15%) develop a comprehensive JUnit 4 test case for the Map interface
  • (5%) using inheritance, create one specialized version of the test case for each of the following implementations:
    • java.util.HashMap
    • java.util.TreeMap
    • java.util.LinkedHashMap
  • (40%) based on another specialized version of the test case, develop your own implementation, ChainedHashMap, using a fixed-size hash table with chaining
  • (10%) develop a performance evaluation class for the Map interface
  • (10%) apply the the performance evaluation to all four implementations (see details below)
  • (10%) provide sufficient documentation in the form of inline and Javadoc comments

Additional requirements

  • Make sure your project has separate src and test folders and refers to JUnit 4 as a library.
  • Implement the Map interface as a hash table with chaining using java.util.LinkedList.
  • Ignore the three view methods (entrySet, keySet, and values) in the Map interface for the purpose of this project, including testing. Your implementation should throw a java.lang.UnsupportedOperationException in the body of these methods.
  • For each of the remaining 11 interface methods, you need at least two test methods. For example, test isEmpty on an empty and a non-empty map.
  • Unlike the existing Java map implementations, your implementation must provide a constructor that allows you to pass the hash function as an argument when an instance your class is created. The constructor should also take the table size as another argument.
  • Represent hash functions as objects with the following generic interface:
interface ToInteger<T> {
int apply(T arg);
}
  • Implement the following hash functions for integer keys:
    • last two digits
    • last three digits
    • digit sum (e.g. digitSum.apply(1234) returns 10)
    • modulo some positive number
  • Use System.currentTimeMillis() to calculate running times.
  • Measure the performance as follows:
    • create another JUnit 4 test case for this purpose
    • using the @BeforeClass and @AfterClass annotations, create the following "permanent" fixtures:
      • one (long) LinkedList of random keys to insert (partially) into the map
      • one (not so long) LinkedList of random keys to query the map for
    • write an auxiliary method void doMeasure(String label, Map map, int n, int r) that inserts a specific number, n, of keys (using some dummy value to map to) from the first list, measures the performance for a given large number, r, of retrievals from the second list, and prints the result using the given label
    • for each configuration of map implementation, table size (in the case of your implementation), and hash function (in the case of your implementation), write a @Test method that configures the map instance and performs the measurements for the various numbers of insertions
  • Specifically, measure the following configurations:
    • java.util.HashMap
    • java.util.TreeMap
    • java.util.LinkedHashMap
    • ChainedHashMap, last two digits, size 100
    • ChainedHashMap, last three digits, size 1000
    • ChainedHashMap, digit sum, size 100
    • ChainedHashMap, modulo 101, size 101
    • ChainedHashMap, modulo 1009, size 1009
    • ChainedHashMap, modulo 10007, size 10007
    • ChainedHashMap, modulo 100003, size 100003
  • and the following number of insertions:
    • 100
    • 1000
    • 10000
    • 100000
    • ...
  • choose the number of retrievals, r, globally such that your smallest measurements are at least 100 milliseconds
  • choose the maximum number of insertions such that the longest running times stay around a minute or below

Submission