Considering this Python question:

In general, a compact list of integers represents a set of integers as a list x0, x1, x2, . . . of integers such that x0 < x1 < x2 < . . . , with the meaning that all integers from x0 to x1 1, as well as all from x2 to x3 1, and so on, are included in the set. Thus, the included integers start at x0, then the first integer larger than x0 not to be included is x1, then the next integer after x1 to be included is x2 and so on. The empty set is represented as an empty list (of length 0). If the compact list has an odd length, it contains all values from the last entry in the list up to the maximum value MAX. As a final example, the set of all integers is represented by the one-element compact list MIN: that is, it consists of the single number MIN. You have to implement a class called CompactList which implements various set operations, as described below. Before we describe the various functionalities, we quickly review the basic set operations and relations, to establish notation. Given sets A and B, their union is the set A B defined as the set of all elements that are in A or in B or in both A and B, their intersection is the set A B defined as the set of all elements that are in A and in B, their difference is the set A \ B defined as the set of all elements that are in A but not in B. The set A is a subset of set B, written A B, if each element of A is also an element of B. The sets A and B are considered to be equal if they have the same elements. If all the sets that we consider are contained in some universal set U, then the complement of set A is the set Ac = U \ A. Below, whenever we mention union, intersection, difference or complement, we always refer to the sets represented by compact lists of integers. For example, the union of the set A = {10, . . . , 19} represented by the compact list 10, 20, and the set B = {30, . . . , 39} represented by the compact list 30, 40, is the set A B represented by the compact list 10, 20, 30, 40. As another example, the intersection of the set A with the set C = {15, . . . , 24}, represented by the compact list 15, 25, is the set A C = {15, 16, 17, 18, 19} represented by the compact list 15, 20. For the purposes of our set operations, the universal set is the set {MIN,MIN+1,. . . ,MAX} of integers, and so we take complements with respect to this set. For example, the complement of set A is the set {MIN, . . . , 9} {20, . . . }, represented by the compact list MIN, 10, 20. The following list (a )(m ) describes the functionalities that you have to implement. You can use the template file CompactList.py on Moodle. (a ) Constructor for a compact list from a Python list: __init__(alist) Creates a compact list to represent the set of integers given by the Python list alist. As an example, CompactList([8,3,5,4]) initialises the compact list 3, 6, 8, 9. (b ) Instance method: cardinality() Returns the number of elements in the set represented by this compact list. The worst-case time should be O(n) where n is the length of the compact list. (c ) Instance method: insert(value) Inserts value into the set represented by this compact list if value is not already contained in the set. The worst-case time should be O(n) where n is the length of the compact list. (d ) Instance method: delete(value) Removes value from the set represented by this compact list if value is in the set, otherwise does nothing. The worst-case time should be O(n) where n is the length of the compact list. (e ) Instance method: contains(value) Returns True if value is an element of the set represented by this compact list, otherwise returns False. The worst-case time should be O(log n), where n is the length of this compact list. 2 (f) Instance method: subsetOf(cl) Returns True if the set represented by this compact list is a subset of the set represented by cl, otherwise returns False. The worst-case time should be O(m + n) where m is the length of this compact list and n is the length of cl. (g ) Instance method: equals(cl) Returns True if the set represented by this compact list has the same elements as the set represented by cl, otherwise False. The worst-case time should be O(m + n) where m is the length of this compact list and n is the length of cl. (h ) Instance method: isEmpty() Returns True if the compact list represents the empty set, False if not. The worst-case running time should be O(1). (i) Instance method: complement() Returns the complement of the set represented by this compact list, also represented as a compact list, where the complement is with respect to the universal set of integers determined by MIN and MAX. The worst-case time should be O(n) where n is the length of the compact list. (j) Instance method: union(cl) Returns the union of the set represented by this compact list with the set represented by the compact list cl. The method does not alter the current compact list or cl. The worst-case time should be O(m + n) where m is the length of this compact list and n is the length of cl. (k ) Instance method: intersection(cl) Returns the intersection of the set represented by this compact list with the set represented by the compact list cl. The method does not alter the current compact list or cl. The worst-case time should be O(m + n) where m is the length of this compact list and n is the length of cl. (l) Instance method: difference(cl) Returns the set difference this\cl of the set represented by this compact list with the set represented by cl removed. The method does not alter the current compact list or cl. The worst-case time should be O(m + n) where m is the length of this compact list and n is the length of cl. (m ) Instance method: __str__() Returns a string representation of this compact list x_0, x_1, x_2, ... in the form [x_0,x_1 - 1] U [x_2,x_3 - 1] U ... (that is, as a union of closed intervals of integers). If this compact list is empty, it returns empty.

