Hands-On Data Structures and Algorithms with Rust: Learn programming techniques to build effective, maintainable, and readable code in Rust 2018

Hands-On Data Structures and Algorithms with Rust

Learn programming techniques to build effective, maintainable, and readable code in Rust 2018

Claus Matzinger

BIRMINGHAM - MUMBAI

Hands-On Data Structures and Algorithms with Rust

Copyright © 2019 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author(s), nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.

Commissioning Editor: Richa Tripathi

Acquisition Editor: Shahnish Khan

Content Development Editor: Zeeyan Pinheiro

Technical Editor: Romy Dias

Copy Editor: Safis Editing

Project Coordinator: Vaidehi Sawant

Proofreader: Safis Editing

Indexer: Priyanka Dhadke

Graphics: Alishon Mendonsa

Production Coordinator: Tom Scaria

First published: January 2019

Production reference: 1230119

Published by Packt Publishing Ltd.

Livery Place

35 Livery Street

Birmingham

B3 2PB, UK.

ISBN 978-1-78899-552-8

www.packtpub.com

mapt.io

Mapt is an online digital library that gives you full access to over 5,000 books and videos, as well as industry leading tools to help you plan your personal development and advance your career. For more information, please visit our website.

Why subscribe?

Spend less time learning and more time coding with practical eBooks and Videos from over 4,000 industry professionals

Improve your learning with Skill Plans built especially for you

Get a free eBook or video every month

Mapt is fully searchable

Copy and paste, print, and bookmark content

Packt.com

Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.packt.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at [email protected] for more details.

At www.packt.com, you can also read a collection of free technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on Packt books and eBooks. 

Foreword

Rust is not an easy language to learn. Ask why, and you'll hear that Rust was designed to solve almost any complex problem in system programming, a complicated domain to begin with. It was designed to do it safely, to be incredibly fast, and be very strict; ease of use is a necessary sacrifice. Rust reads like any other imperative language, but it incorporates a number of special concepts that ask you to think through your problems in greater depth and with a different spin than you're used to. It's brutally honest about the complicated parts a system language has to address.

Those are the typical reasons cited for why Rust is hard. The more honest answer is that those people may not have the right teacher.

I met Claus at my first event as an open source developer for Microsoft. He had joined just a few months before, and could show me the ropes. It didn't occur to me until a few weeks later that, as his manager, I was supposed to be teaching him! I've discovered that this is a common situation for Claus: he falls naturally into a teaching role. Not a lecturing bore, either—the kind of teaching where the student doesn't realize that's what's happening until they find themselves using newly acquired knowledge. We've long since moved into other roles, but I've seen the pattern repeated over and over again.

Early in his career as an open source developer, Claus found himself diving deep into documentation. And fair enough: it's often the most important part of a project! Just three lines, he said to me once. I just lost a whole day of my life because someone didn't bother to write three lines of good documentation. I can fix that.

Claus's background was in academic software development, but in his professional life, he has rejected the dry, abstract computer science theory often taught in that environment. He is one of those rare developers who cares deeply about making this easy for people to understand. It's important that it makes sense, it's important that it looks nice, it's important that it's easy to follow—and how to make it that way is intuitive to him. I think it honestly doesn't occur to him that other people struggle to explain things the way he does naturally.

One of the aspects of this book that I appreciated the most when reading it is the balance Claus strikes. It stays focused on the teaching goal without getting sidetracked by more technical detail than is required. We all know the feeling of reading that kind of documentation—the kind that demands to be skimmed. Most readers, including myself, are simply confused by too much theory or detail at the outset. As Claus puts it, most teachers make it sound like something really fancy is going on, but, in reality, it's quite simple. 

This practical approach has made Claus an in-demand speaker, community member, and contributor in the Rust world. This book is his next step into teaching for a broader audience, and I'm excited to see its impact.

