\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{pTree-b --- Shapes with Delete}
\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}
\definecolor{lsting-java}{rgb}{0.9 0.8 0.9}


\begin{document}
\pointsinrightmargin{}

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

\begin{itemize}
\item Extend a \emph{binary search tree} container class to include
  \emph{delete}, \emph{size}, and \emph{height} methods.
  \item Write \lstinline{JUnit} tests for \emph{add} and \emph{delete}
  methods.
\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:} This program includes grading based on using
\emph{test-driven development} (TDD). This requires you to write a
\emph{failing} test for a feature/method, commit the code with the
broken test into \lstinline{git}, make the code pass the test, and
then commit the working code. This will be examined in terms of the
\emph{delete} and \emph{height} methods in your tree class. You may
use TDD for the  size method if you wish, or not.
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 with your \emph{working} \lstinline{pTree-a} solution. This will
give you

\begin{itemize}
\item a \lstinline{Shape} class hierarchy with \lstinline{Shape},
\lstinline{Circle}, and \lstinline{Rectangle}.
\item a \emph{menu-driven} client program that loads a binary-search
  tree with \lstinline{Shape}s from a file.
\item a \lstinline{BST} class that can hold \lstinline{Shape} objects.
\end{itemize}

You will be expected to turn this program in through the \emph{same}
Gitea repository you used for \lstinline{pTree-a}
(\lstinline{F23-205-<ccid>-p005})

\subsection*{Class Hierarchy}
You will create a new class, \lstinline{shapes.Triangle}. All four
\lstinline{Shape} classes are in the new diagram with descriptions
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.
\item[Triangle] Keeps \emph{width} and \emph{height}, overrides
  \lstinline{area} to return the area of the triangle.
\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*{Binary Search Tree}
You will modify your \lstinline{BST} class to have the following
public interface:

\subsubsection*{Binary Search 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}]
package tree;
class BST {
  public BST();
  public void add(Shape newbie);
  public Shape find(String nameToSearchFor);
  // true if found and deleted; false otherwise
  public boolean delete(String nameToDelete);
  // the list of Shapes, one per line
  public String inOrder();
  // the lint of Shapes, indented by tree depth, one per line
  public String inOrderIndented();
  // height of the tree (empty tree height 0)
  public int height();
  // size of the tree (number of nodes)
  public int size();
\end{lstlisting}

\subsubsection*{Testing}
Before implementing \lstinline{delete}, create a \lstinline{JUnit}
test class in the \lstinline{app/src/test/java/tree} folder,
\lstinline{BSTTest.java}. (You may need to add back these
directories.)

The important \lstinline{import} statements for a test file like this
are

\begin{lstlisting}[backgroundcolor=\color{lsting-java}]
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
\end{lstlisting}

Remember that \lstinline{Test} is a Java \emph{annotation} (it comes
after an \lstinline{@} sign and labels a method as a test to be run).

Add a test to your test class that checks what happens when you delete
from an empty tree:

\begin{lstlisting}[backgroundcolor=\color{lsting-java}]
@Test
void DeleteFromNewTreeTest() {
  BST bst = new BST();
  assertFalse(bst.delete("Bet this isn't found."));
}
\end{lstlisting}

Try to compile. It will fail because there is no \lstinline{delete}
method yet. You have a failing test! Add and commit everything.

Make the test pass as simply as possible. That means your delete is
going to be

\begin{lstlisting}[backgroundcolor=\color{lsting-java}]
public boolean delete(String nameToDelete) {
  return false;
}
\end{lstlisting}

Now your code should compile and the test pass. Add and commit. (This
assignment will stop saying ``Add and commit.'' after each
\emph{failing} test and each \emph{passing} test; it is there
implicitly.)

Next, add a new test that adds a shape to the tree and then deletes
it. It is a new \lstinline{@Test} method. This will fail because the
call to \lstinline{delete} should return \lstinline{true} when it
succeeds in removing the shape. (Okay, one more time: \textbf{Add and
  commit.})

This means you need to make \lstinline{delete} work. This is one of
the easy cases.

Now, make a new test that creates a more complex tree. Check that you
can successfully delete a node with no children, one with just a left
child, one with just a right child, and one with two non-singleton
tree children. This could be one or four test methods. Up to you.

You can use the indenting print function to get the structure of the
tree, if you like, before and after the \lstinline{delete}. Or you can
use the search function to make sure only the expected node goes away.

Notice that you are, implicitly, testing \lstinline{add}, too. You
will test \lstinline{add} explicitly now: write a test method for
building a \emph{degenerate} tree by inserting in sorted order. Use
the indenting print method to make sure the structure is what you
expect.

There is a problem: the test is supposed to initially fail. Why is
that? so that you can be sure that you are testing the thing you mean
to test. An \emph{empty} test will pass without checking anything in
your code. So: break your test code by changing the expected
value. Now it will fail \textbf{and} you know that it is being
run. Add and commit, fix, add and commit.

Also implement \lstinline{size} and \lstinline{height}. You are not
required to use TDD for these methods.

\subsection*{Input/Output}
\lstinline{main.TreeClientProgram} expects a shape file name on the
command-line. Only difference from previous the previous version is
that the type might be \lstinline{Triangle}; a \lstinline{Triangle}
has the same fields as a \lstinline{Rectangle}.

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} or
\lstinline{Triangle} has a line with the width and height.

\subsection*{Design Considerations}

The tree must be kept ordered in ascending order by \emph{name}: this
is different from the previous project. The \emph{search} method now
prompts for a name rather than an area (as does \lstinline{delete}).

Use the indented print method to make sure that the tree is
constructed correctly. Play with the code to see if you can break
it. If you do, you might want to write a test that breaks it the same
way and then fix the code to make the test pass (without causing other
tests to fail).

\subsection*{Documentation}

\subsubsection*{\lstinline{README}}
Must document how you tested. You can point at your \lstinline{JUnit}
tests.

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:
