book

Introduction to the Art of Programming Using Scala

Name: Introduction to the Art of Programming Using Scala
Author: Mark C. Lewis
ISBN: 9781498759687

by Mark C. Lewis

November 2012

Beginner

936 pages

28h 4m

English

Chapman and Hall/CRC

Read now

Unlock full access

Preliminaries
Acknowledgments
Preface
To the StudentUsing this BookBook WebsiteTo the InstructorUsing this BookFigure 1
Part I Introductory Concepts
Chapter 1 Basics of Computers, Computing, and Programming
1.1 History1.2 Hardware1.3 Software1.4 Nature of Programming1.5 Programming Paradigms1.5.1 Imperative Programming1.5.2 Functional Programming1.5.3 Object-Oriented Programming1.5.4 Logic Programming1.5.5 Nature of Scala1.6 End of Chapter Material1.6.1 Summary of Concepts1.6.2 Exercises1.6.3 ProjectsFigure 1.1
Chapter 2 Getting to Know the Tools
2.1 Unix/Linux (includes Mac OS X)2.1.1 Command-Line2.1.1.1 Files and Directories2.1.1.2 Aside2.1.1.3 Helpful Tips2.1.1.4 Permissions2.1.1.5 Compression/Archiving2.1.1.6 Remote2.1.1.7 Other Commands2.1.2 I/O Redirection2.1.3 Text Editors (vi/vim)2.2 Windows2.2.1 Command-Line2.2.1.1 Files and Directories2.2.2 Text Editors2.2.2.1 Edit2.2.2.2 Notepad2.2.2.3 Others2.2.3 Other Commands2.3 Scala Tools2.4 End of Chapter Material2.4.1 Summary of Concepts2.4.2 ExercisesFigure 2.1Figure 2.2Figure 2.3Figure 2.4
Chapter 3 Scala Basics
3.1 Expressions, Types, and Basic Math3.2 Objects and Methods3.3 Other Basic Types3.4 Back to the Numbers3.4.1 Binary Arithmetic3.4.2 Negative Numbers in Binary3.4.3 Other Integer Types3.4.4 Octal and Hexadecimal3.4.5 Non-Integer Numbers3.5 The math Object3.6 Details of Char and String3.7 Naming Values and Variables3.8 Sequential Execution3.8.1 Comments3.9 A Tip for Learning to Program3.10 End of Chapter Material3.10.1 Problem-Solving Approach3.10.2 Summary of Concepts3.10.3 Self-Directed Study3.10.4 ExercisesFigure 3.1Figure 3.2Table 3.1Table 3.2Table 3.3
Chapter 4 Conditionals
4.1 Motivating Example4.2 The if Expression4.3 Comparisons4.4 Boolean Logic4.5 Bigger ExpressionsBit-wise Arithmetic4.6 End of Chapter Material4.6.1 Problem-Solving Approach4.6.2 Summary of Concepts4.6.3 Self-Directed Study4.6.4 Exercises4.6.5 ProjectsTable 4.1Table 4.2Table 4.3Table 4.4
Chapter 5 Functions
5.1 Motivating Example5.2 Function Refresher5.3 Making and Using Functions5.4 Problem Decomposition5.5 Function Literals5.6 Non-Functional Functions/Procedures5.7 type Declarations5.8 Putting it Together5.9 End of Chapter Material5.9.1 Problem-Solving Approach5.9.2 Summary of Concepts5.9.3 Self-Directed Study5.9.4 Exercises5.9.5 ProjectsFigure 5.1Figure 5.2
Chapter 6 Recursion for Iteration
6.1 Basics of Recursion6.2 Writing Recursion6.3 User Input6.4 Abstraction6.5 Matching6.6 Putting it Together6.7 Looking Ahead6.8 End of Chapter Material6.8.1 Problem-Solving Approach6.8.2 Summary of Concepts6.8.3 Self-Directed Study6.8.4 Exercises6.8.5 ProjectsFigure 6.1

