Chapters
Chapters

Chapters

Hide chapters

Dart Apprentice: Beyond the Basics

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Dart Apprentice: Beyond the Basics

Section 1: 15 chapters
Show chapters Hide chapters

8. Generics
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a Kodeco Personal subscription.

Unlock now

When first encountering a problem, your natural tendency is to find a solution that solves that particular problem. You don’t worry about related problems; you care only about the problem that’s troubling you now.

Say you want to learn French. You might begin by trying to memorize sentences from a phrasebook. That turns out to be a slow and ineffective method. After trying several other language-learning techniques, you discover that lots of easy listening and reading input helps you learn much faster. Your problem is solved; you’ve learned French well enough to understand and communicate.

Then, you decide to learn Chinese. Do you return to the phrasebooks? Of course not. There’s no need to learn how to learn all over again. You already found a language-learning method that worked for you with French. You can use that same method with Chinese. You might need to pick up a few more techniques to help you learn those characters, but the overall method remains the same: lots of easy listening and reading input.

The more languages you learn, the better you get at learning languages. You’ve generalized the language learning process to the point where you know exactly how you would tackle any language.

Instead of French, Chinese or Urdu, now think String, bool and int. In Dart, generics refers to generalizing specific types so you can handle them all similarly. This chapter will teach not only how to use generic types but also how to create new generic classes and collections.

Using Generics

You’ve already encountered Dart generics earlier if you read Dart Apprentice: Fundamentals. In Chapter 12, “Lists”, you saw this example:

List<String> snacks = [];

Whenever you see the < > angle brackets surrounding a type, you should think, “Hey, that’s generics!” List is a generic collection. It can hold strings, integers, doubles or any other type. By specifying <String> in angle brackets, you’re declaring this list will hold only strings.

Replace the line above with a fuller example:

List<String> snacks = ['chips', 'nuts'];

Each element in the list is a string: 'chips' is a string and so is 'nuts'. If you tried to add the integer 42, Dart would complain at you.

See for yourself. Replace the line above with the following:

List<String> snacks = ['chips', 'nuts', 42];

The compiler gives the following error message:

The element type 'int' can't be assigned to the list type 'String'.

No integers are allowed in a string list! If you want to allow both integers and strings in the same list, you can set the list type to Object, which is a supertype of both String and int. Replace String in the line above with Object:

List<Object> snacks = ['chips', 'nuts', 42];

Now, the compiler no longer complains.

Because List is generic, it can contain any type. Here are some more examples:

List<int> integerList = [3, 1, 4];
List<double> doubleList = [3.14, 8.0, 0.001];
List<bool> booleanList = [true, false, false];

These are all generics at work. A single type List can store an ordered collection of any other type. There was no need to create different classes like IntList, DoubleList or BoolList for each type. If the language had been designed like that, it would have been like reinventing the wheel every time you needed a new list for a different type. Generics prevents code duplication.

All Dart collections use generics, not just List. For example, Set and Map do as well:

Set<int> integerSet = {3, 1, 4};
Map<int, String> intToStringMap = {1: 'one', 2: 'two', 3: 'three'};

Map uses generic types for both the key and the value. This means you can map int to String, or String to int, or bool to double and so on.

Using generic classes is easy enough. Now, you’ll take your skills to the next level by learning to create generic classes and functions.

Creating Generic Classes

Collections are where you see generics the most, so to give you something to practice on, you’re going to create a generic collection called a tree. Trees are an important data structure you’ll find in many computer science applications. Some examples include:

kelund gitxn yxahq cibg pvajk

7 3 5 3 1 4

Starting With a Non-Generic Integer Class

You’ll begin by creating a node and a tree in a non-generic way. Then, you’ll generalize your approach so it can handle any data type.

class IntNode {
  IntNode(this.value);
  int value;

  IntNode? leftChild;
  IntNode? rightChild;
}

IntNode createIntTree() {
  final zero = IntNode(0);
  final one = IntNode(1);
  final five = IntNode(5);
  final seven = IntNode(7);
  final eight = IntNode(8);
  final nine = IntNode(9);

  seven.leftChild = one;
  one.leftChild = zero;
  one.rightChild = five;
  seven.rightChild = nine;
  nine.leftChild = eight;

  return seven;
}

final intTree = createIntTree();

Reimplementing the Tree With String Nodes

You’ve built an integer tree. What would you need to change if you wanted to put strings in the tree like so:

zuva ihu pose eazcv sixob bisu 

class StringNode {
  StringNode(this.value);
  String value;

  StringNode? leftChild;
  StringNode? rightChild;
}

StringNode createStringTree() {
  final zero = StringNode('zero');
  final one = StringNode('one');
  final five = StringNode('five');
  final seven = StringNode('seven');
  final eight = StringNode('eight');
  final nine = StringNode('nine');

  seven.leftChild = one;
  one.leftChild = zero;
  one.rightChild = five;
  seven.rightChild = nine;
  nine.leftChild = eight;

  return seven;
}

final stringTree = createStringTree();

Comparing the Duplication

Currently, you’ve got a lot of code duplication. Here’s the integer node class again:

class IntNode {
  IntNode(this.value);
  int value;

  IntNode? leftChild;
  IntNode? rightChild;
}

class StringNode {
  StringNode(this.value);
  String value;

  StringNode? leftChild;
  StringNode? rightChild;
}

class BooleanNode {
  BooleanNode(this.value);
  bool value;

  BooleanNode? leftChild;
  BooleanNode? rightChild;
}

class DoubleNode {
  DoubleNode(this.value);
  double value;

  DoubleNode? leftChild;
  DoubleNode? rightChild;
}

Creating a Generic Node

Using generics allows you to remove all the duplication you saw in the previous section.