You've chosen a great teacher! Rust is difficult to learn, but it doesn't have to be. Just ask Claus.

Campbell Vertesi

Principal Software Engineer Manager

twitter: @ohthehugemanatee

ohthehugemanatee.org

Contributors

About the author

Claus Matzinger is a software engineer with a very diverse background. After working in a small company maintaining code for embedded devices, he joined a large corporation to work on legacy Smalltalk applications. This led to a great interest in programming languages early on, and Claus became the CTO for a health games start-up based on Scala technology.

Since then, Claus' roles have shifted toward customer-facing roles in the IoT database-technology start-up crate.io and, most recently, Microsoft. There, he hosts a podcast, writes code together with customers, and blogs about the solutions arising from these engagements. For more than 5 years, Claus has implemented software to help customers innovate, achieve, and maintain success.

Any large project is a joint effort, and many people have helped me create this book. There is the Rust community, who eagerly helped with my questions; the Packt team, who provided comments on my writing; my colleagues, with whom I kept discussing language details; and—above all—my future wife, who gave me the space and support to write every day.

Thank you, all!

About the reviewer

Ivo Balbaert is a former lecturer in (web) programming and databases at CVO Antwerpen, a community college in Belgium. He received a Ph.D. in applied physics from the University of Antwerp in 1986. He worked in the software industry for 20 years, as a developer and consultant in several companies, and for 10 years as a project manager at Antwerp University Hospital. From 2000 onward, he switched to part-time teaching, developing software, and writing technical books.

In 2012, he authored The Way To Go, a book on the Go programming language. He also wrote a number of introductory books on new programming languages, including Dart, Crystal, Julia, Rust, and Red, most of them published by Packt.

Packt is searching for authors like you

If you're interested in becoming an author for Packt, please visit authors.packtpub.com and apply today. We have worked with thousands of developers and tech professionals, just like you, to help them share their insight with the global tech community. You can make a general application, apply for a specific hot topic that we are recruiting an author for, or submit your own idea.

Table of Contents

Title Page

Copyright and Credits

Hands-On Data Structures and Algorithms with Rust

About Packt

Why subscribe?

Packt.com

Foreword

Contributors

About the author

About the reviewer

Packt is searching for authors like you

Preface

Who this book is for

What this book covers

To get the most out of this book

Download the color images

Download the example code files

Conventions used

Get in touch

Reviews

Hello Rust!

Rust in 2018

The 2018 edition

The Rust language

Objects and behavior

Going wrong

Macros

Unsafe

Borrowing and ownership

Exceptional lifetimes

Multiple owners

Concurrency and mutability

Immutable variables

Shadowing

Interior mutability

Moving data

Sharing data

Send and Sync

Deeper into Rust

Requests for Comments (RFCs)

Summary

Questions

Further reading

Cargo and Crates

Cargo

Project configuration

The manifest – Cargo.toml

Package

Profiles

Dependencies

Dependencies – Cargo.lock

Commands

The compile and run commands

Testing

Third-party subcommands

Crates

Rust libraries and binaries

Static and dynamic libraries

Linking and interoperability

FFI

Wasm

The main repository – crates.io

Publishing

Summary

Questions

Further reading

Storing Efficiently

Heaps and stacks

Sized and unsized

Generics

Accessing the box

Copying and cloning

Immutable storage

States and reasoning

Concurrency and performance

Summary

Questions

Further reading

Lists, Lists, and More Lists

Linked lists

A transaction log

Adding entries

Log replay

After use

Wrap up

Upsides

Downsides

Doubly linked list

A better transaction log

Examining the log

Reverse

Wrap up

Upsides

Downsides

Skip lists

The best transaction log

The list

Adding data

Leveling up

Jumping around

Thoughts and discussion

Upsides

Downsides

Dynamic arrays

Favorite transactions

Internal arrays

Quick access

Wrap up

Upsides

Downsides

Summary

Questions

Further reading

Robust Trees

