Suppose you are consulting for a corporation that would like to start a new digital identification (ID) card system. Each employee will be given a distinct ID number, which is a positive integer. These numbers are assigned permanently for life, and cannot be changed. However, as employees join, leave, and potentially re-join the company, their ID numbers can become active or inactive. An ID number is valid when it has been issued by the system, or invalid if that has never happened (e.g. large random numbers are probably invalid). You will design an ID generator data structure that supports the following operations.

// Initialize a new ID generator. ID_INIT() // Generate and then return an ID number for a new employee. This // number is guaranteed to be valid, active, and distinct from all IDs // generated in the past. ID_GENERATE() // Return true if id is a valid ID number (i.e. has been returned by // ID_GENERATE above). ID_VALID(id) // Return true if id is an active and valid ID number. // Return false otherwise (id is inactive or invalid). ID_ACTIVE(id) // Given id that is an active and valid ID, record that // id is now inactive. id remains valid. // Throw an exception if id is not currently active and valid. ID_DEACTIVATE(id) // Given id that is an inactive and valid ID, record that // id is active again. id remains valid. // Throw an exception if id is not currently inactive and valid. ID_ACTIVATE(id)

Design a data structure that implements all these operations; write clear pseudocode that shows how each operation works. You should build upon the data structures we have already covered in class. Your structure should support each of these operations in O(1) time (worst-case, expected, or amortized); and take O(n) space; where n is the number of currently-active IDs. In particular, space should be proportional to the number of active IDs, not the number of valid IDs. Hint: There is a very simple way to track which IDs are valid; do not over-think this part.