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 text.
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:
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:
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]);
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
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.
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:
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';
}
@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.
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
Tas a generic symbol for any single type. - Use the letter
Eto refer to the element type in a generic collection. - You can restrict the range of allowable types by using the
extendskeyword 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.