Data Structures

Data structures are basically just that -- they are structures which can hold some data together. In other words, they are used to store a collection of related data.

There are four built-in data structures in Auto -- List, Tuple, HashMap and HashSet. We will see how to use each of them and how they make life easier for us.

List

A List is a data structure that holds an ordered collection of items i.e. you can store a sequence of items in a list. This is easy to imagine if you can think of a shopping list where you have a list of items to buy, except that you probably have each item on a separate line in your shopping list whereas in Auto you put commas in between them.

The list of items should be enclosed in square brackets so that Auto understands that you are specifying a list. Once you have created a list, you can add, remove or search for items in the list. Since we can add and remove items, we say that a list is a mutable data type i.e. this type can be altered.

Quick Introduction To Objects And Methods

Although we've been generally delaying the discussion of objects and classes till now, a little explanation is needed right now so that you can understand lists better. We will explore this topic in detail in a later chapter.

A list is an example of usage of objects and methods. When we use a variable i and assign a value to it, say integer 5 to it, you can think of it as creating an object (i.e. instance) i of class (i.e. type) int.

A class can also have methods i.e. functions defined for use with respect to that class only. You can use these pieces of functionality only when you have an object of that class. For example, Auto provides an append method for the List type which allows you to add an item to the end of the list. For example, mylist.append('an item') will add that string to the list mylist. Note the use of dotted notation for accessing methods of the objects.

Methods are accessed using the dotted notation, for example, mylist.append('an item').

Using lists

How It Works

The variable shoplist is a shopping list for someone who is going to the market. In shoplist, we only store strings of the names of the items to buy but you can add any kind of object to a list including numbers and even other lists.

We have also used the for..in loop to iterate through the items of the list. By now, you must have realised that a list is also a sequence. The speciality of sequences will be discussed in a later section.

Notice the use of the end parameter in the call to print function to indicate that we want to end the output with a space instead of the usual line break.

Next, we add an item to the list using the append method of the list object, as already discussed before. Then, we check that the item has been indeed added to the list by printing the contents of the list by simply passing the list to the print function which prints it neatly.

Then, we sort the list by using the sort method of the list. It is important to understand that this method affects the list itself and does not return a modified list -- this is different from the way strings work. This is what we mean by saying that lists are mutable and that strings are immutable.

Next, when we finish buying an item in the market, we want to remove it from the list. We achieve this by using the remove method. Here, we mention which item of the list we want to remove by specifying its index. We specify that we want to remove the first item from the list and hence we use shoplist.remove(0) (remember that Auto starts counting from 0).

Note for Python Programmers:

In Auto, you use shoplist.remove(0) to remove an item by index, whereas Python uses del shoplist[0]. The a2p transpiler converts list.remove(index) to del list[index] in the generated Python code. Also, Auto uses list.len() as a method call, while Python uses len(list) as a built-in function.

Tuple

Tuples are used to hold together multiple objects. Think of them as similar to lists, but without the extensive functionality that the list type gives you. One major feature of tuples is that they are immutable like strings i.e. you cannot modify tuples.

Tuples are defined by specifying items separated by commas within a pair of parentheses.

Tuples are usually used in cases where a statement or a user-defined function can safely assume that the collection of values (i.e. the tuple of values used) will not change.

Using tuples

How It Works

The variable zoo refers to a tuple of items. We see that the len function can be used to get the length of the tuple. This also indicates that a tuple is a sequence as well.

We are now shifting these animals to a new zoo since the old zoo is being closed. Therefore, the new_zoo tuple contains some animals which are already there along with the animals brought over from the old zoo. Back to reality, note that a tuple within a tuple does not lose its identity.

We can access the items in the tuple by specifying the item's position within a pair of square brackets just like we did for lists. This is called the indexing operator. We access the third item in new_zoo by specifying new_zoo[2] and we access the third item within the third item in the new_zoo tuple by specifying new_zoo[2][2]. This is pretty simple once you've understood the idiom.

Tuple with 0 or 1 items

An empty tuple is constructed by an empty pair of parentheses such as myempty = (). However, a tuple with a single item is not so simple. You have to specify it using a comma following the first (and only) item so that Auto can differentiate between a tuple and a pair of parentheses surrounding the object in an expression i.e. you have to specify singleton = (2 , ) if you mean you want a tuple containing the item 2.

