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 iNodeAttr = 
           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} =
      let val allocTable = Temp.Table.empty
          val spillList = nil
          val Liveness.IGRAPH{graph=iGraph, gtemp=gtemp,
                              moves=moves,...} = 
              interference
          val iNodeList = Graph.nodes(iGraph)
          val adjINodesListInitial = map Graph.adj iNodeList

          (* Making iNodeAttrTbl: Table for iNode attributes *)
          fun initINodeAttr(iNode,iNodeAttrTbl) =
              let val isPrecolored = Option.isSome(Table.look(initial,iNode))
              in if isPrecolored = true 
                 then Table.enter(iNodeAttrTbl,iNode,PRECOLORED)
                 else Table.enter(iNodeAttrTbl,iNode,INITIAL)
              end
          val iNodeList = Graph.nodes(iGraph)
          val iNodeAttrTblInitial = foldl initINodeAttr Table.empty iNodeList

          fun getTempsWithAttr(iNodeAttrTbl,attr) = 
              let fun hasAttr(iNode) =
                      valOf(Graph.Table.look(iNodeAttrTbl,iNode)) = attr
              in List.map gtemp (List.filter hasAttr iNodeList)
              end

          fun adjacentTemps(adjINodesList,iNodeAttrTbl,iNode) = 
              let fun makeNewSet(list) = Set.addList(Set.empty,list)
                  val sTempsList = getTempsWithAttr(iNodeAttrTbl,SELECTED)
                  val cTempsList = getTempsWithAttr(iNodeAttrTbl,COALESCED)
                  val sTempsSet = makeNewSet(sTempsList)
                  val scTempsSet = Set.addList(sTempsSet,cTempsList)
                  val adjTempsSet = makeNewSet(List.map gtemp adjINodesList)
              in Set.difference(adjTempsSet,scTempsSet)
              end
          fun degree(adjacentTemps) = Set.numItems(adjacentTemps)

          val moveNodesList = List.map (fn (key,_) => key) 
                                       (Map.listItemsi(moveAttrTbl))

          fun nodeMoves(node) =
              let val moveListN = valOf(Table.look(moves,node))
                  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 (allocTable, spillList)
      end
end