Binary search tree

IoT device management

More devices

Finding the right one

Finding all devices

Wrap up

Upsides

Downsides

Red-black tree

Better IoT device management

Even more devices

Balancing the tree

Finding the right one, now

Wrap up

Upsides

Downsides

Heaps

A huge inbox

Getting messages in

Taking messages out

Wrap up

Upsides

Downsides

Trie

More realistic IoT device management

Adding paths

Walking

Wrap up

Upsides

Downsides

B-Tree

An IoT database

Adding stuff

Searching for stuff

Walking the tree

Wrap up

Upsides

Downsides

Graphs

The literal Internet of Things

Neighborhood search

The shortest path

Wrap up

Upsides

Downsides

Summary

Questions

Exploring Maps and Sets

Hashing

Create your own

Message digestion

Wrap up

Maps

A location cache

The hash function

Adding locations

Fetching locations

Wrap up

Upsides

Downsides

Sets

Storing network addresses

Networked operations

Union

Intersection

Difference

Wrap up

Upsides

Downsides

Summary

Questions

Further reading

Collections in Rust

Sequences

Vec<T> and VecDeque<T>

Architecture

Insert

Look up

Remove

LinkedList<T>

Architecture

Insert

Look up

Remove

Wrap up

Maps and sets

HashMap and HashSet

Architecture

Insert

Lookup

Remove

BTreeMap and BTreeSet

Architecture

Insert

Look up

Remove

Wrap up

Summary

Questions

Further reading

Algorithm Evaluation

The Big O notation

Other people's code

The Big O

Asymptotic runtime complexity

Making your own

Loops

Recursion

Complexity classes

O(1)

O(log(n))

O(n)

O(n log(n))

O(n²)

O(2n)

Comparison

In the wild

Data structures

Everyday things

Exotic things

Summary

Questions

Further reading

Ordering Things

From chaos to order

Bubble sort

Shell sort

Heap sort

Merge sort

Quicksort

Summary

Questions

Further reading

Finding Stuff

Finding the best

Linear searches

Jump search

Binary searching

Wrap up

Summary

Questions

Further reading

Random and Combinatorial

Pseudo-random numbers

LCG

Wichmann-Hill

The rand crate

Back to front

Packing bags or the 0-1 knapsack problem

N queens

Advanced problem solving

Dynamic programming

The knapsack problem improved

Metaheuristic approaches

Example metaheuristic – genetic algorithms

Summary

Questions

Further reading

Algorithms of the Standard Library

Slicing and iteration

Iterator

Slices

Search

Linear search

Binary search

Sorting

Stable sorting

Unstable sorting

Summary

Questions

Further reading

Assessments

Chapter 1

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

Chapter 7

Chapter 8

Chapter 9

Chapter 10

Chapter 11

Chapter 12

Other Books You May Enjoy

Leave a review - let other readers know what you think

Preface

When I first made the effort of learning one programming language a year, I started with Ruby, then learned a bit of Scala, until, in 2015, I started with a very new language: Rust. My first attempts at creating a Slack (a team chat program) bot were somewhat successful but very frustrating. Being used to Python's flexibility with JSON data and permissive compiler, Rust's steep learning curve quickly took its toll.

The next projects were more successful. A database driver, as well as my very own Internet of Things (IoT)-type client and server application for the Raspberry Pi, allowed me to collect temperature data in a rock-solid manner. Unlike Python, if the program compiled, it would almost certainly work as expected—and I loved it.

Since then, a lot has changed. Big companies such as Microsoft and Amazon are picking up Rust as a way to create safe and fast code on embedded devices as well as in the cloud. With WebAssembly (Wasm), Rust is gaining traction in the web frontend space, and gaming companies are starting to build game engines in Rust. 2018 has been a great year for the technology and the Rust community, both of which will continue to grow in 2019 (and beyond).

