Task
Scenario
Binary Search Trees (BSTs) and their kin can be used in many different scenarios. We’ll use them to implement fast searches and views into an array of objects, using data of several different data types for indexed attributes.
We’re given a starting data set of wearable devices, falling into various categories like health, fitness, lifestyle, etc. The sample file (wearables.txt) has over five hundred such devices.
The simple text file contains:
- An integer on the first line, telling how many items are in the file.
- A header line, describing the contents of each attribute given per item. This is for your information; you don’t need your code to utilize it.
- Wearable items, one per line, with attribute data delimited by “@”.
Indexes
Data Used
We want fast searches and index-based views into the Wearable data using three different indexes:
- Ranking - the wearable devices are ranked by consumers, from 1 to n. These rankings will always be unique (you don’t have to check for that; just assume it).
- Price - device prices vary greatly, and aren’t unique. If the price isn’t known, a price of -99.99 is provided in the file.
- Company Name - some companies produce many items; some, only one or two (i.e., these aren’t unique). We want an easy way to find and display those.
Building the Indexes
You’ll need a BST for the ranking index. Each node must carry both the index data (rank, in this case) and the array index at which that Wearable exists in the array. For example, the first item in the file is ranked 548, but will live at index 0 in the array.
For the other two indexes, you’ll need to get more creative, as there will be repeated data. But like the ranking index, the nodes you’ll primarily rely on must carry both the index data (price, and company name, respectively), and the array index at which that data is found.
Services
Index will provide two basic services:
- The index will allow client code to search for index data and retrieve the array index at which that data is found (or a negative number, if the index data is not found). In cases where multiple items may share the same index data, return the index of any single item that matches.
- The index will allow the generation of a list (packaged into a single string) that shows the items as seen through the lens of the index. This list will be sorted (“free” if you traverse the tree properly), and should be attractive. Remember that with price and company name indexes, there may be multiple items that will fall together; take some time and ensure the result makes that grouping clear to the eye.
Design Documentation
Don’t underestimate the design requirements of this project; they are substantial. Before you code, create appropriate design documentation and obtain feedback. Update designs per feedback, then use them during the rest of the development process, and submit them as part of your project. For this project, this you’ll need a UML Class Diagram and UML Object Diagram.
Code Implementation
Building Blocks You’ll Need
- Binary and k-ary Search Trees
- Generics
- Recursion
Requirements
Here are requirements for your coding project:
- Each Wearable should become its own object. Provide accessors for everything. You may skip mutators, assuming one full-bodied constructor is sufficient for now.
- A separate class, Wearables (with no constructor parameters), manages an array of these objects (created while reading the file), and call for the creation of the various indexes described below. Don’t proliferate FileNotFoundException throws from the reading method; if it fails, the array is just empty.
- In a Main class, after instantiating the Wearables object, write some code that demonstrates the find and viewing capabilities of each index.
- Each of the three indexes should have its own class. Each constructor should populate its index. They should do this without re-reading the file; the Wearable array is the basis for index work.
- You’ll need two basic types of nodes, one for the unique index, one for the non-unique indexes. Do not create separate classes of nodes for each type of data indexed, however; instead, create node classes that will provide flexibility and allow instantiation using any necessary data type, including those we need now or might need in the future. For the non-unique indexes, you’ll want an additional node type that should become apparent as you design.
- Use no public data except in nodes; we understand that navigation through nodes requires public access.
- Implement no sorting algorithms anywhere in this project.
Style
Follow the Course Style Guide. You’ll lose points on every assignment if you fail to do so.
Testing
Take a break from the usual JUnit unit tests. If you get the whole thing working properly, we’ll assume you’re darn close on most of these objects and their methods.
Submitting Your Work
In Canvas, submit a compressed file (.zip or .jar) containing the full contents of your project folder. If creating with BlueJ, make sure and choose “Include source.” Include final design documentation (discussed here) in your submission.
Hints
- Before starting this project, incorporate feedback from your designs; you should start building on a firm foundation.
- There will be code that is repeated (or awfully similar) in all three index classes. Because of data type differences, this is a hard issue to overcome. I suggest you don’t try to further “generify” indexes; it’s a rabbit hole that you don’t have time for at this point.
- Apart from the issue discussed in the previous bullet point, don’t repeat code; be smart and leverage existing code.
Extra Credit
In addition to allowing only index-based list generation for the entire array of wearables, provide an overloaded method which allows the client to specify an inclusive range of values. For example, the client might want a list of only the top 20 items by rank (minimum is one, maximum is 20). For prices, they might want items priced from $0.01 to $99.99. For companies, they might want companies “Archos” through “Casio”.