\documentclass[noanswers,addpoints,11pt]{exam}
\usepackage{soul}
\usepackage[xetex]{hyperref}
\usepackage[table,usenames]{xcolor}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{cancel}
\usepackage{datetime}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage[margin=0.85in]{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{makecell}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{pstricks}
\usepackage{tabularx}
\usepackage[most]{tcolorbox}
\usepackage{textcomp}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,decorations.pathmorphing,backgrounds,positioning,fit}
\usepackage{xltxtra}

% compact itemized and then enumerated
\setlist{leftmargin=*,
  noitemsep,
  topsep=5pt,
  parsep=0pt,
  partopsep=0pt,
}

\setlist[enumerate]{leftmargin=*,
  itemsep=2pt,
  topsep=0pt,
  parsep=0pt,
  partopsep=0pt,
}

% ----- Fonts -----
\usepackage{fontspec}
\defaultfontfeatures{Scale=MatchLowercase}
% - CONDITIONALLY USE LADDBC FONTS
\IfFontExistsTF{Gentium Book Basic}{
  \setmainfont{Gentium Book Basic}
}{
  \setmainfont{Times New Roman}
}
\IfFontExistsTF{Comic Code}{
  \setmonofont{Comic Code}[
  Scale = 0.85,
  ]
}{
}

\setsansfont{Arial}

% - LISTING FONT = TTFONT
\lstset{
  basicstyle=\ttfamily,
  language={},
}
% ----- Fonts -----
\newcommand{\checkpoint}{{\Large $\checkmark$} }

% classname
\newcommand\assignmentTitle{pPizza - Polymorphic, Decorated Pizza Simulation}
\newcommand\semester{Fall 2023}
\newcommand\className{Computer Science III}
\newcommand\classNumber{CIS~205}
\newcommand\classFullName{\classNumber~\className}
\renewcommand{\dateseparator}{-}
\yyyymmdddate

% /classname

\pagestyle{headandfoot}
\firstpageheader{\classNumber\\\semester}{\assignmentTitle\\~}{\today\\~}
\runningheader{\assignmentTitle}{}{\today}