For this reason, I hope to provide a learning resource for creating more sophisticated Rust code from a practical angle. Wherever your journey leads you, learning about Rust and its various programming models will change your view of code for the better.

Who this book is for

Rust has great tutorials for learning the fundamentals of the language. There are workshops at every conference, regular meetups in many cities, and a very helpful online community. However, many developers find themselves beyond these resources but still don't feel ready for more complex solutions. Especially coming from different backgrounds with years of experience, the transition can be daunting: examples on the one side feature some type of a Hello World! program; on the other side, there are huge Rust open source projects with thousands of lines of code – impossible to learn from quickly. If you feel like this, then this book is for you.

What this book covers

Chapter 1, Hello Rust!, gives a short recap of the Rust programming language and what changed in the 2018 edition.

Chapter 2, Cargo and Crates, discusses Rust's cargo build tool. We will explore the configuration as well as the build process and modularization options.

Chapter 3, Storing Efficiently, looks at how in Rust, knowing where values are stored is not only important for performance, but also important for understanding error messages and the language in general. In this chapter, we think about stack and heap memory.  

Chapter 4, Lists, Lists, and More Lists, covers the first data structures: lists. Using several examples, this chapter goes into variations of sequential data structures and their implementations.

Chapter 5, Robust Trees, continues our journey through popular data structures: trees are next on the list. In several detailed examples, we explore the inner workings of these efficient designs and how they improve application performance considerably. 

Chapter 6, Exploring Maps and Sets, explores the most popular key-value stores: maps. In this chapter, techniques surrounding hash maps; hashing; and their close relative, the set; are described in detail. 

Chapter 7, Collections in Rust, attempts to connect to the Rust programmer's daily life, going into the details of the Rust std::collections library, which contains the various data structures provided by the Rust standard library.

Chapter 8, Algorithm Evaluation, teaches you how to evaluate and compare algorithms. 

Chapter 9, Ordering Things, will look at sorting values, an important task in programming—this chapter uncovers how that can be done quickly and safely.

Chapter 10, Finding Stuff, moves onto searching, which is especially important if there is no fundamental data structure to support it. In these cases, we use algorithms to be able to quickly find what we are looking for. 

Chapter 11, Random and Combinatorial, is where we will see that, outside of sorting and searching, there are many problems that can be tackled algorithmically. This chapter is all about those: random number generation, backtracking, and improving computational complexities.

Chapter 12, Algorithms of the Standard Library, explores how the Rust standard library does things when it comes to everyday algorithmic tasks such as sorting and searching.

To get the most out of this book

This book comes with a lot of code examples and implementations. For you to learn the most that you can, it is recommended to install Rust (any version later than 1.33 should do) and run all of the examples. Here are a few recommendations for text editors and other tools:

Microsoft's Visual Studio Code (https://code.visualstudio.com/), arguably one of the best Rust code editors

