– Typee Documentation –
4 – Built-in Containers
4.3 – Maps
Maps are specific containers for which content is indexed on keys. Every item is associated with a unique key and can be found back by indexing the container with its key. Maps may contain any type of items as well as items of many types. Meanwhile, keys must be hashable, which is the case for scalar values and which will be the case for any instance of classes that define the operator #. This means that keys may also be of many types.
In some programming languages, maps are named dictionaries. This is the case in Python for instance, with the built-in type dict.
4.3.1 Maps Declaration
The formal EBNF specification of the syntax of maps declaration in Typee is:
<map declaration> ::= <map type> <identifier> [ '=' <map content> ]
<map content> ::= '[' [<map form>] ']'
<map entry> ::= <expression> ':' <expression>
<map form> ::= <map entry> [<map list or comprehension>]
<map list> ::= (',' <map entry>)*
<map list or comprehension> ::= ',' <map entry> <map list> |
<for comprehension>
<map type> ::= 'map' <map contained types>
<for comprehension> ::= 'for' '(' <target list>
'in' <expression> <iter comprehension> ')'
<if comprehension> ::= 'if' '(' (<conditional expression> |
<unnamed func>) ')'
<iter comprehension>
<iter comprehension> ::= [ <for comprehension> | <if comprehension> ]
<map contained types>::= '<' <types list> '>' ( ',' '<' <types list> '>' )
<target> ::= <dotted name> (<subscription or slicing>)*
<targets list> ::= <target> ( ',' <target> <targets list'> )*
<types list> ::= <type> | '(' <type> ( ',' <type> )* ')'
So, there is no need to specify any contained type for a map in Typee. This is the exact equivalent of dict in Python, for instance. Meanwhile, there are two ways to declare contained types in a map.
The first one declares only types for contained values. The syntax is a type or a list of types (i.e. types names separated by commas and embedded in parenthesis) embedded between angle brackets < >.
The second one declares two types or list of types within the angle brackets, sperated by a single comma. In this second case, the first type or list of types (embedded in parenthesis) declares the types allowed for the indexing keys and the second type or list of types declares the types allowed for the contained items. See examples below.
Of course, if a type or a list of types are declared, the map may only contain items of these types.
Examples:
const map<str> progr_languages = [ 'cp': 'C++', 'cs': 'C#', 'j' : 'Java', 'js': 'JavaScript', 'p' : 'Python', 'pe': 'Perl', 'r' : 'Ruby' ]; map empty_map = []; map<(str, int32, float64)> my_map; map comprehension_map = [ i: 11*i for( uint8 i in [0:20] ) ]; const map<uint32, ? in (str, _int_)> typed_map = [ 0: 'item 0', 5: 500 // next line contains two type errors: // 'ten': 10.0 ];
4.3.2 Maps Indexation
There is only one way for indexing a map: key indexing. This is something like subscripting but using the keys of the map as the indexes. As such, there may be one and only one entry per key in a map. As will be seen in a below sub-section, associating a value to an existing key in a map leads to the replacement of previous value associated with this key. The indexing operator in Typee is [ ].
Example:
map mult_11_table = [ i: 11*i for( uint8 i in [0:20] ) ]; for( uint8 i in [0:10] ) print( i, 'x 11 =', mult_11_table[i] ); // prints 0 x 11 = 0 up to 10 x 11 = 110, one value per line
4.3.3 Maps Iterations
Maps are iterable. Iterating through a map is done via statement for. There are three ways to iterate a map: getting at each iteration a pair (key, value); getting at each iteration the sole key; getting at each iteration the sole value.
Meanwhile, maps are not sorted in-place in Typee. This means that the order in which keys, item values or pairs of keys and items values are returned is not guaranteed to be the same every time, as well as it is not guaranteed also among the targeted programming languages and operating systems.
4.3.3.1 Getting pair (key, value)
Statement for iterates two variables on the map.
Example:
const map<str, str> progr_languages = [ 'cp': 'C++', 'cs': 'C#', 'j' : 'Java', 'js': 'JavaScript', 'p' : 'Python', 'pe': 'Perl', 'r' : 'Ruby' ]; for( str key, str value in progr_languages ) print( key, '->', value ); // prints: // cp -> C++ // cs -> C# // ... // r -> Ruby
4.3.3.2 Getting key
Here, statement for iterates only on the ‘keys’ part of the map. The ‘keys’ part of the map is provided by built-in method keys() which is presented in a next sub-section of this documentation.
Example:
for( str key in progr_languages.keys() ) print( key, '->', progr_languages[key] ); // prints: // cp -> C++ // cs -> C# // ... // r -> Ruby
4.3.3.2 Getting value
There, statement for iterates only on the ‘values’ part of the map. The ‘values’ part of the map is provided by built-in method values() which is presented in a next sub-section of this documentation.
Example:
for( str val in progr_languages.values() ) print( val ); // prints: // C++ // C# // ... // Ruby
4.3.4 Maps Manipulations
Typee provides built-in functions and operators for the manipulation of maps. They are of a few kinds and are all presented in next sub-sections.
All of these functions are methods-like. They can be applied to a map as would be built-in methods:
my_map.map_function(...)
4.3.4.1 Map emptying and deleting
map empty()
Empties the map: every item contained in it is deleted and returns a reference to the operated map. This may lead to a call to the destructors of the contained items when they are instancies of classes that define a destructor. Programmers have to take care there because some items may have been previously referenced in code. These references will then reference released resources (i.e. most of the time, memory space) and should not be later accessed in the code.
Example:
map my_map = [ 'a': 'A', 'b': 'B' ]; print( my_map.empty() ); // prints: []
delete
del
Typee instruction delete applied to a map deletes the map and its whole content. This may lead to a call to the destructors of the contained items when they are instancies of classes that define a destructor. Programmers have to take care there because some items may have been previously referenced in code. These references will then reference released resources (i.e. most of the time, memory space) and should not be later accessed in the code.
Keyword del is a wrapper to keyword delete.
Example:
map my_map = [ 'A', 'b': 'B' ]; del my_map ; print( my_map ); // prints: none
4.3.4.2 Maps merging
Merging maps in one map is done in Typee with operator
map operator + ( map left, map right )
The merging of maps is operated by Typee operator +. It creates a new map which is the merging of maps left and right. If items get same key in both maps, the right map content will take precedence and will be put in the resulting merged map.
Example:
map my_map = [ 'a': 'A', 'b': 'B' ]; print( my_map + [ 'c': 'C', 'a': 'AA'] ); // prints: ['a':'AA', 'b':'B', 'c':'C']
map operator += ( map other )
The in-place merging of maps is operated by Typee operator +=. The argument map other is merged with the operated map. If values get same keys in both maps, the content of map other takes precedence. This operator returns a reference to the operated map.
Example:
map my_map = [ 'a': 'A', 'b': 'B' ]; map my_map2 = [ 'c':'C', 'a':'AA' ]; my_map += my_map 2; print( my_map ); // prints: ['a':'AA', 'b':'B', 'c':'C']
4.3.4.3 Items adding, modifying and deleting
Maps are of variable length. Items of any type may be added to them or removed from them. They can be modified in place also.
All these operations are done via the indexing of the map.
Adding an item to a map
The added item may be of any type if no type has been specified at map delcaration or it has to be of a delcared type otherwise. It is added to the operated map if the specified key is not already present in the map.
Example:
map my_map = ['b': 2]; my_map[ 'a' ] = 1; print( my_map ); // prints: ['b': 2, 'a': 1]
Modifying an item in a map
If the key used to index the map already exists, the current item that is associated with this key is replaced with the new item.
Example:
map my_map = ['b': 2]; my_map[ 'a' ] = 1; print( my_map ); // prints: ['b': 2, 'a': 1] my_map[ 'a' ] = 'A'; print( my_map ); // prints: ['b': 2, 'a': 'A']
Deleting an item in a map
Keyword delete, when applied to a map indexed by a key, removes the item associated with this key from within the operated map.
delete
del
Typee statement delete and its wrapper del deletes key-ed entries from map.
If key is not found in map an exception KeyNotFoundException is raised. This may be detected at translation time, in which case Typee translators will set en error. But most of the time, this will not be detectable before run-time. The exception will then be raised at run-time.
Examples:
map my_map = ['b': 2, 'a': 1, 10: 'a string']; del my_map[10]; print( my_map ); // prints: ['b': 2, 'a': 1] del my_map['b']; print( my_map ); // prints: ['a': 1]
map delitem( const ? item )
This function removes all the occurrences of the item from the map. It returns a reference to the map for function calls to be cascadable. If item is not found, an exception NotFoundException is raised. This may be detected at translation time for a very few cases. Typee translators will then set en error. But most of the time, this will not be detectable before run-time. The exception will then be raised at run-time.
Example:
map my_map = ['b': 2, 'a': 1, 10: 'a string']; my_map.delitem( 1 ).delitem( 'a string' ); print( my_map ); // prints: ['b': 2]
4.3.4.4 Items counting
How many items in a map?
const uint64 count()
Returns the number of items contained in a map.
Example:
map my_map = ['b': 2, 'a': 1, 10: 'a string']; print( my_map.count() ); // prints: 3
const uint64 count( const ? value)
Returns the count of value that are present as a value in a map, when associated with different keys.
4.3.4.5 Keys and Items searching
In a map, the default searching is done on keys and is addressed with Typee keywords in and not in. Searching for items by their values or references is not the default and is addressed by functions.
const bool operator in ( const ? item, const map container )
Keyword in checks for the presence of a key into a map. Result is either true if key has been found in the map and false otherwise. It is a good idea to check for keys before indexing a map when no exception management is foreseen in your code.
Examples:
map my_map = ['b': 2, 'a': 1, 10: 'a string']; print( 2 in my_map ); // prints false print( 10 in my_map ); // prints true
const bool operator not in ( const ? item, const map container )
The association of these two keywords is the counterpart of keyword in.
Examples:
map my_map = ['b': 2, 'a': 1, 10: 'a string']; print( 2 not in my_map ); // prints true print( 10 not in my_map ); // prints false
const ? key( const ? item )
Returns the key in the map of the first found occurence of argument item. Returns special value none if item is not found in the map. Typee does not specifies the order of the searching in a map. Results may be different from time to time. See keys() below to get keys values for every occurrences of a same item in a map.
Example:
map my_map = ['b': 2, 'a': 1, 10: 'a string']; print( my_map.key( 2) ); // prints b print( my_map.key(10) ); // prints none
const list keys( const ? item, const uint64 n_max )
Returns a list of keys of n_max occurences of argument item in the map. If none is found, returns an empty list. Typee does not specifies the order of the searching in a map. Results may be different from time to time. Notice that lists are explained in the previous section of this documentation.
Example:
map my_map = ['c': 1, 'b': 2, 'a': 1, 10: 'a string', '2nd': 1]; print( my_map.indexes(1, 2) ); // prints ['c', 'a'] print( my_map.indexes(1, 3) ); // prints ['c', 'a', '2nd'] print( my_map.indexes(125, 1) ); // prints []
const list keys( const ? item )
Returns the list of keys of all occurences of argument item in the the map. If none is found, returns an empty list. Notice that lists are explained in the next section of this documentation.
Example:
map my_map = ['c': 1, 'b': 2, 'a': 1, 10: 'a string', '2nd': 1]; print( my_map.indexes(2) ); // prints ['b'] print( my_map.indexes(1) ); // prints ['c', 'a', '2nd'] print( my_map.indexes(125) ); // prints []
4.3.4.6 Map copying and referencing
Copying a map means creating a new map with same content in heap or stack memory. Any transformation done then on one of the maps will not modify the other one.
Referencing a map is to be understood as creating an alias or defining a pointer to the original map. Any transformation applied then to the map will be reflected through its reference. Any transformation applied also to its reference will be applied in the original map.
Syntax is straightforward. Let’s illustrate it with simple examples:
map my_map = ['c': 1, 'b': 2, 'a': 1, 10: 'a string', '2nd': 1]; map<(uint8,str), (uint8,str)> dst_map; dst_map = src_map ; // map copy dst_map[0] = 10; print( src_map, '\n', dst_map); // prints: // ['c': 1, 'b': 2, 'a': 1, 10: 'a string', '2nd': 1] // ['c': 1, 'b': 2, 'a': 1, 10: 'a string', '2nd': 1, 0: 10] dst_map = &src_map; // map reference dst_map[0] = 100; print( src_map, '\n', dst_map); // prints: // ['c': 1, 'b': 2, 'a': 1, 10: 'a string', '2nd': 1, 0: 10] // ['c': 1, 'b': 2, 'a': 1, 10: 'a string', '2nd': 1, 0: 10]
4.3.4.7 Map sorting
There are two main classes of sorting algorithms: unstable and stable. Stable sorting means that equal items will stay ordered between each others the same way they where before sorting. Such sorts are most of the time a little bit slower than unstable sorts, but they are much appreciated because of this particular main characteristic.
It appears that some other programming languages offer by default a stable sorting function, based on the Timsort algorithm. This is a hybrid algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. (source: Wikipedia). This algorithm had been first introduced in [1] by Peter McIlroy in 1993 and had been implemented by Tim Peters (Timsort…) in 2002 for the Python sort() built-in function. Since then, this algorithm has been enhanced (a bug has been found) and has also been implemented for Java.
[1]: “Optimistic Sorting and Information Theoretic Complexity“, Peter McIlroy, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 467–474, January 1993.
So, it may be that the unstable sorting function built in Typee will finally be translated into a stable version of a sorting algorithm, depending on the targeted programming language. This will enventually be the case when translating Typee code to Python or Java.
Meanwhile, maps are never sorted in place in Typee, on the contrary of arrays or lists for instance. There is no “stable” version of the sort also in current version of Typee maps. Moreover, the only default sort() method sorts maps on their keys. To get a map sorted on its items values, some easy trick is nevertheless available – see examples later shown in this section of the documentation.
It has to be noticed that sorting a map results in an unnamed sorted list of pairs (key, item) that can then be accessed, for instance, in a for loop. We provide examples also about this in this section of the documentation.
list sort()
This is the basic sort function in Typee. Maps are sorted in the ascending order of their keys. Its result is a sorted list containing pairs of (key, item) in the ascending order of their keys. Of course, used keys have to be comparable. In Python for instance, there is no way to compare strings and integers. In Typee, objects and scalar are comparable as soon as they get a hash code. All scalar types in Typee are hashable when they are used as keys in a map, so strings and integers (or floats) for keys will be comparable. If you use instances of classes (i.e. objects), these classes must define at least operator # to be comparable. Hash value will always be used for sorting keys of maps.
If some key is not comparable, a TypeException will be raised at run-time (unless this will be possible to check at translation time, in which case en error will be set by Typee translators).
Example:
map my_map = ['b': 2, 'c': 1, 'a': 1, 10: 'a string']; print( my_map.sort() ); // prints [(10, 'a string'), ('a', 1), ('b', 2), ('c', 1)]
list sort( const int32 comp_func(const ?, const ?) )
list sort( const int32 comp_func< ItemT >(const ItemT, const ItemT) )
This signature of built-in function sort() specifies the comparison function to be used for the sorting operation on the keys of the map. Comparison functions here have to accept two arguments of any type with a constraint: these arguments have to be comparable together. If they are not, either a type error will be set at translation time or (most often) a TypeException will be raised at run-time. Be cautious there. These comparison functions are expected to return a signed integer value:
- less than 0 if first argument is less than second one;
- equal to 0 if both arguments are equal;
- greater than 0 if first argument is greater than second one.
The result of this sort is a list containing pairs of (key, item) in the ascending order of their keys.
list reverse_sort()
This is the counter part of function sort(). It sorts maps in the descending order of their keys. Its result is a sorted list containing pairs of (key, item) in the descending order of their keys. Of course, used keys have to be comparable. In Python for instance, there is no way to compare strings and integers. In Typee, objects and scalar are comparable as soon as they get a hash code. All scalar types in Typee are hashable when they are used as keys in a map, so strings and integers (or floats) for keys will be comparable. If you use instances of classes (i.e. objects), these classes must define at least operator # to be comparable. Hash value will always be used for sorting keys of maps.
If some key is not comparable, a TypeException will be raised at run-time (unless this will be possible to check at translation time, in which case an error will be set by Typee translators).
list reverse_sort( const int32 comp_func(const ?, const ?) )
list reverse_sort( const int32 comp_func< ItemT >(const ItemT, const ItemT) )
This is the counter part of function sort() when passed a comparison function as argument. It sorts maps in the reverse order that the comparison function results in on their keys. Comparison functions here have to accept two arguments of any type with a constraint: these arguments have to be comparable together. If they are not, either a type error will be set at translation time or (most often) a TypeException will be raised at run-time. Be cautious there. These comparison functions are expected to return a signed integer value:
- less than 0 if first argument is less than second one;
- equal to 0 if both arguments are equal;
- greater than 0 if first argument is greater than second one.
The result of this sort is a list containing pairs of (key, item) in the descending order of their keys.
Sorting maps on items
There is no specific way in Typee to sort items of a map. Remember, maps are not sorted in-place. Their sorting only results in sorted lists. The way to get items of a map sorted in Typee is the next one, and is valid for any of the three signatures of function sort():
map my_map = ['c': 1, 'b': 2, 'a': 1, 10: 'a string']; print( my_map.items().sort() ); // prints: [1, 1, 2, 'a string']
The same may be applied with function reverse_sort() and with its two signatures also.
4.3.5 Maps as arguments
Functions and methods signatures are constituted of the types of their arguments and the type of value they return. Maps may be passed as arguments to functions and methods and may be passed back to caller on return. Keyword map is a generic type to specify any kind of map, whatever its size and the maybe declared types for its content.
Next section formerly explains built-in sets.