Note for Python Programmers:

Auto uses Tuple as the type name and (T1, T2, ...) for tuple type annotations, while Python uses tuple. The a2p transpiler handles this conversion. A list within a list does not lose its identity i.e. lists are not flattened. The same applies to a tuple within a tuple, or a tuple within a list, or a list within a tuple, etc.

Dictionary (HashMap)

A HashMap is like an address-book where you can find the address or contact details of a person by knowing only his/her name i.e. we associate keys (name) with values (details). Note that the key must be unique just like you cannot find out the correct information if you have two persons with the exact same name.

Note that you can use only immutable objects (like strings) for the keys of a HashMap but you can use either immutable or mutable objects for the values of the HashMap. This basically translates to say that you should use only simple objects for keys.

Pairs of keys and values are specified in a HashMap by using the notation d = {key1 : value1, key2 : value2 }. Notice that the key-value pairs are separated by a colon and the pairs are separated themselves by commas and all this is enclosed in a pair of curly braces.

Remember that key-value pairs in a HashMap are not ordered in any manner. If you want a particular order, then you will have to sort them yourself before using it.

Using dictionaries (HashMap)

How It Works

We create the dictionary ab using the notation already discussed. We then access key-value pairs by specifying the key using the indexing operator as discussed in the context of lists and tuples. Observe the simple syntax.

We can delete key-value pairs using the remove method of the HashMap. We simply specify the HashMap and the key to be removed. There is no need to know the value corresponding to the key for this operation.

Next, we access each key-value pair of the HashMap using the keys method which returns a collection of all keys. We retrieve each key using the for..in loop and then access the corresponding value using the indexing operator.

We can add new key-value pairs by simply using the indexing operator to access a key and assign that value, as we have done for Guido in the above case.

We can check if a key exists using the contains_key method.

Note for Python Programmers:

Auto uses HashMap<K, V> as the type name where Python uses dict. Auto uses map.contains_key("key") to check for key existence, while Python uses "key" in map. The a2p transpiler converts HashMap to dict and contains_key to the in operator automatically. Similarly, Auto uses map.remove("key") where Python uses del map["key"].

Sequences

Lists, tuples and strings are examples of sequences, but what are sequences and what is so special about them?

The major features are membership tests, (i.e. the contains method) and indexing operations, which allow us to fetch a particular item in the sequence directly.

The three types of sequences mentioned above -- lists, tuples and strings, also have a slicing operation which allows us to retrieve a slice of the sequence i.e. a part of the sequence.

Sequences (indexing and slicing)

How It Works

First, we see how to use indexes to get individual items of a sequence. This is also referred to as the subscription operation. Whenever you specify a number to a sequence within square brackets as shown above, Auto will fetch you the item corresponding to that position in the sequence. Remember that Auto starts counting numbers from 0. Hence, shoplist[0] fetches the first item and shoplist[3] fetches the fourth item in the shoplist sequence.

The index can also be a negative number, in which case, the position is calculated from the end of the sequence. Therefore, shoplist[-1] refers to the last item in the sequence and shoplist[-2] fetches the second last item in the sequence.

The slicing operation is used by specifying the name of the sequence followed by an optional pair of numbers separated by a colon within square brackets. Note that this is very similar to the indexing operation you have been using till now. Remember the numbers are optional but the colon isn't.

The first number (before the colon) in the slicing operation refers to the position from where the slice starts and the second number (after the colon) indicates where the slice will stop at. If the first number is not specified, Auto will start at the beginning of the sequence. If the second number is left out, Auto will stop at the end of the sequence. Note that the slice returned starts at the start position and will end just before the end position i.e. the start position is included but the end position is excluded from the sequence slice.

Thus, shoplist[1:3] returns a slice of the sequence starting at position 1, includes position 2 but stops at position 3 and therefore a slice of two items is returned. Similarly, shoplist[:] returns a copy of the whole sequence.

You can also do slicing with negative positions. Negative numbers are used for positions from the end of the sequence. For example, shoplist[:-1] will return a slice of the sequence which excludes the last item of the sequence but contains everything else.

