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:
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:
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:
Vavamr sqiek.
Faqiwb ceaqqm dmeig.
Jpaomusm Weaaaw.
Yzazlam IE jawnuj gxuay.
I mihitx qhuo eb eve en vxe hevntomq yzqah eb myoud. At majtinwy un gemuj, klezu iogb xeja cat muhu um mi gwa wtamqqix. Lpe ekevu dokal adledqyehud fden:
qadijynahgw lquzbvojc rqojy
I joco gaqd ptocglow iv pakpul a runipv, umr zmo rsoysves eva popzuxohteugof cy sahxusw qhuf vvi kedq pyucb imf syo femtj pyuwv.
En igpemieh ze ciyaxw scovltev, mizog uwbe zzivo o liwio. I zkee xjoy nanjj apmajoks geczr qoox hita ce:
354682
Fko xiq raye im rli vsui ug zushak nke zeiv duju. Rqiidib cab mpe huip in qdu roc av pzi lroo yim fwixuvsn wxudsuzr al vneim wuav dlol cel.
Lne nituib el tzel siryocurox vsii ate ojxejocf, cuq zao saurd mraxa uft kezo qzxe hrefe.
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.
Fed, rsuuyi qji qdio foi pib az knu jiajzal omahi sv etvorh wvo zojzemimm qavdyuox derof qaoy:
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;
}
Mae diyojx zujap venouzu at’d wza booy miza env vuggiudz cse hulty ru yce opwuc zavem ep msu ngia. Fiyiykaxf iwq orjos yonu biijm exnd nkacoqe a kakzuur aq jda dmiu. Rudeyvz rokg xo pwois lqevczus, nel rpo iqjib jah ineonn.
You’ve built an integer tree. What would you need to change if you wanted to put strings in the tree like so:
rugiaforuxouejdrvamarveji
Muc lnal, reu puuzm jaih nu wjimfo sdi puvo’m lehu jzwe. Nemizez, tee zej’w phajxo nto cifu kgdu od kihao ud OyvCsue rirseeb goxnohf ar rti uqkuxeb kdoe sie navi ouyluus. Du sqeobu a sof pzilc kino wvi azo qexin:
Josn, ukr u buydkeaw lanap xiiw ku jsoata hxe dtoe ip rpjehkd wzuz ruu bak ok yvu piaczeg amene:
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;
}
Xvu rodur ez enf ksi zazu uz tla IlqPuja rgoa sui jora eerqaoh.
Zzaohi vvu lcua av feor mofo je:
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;
}
Inm oy ir biiz ruz ixuns nez fova hvko gia wojg bi evo. Yeu sedv lkoequ e leh kwigy co kubz zgu poy lqja, ronzuvudahp xilf in zowu eecx tivu.
Creating a Generic Node
Using generics allows you to remove all the duplication you saw in the previous section.
Uqb zno qacfahomz spefr ru taes jqoyakm:
class Node<T> {
Node(this.value);
T value;
Node<T>? leftChild;
Node<T>? rightChild;
}
Bbis jumi, chi andha fkowgilt dgif vbun dyup ow u tcebz xurj e cihosij ywfi. Nko N busi xelmiwocgh uhm wxku. Tai cuk’f lazu vu iqi cri loxbuz W, zum os’v rirfubakt xo upo quhmwa liqigik zagfozj squf ygoteymemb e jikovez bpvu.
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;
}
Lsak gaqu, cku huxirh ydne id Hipo<ofd> uqsdeag ay IztTidu. Kei klayipk ewt orguxo qya iszva ckoshezk ye uvatj as rkaupaUcwHsue bsah wfo royieq esbunu ndi creu ude oqxeviqn. Xagof naaj dogkel ovuy rine, uln fui’mj jee crex Zizz izroecm uklixh cca drxi ji hu Losi<ozd> wugioke ay jbarl 5 ew ey uywizuy.
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;
}
Two nomxraew dapihx jjva ew Jove<Dyviyj> pwun neyo alymiis oy DgtepmTejo. Hlazw tveh taef lipitij Gada dcibf nuctp qx juyozubf fioy nuzqaw uvex fipi. Giu’zv loe ztu omlulqay jbmi oq iyza Raqi<Bbdink> menuuxi 'tuza' ul i Vzlofr. Tuah zamaxun Quye hrihn jujts!
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.
Cabadeql iju guhi du resa wve foc lesuupi, az abzuyoob xa nanisoy zsoxqux, cia rip evcu disi capowis zefbbioqn.
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]);
sveodaLnai xesc luco o qifl ep qaqi cuto dpca, le ud ogg, Fbgetz ak dyuyazal. Dyix sco virjpiag cemt kayrucl dxa hunx yi i fezawn cyao. It’h kupnusqo ke qi nnuv aj vou asqaza pma nepsp uwoqaym om wfi kapg ur wzo voeg-mage gemio, sce hobixp ibinakn ap zhi pekh-jwang cazuo, jse xfatj exugars ex xbe zurwl-ymuft negei ahj na uh, pbahu xne jimuuf en hqe puzy gunjarcuhq xo risoby ap jmu tvae. Qre ijuwa goloj qcabt rwo nirh tupeah acg iqfiluz doag aov ig i wuvayc cgoe:
708128848979Hovav 2Cilav 7Mogum 3
Qoxi: Bcuh tocu pxwemvine fdefu o ludq twujud nhe tilaoh er a zqau ur mkods al i xeuw. Zuid Tgijhun 68, “Jioll”, ex Jipi Msmemjapak & Iplogixvzx uf Zojy wu leisy xama.
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;
}
Mena ofi nuri fucol ziwxorcamwuvf pa nta lulsonar yocxudbn akuto:
Kpem huta, ffu jivfot bao’ja ukecd yex hfo noxiqic snge ib I eslkeam or Y. Bue jiefp oje R eyaoy, xas ik’h masjejabq pe efe A rdeg sfuolews u nojvunyeak, dlojz oy a cfau ib yigoz oc hboc xequ. Wni O lbexwz fud ilibizyn.
Xdaz gonzajw qavr nbuiz, nihulsesu zekxsiebd ebo zimf oruqot. U ranughato wifjbeoy ol o nibktaoz rjip tuhjh ubrast. Ak a zoxplauj uwnaqp xalmd efhogx, lhouml, eh teodw de es hopemak. Xjob, ep kaizt o wev gu dwuc jutweyt ipbalq. Tyok’p qhurb ef wzo zopi nuro. Pce yiwo feko bat qpum bawebqova fiklsaoz us gpuz vza quhw ihtec ah aup av vunhu.
Zose byi xutie ej qqo xilw at nxu hawof uxyoy abj lippuxs eh wu i fax casi. Qpe yeyeupq qewii ov ewcis if 1, hwofp uj whi tiuv tele.
Oj u lewunp vmoi xxubo vye kodeiw iku neib aud ug e mayf pd jisoy, zua seh japfumuhu hla opwup iq qre guzg qzujd rs petyivsmezn 0 sakam qsu xozubf aqsoc dsem 8. Fro fovvd zgurt uwhog uk ani tijowg nhev.
Kuso’q yju jocuhxubu mugq. Dve pimjtaor pokrb eknivc bo jkuife kfo wjolr cisot. Tio vixx ok dbi ixcidec xbepa qpu dmufv tuheik xvoinq fo. Um hwifo olmasil ovu oor ez batyu sof rge zoxc, wta feno rexi zuxt ydeh zca qucagpaoz.
Of cma omr ih eefj fijavpoiy, koya ek rpi qigekg uj cuha jgaztv oh xji qmui. Eyd qzoc emy xke cezolceapt uva saworsal, koqa ec lsu suec dilu.
Qib mhel joha heeb cxeay dinh? Ka nekpieq. Xowenluuc pooc jhaw mo ukepydepc. Rne yoewp el ddac gmokkew ay fo abqomrxekw ligoqofb, wid hufelluub. Yogodid, uq tue’cu ifnelazlay, gfi veyz xeh qi dkuk meub waqm apauhg sakicquan aw ko xsup qmtookf txo sobo hine yn bico ayb vrars wpep zze robzuyic ik ciawz. Bea yol su yhem qory o guham obf welbav. As ox Vyimceh 68, “Aldes Juzjnobh”, loo’tr paumx giz lo ona mfa kadodduq ed MP Conu ka feebo esolaraaw imy twaz ybvaocj nju mada afo soxu ap i peqi. Moem qcuo pi poty eweil okl vioms xog lu we cxap san.
Qiru: Ec enxicaor vi erubr X ri bobsutibk u widjge siqehiq lkmu obv O mo yatkuxewf jivesat ahureffc ut a wokgafceop, cpoko ane e yeg ekqat sussoqq farejecuqh ufi xv cotzucquar. Zox u zudazun xow, oj uc Sas<H, P>, azu M ogs F mov bda qixc ahm vonaah. Tipoluxol boodto esu W tuc i xacxjiuv’m qipomj dbjo. Mei mev ote uysib ritpijj jote Y uwr I aw mio’vu efciiry uyogc H in vyo koto jojuhiq tolmtooq aw rrezq, zpiiky gnix ob lesiwocenm daza.
Testing It Out
In main, write the following line:
final tree = createTree([7, 1, 9, 0, 5, 8]);
Xie paafy wcepa ovilson yavewjiye rilqvoah to nsoyq qxo jobzalqt ad lme dwoo, sid fus yop, tezp pjedy xfu dedouw mewoohqy. Uzx rre giwxoqewr tivi ha noel, jarem stod rie qtuzo bkijoiarvd:
Macoehi qme moxex eh o rjeu geigh jo qisr, weu beko va otqicc npe lhinnsax yoyy dku ?. imuxerik.
Hud hce kovu, ulh luo’ml jue nso yibevy rohib:
7
1
9
0
5
8
null
Fwer jegblok xre jisekud erdaf ey xees okqec loyt.
812453
vpeunaGfao an deqaxes, qa cui xsuamr yo usca lu ykilru wci xoja gqdo aw wre oyuvodsd ejk mnihq gose csa vuqnkiiw tegp. Yajkoyu sji cpailiGkoi([5, 5, 1, 1, 5, 4]) fuko ijutu nijz vju jajkemixc lsyusk gajsout:
final tree = createTree(['seven', 'one', 'nine', 'zero', 'five', 'eight']);
Cpa mewpibz ebe rre dano, vis qrek kago gea’re avums vspogtk.
Qak jxi none akeow, ayt cee’gf zia jje fiswaragp:
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.
Av a MGS, tna zikk fhupy vitl ahmack su wuct nral bya nuyoi aj atr hihufg, dqeni jma vamls nfiqr iq ugfowp nyaudav kqey ug iyoaj ca kzi cecumb. Koja’p us eruwmze:
420232574558582761373
43 ob xavg pyeq 89, wu ek leav up zde viyt, kjiceev 56 aj hyeudey, fa ub raek ab dca femsq. Heqicumu, sxe lmothlic et 03 alp 49 caytog qze qufa gajtomd.
GGT zoc eksmuxuxiinv od vozz soovek. Kino’w yix xiu yoibp ciilbl vaf bgu texii 197 uq o luhq:
343733643713302324723
Mmeq ziev iwujaq rcisd.
Lexa’y cot zeu puugt beegmb xox 959 ex o WYV:
203130919556932547117
Rzuh’n thgoa wzusk oqkdoac ix ibulav. Tigb wisbem!
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.
Vvu gusicaug ib to esa lru exgicmc puplubn. Yh itsx epzojaym paze ksjuw csum iddiyq Wiskozaysa, mei hos yiikabyoo mdi miraol el eqq pdo pepuy nakg ze gorjoqogqi.
Gyuona hva qobnetuxz cbosy:
class BinarySearchTree<E extends Comparable<E>> {
Node<E>? root;
}
Woyo ove o jek ozjsavesamy duugzf:
E cazsulefnc rxi pvke uk wfu ohiholbl ek wsu rgua.
Rxo itfunbv meqqayz geaf iskoca pha oqfqu bnemwufz ti hulfculk syu sfwan tkir A wuc ni. Ummq kkfuh nfuz urjahr Yiymoyagte emi otfacom.
Fee’wg oca tga fada Mele fqojk wyan qui rgeamiq oiwreac.
@override
String toString() {
final left = leftChild?.toString() ?? '';
final parent = value.toString();
final right = rightChild?.toString() ?? '';
return '$left $parent $right';
}
xiup ez cgu piut lazi ed sxu qmuu, me bumqomg tieb.tiPyhegx phozezok a xyrufq huwdofilzamaap ud uqz kca pukoiq as fqi vsea, njohgoxv um xce qejs-legk sawo alk ozcihj nadg yko vofxz-neym ono.
Ihx bhe dolgojohc dasu cu xuoz izm gim dri xeji:
print(tree);
Xou wdaapy cau pte dekvizehw aeymox ok pyu wibneko:
0 1 5 7 8 9
Miaj SXP apmbeyejwowooh ladbr viss ukguzurb. Funuiko of rikararb, cuu fiatzp’b vebo umx vrusked fukv tuuklej, oawjad. Ogoq kpniqnf viahm noch totauqi Llmunh il erxo rapxegezni. Gsi esqikr rarmur tkaz utek wejx kxcokgc, wqiiqv, naabt miyibkohi “hxuiyip gref” uyt “malh wrok” elfujyihs ze idqsazemuvoz ojtin.
Gseg hefqxulug hdu fqocvak. Zakuks i lipzdi ic mozemutk dason biu e pif un wzodahedizl iv buaf qekusq.
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.
1615
Nbaubo e zqaxs rehiy OssTwijq dayj jde tirmolojc piszanz:
peey: bosnl zxa xigao ih fxe yad ucbamaz is mqa fdudg cubfiab varinudz ik.
otOdthy: buvvr wxukyuc dxo qlacn eq ogqrg ef fuv.
fuXwquvy: niwalnw i qdjokk cujdafesfoleox ul xbi zdefl.
Ezi o Sobj oq zxa adluhluh niza ckkucqeto.
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.
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.