class Node<T> {
  Node(this.value);
  T value;

  Node<T>? leftChild;
  Node<T>? rightChild;
}

Updating the Integer Tree

Now, replace createIntTree with the updated version that uses generics:

Node<int> createIntTree() {
  final zero = Node(0);
  final one = Node(1);
  final five = Node(5);
  final seven = Node(7);
  final eight = Node(8);
  final nine = Node(9);

  seven.leftChild = one;
  one.leftChild = zero;
  one.rightChild = five;
  seven.rightChild = nine;
  nine.leftChild = eight;

  return seven;
}

final intTree = createIntTree();

Updating the String Tree

Update createStringTree in the same way. Replace the previous function with the following version:

Node<String> createStringTree() {
  final zero = Node('zero');
  final one = Node('one');
  final five = Node('five');
  final seven = Node('seven');
  final eight = Node('eight');
  final nine = Node('nine');

  seven.leftChild = one;
  one.leftChild = zero;
  one.rightChild = five;
  seven.rightChild = nine;
  nine.leftChild = eight;

  return seven;
}

Creating Generic Functions

You’ve successfully made a generic Node class. However, the functions you wrote to build your tree aren’t generic. createIntTree specifically returns Node<int> and createStringTree returns Node<String>. Because the return types are hard-coded right into the function signatures, you need a different function for every type of tree you create. This, too, is a lot of code duplication.

Storing a Tree in a List

Before giving you the code for the generic function, this is how it’s going to work:

final tree = createTree([7, 1, 9, 0, 5, 8]);
0 4 0 0 4 1 0 0 8 1 5 1 Luyak 1 Zehih 4 Ficay 2

Implementing the Function

Now that you’ve got a little background, add the following function below main:

// 1
Node<E>? createTree<E>(List<E> nodes, [int index = 0]) {
  // 2
  if (index >= nodes.length) return null;
  // 3
  final node = Node(nodes[index]);
  // 4
  final leftChildIndex = 2 * index + 1;
  final rightChildIndex = 2 * index + 2;
  // 5
  node.leftChild = createTree(nodes, leftChildIndex);
  node.rightChild = createTree(nodes, rightChildIndex);
  // 6
  return node;
}

Testing It Out

In main, write the following line:

final tree = createTree([7, 1, 9, 0, 5, 8]);

print(tree?.value);
print(tree?.leftChild?.value);
print(tree?.rightChild?.value);
print(tree?.leftChild?.leftChild?.value);
print(tree?.leftChild?.rightChild?.value);
print(tree?.rightChild?.leftChild?.value);
print(tree?.rightChild?.rightChild?.value);

7
1
9
0
5
8
null
7 9 7 4 0 6 

final tree = createTree(['seven', 'one', 'nine', 'zero', 'five', 'eight']);

seven
one
nine
zero
five
eight
null

Generics of a Specified Subtype

In the example above, your Node could hold data of any type. Sometimes, though, you don’t want to allow just any type. The values have to adhere to certain characteristics. A Binary Search Tree (BST) is an example of such a situation.

3 70 91 92 0 53 32 363 64 92 06

6 35 78 28 35 8 91 241 13 67 91

6 85 68 35 3 64 00 721 25 75 93

Implementing a Binary Search Tree

For BST to work, the types inside the nodes need to be comparable. It wouldn’t make sense to create a BST of User objects or Widget objects because these objects aren’t inherently comparable. That means you need a way of restricting the element type within the BST nodes.

class BinarySearchTree<E extends Comparable<E>> {
  Node<E>? root;
}

void insert(E value) {
  root = _insertAt(root, value);
}

Node<E> _insertAt(Node<E>? node, E value) {
  // 1
  if (node == null) {
    return Node(value);
  }
  // 2
  if (value.compareTo(node.value) < 0) {
    node.leftChild = _insertAt(node.leftChild, value);
  } else {
    node.rightChild = _insertAt(node.rightChild, value);
  }
  // 3
  return node;
}

Building the Tree

For the example below, you’ll create the following binary search tree:

1 3 6 1 6 1 

var tree = BinarySearchTree<num>();
tree.insert(7);
tree.insert(1);
tree.insert(9);
tree.insert(0);
tree.insert(5);
tree.insert(8);

@override
String toString() {
  final left = leftChild?.toString() ?? '';
  final parent = value.toString();
  final right = rightChild?.toString() ?? '';
  return '$left $parent $right';
}
6 8 2 5 7 4 7 1 9 8 8 2 

@override
String toString() => root.toString();

print(tree);

 0  1  5  7  8  9

Challenges

Before moving on, here are some challenges to test your knowledge of generics. It’s best if you try to solve them yourself, but solutions are available with the supplementary materials for this book if you get stuck.

Challenge 1: A Stack of Numbers

A stack is a first-in-last-out (FILO) data structure. When you add new values, you put them on top of the stack, covering up the old values. Likewise, when you remove values from the stack, you can only remove them from the top of the stack.

5 0 4 2

Challenge 2: A Stack of Anything

Generalize your solution in Challenge 1 by creating a Stack class that can hold data of any type.

Key Points

  • Generics allow classes and functions to accept data of any type.
  • The angle brackets surrounding a type tell the class or function the data type it will use.
  • Use the letter T as a generic symbol for any single type.
  • Use the letter E to refer to the element type in a generic collection.
  • You can restrict the range of allowable types by using the extends keyword within the angle brackets.

Where to Go From Here?

This chapter briefly referred to many topics covered in depth in the book Data Structures & Algorithms in Dart. Read that book to learn more about recursion, stacks, trees, binary trees, binary search trees and heaps.

7. Extension Methods
9. Enhanced Enums
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2023 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.

Unlock now

Access this book

To highlight or take notes, you'll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99