8 Generics

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 intto 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:

• Binary trees.
• Binary search trees.
• Priority Queues.
• Flutter UI widget trees.

A binary tree is one of the simplest types of trees. It consists of nodes, where each node can have up to two children. The image below illustrates this:

A node with children is called a parent, and the children are differentiated by calling them the left child and the right child.

In addition to having children, nodes also store a value. A tree that holds integers might look like so:

The top node of the tree is called the root node. Whoever put the root at the top of the tree was probably standing on their head that day.

The values in this particular tree are integers, but you could store any data type there.

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.

Create the following class below the main method in your Dart project:

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

  IntNode? leftChild;
  IntNode? rightChild;
}

IntNode has three properties. The constructor allows you to set the node’s value. leftChild and rightChild are optional because not every node has children.

Now, create the tree you saw in the diagram above by adding the following function below main:

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;
}

You return seven because it’s the root node and contains the links to the other nodes in the tree. Returning any other node would only provide a portion of the tree. Parents link to their children, not the other way around.

Now, in main, create the tree by calling your function:

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:

For that, you would need to change the node’s data type. However, you can’t change the data type of value in IntTree without messing up the integer tree you made earlier. So create a new class like the one below:

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

  StringNode? leftChild;
  StringNode? rightChild;
}

Now, value is of type String instead of int.

Next, add a function below main to create the tree of strings that you saw in the diagram above:

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;
}

The logic is all the same as the IntNode tree you made earlier.

Create the tree in main like so:

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;
}

And here’s the string node class:

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

  StringNode? leftChild;
  StringNode? rightChild;
}

And what if you wanted to make a tree of Boolean values? Here’s what the node class would look like:

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

  BooleanNode? leftChild;
  BooleanNode? rightChild;
}

And then, if you decided you needed a tree of floating-point values, you’d have to create a whole new class:

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

  DoubleNode? leftChild;
  DoubleNode? rightChild;
}

And on it goes for every new data type you want to use. You must create a new class to hold the new type, duplicating lots of code each time.

Creating a Generic Node

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

Add the following class to your project:

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

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

This time, the angle brackets show that this is a class with a generic type. The T here represents any type. You don’t have to use the letter T, but it’s customary to use single capital letters when specifying a generic type.

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;
}

This time, the return type is Node<int> instead of IntNode. You specify int inside the angle brackets so users of createIntTree know the values inside the tree are integers. Hover your cursor over zero, and you’ll see that Dart already infers the type to be Node<int> because it knows 0 is an integer.

Back in main, the code is still the same:

final intTree = createIntTree();

Hover your cursor over intTree, and you’ll see that the inferred type is Node<int>. Dart knows it because you wrote that as the return type of 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;
}

The function return type is Node<String> this time instead of StringNode. Check that your generic Node class works by hovering your cursor over zero. You’ll see the inferred type is also Node<String> because 'zero' is a String. Your generic Node class works!

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.

Generics are here to save the day because, in addition to generic classes, you can also make generic functions.

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]);

createTree will take a list of some data type, be it int, String or whatever. Then the function will convert the list to a binary tree. It’s possible to do that if you assume the first element in the list is the root-node value, the second element is the left-child value, the third element is the right-child value and so on, where the values in the list correspond to levels in the tree. The image below shows the list values and indexes laid out in a binary tree:

Note

This data structure where a list stores the values of a tree is known as a heap. Read Chapter 13, “Heaps”, in Data Structures & Algorithms in Dart to learn more.

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;
}

Here are some notes corresponding to the numbered comments above:

1. This time, the letter you’re using for the generic type is E instead of T. You could use T again, but it’s customary to use E when creating a collection, which is a tree of nodes in this case. The E stands for elements.
2. When working with trees, recursive functions are very useful. A recursive functionis a function that calls itself. If a function always calls itself, though, it could go on forever. Thus, it needs a way to stop calling itself. That’s known as the base case. The base case for this recursive function is when the list index is out of range.
3. Take the value in the list at the given index and convert it to a new node. The default value of index is 0, which is the root node.
4. In a binary tree where the values are laid out in a list by level, you can calculate the index of the left child by multiplying 2 times the parent index plus 1. The right child index is one beyond that.
5. Here’s the recursive part. The function calls itself to create the child nodes. You pass in the indexes where the child values should be. If those indexes are out of range for the list, the base case will stop the recursion.
6. At the end of each recursion, node is the parent of some branch in the tree. And when all the recursions are finished, node is the root node.

