Integer ID pool

I would really appreciate some feedback on the code I wrote to solve the following problem:

Design an IdManager.


IdManager manages a pool of integer ids. (from 1 to n). It should
provide api’s to get_id() and free_id().


get_id(): It returns any id , available in the pool. An Id cannot be
given away again, unless it has been freed.


free_id(int id): It returns the id back to the pool, so that it can be
given out again.


Discuss the api’s definitions, data structures and write tests.

Here is my description:

I used two data structures in my ID Manager. My goal was to make both free_id and get_id \$O(1)\$. I used a dictionary
to keep track of which ids are free, and a list as a stack to give the free ids away. The problem I addressed with
the dictionary was that if I just used a stack to manage the ids, the user of the API could call free_id multiple
times on an id that was already free, and fill the stack up with ids that were not really free. So I decided to use a
dictionary to keep track of whether an id was free or not. That way I can only add an id to the stack if the id is
marked False and raise an exception if a user tries to call free_id on an id that is already free. The result is that
free_id uses append on a list which is \$O(1)\$, set on a dictionary which is also \$O(1)\$ and in dictionary which is also
\$O(1)\$. In get_id, I call pop on the stack which is \$O(1)\$, as well as set on the dictionary which is also \$O(1)\$.

```
import unittest

class IDManager():
def __init__(self, n):
"""
:param pool: integer to create pool from 1 to n
:return: IDManager for managing pool of ids
"""
if not isinstance(n, int):
raise Exception('N must be an int, got type {}'.format(type(n)))
self.id_dict = {i: True for i in range(1, n + 1)}
self.stack = [i for i in range(1, n + 1)]

def get_id(self):
"""
:return: a freed integer id

What about just using a set to store ids? Then you don't need double storage.

Eg

class IdManagerException(Exception): pass

class IdManager(object):
  def __init__(self, n):
    self.max = n
    self.ids = set(range(1, n + 1))

  def get_id(self):
    try:
      return self.ids.pop()
    except KeyError:
      raise IdManagerException("no available ids")

  def free_id(self, n):
    if n > self.max:
      raise IdManagerException("id %d out of range (max %d)" % (n, self.max))

    self.ids.add(n) # no-op if n already there, do we care?

StackExchange Code Review Q#90468, answer score: 5