Chapter 7 Arrays and Lists in Scala
7.1 Making Arrays7.2 Using Arrays7.3 Lists7.4 Standard Methods7.4.1 Basic Methods7.4.2 Higher-Order Methods7.4.3 Combinatorial/Iterator Methods7.5 A World of Types7.5.1 The Option Type7.5.2 Parametric Functions7.5.3 Subtyping7.6 Variable Length Argument Lists7.7 Mutability and Aliasing7.8 Basic Argument Passing7.9 Pass-By-Name7.10 Fill and Tabulate7.11 Complete Grades Script/Software Development7.12 End of Chapter Material7.12.1 Problem-Solving Approach7.12.2 Summary of Concepts7.12.3 Self-Directed Study7.12.4 Exercises7.12.5 ProjectsFigure 7.1Figure 7.2Figure 7.3Figure 7.4Figure 7.5Figure 7.6
Chapter 8 Loops
8.1 while Loop8.2 do-while Loop8.3 for Loop8.3.1 Range Type8.3.2 yield8.3.3 if Guards8.3.4 Multiple Generators8.3.5 Patterns in for Loops8.3.6 Variable Declarations8.4 Multidimensional Arrays8.5 Testing8.6 Putting it Together8.7 End of Chapter Material8.7.1 Problem-Solving Approach8.7.2 Summary of Concepts8.7.3 Self-Directed Study8.7.4 Exercises8.7.5 Projects
Chapter 9 Text Files
9.1 I/O Redirection9.2 Packages and import Statements9.3 Reading from Files9.3.1 Iterators9.3.2 String split Method9.3.3 Reading from Other Things9.3.4 Other Options (Java Based)9.4 Writing to File9.4.1 Appending to File9.5 Use Case: Simple Encryption9.5.1 Command-Line Arguments9.5.2 Mapping a File9.5.3 Character Offset9.5.4 Alphabet Flip9.5.5 Key Word9.5.6 Putting it Together9.5.7 Primes and Real Cryptography9.6 End of Chapter Material9.6.1 Summary of Concepts9.6.2 Self-Directed Study9.6.3 Exercises9.6.4 Projects
Chapter 10 Case Classes
10.1 User-Defined Types10.2 Case Classes10.2.1 Making Objects10.2.2 Accessing Elements10.2.3 Named and Default Arguments (Advanced)10.2.4 The copy Method10.2.5 Case Class Patterns10.3 Mutable Classes10.4 Putting it Together10.5 End of Chapter Material10.5.1 Summary of Concepts10.5.2 Self-Directed Study10.5.3 Exercises10.5.4 Projects
Chapter 11 GUIs
11.1 GUI Libraries and History11.2 GUI Components11.2.1 Frames and Windows11.2.2 Components11.2.3 Panels and Panes11.2.4 Menus11.2.5 Tooltips11.3 Basic Interactivity11.3.1 Partial Functions11.3.2 Publishers and Reactors11.3.3 Mnemonics11.4 FileChooser11.5 Tables11.5.1 Table Actions11.5.2 Table Models11.6 Putting it Together11.7 End of Chapter Material11.7.1 Summary of Concepts11.7.2 Self-Directed Study11.7.3 Exercises11.7.4 ProjectsFigure 11.1Figure 11.2Figure 11.3
Chapter 12 Graphics
12.1 Custom-Drawn Panels12.2 java.awt.Graphics2D12.2.1 Shapes12.2.2 Settings12.2.2.1 Paint12.2.2.2 Stroke12.2.2.3 Font12.2.2.4 Clip12.2.2.5 Transform12.2.3 Affine Transforms12.3 Images12.3.1 BufferedImage12.3.2 Reading and Writing Images12.3.3 Double Buffering12.3.4 Revisiting TexturePaint12.4 Other Events12.4.1 Mouse Events12.4.2 Keyboard Events12.5 Animation with Timer12.6 Putting it Together12.7 End of Chapter Material12.7.1 Summary of Concepts12.7.2 Exercises12.7.3 ProjectsFigure 12.1Figure 12.2Figure 12.3Figure 12.4Figure 12.5Figure 12.6Figure 12.7
Chapter 13 Sorting and Searching
13.1 Basic Comparison Sorts13.1.1 Bubble Sort13.1.2 Selection Sort (Min/Max)13.1.3 Insertion Sort13.1.4 Testing and Verifying Sorts13.1.5 Sort Visualization13.1.6 Order Analysis13.1.7 Shell Sort (Diminishing Gap Sort)13.2 Searching13.2.1 Sequential Search (Linear Search)13.2.2 Binary Search13.3 Performance and Timing13.4 Classifying Bugs13.5 Memory Layout13.6 Sorting/Searching with case classes13.7 Putting it Together13.8 End of Chapter Material13.8.1 Summary of Concepts13.8.2 Exercises13.8.3 ProjectsTable 13.1
Chapter 14 XML
14.1 Description of XML14.1.1 Tags14.1.2 Elements14.1.3 Attributes14.1.4 Content14.1.5 Special Characters14.1.6 Comments14.1.7 Overall Format14.1.8 Comparison to Flat File14.1.8.1 Flexibility in XML14.2 XML in Scala14.2.1 Loading XML14.2.2 Parsing XML14.2.3 Building XML14.2.4 Writing XML to File14.2.5 XML Patterns14.3 Putting it Together14.4 End of Chapter Material14.4.1 Summary of Concepts14.4.2 Self-Directed Study14.4.3 Exercises14.4.4 Projects
Chapter 15 Recursion
15.1 Power of Recursion15.2 Fibonacci Numbers15.3 Permutations15.4 Towers of Hanoi15.5 Mazes15.6 Sorts15.6.1 Divide and Conquer Sorts15.6.1.1 Merge Sort15.6.1.2 Quicksort15.7 Putting it Together15.8 End of Chapter Material15.8.1 Summary of Concepts15.8.2 Exercises15.8.3 ProjectsFigure 15.1Figure 15.2
Part II Object-Orientation, Abstraction, and Data Structures
Chapter 16 Object-Orientation
16.1 Basics of Object-Orientation16.1.1 Methods and Members16.1.1.1 Parameters as Members16.1.1.2 Visibility16.1.2 this Keyword16.1.3 Encapsulation/Separating Interface from Implementation16.1.4 Special Methods16.1.4.1 Operator Methods16.1.4.2 Unary Operators16.1.4.3 Property Assignment Methods16.1.4.4 The apply Method16.1.4.5 The update Method16.1.4.6 Overloading Methods16.1.4.7 Vector Example16.1.5 object Declarations16.1.5.1 Applications16.1.5.2 Introduction to Companion Objects16.1.6 Object Decomposition16.2 Revisiting the API16.3 Meaning of case classes16.4 import Options16.5 End of Chapter Material16.5.1 Summary of Concepts16.5.2 Exercises16.5.3 ProjectsFigure 16.1Table 16.1
Chapter 17 Bigger Programs/New Tools
17.1 Eclipse IDE17.2 Concurrent Versions System (CVS)17.2.1 Making the Repository17.2.2 Set-up in Eclipse17.2.3 Getting Access on Other Systems17.2.4 Repository Usage and Rules17.3 Scaladoc Comments17.4 End of Chapter Material17.4.1 Summary of Concepts17.4.2 Exercises17.4.3 ProjectsFigure 17.1Figure 17.2Figure 17.3Figure 17.4Figure 17.5Figure 17.6Figure 17.7Figure 17.8
Chapter 18 A Project (Drawing Program)
18.1 Software Development Stages18.2 Analysis18.3 Design18.4 Making Packages18.5 Project Analysis and Design18.6 Implementing the GUI18.7 End of Chapter Material18.7.1 Summary of Concepts18.7.2 Exercises18.7.3 ProjectsFigure 18.1Figure 18.2Figure 18.3Figure 18.4Figure 18.5
Chapter 19 Abstraction and Polymorphism
19.1 Polymorphism19.2 Inclusion Polymorphism (Inheritance and Subtyping)19.2.1 private Visibility and Inheritance19.2.2 Protected Visibility19.2.3 Calling Methods on the Supertype19.2.4 Anonymous Classes19.2.5 Abstract Classes19.2.6 traits19.2.7 final19.2.8 Method Resolution19.2.9 Inheriting from Function Types19.3 Inheritance in the Project19.3.1 Drawables19.3.2 Integration with Drawing19.4 Parametric Polymorphism19.4.1 Parametric Types19.4.2 Parametric Functions and Methods19.4.3 Type Bounds19.5 End of Chapter Material19.5.1 Summary of Concepts19.5.2 Exercises19.5.3 ProjectsFigure 19.1Figure 19.2Figure 19.3Figure 19.4Figure 19.5Figure 19.6
Chapter 20 Other Collection Types
20.1 The scala.collection Packages20.1.1 scala.collection.immutable20.1.2 scala.collection.mutable20.2 Sets20.2.1 Running Through Sets20.2.2 Mutable vs. Immutable20.2.3 Using a Set20.3 Maps20.3.1 Looping Through a Map20.3.2 Using Maps20.4 Buffers20.5 Collections as Functions20.6 Project Integration20.6.1 Commands20.6.2 Adding Drawables20.7 End of Chapter Material20.7.1 Summary of Concepts20.7.2 Exercises20.7.3 ProjectsFigure 20.1Figure 20.2Figure 20.3
Chapter 21 Multithreading and Concurrency
21.1 The Multicore Future21.2 Basic Threads21.2.1 Problems with Threads21.2.1.1 Race Conditions21.2.1.2 Deadlock21.2.2 Synchronization21.2.3 Wait/Notify21.2.4 Other Thread Methods21.3 Concurrency Library21.3.1 Executors and Executor Services21.3.2 Callable and Futures21.3.3 Parallel Data Structures21.3.3.1 Shared Barriers21.3.3.2 The Exchange21.3.3.3 Assembly Line21.3.3.4 Ticketed Passengers21.3.3.5 Other Threadsafe Types21.3.4 Atomic (java.util.concurrent.atomic)21.3.5 Locks (java.util.concurrent.locks)21.4 Parallel Collections21.5 Introduction to Scala Actors21.6 Multithreaded Mandelbrot (Project Integration)21.7 Multithreading in GUIs21.8 Animated Bouncing Balls (Project Integration)21.9 End of Chapter Material21.9.1 Summary of Concepts21.9.2 Exercises21.9.3 ProjectsFigure 21.1Figure 21.2Figure 21.3
Chapter 22 Stream I/O
22.1 The java.io Package22.2 Streams for Files22.3 Exceptions22.3.1 try-catch-finally22.3.2 Effect of Exceptions22.3.3 Loan Pattern22.4 Decorating Streams22.4.1 Buffering22.4.2 Binary Data22.4.3 Serialization22.4.3.1 Binary Serialization22.4.3.2 XML Serialization22.5 Saving Drawings (Project Integration)22.6 End of Chapter Material22.6.1 Summary of Concepts22.6.2 Exercises22.6.3 Projects
Chapter 23 Networking
23.1 TCP and UDP23.2 Sockets23.2.1 TCP Sockets23.2.2 UDP Sockets23.2.3 Streams from Sockets23.3 URLs23.4 Remote Method Invocation (RMI)23.5 Collaborative Drawing (Project Integration)23.6 End of Chapter Material23.6.1 Summary of Concepts23.6.2 Exercises23.6.3 ProjectsFigure 23.1Figure 23.2Figure 23.3
Chapter 24 Stacks and Queues
24.1 Abstract Data Types (ADTs)24.2 Operations on Stacks and Queues24.3 Real Meaning of O24.4 O(1) Requirement24.5 Array-Based Stack24.6 Array-Based Queue24.7 Unit Tests24.7.1 Setup24.7.2 Writing Tests24.7.3 Test Suites24.7.4 Test-Driven Development24.8 RPN Calculator24.9 End of Chapter Material24.9.1 Summary of Concepts24.9.2 Exercises24.9.3 ProjectsFigure 24.1Figure 24.2Figure 24.3Figure 24.4Figure 24.5
Chapter 25 Linked Lists
25.1 The List/Seq ADT25.2 Nature of Arrays25.3 Nature of Linked Lists25.4 Mutable Singly-Linked List25.4.1 Implementing mutable.Buffer25.4.2 Iterators25.5 Mutable Doubly-Linked List25.6 Immutable Singly-Linked List25.7 Linked List-Based Stacks and Queues25.7.1 Linked List-Based Stack25.7.2 Linked List-Based Queue25.8 End of Chapter Material25.8.1 Summary of Concepts25.8.2 Exercises25.8.3 ProjectsFigure 25.1
Chapter 26 Priority Queues
26.1 Two Approaches26.1.1 Searching by Priority26.1.2 Sorted Linked List26.1.3 Problems with Arrays26.2 Project Integration: Discrete Event Simulation26.2.1 Cell Splitting26.2.2 Collision Handling26.3 End of Chapter Material26.3.1 Summary of Concepts26.3.2 Exercises26.3.3 ProjectsFigure 26.1
Chapter 27 Refactoring
27.1 Smells27.2 Refactorings27.2.1 Built-in Refactoring Methods27.2.2 Introduce Null Object27.2.3 Add and Remove Parameter27.2.4 Cures for Switch Statements27.2.5 Consolidate Conditional Expression27.2.6 Convert Procedural Design to Objects27.2.7 Encapsulate Collection27.2.8 Push Down or Pull Up Field or Method27.2.9 Substitute Algorithm27.3 End of Chapter Material27.3.1 Summary of Concepts27.3.2 Exercises27.3.3 Projects
Chapter 28 Recursion
28.1 Refresher28.2 Project Integration: A Maze28.2.1 Revisiting the Basic Approach28.2.2 Graphical Editing28.2.3 Optimizing the Maze28.3 Graph Traversals28.4 Divide and Conquer28.4.1 Merge Sort28.4.2 Quicksort28.4.3 Formula Parser28.5 End of Chapter Material28.5.1 Summary of Concepts28.5.2 Exercises28.5.3 Projects
Chapter 29 Trees
29.1 General Trees29.1.1 Implementations29.1.2 Traversals29.2 Project Integration: Formula Parsing29.2.1 Formula Tree Traversals and In-order Traversal29.3 Binary Search Trees: Binary Trees as Maps29.3.1 Order Analysis29.3.2 Immutable BSTs29.4 End of Chapter Material29.4.1 Summary of Concepts29.4.2 Exercises29.4.3 ProjectsFigure 29.1Figure 29.2Figure 29.3Figure 29.4Figure 29.5Figure 29.6
Chapter 30 Regular Expressions and Context-Free Parsers
30.1 Chomsky Grammars30.1.1 Regular Grammars30.1.2 Context-Free Grammars30.1.3 Context-Sensitive Grammars30.1.4 Recursively Enumerable Grammars30.2 Regular Expressions30.2.1 Characters and Character Classes30.2.2 Logical Operators and Capturing Groups30.2.3 Greedy Quantifiers30.2.4 Boundary Requirements30.2.5 Using Regular Expressions in Code30.2.6 Drawback of Regular Expressions30.3 Context-Free Parsers30.3.1 Default Output30.3.2 Specified Output30.4 Project Integration30.5 End of Chapter Material30.5.1 Summary of Concepts30.5.2 Exercises30.5.3 Projects
Chapter 31 Spatial Trees
31.1 Spatial Data and Grids31.2 Quadtrees and Octrees31.3 kD-Trees31.4 Efficient Bouncing Balls31.5 End of Chapter Material31.5.1 Summary of Concepts31.5.2 Exercises31.5.3 ProjectsFigure 31.1Figure 31.2Figure 31.3
Chapter 32 Binary Heaps
32.1 Binary Heaps32.1.1 Binary Heaps as Arrays32.2 Heaps as Priority Queues32.3 Heapsort32.4 End of Chapter Material32.4.1 Summary of Concepts32.4.2 Exercises32.4.3 ProjectsFigure 32.1Figure 32.2Figure 32.3Figure 32.4Figure 32.5
Chapter 33 Direct Access Binary Files
33.1 Random Access Files33.1.1 Fixed Record Length33.1.2 Indexed Variable Record Length33.2 Linked Structures in Files33.3 End of Chapter Material33.3.1 Summary of Concepts33.3.2 Exercises33.3.3 ProjectsFigure 33.1Figure 33.2Figure 33.3Table 33.1
Chapter 34 Actors
34.1 Actor Model34.2 scala.actors Package34.2.1 The receive Method and Messages34.2.2 react, loop, and loopWhile34.3 Circuit Simulation34.4 End of Chapter Material34.4.1 Summary of Concepts34.4.2 Exercises34.4.3 ProjectsFigure 34.1Figure 34.2
Chapter 35 Augmenting Trees
35.1 Augmentation of Trees35.2 Balanced BSTs35.2.1 Rotations35.2.2 Implementation35.3 Order-Statistic Trees: Trees as Sequences35.4 Augmented Spatial Trees35.5 End of Chapter Material35.5.1 Summary of Concepts35.5.2 Exercises35.5.3 ProjectsFigure 35.1Figure 35.2Figure 35.3
Chapter 36 Wrapping Up
36.1 What You Have Learned36.2 The Possibilities/A Pet Project36.2.1 General 2-D Application36.2.2 3-D Application36.2.3 Mobile36.2.4 Web36.2.5 GPGPU36.2.6 AI, NLP, and Machine Learning36.2.7 Open-Source and More36.3 End of Chapter Material36.3.1 Exercises36.3.2 Projects
Appendix A Quick Preview of Java
A.1 Hello WorldA.2 Arrays, Primitives, and MoreA.3 File Names and InterfacesA.4 Constructors and @OverrideA.5 Generics and PolymorphismA.6 Lacking Functional AspectsA.7 Much More
Appendix B Advanced Scala Concepts
B.1 abstract type MembersB.2 EnumerationsB.3 implicitsB.3.1 Basic implict ConverstionsB.3.2 Rules and Limits on implicitsB.3.3 implicit ParametersB.3.4 The Meaning of <%B.4 sealed classesB.5 Covariant, Contravariant, and Invariant TypesB.6 ExtractorsB.6.1 unapplyB.6.2 unapplySeqB.7 lazy Member DataB.8 scala.collection.immutable.StreamB.9 Nested TypesB.10 Self TypesB.11 Making Executable JAR Files
Appendix C Glossary
Bibliography

Content preview from Introduction to the Art of Programming Using Scala

Chapter 29

Trees

"I think that I shall never see

A poem as lovely as a tree." - Joyce Kilmer

In this chapter you will learn about the concept of a tree as they are known in Computer Science. While we will not be writing poems about them, we will construct some lovely code to provide efficient implementations of some Abstract Data Type (ADT).

29.1 General Trees

Chapter 25 introduced the concept of the linked structure using the simplest form of a linked list. The most general expression of a linked structure is the graph that was briefly presented in chapter 28. A tree is a linked structure that falls somewhere between these two extremes. Like the other two, a tree is formed of nodes with edges between them. We consider these edges to have a direction, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781439896679

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Introduction to the Art of Programming Using Scala

by Mark C. Lewis

Trees

29.1 General Trees

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.