Did that make your brain hurt? No worries. Recursion does that to everybody. The point of this chapter is to understand generics, not recursion. However, if you’re interested, the best way to wrap your mind around recursion is to step through the code line by line and track what the computer is doing. You can do that with a paper and pencil. Or in Chapter 10, “Error Handling”, you’ll learn how to use the debugger in VS Code to pause execution and step through the code one line at a time. Feel free to jump ahead and learn how to do that now.

Note

In addition to using T to represent a single generic type and E to represent generic elements in a collection, there are a few other letters developers use by convention. For a generic map, as in Map<K, V>, use Kand V for the keys and values. Sometimes people use R for a function’s return type. You can use other letters like S and U if you’re already using T in the same generic function or class, though this is relatively rare.

Testing It Out

In main, write the following line:

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

You could write another recursive function to print the contents of the tree, but for now, just print the values manually. Add the following code to main, below what you wrote previously:

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);

Because the nodes of a tree could be null, you have to access the children with the ?.operator.

Run the code, and you’ll see the result below:

7
1
9
0
5
8
null

This matches the layered order of your input list.

createTree is generic, so you should be able to change the data type of the elements and still have the function work. Replace the createTree([7, 1, 9, 0, 5, 8]) line above with the following string version:

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

The numbers are the same, but this time you’re using strings.

Run the code again, and you’ll see the following:

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.

In a BST, the left child must always be less than the value of its parent, while the right child is always greater than or equal to the parent. Here’s an example:

18 is less than 40, so it goes on the left, whereas 77 is greater, so it goes on the right. Likewise, the children of 18 and 77 follow the same pattern.

BST has applications in fast lookup. Here’s how you would search for the value 105 in a list:

That took eleven steps.

Here’s how you would search for 105 in a BST:

That’s three steps instead of eleven. Much faster!

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.

The solution is to use the extends keyword. By only allowing data types that extend Comparable, you can guarantee the values in all the nodes will be comparable.

Create the following class:

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

Here are a few explanatory points:

• E represents the type of the elements in the tree.
• The extends keyword goes inside the angle brackets to restrict the types that E can be. Only types that extend Comparable are allowed.
• You’ll use the same Node class that you created earlier.

Now, add the following methods to BinarySearchTree:

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;
}

_insertAt is also a recursive function:

1. This is the base case. Create a new node if the parent node doesn’t have a child at this location.
2. compareTo is a method on types that extend Comparable. This method returns -1 if the first value is less than the second, +1 if it’s greater, and 0 if they’re the same. If the value is smaller, insert the node at the left child. Otherwise, insert it at the right child. Calling _insertAt recursively searches the tree until it finds an empty child.
3. When the recursion finishes, this function will return the root node.

Building the Tree

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

Add the code below to main:

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

You specified the type as num rather than int because int doesn’t directly implement Comparable, whereas num does.

To make printing easier, find your Node class and add the following override:

@override
String toString() {
  final left = leftChild?.toString() ?? '';
  final parent = value.toString();
  final right = rightChild?.toString() ?? '';
  return '$left $parent $right';
}

This recursively calls the toString methods of the left and right children. Because the parent value is calculated after the left child and before the right child, this is known as in-order traversal.

For a BST, this has the effect of printing the values in order from least to greatest:

Find BinarySearchTree and add the following override:

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

root is the root node of the tree, so calling root.toString provides a string representation of all the values in the tree, starting at the left-most node and ending with the right-most one.

Add the following line to main and run the code:

print(tree);

You should see the following output in the console:

 0  1  5  7  8  9

Your BST implementation works with integers. Because of generics, you wouldn’t have any problem with doubles, either. Even strings would work because String is also comparable. The insert method when used with strings, though, would determine “greater than” and “less than” according to alphabetical order.

This completes the chapter. Having a handle on generics gives you a lot of flexibility in your coding.

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.

Create a class named IntStack with the following methods:

• push: adds an integer to the top of the stack.
• pop: removes and returns the top integer from the stack.
• peek: tells the value of the top integer in the stack without removing it.
• isEmpty: tells whether the stack is empty or not.
• toString: returns a string representation of the stack.

Use a List as the internal data structure.

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.