signature COLOR =
sig
  structure Frame : FRAME
  type allocation = Frame.register Temp.Table.table
  datatype moveAttr = COALESCED_MOVE | CONSTRAINED_MOVE | FROZEN_MOVE
                    | WORKLIST_MOVE | ACTIVE_MOVE
  val color : {interference: Liveness.igraph,
               initial: allocation,
               spillCost: Graph.node -> int,
               registers: Frame.register list,
               moveAttrTbl: moveAttr Graph.Table.table}
              -> allocation * Temp.temp list
end

structure Color (* :COLOR *)  =
struct
  structure Frame = Frame
  structure Table = Graph.Table
  structure Set = IntListSet
  structure Map = IntBinaryMap
  type allocation = Frame.register Temp.Table.table
  datatype igNodeAttr = 
           PRECOLORED | INITIAL | SIMPLIFYWORK 
         | FREEZEWORK | SPILLWORK | SPILLED | COALESCED 
         | COLORED | SELECTED
  datatype moveAttr = COALESCED_MOVE | CONSTRAINED_MOVE | FROZEN_MOVE
                    | WORKLIST_MOVE | ACTIVE_MOVE
  fun color {interference,initial,spillCost,registers,
             moveAttrTbl=moveAttrTblInitial} =
      let val allocTable = Temp.Table.empty (* Variable *)
          val spillList = nil               (* Variable *)
          val Liveness.IGRAPH{graph=iGraph, (* Fixed - Used once *)
                              gtemp=gtemp,  (* Fixed - Moderately used *)
                              moves=moves,  (* Fixed - Used in nodeMoves() *)
                              ...} = 
              interference 
          val igNodeList = Graph.nodes(iGraph) (* Fixed - Heaviliy used *)

          (* Making igNodeAttrTbl: Table for igNode attributes *)
          local fun initIgNodeAttrTbl(igNode,table) =
                    let val isPrecolored = 
                            Option.isSome(Table.look(initial,igNode))
                    in if isPrecolored = true 
                       then Table.enter(table,igNode,PRECOLORED)
                       else Table.enter(table,igNode,INITIAL)
                    end
          in 
          val igNodeAttrTblInitial = 
              foldl initIgNodeAttrTbl Table.empty igNodeList
          end

          fun getAdjacentTempsBase igNodeAttrTbl igNode = 
              let fun getTempsWithAttr(attr) = 
                      let fun hasAttr(igNode) =
                              (valOf(Graph.Table.look(igNodeAttrTbl,igNode)) 
                               = attr)
                      in List.map gtemp (List.filter hasAttr igNodeList)
                      end
                  fun makeNewSet(list) = Set.addList(Set.empty,list)
                  val adjIgNodes = Graph.adj(igNode)
                  val sTempsList = getTempsWithAttr(SELECTED)
                  val cTempsList = getTempsWithAttr(COALESCED)
                  val sTempsSet = makeNewSet(sTempsList)
                  val scTempsSet = Set.addList(sTempsSet,cTempsList)
                  val adjTempsSet = makeNewSet(List.map gtemp adjIgNodes)
              in Set.difference(adjTempsSet,scTempsSet)
              end
          fun degreeBase igNodeAttrTbl igNode = 
              Set.numItems(getAdjacentTempsBase igNodeAttrTbl igNode)

          fun moveRelatedBase moveAttrTbl igNode = 
              let fun nodeMoves(igNode) =
                      let val moveListN = valOf(Table.look(moves,igNode))
                          fun isActiveMovesOrWorkListMoves(moveNode) =
                              let val moveAttr = 
                                      valOf(Table.look(moveAttrTbl,moveNode))
                              in moveAttr = ACTIVE_MOVE orelse
                                 moveAttr = WORKLIST_MOVE
                              end
                      in List.filter isActiveMovesOrWorkListMoves moveListN 
                      end
              in length(nodeMoves(igNode)) <> 0
              end

          fun makeWorkList(moveAttrTbl,igNodeAttrTbl) = 
              let val igNodes = Graph.nodes(iGraph)
                  val numOfRegisters = length(Frame.registers)
                  val degree = degreeBase igNodeAttrTbl
                  val moveRelated = moveRelatedBase moveAttrTbl

                  fun setAttr(igNode,igNodeAttrTblOrig) = 
                      let val origAttr = 
                              valOf(Table.look(igNodeAttrTblOrig,igNode))
                      in case origAttr
                          of INITIAL =>
                             if degree(igNode) >= numOfRegisters
                             then Table.enter(igNodeAttrTblOrig,
                                              igNode,SPILLWORK)
                             else if moveRelated(igNode)
                             then Table.enter(igNodeAttrTblOrig,
                                              igNode,FREEZEWORK)
                             else Table.enter(igNodeAttrTblOrig,
                                              igNode,SIMPLIFYWORK)
                           | _ => igNodeAttrTblOrig
                      end
              in foldl setAttr igNodeAttrTbl igNodes
              end
          val igNodeAttrTbl = makeWorkList(moveAttrTblInitial,
                                           igNodeAttrTblInitial)
      in (allocTable, spillList)
      end
end