# Lab #2: Ordered Set Class

### Objective

During this activity, students will be able to:

• Implement a generic ordered set class and its corresponding operations using Python.
IMPORTANT

For this programming assignment, students are required to complete all work by themselves and are not permitted to automatically generate code by using AI-assisted tools such as GitHub Copilot, ChatGPT, Gemini, or any similar platforms. Using AI tools in this way would undermine the learning process and violate academic integrity policies. The purpose of this assignment is to assess your understanding and application of the concepts covered in class. Failure to comply with these guidelines may result in academic penalties, including but not limited to, a lower grade.

If you have any questions about the assignment or need clarification on any concepts, please do not hesitate to visit your instructor during office hours. Rely solely on your own knowledge, the course materials, and any authorized resources provided by the instructor.

## Description

This activity must be developed in the pre-assigned teams of two.

NOTE: The files developed so far in class for this lab are available in the course’s GitHub repository.

Starting from the code in the ordered_set.py file created in class, add the operations described below to the generic OrderedSet[T] class. Remember that an ordered set is a collection of non-repeated elements where the order of insertion is preserved and guaranteed during iteration.

Operation Description
def __init__(     self,     values: Iterable[T] = [] ) -> None Initialize an new instance of this class with the elements contained in values.
def __repr__(self) -> str Called by the repr() built-in function to compute the “official” string representation of this ordered set. When the set is empty, it returns the string "OrderedSet()". When the set has one or more elements, the returned string should contain inside the parenthesis a square bracket delimited list with all its elements separated by commas, for example: "OrderedSet([1, 2, 3])".
def __contains__(     self,     value: T ) -> bool $$x \in A$$
Called by the in operator to determine if value is contained in this ordered set.
def __len__(self) -> int: $$\lvert A \rvert$$
Called by the built-in function len() to determine the number of elements (cardinality) contained in this ordered set.
def add(     self,     value: T ) -> None Add element value to this ordered set if it is not present.
def discard(     self,     value: T ) -> None Remove element value from this ordered set if it is present.
def remove(     self,     value: T ) -> None Remove element value from this ordered set. Raises KeyError if value is not contained in the set.
def __iter__(     self ) -> Iterator[T] Called when an iterator is required for this ordered set. For example, in a for loop, or when calling the iter() built-in function. This method should return a new iterator object that can iterate over all the elements in this ordered set using the iterator protocol.
def __eq__(     self,     other: object ) -> bool $$A = B$$
Called by the == operator to determine if this ordered set is equal to other. Set $$A$$ is equal to set $$B$$ if both sets have exactly the same elements. The order of the elements does not matter.
def __le__(     self,     other: OrderedSet[T] ) -> bool $$A \subseteq B$$
Called by the <= operator to determine if this ordered set is a subset of other. Set $$A$$ is a subset of a set $$B$$ if all elements of $$A$$ are also elements of $$B$$. The order of the elements does not matter.
def __lt__(     self,     other: OrderedSet[T] ) -> bool $$A \subset B$$
Called by the < operator to determine if this ordered set is a proper subset of other. Set $$A$$ is a proper subset of a set $$B$$ if all elements of $$A$$ are also elements of $$B$$, but $$A \ne B$$. The order of the elements does not matter.
def __ge__(     self,     other: OrderedSet[T] ) -> bool $$A \supseteq B$$
Called by the >= operator to determine if this ordered set is a superset of other. Set $$A$$ is a supersubset of a set $$B$$ if all elements of $$B$$ are also elements of $$A$$. The order of the elements does not matter.
def __gt__(     self,     other: OrderedSet[T] ) -> bool $$A \supset B$$
Called by the > operator to determine if this ordered set is a proper super of other. Set $$A$$ is a proper superset of a set $$B$$ if all elements of $$B$$ are also elements of $$A$$, but $$A \ne B$$. The order of the elements does not matter.
def isdisjoint(     self,     other: OrderedSet[T] ) -> bool Determine if this ordered set and other are disjoint sets. Sets are disjoint if and only if their intersection is the empty set.
def __and__(     self,     other: OrderedSet[T] ) -> OrderedSet[T] $$A \cap B$$
Called by the & operator to determine the intersection of this ordered set and other. Returns a new ordered set with the elements that are common to this ordered set and other.
NOTE: The resulting elements should be in the same order as self.
def __or__(     self,     other: OrderedSet[T] ) -> OrderedSet[T] $$A \cup B$$
Called by the | operator to determine the union of this ordered set with other. Returns a new ordered set with all the elements of this ordered set and all the elements of other.
NOTE: The resulting elements should be in the same order as self and then other.
def __sub__(     self,     other: OrderedSet[T] ) -> OrderedSet[T] $$A - B$$
Called by the - operator to determine the difference between this ordered set and other. Returns a new ordered set with all the elements of this ordered set that do not belong to other.
NOTE: The resulting elements should be in the same order as self.
def __xor__(     self,     other: OrderedSet[T] ) -> OrderedSet[T] $$A \ominus B$$
Called by the ^ operator to determine the symmetric difference between this ordered set and other. Returns a new ordered set with all the elements that belong to this ordered set or to other but not to both.
NOTE: The resulting elements should be in the same order as self and then other.
def clear(self) -> None Remove all elements from the this ordered set.
def pop(self) -> T Remove and return the last element added to this ordered set. Raises KeyError if this set is empty.

• Test your code using the tests in the file test_ordered_set.py (19 tests in total). Make sure your code has no failures and no errors.
• Make sure your editor has basic type checking enabled. All your code should use type hints adequately.
• Add a comment at the beginning of each method documenting its time complexity.

## Deliverables

Place in a comment at the top of the ordered_set.py source file the authors’ personal information (student ID and name), for example:

#----------------------------------------------------------
# Lab #2: Ordered Set Class
# Implementation of a generic ordered set class and its
# corresponding operations.
#
# Date: 18-Sep-2024
# Authors:
#           A01770771 James Howlett

To deliver the ordered_set.py file, please provide the following information: