(^44) | Chapter 3: Patterns and Domains

(protected)

Declares that the attribute or method is visible to the class or any of its
subclasses; if the underlying implementation is Java, then the attribute or
method is also visible to classes within the same package. Note that in our
C++ implementations, we do not use multiple inheritance or friend classes,
so the semantics are nearly identical.
~ (package-private)
Declares that the attribute or method is visible only to classes within the same
package; used only by Java designs.

• (private)
  Declares that the attribute is visible only to the class itself in which the
  attribute is defined. We intentionally do not list in the class diagram any
  private methods that may exist.

• (public)
  Declares that the attribute or method is visible and accessible to anyone.
  Public attributes are, in general, assumed to be “final” as well, implying that
  they are constant even within the same class.
  Class methods declare their return type (which may bevoid) and parameter list
  (which may be empty). Constructor methods have the same name as the class
  within which they are defined. Destructor methods (only in C++) can be identi-
  fied by the “~” symbol in their name. Naturally the reader may be confused
  between a C++ destructor and a Java package-private method, since they use the
  same symbol. Look to the accompanying text in the algorithm chapters, which
  will help differentiate these two situations.
  In Java, there is an additional type of relationship between a class and an inter-
  face that the class implements. For example, SegmentTreeNode implements
  IInterval, which means thatSegmentTreeNodemust complete the implementation
  of methods specified only inIInterval. This relationship is depicted in Figure 3-3
  by means of a dashed line terminating in an open triangle.

Empirical Evaluation Format

The implementations of the algorithms are all executed with a series of bench-

mark problems, appropriate for each individual algorithm. The appendix provides

more detail on the mechanisms used for timing purposes. In general, we execute

all algorithms on two different platforms: a common desktop environment and a

high-end Linux cluster. Together these provide a range within which most

systems should exist. To properly evaluate the performance, a test suite is

composed of a set ofkindividual trials (typicallyk≥10). The best and worst

performers are discarded as outliers, the remainingk–2 trials are aggregated, and

the average and standard deviations are computed. Tables are shown with

problem size instances ranging fromn=2 to 2^20.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use