Java代写：CS2510 Function objects, generics, and design practice

发表于   |   分类于

代写Java的基础练习题，包括sorting, binary search tree以及小游戏Sokoban.

Instructions

As always, be careful of your naming of classes, interfaces, methods, and files.

Function objects, sorting

Without using generics, design an interface and classes representing a list of strings. Name this file Strings.java.

  • Design the interface IStringsCompare that contains a method

  • Design a function-object class StringZetabetComp that implements this interface by comparing the Strings reverse-lexicographically: in other words, “zebra” comes before “zany”, and longer words come before shorter ones.

  • Design a function-object class StringLengthComp that implements this interface by comparing the Strings by their length from the shortest to the longest.

  • Design a method isSorted that confirms whether this list is sorted. It should work for either comparison.

  • Design the method merge to merge this sorted list with the given sorted list, producing a new list containing the elements of the two lists sorted according to the given comparison. (This is very similar to a problem on a prior homework…) You should not implement this method by using sort.

  • Design the method sort that produces a sorted list, in the order given by the given IStringsCompare function object.

  • Design the method sameList that takes a given list and returns true if the two lists contain the same data in the same order.

Using generics, design a generic list interface IList and classes that implement it. Name this file StringsGen.java.

Using the following interface, revise your answers to the problems above:

1
2
3
4
5
6
interface IComparator<T> {
    // Returns a negative number if t1 comes before t2 in this ordering
    // Returns zero              if t1 is the same as t2 in this ordering
    // Returns a positive number if t1 comes after t2 in this ordering
    int compare(T t1, T t2);
}

Hint: you will need to change the signature for sameList — how can you check if two values of type T are the same?

Since you cannot have two classes with the same name in the same project, rename the comparators that implement generic interfaces StringLengthCompGen and StringZetabetCompGen.

Function objects, binary search trees

You will work with a binary search tree that represents a collection of Book objects. Remember, a binary search tree represents an ordered collection of data where each node holds one data item and has links to two subtrees, such that all data items in the left subtree come before the current data item and all data items in the right subtree come after the current data item. Binary search trees are generic over the type of data they contain.

The tree with no data is represented as a leaf.

Start a new project and define in it the class that represents a Book as shown in the class diagram below. We want to keep track of the books in several different ordered ways - by title, by author, and by price.

For brevity in this assignment, and because every node in a BST must know about how the ordering works, we’ve included an IComparator as a field of the abstract base class of BST nodes and leaves, rather than only using an interface.

  • Design the classes BooksByTitle, BooksByAuthor, and BooksByPrice that allow us to compare the books by their title, their author, or price respectively. String-based comparisons should be alphabetical; numeric comparisons should be by increasing value.

  • Design the classes that represent a binary search tree of books, following the class diagram shown above. Make examples of data. (In this example we use an abstract class, rather than an interface, because we need the order field.) To be clear: you are designing generic classes for this problem, even though the problem is only discussing trees of books.

  • Design the method insert that takes an item and produces a new binary search tree with the given item inserted in the correct place. If the value is a duplicate according to the tree order, insert it into the right-side subtree. This should work for any of the comparators above. (Where should the newly created nodes obtain their ordering from?)

  • Design the method getLeast that returns the smallest item (according to the tree order) contained in this tree. In the Leaf class, you should throw an exception: throw new RuntimeException(“No least item of an empty tree”)

  • Design the method getAllButLeast that returns the tree containing everything except the least item of this tree. In the Leaf class, you should throw an exception: throw new RuntimeException(“No items in an empty tree”)

  • Design the method sameTree that determines whether this binary search tree is the same as the given one: that is, they have matching structure and matching data in all nodes.

  • Design the method sameData that determines whether this binary search tree contains the same books in the same order as the given tree.

  • Copy into your project the IList interface and its related classes. Make examples of IList, including examples that contain the same books (in the same order) as some of your binary search trees.

  • We would like to know whether a binary search tree of books contains the same data as a list of books.

  • Design the method for the binary search trees sameAsList that consumes a list of books and determines whether the binary search tree contains the same books as the given list (in the same order).

Hint: There are two ways how this can be done.

The first one is to add the methods isEmpty(), getFirst(), and getRest() to the classes that represent the list of books. But we know this is not the best way to do this.

The second is to first design the method buildList below, then compare the resulting list with the one given before.

  • Design a buildTree method for the classes that represent a list of books. The method consumes a binary search tree of books, and inserts into it all items in this list, returning at the end a binary search tree that contains all items in this list.
    If this method is invoked with a binary search tree that is a Leaf, then the resulting tree should be the sameAsList when compared to the sorted version of this list.
    So, for example, the list (b3, b1, b4, b5) would produce the tree bstD shown above.

  • Design the method buildList for the classes that represent the binary search tree that consumes a list of books and adds to it one at a time all items from this tree in the sorted order. (If we invoke this method with an empty list, we end up with a list of all items in this tree in the reverse order.)

Sokoban

Many of you had difficulty last week working on the game problem: rather than focusing on the data representations, people got distracted by problems with making the images work. This problem asks you not to implement anything, but merely to design another game: think through the data definitions that are needed and the methods on them that are required to implement the game logic, but don’t worry about details on how the images or event handlers are supposed to work.

Design but do not implement the game “Sokoban”. Sokoban is a puzzle game in which the player pushes boxes around a warehouse, with the goal of placing the boxes on specific targets. You can play the game online here — also read the How to Play guide.

As a hint to get you started, you should design your world so that you can keep track of at least the following information:

  • The shape of the warehouse (where the walls are),
  • The boxes,
  • The targets,
  • The player,
  • And anything else that you feel will be necessary for game play!

Some tricky things to keep in mind:

  • The boxes can still move after they have been placed on a target, but while they are on a target they should be displayed differently so the user knows they are on a target
  • The player cannot push two or more boxes at once
  • The game ends when a player has pushed all the boxes onto targets

Your design must cover the Controls, the Puzzle Types, and the Essentials; it does not need to support the Objects described here.

You should submit a Design.txt document which describes each of the classes in your design and what they all do. If you think it’s helpful, include an ASCII-art class diagram to show the relationships between the classes.

Your design must include templates for all of your classes. Since you are not implementing these methods, this is essentially asking you for a comprehensive wish list of the methods you think will be necessary for the game. This does not mean that you should wish for hundreds of methods in the hope that they might be useful. Rather, you should provide a rationale for them by explaining for each method which other methods need it.