Rust support for Visual Studio Code via a plugin (https://github.com/rust-lang/rls-vscode) 

Rust Language Server (RLS), found at https://github.com/rust-lang/rls-vscode, installed via rustup (https://rustup.rs/)

Debugging support using the LLDB frontend plugin (https://github.com/vadimcn/vscode-lldb) for Visual Studio Code

Having this environment set up and being familiar with it is great for your daily Rust programming, and will let you debug and inspect the workings of the code provided in this book. For you to get the most out of this book, we recommend that you do the following:

Check out the source code in the repository to get the whole picture. The snippets are only isolated examples to show specifics.

Don't blindly trust our results; run the tests and benchmarks of each sub-project (chapters) to reproduce the findings yourself.

Download the color images

We also provide a PDF file that has color images of the screenshots/diagrams used in this book. You can download it here https://www.packtpub.com/sites/default/files/downloads/9781788995528_ColorImages.pdf.

Download the example code files

You can download the example code files for this book from your account at www.packt.com. If you purchased this book elsewhere, you can visit www.packt.com/support and register to have the files emailed directly to you.

You can download the code files by following these steps:

Log in or register at www.packt.com.

Select the SUPPORT tab.

Click on Code Downloads & Errata.

Enter the name of the book in the Search box and follow the onscreen instructions.

Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:

WinRAR/7-Zip for Windows

Zipeg/iZip/UnRarX for Mac

7-Zip/PeaZip for Linux

The code bundle for the book is also hosted on GitHub at https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Rust. In case there's an update to the code, it will be updated on the existing GitHub repository.

We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

Conventions used

There are a number of text conventions used throughout this book.

CodeInText: Indicates code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles. Here is an example: The reason is that the passing_through variable outlives x.

A block of code is set as follows:

fn my_function() {

    let x = 10;

    do_something(x); // ownership is moved here

    let y = x; // x is now invalid!

}

When we wish to draw your attention to a particular part of a code block, the relevant lines or items are set in bold:

fn main() {

let mut a = 42;

    let b = &a; // borrow a

    let c = &mut a; // borrow a again, mutably

    // ... but don't ever use b

}

Any command-line input or output is written as follows:

$ cargo test

Bold: Indicates a new term, an important word, or words that you see onscreen. For example, words in menus or dialog boxes appear in the text like this. Here is an example: Select System info from the Administration panel.

Warnings or important notes appear like this.

Tips and tricks appear like this.

Get in touch

Feedback from our readers is always welcome.

General feedback: If you have questions about any aspect of this book, mention the book title in the subject of your message and email us at [email protected].

Errata: Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you have found a mistake in this book, we would be grateful if you would report this to us. Please visit www.packt.com/submit-errata, selecting your book, clicking on the Errata Submission Form link, and entering the details.

Piracy: If you come across any illegal copies of our works in any form on the Internet, we would be grateful if you would provide us with the location address or website name. Please contact us at [email protected] with a link to the material.

If you are interested in becoming an author: If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, please visit authors.packtpub.com.

Reviews

Please leave a review. Once you have read and used this book, why not leave a review on the site that you purchased it from? Potential readers can then see and use your unbiased opinion to make purchase decisions, we at Packt can understand what you think about our products, and our authors can see your feedback on their book. Thank you!

For more information about Packt, please visit packt.com.

Hello Rust!

First, thank you for picking up a copy of this book! Many of you will only have talked about the topic of algorithms and data structures back in university. In fact, regardless of whether this is your first endeavor in programming or not, we worked hard to make this book a great learning experience. Our primary focus will be the unique influence of Rust on algorithm and data structure design, so we would like to start with a recap of important fundamentals.

Starting off with the Rust 2018 edition changes, we will cover how borrowing and ownership, mutability, and concurrency influence how and where data can be held, and what algorithms can be executed. In this chapter, you can look forward to learning about the following:

A quick refresh on Rust and what awaits in the 2018 edition (Rust 1.31)

The latest and greatest about borrowing and ownership

How we can leverage concurrency and mutability properly

References (not pointers!) to where Rust lives

Rust in 2018

How old is Rust? It started off in 2006 as a side project of Graydon Hoare, an engineer at Mozilla, and was later (in 2009) adopted by the company. Fast forward to less than a decade later to May 15, 2015, and the Rust team announced a stable version 1.0!

During its journey, there have been many features that have been added and removed again (for example, a garbage collector, classes, and interfaces) to help it become the fast and safe language that it is today.

Before getting deeper into borrowing and ownership, mutability, concurrency, safety, and so on in Rust, we would like to recap some major concepts in Rust and why they change architectural patterns significantly.

The 2018 edition

Rust in the 2015 edition is essentially the 1.0 version with a few non-breaking additions. Between 2015 and 2018, however, features and Requests for Comments (RFCs), Rust's way of changing core features with the community, accumulated, and worries about backward compatibility arose.

With the goal of keeping this compatibility, editions