class_docstr: Sampler based on Vose's algorithm for the alias method. See
  http://www.keithschwarz.com/darts-dice-coins/ for a good explanation.
  
  The general idea is that we store a table of triples (base, alternate, p).
  base. We then pick a triple uniformly at random, and choose its alternate
  value with probability p and else choose its base value. The triples are
  chosen so that the resulting mixture has the right distribution.
  
  We maintain the following invariants to try to produce good shrinks:
  
  1. The table is in lexicographic (base, alternate) order, so that choosing
     an earlier value in the list always lowers (or at least leaves
     unchanged) the value.
  2. base[i] < alternate[i], so that shrinking the draw always results in
     shrinking the chosen element.
class_docstr_tok: ["Sampler","based","on","Vose","'s","algorithm","for","the","alias","method",".","See","http",":","\/\/www.keithschwarz.com\/darts-dice-coins\/","for","a","good","explanation",".","The","general","idea","is","that","we","store","a","table","of","triples","(","base",",","alternate",",","p",")",".","base",".","We","then","pick","a","triple","uniformly","at","random",",","and","choose","its","alternate","value","with","probability","p","and","else","choose","its","base","value",".","The","triples","are","chosen","so","that","the","resulting","mixture","has","the","right","distribution",".","We","maintain","the","following","invariants","to","try","to","produce","good","shrinks",":","1",".","The","table","is","in","lexicographic","(","base",",","alternate",")","order",",","so","that","choosing","an","earlier","value","in","the","list","always","lowers","(","or","at","least","leaves","unchanged",")","the","value",".","2.","base","[","i","]","<","alternate","[","i","]",",","so","that","shrinking","the","draw","always","results","in","shrinking","the","chosen","element","."]
code: def __init__(self, weights: Sequence[float]):
      n = len(weights)
  
      table: "list[list[int | float | None]]" = [
          [i, None, None] for i in range(n)
      ]
  
      total = sum(weights)
  
      num_type = type(total)
  
      zero = num_type(0)  # type: ignore
      one = num_type(1)  # type: ignore
  
      small: "List[int]" = []
      large: "List[int]" = []
  
      probabilities = [w / total for w in weights]
      scaled_probabilities: "List[float]" = []
  
      for i, alternate_chance in enumerate(probabilities):
          scaled = alternate_chance * n
          scaled_probabilities.append(scaled)
          if scaled == 1:
              table[i][2] = zero
          elif scaled < 1:
              small.append(i)
          else:
              large.append(i)
      heapq.heapify(small)
      heapq.heapify(large)
  
      while small and large:
          lo = heapq.heappop(small)
          hi = heapq.heappop(large)
  
          assert lo != hi
          assert scaled_probabilities[hi] > one
          assert table[lo][1] is None
          table[lo][1] = hi
          table[lo][2] = one - scaled_probabilities[lo]
          scaled_probabilities[hi] = (
              scaled_probabilities[hi] + scaled_probabilities[lo]
          ) - one
  
          if scaled_probabilities[hi] < 1:
              heapq.heappush(small, hi)
          elif scaled_probabilities[hi] == 1:
              table[hi][2] = zero
          else:
              heapq.heappush(large, hi)
      while large:
          table[large.pop()][2] = zero
      while small:
          table[small.pop()][2] = zero
  
      self.table: "List[Tuple[int, int, float]]" = []
      for base, alternate, alternate_chance in table:  # type: ignore
          assert isinstance(base, int)
          assert isinstance(alternate, int) or alternate is None
          if alternate is None:
              self.table.append((base, base, alternate_chance))
          elif alternate < base:
              self.table.append(
                  (alternate, base, one - alternate_chance)
              )
          else:
              self.table.append((base, alternate, alternate_chance))
      self.table.sort()
  
imports: import enum
  import hashlib
  import heapq
  import sys
  from collections import OrderedDict, abc
  from functools import lru_cache
  from typing import TYPE_CHECKING, List, Optional, Sequence, Tuple, Type, TypeVar, Union
  from hypothesis.errors import InvalidArgument
  from hypothesis.internal.compat import int_from_bytes
  from hypothesis.internal.floats import next_up
label_desc: Use image node_id 1 to create a new Sampler object  with example: obj = Sampler(weights)