<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: oklch(95% 0 0); border: 1px solid oklch(80% 0 0); } summary { font-weight: bolder; } </style> # Lab 9: Iterators and Regex # Learning Objectives In this lab, you will learn to: - Implement Python's iterator protocol for a new `LinkedList` collection. - Design a new iterator class for a `HashMap` type. - Apply regular expressions to search for patterns in a file. # Setup Use this **[GitHub Classroom link](https://classroom.github.com/a/KDuHyJNQ)** to get the stencil code for this assignment. For instructions on how to clone the Stencil and set up VSCode to use it, see the **[Python Stencil Setup Guide](https://docs.cs200.io/s/python-stencil-setup-guide)**.   **Environment setup**: Make sure your VSCode is set up as per our [setup guide](https://docs.cs200.io/s/vscode-python-setup-guide), and that you can [run the test files from HW0](https://docs.cs200.io/#Testing-your-Python-setup) to make sure your setup is working.  If you have issues during the setup process, see [here](https://docs.cs200.io/s/python-stencil-setup-guide#Troubleshooting). <!-- # Iterators In both Python and Java, we have iterated over lists using a notation that visits each element in the list exactly once, as in: ```java // Java for (DataType item : linklist) { ... } ``` ```python # Python for elt in lst: ... ``` The idea of “visit each item once” isn’t limited to lists. We could imagine doing that over any data structure that has a collection of elements, such as all the nodes in a tree, all the nodes in a graph, or all the keys in a hash table (or dictionary). Because iterating over elements makes sense in a lot of situations, many languages give programmers a way to make foreach-loops work on their own data structures (e.g., graph nodes). There is an analogous technique in Java. --> # Iterators In both Python and Java, we have iterated over lists using a notation that visits each element in the list exactly once, as in: ```java // Java for (DataType item : linklist) { ... } ``` ```python # Python for elt in lst: ... ``` The idea of “visit each item once” isn’t limited to lists. We could imagine doing that over any data structure that has a collection of elements, such as all the nodes in a tree, all the nodes in a graph, or all the keys in a hash table (or dictionary). Because iterating over elements makes sense in a lot of situations, many languages give programmers a way to make foreach-loops work on their own data structures (e.g., graph nodes, etc)--fundamentally, these are called *iterators*. :::info This exercise may seem like it's narrowly about Python, but iterators appear in many languages, including [**Java**](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Iterator.html)! Visiting all of the items in a collection is a fundamental operation that you'll see throughout your CS career! ::: ## Writing a `LinkedList` iterator In this lab, we will imagine that you've created a custom data structure (or *collection*) to represent linked lists in Python. We've done the hard work for you: an implementation of a `LinkedList` is provided in `linked_list.py`. You want to use your custom collection with Python's `for` loops in the same way that you would use a regular `list`: ```python # Standard Python list regular_list = list() regular_list.append("b") regular_list.append("c") regular_list.insert(0, "a") # This prints "a" "b" "c", just like you would expect! for item in regular_list: print(item) ``` ```python # Our linked list (no iterator yet!) custom_list = LinkedList() custom_list.add_last("b") custom_list.add_last("c") custom_list.add_first("a") # This results in a `TypeError`! for item in custom_list: print(item) ``` **What's wrong?** We never told Python how to work with our custom data structure! <section> ### Task 0 Read the following "background" sections to understand what it takes to make an iterator and why it's useful. The next few tasks will guide you through the process--so you don't need to remember every detail yet--but it's important that you get a sense of what we're doing before going forward. </section> ### Background: how to make an iterator in Python [**The Python documentation**](https://docs.python.org/3/library/stdtypes.html#iterator-types) explains what steps are necessary for making your custom collection work in `for` loops: 1. To make a collection iterable, it needs at least two classes: - The *collection class* (in this example `LinkedList`): this is the main class representing the data structure - The *iterator class* (in this example `LinkedListIterator`): this class represents how the iterator will behave 3. The <u>collection class</u> needs a method called `__iter__` (that is, `iter` with **two** underscores on either side) which returns a new instance of your iterator class. Python will automatically call this method before running a `for` loop. 4. The <u>iterator class</u> needs a method called `__next__` that returns the next item of your collection. Python will automatically call this method before every iteration of the for loop. When there are no items remaining, `__next__` should raise the `StopIteration` exception. 5. The <u>iterator class</u> needs a method called `__iter__` that just returns `self`. This is a convenience method for putting an iterator object directly into a `for` loop. Once these methods exist, Python will automatically use them in a standard for-each loop. Using our `LinkedList` example, the idea is we want to be able to write the following code: ```python # Version we write custom_list = LinkedList() for item in custom_list: print(item) ``` Under the hood, Python will use our iterator to implement the loop like this: ```python # What python does "under the hood" custom_list = LinkedList() custom_list_iterator = custom_list.__iter__() # Make an iterator object while True: # Loop until break, or error try: item = custom_list_iterator.__next__() # Call __next__() in a loop except StopIteration: break # there are no more items # the body of the `for` loop goes here! print(item) ``` :::info The key point is that **as programmers, we don't need to write the "under the hood" version, or even care about how the data structure is organized**--as long as the iterator exists, we can just write a nice for-each loop to access all the things in the data structure! Pretty neat, right? :sunglasses: ::: So iterators are useful when we're *using* a data structure--as authors of the data structure (in this case, our `LinkedList` class), we need to do some work up front to figure out *how* the iterator will iterate through all objects in it. **How does this work?** The basic idea is that iterating through a data structure creates an *instance* of the iterator class (`current_list_iterator`) above. The iterator object then needs to keep track of *where it is in the data structure* so it can return the next element each time `__next__()` is called, and then stop when it reaches the end (by raising the `StopIteration` exception). Let's see how to do this using our `LinkedList`. #### Making a `LinkedList` iterator With this idea in mind, here are the most important questions to think about--we'll work through each one step-by-step in the tasks below: - What *state* does the iterator class need to hold? (state is stored in the fields of the iterator class) - What should the iterator's initial state be? (provided to the iterator class's constructor in `__iter__`) - How do we extract the next item from the state? (What should `__next__` return) - How do we decide when there are no more items? (When to raise `StopIteration` in `__next__`?) - How do we update the state to reflect when an item was returned? (How should the object be updated when `__next__` is called?) :::info **Stop and think**: Before trying this on the `LinkedList`, try to work through these steps for an iterator you've already seen before: `range`, which is used in statements like `for i in range(5)`. <details> <summary>Click to reveal</summary> - Needs to keep track of the current number and the max count. - Starts the current number off at 0, and sets the max count to the argument of `range`. - Gets the next item by looking current number. - Stops iteration when the current number is greater than or equal to the max count. - Updates the state by incrementing the current number. </details> ::: Now, let's build `LinkedListIterator` using what we've learned. <section> ### Task 1 Identify the state that `LinkedListIterator` needs to keep track of. What part(s) of `LinkedList` should `LinkedListIterator` be provided? There is more than one possible answer! </section> <section> ### Task 2 Given this state, decide how to get the next item. How do you decide when there are no more items? What should happen to the state after we pick an item to return? </section> <section> ### Task 3 Update `LinkedList.py` to reflect your decisions. You are responsible for `LinkedList.__iter__`, `LinkedListIterator`'s constructor, and `LinkedListIterator.__next__`. <details> <summary>Why do we need a separate <code>LinkedListIterator </code> class?</summary> Imagine we stored the state of the iteration in `LinkedList` instead of `LinkedListIterator`. The issue would become apparent when you tried to construct multiple nested `for` loops. Calling `__next__` on the inner loop would advance the outer iteration, since they point to the same object on the heap. Each `for` loop needs to manage its own iteration state to avoid this kind of aliasing. </details> </section> :::warning **Hint**: Your `LinkedList` is built from a bunch of `Node`s, but a user shouldn't have to think about that! The `for` loop should iterate over the elements of your list (e.g. numbers, strings). ::: :::success **Checkpoint!_:_** Call over a TA to check your work. Ask them any questions you have about how this works. ::: ## Designing a `HashMap` iterator Let’s think back to HW3, where you implemented hashtables. How might you implement a Hashtable iterator? What would that even mean? We’ll do this as a design exercise; **you won’t turn this into code**--as you work on the next steps, just take notes in a notebook or a doc/text file. Recall the internal data structure of a hashtable: we had an array of lists of `KVPair`. Assume that we want a hashtable `for`-loop to iterate over the `KVPair`s. For example (assuming we had implemented the same design in Python): ```python custom_hash_table = HashTable() custom_hash_table.insert("a", 3) custom_hash_table.insert("b", 6) custom_hash_table.insert("c", 1) for pair in custom_hash_table: print(pair.key, '->', pair.value) ``` <section> ### Task 4 Your classmates are having a debate about what the order of pairs would be upon printing the hashtable. - One says the pairs would print in the order (by keys) “a”, “b”, “c” because that’s the order in which they were added. - Another says the order is unpredictable to the programmer. Discuss these two perspectives. Why might the second student claim the order is unpredictable? Which one do you think should be right? Does it matter? </section> <section> ### Task 5 Now think about how you might implement the hashtable. Answer the following two questions: 1. Where in the underlying data structure might we find the first `KVPair`? Think about the array of lists of `KVPairs`. Where could your code easily get a first item? 2. In the `LinkedList` iterator, you kept track of the current node in the list in order to compute `__next__`. What might you keep track of here in order to advance to the next `KVPair` for the loop? </section> :::success **Checkpoint**: Call over a TA to check your work. Ask them any questions you have about how this works. ::: <section> ### Task 6 **If you are in the second hour of the lab, skip this task.** Think about the efficiency of your design for `__next__`. Ideally, an iterator visits each item to be produced exactly once, with constant time needed to advance from one item to the next under the hood. Does your design achieve that? If not, how might your design achieve that? </section> # Regular Expressions Imagine that you were given the text from an email message and asked to find all of the references to Brown course codes (such as `"CSCI0200"`) in the message. How might you do this? If you were searching for a specific course, you could get the text as a list of strings and loop over all of the strings, checking which ones were equal to `"CSCI0200"`. But we’re asking something different: we’re asking you to identify all strings of a specific _shape_ (here, four capital letters followed by four digits). How would you write _that_ program? Tasks like this that involve searching (and perhaps replacing) strings based on their shapes are common in programming. In fact, this is so common that languages provide constructs to describe the shape of strings you want, while the language handles checking each string against the expected shape in an efficient way. **These "shapes", which denote what patterns of text should look like, are called _regexes_ or _regexps_ (short for “regular expressions”, a term that arises from the mathematical foundations of computation).** This part of lab will teach you how to write regular expressions. **You will use regular expressions in the Search assignment.** (And they're a super handy tool to know in for general programming outside this course!) We’re going to start having you work on [a website](https://regex101.com) designed to teach about writing regular expressions. Afterwards, you’ll write a small program to see how to use regexes within a Python program. ### Warmup Exercises <section> ### Task 7 1. Go to [regex101.com](https://regex101.com), which is an awesome site for building and testing regular expressions. 2. Put the following string into the "Test String" box ``` The cat in the hat was late, and that was a great surprise ``` 3. Enter the pattern string `cat` into the "Regular expression" box, like this: ____ 4. At this point, your regex101 window should look like this (see annotations or details)  5. Notice that the _cat_ string is highlighted in the text--**this shows what part of the text matched your regex**! If you don't see `cat`highlighted, make sure your regex101 window looks like the figure above (make sure "Python" and "Match" are checked at the left). If you still have issues, call over a TA for help. </section> <section> ### Task 8 Now let’s start building up patterns in which not all characters are fixed. Let’s say we want look for every 3 letter word in a body of text that contains “at” (e.g. “cat”, “bat”, “sat”, etc). For this, we can use `[a-z]at`. The brackets create a set of characters to search for, and the a-z gives a range of every character between a and z in the ASCII character list. Put this new regex into the site, and see what matches. </section> <section> ### Task 9 Now instead, suppose we want every single word ending in “at”, regardless of length (e.g. “at”, “bat”, “seat”, etc). For this, we can use a _quantifier_--the most common (which you may have seen before, outside of regexes) is `*`. The `*` quantifier says that there can be **any number, including 0, of the character proceeding it** in the string it finds. This means `[a-z]*at` will do what we want: find every String consisting of some number of letters followed by “at”. Put this new regex into the site, and see what matches. </section> <section> ### Task 10 If we want to exclude “at” and only find words with 3 or more letters, we could instead use `[a-z]+at` instead. The `+` quantifier requires there be **one or more** a-z characters. Put this new regex into the site, and see what matches. </section> This regex still has some issues though. For example, if we wanted to use it to find all of the words ending in “at”, we see (by the highlights in the website) that it matches “lat” (as part of “late”). We need some way to specify that the “at” actually be at the end of the word. For this, we can use a “word boundary,” which requires that there be “word characters” (letters, numbers or underscores) on only one side of the boundary. This is represented as `\b` in the regex syntax. <section> ### Task 11 So our new regex, `[a-z]*at\b`, will match “at”, “cat”, “seat”, and “great”, but not “ate”, “late”, “bat9”, or “at\_home”. Put this new regex into the site, and see what matches. </section> If we want to avoid matches like “seat” or “great”, we could add a word boundary to the beginning as well, for a final regex of `\b[a-z]at\b`. ### More challenging examples Now that you’ve seen the basics of character ranges, quantifiers, and boundaries, we can build up to more interesting patterns. The bottom of our course [regex guide](https://docs.google.com/document/d/1mjw88yF1RIsnuM6amVBoZ1sLx9tRFF1T-3rGTcrcJUU/edit?usp=sharing) shows other characters you can use in regexes (to match things like spaces, sets of characters, and more). <section> ### Task 12 Craft regexes to match on the following criteria using [regex101.com](https://regex101.com) (modify your text string as needed to check your work): - All space separated words. - All words that start with a capital letter. - Any capitalization of the word train (i.e., TRAIN, train, tRAIn, TrAiN, etc,) - All words of length 4 (i.e., 4 characters) - All words inside quotes (Hint: think escaped characters!) </section> ### Regexes in Python Now we’re going to use regexes in Python! Python comes with a built in `re` library that performs many of the functions you would want using regexes. You can read all about this library in the [Python documentation](https://docs.python.org/3/library/re.html). The function that will get the most use out of in this class is `findall`, which takes in a regex and a string to look through and returns a list of all the instances from the string that match the given regex. Other methods you may find helpful are `finditer`, `sub`, and `split`. In Python, the syntax you use to specify a regex is `r"<insert regex here>"`. The `r` and the quotation marks are necessary, as they help Python better parse escape characters. In `regex.py` you will find a class called `Registrar`, which handles student emails and the course codes each student email (and thus, each student) is associated with. There are three methods in the class, `view_emails`, `view_courses`, and `make_changes`. Assume the registrar is for Brown University, and thus has Brown-styled emails and course codes. These methods should have the following functionality: - `view_emails` should provide all of the emails found in the document. For this problem, a Brown email address contains any number (at least 1) of names separated by single underscores, followed by a group of zero or more numbers and then “@brown.edu”, where a name is a group of lowercase letters and dashes. - `view_courses` should provide all of the course codes found in the document. Courses consist of 3 to 4 capital letters, followed by 4 numbers, with an optional capital letter at the end! - `make_changes` takes in a regex of a pattern that should be changed and a replacement string of what that pattern should be changed to. This is a general method, and therefore should be able to make changes to either emails or course codes. (Hint: check out the `sub` method!) <section> ### Task 13 Fill out the methods in the `Registrar` class with the specifications above. Get ready to show a TA the results of your regex matching! </section> :::success **Checkpoint:** Congratulations, you’ve completed this week’s lab! Check in with a TA, and then you can go home. Nice job! ::: *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the_ [_anonymous feedback form_](https://docs.google.com/forms/d/1KqjKrDqaHAdjpmeXuQkOkeFKjuurzWHfc3HyJbXVxIs/edit)_._