Please review this provided answer, especially the union, intersection and difference parts. flag if there is any inconsistecny, incomplete part, or further improvement, required. The final answer shuold properly run according to the given example.

MIN = -1000 MAX = 1000

class CompactList: def __init__(self,inlist=[]): sorted_list = sorted(set(inlist)) self.compact_list = self.compress(sorted_list) def compress(self, sorted_list): compact_list = [] i = 0 while i < len(sorted_list): start = sorted_list[i] end = start + 1

while end in sorted_list: end += 1

compact_list.extend([start, end]) i = sorted_list.index(end)if end in sorted_list else len(sorted_list)

return compact_list def cardinality(self): return sum((end - start) for start, end in zip(self.compact_list[0::2], self.compact_list[1::2])) def insert(self,value): if not self.contains(value): i = bisect_left(self.compact_list, value) self.compact_list[i:i] = [value, value + 1] def delete(self,value): if self.contains(value): index = self.compact_list.index(value) del self.compact_list[index:index + 2]

def contains(self,value): i = 0 while i < len(self.compact_list): start, end = self.compact_list[i], self.compact_list[i + 1] if start <= value < end: return True i += 2 return False def subsetOf(self,cl): return all(cl.contains(value) for value in self) def equals(self,cl): return all(cl.contains(value) for value in self)

def isEmpty(self): return not bool(self.compact_list)

def complement(self): complement_list = [] if not self.isEmpty(): start = MIN for end in self.compact_list[0::2]: complement_list.extend([start, end]) start = end + 1 if complement_list[-1] < MAX: complement_list.extend([complement_list[-1] + 1, MAX + 1])

return CompactList(complement_list)

def union(self,cl): union_list = self.compact_list + cl.compact_list union_list.sort() return CompactList(union_list)

def intersection(self,cl): intersection_list = [] i, j = 0, 0

while i < len(self.compact_list) and j < len(cl.compact_list): start1, end1 = self.compact_list[i], self.compact_list[i + 1] start2, end2 = cl.compact_list[j], cl.compact_list[j + 1]

if end1 <= start2: i += 2 elif end2 <= start1: j += 2 else: # Compute the intersection between the two intervals start = max(start1, start2) end = min(end1, end2)

intersection_list.extend([start, end])

if end1 < end2: i += 2 else: j += 2

return CompactList(intersection_list) def difference(self,cl): difference_list = [] i, j = 0, 0

while i < len(self.compact_list) and j < len(cl.compact_list): start1, end1 = self.compact_list[i], self.compact_list[i + 1] start2, end2 = cl.compact_list[j], cl.compact_list[j + 1]

if end1 <= start2: difference_list.extend([start1, end1]) i += 2 elif end2 <= start1: i += 2 else: # Compute the difference between the two intervals if start1 < start2: difference_list.extend([start1, start2])

i += 2

if end1 > end2: difference_list.extend([end2, end1])

return CompactList(difference_list) def __str__(self): intervals = [f'[{start},{end - 1}]' for start, end in zip(self.compact_list[0::2], self.compact_list[1::2])] return ' U '.join(intervals) if intervals else 'empty'

if __name__ == "__main__":

mycl1 = CompactList([]) print(mycl1) print(mycl1.cardinality()) mycl2 = CompactList([9,8,3,4,5]) print(mycl2) print(mycl2.cardinality()) print(mycl2, "contains 4:",mycl2.contains(4))

mycl1 = CompactList([10,1,11]) mycl3 = mycl1.union(mycl2) print(mycl3) print(mycl3.cardinality()) mycl1 = mycl2.complement() print(mycl1) print(mycl1.cardinality())

mycl1 = CompactList([MAX]) print(mycl1) print(mycl1.cardinality())