\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 658: Software Language Engineering Data Abstraction: Java Supplement},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother

\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 658: Software Language Engineering\\
Data Abstraction: Java Supplement}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{17 February 2018}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2018, \href{http://www.cs.olemiss.edu/~hcc}{H. Conrad
Cunningham}\\
Professor of \href{https://www.cs.olemiss.edu}{Computer and Information
Science}\\
\href{http://www.olemiss.edu}{University of Mississippi}\\
211 Weir Hall\\
P.O. Box 1848\\
University, MS 38677\\
(662) 915-5358

\textbf{Advisory}: The HTML version of this document requires use of a
browser that supports the display of MathML. A good choice as of
February 2018 is a recent version of Firefox from Mozilla.

\hypertarget{data-abstraction-java-supplement}{%
\section{Data Abstraction: Java
Supplement}\label{data-abstraction-java-supplement}}

\hypertarget{introduction}{%
\subsection{Introduction}\label{introduction}}

This set of notes forms a Java-specific supplement to the lecture notes
on \href{DataAbstraction.html}{Data Abstraction}. However, most of the
concepts apply to other object-oriented languages such as Scala. The
discussion here is meant to be read after completion of the Data
Abstraction notes.

This set of notes discusses use of Java to implement abstract data types
(ADTs). It seeks to use good object-oriented programming practices, but
it does not cover the principles and practices of object-oriented
programming fully. For more information on object orientation, see the
notes on \href{OOSoftDev.html}{Object-Oriented Software Development} and
\href{http://www.cs.olemiss.edu/~hcc/csci450/notes/HaskellNotes/01Fundamental450.html\#object-oriented}{Object-Oriented
programming paradigm}.

\hypertarget{java-class-implementation-for-day}{%
\subsection{Java Class Implementation for
Day}\label{java-class-implementation-for-day}}

The following implementation of the \texttt{Day} ADT is adapted from the
like-named class in Chapter 4 of the book \emph{Core Java 1.2: Volume I
-\/- Fundamentals} (Fourth Edition) by Cay S. Horstmann and Gary
Cornell.

In general, this set of notes assumes that the implementations of the
ADTs use mutable (stateful) objects. The approach to design of mutator
methods would be somewhat different if immutable objects are used. But
otherwise the general approach to design applies to immutable objects.

Caveat: This document was originally written before the release of Java
5. However, other than needing to be updated to incorporate newer Java
features such as generics, functional interfaces, and lambdas, the
principles are still relevant to contemporary Java programming.

\hypertarget{java-classes}{%
\subsection{Java Classes}\label{java-classes}}

As a language construct, a Java \texttt{class} is similar to a
user-defined \texttt{struct} type in C or user-defined record
\emph{type} in Pascal. A \texttt{class} is a template for constructing
data items that have the same structure but differing values (states).
We say that an item constructed by a class is a \emph{class instance}
(or, as we see later, an \emph{object}).

Like the C structure type or Pascal record type, a Java class can
consist of several components. In C and Pascal, all the components are
data fields. However, in Java, functions and procedures may be included
as components of a class. These procedures and functions are called
\emph{methods}.

\hypertarget{class-and-instance-methods}{%
\subsubsection{Class and Instance
Methods}\label{class-and-instance-methods}}

A method declared in a class may be either a class method or instance
method.

\begin{itemize}
\item
  A \emph{class method} is associated with the class as a whole, not
  with any specific instance.
\item
  An \emph{instance method} is associated with an instance of the class.
\end{itemize}

We declare a method as a \emph{class method} by giving the keyword
\texttt{static} in the header of its definition. For example, a
\texttt{main} method of a program is a class method of the class in
which it is defined.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{void} \FunctionTok{main}\NormalTok{(}\BuiltInTok{String}\NormalTok{[] args) }
\NormalTok{    \{   }\CommentTok{//  beginning code for the program}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

If we \emph{do not include} the keyword \texttt{static} in the header of
a method definition, the method is an \emph{instance method}. For
example, consider methods to implement the \texttt{push} and
\texttt{top} operations of a class that implements a \texttt{StackB}.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \DataTypeTok{void} \FunctionTok{pop}\NormalTok{()}
\NormalTok{    \{   }\CommentTok{// code for pop operation}
\NormalTok{    \}}

    \KeywordTok{public} \BuiltInTok{Object} \FunctionTok{top}\NormalTok{()}
\NormalTok{    \{   }\CommentTok{// code for top operation}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Note that \texttt{pop()} is a \emph{procedure} (i.e., it has return type
\texttt{void}) method and \texttt{top} is a \emph{function} method.

Scala note: The Scala language does not have static members of classes.
However, the methods of a Scala singleton \texttt{object} have basically
the same characteristics described above for ``class methods''. Often
the ``class methods'' appear in the companion \texttt{object} for a
class. i.e., the \texttt{object} with the same name as the class.

\hypertarget{class-and-instance-variables}{%
\subsubsection{Class and Instance
Variables}\label{class-and-instance-variables}}

In a similar fashion, the variables (data fields) declared in a class
may be either class variables or instance variables.

\begin{itemize}
\item
  A \emph{class variable} is associated with the class as a whole; there
  is only one copy of the variable for the entire class. As with
  methods, the keyword \texttt{static} is used to declare a class
  variable.
\item
  An \emph{instance variable} is associated with an instance of the
  class; each instance has its own instance of the variable. As with
  methods, the absence of the keyword \texttt{static} denotes an
  instance variable.
\end{itemize}

An instance method has direct access to the instance variables of the
class instance (object) to which it is applied. The instance's variables
are implicit arguments of the method calls. (If needed to distinguish
among names, the builtin variable \texttt{this} can be used to refer to
the instance to which the method is applied.) The instance methods also
have access to the class variables (if any).

Class methods only have access to the class variables. The methods do
not have any implicit arguments. In fact, class methods can be called
without any instances of the class being in existence.

Scala note: The Scala language does not have static members of classes.
However, the variables of a Scala singleton \texttt{object} have
basically the same characteristics described above for ``class
variables''. Often the ``class variables'' appear in the companion
\texttt{object} for a class. i.e., the \texttt{object} with the same
name as the class.

\hypertarget{public-and-private-accessibility}{%
\subsubsection{Public and Private
Accessibility}\label{public-and-private-accessibility}}

The components of a class can be designated as \texttt{public} or
\texttt{private}.

\begin{itemize}
\item
  The \texttt{public} components of the class are accessible from
  anywhere in the program (i.e., from any package).
\item
  The \texttt{private} components are only accessible from inside the
  class.
\end{itemize}

As a general rule, the data fields of a class should be \emph{private
instance variables}, meaning that they are associated with a specific
instance and are only accessible by the instance methods. This hides, or
encapsulates, the data fields within the class instance.

Note: Actually, the instance methods of a Java class can access the
instance variables of any instance of that class, not just the current
instance.

In general, avoid public instance variables. They break the principle of
information hiding, leading to potential entanglements among modules.

A public method of a class is a service provided by that instance to
other parts of a program. The private methods of a class can be used in
implementing the public methods.

Class methods and variables should be used sparingly. These are more or
less the types of subprograms and global variables found in languages
like C and Pascal. Their excessive use can greatly reduce the potential
benefits that can be realized from object-oriented techniques.

Java note: There are two other types of accessibility, ``friendly'' and
\texttt{protected}, but \texttt{public} and \texttt{private} are
sufficient for our discussion of ADT implementations.

Scala note: Although similar in concept to that of Java, the
accessibility features of Scala differ somewhat. By default, all
features are public in Scala, but accessibility can restricted in a more
fine-grained manner than in Java. The unmodified keyword
\texttt{private} has the same meaning as in Java.

\hypertarget{primitive-and-reference-variables}{%
\subsubsection{Primitive and Reference
Variables}\label{primitive-and-reference-variables}}

A Java variable is a strongly typed ``container'' in memory that is
declared to hold either:

\begin{itemize}
\item
  a \emph{value} of the associated primitive data type such as integers
  (\texttt{int}), floating point numbers (\texttt{double}), booleans
  (\texttt{boolean}), and single characters (\texttt{char}).
\item
  a \emph{reference} to (i.e., memory address of) an instance of the
  associated class (or other reference) type.
\end{itemize}

Java note: Although arrays are not class instances, array variables hold
a reference to an instance of the array.

The class instances themselves are stored in the dynamically managed
heap memory area. Java allocates memory from the heap to hold newly
constructed instances of a class. Java's garbage collector reclaims the
memory for instances that are no longer needed by the program.

Note: Recent versions of Java can sometimes hide the differences between
primitive values and references by automatically ``boxing'' primitive
values as instances of the corresponding wrapper classes (e.g.,
\texttt{int} values as \texttt{Integer} instances). Scala goes further
in that primitives and references are in the same type hierarchy.
However, both languages run on the Java Virtual Machine, which makes a
distinction between primitive values and references (i.e., pointers), so
it is not possible to avoid the distinction entirely.

\hypertarget{implementing-adts-as-java-classes}{%
\subsection{Implementing ADTs as Java
Classes}\label{implementing-adts-as-java-classes}}

If only one implementation of an ADT is needed, the following techniques
can be used to implement an ADT using Java.

The implementation techniques discussed in this section implement the
ADT in an imperative way. That is, instead of returning a new instance
of the ADT with a modified state, a mutator operation usually modifies
the state of the existing instance.

Caveat: The discussion of Java in these notes does not use generic type
parameters. For the \texttt{StackB} ADT (defined in the
\href{DataAbstraction.html}{Data Abstraction} notes), the type of the
\texttt{Item} values stored in the stack can be a parameter of the
\texttt{StackB} class.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  \textbf{Use the Java \texttt{class} construct to represent the entire
  ADT.} If we want to allow access to the class from anywhere in the
  program, we will make the class \texttt{public}.

  For the \texttt{StackB} ADT, we can use the following structure for
  the class:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \KeywordTok{class}\NormalTok{ StackB}
\NormalTok{    \{   }\CommentTok{// implementation of instance methods and data here}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}
\item
  \textbf{Use an instance of the Java class to represent an instance of
  the ADT and, hence, variables of the class type to hold references to
  instances.}

  For example, to declare a variable that can hold a reference to a
  \texttt{StackB} instance, we can use the following declaration:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    StackB stk;}
\end{Highlighting}
\end{Shaded}
\item
  \textbf{As each component of the class is defined, ensure that the
  semantics of the ADT operations are implemented appropriately.} That
  is, make sure:

  \begin{itemize}
  \item
    an appropriate implementation (representation) invariant is defined
    to capture what it means for the internal state of an instance to be
    valid,
  \item
    the interface and implementation invariants are established (i.e.,
    made true) by the constructors and preserved (i.e., kept true) by
    the mutator and accessor methods,
  \item
    each method's postcondition is established by the method in any
    circumstance when it is called with the precondition true.
  \end{itemize}

  The class and its methods should be documented with the invariants,
  preconditions, and postconditions.
\item
  \textbf{Represent the ADT's constructors by Java constructor methods.
  In most circumstances, also include a parameterless default
  constructor.}

  A Java constructor is a method with the same name as the class. It
  does not have a return type specified. Upon creation of an instance of
  the class, the constructor initializes the instance's state so that
  the class invariants are established.

  A constructor is normally invoked by the Java operator \texttt{new}.
  The operator \texttt{new} allocates memory on the heap for the
  instance, calls the constructor to initialize the new instance, and
  then returns a reference to the new instance.

  For example, we can represent the ADT operation \texttt{create} by the
  constructor method \texttt{StackB}.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \KeywordTok{class}\NormalTok{ StackB}
\NormalTok{    \{   }\KeywordTok{public} \FunctionTok{StackB}\NormalTok{(}\DataTypeTok{int}\NormalTok{ size)}
\NormalTok{        \{   }\CommentTok{// initialization code}
\NormalTok{        \}}

    \CommentTok{// rest of StackB methods and data ...}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

  A user of the \texttt{StackB} class can then declare a variable and
  initialize it to hold a reference to a new stack with a capacity of
  100 items as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    StackB stk = }\KeywordTok{new} \FunctionTok{StackB}\NormalTok{(}\DecValTok{100}\NormalTok{);}
\end{Highlighting}
\end{Shaded}

  The expression \texttt{new\ StackB(100)} allocates a \texttt{StackB}
  instance in the heap storage and calls the constructor above to
  initialize the data fields encapsulated within the instance.
\item
  \textbf{Represent the ADT operations by instance methods of the
  class.} Thus the state of the ADT instance, which is given explicitly
  in the ADT signatures, becomes an \emph{implicit argument} of all
  method calls. Mutators also have the state as an implicit return.

  We can apply a method to a class instance by using the selector (i.e.,
  ``dot'') notation. This notation is similar to the notation for
  accessing \texttt{record} components in Pascal.

  For example, in the case of the \texttt{StackB} ADT we can represent
  the operations as instance methods of class \texttt{StackB}. The
  explicit \texttt{StackB} parameters and return values of the
  operations thus become implicit.

  Suppose we want to push an item \texttt{x} onto the \texttt{stk}
  created above. We can do that with the following code:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{if}\NormalTok{ (!stk.}\FunctionTok{full}\NormalTok{())}
\NormalTok{        stk.}\FunctionTok{push}\NormalTok{(x); }
\end{Highlighting}
\end{Shaded}

  We can then examine the top item and remove it:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{if}\NormalTok{ (!stk.}\FunctionTok{empty}\NormalTok{())}
\NormalTok{    \{   it = stk.}\FunctionTok{top}\NormalTok{();}
\NormalTok{        stk.}\FunctionTok{pop}\NormalTok{(); }
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}
\item
  \textbf{Make the constructors, mutators, accessors, and destructors
  \texttt{public} methods of the class.} That is, precede the method's
  definition by the keyword \texttt{public}.
\item
  \textbf{Represent the ADT mutator operations by Java procedure (i.e.,
  \texttt{void}) methods, except those mutator operations that
  explicitly require new instances to be generated (e.g., a copy or
  \texttt{clone} operation).}

  For example, the \texttt{pop} method of \texttt{StackB} would have the
  following structure:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \DataTypeTok{void} \FunctionTok{pop}\NormalTok{()}
\NormalTok{    \{   }\CommentTok{//  code to implement operation}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

  A mutator method modifies the encapsulated state of the class instance
  (which is the implicit argument of the method). In any circumstance in
  which its precondition and the class invariants hold on entry, the
  method must establish its postcondition and reestablish the invariants
  upon exit. (The invariant might not hold in the middle of the method's
  execution.)

  Comment: Implementing mutator operations as procedure calls that
  modify the stored state is really an optimization. All mutators can be
  implemented in the applicative style, returning a modified copy of the
  instance. This implementation might, however, be inefficient in use of
  processor time and memory.
\item
  \textbf{For certain mutator operations (e.g., copy or \texttt{clone}),
  implement the corresponding Java methods to return new instances of
  the class rather than to modify the current instance (i.e., their
  implicit arguments).}

  Any mutator method must, of course, establish its postcondition and
  reestablish the invariants for the current instance. In addition,
  these applicative mutators must also establish the invariants for the
  new instance returned.
\item
  \textbf{Represent the ADT accessor operations by Java function methods
  of the proper return type.}

  For example, the \texttt{empty} method of \texttt{StackB} would have
  the following structure:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \DataTypeTok{boolean} \FunctionTok{empty}\NormalTok{()}
\NormalTok{    \{   }\CommentTok{//  code to implement operation}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

  An accessor method accesses the encapsulated state of the class
  instance (which is the implicit argument) and computes a value to be
  returned. In any circumstance in which its precondition and the class
  invariants hold on entry, the method must establish its postcondition
  and reestablish the invariants upon exit. (The invariant might not
  hold in the middle of the method's execution.)
\item
  \textbf{If necessary for deallocation of internal resources, represent
  the ADT destructor methods by explicit Java procedures; in most cases,
  however. just allow the automatic garbage collection to reclaim
  instances that are no longer being used.}

  For example, in the \texttt{StackB} class, we might include an
  explicit destroy operation that releases the storage resources and
  disables further use of the instance.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \DataTypeTok{void} \FunctionTok{destroy}\NormalTok{()}
\NormalTok{    \{   }\CommentTok{//  code to free resources}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

  Note: The Java framework allows a \texttt{finalize()} method to be
  included in each class. This method is called implicitly whenever the
  garbage collector detects that the instance is no longer in use.
  However, since it is difficult to predict when (if ever) this method
  will be executed, it is safer to include explicit destructors when
  resources are in short supply and must be explicitly managed.
\item
  \textbf{Use \texttt{private} data fields of the Java class to
  represent the encapsulated state of the instance needed for a
  particular implementation.} By making the data fields \texttt{private}
  they are still available to the instance's methods, but are not
  visible outside the class.

  For example, the \texttt{StackB} class might have the following data
  fields:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \KeywordTok{class}\NormalTok{ StackB}
\NormalTok{    \{   }\CommentTok{//  public operations of class instance}

        \CommentTok{//  encapsulated data fields of class instance}
        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ topItem;   }\CommentTok{// Pointer to next index for insertion}
        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ capacity;  }\CommentTok{// Maximum number of items in stack}
        \KeywordTok{private} \BuiltInTok{Object}\NormalTok{[] stk;  }\CommentTok{// the stack}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}
\item
  \textbf{Do not use \texttt{public} data fields in the class. These
  violate the principle of information hiding. Instead introduce
  appropriate accessor and mutator methods to allow manipulation of the
  hidden state.}
\item
  \textbf{Include, as appropriate, \texttt{private} methods to aid in
  implementation.}

  Functionality common to several methods can be placed in separate
  functions and procedures as needed. However, since these are
  \texttt{private}, they can only be accessed from within the class and
  thus can be changed without affecting the public interface of the
  class.
\item
  \textbf{Add any other methods needed to make the ADT fit into the Java
  environment.}

  For example, it is frequently useful to add public \texttt{toString}
  and \texttt{clone} methods. The \texttt{toString} method returns a
  Java \texttt{String} reflecting the ``value'' of the instance in a
  format suitable for printing. The \texttt{clone} method creates a new
  instance that has the same value as the current instance.
\item
  \textbf{In general, avoid use of class (i.e., \texttt{static})
  variables.} Since a class variable is shared among all instances of
  the class, it may be difficult to preserve the invariants for
  individual instances as the value of the class variable changes.

  However, it is a good programming practice to \textbf{use class
  \emph{constants} where appropriate.} These are data fields declared
  with both the \texttt{static} and \texttt{final} modifiers. Their
  values may be initialized but cannot be changed thereafter.

  These constants may be declared \texttt{private} if usage is to be
  restricted to the class or \texttt{public} if the users of the class
  also need access.

  By convention, the names of constants are normally written with all
  uppercase letters. For example, the following defines a symbolic name
  for the integer code used for Sunday as a day of the week in the
  \texttt{Day} class defined later.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ SUNDAY = }\DecValTok{1}\NormalTok{;}
\end{Highlighting}
\end{Shaded}
\end{enumerate}

Caveat: When this set of notes was originally written, Java did not yet
have generics. So the examples below handle the type parameters of the
ADT in other ways. A Java generic provides a class facility that can be
parameterized with types (like the C++ \texttt{template} or Ada
\texttt{generic} mechanisms).

For example, in the implementation below we represent the set
\texttt{Item} of the \texttt{StackB} ADT by the class \texttt{Object}.
As we will see when we discuss inheritance, the \texttt{Object} type
will allow us to store an instance of any class on the \texttt{StackB}.
With this definition, any data of a reference type can appear in the
stack, but values of the primitive types cannot. A better implementation
would have \texttt{Item} as type parameter of the class.

The next section gives a Java implementation of the \texttt{StackB} ADT.
A similar constructive definition and two implementations of a
\href{Queue.html}{Queue ADT} are available in a separate document.

\hypertarget{java-implementation-of-bounded-stack}{%
\subsubsection{Java Implementation of Bounded
Stack}\label{java-implementation-of-bounded-stack}}

In this section, we give an implementation of the \texttt{StackB} ADT
that uses an array of objects and an integer ``pointer'' to represent
the stack. (This implementation does not use Java generic classes.)

This implementation is not robust; each operation assumes that its
precondition holds. A more robust implementation might check whether the
precondition holds and throw an exception if it does not.

Remember that the invariants are implicitly pre- and postconditions of
all mutator and accessor methods, postconditions of the constructor, and
preconditions of the destructor.

\begin{Shaded}
\begin{Highlighting}[]
    \CommentTok{// A Bounded Stack ADT}
    \KeywordTok{public} \KeywordTok{class}\NormalTok{ StackB }
\NormalTok{    \{   }\CommentTok{// Interface Invariant:  Once created and until destroyed, this}
        \CommentTok{//     stack instance has a valid and consistent internal state }

        \KeywordTok{public} \FunctionTok{StackB}\NormalTok{(}\DataTypeTok{int}\NormalTok{ size)}
        \CommentTok{// Pre:   size >= 0}
        \CommentTok{// Post:  initialized new instance with capacity size && empty()}
\NormalTok{        \{   stk = }\KeywordTok{new} \BuiltInTok{Object}\NormalTok{[size];}
\NormalTok{            capacity = size;}
\NormalTok{        topItem = }\DecValTok{0}\NormalTok{;}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{void} \FunctionTok{push}\NormalTok{(}\BuiltInTok{Object}\NormalTok{ item)}
        \CommentTok{// Pre:   not full()}
        \CommentTok{// Post:  item added as the new top of this instance's stack}
\NormalTok{        \{   stk[topItem] = item;}
\NormalTok{            topItem++;}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{void} \FunctionTok{pop}\NormalTok{()}
        \CommentTok{// Pre:   not empty()}
        \CommentTok{// Post:  item at top of stack removed from this instance}
\NormalTok{        \{   topItem--;}
\NormalTok{            stk[topItem] = }\KeywordTok{null}\NormalTok{;}
\NormalTok{        \}}

        \KeywordTok{public} \BuiltInTok{Object} \FunctionTok{top}\NormalTok{()}
        \CommentTok{// Pre:   not empty()}
        \CommentTok{// Post:  return item at top of this instance's stack}
\NormalTok{        \{   }\KeywordTok{return}\NormalTok{ stk[topItem}\DecValTok{-1}\NormalTok{];}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{boolean} \FunctionTok{empty}\NormalTok{()}
        \CommentTok{// Pre:   true}
        \CommentTok{// Post:  return true iff this instance's stack has no elements}
\NormalTok{        \{   }\KeywordTok{return}\NormalTok{ (topItem <= }\DecValTok{0}\NormalTok{);}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{boolean} \FunctionTok{full}\NormalTok{()}
        \CommentTok{// Pre:   true}
        \CommentTok{// Post:  return true iff this instance's stack is at full capacity}
\NormalTok{        \{  }\KeywordTok{return}\NormalTok{ (topItem >= capacity);}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{void} \FunctionTok{destroy}\NormalTok{()}
        \CommentTok{// Pre:   true}
        \CommentTok{// Post:  internal resources released;  stack effectively deleted}
\NormalTok{        \{   stk = }\KeywordTok{null}\NormalTok{;}
\NormalTok{        capacity = }\DecValTok{0}\NormalTok{;}
\NormalTok{            topItem = }\DecValTok{0}\NormalTok{;}
\NormalTok{        \} }

        \CommentTok{// Implementation Invariant for informal model:  }
        \CommentTok{//     0 <= topItem <= capacity &&}
        \CommentTok{//     stack is in array section stk[0..topItem-1]}
        \CommentTok{//         with the top at stk[topItem-1], etc.}

        \CommentTok{// Implementation Invariant for more formal model representing stack }
        \CommentTok{// as tuple (integer max, sequence stkseq)}
        \CommentTok{//     m == capacity && 0 <= topItem <= capacity &&}
        \CommentTok{//     stackInArray(stk,topItem,stkseq)}
        \CommentTok{//     where stackInArray(arr,t,ss) = if t == 0 then ss == []}
        \CommentTok{//                                    else arr[t-1] == head(ss)}
        \CommentTok{//                                       && stackInArray(arr,t-1,tail(ss))}

        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ topItem;   }\CommentTok{// Pointer to next index for insertion}
        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ capacity;  }\CommentTok{// Maximum number of items in stack}
        \KeywordTok{private} \BuiltInTok{Object}\NormalTok{[] stk;  }\CommentTok{// the stack}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

\hypertarget{better-approach-to-implementing-adts-in-java}{%
\subsection{Better Approach to Implementing ADTs in
Java}\label{better-approach-to-implementing-adts-in-java}}

If several different implementations of an ADT are needed, then the Java
specification of an ADT's interface should be separated from the class
implementation. The interface specification can be reused among several
classes and various implementations of the interface can be used
interchangeably.

This can be done as follows:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  \textbf{Define a Java \texttt{interface} that specifies the type
  signatures for the ADT's mutator and accessor (and, if needed,
  destructor) operations.} These method signatures should have the same
  characteristics as described above in the discussion of class-based
  specification.
\item
  \textbf{Specify and document the \texttt{interface} by the interface
  invariants, preconditions, and postconditions that must be supported
  by any implementation of the ADT.} There are no implementation
  invariants for an interface, but individual classes that implement the
  \texttt{interface} will have them.

  For example, a bounded stack \texttt{interface} might be specified as
  follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \KeywordTok{interface}\NormalTok{ StackADT }
\NormalTok{    \{   }\CommentTok{// Interface Invariant:  Once created and until destroyed, this}
        \CommentTok{//     stack instance has a valid and consistent internal state }

        \KeywordTok{public} \DataTypeTok{void} \FunctionTok{push}\NormalTok{(}\BuiltInTok{Object}\NormalTok{ item);}
        \CommentTok{// Pre:   not full()}
        \CommentTok{// Post:  item added as the new top of this instance's stack}

\NormalTok{        ...}

        \KeywordTok{public} \BuiltInTok{Object} \FunctionTok{top}\NormalTok{();}
        \CommentTok{// Pre:   not empty()}
        \CommentTok{// Post:  return item at top of this instance's stack}

\NormalTok{        ...}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}
\item
  \textbf{Provide one or more concrete classes that implement the
  \texttt{interface}.}

  For example, an array-based \texttt{StackADT} could be implemented
  similarly to the \texttt{StackB} definition given in the previous
  section.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{public} \KeywordTok{class}\NormalTok{ StackInArray }\KeywordTok{implements}\NormalTok{ StackADT}
\NormalTok{    \{   }\CommentTok{// Interface Invariant:  Once created and until destroyed, this}
        \CommentTok{//     stack instance has a valid and consistent internal state }

    \KeywordTok{public} \FunctionTok{StackInArray}\NormalTok{(}\DataTypeTok{int}\NormalTok{ size)}
    \CommentTok{// Pre:   size >= 0}
    \CommentTok{// Post:  initialized new instance with capacity size && empty()}
\NormalTok{    \{   stk = }\KeywordTok{new} \BuiltInTok{Object}\NormalTok{[size];}
\NormalTok{    capacity = size;}
\NormalTok{             topItem = }\DecValTok{0}\NormalTok{;}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{void} \FunctionTok{push}\NormalTok{(}\BuiltInTok{Object}\NormalTok{ item)}
        \CommentTok{// Pre:   not full()}
        \CommentTok{// Post:  item added as the new top of this instance's stack}
\NormalTok{        \{   stk[topItem] = item;}
\NormalTok{            topItem++;}
\NormalTok{        \}}

\NormalTok{        ...}

        \KeywordTok{public} \BuiltInTok{Object} \FunctionTok{top}\NormalTok{()}
        \CommentTok{// Pre:   not empty()}
        \CommentTok{// Post:  return item at top of this instance's stack}
\NormalTok{        \{   }\KeywordTok{return}\NormalTok{ stk[topItem}\DecValTok{-1}\NormalTok{]; }
\NormalTok{        \}}

\NormalTok{        ...}

        \CommentTok{// Implementation Invariant for informal model:  }
        \CommentTok{//     0 <= topItem <= capacity &&}
        \CommentTok{//     stack is in array section stk[0..topItem-1]}
        \CommentTok{//         with the top at stk[topItem-1], etc.}

        \CommentTok{// Implementation Invariant for more formal model representing stack }
        \CommentTok{// as tuple (integer max, sequence stkseq)}
        \CommentTok{//     m == capacity && 0 <= topItem <= capacity &&}
        \CommentTok{//     stackInArray(stk,topItem,stkseq)}
        \CommentTok{//     where stackInArray(arr,t,ss) = }
        \CommentTok{//               if t == 0 then ss == []}
        \CommentTok{//               else arr[t-1] == head(ss)}
        \CommentTok{//                    && stackInArray(arr,t-1,tail(ss))}

        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ topItem;   }\CommentTok{// Pointer to next index for insertion}
        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ capacity;  }\CommentTok{// Maximum number of items in stack}
        \KeywordTok{private} \BuiltInTok{Object}\NormalTok{[] stk;  }\CommentTok{// the stack}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}
\item
  \textbf{Declare variables of the ADT's \texttt{interface} type to hold
  instances of any concrete class that implements the
  \texttt{interface}.} Any of the operations defined in the
  \texttt{interface} can be applied to the instance to which this
  variable refers.

  For example, a variable of type \texttt{StackADT} can hold instances
  of any concrete class that implements the
  \texttt{interface\ StackADT}.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    StackADT theStack = }\KeywordTok{new} \FunctionTok{StackInArray}\NormalTok{(}\DecValTok{100}\NormalTok{);}
\NormalTok{    theStack.}\FunctionTok{push}\NormalTok{(}\StringTok{"Hello World"}\NormalTok{);}
\end{Highlighting}
\end{Shaded}
\end{enumerate}

For an ADT specification and implementations that follow this approach,
see the description of the \href{RankedSequence.html}{Ranked Sequence
ADT} case study given in a separate document. In addition to Java
interfaces, the Ranked Sequence case study uses other Java features such
as exceptions, enumerations, packages, and Javadoc annotations.

\hypertarget{java-class-implementation-for-day-1}{%
\subsubsection{Java Class Implementation for
Day}\label{java-class-implementation-for-day-1}}

The following implementation of the \texttt{Day} ADT is adapted from the
like-named class in Chapter 4 of the book \emph{Core Java 1.2: Volume I
-\/- Fundamentals} (Fourth Edition) by Cay S. Horstmann and Gary Cornell
(Sun Microsystems Press/Prentice Hall, 1999).

This implementation represents the calendar as three integers. It
converts the dates to and from Julian dates to do some of the
operations.

\begin{Shaded}
\begin{Highlighting}[]
    \CommentTok{//  This class implementation is adapted from the Day class in}
    \CommentTok{//  Horstmann and Cornell, Core Java 1.2: Volume I - Fundamentals }
    \CommentTok{//  (Fourth Edition), Prentice Hall, 1999.}

    \KeywordTok{import}\ImportTok{ java.util.*;}
    \KeywordTok{import}\ImportTok{ java.io.*;}

    \KeywordTok{public} \KeywordTok{class}\NormalTok{ Day }
\NormalTok{    \{}
        \CommentTok{// Interface Invariant:  Once created and until destroyed, this}
        \CommentTok{//    instance contains a valid date.  gateau() != 0 && }
        \CommentTok{//    1 <= getMonth() <= 12 && 1 <= getDay() <= #days in getMonth().}
        \CommentTok{//    Also calendar date getMonth()/getDay()/getYear() does not}
        \CommentTok{//    fall in the gap formed by the change to the modern}
        \CommentTok{//    (Gregorian) calendar.  }

      \CommentTok{//  Constants for days of the week}

        \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ SUNDAY    = }\DecValTok{1}\NormalTok{;}
        \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ MONDAY    = }\DecValTok{2}\NormalTok{;}
        \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ TUESDAY   = }\DecValTok{3}\NormalTok{;}
        \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ WEDNESDAY = }\DecValTok{4}\NormalTok{;}
        \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ THURSDAY  = }\DecValTok{5}\NormalTok{;}
        \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ FRIDAY    = }\DecValTok{6}\NormalTok{;}
        \KeywordTok{public} \DataTypeTok{static} \DataTypeTok{final} \DataTypeTok{int}\NormalTok{ SATURDAY  = }\DecValTok{7}\NormalTok{;}

      \CommentTok{// Constructors}

        \KeywordTok{public} \FunctionTok{Day}\NormalTok{()}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  the new instance's day, month, and year set to today's}
        \CommentTok{//             date (i.e., the date of creation of the instance)}
        \CommentTok{//}
        \CommentTok{//  Implementation uses GregorianCalendar class from the Java API}
        \CommentTok{//  to get today's date.}
        \CommentTok{//}
\NormalTok{        \{   }\BuiltInTok{GregorianCalendar}\NormalTok{ todaysDate = }\KeywordTok{new} \BuiltInTok{GregorianCalendar}\NormalTok{();}
\NormalTok{            year  = todaysDate.}\FunctionTok{get}\NormalTok{(}\BuiltInTok{Calendar}\NormalTok{.}\FunctionTok{YEAR}\NormalTok{);}
\NormalTok{            month = todaysDate.}\FunctionTok{get}\NormalTok{(}\BuiltInTok{Calendar}\NormalTok{.}\FunctionTok{MONTH}\NormalTok{) + }\DecValTok{1}\NormalTok{;}
\NormalTok{            day   = todaysDate.}\FunctionTok{get}\NormalTok{(}\BuiltInTok{Calendar}\NormalTok{.}\FunctionTok{DAY_OF_MONTH}\NormalTok{);}
\NormalTok{        \}}
          
        \KeywordTok{public} \FunctionTok{Day}\NormalTok{(}\DataTypeTok{int}\NormalTok{ y, }\DataTypeTok{int}\NormalTok{ m, }\DataTypeTok{int}\NormalTok{ d)}
               \KeywordTok{throws} \BuiltInTok{IllegalArgumentException}
        \CommentTok{//  Pre:   y != 0 && 1 <= m <= 12 && 1 <= d <= #days in month m}
        \CommentTok{//         (y,m,d) does not fall in the gap formed by the}
        \CommentTok{//             change to the modern (Gregorian) calendar.}
        \CommentTok{//  Post:  the new instance's day, month, and year set to y, m,}
        \CommentTok{//         and d, respectively  }
        \CommentTok{//  Exception:  IllegalArgumentException if y m d not a valid date}
\NormalTok{        \{   year  = y;}
\NormalTok{            month = m;}
\NormalTok{            day   = d;}
            \KeywordTok{if}\NormalTok{ (!}\FunctionTok{isValid}\NormalTok{())}
                \KeywordTok{throw} \KeywordTok{new} \BuiltInTok{IllegalArgumentException}\NormalTok{();}
\NormalTok{        \}}

      \CommentTok{// Mutators}

        \KeywordTok{public} \DataTypeTok{void} \FunctionTok{setDay}\NormalTok{(}\DataTypeTok{int}\NormalTok{ y, }\DataTypeTok{int}\NormalTok{ m, }\DataTypeTok{int}\NormalTok{ d)  }
                    \KeywordTok{throws} \BuiltInTok{IllegalArgumentException}
        \CommentTok{//  Pre:   y != 0 && 1 <= m <= 12 && 1 <= d <= #days in month m}
        \CommentTok{//         (y,m,d) does not fall in the gap formed by the}
        \CommentTok{//             change to the modern (Gregorian) calendar.}
        \CommentTok{//  Post:  this instance's day, month, and year set to y, m,}
        \CommentTok{//         and d, respectively  }
        \CommentTok{//  Exception:  IllegalArgumentException if y m d not a valid date}
\NormalTok{        \{   year  = y;}
\NormalTok{            month = m;}
\NormalTok{            day   = d;}
            \KeywordTok{if}\NormalTok{ (!}\FunctionTok{isValid}\NormalTok{())}
                \KeywordTok{throw} \KeywordTok{new} \BuiltInTok{IllegalArgumentException}\NormalTok{();}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{void} \FunctionTok{advance}\NormalTok{(}\DataTypeTok{int}\NormalTok{ n)}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  this instance's date moved n days later.  (Negative n}
        \CommentTok{//             moves to an earlier date.) }
\NormalTok{        \{   }\FunctionTok{fromJulian}\NormalTok{(}\FunctionTok{toJulian}\NormalTok{() + n);}
\NormalTok{        \}}

      \CommentTok{// Accessors}

        \KeywordTok{public} \DataTypeTok{int} \FunctionTok{getDay}\NormalTok{()}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  returns the day from this instance, where }
        \CommentTok{//             1 <= getDay() <= #days in this instance's month}
\NormalTok{        \{   }\KeywordTok{return}\NormalTok{ day;}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{int} \FunctionTok{getMonth}\NormalTok{()}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  returns the month from this instance's date, where}
        \CommentTok{//             1 <= getMonth() <= 12}
\NormalTok{        \{   }\KeywordTok{return}\NormalTok{ month;}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{int} \FunctionTok{getYear}\NormalTok{()}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  returns the year from this instance's date, where }
        \CommentTok{//             getYear() != 0}
\NormalTok{        \{   }\KeywordTok{return}\NormalTok{ year;}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{int} \FunctionTok{getWeekday}\NormalTok{()}
        \CommentTok{// Pre:   true}
        \CommentTok{// Post:  returns the day of the week upon which this instance}
        \CommentTok{//            falls, where 1 <= getWeekday() <= 7;}
        \CommentTok{//            1 == Sunday, 2 == Monday, ..., 7 == Saturday}
\NormalTok{        \{   }\CommentTok{//  calculate day of week}
            \KeywordTok{return}\NormalTok{ (}\FunctionTok{toJulian}\NormalTok{() + }\DecValTok{1}\NormalTok{) % }\DecValTok{7}\NormalTok{ + }\DecValTok{1}\NormalTok{;}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{boolean} \FunctionTok{equals}\NormalTok{(Day dd)}
        \CommentTok{//  Pre:   dd is a valid instance of Day}
        \CommentTok{//  Post:  returns true if and only if this instance and instance}
        \CommentTok{//             dd denote the same calendar date}
\NormalTok{        \{   }\KeywordTok{return}\NormalTok{ (year == dd.}\FunctionTok{getYear}\NormalTok{() && month == dd.}\FunctionTok{getMonth}\NormalTok{()}
\NormalTok{                    && day == dd.}\FunctionTok{getDay}\NormalTok{());}
\NormalTok{        \}}

        \KeywordTok{public} \DataTypeTok{int} \FunctionTok{daysBetween}\NormalTok{(Day dd)}
        \CommentTok{//  Pre:   dd is a valid instance of Day}
        \CommentTok{//  Post:  returns the number of calendar days from the dd}
        \CommentTok{//             instance's date to this instance's date, where}
        \CommentTok{//             equals(dd.advance(n)) would hold}
\NormalTok{        \{   }\CommentTok{//  implementation code}
            \KeywordTok{return} \FunctionTok{toJulian}\NormalTok{() - dd.}\FunctionTok{toJulian}\NormalTok{();}
\NormalTok{        \}}

        \KeywordTok{public} \BuiltInTok{String} \FunctionTok{toString}\NormalTok{()}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  returns this instance's date expressed in the format}
        \CommentTok{//             "Day[year,month,day]"}
\NormalTok{        \{}
            \KeywordTok{return} \StringTok{"Day["}\NormalTok{ + year + }\StringTok{","}\NormalTok{ + month + }\StringTok{","}\NormalTok{ + day + }\StringTok{"]"}\NormalTok{;}
\NormalTok{        \}}

      \CommentTok{//  Destructors -- None needed}

      \CommentTok{//  Private Methods}
     
        \KeywordTok{private} \DataTypeTok{boolean} \FunctionTok{isValid}\NormalTok{()}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  returns true iff this is a valid date}
\NormalTok{        \{   Day t = }\KeywordTok{new} \FunctionTok{Day}\NormalTok{();}
\NormalTok{            t.}\FunctionTok{fromJulian}\NormalTok{(}\KeywordTok{this}\NormalTok{.}\FunctionTok{toJulian}\NormalTok{());}
            \KeywordTok{return}\NormalTok{ t.}\FunctionTok{day}\NormalTok{ == day && t.}\FunctionTok{month}\NormalTok{ == month }
\NormalTok{                   && t.}\FunctionTok{year}\NormalTok{ == year;}
\NormalTok{        \}}

        \KeywordTok{private} \DataTypeTok{int} \FunctionTok{toJulian}\NormalTok{()}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  returns Julian day number that begins at noon of this day}
        \CommentTok{//}
        \CommentTok{//  A positive year signifies A.D., negative year B.C. }
        \CommentTok{//  Remember that the year after 1 B.C. was 1 A.D. (i.e., no year 0).}
        \CommentTok{//}
        \CommentTok{//  A convenient reference point is that May 23, 1968, at noon}
        \CommentTok{//  is Julian day 2440000.}
        \CommentTok{//}
        \CommentTok{//  Julian day 0 is a Monday.}
        \CommentTok{//}
        \CommentTok{//  This algorithm is from Press et al., Numerical Recipes}
        \CommentTok{//  in C, 2nd ed., Cambridge University Press 1992.}
        \CommentTok{//}
\NormalTok{        \{   }\DataTypeTok{int}\NormalTok{ jy = year;}
            \KeywordTok{if}\NormalTok{ (year < }\DecValTok{0}\NormalTok{) }
\NormalTok{                jy++;}
            \DataTypeTok{int}\NormalTok{ jm = month;}
            \KeywordTok{if}\NormalTok{ (month > }\DecValTok{2}\NormalTok{) }
\NormalTok{                jm++;}
            \KeywordTok{else}
\NormalTok{            \{   jy--;}
\NormalTok{                jm += }\DecValTok{13}\NormalTok{;}
\NormalTok{            \}}
            \DataTypeTok{int}\NormalTok{ jul = (}\DataTypeTok{int}\NormalTok{) (java.}\FunctionTok{lang}\NormalTok{.}\FunctionTok{Math}\NormalTok{.}\FunctionTok{floor}\NormalTok{(}\FloatTok{365.25}\NormalTok{ * jy) }
\NormalTok{                      + java.}\FunctionTok{lang}\NormalTok{.}\FunctionTok{Math}\NormalTok{.}\FunctionTok{floor}\NormalTok{(}\FloatTok{30.6001}\NormalTok{*jm) + day + }\FloatTok{1720995.0}\NormalTok{);}

            \DataTypeTok{int}\NormalTok{ IGREG = }\DecValTok{15}\NormalTok{ + }\DecValTok{31}\NormalTok{*(}\DecValTok{10}\NormalTok{+}\DecValTok{12}\NormalTok{*}\DecValTok{1582}\NormalTok{);}
                \CommentTok{// Gregorian Calendar adopted Oct. 15, 1582}

            \KeywordTok{if}\NormalTok{ (day + }\DecValTok{31}\NormalTok{ * (month + }\DecValTok{12}\NormalTok{ * year) >= IGREG)}
               \CommentTok{// change over to Gregorian calendar}
\NormalTok{            \{   }\DataTypeTok{int}\NormalTok{ ja = (}\DataTypeTok{int}\NormalTok{)(}\FloatTok{0.01}\NormalTok{ * jy);}
\NormalTok{                jul += }\DecValTok{2}\NormalTok{ - ja + (}\DataTypeTok{int}\NormalTok{)(}\FloatTok{0.25}\NormalTok{ * ja);}
\NormalTok{            \}}
            \KeywordTok{return}\NormalTok{ jul;}
\NormalTok{        \}}

        \KeywordTok{private} \DataTypeTok{void} \FunctionTok{fromJulian}\NormalTok{(}\DataTypeTok{int}\NormalTok{ j)}
        \CommentTok{//  Pre:   true}
        \CommentTok{//  Post:  this calendar Day is set to Julian date j}
        \CommentTok{//}
        \CommentTok{//  This algorithm is from Press et al., Numerical Recipes}
        \CommentTok{//  in C, 2nd ed., Cambridge University Press 1992}
        \CommentTok{//}
\NormalTok{        \{   }\DataTypeTok{int}\NormalTok{ ja = j;}
       
            \DataTypeTok{int}\NormalTok{ JGREG = }\DecValTok{2299161}\NormalTok{;}
                \CommentTok{/* the Julian date of the adoption of the Gregorian}
\CommentTok{                   calendar    }
\CommentTok{                */}   

            \KeywordTok{if}\NormalTok{ (j >= JGREG)}
            \CommentTok{/* correct for crossover to Gregorian Calendar */}   
\NormalTok{            \{   }\DataTypeTok{int}\NormalTok{ jalpha = (}\DataTypeTok{int}\NormalTok{)(((}\DataTypeTok{float}\NormalTok{)(j - }\DecValTok{1867216}\NormalTok{) - }\FloatTok{0.25}\NormalTok{) }
\NormalTok{                    / }\FloatTok{36524.25}\NormalTok{);}
\NormalTok{                ja += }\DecValTok{1}\NormalTok{ + jalpha - (}\DataTypeTok{int}\NormalTok{)(}\FloatTok{0.25}\NormalTok{ * jalpha);}
\NormalTok{            \}}
            \DataTypeTok{int}\NormalTok{ jb = ja + }\DecValTok{1524}\NormalTok{;}
            \DataTypeTok{int}\NormalTok{ jc = (}\DataTypeTok{int}\NormalTok{)(}\FloatTok{6680.0}\NormalTok{ + ((}\DataTypeTok{float}\NormalTok{)(jb}\DecValTok{-2439870}\NormalTok{) - }\FloatTok{122.1}\NormalTok{)}
\NormalTok{                     /}\FloatTok{365.25}\NormalTok{);}
            \DataTypeTok{int}\NormalTok{ jd = (}\DataTypeTok{int}\NormalTok{)(}\DecValTok{365}\NormalTok{ * jc + (}\FloatTok{0.25}\NormalTok{ * jc));}
            \DataTypeTok{int}\NormalTok{ je = (}\DataTypeTok{int}\NormalTok{)((jb - jd)/}\FloatTok{30.6001}\NormalTok{);}
\NormalTok{            day = jb - jd - (}\DataTypeTok{int}\NormalTok{)(}\FloatTok{30.6001}\NormalTok{ * je);}
\NormalTok{            month = je - }\DecValTok{1}\NormalTok{;}
            \KeywordTok{if}\NormalTok{ (month > }\DecValTok{12}\NormalTok{) }
\NormalTok{                month -= }\DecValTok{12}\NormalTok{;}
\NormalTok{            year = jc - }\DecValTok{4715}\NormalTok{;}
            \KeywordTok{if}\NormalTok{ (month > }\DecValTok{2}\NormalTok{) }
\NormalTok{                --year;}
            \KeywordTok{if}\NormalTok{ (year <= }\DecValTok{0}\NormalTok{) }
\NormalTok{                --year;}
\NormalTok{        \}}

        \CommentTok{//  Implementation Invariants:}
        \CommentTok{//      year != 0 && 1 <= month <= 12 && 1 <= day <= #days in month}
        \CommentTok{//      (year,month,day) not in gap formed by the change to the}
        \CommentTok{//      modern (Gregorian) calendar}

        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ year;  }
        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ month; }
        \KeywordTok{private} \DataTypeTok{int}\NormalTok{ day;}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

\hypertarget{acknowledgments}{%
\subsection{Acknowledgments}\label{acknowledgments}}

These notes were originally part of the \href{DataAbstraction.html}{Data
Abstraction} notes. I separated them into a separate document for the
Lua-based offerings of CSci 658 in Fall 2013. See the
\href{DataAbstraction.html\#acknowledgements}{Acknowledgments} section
of those notes for more information.

For the Elixir-based offering of CSci 556 Multiparadigm Programming in
Spring 2015 and the Scala-based offering of CSci 555 Functional
Programming in Spring 2016, I modified the notes to be more language
independent.

I modified this document slightly in 2017 to be launched from the
revised (Pandoc Markdown) version of the Data Abstraction document. I
reformatted this document to use Pandoc Markdown in Spring 2018.

The Java \texttt{Day} implementation is adapted from:

\begin{itemize}
\tightlist
\item
  Cay S. Horstmann and Gary Cornell. \emph{Core Java 1.2: Volume I -\/-
  Fundamentals}, Fourth Edition, Sun Microsystems Press, Prentice-Hall,
  1999.
\end{itemize}

\hypertarget{concepts}{%
\subsection{Concepts}\label{concepts}}

TODO

\end{document}