\newenvironment{showExample}[1]{
  \begingroup
  \renewcommand{\solutiontitle}{\noindent\textbf{Example:}\enspace}
  \printanswers
  \begin{solution}[#1]
  }{
  \end{solution}
  \endgroup
}

\definecolor{outputgray}{gray}{0.95}


\begin{document}
\pointsinrightmargin{}

\section*{Learning Outcomes}
Upon completing this assignment, students should be able to

\begin{itemize}
  \item Create a \emph{binary search tree} container class with
    \emph{add}, \emph{find}, and \emph{toString}
  \item Store objects in a collection that behave
    \emph{polymorphicly}.
  \item Use \lstinline{git} to commit each ``chunk'' of working
    code. (Make proper use of \lstinline{git}/version control.)
\end{itemize}

\section*{Introduction}

Students will write a \lstinline{OrderedShapes} program that reads a
file full of \lstinline{Shape} objects (class hierarchy below) and
inserts them into a \emph{binary search tree} according to their
\textbf{area}. Then the user can enter commands to search for a shape
with a given area, print out the whole collection in increasing order
by area, print out the whole collection in decreasing order by area,
or quit the program.

\textbf{Note}: Your use of \lstinline{git} is part of the rubric for
this program. You are expected to build your features one at a time,
adding the new/changed \emph{working} code to your \lstinline{git}
repository as you  go along. There should be a fair number of commits
in this repo, each with a \textbf{commit message} stating what was
completed (this can go in the first line of the message; no need to
write a novel).

Second note: the \emph{right} way to do testing is to write tests for
each feature as you go. This would be a good chance to practice this
\textbf{but} you are not obligated to do this.

You can associate your local repo with your repo for turn-in on Gitea
at any point. When you push the repo, the whole history of the project
(all commits along with the date/time, commit message, and user who
made the commit) is pushed. If you have problems pushing changed code,
let Dr. Ladd know and he can help interpret \lstinline{git} error
messages.

\section*{Method}

\subsection*{Getting Started}

Start by creating a new directory for your solution to
\lstinline{F23-205-<ccid>-p005} (you \textbf{will} name the repo on
Gitea with that format; call the directory whatever you want).

Initialize the directory with Gradle. Name the project
\lstinline{tree} and have the source package be \lstinline{main}.
Modify the created project so that the main class is called
\lstinline{main.TreeClientProgram} and so that \lstinline{gradle run} passes
the keyboard in to the running program.

Compile and run the hello world created by Gradle so you feel like
your code works.

\subsubsection*{\texttt{menu.Menu}}
\textbf{Note:} This is to use your simple, text-based \texttt{Menu}
class. This is \emph{not} to use JavaFX, Swing, or any other Java
GUI. If you need assistance with \texttt{menu.Menu}, talk to the
instructor.

Add \lstinline{menu.Menu} (from the first assignment in this class) to
the project. There is only one menu for this program:

\begin{lstlisting}[language={}]
find - find a shape by area
dec - list all shapes in decreasing order by area
inc - list all shapes in increasing order by area
quit - quit the program
\end{lstlisting}

Add this menu to \lstinline{main.TreeClientProgram} while modifying it
to use our standard create-and-run structure. For now, the
\lstinline{run} method should loop, calling \lstinline{match} on the
menu until the user quits. There is nothing else to do right now.

\subsection*{Class Hierarchy}
You will create a new package, \lstinline{shapes} and put three
classes in it. The classes are related as shown in the diagram below:

\begin{center}
\includegraphics[width=0.8\textwidth]{shapes}
\end{center}

\begin{description}[font=\ttfamily]
\item[Shape] The ultimate parent of the hierarchy. Keeps track of the
  \emph{name} of the shape (an identifier) and has an \lstinline{area}
  method that returns zero.
\item[Circle] Keeps a \emph{radius} and overrides \lstinline{area} to
  return the area of the circle.
\item[Rectangle] Keeps \emph{width} and \emph{height}, overrides
  \lstinline{area} to return the area of the rectangle.
\end{description}

These are very short classes. They should have \lstinline{toString}
methods that returns the \emph{type} of the shape, its \emph{name}, and
any specific information for the given type.

\subsection*{Input/Output}
Modify your program to take a \emph{shape file name} on the
command-line. Your program must handle the
\textbf{no-file-named-on-the-command-line} error before calling the
\lstinline{TreeClientProgram} constructor.

The constructor should take and save the data file name.

Modify \lstinline{run} to load data from the file of shapes. Right now
you do not have anywhere to store them. The load method opens the file
and handles the \textbf{file-not-found} error.

The data file has the following format:

\begin{lstlisting}[language={},backgroundcolor=\color{outputgray}]
Shape
unspecified-shape-1
Circle
small-circle
1.5
Rectangle
square-B
12 12
Circle
big-circle
22.8
\end{lstlisting}

Notice that each shape begins with the name of the class on a line by
itself. The next line is the name of the shape. A \lstinline{Circle}
then has a line with a radius on it and a \lstinline{Rectangle} has a
line with the width and height.

At this point, you can read the file and test your constructors. Next
you will build a tree to hold the \lstinline{Shape}s you read.

\subsubsection*{Binary Search Tree}
Add a new package, \lstinline{tree}. Put the class \lstinline{BST} in
the package. The class interface (the public functions it should have)
is:
\begin{lstlisting}[language=java,backgroundcolor=\color{outputgray}]
class BST {
  public BST();
  public void add(Shape newbie);
  public Shape find(double areaToSearchFor);
  public String shapesInDecreasingOrder();
  public String shapesInIncreasingOrder();
\end{lstlisting}

Feel free to have \lstinline{private} helper methods.

Use the \lstinline{toString} methods you put in the \lstinline{Shape}
classes to assemble the in-some-order strings.

Modify \lstinline{TreeClientProgram.run} to put the shapes in a new
tree and the menu handler to call the right methods on the tree.

\subsection*{Design Considerations}

The tree must be kept ordered as stated above.

There are six (6) Java files across four (4) packages. No one of
them is very long (and \lstinline{menu.Menu} is already written). Work
a little bit at a time, checking that it compiles and runs as you go.

\subsection*{Documentation}

\subsubsection*{\lstinline{README}}
Must document how you tested. How do you know that it is right?

Must include instructions on how to \textbf{compile} and how to
\textbf{run} the program as submitted.

\subsection*{Deliverables}
\textbf{Submission medium}: \lstinline{git} to Gitea at
\lstinline{cs-devel.potsdam.edu}.
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
