from sys import getsizeof, stderr
from itertools import chain
from collections import deque
from reprlib import repr
from array import array


def deepSize(o, handlers={}, verbose=False, seen=None):
  """ Returns the approximate memory footprint an object and all of its contents.

  Automatically finds the contents of the following builtin containers and
  their subclasses:  tuple, list, deque, dict, set and frozenset.
  To search other containers, add handlers to iterate over their contents:

      handlers = {SomeContainerClass: iter,
                  OtherContainerClass: OtherContainerClass.get_elements}

  """
  def dict_handler(d):
    return chain.from_iterable(d.items())

  all_handlers = {
      tuple: iter,
      list: iter,
      deque: iter,
      dict: dict_handler,
      set: iter,
      frozenset: iter,
  }
  all_handlers.update(handlers)     # user handlers take precedence
  if seen is None:
    seen = set()                      # track which object id's have already been seen
  default_size = getsizeof(0)       # estimate sizeof object without __sizeof__

  def sizeof(o):
      if id(o) in seen:       # do not double count the same object
          return 0
      seen.add(id(o))
      s = getsizeof(o, default_size)

      if verbose:
          print(s, type(o), repr(o), file=stderr)

      for typ, handler in all_handlers.items():
          if isinstance(o, typ):
              s += sum(map(sizeof, handler(o)))
              break
      return s

  return sizeof(o)


def findStretches(sequence, threshold=1, amount=None):
  default = (((sequence[0], sequence[-1]),), 0)
  if amount == 1:
    return default
  prevN = 1
  gaps = []
  for n in sequence:
    gap = n - prevN
    if gap > 1:
      gaps.append((prevN, n))
    prevN = n
  nInGap = sum(e - b - 1 for (b, e) in gaps if b >= sequence[0] and e <= sequence[-1])
  nTotal = sequence[-1] - sequence[0] + 1
  gapRatio = nInGap / nTotal if nTotal else 0
  gaps = tuple((b, e) for (b, e) in gaps if e - b > threshold)
  if len(gaps) == 0:
    return default
  if amount is not None and len(gaps) > amount:
    gaps = sorted(
        sorted(gaps, key=lambda x: (x[0] - x[1], x[0]))[0:amount],
        key=lambda x: x[0],
    )
  stretches = []
  if sequence[0] <= gaps[0][0]:
    stretches.append((sequence[0], gaps[0][0]))
  for (i, gap) in enumerate(gaps[0:-1]):
    stretches.append((gap[1], gaps[i + 1][0]))
  if sequence[-1] >= gaps[-1][1]:
    stretches.append((gaps[-1][1], sequence[-1]))
  return (stretches, gapRatio)


CONTAINER_TYPE = {
    'dict': dict,
    'tup': tuple,
}
ELEMENT_TYPE = {
    'int': int,
    'str': str,
    'tup': tuple,
}


