You are previewing Introduction to the Art of Programming Using Scala.
O'Reilly logo
Introduction to the Art of Programming Using Scala

Book Description

With its flexibility for programming both small and large projects, Scala is an ideal language for teaching beginning programming. Yet there are no textbooks on Scala currently available for the CS1/CS2 levels. Introduction to the Art of Programming Using Scala presents many concepts from CS1 and CS2 using a modern, JVM-based language that works well for both programming in the small and programming in the large.

The book progresses from true programming in the small to more significant projects later, leveraging the full benefits of object orientation. It first focuses on fundamental problem solving and programming in the small using the REPL and scripting environments. It covers basic logic and problem decomposition and explains how to use GUIs and graphics in programs. The text then illustrates the benefits of object-oriented design and presents a large collection of basic data structures showing different implementations of key ADTs along with more atypical data structures. It also introduces multithreading and networking to provide further motivating examples.

By using Scala as the language for both CS1 and CS2 topics, this textbook gives students an easy entry into programming small projects as well as a firm foundation for taking on larger-scale projects. Many student and instructor resources are available at www.programmingusingscala.net

Table of Contents

  1. Preliminaries
  2. Acknowledgments
  3. Preface
    1. To the Student
      1. Using this Book
      2. Book Website
    2. To the Instructor
      1. Using this Book
      1. Figure 1
      1. 1.1 History
      2. 1.2 Hardware
      3. 1.3 Software
      4. 1.4 Nature of Programming
      5. 1.5 Programming Paradigms
        1. 1.5.1 Imperative Programming
        2. 1.5.2 Functional Programming
        3. 1.5.3 Object-Oriented Programming
        4. 1.5.4 Logic Programming
        5. 1.5.5 Nature of Scala
      6. 1.6 End of Chapter Material
        1. 1.6.1 Summary of Concepts
        2. 1.6.2 Exercises
        3. 1.6.3 Projects
        1. Figure 1.1
      1. 2.1 Unix/Linux (includes Mac OS X)
        1. 2.1.1 Command-Line
          1. 2.1.1.1 Files and Directories
          2. 2.1.1.2 Aside
          3. 2.1.1.3 Helpful Tips
          4. 2.1.1.4 Permissions
          5. 2.1.1.5 Compression/Archiving
          6. 2.1.1.6 Remote
          7. 2.1.1.7 Other Commands
        2. 2.1.2 I/O Redirection
        3. 2.1.3 Text Editors (vi/vim)
      2. 2.2 Windows
        1. 2.2.1 Command-Line
          1. 2.2.1.1 Files and Directories
        2. 2.2.2 Text Editors
          1. 2.2.2.1 Edit
          2. 2.2.2.2 Notepad
          3. 2.2.2.3 Others
        3. 2.2.3 Other Commands
      3. 2.3 Scala Tools
      4. 2.4 End of Chapter Material
        1. 2.4.1 Summary of Concepts
        2. 2.4.2 Exercises
        1. Figure 2.1
        2. Figure 2.2
        3. Figure 2.3
        4. Figure 2.4
      1. 3.1 Expressions, Types, and Basic Math
      2. 3.2 Objects and Methods
      3. 3.3 Other Basic Types
      4. 3.4 Back to the Numbers
        1. 3.4.1 Binary Arithmetic
        2. 3.4.2 Negative Numbers in Binary
        3. 3.4.3 Other Integer Types
        4. 3.4.4 Octal and Hexadecimal
        5. 3.4.5 Non-Integer Numbers
      5. 3.5 The math Object
      6. 3.6 Details of Char and String
      7. 3.7 Naming Values and Variables
      8. 3.8 Sequential Execution
        1. 3.8.1 Comments
      9. 3.9 A Tip for Learning to Program
      10. 3.10 End of Chapter Material
        1. 3.10.1 Problem-Solving Approach
        2. 3.10.2 Summary of Concepts
        3. 3.10.3 Self-Directed Study
        4. 3.10.4 Exercises
        1. Figure 3.1
        2. Figure 3.2
        1. Table 3.1
        2. Table 3.2
        3. Table 3.3
      1. 4.1 Motivating Example
      2. 4.2 The if Expression
      3. 4.3 Comparisons
      4. 4.4 Boolean Logic
      5. 4.5 Bigger Expressions
      6. Bit-wise Arithmetic
      7. 4.6 End of Chapter Material
        1. 4.6.1 Problem-Solving Approach
        2. 4.6.2 Summary of Concepts
        3. 4.6.3 Self-Directed Study
        4. 4.6.4 Exercises
        5. 4.6.5 Projects
        1. Table 4.1
        2. Table 4.2
        3. Table 4.3
        4. Table 4.4
      1. 5.1 Motivating Example
      2. 5.2 Function Refresher
      3. 5.3 Making and Using Functions
      4. 5.4 Problem Decomposition
      5. 5.5 Function Literals
      6. 5.6 Non-Functional Functions/Procedures
      7. 5.7 type Declarations
      8. 5.8 Putting it Together
      9. 5.9 End of Chapter Material
        1. 5.9.1 Problem-Solving Approach
        2. 5.9.2 Summary of Concepts
        3. 5.9.3 Self-Directed Study
        4. 5.9.4 Exercises
        5. 5.9.5 Projects
        1. Figure 5.1
        2. Figure 5.2
      1. 6.1 Basics of Recursion
      2. 6.2 Writing Recursion
      3. 6.3 User Input
      4. 6.4 Abstraction
      5. 6.5 Matching
      6. 6.6 Putting it Together
      7. 6.7 Looking Ahead
      8. 6.8 End of Chapter Material
        1. 6.8.1 Problem-Solving Approach
        2. 6.8.2 Summary of Concepts
        3. 6.8.3 Self-Directed Study
        4. 6.8.4 Exercises
        5. 6.8.5 Projects
        1. Figure 6.1
      1. 7.1 Making Arrays
      2. 7.2 Using Arrays
      3. 7.3 Lists
      4. 7.4 Standard Methods
        1. 7.4.1 Basic Methods
        2. 7.4.2 Higher-Order Methods
        3. 7.4.3 Combinatorial/Iterator Methods
      5. 7.5 A World of Types
        1. 7.5.1 The Option Type
        2. 7.5.2 Parametric Functions
        3. 7.5.3 Subtyping
      6. 7.6 Variable Length Argument Lists
      7. 7.7 Mutability and Aliasing
      8. 7.8 Basic Argument Passing
      9. 7.9 Pass-By-Name
      10. 7.10 Fill and Tabulate
      11. 7.11 Complete Grades Script/Software Development
      12. 7.12 End of Chapter Material
        1. 7.12.1 Problem-Solving Approach
        2. 7.12.2 Summary of Concepts
        3. 7.12.3 Self-Directed Study
        4. 7.12.4 Exercises
        5. 7.12.5 Projects
        1. Figure 7.1
        2. Figure 7.2
        3. Figure 7.3
        4. Figure 7.4
        5. Figure 7.5
        6. Figure 7.6
      1. 8.1 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">while</span> Loop Loop
      2. 8.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">do-while</span> Loop Loop
      3. 8.3 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">for</span> Loop Loop
        1. 8.3.1 Range Type
        2. 8.3.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">yield</span>
        3. 8.3.3 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">if</span> Guards Guards
        4. 8.3.4 Multiple Generators
        5. 8.3.5 Patterns in <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">for</span> Loops Loops
        6. 8.3.6 Variable Declarations
      4. 8.4 Multidimensional Arrays
      5. 8.5 Testing
      6. 8.6 Putting it Together
      7. 8.7 End of Chapter Material
        1. 8.7.1 Problem-Solving Approach
        2. 8.7.2 Summary of Concepts
        3. 8.7.3 Self-Directed Study
        4. 8.7.4 Exercises
        5. 8.7.5 Projects
      1. 9.1 I/O Redirection
      2. 9.2 Packages and <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">import</span> Statements Statements
      3. 9.3 Reading from Files
        1. 9.3.1 Iterators
        2. 9.3.2 String <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">split</span> Method Method
        3. 9.3.3 Reading from Other Things
        4. 9.3.4 Other Options (Java Based)
      4. 9.4 Writing to File
        1. 9.4.1 Appending to File
      5. 9.5 Use Case: Simple Encryption
        1. 9.5.1 Command-Line Arguments
        2. 9.5.2 Mapping a File
        3. 9.5.3 Character Offset
        4. 9.5.4 Alphabet Flip
        5. 9.5.5 Key Word
        6. 9.5.6 Putting it Together
        7. 9.5.7 Primes and Real Cryptography
      6. 9.6 End of Chapter Material
        1. 9.6.1 Summary of Concepts
        2. 9.6.2 Self-Directed Study
        3. 9.6.3 Exercises
        4. 9.6.4 Projects
      1. 10.1 User-Defined Types
      2. 10.2 Case Classes
        1. 10.2.1 Making Objects
        2. 10.2.2 Accessing Elements
        3. 10.2.3 Named and Default Arguments (Advanced)
        4. 10.2.4 The <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">copy</span> Method Method
        5. 10.2.5 Case Class Patterns
      3. 10.3 Mutable Classes
      4. 10.4 Putting it Together
      5. 10.5 End of Chapter Material
        1. 10.5.1 Summary of Concepts
        2. 10.5.2 Self-Directed Study
        3. 10.5.3 Exercises
        4. 10.5.4 Projects
      1. 11.1 GUI Libraries and History
      2. 11.2 GUI Components
        1. 11.2.1 Frames and Windows
        2. 11.2.2 Components
        3. 11.2.3 Panels and Panes
        4. 11.2.4 Menus
        5. 11.2.5 Tooltips
      3. 11.3 Basic Interactivity
        1. 11.3.1 Partial Functions
        2. 11.3.2 Publishers and Reactors
        3. 11.3.3 Mnemonics
      4. 11.4 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">FileChooser</span>
      5. 11.5 Tables
        1. 11.5.1 Table Actions
        2. 11.5.2 Table Models
      6. 11.6 Putting it Together
      7. 11.7 End of Chapter Material
        1. 11.7.1 Summary of Concepts
        2. 11.7.2 Self-Directed Study
        3. 11.7.3 Exercises
        4. 11.7.4 Projects
        1. Figure 11.1
        2. Figure 11.2
        3. Figure 11.3
      1. 12.1 Custom-Drawn Panels
      2. 12.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">java.awt.Graphics2D</span>
        1. 12.2.1 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">Shape</span>ss
        2. 12.2.2 Settings
          1. 12.2.2.1 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">Paint</span>
          2. 12.2.2.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">Stroke</span>
          3. 12.2.2.3 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">Font</span>
          4. 12.2.2.4 Clip
          5. 12.2.2.5 Transform
        3. 12.2.3 Affine Transforms
      3. 12.3 Images
        1. 12.3.1 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">BufferedImage</span>
        2. 12.3.2 Reading and Writing Images
        3. 12.3.3 Double Buffering
        4. 12.3.4 Revisiting TexturePaint
      4. 12.4 Other Events
        1. 12.4.1 Mouse Events
        2. 12.4.2 Keyboard Events
      5. 12.5 Animation with Timer
      6. 12.6 Putting it Together
      7. 12.7 End of Chapter Material
        1. 12.7.1 Summary of Concepts
        2. 12.7.2 Exercises
        3. 12.7.3 Projects
        1. Figure 12.1
        2. Figure 12.2
        3. Figure 12.3
        4. Figure 12.4
        5. Figure 12.5
        6. Figure 12.6
        7. Figure 12.7
      1. 13.1 Basic Comparison Sorts
        1. 13.1.1 Bubble Sort
        2. 13.1.2 Selection Sort (Min/Max)
        3. 13.1.3 Insertion Sort
        4. 13.1.4 Testing and Verifying Sorts
        5. 13.1.5 Sort Visualization
        6. 13.1.6 Order Analysis
        7. 13.1.7 Shell Sort (Diminishing Gap Sort)
      2. 13.2 Searching
        1. 13.2.1 Sequential Search (Linear Search)
        2. 13.2.2 Binary Search
      3. 13.3 Performance and Timing
      4. 13.4 Classifying Bugs
      5. 13.5 Memory Layout
      6. 13.6 Sorting/Searching with <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">case class</span>eses
      7. 13.7 Putting it Together
      8. 13.8 End of Chapter Material
        1. 13.8.1 Summary of Concepts
        2. 13.8.2 Exercises
        3. 13.8.3 Projects
        1. Table 13.1
      1. 14.1 Description of XML
        1. 14.1.1 Tags
        2. 14.1.2 Elements
        3. 14.1.3 Attributes
        4. 14.1.4 Content
        5. 14.1.5 Special Characters
        6. 14.1.6 Comments
        7. 14.1.7 Overall Format
        8. 14.1.8 Comparison to Flat File
          1. 14.1.8.1 Flexibility in XML
      2. 14.2 XML in Scala
        1. 14.2.1 Loading XML
        2. 14.2.2 Parsing XML
        3. 14.2.3 Building XML
        4. 14.2.4 Writing XML to File
        5. 14.2.5 XML Patterns
      3. 14.3 Putting it Together
      4. 14.4 End of Chapter Material
        1. 14.4.1 Summary of Concepts
        2. 14.4.2 Self-Directed Study
        3. 14.4.3 Exercises
        4. 14.4.4 Projects
      1. 15.1 Power of Recursion
      2. 15.2 Fibonacci Numbers
      3. 15.3 Permutations
      4. 15.4 Towers of Hanoi
      5. 15.5 Mazes
      6. 15.6 Sorts
        1. 15.6.1 Divide and Conquer Sorts
          1. 15.6.1.1 Merge Sort
          2. 15.6.1.2 Quicksort
      7. 15.7 Putting it Together
      8. 15.8 End of Chapter Material
        1. 15.8.1 Summary of Concepts
        2. 15.8.2 Exercises
        3. 15.8.3 Projects
        1. Figure 15.1
        2. Figure 15.2
      1. 16.1 Basics of Object-Orientation
        1. 16.1.1 Methods and Members
          1. 16.1.1.1 Parameters as Members
          2. 16.1.1.2 Visibility
        2. 16.1.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">this</span> Keyword Keyword
        3. 16.1.3 Encapsulation/Separating Interface from Implementation
        4. 16.1.4 Special Methods
          1. 16.1.4.1 Operator Methods
          2. 16.1.4.2 Unary Operators
          3. 16.1.4.3 Property Assignment Methods
          4. 16.1.4.4 The <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">apply</span> Method Method
          5. 16.1.4.5 The <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">update</span> Method Method
          6. 16.1.4.6 Overloading Methods
          7. 16.1.4.7 Vector Example
        5. 16.1.5 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">object</span> Declarations Declarations
          1. 16.1.5.1 Applications
          2. 16.1.5.2 Introduction to Companion Objects
        6. 16.1.6 Object Decomposition
      2. 16.2 Revisiting the API
      3. 16.3 Meaning of <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">case class</span>eses
      4. 16.4 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">import</span> Options Options
      5. 16.5 End of Chapter Material
        1. 16.5.1 Summary of Concepts
        2. 16.5.2 Exercises
        3. 16.5.3 Projects
        1. Figure 16.1
        1. Table 16.1
      1. 17.1 Eclipse IDE
      2. 17.2 Concurrent Versions System (CVS)
        1. 17.2.1 Making the Repository
        2. 17.2.2 Set-up in Eclipse
        3. 17.2.3 Getting Access on Other Systems
        4. 17.2.4 Repository Usage and Rules
      3. 17.3 Scaladoc Comments
      4. 17.4 End of Chapter Material
        1. 17.4.1 Summary of Concepts
        2. 17.4.2 Exercises
        3. 17.4.3 Projects
        1. Figure 17.1
        2. Figure 17.2
        3. Figure 17.3
        4. Figure 17.4
        5. Figure 17.5
        6. Figure 17.6
        7. Figure 17.7
        8. Figure 17.8
      1. 18.1 Software Development Stages
      2. 18.2 Analysis
      3. 18.3 Design
      4. 18.4 Making Packages
      5. 18.5 Project Analysis and Design
      6. 18.6 Implementing the GUI
      7. 18.7 End of Chapter Material
        1. 18.7.1 Summary of Concepts
        2. 18.7.2 Exercises
        3. 18.7.3 Projects
        1. Figure 18.1
        2. Figure 18.2
        3. Figure 18.3
        4. Figure 18.4
        5. Figure 18.5
      1. 19.1 Polymorphism
      2. 19.2 Inclusion Polymorphism (Inheritance and Subtyping)
        1. 19.2.1 private Visibility and Inheritance
        2. 19.2.2 Protected Visibility
        3. 19.2.3 Calling Methods on the Supertype
        4. 19.2.4 Anonymous Classes
        5. 19.2.5 Abstract Classes
        6. 19.2.6 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">traits</span>
        7. 19.2.7 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">final</span>
        8. 19.2.8 Method Resolution
        9. 19.2.9 Inheriting from Function Types
      3. 19.3 Inheritance in the Project
        1. 19.3.1 Drawables
        2. 19.3.2 Integration with Drawing
      4. 19.4 Parametric Polymorphism
        1. 19.4.1 Parametric Types
        2. 19.4.2 Parametric Functions and Methods
        3. 19.4.3 Type Bounds
      5. 19.5 End of Chapter Material
        1. 19.5.1 Summary of Concepts
        2. 19.5.2 Exercises
        3. 19.5.3 Projects
        1. Figure 19.1
        2. Figure 19.2
        3. Figure 19.3
        4. Figure 19.4
        5. Figure 19.5
        6. Figure 19.6
      1. 20.1 The scala.collection Packages
        1. 20.1.1 scala.collection.immutable
        2. 20.1.2 scala.collection.mutable
      2. 20.2 Sets
        1. 20.2.1 Running Through Sets
        2. 20.2.2 Mutable vs. Immutable
        3. 20.2.3 Using a Set
      3. 20.3 Maps
        1. 20.3.1 Looping Through a Map
        2. 20.3.2 Using Maps
      4. 20.4 Buffers
      5. 20.5 Collections as Functions
      6. 20.6 Project Integration
        1. 20.6.1 Commands
        2. 20.6.2 Adding Drawables
      7. 20.7 End of Chapter Material
        1. 20.7.1 Summary of Concepts
        2. 20.7.2 Exercises
        3. 20.7.3 Projects
        1. Figure 20.1
        2. Figure 20.2
        3. Figure 20.3
      1. 21.1 The Multicore Future
      2. 21.2 Basic Threads
        1. 21.2.1 Problems with Threads
          1. 21.2.1.1 Race Conditions
          2. 21.2.1.2 Deadlock
        2. 21.2.2 Synchronization
        3. 21.2.3 Wait/Notify
        4. 21.2.4 Other Thread Methods
      3. 21.3 Concurrency Library
        1. 21.3.1 Executors and Executor Services
        2. 21.3.2 Callable and Futures
        3. 21.3.3 Parallel Data Structures
          1. 21.3.3.1 Shared Barriers
          2. 21.3.3.2 The Exchange
          3. 21.3.3.3 Assembly Line
          4. 21.3.3.4 Ticketed Passengers
          5. 21.3.3.5 Other Threadsafe Types
        4. 21.3.4 Atomic (<span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">java.util.concurrent.atomic</span>))
        5. 21.3.5 Locks (<span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">java.util.concurrent.locks</span>))
      4. 21.4 Parallel Collections
      5. 21.5 Introduction to Scala Actors
      6. 21.6 Multithreaded Mandelbrot (Project Integration)
      7. 21.7 Multithreading in GUIs
      8. 21.8 Animated Bouncing Balls (Project Integration)
      9. 21.9 End of Chapter Material
        1. 21.9.1 Summary of Concepts
        2. 21.9.2 Exercises
        3. 21.9.3 Projects
        1. Figure 21.1
        2. Figure 21.2
        3. Figure 21.3
      1. 22.1 The <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">java.io</span> Package Package
      2. 22.2 Streams for Files
      3. 22.3 Exceptions
        1. 22.3.1 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">try-catch-finally</span>
        2. 22.3.2 Effect of Exceptions
        3. 22.3.3 Loan Pattern
      4. 22.4 Decorating Streams
        1. 22.4.1 Buffering
        2. 22.4.2 Binary Data
        3. 22.4.3 Serialization
          1. 22.4.3.1 Binary Serialization
          2. 22.4.3.2 XML Serialization
      5. 22.5 Saving Drawings (Project Integration)
      6. 22.6 End of Chapter Material
        1. 22.6.1 Summary of Concepts
        2. 22.6.2 Exercises
        3. 22.6.3 Projects
      1. 23.1 TCP and UDP
      2. 23.2 Sockets
        1. 23.2.1 TCP Sockets
        2. 23.2.2 UDP Sockets
        3. 23.2.3 Streams from Sockets
      3. 23.3 URLs
      4. 23.4 Remote Method Invocation (RMI)
      5. 23.5 Collaborative Drawing (Project Integration)
      6. 23.6 End of Chapter Material
        1. 23.6.1 Summary of Concepts
        2. 23.6.2 Exercises
        3. 23.6.3 Projects
        1. Figure 23.1
        2. Figure 23.2
        3. Figure 23.3
      1. 24.1 Abstract Data Types (ADTs)
      2. 24.2 Operations on Stacks and Queues
      3. 24.3 Real Meaning of <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="cItalic">O</span>
      4. 24.4 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="cItalic">O</span>(1) Requirement(1) Requirement
      5. 24.5 Array-Based Stack
      6. 24.6 Array-Based Queue
      7. 24.7 Unit Tests
        1. 24.7.1 Setup
        2. 24.7.2 Writing Tests
        3. 24.7.3 Test Suites
        4. 24.7.4 Test-Driven Development
      8. 24.8 RPN Calculator
      9. 24.9 End of Chapter Material
        1. 24.9.1 Summary of Concepts
        2. 24.9.2 Exercises
        3. 24.9.3 Projects
        1. Figure 24.1
        2. Figure 24.2
        3. Figure 24.3
        4. Figure 24.4
        5. Figure 24.5
      1. 25.1 The List/Seq ADT
      2. 25.2 Nature of Arrays
      3. 25.3 Nature of Linked Lists
      4. 25.4 Mutable Singly-Linked List
        1. 25.4.1 Implementing <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">mutable.Buffer</span>
        2. 25.4.2 Iterators
      5. 25.5 Mutable Doubly-Linked List
      6. 25.6 Immutable Singly-Linked List
      7. 25.7 Linked List-Based Stacks and Queues
        1. 25.7.1 Linked List-Based Stack
        2. 25.7.2 Linked List-Based Queue
      8. 25.8 End of Chapter Material
        1. 25.8.1 Summary of Concepts
        2. 25.8.2 Exercises
        3. 25.8.3 Projects
        1. Figure 25.1
      1. 26.1 Two Approaches
        1. 26.1.1 Searching by Priority
        2. 26.1.2 Sorted Linked List
        3. 26.1.3 Problems with Arrays
      2. 26.2 Project Integration: Discrete Event Simulation
        1. 26.2.1 Cell Splitting
        2. 26.2.2 Collision Handling
      3. 26.3 End of Chapter Material
        1. 26.3.1 Summary of Concepts
        2. 26.3.2 Exercises
        3. 26.3.3 Projects
        1. Figure 26.1
      1. 27.1 Smells
      2. 27.2 Refactorings
        1. 27.2.1 Built-in Refactoring Methods
        2. 27.2.2 Introduce Null Object
        3. 27.2.3 Add and Remove Parameter
        4. 27.2.4 Cures for Switch Statements
        5. 27.2.5 Consolidate Conditional Expression
        6. 27.2.6 Convert Procedural Design to Objects
        7. 27.2.7 Encapsulate Collection
        8. 27.2.8 Push Down or Pull Up Field or Method
        9. 27.2.9 Substitute Algorithm
      3. 27.3 End of Chapter Material
        1. 27.3.1 Summary of Concepts
        2. 27.3.2 Exercises
        3. 27.3.3 Projects
      1. 28.1 Refresher
      2. 28.2 Project Integration: A Maze
        1. 28.2.1 Revisiting the Basic Approach
        2. 28.2.2 Graphical Editing
        3. 28.2.3 Optimizing the Maze
      3. 28.3 Graph Traversals
      4. 28.4 Divide and Conquer
        1. 28.4.1 Merge Sort
        2. 28.4.2 Quicksort
        3. 28.4.3 Formula Parser
      5. 28.5 End of Chapter Material
        1. 28.5.1 Summary of Concepts
        2. 28.5.2 Exercises
        3. 28.5.3 Projects
      1. 29.1 General Trees
        1. 29.1.1 Implementations
        2. 29.1.2 Traversals
      2. 29.2 Project Integration: Formula Parsing
        1. 29.2.1 Formula Tree Traversals and In-order Traversal
      3. 29.3 Binary Search Trees: Binary Trees as Maps
        1. 29.3.1 Order Analysis
        2. 29.3.2 Immutable BSTs
      4. 29.4 End of Chapter Material
        1. 29.4.1 Summary of Concepts
        2. 29.4.2 Exercises
        3. 29.4.3 Projects
        1. Figure 29.1
        2. Figure 29.2
        3. Figure 29.3
        4. Figure 29.4
        5. Figure 29.5
        6. Figure 29.6
      1. 30.1 Chomsky Grammars
        1. 30.1.1 Regular Grammars
        2. 30.1.2 Context-Free Grammars
        3. 30.1.3 Context-Sensitive Grammars
        4. 30.1.4 Recursively Enumerable Grammars
      2. 30.2 Regular Expressions
        1. 30.2.1 Characters and Character Classes
        2. 30.2.2 Logical Operators and Capturing Groups
        3. 30.2.3 Greedy Quantifiers
        4. 30.2.4 Boundary Requirements
        5. 30.2.5 Using Regular Expressions in Code
        6. 30.2.6 Drawback of Regular Expressions
      3. 30.3 Context-Free Parsers
        1. 30.3.1 Default Output
        2. 30.3.2 Specified Output
      4. 30.4 Project Integration
      5. 30.5 End of Chapter Material
        1. 30.5.1 Summary of Concepts
        2. 30.5.2 Exercises
        3. 30.5.3 Projects
      1. 31.1 Spatial Data and Grids
      2. 31.2 Quadtrees and Octrees
      3. 31.3 kD-Trees
      4. 31.4 Efficient Bouncing Balls
      5. 31.5 End of Chapter Material
        1. 31.5.1 Summary of Concepts
        2. 31.5.2 Exercises
        3. 31.5.3 Projects
        1. Figure 31.1
        2. Figure 31.2
        3. Figure 31.3
      1. 32.1 Binary Heaps
        1. 32.1.1 Binary Heaps as Arrays
      2. 32.2 Heaps as Priority Queues
      3. 32.3 Heapsort
      4. 32.4 End of Chapter Material
        1. 32.4.1 Summary of Concepts
        2. 32.4.2 Exercises
        3. 32.4.3 Projects
        1. Figure 32.1
        2. Figure 32.2
        3. Figure 32.3
        4. Figure 32.4
        5. Figure 32.5
      1. 33.1 Random Access Files
        1. 33.1.1 Fixed Record Length
        2. 33.1.2 Indexed Variable Record Length
      2. 33.2 Linked Structures in Files
      3. 33.3 End of Chapter Material
        1. 33.3.1 Summary of Concepts
        2. 33.3.2 Exercises
        3. 33.3.3 Projects
        1. Figure 33.1
        2. Figure 33.2
        3. Figure 33.3
        1. Table 33.1
      1. 34.1 Actor Model
      2. 34.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">scala.actors</span> Package Package
        1. 34.2.1 The receive Method and Messages
        2. 34.2.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">react, loop</span>, and , and <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">loopWhile</span>
      3. 34.3 Circuit Simulation
      4. 34.4 End of Chapter Material
        1. 34.4.1 Summary of Concepts
        2. 34.4.2 Exercises
        3. 34.4.3 Projects
        1. Figure 34.1
        2. Figure 34.2
      1. 35.1 Augmentation of Trees
      2. 35.2 Balanced BSTs
        1. 35.2.1 Rotations
        2. 35.2.2 Implementation
      3. 35.3 Order-Statistic Trees: Trees as Sequences
      4. 35.4 Augmented Spatial Trees
      5. 35.5 End of Chapter Material
        1. 35.5.1 Summary of Concepts
        2. 35.5.2 Exercises
        3. 35.5.3 Projects
        1. Figure 35.1
        2. Figure 35.2
        3. Figure 35.3
      1. 36.1 What You Have Learned
      2. 36.2 The Possibilities/A Pet Project
        1. 36.2.1 General 2-D Application
        2. 36.2.2 3-D Application
        3. 36.2.3 Mobile
        4. 36.2.4 Web
        5. 36.2.5 GPGPU
        6. 36.2.6 AI, NLP, and Machine Learning
        7. 36.2.7 Open-Source and More
      3. 36.3 End of Chapter Material
        1. 36.3.1 Exercises
        2. 36.3.2 Projects
    1. A.1 Hello World
    2. A.2 Arrays, Primitives, and More
    3. A.3 File Names and Interfaces
    4. A.4 Constructors and <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">@Override</span>
    5. A.5 Generics and Polymorphism
    6. A.6 Lacking Functional Aspects
    7. A.7 Much More
    1. B.1 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">abstract</span> type Members type Members
    2. B.2 Enumerations
    3. B.3 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">implicit</span>ss
      1. B.3.1 Basic <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">implict</span> Converstions Converstions
      2. B.3.2 Rules and Limits on implicits
      3. B.3.3 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">implicit</span> Parameters Parameters
      4. B.3.4 The Meaning of <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">&lt;%</span>
    4. B.4 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">sealed class</span>eses
    5. B.5 Covariant, Contravariant, and Invariant Types
    6. B.6 Extractors
      1. B.6.1 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">unapply</span>
      2. B.6.2 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">unapplySeq</span>
    7. B.7 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">lazy</span> Member Data Member Data
    8. B.8 <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="code">scala.collection.immutable.Stream</span>
    9. B.9 Nested Types
    10. B.10 Self Types
    11. B.11 Making Executable JAR Files