<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ -->
<title>utils/GraphColor.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>{-# OPTIONS -fno-warn-missing-signatures #-}</span>
<a name="line-2"></a>
<a name="line-3"></a><span class='hs-comment'>-- | Graph Coloring.</span>
<a name="line-4"></a><span class='hs-comment'>-- This is a generic graph coloring library, abstracted over the type of</span>
<a name="line-5"></a><span class='hs-comment'>-- the node keys, nodes and colors.</span>
<a name="line-6"></a><span class='hs-comment'>--</span>
<a name="line-7"></a>
<a name="line-8"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>GraphColor</span> <span class='hs-layout'>(</span>
<a name="line-9"></a> <span class='hs-keyword'>module</span> <span class='hs-conid'>GraphBase</span><span class='hs-layout'>,</span>
<a name="line-10"></a> <span class='hs-keyword'>module</span> <span class='hs-conid'>GraphOps</span><span class='hs-layout'>,</span>
<a name="line-11"></a> <span class='hs-keyword'>module</span> <span class='hs-conid'>GraphPpr</span><span class='hs-layout'>,</span>
<a name="line-12"></a> <span class='hs-varid'>colorGraph</span>
<a name="line-13"></a><span class='hs-layout'>)</span>
<a name="line-14"></a>
<a name="line-15"></a><span class='hs-keyword'>where</span>
<a name="line-16"></a>
<a name="line-17"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>GraphBase</span>
<a name="line-18"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>GraphOps</span>
<a name="line-19"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>GraphPpr</span>
<a name="line-20"></a>
<a name="line-21"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Unique</span>
<a name="line-22"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqFM</span>
<a name="line-23"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqSet</span>
<a name="line-24"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Outputable</span>
<a name="line-25"></a>
<a name="line-26"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Maybe</span>
<a name="line-27"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span>
<a name="line-28"></a>
<a name="line-29"></a>
<a name="line-30"></a><a name="colorGraph"></a><span class='hs-comment'>-- | Try to color a graph with this set of colors.</span>
<a name="line-31"></a><span class='hs-comment'>-- Uses Chaitin's algorithm to color the graph.</span>
<a name="line-32"></a><span class='hs-comment'>-- The graph is scanned for nodes which are deamed 'trivially colorable'. These nodes</span>
<a name="line-33"></a><span class='hs-comment'>-- are pushed onto a stack and removed from the graph.</span>
<a name="line-34"></a><span class='hs-comment'>-- Once this process is complete the graph can be colored by removing nodes from</span>
<a name="line-35"></a><span class='hs-comment'>-- the stack (ie in reverse order) and assigning them colors different to their neighbors.</span>
<a name="line-36"></a><span class='hs-comment'>--</span>
<a name="line-37"></a><span class='hs-definition'>colorGraph</span>
<a name="line-38"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>color</span>
<a name="line-39"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>color</span><span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>k</span>
<a name="line-40"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>color</span><span class='hs-layout'>)</span>
<a name="line-41"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Bool</span> <span class='hs-comment'>-- ^ whether to do iterative coalescing</span>
<a name="line-42"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int</span> <span class='hs-comment'>-- ^ how many times we've tried to color this graph so far.</span>
<a name="line-43"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>UniqFM</span> <span class='hs-layout'>(</span><span class='hs-conid'>UniqSet</span> <span class='hs-varid'>color</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ map of (node class -> set of colors available for this class).</span>
<a name="line-44"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Triv</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- ^ fn to decide whether a node is trivially colorable.</span>
<a name="line-45"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.</span>
<a name="line-46"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- ^ the graph to color.</span>
<a name="line-47"></a>
<a name="line-48"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- the colored graph.</span>
<a name="line-49"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>UniqSet</span> <span class='hs-varid'>k</span> <span class='hs-comment'>-- the set of nodes that we couldn't find a color for.</span>
<a name="line-50"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>UniqFM</span> <span class='hs-varid'>k</span> <span class='hs-layout'>)</span> <span class='hs-comment'>-- map of regs (r1 -> r2) that were coaleced</span>
<a name="line-51"></a> <span class='hs-comment'>-- r1 should be replaced by r2 in the source</span>
<a name="line-52"></a>
<a name="line-53"></a><span class='hs-definition'>colorGraph</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>spinCount</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph0</span>
<a name="line-54"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span>
<a name="line-55"></a> <span class='hs-comment'>-- If we're not doing iterative coalescing then do an aggressive coalescing first time</span>
<a name="line-56"></a> <span class='hs-comment'>-- around and then conservative coalescing for subsequent passes.</span>
<a name="line-57"></a> <span class='hs-comment'>--</span>
<a name="line-58"></a> <span class='hs-comment'>-- Aggressive coalescing is a quick way to get rid of many reg-reg moves. However, if</span>
<a name="line-59"></a> <span class='hs-comment'>-- there is a lot of register pressure and we do it on every round then it can make the</span>
<a name="line-60"></a> <span class='hs-comment'>-- graph less colorable and prevent the algorithm from converging in a sensible number</span>
<a name="line-61"></a> <span class='hs-comment'>-- of cycles.</span>
<a name="line-62"></a> <span class='hs-comment'>--</span>
<a name="line-63"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph_coalesced</span><span class='hs-layout'>,</span> <span class='hs-varid'>kksCoalesce1</span><span class='hs-layout'>)</span>
<a name="line-64"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>iterative</span>
<a name="line-65"></a> <span class='hs-keyword'>then</span> <span class='hs-layout'>(</span><span class='hs-varid'>graph0</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-66"></a> <span class='hs-keyword'>else</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>spinCount</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span>
<a name="line-67"></a> <span class='hs-keyword'>then</span> <span class='hs-varid'>coalesceGraph</span> <span class='hs-conid'>True</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>graph0</span>
<a name="line-68"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>coalesceGraph</span> <span class='hs-conid'>False</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>graph0</span>
<a name="line-69"></a>
<a name="line-70"></a> <span class='hs-comment'>-- run the scanner to slurp out all the trivially colorable nodes</span>
<a name="line-71"></a> <span class='hs-comment'>-- (and do coalescing if iterative coalescing is enabled)</span>
<a name="line-72"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ksTriv</span><span class='hs-layout'>,</span> <span class='hs-varid'>ksProblems</span><span class='hs-layout'>,</span> <span class='hs-varid'>kksCoalesce2</span><span class='hs-layout'>)</span>
<a name="line-73"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>colorScan</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph_coalesced</span>
<a name="line-74"></a>
<a name="line-75"></a> <span class='hs-comment'>-- If iterative coalescing is enabled, the scanner will coalesce the graph as does its business.</span>
<a name="line-76"></a> <span class='hs-comment'>-- We need to apply all the coalescences found by the scanner to the original</span>
<a name="line-77"></a> <span class='hs-comment'>-- graph before doing assignColors.</span>
<a name="line-78"></a> <span class='hs-comment'>--</span>
<a name="line-79"></a> <span class='hs-comment'>-- Because we've got the whole, non-pruned graph here we turn on aggressive coalecing</span>
<a name="line-80"></a> <span class='hs-comment'>-- to force all the (conservative) coalescences found during scanning.</span>
<a name="line-81"></a> <span class='hs-comment'>--</span>
<a name="line-82"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph_scan_coalesced</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span>
<a name="line-83"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mapAccumL</span> <span class='hs-layout'>(</span><span class='hs-varid'>coalesceNodes</span> <span class='hs-conid'>True</span> <span class='hs-varid'>triv</span><span class='hs-layout'>)</span> <span class='hs-varid'>graph_coalesced</span> <span class='hs-varid'>kksCoalesce2</span>
<a name="line-84"></a>
<a name="line-85"></a> <span class='hs-comment'>-- color the trivially colorable nodes</span>
<a name="line-86"></a> <span class='hs-comment'>-- during scanning, keys of triv nodes were added to the front of the list as they were found</span>
<a name="line-87"></a> <span class='hs-comment'>-- this colors them in the reverse order, as required by the algorithm.</span>
<a name="line-88"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph_triv</span><span class='hs-layout'>,</span> <span class='hs-varid'>ksNoTriv</span><span class='hs-layout'>)</span>
<a name="line-89"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>assignColors</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph_scan_coalesced</span> <span class='hs-varid'>ksTriv</span>
<a name="line-90"></a>
<a name="line-91"></a> <span class='hs-comment'>-- try and color the problem nodes</span>
<a name="line-92"></a> <span class='hs-comment'>-- problem nodes are the ones that were left uncolored because they weren't triv.</span>
<a name="line-93"></a> <span class='hs-comment'>-- theres a change we can color them here anyway.</span>
<a name="line-94"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph_prob</span><span class='hs-layout'>,</span> <span class='hs-varid'>ksNoColor</span><span class='hs-layout'>)</span>
<a name="line-95"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>assignColors</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph_triv</span> <span class='hs-varid'>ksProblems</span>
<a name="line-96"></a>
<a name="line-97"></a> <span class='hs-comment'>-- if the trivially colorable nodes didn't color then something is probably wrong</span>
<a name="line-98"></a> <span class='hs-comment'>-- with the provided triv function.</span>
<a name="line-99"></a> <span class='hs-comment'>--</span>
<a name="line-100"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>not</span> <span class='hs-varop'>$</span> <span class='hs-varid'>null</span> <span class='hs-varid'>ksNoTriv</span>
<a name="line-101"></a> <span class='hs-keyword'>then</span> <span class='hs-varid'>pprPanic</span> <span class='hs-str'>"colorGraph: trivially colorable nodes didn't color!"</span> <span class='hs-comment'>-- empty</span>
<a name="line-102"></a> <span class='hs-layout'>(</span> <span class='hs-varid'>empty</span>
<a name="line-103"></a> <span class='hs-varop'>$$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"ksTriv = "</span> <span class='hs-varop'><></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>ksTriv</span>
<a name="line-104"></a> <span class='hs-varop'>$$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"ksNoTriv = "</span> <span class='hs-varop'><></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>ksNoTriv</span>
<a name="line-105"></a> <span class='hs-varop'>$$</span> <span class='hs-varid'>text</span> <span class='hs-str'>"colors = "</span> <span class='hs-varop'><></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>colors</span>
<a name="line-106"></a> <span class='hs-varop'>$$</span> <span class='hs-varid'>empty</span>
<a name="line-107"></a> <span class='hs-varop'>$$</span> <span class='hs-varid'>dotGraph</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>text</span> <span class='hs-str'>"white"</span><span class='hs-layout'>)</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>graph_triv</span><span class='hs-layout'>)</span>
<a name="line-108"></a>
<a name="line-109"></a> <span class='hs-keyword'>else</span> <span class='hs-layout'>(</span> <span class='hs-varid'>graph_prob</span>
<a name="line-110"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>mkUniqSet</span> <span class='hs-varid'>ksNoColor</span> <span class='hs-comment'>-- the nodes that didn't color (spills)</span>
<a name="line-111"></a> <span class='hs-layout'>,</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>iterative</span>
<a name="line-112"></a> <span class='hs-keyword'>then</span> <span class='hs-layout'>(</span><span class='hs-varid'>listToUFM</span> <span class='hs-varid'>kksCoalesce2</span><span class='hs-layout'>)</span>
<a name="line-113"></a> <span class='hs-keyword'>else</span> <span class='hs-layout'>(</span><span class='hs-varid'>listToUFM</span> <span class='hs-varid'>kksCoalesce1</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-114"></a>
<a name="line-115"></a>
<a name="line-116"></a><span class='hs-comment'>-- | Scan through the conflict graph separating out trivially colorable and</span>
<a name="line-117"></a><span class='hs-comment'>-- potentially uncolorable (problem) nodes.</span>
<a name="line-118"></a><span class='hs-comment'>--</span>
<a name="line-119"></a><span class='hs-comment'>-- Checking whether a node is trivially colorable or not is a resonably expensive operation,</span>
<a name="line-120"></a><span class='hs-comment'>-- so after a triv node is found and removed from the graph it's no good to return to the 'start'</span>
<a name="line-121"></a><span class='hs-comment'>-- of the graph and recheck a bunch of nodes that will probably still be non-trivially colorable.</span>
<a name="line-122"></a><span class='hs-comment'>--</span>
<a name="line-123"></a><span class='hs-comment'>-- To ward against this, during each pass through the graph we collect up a list of triv nodes</span>
<a name="line-124"></a><span class='hs-comment'>-- that were found, and only remove them once we've finished the pass. The more nodes we can delete</span>
<a name="line-125"></a><span class='hs-comment'>-- at once the more likely it is that nodes we've already checked will become trivially colorable</span>
<a name="line-126"></a><span class='hs-comment'>-- for the next pass.</span>
<a name="line-127"></a><span class='hs-comment'>--</span>
<a name="line-128"></a><span class='hs-comment'>-- TODO: add work lists to finding triv nodes is easier.</span>
<a name="line-129"></a><span class='hs-comment'>-- If we've just scanned the graph, and removed triv nodes, then the only</span>
<a name="line-130"></a><span class='hs-comment'>-- nodes that we need to rescan are the ones we've removed edges from.</span>
<a name="line-131"></a>
<a name="line-132"></a><a name="colorScan"></a><span class='hs-definition'>colorScan</span>
<a name="line-133"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>color</span>
<a name="line-134"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>cls</span>
<a name="line-135"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>)</span>
<a name="line-136"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Bool</span> <span class='hs-comment'>-- ^ whether to do iterative coalescing</span>
<a name="line-137"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Triv</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- ^ fn to decide whether a node is trivially colorable</span>
<a name="line-138"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ fn to choose a node to potentially leave uncolored if nothing is trivially colorable.</span>
<a name="line-139"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- ^ the graph to scan</span>
<a name="line-140"></a>
<a name="line-141"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-varid'>k</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>k</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- triv colorable nodes, problem nodes, pairs of nodes to coalesce</span>
<a name="line-142"></a>
<a name="line-143"></a><span class='hs-definition'>colorScan</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph</span>
<a name="line-144"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>colorScan_spin</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span>
<a name="line-145"></a>
<a name="line-146"></a><a name="colorScan_spin"></a><span class='hs-definition'>colorScan_spin</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph</span>
<a name="line-147"></a> <span class='hs-varid'>ksTriv</span> <span class='hs-varid'>ksSpill</span> <span class='hs-varid'>kksCoalesce</span>
<a name="line-148"></a>
<a name="line-149"></a> <span class='hs-comment'>-- if the graph is empty then we're done</span>
<a name="line-150"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>isNullUFM</span> <span class='hs-varop'>$</span> <span class='hs-varid'>graphMap</span> <span class='hs-varid'>graph</span>
<a name="line-151"></a> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>ksTriv</span><span class='hs-layout'>,</span> <span class='hs-varid'>ksSpill</span><span class='hs-layout'>,</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>kksCoalesce</span><span class='hs-layout'>)</span>
<a name="line-152"></a>
<a name="line-153"></a> <span class='hs-comment'>-- Simplify:</span>
<a name="line-154"></a> <span class='hs-comment'>-- Look for trivially colorable nodes.</span>
<a name="line-155"></a> <span class='hs-comment'>-- If we can find some then remove them from the graph and go back for more.</span>
<a name="line-156"></a> <span class='hs-comment'>--</span>
<a name="line-157"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>nsTrivFound</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span>
<a name="line-158"></a> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>scanGraph</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>node</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>triv</span> <span class='hs-layout'>(</span><span class='hs-varid'>nodeClass</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>nodeConflicts</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>nodeExclusions</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span>
<a name="line-159"></a>
<a name="line-160"></a> <span class='hs-comment'>-- for iterative coalescing we only want non-move related</span>
<a name="line-161"></a> <span class='hs-comment'>-- nodes here</span>
<a name="line-162"></a> <span class='hs-varop'>&&</span> <span class='hs-layout'>(</span><span class='hs-varid'>not</span> <span class='hs-varid'>iterative</span> <span class='hs-varop'>||</span> <span class='hs-varid'>isEmptyUniqSet</span> <span class='hs-layout'>(</span><span class='hs-varid'>nodeCoalesce</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-163"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>graph</span>
<a name="line-164"></a>
<a name="line-165"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>ksTrivFound</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>map</span> <span class='hs-varid'>nodeId</span> <span class='hs-varid'>nsTrivFound</span>
<a name="line-166"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>graph2</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>foldr</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>k</span> <span class='hs-varid'>g</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>let</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>g'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>delNode</span> <span class='hs-varid'>k</span> <span class='hs-varid'>g</span>
<a name="line-167"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>g'</span><span class='hs-layout'>)</span>
<a name="line-168"></a> <span class='hs-varid'>graph</span> <span class='hs-varid'>ksTrivFound</span>
<a name="line-169"></a>
<a name="line-170"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>colorScan_spin</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph2</span>
<a name="line-171"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ksTrivFound</span> <span class='hs-varop'>++</span> <span class='hs-varid'>ksTriv</span><span class='hs-layout'>)</span>
<a name="line-172"></a> <span class='hs-varid'>ksSpill</span>
<a name="line-173"></a> <span class='hs-varid'>kksCoalesce</span>
<a name="line-174"></a>
<a name="line-175"></a> <span class='hs-comment'>-- Coalesce:</span>
<a name="line-176"></a> <span class='hs-comment'>-- If we're doing iterative coalescing and no triv nodes are avaliable</span>
<a name="line-177"></a> <span class='hs-comment'>-- then it's time for a coalescing pass.</span>
<a name="line-178"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>iterative</span>
<a name="line-179"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>coalesceGraph</span> <span class='hs-conid'>False</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>graph</span> <span class='hs-keyword'>of</span>
<a name="line-180"></a>
<a name="line-181"></a> <span class='hs-comment'>-- we were able to coalesce something</span>
<a name="line-182"></a> <span class='hs-comment'>-- go back to Simplify and see if this frees up more nodes to be trivially colorable.</span>
<a name="line-183"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph2</span><span class='hs-layout'>,</span> <span class='hs-varid'>kksCoalesceFound</span> <span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-184"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>colorScan_spin</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph2</span>
<a name="line-185"></a> <span class='hs-varid'>ksTriv</span> <span class='hs-varid'>ksSpill</span> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-varid'>kksCoalesceFound</span> <span class='hs-varop'>++</span> <span class='hs-varid'>kksCoalesce</span><span class='hs-layout'>)</span>
<a name="line-186"></a>
<a name="line-187"></a> <span class='hs-comment'>-- Freeze:</span>
<a name="line-188"></a> <span class='hs-comment'>-- nothing could be coalesced (or was triv),</span>
<a name="line-189"></a> <span class='hs-comment'>-- time to choose a node to freeze and give up on ever coalescing it.</span>
<a name="line-190"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph2</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-191"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyword'>case</span> <span class='hs-varid'>freezeOneInGraph</span> <span class='hs-varid'>graph2</span> <span class='hs-keyword'>of</span>
<a name="line-192"></a>
<a name="line-193"></a> <span class='hs-comment'>-- we were able to freeze something</span>
<a name="line-194"></a> <span class='hs-comment'>-- hopefully this will free up something for Simplify</span>
<a name="line-195"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph3</span><span class='hs-layout'>,</span> <span class='hs-conid'>True</span><span class='hs-layout'>)</span>
<a name="line-196"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>colorScan_spin</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph3</span>
<a name="line-197"></a> <span class='hs-varid'>ksTriv</span> <span class='hs-varid'>ksSpill</span> <span class='hs-varid'>kksCoalesce</span>
<a name="line-198"></a>
<a name="line-199"></a> <span class='hs-comment'>-- we couldn't find something to freeze either</span>
<a name="line-200"></a> <span class='hs-comment'>-- time for a spill</span>
<a name="line-201"></a> <span class='hs-layout'>(</span><span class='hs-varid'>graph3</span><span class='hs-layout'>,</span> <span class='hs-conid'>False</span><span class='hs-layout'>)</span>
<a name="line-202"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>colorScan_spill</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph3</span>
<a name="line-203"></a> <span class='hs-varid'>ksTriv</span> <span class='hs-varid'>ksSpill</span> <span class='hs-varid'>kksCoalesce</span>
<a name="line-204"></a>
<a name="line-205"></a> <span class='hs-comment'>-- spill time</span>
<a name="line-206"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-207"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>colorScan_spill</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph</span>
<a name="line-208"></a> <span class='hs-varid'>ksTriv</span> <span class='hs-varid'>ksSpill</span> <span class='hs-varid'>kksCoalesce</span>
<a name="line-209"></a>
<a name="line-210"></a>
<a name="line-211"></a><a name="colorScan_spill"></a><span class='hs-comment'>-- Select:</span>
<a name="line-212"></a><span class='hs-comment'>-- we couldn't find any triv nodes or things to freeze or coalesce,</span>
<a name="line-213"></a><span class='hs-comment'>-- and the graph isn't empty yet.. We'll have to choose a spill</span>
<a name="line-214"></a><span class='hs-comment'>-- candidate and leave it uncolored.</span>
<a name="line-215"></a><span class='hs-comment'>--</span>
<a name="line-216"></a><span class='hs-definition'>colorScan_spill</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph</span>
<a name="line-217"></a> <span class='hs-varid'>ksTriv</span> <span class='hs-varid'>ksSpill</span> <span class='hs-varid'>kksCoalesce</span>
<a name="line-218"></a>
<a name="line-219"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>kSpill</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph</span>
<a name="line-220"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>graph'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>delNode</span> <span class='hs-varid'>kSpill</span> <span class='hs-varid'>graph</span>
<a name="line-221"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>colorScan_spin</span> <span class='hs-varid'>iterative</span> <span class='hs-varid'>triv</span> <span class='hs-varid'>spill</span> <span class='hs-varid'>graph'</span>
<a name="line-222"></a> <span class='hs-varid'>ksTriv</span> <span class='hs-layout'>(</span><span class='hs-varid'>kSpill</span> <span class='hs-conop'>:</span> <span class='hs-varid'>ksSpill</span><span class='hs-layout'>)</span> <span class='hs-varid'>kksCoalesce</span>
<a name="line-223"></a>
<a name="line-224"></a>
<a name="line-225"></a><span class='hs-comment'>-- | Try to assign a color to all these nodes.</span>
<a name="line-226"></a>
<a name="line-227"></a><a name="assignColors"></a><span class='hs-definition'>assignColors</span>
<a name="line-228"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>color</span>
<a name="line-229"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>color</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>)</span>
<a name="line-230"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>UniqFM</span> <span class='hs-layout'>(</span><span class='hs-conid'>UniqSet</span> <span class='hs-varid'>color</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ map of (node class -> set of colors available for this class).</span>
<a name="line-231"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- ^ the graph</span>
<a name="line-232"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>k</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- ^ nodes to assign a color to.</span>
<a name="line-233"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- the colored graph</span>
<a name="line-234"></a> <span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>k</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- the nodes that didn't color.</span>
<a name="line-235"></a>
<a name="line-236"></a><span class='hs-definition'>assignColors</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph</span> <span class='hs-varid'>ks</span>
<a name="line-237"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>assignColors'</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>ks</span>
<a name="line-238"></a>
<a name="line-239"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>assignColors'</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>graph</span> <span class='hs-varid'>prob</span> <span class='hs-conid'>[]</span>
<a name="line-240"></a> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>graph</span><span class='hs-layout'>,</span> <span class='hs-varid'>prob</span><span class='hs-layout'>)</span>
<a name="line-241"></a>
<a name="line-242"></a> <span class='hs-varid'>assignColors'</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph</span> <span class='hs-varid'>prob</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-conop'>:</span><span class='hs-varid'>ks</span><span class='hs-layout'>)</span>
<a name="line-243"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>assignColor</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>k</span> <span class='hs-varid'>graph</span> <span class='hs-keyword'>of</span>
<a name="line-244"></a>
<a name="line-245"></a> <span class='hs-comment'>-- couldn't color this node</span>
<a name="line-246"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>assignColors'</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span> <span class='hs-conop'>:</span> <span class='hs-varid'>prob</span><span class='hs-layout'>)</span> <span class='hs-varid'>ks</span>
<a name="line-247"></a>
<a name="line-248"></a> <span class='hs-comment'>-- this node colored ok, so do the rest</span>
<a name="line-249"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>graph'</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>assignColors'</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph'</span> <span class='hs-varid'>prob</span> <span class='hs-varid'>ks</span>
<a name="line-250"></a>
<a name="line-251"></a>
<a name="line-252"></a> <span class='hs-varid'>assignColor</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>u</span> <span class='hs-varid'>graph</span>
<a name="line-253"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>selectColor</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph</span> <span class='hs-varid'>u</span>
<a name="line-254"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>setColor</span> <span class='hs-varid'>u</span> <span class='hs-varid'>c</span> <span class='hs-varid'>graph</span><span class='hs-layout'>)</span>
<a name="line-255"></a>
<a name="line-256"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-257"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span>
<a name="line-258"></a>
<a name="line-259"></a>
<a name="line-260"></a>
<a name="line-261"></a><a name="selectColor"></a><span class='hs-comment'>-- | Select a color for a certain node</span>
<a name="line-262"></a><span class='hs-comment'>-- taking into account preferences, neighbors and exclusions.</span>
<a name="line-263"></a><span class='hs-comment'>-- returns Nothing if no color can be assigned to this node.</span>
<a name="line-264"></a><span class='hs-comment'>--</span>
<a name="line-265"></a><span class='hs-definition'>selectColor</span>
<a name="line-266"></a> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-conid'>Uniquable</span> <span class='hs-varid'>color</span>
<a name="line-267"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>color</span><span class='hs-layout'>,</span> <span class='hs-conid'>Outputable</span> <span class='hs-varid'>cls</span><span class='hs-layout'>)</span>
<a name="line-268"></a> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>UniqFM</span> <span class='hs-layout'>(</span><span class='hs-conid'>UniqSet</span> <span class='hs-varid'>color</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- ^ map of (node class -> set of colors available for this class).</span>
<a name="line-269"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Graph</span> <span class='hs-varid'>k</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>color</span> <span class='hs-comment'>-- ^ the graph</span>
<a name="line-270"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>k</span> <span class='hs-comment'>-- ^ key of the node to select a color for.</span>
<a name="line-271"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-varid'>color</span>
<a name="line-272"></a>
<a name="line-273"></a><span class='hs-definition'>selectColor</span> <span class='hs-varid'>colors</span> <span class='hs-varid'>graph</span> <span class='hs-varid'>u</span>
<a name="line-274"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-comment'>-- lookup the node</span>
<a name="line-275"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>node</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lookupNode</span> <span class='hs-varid'>graph</span> <span class='hs-varid'>u</span>
<a name="line-276"></a>
<a name="line-277"></a> <span class='hs-comment'>-- lookup the available colors for the class of this node.</span>
<a name="line-278"></a> <span class='hs-varid'>colors_avail</span>
<a name="line-279"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>colors</span> <span class='hs-layout'>(</span><span class='hs-varid'>nodeClass</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-280"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>pprPanic</span> <span class='hs-str'>"selectColor: no colors available for class "</span> <span class='hs-layout'>(</span><span class='hs-varid'>ppr</span> <span class='hs-layout'>(</span><span class='hs-varid'>nodeClass</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-281"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>cs</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>cs</span>
<a name="line-282"></a>
<a name="line-283"></a> <span class='hs-comment'>-- find colors we can't use because they're already being used</span>
<a name="line-284"></a> <span class='hs-comment'>-- by a node that conflicts with this one.</span>
<a name="line-285"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>nsConflicts</span>
<a name="line-286"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>sequence</span>
<a name="line-287"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-varid'>lookupNode</span> <span class='hs-varid'>graph</span><span class='hs-layout'>)</span>
<a name="line-288"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>uniqSetToList</span>
<a name="line-289"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>nodeConflicts</span> <span class='hs-varid'>node</span>
<a name="line-290"></a>
<a name="line-291"></a> <span class='hs-varid'>colors_conflict</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkUniqSet</span>
<a name="line-292"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>catMaybes</span>
<a name="line-293"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>nodeColor</span> <span class='hs-varid'>nsConflicts</span>
<a name="line-294"></a>
<a name="line-295"></a> <span class='hs-comment'>-- the prefs of our neighbors</span>
<a name="line-296"></a> <span class='hs-varid'>colors_neighbor_prefs</span>
<a name="line-297"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkUniqSet</span>
<a name="line-298"></a> <span class='hs-varop'>$</span> <span class='hs-varid'>concat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>nodePreference</span> <span class='hs-varid'>nsConflicts</span>
<a name="line-299"></a>
<a name="line-300"></a> <span class='hs-comment'>-- colors that are still valid for us</span>
<a name="line-301"></a> <span class='hs-varid'>colors_ok_ex</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>minusUniqSet</span> <span class='hs-varid'>colors_avail</span> <span class='hs-layout'>(</span><span class='hs-varid'>nodeExclusions</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span>
<a name="line-302"></a> <span class='hs-varid'>colors_ok</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>minusUniqSet</span> <span class='hs-varid'>colors_ok_ex</span> <span class='hs-varid'>colors_conflict</span>
<a name="line-303"></a>
<a name="line-304"></a> <span class='hs-comment'>-- the colors that we prefer, and are still ok</span>
<a name="line-305"></a> <span class='hs-varid'>colors_ok_pref</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>intersectUniqSets</span>
<a name="line-306"></a> <span class='hs-layout'>(</span><span class='hs-varid'>mkUniqSet</span> <span class='hs-varop'>$</span> <span class='hs-varid'>nodePreference</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span> <span class='hs-varid'>colors_ok</span>
<a name="line-307"></a>
<a name="line-308"></a> <span class='hs-comment'>-- the colors that we could choose while being nice to our neighbors</span>
<a name="line-309"></a> <span class='hs-varid'>colors_ok_nice</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>minusUniqSet</span>
<a name="line-310"></a> <span class='hs-varid'>colors_ok</span> <span class='hs-varid'>colors_neighbor_prefs</span>
<a name="line-311"></a>
<a name="line-312"></a> <span class='hs-comment'>-- the best of all possible worlds..</span>
<a name="line-313"></a> <span class='hs-varid'>colors_ok_pref_nice</span>
<a name="line-314"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>intersectUniqSets</span>
<a name="line-315"></a> <span class='hs-varid'>colors_ok_nice</span> <span class='hs-varid'>colors_ok_pref</span>
<a name="line-316"></a>
<a name="line-317"></a> <span class='hs-comment'>-- make the decision</span>
<a name="line-318"></a> <span class='hs-varid'>chooseColor</span>
<a name="line-319"></a>
<a name="line-320"></a> <span class='hs-comment'>-- everyone is happy, yay!</span>
<a name="line-321"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>not</span> <span class='hs-varop'>$</span> <span class='hs-varid'>isEmptyUniqSet</span> <span class='hs-varid'>colors_ok_pref_nice</span>
<a name="line-322"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>c</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>filter</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>elementOfUniqSet</span> <span class='hs-varid'>x</span> <span class='hs-varid'>colors_ok_pref_nice</span><span class='hs-layout'>)</span>
<a name="line-323"></a> <span class='hs-layout'>(</span><span class='hs-varid'>nodePreference</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span>
<a name="line-324"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>c</span>
<a name="line-325"></a>
<a name="line-326"></a> <span class='hs-comment'>-- we've got one of our preferences</span>
<a name="line-327"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>not</span> <span class='hs-varop'>$</span> <span class='hs-varid'>isEmptyUniqSet</span> <span class='hs-varid'>colors_ok_pref</span>
<a name="line-328"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>c</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>filter</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>elementOfUniqSet</span> <span class='hs-varid'>x</span> <span class='hs-varid'>colors_ok_pref</span><span class='hs-layout'>)</span>
<a name="line-329"></a> <span class='hs-layout'>(</span><span class='hs-varid'>nodePreference</span> <span class='hs-varid'>node</span><span class='hs-layout'>)</span>
<a name="line-330"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>c</span>
<a name="line-331"></a>
<a name="line-332"></a> <span class='hs-comment'>-- it wasn't a preference, but it was still ok</span>
<a name="line-333"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>not</span> <span class='hs-varop'>$</span> <span class='hs-varid'>isEmptyUniqSet</span> <span class='hs-varid'>colors_ok</span>
<a name="line-334"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>c</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>uniqSetToList</span> <span class='hs-varid'>colors_ok</span>
<a name="line-335"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>c</span>
<a name="line-336"></a>
<a name="line-337"></a> <span class='hs-comment'>-- no colors were available for us this time.</span>
<a name="line-338"></a> <span class='hs-comment'>-- looks like we're going around the loop again..</span>
<a name="line-339"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-340"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span>
<a name="line-341"></a>
<a name="line-342"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>chooseColor</span>
<a name="line-343"></a>
<a name="line-344"></a>
<a name="line-345"></a>
</pre></body>
</html>