You can also provide a third argument for the slice, which is the step for the slicing (by default, the step size is 1):

>>> shoplist = ['apple', 'mango', 'carrot', 'banana']
>>> shoplist[::1]
['apple', 'mango', 'carrot', 'banana']
>>> shoplist[::2]
['apple', 'carrot']
>>> shoplist[::3]
['apple', 'banana']
>>> shoplist[::-1]
['banana', 'carrot', 'mango', 'apple']

Notice that when the step is 2, we get the items with position 0, 2,... When the step size is 3, we get the items with position 0, 3, etc.

The great thing about sequences is that you can access tuples, lists and strings all in the same way!

Note for Python Programmers:

Auto's slicing syntax is the same as Python's: seq[start:stop:step]. The a2p transpiler passes slicing operations through unchanged since both languages share the same syntax. Negative indexing and slicing also work identically in both languages.

Set (HashSet)

Sets are unordered collections of simple objects. These are used when the existence of an object in a collection is more important than the order or how many times it occurs.

Using sets, you can test for membership, whether it is a subset of another set, find the intersection between two sets, and so on.

Using sets (HashSet)

How It Works

If you remember basic set theory mathematics from school, then this example is fairly self-explanatory. But if not, you can google "set theory" and "Venn diagram" to better understand our use of sets.

Note for Python Programmers:

Auto uses HashSet<T> as the type name where Python uses set. Auto uses set.contains("item") to check membership, while Python uses "item" in set. The a2p transpiler converts HashSet to set and contains to the in operator. The set literal syntax {...} is the same in both languages.

References

When you create an object and assign it to a variable, the variable only refers to the object and does not represent the object itself! That is, the variable name points to that part of your computer's memory where the object is stored. This is called binding the name to the object.

Generally, you don't need to be worried about this, but there is a subtle effect due to references which you need to be aware of:

References

How It Works

Remember that if you want to make a copy of a list or such kinds of sequences or complex objects (not simple objects such as integers), then you have to use the slicing operation to make a copy. If you just assign the variable name to another name, both of them will ''refer'' to the same object and this could be trouble if you are not careful.

The output shows that modifying the copy (mylist_copy) does not affect the original list (mylist). This is because we used mylist[:] to create a proper copy, not just a reference.

Note for Python Programmers:

The reference behavior is the same in both Auto and Python. Remember that an assignment statement for lists does not create a copy. You have to use the slicing operation (mylist[:]) to make a copy of the sequence. This works identically in both languages.

More About Strings

We have already discussed strings in detail earlier. What more can there be to know? Well, did you know that strings are also objects and have methods which do everything from checking part of a string to stripping spaces?

The strings that you use in programs are all of the type str. Some useful methods of this type are demonstrated in the next example.

String methods

How It Works

Here, we see a lot of the string methods in action. The startswith method is used to find out whether the string starts with the given string. The contains method is used to check if a given string is a part of the string.

The str type also has a neat method to join the items of a sequence with the string acting as a delimiter between each item of the sequence and returns a bigger string generated from this.

Note for Python Programmers:

Most string methods work the same in both languages. The key difference is that Auto uses str.contains("substr") where Python uses "substr" in str. The a2p transpiler converts contains to the in operator. Methods like startswith, replace, join, and split are identical in both languages.

Summary

We have explored the various built-in data structures of Auto in detail. These data structures will be essential for writing programs of reasonable size. Here are the key takeaways:

• List ([T]) -- mutable ordered collection. Use list.append(), list.remove(), list.sort(), and list.len().
• Tuple ((T1, T2, ...)) -- immutable ordered collection. Cannot be modified after creation.
• HashMap<K, V> ({k: v, ...}) -- key-value pairs. Use map.contains_key(), map.keys(), and map.remove().
• HashSet<T> ({v1, v2, ...}) -- unique values. Use set.contains(), set.add(), set.remove(), and set.intersection().
• Sequences -- lists, tuples, and strings all support indexing (seq[0]), slicing (seq[1:3]), and negative indexing (seq[-1]).
• References -- use seq[:] to make a copy of a sequence instead of just creating another reference.
• String methods -- startswith, contains, replace, join, split and many more.

Now that we have a lot of the basics of Auto in place, we will next see how to design and write a real-world program.