1# @ohos.util.TreeMap (Nonlinear Container TreeMap)
2
3**TreeMap** stores key-value (KV) pairs. Each key must be unique and have only one value.
4
5**TreeMap** is implemented using a red-black tree, which is a binary search tree where keys are stored in sorted order for efficient insertion and removal.
6
7**[HashMap](js-apis-hashmap.md)** is faster in accessing data than **TreeMap**, because the former accesses data based on the hash code of the key, whereas the latter stores and accesses the keys in sorted order.
8
9Recommended use case: Use **TreeMap** when you need to store KV pairs in sorted order.
10
11This topic uses the following to identify the use of generics:
12
13- K: Key
14
15- V: Value
16
17> **NOTE**
18>
19> The initial APIs of this module are supported since API version 8. Newly added APIs will be marked with a superscript to indicate their earliest API version.
20
21
22## Modules to Import
23
24```ts
25import { TreeMap } from '@kit.ArkTS';
26```
27
28## TreeMap
29
30### Attributes
31
32**Atomic service API**: This API can be used in atomic services since API version 12.
33
34**System capability**: SystemCapability.Utils.Lang
35
36| Name| Type| Readable| Writable| Description|
37| -------- | -------- | -------- | -------- | -------- |
38| length | number | Yes| No| Number of elements in a tree map (called container later).|
39
40
41### constructor
42
43constructor(comparator?:(firstValue: K, secondValue: K) => boolean)
44
45A constructor used to create a **TreeMap** instance. It supports sorting elements in ascending or descending order by using comparators.
46
47**Atomic service API**: This API can be used in atomic services since API version 12.
48
49**System capability**: SystemCapability.Utils.Lang
50
51**Parameters**
52
53| Name| Type| Mandatory| Description|
54| -------- | -------- | -------- | -------- |
55| comparator | function | No| Custom comparator, which can be used to sort elements based on the comparison relationship. The default value is **hole** (a blank placeholder), indicating that no comparator is provided.|
56
57**Error codes**
58
59For details about the error codes, see [Universal Error Codes](../errorcode-universal.md) and [Utils Error Codes](errorcode-utils.md).
60
61| ID| Error Message|
62| -------- | -------- |
63| 401      | Parameter error. Possible causes: 1.Incorrect parameter types; 2.Parameter verification failed. |
64| 10200012 | The TreeMap's constructor cannot be directly invoked. |
65
66**Example**
67
68```ts
69// Default constructor.
70let treeMap : TreeMap<number, number> = new TreeMap();
71```
72
73```ts
74// Use the comparator firstValue < secondValue if the elements are expected to be sorted in ascending order. Use firstValue > secondValue if the elements are expected to be sorted in descending order.
75let treeMap : TreeMap<string,string> = new TreeMap<string,string>((firstValue: string, secondValue: string) : boolean => {return firstValue > secondValue});
76treeMap.set("aa","3");
77treeMap.set("dd","1");
78treeMap.set("cc","2");
79treeMap.set("bb","4");
80let numbers = Array.from(treeMap.keys())
81for (let item of numbers) {
82  console.log("treeMap:" + item);
83}
84```
85
86```ts
87// When a custom type is inserted, a comparator must be provided.
88 class TestEntry{
89   public id: number = 0;
90 }
91 let ts1: TreeMap<TestEntry, string> = new TreeMap<TestEntry, string>((t1: TestEntry, t2: TestEntry): boolean => {return t1.id < t2.id;});
92 let entry1: TestEntry = {
93   id: 0
94 };
95 let entry2: TestEntry = {
96   id: 1
97 }
98 ts1.set(entry1, "0");
99 ts1.set(entry2, "1");
100 console.log("treeMap: ", ts1.length);
101
102```
103
104
105### isEmpty
106
107isEmpty(): boolean
108
109Checks whether this container is empty (contains no element).
110
111**Atomic service API**: This API can be used in atomic services since API version 12.
112
113**System capability**: SystemCapability.Utils.Lang
114
115**Return value**
116
117| Type| Description|
118| -------- | -------- |
119| boolean | Returns **true** if the container is empty; returns **false** otherwise.|
120
121**Error codes**
122
123For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
124
125| ID| Error Message|
126| -------- | -------- |
127| 10200011 | The isEmpty method cannot be bound. |
128
129**Example**
130
131```ts
132let treeMap : TreeMap<number, number> = new TreeMap();
133let result = treeMap.isEmpty();
134```
135
136
137### hasKey
138
139hasKey(key: K): boolean
140
141Checks whether this container has the specified key.
142
143**Atomic service API**: This API can be used in atomic services since API version 12.
144
145**System capability**: SystemCapability.Utils.Lang
146
147**Parameters**
148
149| Name| Type| Mandatory| Description|
150| -------- | -------- | -------- | -------- |
151| key | K | Yes| Target key.|
152
153**Return value**
154
155| Type| Description|
156| -------- | -------- |
157| boolean | Returns **true** if the specified key is contained; returns **false** otherwise.|
158
159**Error codes**
160
161For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
162
163| ID| Error Message|
164| -------- | -------- |
165| 10200011 | The hasKey method cannot be bound. |
166
167**Example**
168
169```ts
170let treeMap : TreeMap<string, number> = new TreeMap();
171treeMap.set("squirrel", 123);
172let result = treeMap.hasKey("squirrel");
173```
174
175
176### hasValue
177
178hasValue(value: V): boolean
179
180Checks whether this container has the specified value.
181
182**Atomic service API**: This API can be used in atomic services since API version 12.
183
184**System capability**: SystemCapability.Utils.Lang
185
186**Parameters**
187
188| Name| Type| Mandatory| Description|
189| -------- | -------- | -------- | -------- |
190| value | V | Yes| Target value.|
191
192**Return value**
193
194| Type| Description|
195| -------- | -------- |
196| boolean | Returns **true** if the specified value is contained; returns **false** otherwise.|
197
198**Error codes**
199
200For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
201
202| ID| Error Message|
203| -------- | -------- |
204| 10200011 | The hasValue method cannot be bound. |
205
206**Example**
207
208```ts
209let treeMap : TreeMap<string, number> = new TreeMap();
210treeMap.set("squirrel", 123);
211let result = treeMap.hasValue(123);
212```
213
214
215### get
216
217get(key: K): V
218
219Obtains the value of the specified key in this container.
220
221**Atomic service API**: This API can be used in atomic services since API version 12.
222
223**System capability**: SystemCapability.Utils.Lang
224
225**Parameters**
226
227| Name| Type| Mandatory| Description|
228| -------- | -------- | -------- | -------- |
229| key | K | Yes| Target key.|
230
231**Return value**
232
233| Type| Description|
234| -------- | -------- |
235| V | Value obtained. If nothing is obtained, **undefined** is returned.|
236
237**Error codes**
238
239For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
240
241| ID| Error Message|
242| -------- | -------- |
243| 10200011 | The get method cannot be bound. |
244
245**Example**
246
247```ts
248let treeMap : TreeMap<string, number> = new TreeMap();
249treeMap.set("squirrel", 123);
250treeMap.set("sparrow", 356);
251let result = treeMap.get("sparrow");
252```
253
254
255### getFirstKey
256
257getFirstKey(): K
258
259Obtains the first key in this container.
260
261**Atomic service API**: This API can be used in atomic services since API version 12.
262
263**System capability**: SystemCapability.Utils.Lang
264
265**Return value**
266
267| Type| Description|
268| -------- | -------- |
269| K | Key obtained. If nothing is obtained, **undefined** is returned.|
270
271**Error codes**
272
273For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
274
275| ID| Error Message|
276| -------- | -------- |
277| 10200011 | The getFirstKey method cannot be bound. |
278
279**Example**
280
281```ts
282let treeMap : TreeMap<string, number> = new TreeMap();
283treeMap.set("squirrel", 123);
284treeMap.set("sparrow", 356);
285let result = treeMap.getFirstKey();
286```
287
288
289### getLastKey
290
291getLastKey(): K
292
293Obtains the last key in this container.
294
295**Atomic service API**: This API can be used in atomic services since API version 12.
296
297**System capability**: SystemCapability.Utils.Lang
298
299**Return value**
300
301| Type| Description|
302| -------- | -------- |
303| K | Key obtained. If nothing is obtained, **undefined** is returned.|
304
305**Error codes**
306
307For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
308
309| ID| Error Message|
310| -------- | -------- |
311| 10200011 | The getLastKey method cannot be bound. |
312
313**Example**
314
315```ts
316let treeMap : TreeMap<string, number> = new TreeMap();
317treeMap.set("squirrel", 123);
318treeMap.set("sparrow", 356);
319let result = treeMap.getLastKey();
320```
321
322
323### setAll
324
325setAll(map: TreeMap<K, V>): void
326
327Adds all elements in a **TreeMap** instance to this container.
328
329**Atomic service API**: This API can be used in atomic services since API version 12.
330
331**System capability**: SystemCapability.Utils.Lang
332
333**Parameters**
334
335| Name| Type| Mandatory| Description|
336| -------- | -------- | -------- | -------- |
337| map | TreeMap<K, V> | Yes| **TreeMap** object to be added to the container.|
338
339**Error codes**
340
341For details about the error codes, see [Universal Error Codes](../errorcode-universal.md) and [Utils Error Codes](errorcode-utils.md).
342
343| ID| Error Message|
344| -------- | -------- |
345| 401      | Parameter error. Possible causes: 1. Mandatory parameters are left unspecified; 2. Incorrect parameter types. |
346| 10200011 | The setAll method cannot be bound. |
347
348**Example**
349
350```ts
351let treeMap : TreeMap<string, number> = new TreeMap();
352treeMap.set("squirrel", 123);
353treeMap.set("sparrow", 356);
354let map : TreeMap<string, number> = new TreeMap();
355map.set("demo", 12);
356map.setAll(treeMap); // Add all elements in the treeMap to the map.
357map.forEach((value ?: number, key ?: string) : void => {
358  console.log("value" + value, "key" + key); // Print result: 12 demo, 356 sparrow, and 123 squirrel
359})
360```
361
362
363### set
364
365set(key: K, value: V): Object
366
367Adds or updates an element in this container.
368
369**Atomic service API**: This API can be used in atomic services since API version 12.
370
371**System capability**: SystemCapability.Utils.Lang
372
373**Parameters**
374
375| Name| Type| Mandatory| Description|
376| -------- | -------- | -------- | -------- |
377| key | K | Yes| Key of the target element.|
378| value | V | Yes| Value of the target element.|
379
380**Return value**
381
382| Type| Description|
383| -------- | -------- |
384| Object | Container that contains the new element.|
385
386**Error codes**
387
388For details about the error codes, see [Universal Error Codes](../errorcode-universal.md) and [Utils Error Codes](errorcode-utils.md).
389
390| ID| Error Message|
391| -------- | -------- |
392| 401      | Parameter error. Possible causes: 1. Mandatory parameters are left unspecified; 2. Incorrect parameter types; 3. Parameter verification failed. |
393| 10200011 | The set method cannot be bound. |
394
395**Example**
396
397```ts
398let treeMap : TreeMap<string, number> = new TreeMap();
399treeMap.set("squirrel", 123);
400```
401
402
403### remove
404
405remove(key: K): V
406
407Removes the element with the specified key from this container.
408
409**Atomic service API**: This API can be used in atomic services since API version 12.
410
411**System capability**: SystemCapability.Utils.Lang
412
413**Parameters**
414
415| Name| Type| Mandatory| Description|
416| -------- | -------- | -------- | -------- |
417| key | K | Yes| Target key.|
418
419**Return value**
420
421| Type| Description|
422| -------- | -------- |
423| V | Value of the element removed.|
424
425**Error codes**
426
427For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
428
429| ID| Error Message|
430| -------- | -------- |
431| 10200011 | The remove method cannot be bound. |
432
433**Example**
434
435```ts
436let treeMap : TreeMap<string, number> = new TreeMap();
437treeMap.set("squirrel", 123);
438treeMap.set("sparrow", 356);
439let result = treeMap.remove("sparrow");
440```
441
442
443### getLowerKey
444
445getLowerKey(key: K): K
446
447Obtains the key that is equal to placed in front of the input key in this container.
448
449**Atomic service API**: This API can be used in atomic services since API version 12.
450
451**System capability**: SystemCapability.Utils.Lang
452
453**Parameters**
454
455| Name| Type| Mandatory| Description|
456| -------- | -------- | -------- | -------- |
457| key | K | Yes| Input key.|
458
459**Return value**
460
461| Type| Description|
462| -------- | -------- |
463| K | Key obtained. If nothing is obtained, **undefined** is returned.|
464
465**Error codes**
466
467For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
468
469| ID| Error Message|
470| -------- | -------- |
471| 10200011 | The getLowerKey method cannot be bound. |
472
473**Example**
474
475```ts
476let treeMap : TreeMap<string, number> = new TreeMap();
477treeMap.set("squirrel", 123);
478treeMap.set("sparrow", 356);
479treeMap.set("gander", 356);
480let result = treeMap.getLowerKey("sparrow");
481```
482
483
484### getHigherKey
485
486getHigherKey(key: K): K
487
488Obtains the key that is equal to or placed next to the input key in this container.
489
490**Atomic service API**: This API can be used in atomic services since API version 12.
491
492**System capability**: SystemCapability.Utils.Lang
493
494**Parameters**
495
496| Name| Type| Mandatory| Description|
497| -------- | -------- | -------- | -------- |
498| key | K | Yes| Input key.|
499
500**Return value**
501
502| Type| Description|
503| -------- | -------- |
504| K | Key obtained. If nothing is obtained, **undefined** is returned.|
505
506**Error codes**
507
508For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
509
510| ID| Error Message|
511| -------- | -------- |
512| 10200011 | The getHigherKey method cannot be bound. |
513
514**Example**
515
516```ts
517let treeMap : TreeMap<string, number> = new TreeMap();
518treeMap.set("squirrel", 123);
519treeMap.set("sparrow", 356);
520treeMap.set("gander", 356);
521let result = treeMap.getHigherKey("sparrow");
522```
523
524### replace
525
526replace(key: K, newValue: V): boolean
527
528Replaces an element in this container.
529
530**Atomic service API**: This API can be used in atomic services since API version 12.
531
532**System capability**: SystemCapability.Utils.Lang
533
534**Parameters**
535
536| Name| Type| Mandatory| Description|
537| -------- | -------- | -------- | -------- |
538| key | K | Yes| Key of the target element.|
539| newValue | V | Yes| New value of the element.|
540
541**Return value**
542
543| Type| Description|
544| -------- | -------- |
545| boolean | Returns **true** if the element is replaced successfully; returns **false** otherwise.|
546
547**Error codes**
548
549For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
550
551| ID| Error Message|
552| -------- | -------- |
553| 10200011 | The replace method cannot be bound. |
554
555**Example**
556
557```ts
558let treeMap : TreeMap<string, number> = new TreeMap();
559treeMap.set("sparrow", 123);
560let result = treeMap.replace("sparrow", 357);
561```
562
563
564### clear
565
566clear(): void
567
568Clears this container and sets its length to **0**.
569
570**Atomic service API**: This API can be used in atomic services since API version 12.
571
572**System capability**: SystemCapability.Utils.Lang
573
574**Error codes**
575
576For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
577
578| ID| Error Message|
579| -------- | -------- |
580| 10200011 | The clear method cannot be bound. |
581
582**Example**
583
584```ts
585let treeMap : TreeMap<string, number> = new TreeMap();
586treeMap.set("squirrel", 123);
587treeMap.set("sparrow", 356);
588treeMap.clear();
589```
590
591
592### keys
593
594keys(): IterableIterator&lt;K&gt;
595
596Obtains an iterator that contains all the keys in this container.
597
598**Atomic service API**: This API can be used in atomic services since API version 12.
599
600**System capability**: SystemCapability.Utils.Lang
601
602**Return value**
603
604| Type| Description|
605| -------- | -------- |
606| IterableIterator&lt;K&gt; | Iterator obtained.|
607
608**Error codes**
609
610For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
611
612| ID| Error Message|
613| -------- | -------- |
614| 10200011 | The keys method cannot be bound. |
615
616**Example**
617
618```ts
619let treeMap : TreeMap<string, number> = new TreeMap();
620treeMap.set("squirrel", 123);
621treeMap.set("sparrow", 356);
622let it = treeMap.keys();
623let t: IteratorResult<string> = it.next();
624while(!t.done) {
625  console.log("TreeMap " + t.value);
626  t = it.next()
627}
628```
629
630
631### values
632
633values(): IterableIterator&lt;V&gt;
634
635Obtains an iterator that contains all the values in this container.
636
637**Atomic service API**: This API can be used in atomic services since API version 12.
638
639**System capability**: SystemCapability.Utils.Lang
640
641**Return value**
642
643| Type| Description|
644| -------- | -------- |
645| IterableIterator&lt;V&gt; | Iterator obtained.|
646
647**Error codes**
648
649For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
650
651| ID| Error Message|
652| -------- | -------- |
653| 10200011 | The values method cannot be bound. |
654
655**Example**
656
657```ts
658let treeMap : TreeMap<string, number> = new TreeMap();
659treeMap.set("squirrel", 123);
660treeMap.set("sparrow", 356);
661let it = treeMap.values();
662let t: IteratorResult<number> = it.next();
663while(!t.done) {
664  console.log("TreeMap" + t.value);
665  t = it.next()
666}
667```
668
669
670### forEach
671
672forEach(callbackFn: (value?: V, key?: K, map?: TreeMap<K, V>) => void, thisArg?: Object): void
673
674Uses a callback to traverse the elements in this container and obtain their position indexes.
675
676**Atomic service API**: This API can be used in atomic services since API version 12.
677
678**System capability**: SystemCapability.Utils.Lang
679
680**Parameters**
681
682| Name| Type| Mandatory| Description|
683| -------- | -------- | -------- | -------- |
684| callbackFn | function | Yes| Callback invoked to traverse the elements in the container.|
685| thisArg | Object | No| Value of **this** to use when **callbackFn** is invoked. The default value is this instance.|
686
687callbackFn
688| Name| Type| Mandatory| Description|
689| -------- | -------- | -------- | -------- |
690| value | V | No| Value of the element that is currently traversed. The default value is the value of the first key-value pair.|
691| key | K | No| Key of the element that is currently traversed. The default value is the key of the first key-value pair.|
692| map | TreeMap<K, V> | No| Instance that calls the **forEach** API. The default value is this instance.|
693
694**Error codes**
695
696For details about the error codes, see [Universal Error Codes](../errorcode-universal.md) and [Utils Error Codes](errorcode-utils.md).
697
698| ID| Error Message|
699| -------- | -------- |
700| 401      | Parameter error. Possible causes: 1. Mandatory parameters are left unspecified; 2. Incorrect parameter types. |
701| 10200011 | The forEach method cannot be bound. |
702
703**Example**
704
705```ts
706let treeMap : TreeMap<string, number> = new TreeMap();
707treeMap.set("sparrow", 123);
708treeMap.set("gull", 357);
709treeMap.forEach((value ?: number, key ?: string) : void => {
710  console.log("value:" + value, "key:" + key);
711});
712```
713```ts
714 // You are not advised to use the set or remove APIs in forEach because they may cause unpredictable risks such as infinite loops. You can use the for loop when inserting or deleting data.
715 let treeMap : TreeMap<string, number> = new TreeMap();
716 for(let i = 0; i < 10; i++) {
717   treeMap.set("sparrow" + i, 123);
718 }
719 for(let i = 0;i < 10; i++) {
720   treeMap.remove("sparrow" + i);
721 }
722```
723
724### entries
725
726entries(): IterableIterator<[K, V]>
727
728Obtains an iterator that contains all the elements in this container.
729
730**Atomic service API**: This API can be used in atomic services since API version 12.
731
732**System capability**: SystemCapability.Utils.Lang
733
734**Return value**
735
736| Type| Description|
737| -------- | -------- |
738| IterableIterator<[K, V]> | Iterator obtained.|
739
740**Error codes**
741
742For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
743
744| ID| Error Message|
745| -------- | -------- |
746| 10200011 | The entries method cannot be bound. |
747
748**Example**
749
750```ts
751let treeMap : TreeMap<string, number> = new TreeMap();
752treeMap.set("squirrel", 123);
753treeMap.set("sparrow", 356);
754let it = treeMap.entries();
755let t: IteratorResult<Object[]> = it.next();
756while(!t.done) {
757  console.log("TreeMap" + t.value);
758  t = it.next()
759}
760```
761```ts
762 // You are not advised to use the set or remove APIs in entries because they may cause unpredictable risks such as infinite loops. You can use the for loop when inserting or deleting data.
763 let treeMap : TreeMap<string, number> = new TreeMap();
764 for(let i = 0; i < 10; i++) {
765   treeMap.set("sparrow" + i, 123);
766 }
767 for(let i = 0;i < 10; i++) {
768   treeMap.remove("sparrow" + i);
769 }
770```
771
772### [Symbol.iterator]
773
774[Symbol.iterator]\(): IterableIterator&lt;[K, V]&gt;
775
776Obtains an iterator, each item of which is a JavaScript object.
777
778**Atomic service API**: This API can be used in atomic services since API version 12.
779
780**System capability**: SystemCapability.Utils.Lang
781
782**Return value**
783| Type| Description|
784| -------- | -------- |
785| IterableIterator<[K, V]> | Iterator obtained.|
786
787**Error codes**
788
789For details about the error codes, see [Utils Error Codes](errorcode-utils.md).
790
791| ID| Error Message|
792| -------- | -------- |
793| 10200011 | The Symbol.iterator method cannot be bound. |
794
795**Example**
796
797```ts
798let treeMap : TreeMap<string, number> = new TreeMap();
799treeMap.set("squirrel", 123);
800treeMap.set("sparrow", 356);
801
802// Method 1:
803let it = treeMap.entries();
804let t: IteratorResult<Object[]> = it.next();
805while(!t.done) {
806  console.log("TreeMap" + t.value);
807  t = it.next()
808}
809
810// Method 2:
811 let iter = treeMap[Symbol.iterator]();
812 let temp: IteratorResult<Object[]> = iter.next();
813 while(!temp.done) {
814   console.log("key:" + temp.value[0]);
815   console.log("value:" + temp.value[1]);
816   temp = iter.next();
817 }
818```
819```ts
820 // You are not advised to use the set or remove APIs in Symbol.iterator because they may cause unpredictable risks such as infinite loops. You can use the for loop when inserting or deleting data.
821 let treeMap : TreeMap<string, number> = new TreeMap();
822 for(let i = 0; i < 10; i++) {
823   treeMap.set("sparrow" + i, 123);
824 }
825 for(let i = 0;i < 10; i++) {
826   treeMap.remove("sparrow" + i);
827 }
828```
829