text: #!/usr/bin/env python
  
  # Copyright (c) 2014–2018, Eddie Antonio Santos <easantos@ualberta.ca>
  #
  # Permission to use, copy, modify, and/or distribute this software for any
  # purpose with or without fee is hereby granted, provided that the above
  # copyright notice and this permission notice appear in all copies.
  #
  # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  
  """
  Adapted from:
  https://bitbucket.org/eddieantonio/chromatic/src/9c1c6c61881e2ff99fea63abef481cf2c6e19301/colour_preview.py
  """
  
  from __future__ import division
  from __future__ import print_function
  
  import math
  import collections
  import functools
  import pprint
  
  from color_db import COLORS
  
  
  colours = [(rgb, name) for name, rgb in COLORS.items()]
  colours.sort(key=lambda pair: pair[1])
  
  
  suggested_styles = """
  body { margin: 0 }
  pre {
      white-space: pre-wrap;
      text-indent: -1em;
      padding: 1em 1em 1em 2em;
      box-shadow: inset 0px 2px 12px black;
  }
  .colour-box {
      font: bold 16pt sans-serif;
      text-align: center;
      padding: 1em;
      color: white;
  }
  """
  
  # C templates:
  template = """/* AUTOGENERATED FILE. DO NOT MODIFY. */
  #include "rgbtree.h"
  
  RGB_Node {name:s}[] = {{
      {tree:s}
  }};
  """
  node_template = ("{{ .id = {id: >3d}, "
                   ".colour = {{{{{color[0]: >3d}, {color[1]: >3d}, {color[2]: >3d}}}}}, "
                   ".axis = {axis:s}"
                   ".left = {left}, "
                   ".right = {right} }}")
  node_sep = ",\n    "
  AXES = 'RED GREEN BLUE'.split()
  
  KdNode = collections.namedtuple('KdNode', 'data pos depth left right')
  
  
  def _kd_node_dictify(self):
      """
      Returns a dict of the KdNode as dict, recursivly (all descendants
      are dicts made into dicts as well). Useful for pretty printing.
      """
      printable = self._asdict()
  
      for side in ('left', 'right'):
          if printable[side]:
              printable[side] = _kd_node_dictify(printable[side])
  
      return printable
  
  KdNode.dictify = _kd_node_dictify
  KdNode.__repr__ = lambda self: repr(self.dictify())
  
  
  class KdTree(object):
  
      """
      k-d tree.
      """
      node_factory = KdNode
  
      def __init__(self, seed):
          self.k = None
          self.root = None
          self.populate(seed)
  
      def populate(self, seed):
          """
          Uses seed to instantiate the k-d tree.
          """
          if not seed:
              self.root = None
  
          seed_list = list(seed)
          point, data = seed_list[0]
          self.k = len(point)
  
          self.root = self._create_tree(seed_list, 0)
  
      def _create_tree(self, seed, depth):
          if not seed:
              return None
  
          axis = depth % self.k
          sorted_seed = sorted(seed, key=lambda t: t[0][axis])
  
          median_index = len(sorted_seed) // 2
          lower, pivot, upper = partition(sorted_seed, median_index)
  
          pivot_pos, pivot_data = pivot
          node = self.node_factory(
              data=pivot_data,
              pos=pivot_pos,
              depth=depth,
              left=self._create_tree(lower, depth + 1),
              right=self._create_tree(upper, depth + 1))
  
          return node
  
      def _collate_descendants(self, target, depth, closest_node, child):
          """
          Finds the best descendant starting from child. If the closest
          node from the child's descendants is better than the
          current_node, this tuple is returned. Else, the currrent_node is
          returned.
          """
  
          node, current_best = closest_node
  
          best_descendant = self._find_nearest(target, child, depth + 1)
          descendant, descendant_distance = best_descendant
  
          if descendant_distance < current_best:
              return best_descendant
          else:
              return closest_node
  
      def find_nearest(self, target, node=None):
          if not node:
              node = self.root
  
          return self._find_nearest(target, node, 0)
  
      def _find_nearest(self, target, node, depth):
          """
          Finds the node in the tree that is closest to the target,
          a position with the same dimensions as the nodes in the tree.
          """
  
          this_distance = squared_euclidean_distance(node.pos, target)
          closest_node = (node, this_distance)
  
          if not (node.left or node.right):
              return closest_node
  
          axis = depth % self.k
          if target[axis] < node.pos[axis]:
              nearer_child, farther_child = node.left, node.right
          else:
              nearer_child, farther_child = node.right, node.left
  
          find_in_child = functools.partial(self._collate_descendants,
                                            target, depth)
  
          if nearer_child:
              closest_node = find_in_child(closest_node, nearer_child)
  
          if farther_child:
              if abs(target[axis] - node.pos[axis]) < closest_node[1]:
                  closest_node = find_in_child(closest_node, farther_child)
  
          return closest_node
  
      def dictify(self):
          return self.root.dictify()
  
  
  def squared_euclidean_distance(p, q):
      """
      N-dimensional squared Euclidean distance. Like Euclidean distance,
      but squared! Forgoing the square root is a minor optimization but it
      shaves off a few cycles when only distances need be to compared.
      Unlike euclidean_distance, the return value is not guaranteed to be
      a float.
  
      >>> squared_euclidean_distance([0, 0, 0], [1, 1, 1])
      3
      >>> squared_euclidean_distance((0, 0), (3, 4))
      25
      """
      differences_squared = ((pn - qn) ** 2 for pn, qn in zip(p, q))
      return sum(differences_squared)
  
  
  def euclidean_distance(p, q):
      """
      N-dimensional Euclidean distance. Given two iteratables with the
      same dimensions (not enforced--be careful!), returns the Euclidean
      distance between the points.
  
      >>> euclidean_distance((7,), (5,))
      2.0
      >>> euclidean_distance((0, 0), (3, 4))
      5.0
      """
      return math.sqrt(squared_euclidean_distance(p, q))
  
  
  def partition(l, pivot_index):
      """
      Partitions a list at pivot index. Returns a tuple consisting of the
      sublist before the partition, the pivot, and the sublist after the
      pivot.
      """
      return (l[:pivot_index], l[pivot_index], l[pivot_index + 1:])
  
  
  def make_divs(colour_table):
      """
      Make <div> elements for a list of (normalized RGB tuple, name).
  
      Returns these <div>s as a string.
      """
      for rgb_tuple, name in colour_table:
          html = (
              "<div class='colour-box'"
              " style='background-color: rgb%(rgb_tuple)r;'"
              "> %(name)s </div>" % locals()
          )
  
          yield html
  
  
  def print_html(*args, **kwargs):
      """
      Prints an HTML snippet to STDOUT. This contatins a preview of each
      colour in `colours` as well as `colours` as a KDTree (pretty-printed
      as a dict).
      """
  
      print('<style>', suggested_styles, '</style>', sep='')
  
      for div in make_divs(colours):
          print(div)
  
      tree = KdTree(colours)
      print('<pre>')
      pprint.pprint(tree.dictify())
      print('</pre>')
  
      return 0
  
  # list all of the nodes ever.
  def list_nodes(node):
      if node is not None:
          yield node
          for branch in (node.left, node.right):
              for ancestor in list_nodes(branch):
                  yield ancestor
  
  def print_c(*args, **kwargs):
      tree = KdTree(colours)
  
      name = "TREE_256_COLOR"
  
      node_index = {}
      node_list = list(list_nodes(tree.root))
  
      # Do a depth first search
      for index, node in enumerate(node_list):
          node_index[id(node)] = index
  
  
      def format_child(node):
          if node is None:
              return "0"
          index = node_index[id(node)]
          return "{name:s} + {index:d}".format(name=name, index=index)
  
      def format_axis(node):
          axis_name = AXES[node.depth % 3] + ','
          return "{: <7s}".format(axis_name)
  
      def gen_struct():
          for node in node_list:
              canonical_id = int(node.data, 10)
  
              yield node_template.format(id=canonical_id,
                                         color=node.pos,
                                         axis=format_axis(node),
                                         left=format_child(node.left),
                                         right=format_child(node.right))
      inner = node_sep.join(gen_struct())
  
      print(template.format(name=name, tree=inner))
  
  
  if __name__ == '__main__':
      import sys
  
      main = print_html if '--html' in sys.argv else print_c
  
      sys.exit(main(*sys.argv))
  