def pack(origData, containerSpec, elementSpec, threshold=1000, amount=5):
  UTF8 = 'utf8'

  containerType = CONTAINER_TYPE[containerSpec]
  elementType = ELEMENT_TYPE[elementSpec]

  isDict = containerType is dict
  isInt = elementType is int
  isStr = elementType is str
  isTup = elementType is tuple

  arraySpecifier = 'i'

  if isStr:
    arraySpecifier = 'B'

  valueNumber = array('I')
  valueStart = array('I')
  values = array(arraySpecifier)

  vNumber = 0
  vStart = 0
  offsets = []
  origValueIndex = {}

  if isDict:
    valueNumber.append(0)
    valueStart.append(0)
    values.append(0)
    vNumber = 1
    vStart = 1
    origKeys = sorted(origData)
    (stretches, gapRatio) = findStretches(origKeys, threshold=threshold, amount=amount)

  def addValInt(origVal):
    values.append(origVal)

  def addValStr(origVal):
    nonlocal vStart
    bval = bytes(origVal, encoding=UTF8)
    lval = len(bval)
    values.extend(bval)
    valueStart.append(vStart)
    vStart += lval

  def addValTup(origVal):
    nonlocal vStart
    lval = len(origVal)
    values.extend(origVal)
    valueStart.append(vStart)
    vStart += lval

  addVal = (
      addValStr if isStr else
      addValInt if isInt else
      addValTup if isTup else
      addValInt
  )
  if isDict:
    nKeys = 0
    for (b, e) in stretches:
      offset = b - len(valueNumber)
      offsets.append((b, e, offset))
      for n in range(b, e + 1):
        origVal = origData.get(n, None)
        if origVal is None:
          valueNumber.append(0)
        else:
          nKeys += 1
          thisVNumber = origValueIndex.get(origVal, None)
          if thisVNumber is None:
            thisVNumber = vNumber
            origValueIndex[origVal] = vNumber
            addVal(origVal)
            vNumber += 1
          valueNumber.append(thisVNumber)
  else:
    for origVal in origData:
      thisVNumber = origValueIndex.get(origVal, None)
      if thisVNumber is None:
        thisVNumber = vNumber
        origValueIndex[origVal] = vNumber
        addVal(origVal)
        vNumber += 1
      valueNumber.append(thisVNumber)

  alength = len(valueNumber)
  length = alength
  if isDict:
    offsets = tuple(offsets)
    length = nKeys

  if isStr or isTup:
    valueStart.append(vStart)

  return dict(
      container=containerSpec,
      element=elementSpec,
      valueNumber=valueNumber,
      valueStart=valueStart,
      values=values,
      alength=alength,
      length=length,
      offsets=offsets,
  )


class Pack(object):
  def __init__(self, packedData):
    for (k, v) in packedData.items():
      setattr(self, k, v)
    ctp = self.container
    etp = self.element
    setattr(self, 'get', getattr(self, f'get{ctp}{etp}', None))

  def gettupint(self, n):
    valueNumber = self.valueNumber
    values = self.values
    if n >= len(valueNumber):
      return None
    vNumber = valueNumber[n]
    return values[vNumber]

  def gettuptup(self, n):
    valueNumber = self.valueNumber
    valueStart = self.valueStart
    values = self.values
    if n >= len(valueNumber):
      return None
    vNumber = valueNumber[n]
    vStart = valueStart[vNumber]
    vStartNext = valueStart[vNumber + 1]
    return tuple(values[vStart:vStartNext])

  def gettupstr(self, n):
    UTF8 = 'utf8'
    valueNumber = self.valueNumber
    valueStart = self.valueStart
    values = self.values
    if n >= len(valueNumber):
      return None
    vNumber = valueNumber[n]
    vStart = valueStart[vNumber]
    vStartNext = valueStart[vNumber + 1]
    return str(values[vStart:vStartNext], encoding=UTF8)

  def getdictint(self, n):
    valueNumber = self.valueNumber
    values = self.values
    offsets = self.offsets
    for (b, e, offset) in offsets:
      if b <= n <= e:
        m = n - offset
        vNumber = valueNumber[m]
        if vNumber == 0:
          return None
        return values[vNumber]
    return None

  def getdicttup(self, n):
    valueNumber = self.valueNumber
    valueStart = self.valueStart
    values = self.values
    offsets = self.offsets
    for (b, e, offset) in offsets:
      if b <= n <= e:
        m = n - offset
        vNumber = valueNumber[m]
        if vNumber == 0:
          return None
        vStart = valueStart[vNumber]
        vStartNext = valueStart[vNumber + 1]
        return tuple(values[vStart:vStartNext])
    return None

  def getdictstr(self, n):
    UTF8 = 'utf8'
    valueNumber = self.valueNumber
    valueStart = self.valueStart
    values = self.values
    offsets = self.offsets
    for (b, e, offset) in offsets:
      if b <= n <= e:
        m = n - offset
        vNumber = valueNumber[m]
        if vNumber == 0:
          return None
        vStart = valueStart[vNumber]
        vStartNext = valueStart[vNumber + 1]
        return str(values[vStart:vStartNext], encoding=UTF8)
    return None