/* Ċ Ġ* ĠCopyright Ġ( c ) Ġ 2 0 1 2 - 2 0 1 7 ĠThe ĠAN TLR ĠProject . ĠAll Ġrights Ġreserved . Ċ Ġ* ĠUse Ġof Ġthis Ġfile Ġis Ġgoverned Ġby Ġthe ĠBSD Ġ 3 - clause Ġlicense Ġthat Ċ Ġ* Ġcan Ġbe Ġfound Ġin Ġthe ĠLICENSE . txt Ġfile Ġin Ġthe Ġproject Ġroot . Ċ Ġ*/ Ċ Ċ package Ġorg . antlr . v 4 . kotlin runtime . at n Ċ Ċ import Ġcom . strument a . kotlin multi platform . Bit Set Ċ import Ġorg . antlr . v 4 . kotlin runtime . misc . Abstract Equality Comparator Ċ import Ġorg . antlr . v 4 . kotlin runtime . misc . Flex ible HashMap Ċ import Ġorg . antlr . v 4 . kotlin runtime . misc . M urm ur Hash Ċ Ċ /** Ċ Ġ* ĠThis Ġenumeration Ġdefines Ġthe Ġprediction Ġmodes Ġavailable Ġin ĠAN TLR Ġ 4 Ġalong Ġwith Ċ Ġ* Ġutility Ġmethods Ġfor Ġanaly zing Ġconfiguration Ġsets Ġfor Ġconflicts Ġand / or Ċ Ġ* Ġamb igu ities . Ċ Ġ*/ Ċ enum Ġclass ĠPrediction Mode Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe ĠS LL (*) Ġprediction Ġmode . ĠThis Ġprediction Ġmode Ġignores Ġthe Ġcurrent ĊĠĠĠĠ Ġ* Ġparser Ġcontext Ġwhen Ġmaking Ġpredictions . ĠThis Ġis Ġthe Ġfast est Ġprediction ĊĠĠĠĠ Ġ* Ġmode , Ġand Ġprovides Ġcorrect Ġresults Ġfor Ġmany Ġgrammar s . ĠThis Ġprediction ĊĠĠĠĠ Ġ* Ġmode Ġis Ġmore Ġpowerful Ġthan Ġthe Ġprediction Ġmode Ġprovided Ġby ĠAN TLR Ġ 3 , Ġbut ĊĠĠĠĠ Ġ* Ġmay Ġresult Ġin Ġsyntax Ġerrors Ġfor Ġgrammar Ġand Ġinput Ġcombinations Ġwhich Ġare ĊĠĠĠĠ Ġ* Ġnot ĠS LL . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠWhen Ġusing Ġthis Ġprediction Ġmode , Ġthe Ġparser Ġwill Ġeither Ġreturn Ġa Ġcorrect ĊĠĠĠĠ Ġ* Ġparse Ġtree Ġ( i . e . Ġthe Ġsame Ġparse Ġtree Ġthat Ġwould Ġbe Ġreturned Ġwith Ġthe ĊĠĠĠĠ Ġ* Ġ[. LL ] Ġprediction Ġmode ), Ġor Ġit Ġwill Ġreport Ġa Ġsyntax Ġerror . ĠIf Ġa ĊĠĠĠĠ Ġ* Ġsyntax Ġerror Ġis Ġencountered Ġwhen Ġusing Ġthe Ġ[. S LL ] Ġprediction Ġmode , ĊĠĠĠĠ Ġ* Ġit Ġmay Ġbe Ġdue Ġto Ġeither Ġan Ġactual Ġsyntax Ġerror Ġin Ġthe Ġinput Ġor Ġindicate ĊĠĠĠĠ Ġ* Ġthat Ġthe Ġparticular Ġcombination Ġof Ġgrammar Ġand Ġinput Ġrequires Ġthe Ġmore ĊĠĠĠĠ Ġ* Ġpowerful Ġ[. LL ] Ġprediction Ġabilities Ġto Ġcomplete Ġsuccessfully . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġprediction Ġmode Ġdoes Ġnot Ġprovide Ġany Ġguarantees Ġfor Ġprediction ĊĠĠĠĠ Ġ* Ġbehavior Ġfor Ġsynt act ically - incorrect Ġinputs . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ ĠS LL , ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe ĠLL (*) Ġprediction Ġmode . ĠThis Ġprediction Ġmode Ġallows Ġthe Ġcurrent Ġparser ĊĠĠĠĠ Ġ* Ġcontext Ġto Ġbe Ġused Ġfor Ġresolving ĠS LL Ġconflicts Ġthat Ġoccur Ġduring ĊĠĠĠĠ Ġ* Ġprediction . ĠThis Ġis Ġthe Ġfast est Ġprediction Ġmode Ġthat Ġguarantees Ġcorrect ĊĠĠĠĠ Ġ* Ġparse Ġresults Ġfor Ġall Ġcombinations Ġof Ġgrammar s Ġwith Ġsynt act ically Ġcorrect ĊĠĠĠĠ Ġ* Ġinputs . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠWhen Ġusing Ġthis Ġprediction Ġmode , Ġthe Ġparser Ġwill Ġmake Ġcorrect Ġdecisions ĊĠĠĠĠ Ġ* Ġfor Ġall Ġsynt act ically - correct Ġgrammar Ġand Ġinput Ġcombinations . ĠHowever , Ġin ĊĠĠĠĠ Ġ* Ġcases Ġwhere Ġthe Ġgrammar Ġis Ġtruly Ġambiguous Ġthis Ġprediction Ġmode Ġmight Ġnot ĊĠĠĠĠ Ġ* Ġreport Ġa Ġprecise Ġanswer Ġfor Ġ* exact ly Ġwhich * Ġalternatives Ġare ĊĠĠĠĠ Ġ* Ġambiguous . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġprediction Ġmode Ġdoes Ġnot Ġprovide Ġany Ġguarantees Ġfor Ġprediction ĊĠĠĠĠ Ġ* Ġbehavior Ġfor Ġsynt act ically - incorrect Ġinputs . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ ĠLL , ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe ĠLL (*) Ġprediction Ġmode Ġwith Ġexact Ġamb iguity Ġdetection . ĠIn Ġaddition Ġto ĊĠĠĠĠ Ġ* Ġthe Ġcorrect ness Ġguarantees Ġprovided Ġby Ġthe Ġ[. LL ] Ġprediction Ġmode , ĊĠĠĠĠ Ġ* Ġthis Ġprediction Ġmode Ġin structs Ġthe Ġprediction Ġalgorithm Ġto Ġdetermine Ġthe ĊĠĠĠĠ Ġ* Ġcomplete Ġand Ġexact Ġset Ġof Ġambiguous Ġalternatives Ġfor Ġevery Ġambiguous ĊĠĠĠĠ Ġ* Ġdecision Ġencountered Ġwhile Ġparsing . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġprediction Ġmode Ġmay Ġbe Ġused Ġfor Ġdi agn osing Ġamb igu ities Ġduring ĊĠĠĠĠ Ġ* Ġgrammar Ġdevelopment . ĠDue Ġto Ġthe Ġperformance Ġoverhead Ġof Ġcalculating Ġsets ĊĠĠĠĠ Ġ* Ġof Ġambiguous Ġalternatives , Ġthis Ġprediction Ġmode Ġshould Ġbe Ġa vo ided Ġwhen ĊĠĠĠĠ Ġ* Ġthe Ġexact Ġresults Ġare Ġnot Ġnecessary . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġprediction Ġmode Ġdoes Ġnot Ġprovide Ġany Ġguarantees Ġfor Ġprediction ĊĠĠĠĠ Ġ* Ġbehavior Ġfor Ġsynt act ically - incorrect Ġinputs . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ ĠLL _ EX ACT _ AM BIG _ DE TE CTION ; ĊĊĠĠĠ Ġ/** ĠA ĠMap Ġthat Ġuses Ġjust Ġthe Ġstate Ġand Ġthe Ġstack Ġcontext Ġas Ġthe Ġkey . Ġ Ġ*/ ĊĠĠĠ Ġinternal Ġclass ĠAlt And Context Map Ġ: ĠFlex ible HashMap < AT N Config , ĠBit Set >( Alt And Context Config Equality Comparator . INSTANCE ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠTODO Ġdecor ate ? ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġclass ĠAlt And Context Config Equality Comparator Ġprivate Ġconstructor () Ġ: ĠAbstract Equality Comparator < AT N Config >() Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġhash Ġcode Ġis Ġonly Ġa Ġfunction Ġof Ġthe Ġ[ AT N State . state Number ] ĊĠĠĠĠĠĠĠĠ Ġ* Ġand Ġ[ AT N Config . context ]. ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠhashCode ( o : ĠAT N Config ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar ĠhashCode Ġ= ĠM urm ur Hash . initialize ( 7 ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠhashCode Ġ= ĠM urm ur Hash . update ( hashCode , Ġo . state . state Number ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠhashCode Ġ= ĠM urm ur Hash . update ( hashCode , Ġo . context ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠhashCode Ġ= ĠM urm ur Hash . finish ( hashCode , Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠhashCode ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġequals ( a : ĠAT N Config ?, Ġb : ĠAT N Config ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( a Ġ=== Ġb ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( a Ġ== Ġnull Ġ|| Ġb Ġ== Ġnull ) Ġfalse Ġelse Ġa !!. state . state Number Ġ== Ġb !!. state . state Number Ġ&& Ġa !!. context Ġ== Ġb !!. context ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠINSTANCE Ġ= ĠAlt And Context Config Equality Comparator () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠComputes Ġthe ĠS LL Ġprediction Ġtermination Ġcondition . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThis Ġmethod Ġcomputes Ġthe ĠS LL Ġprediction Ġtermination Ġcondition Ġfor Ġboth Ġof ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġfollowing Ġcases . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* ĠThe Ġusual ĠS LL + LL Ġfallback Ġupon ĠS LL Ġconflict ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* ĠPure ĠS LL Ġwithout ĠLL Ġfallback ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** COMB IN ED ĠS LL + LL ĠPAR SING ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠWhen ĠLL - fallback Ġis Ġenabled Ġupon ĠS LL Ġconflict , Ġcorrect Ġpredictions Ġare ĊĠĠĠĠĠĠĠĠ Ġ* Ġens ured Ġregardless Ġof Ġhow Ġthe Ġtermination Ġcondition Ġis Ġcomputed Ġby Ġthis ĊĠĠĠĠĠĠĠĠ Ġ* Ġmethod . ĠDue Ġto Ġthe Ġsubstant ially Ġhigher Ġcost Ġof ĠLL Ġprediction , Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġprediction Ġshould Ġonly Ġfall Ġback Ġto ĠLL Ġwhen Ġthe Ġadditional Ġlook ahead ĊĠĠĠĠĠĠĠĠ Ġ* Ġcannot Ġlead Ġto Ġa Ġunique ĠS LL Ġprediction . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠAss uming Ġcombined ĠS LL + LL Ġparsing , Ġan ĠS LL Ġconfiguration Ġset Ġwith Ġonly ĊĠĠĠĠĠĠĠĠ Ġ* Ġconflicting Ġsub sets Ġshould Ġfall Ġback Ġto Ġfull ĠLL , Ġeven Ġif Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġconfiguration Ġsets Ġdon 't Ġresolve Ġto Ġthe Ġsame Ġalternative Ġ( e . g . ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 1 , 2 }` Ġand Ġ`{ 3 , 4 }`. ĠIf Ġthere Ġis Ġat Ġleast Ġone Ġnon - conflict ing ĊĠĠĠĠĠĠĠĠ Ġ* Ġconfiguration , ĠS LL Ġcould Ġcontinue Ġwith Ġthe Ġhop es Ġthat Ġmore Ġlook ahead Ġwill ĊĠĠĠĠĠĠĠĠ Ġ* Ġresolve Ġvia Ġone Ġof Ġthose Ġnon - conflict ing Ġconfigurations . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠHere 's Ġthe Ġprediction Ġtermination Ġrule Ġthem : ĠS LL Ġ( for ĠS LL + LL Ġparsing ) ĊĠĠĠĠĠĠĠĠ Ġ* Ġstops Ġwhen Ġit Ġsees Ġonly Ġconflicting Ġconfiguration Ġsub sets . ĠIn Ġcontrast , ĊĠĠĠĠĠĠĠĠ Ġ* Ġfull ĠLL Ġkeeps Ġgoing Ġwhen Ġthere Ġis Ġuncertainty . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** HE UR ISTIC ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠAs Ġa Ġhe uristic , Ġwe Ġstop Ġprediction Ġwhen Ġwe Ġsee Ġany Ġconflicting Ġsubset ĊĠĠĠĠĠĠĠĠ Ġ* Ġunless Ġwe Ġsee Ġa Ġstate Ġthat Ġonly Ġhas Ġone Ġalternative Ġassociated Ġwith Ġit . ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġsingle - alt - state Ġthing Ġlets Ġprediction Ġcontinue Ġupon Ġrules Ġlike ĊĠĠĠĠĠĠĠĠ Ġ* Ġ( otherwise , Ġit Ġwould Ġadmit Ġdef eat Ġtoo Ġsoon ): ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`[ 1 2 | 1 | [], Ġ 6 | 2 | [], Ġ 1 2 | 2 | [] ]. Ġs Ġ: Ġ( ID Ġ| ĠID ĠID ?) Ġ';' Ġ; ` ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠWhen Ġthe ĠAT N Ġsimulation Ġreaches Ġthe Ġstate Ġbefore Ġ` '; ' `, Ġit Ġhas Ġa ĊĠĠĠĠĠĠĠĠ Ġ* ĠD FA Ġstate Ġthat Ġlooks Ġlike : Ġ`[ 1 2 | 1 | [], Ġ 6 | 2 | [], Ġ 1 2 | 2 | [] ] `. ĠN atur ally ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` 1 2 | 1 | [] ` Ġand Ġ` 1 2 | 2 | [] ` Ġconflict , Ġbut Ġwe Ġcannot Ġstop ĊĠĠĠĠĠĠĠĠ Ġ* Ġprocessing Ġthis Ġnode Ġbecause Ġalternative Ġto Ġhas Ġanother Ġway Ġto Ġcontinue , ĊĠĠĠĠĠĠĠĠ Ġ* Ġvia Ġ`[ 6 | 2 | [] ] `. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠIt Ġalso Ġlet 's Ġus Ġcontinue Ġfor Ġthis Ġrule : ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`[ 1 | 1 | [], Ġ 1 | 2 | [], Ġ 8 | 3 | [] ] Ġa Ġ: ĠA Ġ| ĠA Ġ| ĠA ĠB Ġ; ` ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠAfter Ġmatching Ġinput ĠA , Ġwe Ġreach Ġthe Ġstop Ġstate Ġfor Ġrule ĠA , Ġstate Ġ 1 . ĊĠĠĠĠĠĠĠĠ Ġ* ĠState Ġ 8 Ġis Ġthe Ġstate Ġright Ġbefore ĠB . ĠClear ly Ġalternatives Ġ 1 Ġand Ġ 2 ĊĠĠĠĠĠĠĠĠ Ġ* Ġconflict Ġand Ġno Ġamount Ġof Ġfurther Ġlook ahead Ġwill Ġseparate Ġthe Ġtwo . ĊĠĠĠĠĠĠĠĠ Ġ* ĠHowever , Ġalternative Ġ 3 Ġwill Ġbe Ġable Ġto Ġcontinue Ġand Ġso Ġwe Ġdo Ġnot Ġstop ĊĠĠĠĠĠĠĠĠ Ġ* Ġworking Ġon Ġthis Ġstate . ĠIn Ġthe Ġprevious Ġexample , Ġwe 're Ġconcerned Ġwith ĊĠĠĠĠĠĠĠĠ Ġ* Ġstates Ġassociated Ġwith Ġthe Ġconflicting Ġalternatives . ĠHere Ġalt Ġ 3 Ġis Ġnot ĊĠĠĠĠĠĠĠĠ Ġ* Ġassociated Ġwith Ġthe Ġconflicting Ġconfigs , Ġbut Ġsince Ġwe Ġcan Ġcontinue ĊĠĠĠĠĠĠĠĠ Ġ* Ġlooking Ġfor Ġinput Ġreason ably , Ġdon 't Ġdeclare Ġthe Ġstate Ġdone . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** PURE ĠS LL ĠPAR SING ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠTo Ġhandle Ġpure ĠS LL Ġparsing , Ġall Ġwe Ġhave Ġto Ġdo Ġis Ġmake Ġsure Ġthat Ġwe ĊĠĠĠĠĠĠĠĠ Ġ* Ġcombine Ġstack Ġcontexts Ġfor Ġconfigurations Ġthat Ġdiffer Ġonly Ġby Ġsemantic ĊĠĠĠĠĠĠĠĠ Ġ* Ġpredicate . ĠFrom Ġthere , Ġwe Ġcan Ġdo Ġthe Ġusual ĠS LL Ġtermination Ġhe uristic . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** PRE D IC ATES ĠIN ĠS LL + LL ĠPAR SING ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠS LL Ġdecisions Ġdon 't Ġevaluate Ġpredicates Ġuntil Ġafter Ġthey Ġreach ĠD FA Ġstop ĊĠĠĠĠĠĠĠĠ Ġ* Ġstates Ġbecause Ġthey Ġneed Ġto Ġcreate Ġthe ĠD FA Ġcache Ġthat Ġworks Ġin Ġall ĊĠĠĠĠĠĠĠĠ Ġ* Ġsemantic Ġsituations . ĠIn Ġcontrast , Ġfull ĠLL Ġevaluates Ġpredicates Ġcollected ĊĠĠĠĠĠĠĠĠ Ġ* Ġduring Ġstart Ġstate Ġcomputation Ġso Ġit Ġcan Ġignore Ġpredicates Ġthere after . ĊĠĠĠĠĠĠĠĠ Ġ* ĠThis Ġmeans Ġthat ĠS LL Ġtermination Ġdetection Ġcan Ġtotally Ġignore Ġsemantic ĊĠĠĠĠĠĠĠĠ Ġ* Ġpredicates . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠImplementation - wise , Ġ[ AT N Config Set ] Ġcombin es Ġstack Ġcontexts Ġbut Ġnot ĊĠĠĠĠĠĠĠĠ Ġ* Ġsemantic Ġpredicate Ġcontexts Ġso Ġwe Ġmight Ġsee Ġtwo Ġconfigurations Ġlike Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġfollowing . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s , Ġ 1 , Ġx , Ġ{}), Ġ( s , Ġ 1 , Ġx ', Ġ{ p }) ` ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠBefore Ġtesting Ġthese Ġconfigurations Ġagainst Ġothers , Ġwe Ġhave Ġto Ġmerge ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` x ` Ġand Ġ` x '` Ġ( without Ġmodifying Ġthe Ġexisting Ġconfigurations ). ĊĠĠĠĠĠĠĠĠ Ġ* ĠFor Ġexample , Ġwe Ġtest Ġ`( x + x ') == x '' ` Ġwhen Ġlooking Ġfor Ġconflicts Ġin ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġfollowing Ġconfigurations . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s , Ġ 1 , Ġx , Ġ{}), Ġ( s , Ġ 1 , Ġx ', Ġ{ p }), Ġ( s , Ġ 2 , Ġx '', Ġ{}) ` ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠIf Ġthe Ġconfiguration Ġset Ġhas Ġpredicates Ġ( as Ġindicated Ġby ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ AT N Config Set . has Semantic Context ]), Ġthis Ġalgorithm Ġmakes Ġa Ġcopy Ġof ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġconfigurations Ġto Ġstrip Ġout Ġall Ġof Ġthe Ġpredicates Ġso Ġthat Ġa Ġstandard ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ AT N Config Set ] Ġwill Ġmerge Ġeverything Ġignoring Ġpredicates . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġhas S LL Conflict Termin ating Prediction ( mode : ĠPrediction Mode , Ġconfigs : ĠAT N Config Set ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġconfigs Ġ= Ġconfigs ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠConfig s Ġin Ġrule Ġstop Ġstates Ġindicate Ġre aching Ġthe Ġend Ġof Ġthe Ġdecision Ċĉĉ Ġ* Ġrule Ġ( local Ġcontext ) Ġor Ġend Ġof Ġstart Ġrule Ġ( full Ġcontext ). ĠIf Ġall Ċĉĉ Ġ* Ġconfigs Ġmeet Ġthis Ġcondition , Ġthen Ġnone Ġof Ġthe Ġconfigurations Ġis Ġable Ċĉĉ Ġ* Ġto Ġmatch Ġadditional Ġinput Ġso Ġwe Ġterminate Ġprediction . Ċĉĉ Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( all Configs In Rule Stop States ( configs )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġpure ĠS LL Ġmode Ġparsing ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( mode Ġ== ĠPrediction Mode . S LL ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠDon 't Ġbother Ġwith Ġcombining Ġconfigs Ġfrom Ġdifferent Ġsemantic ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcontexts Ġif Ġwe Ġcan Ġfail Ġover Ġto Ġfull ĠLL ; Ġcosts Ġmore Ġtime ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsince Ġwe 'll Ġoften Ġfail Ġover Ġanyway . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( configs . has Semantic Context ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġdup Ġconfigs , Ġto ss ing Ġout Ġsemantic Ġpredicates ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdup Ġ= ĠAT N Config Set () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( c Ġin Ġconfigs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmutable C Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmutable C Ġ= ĠAT N Config ( mutable C , ĠSemantic Context . NONE ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdup . add ( mutable C ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġconfigs Ġ= Ġdup ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnow Ġwe Ġhave Ġcombined Ġcontexts Ġfor Ġconfigs Ġwith Ġdis similar Ġpreds ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġpure ĠS LL Ġor Ġcombined ĠS LL + LL Ġmode Ġparsing ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġalt sets Ġ= Ġget Conflict ing Alt Sub sets ( configs ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġhas Conflict ing Alt Set ( alt sets ) Ġ&& Ġ! has State Associated With One Alt ( configs ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠChecks Ġif Ġany Ġconfiguration Ġin Ġ` configs ` Ġis Ġin Ġa ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ Rule Stop State ]. ĠConfigur ations Ġmeeting Ġthis Ġcondition Ġhave Ġreached ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġend Ġof Ġthe Ġdecision Ġrule Ġ( local Ġcontext ) Ġor Ġend Ġof Ġstart Ġrule Ġ( full ĊĠĠĠĠĠĠĠĠ Ġ* Ġcontext ). ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġconfigs Ġthe Ġconfiguration Ġset Ġto Ġtest ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return Ġ` true ` Ġif Ġany Ġconfiguration Ġin Ġ` configs ` Ġis Ġin Ġa ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ Rule Stop State ], Ġotherwise Ġ` false ` ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġhas Config In Rule Stop State ( configs : ĠAT N Config Set ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( c Ġin Ġconfigs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( c . state Ġis ĠRule Stop State ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠChecks Ġif Ġall Ġconfigurations Ġin Ġ` configs ` Ġare Ġin Ġa ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ Rule Stop State ]. ĠConfigur ations Ġmeeting Ġthis Ġcondition Ġhave Ġreached ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġend Ġof Ġthe Ġdecision Ġrule Ġ( local Ġcontext ) Ġor Ġend Ġof Ġstart Ġrule Ġ( full ĊĠĠĠĠĠĠĠĠ Ġ* Ġcontext ). ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġconfigs Ġthe Ġconfiguration Ġset Ġto Ġtest ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return Ġ` true ` Ġif Ġall Ġconfigurations Ġin Ġ` configs ` Ġare Ġin Ġa ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ Rule Stop State ], Ġotherwise Ġ` false ` ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġall Configs In Rule Stop States ( configs : ĠAT N Config Set ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( config Ġin Ġconfigs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( config . state Ġ! is ĠRule Stop State ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠFull ĠLL Ġprediction Ġtermination . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠCan Ġwe Ġstop Ġlooking Ġahead Ġduring ĠAT N Ġsimulation Ġor Ġis Ġthere Ġsome ĊĠĠĠĠĠĠĠĠ Ġ* Ġuncertainty Ġas Ġto Ġwhich Ġalternative Ġwe Ġwill Ġultimately Ġpick , Ġafter ĊĠĠĠĠĠĠĠĠ Ġ* Ġconsuming Ġmore Ġinput ? ĠEven Ġif Ġthere Ġare Ġpartial Ġconflicts , Ġwe Ġmight Ġknow ĊĠĠĠĠĠĠĠĠ Ġ* Ġthat Ġeverything Ġis Ġgoing Ġto Ġresolve Ġto Ġthe Ġsame Ġminimum Ġalternative . ĠThat ĊĠĠĠĠĠĠĠĠ Ġ* Ġmeans Ġwe Ġcan Ġstop Ġsince Ġno Ġmore Ġlook ahead Ġwill Ġchange Ġthat Ġfact . ĠOn Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġother Ġhand , Ġthere Ġmight Ġbe Ġmultiple Ġconflicts Ġthat Ġresolve Ġto Ġdifferent ĊĠĠĠĠĠĠĠĠ Ġ* Ġminimum s . ĠThat Ġmeans Ġwe Ġneed Ġmore Ġlook Ġahead Ġto Ġdecide Ġwhich Ġof Ġthose ĊĠĠĠĠĠĠĠĠ Ġ* Ġalternatives Ġwe Ġshould Ġpredict . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġbasic Ġidea Ġis Ġto Ġsplit Ġthe Ġset Ġof Ġconfigurations Ġ` C `, Ġinto ĊĠĠĠĠĠĠĠĠ Ġ* Ġconflicting Ġsub sets Ġ`( s , Ġ_, Ġctx , Ġ_ )` Ġand Ġsingleton Ġsub sets Ġwith ĊĠĠĠĠĠĠĠĠ Ġ* Ġnon - conflict ing Ġconfigurations . ĠTwo Ġconfigurations Ġconflict Ġif Ġthey Ġhave ĊĠĠĠĠĠĠĠĠ Ġ* Ġidentical Ġ[ AT N Config . state ] Ġand Ġ[ AT N Config . context ] Ġvalues ĊĠĠĠĠĠĠĠĠ Ġ* Ġbut Ġdifferent Ġ[ AT N Config . alt ] Ġvalue , Ġe . g . Ġ`( s , Ġi , Ġctx , Ġ_ )` ĊĠĠĠĠĠĠĠĠ Ġ* Ġand Ġ`( s , Ġj , Ġctx , Ġ_ )` Ġfor Ġ` i != j `. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠReduce Ġthese Ġconfiguration Ġsub sets Ġto Ġthe Ġset Ġof Ġpossible Ġalternatives . ĊĠĠĠĠĠĠĠĠ Ġ* ĠYou Ġcan Ġcompute Ġthe Ġalternative Ġsub sets Ġin Ġone Ġpass Ġas Ġfollows : ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` A _ s , ctx Ġ= Ġ{ i Ġ| Ġ( s , Ġi , Ġctx , Ġ_ )} ` Ġfor Ġeach Ġconfiguration Ġin ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` C ` Ġholding Ġ` s ` Ġand Ġ` ctx ` Ġfixed . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠOr Ġin Ġpseudo - code , Ġfor Ġeach Ġconfiguration Ġ` c ` Ġin Ġ` C `: ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ< pre > ĊĠĠĠĠĠĠĠĠ Ġ* Ġmap [ c ] ĠU = Ġc .[ alt ][ AT N Config . alt ] Ġ# Ġmap Ġhash / equals Ġuses Ġs Ġand Ġx , Ġnot ĊĠĠĠĠĠĠĠĠ Ġ* Ġalt Ġand Ġnot Ġpred ĊĠĠĠĠĠĠĠ Ġ</ pre > Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġvalues Ġin Ġ` map ` Ġare Ġthe Ġset Ġof Ġ` A _ s , ctx ` Ġsets . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠIf Ġ` | A _ s , ctx |= 1 ` Ġthen Ġthere Ġis Ġno Ġconflict Ġassociated Ġwith ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` s ` Ġand Ġ` ctx `. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠReduce Ġthe Ġsub sets Ġto Ġsing letons Ġby Ġchoosing Ġa Ġminimum Ġof Ġeach Ġsubset . ĠIf ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġunion Ġof Ġthese Ġalternative Ġsub sets Ġis Ġa Ġsingleton , Ġthen Ġno Ġamount Ġof ĊĠĠĠĠĠĠĠĠ Ġ* Ġmore Ġlook ahead Ġwill Ġhelp Ġus . ĠWe Ġwill Ġalways Ġpick Ġthat Ġalternative . ĠIf , ĊĠĠĠĠĠĠĠĠ Ġ* Ġhowever , Ġthere Ġis Ġmore Ġthan Ġone Ġalternative , Ġthen Ġwe Ġare Ġuncert ain Ġwhich ĊĠĠĠĠĠĠĠĠ Ġ* Ġalternative Ġto Ġpredict Ġand Ġmust Ġcontinue Ġlooking Ġfor Ġresolution . ĠWe Ġmay ĊĠĠĠĠĠĠĠĠ Ġ* Ġor Ġmay Ġnot Ġdiscover Ġan Ġamb iguity Ġin Ġthe Ġfuture , Ġeven Ġif Ġthere Ġare Ġno ĊĠĠĠĠĠĠĠĠ Ġ* Ġconflicting Ġsub sets Ġthis Ġround . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġbiggest Ġsin Ġis Ġto Ġterminate Ġearly Ġbecause Ġit Ġmeans Ġwe 've Ġmade Ġa ĊĠĠĠĠĠĠĠĠ Ġ* Ġdecision Ġbut Ġwere Ġuncert ain Ġas Ġto Ġthe Ġevent ual Ġoutcome . ĠWe Ġhaven 't Ġused ĊĠĠĠĠĠĠĠĠ Ġ* Ġenough Ġlook ahead . ĠOn Ġthe Ġother Ġhand , Ġanno unc ing Ġa Ġconflict Ġtoo Ġlate Ġis Ġno ĊĠĠĠĠĠĠĠĠ Ġ* Ġbig Ġdeal ; Ġyou Ġwill Ġstill Ġhave Ġthe Ġconflict . ĠIt 's Ġjust Ġin efficient . ĠIt ĊĠĠĠĠĠĠĠĠ Ġ* Ġmight Ġeven Ġlook Ġuntil Ġthe Ġend Ġof Ġfile . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠNo Ġspecial Ġconsideration Ġfor Ġsemantic Ġpredicates Ġis Ġrequired Ġbecause ĊĠĠĠĠĠĠĠĠ Ġ* Ġpredicates Ġare Ġevaluated Ġon - the - fly Ġfor Ġfull ĠLL Ġprediction , Ġensuring Ġthat ĊĠĠĠĠĠĠĠĠ Ġ* Ġno Ġconfiguration Ġcontains Ġa Ġsemantic Ġcontext Ġduring Ġthe Ġtermination ĊĠĠĠĠĠĠĠĠ Ġ* Ġcheck . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** CONF LI CT ING ĠCONFIG S ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠTwo Ġconfigurations Ġ`( s , Ġi , Ġx )` Ġand Ġ`( s , Ġj , Ġx ') `, Ġconflict ĊĠĠĠĠĠĠĠĠ Ġ* Ġwhen Ġ` i != j ` Ġbut Ġ` x = x ' `. ĠBecause Ġwe Ġmerge Ġall ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s , Ġi , Ġ_ )` Ġconfigurations Ġtogether , Ġthat Ġmeans Ġthat Ġthere Ġare Ġat ĊĠĠĠĠĠĠĠĠ Ġ* Ġmost Ġ` n ` Ġconfigurations Ġassociated Ġwith Ġstate Ġ` s ` Ġfor ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` n ` Ġpossible Ġalternatives Ġin Ġthe Ġdecision . ĠThe Ġmerged Ġstacks ĊĠĠĠĠĠĠĠĠ Ġ* Ġcomp lic ate Ġthe Ġcomparison Ġof Ġconfiguration Ġcontexts Ġ` x ` Ġand ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` x ' `. ĠSam Ġchecks Ġto Ġsee Ġif Ġone Ġis Ġa Ġsubset Ġof Ġthe Ġother Ġby Ġcalling ĊĠĠĠĠĠĠĠĠ Ġ* Ġmerge Ġand Ġchecking Ġto Ġsee Ġif Ġthe Ġmerged Ġresult Ġis Ġeither Ġ` x ` Ġor ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` x ' `. ĠIf Ġthe Ġ` x ` Ġassociated Ġwith Ġlowest Ġalternative Ġ` i ` ĊĠĠĠĠĠĠĠĠ Ġ* Ġis Ġthe Ġsuper set , Ġthen Ġ` i ` Ġis Ġthe Ġonly Ġpossible Ġprediction Ġsince Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġothers Ġresolve Ġto Ġ` min ( i )` Ġas Ġwell . ĠHowever , Ġif Ġ` x ` Ġis ĊĠĠĠĠĠĠĠĠ Ġ* Ġassociated Ġwith Ġ` j > i ` Ġthen Ġat Ġleast Ġone Ġstack Ġconfiguration Ġfor ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` j ` Ġis Ġnot Ġin Ġconflict Ġwith Ġalternative Ġ` i `. ĠThe Ġalgorithm ĊĠĠĠĠĠĠĠĠ Ġ* Ġshould Ġkeep Ġgoing , Ġlooking Ġfor Ġmore Ġlook ahead Ġdue Ġto Ġthe Ġuncertainty . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠFor Ġsimplicity , ĠI 'm Ġdoing Ġa Ġequality Ġcheck Ġbetween Ġ` x ` Ġand ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` x '` Ġthat Ġlets Ġthe Ġalgorithm Ġcontinue Ġto Ġconsume Ġlook ahead Ġlonger ĊĠĠĠĠĠĠĠĠ Ġ* Ġthan Ġnecessary . ĠThe Ġreason ĠI Ġlike Ġthe Ġequality Ġis Ġof Ġcourse Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġsimplicity Ġbut Ġalso Ġbecause Ġthat Ġis Ġthe Ġtest Ġyou Ġneed Ġto Ġdetect Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġalternatives Ġthat Ġare Ġactually Ġin Ġconflict . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** CONTINUE / STOP ĠRULE ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠContinue Ġif Ġunion Ġof Ġresolved Ġalternative Ġsets Ġfrom Ġnon - conflict ing Ġand ĊĠĠĠĠĠĠĠĠ Ġ* Ġconflicting Ġalternative Ġsub sets Ġhas Ġmore Ġthan Ġone Ġalternative . ĠWe Ġare ĊĠĠĠĠĠĠĠĠ Ġ* Ġuncert ain Ġabout Ġwhich Ġalternative Ġto Ġpredict . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġcomplete Ġset Ġof Ġalternatives , Ġ`[ i Ġfor Ġ(_, i ,_ )] `, Ġtells Ġus Ġwhich ĊĠĠĠĠĠĠĠĠ Ġ* Ġalternatives Ġare Ġstill Ġin Ġthe Ġrunning Ġfor Ġthe Ġamount Ġof Ġinput Ġwe 've ĊĠĠĠĠĠĠĠĠ Ġ* Ġconsumed Ġat Ġthis Ġpoint . ĠThe Ġconflicting Ġsets Ġlet Ġus Ġto Ġstrip Ġaway ĊĠĠĠĠĠĠĠĠ Ġ* Ġconfigurations Ġthat Ġwon 't Ġlead Ġto Ġmore Ġstates Ġbecause Ġwe Ġresolve ĊĠĠĠĠĠĠĠĠ Ġ* Ġconflicts Ġto Ġthe Ġconfiguration Ġwith Ġa Ġminimum Ġalternate Ġfor Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġconflicting Ġset . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** CASE S ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* Ġno Ġconflicts Ġand Ġmore Ġthan Ġ 1 Ġalternative Ġin Ġset Ġ=& gt ; Ġcontinue ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* Ġ Ġ`( s , Ġ 1 , Ġx )`, Ġ`( s , Ġ 2 , Ġx )`, Ġ`( s , Ġ 3 , Ġz )`, ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s ', Ġ 1 , Ġy )`, Ġ`( s ', Ġ 2 , Ġy )` Ġyields Ġnon - conflict ing Ġset ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 3 }` ĠU Ġconflicting Ġsets Ġ` min ({ 1 , 2 }) ` ĠU Ġ` min ({ 1 , 2 }) ` Ġ= ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 1 , 3 }` Ġ=& gt ; Ġcontinue ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* Ġ`( s , Ġ 1 , Ġx )`, Ġ`( s , Ġ 2 , Ġx )`, Ġ`( s ', Ġ 1 , Ġy )`, ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s ', Ġ 2 , Ġy )`, Ġ`( s '', Ġ 1 , Ġz )` Ġyields Ġnon - conflict ing Ġset ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 1 }` ĠU Ġconflicting Ġsets Ġ` min ({ 1 , 2 }) ` ĠU Ġ` min ({ 1 , 2 }) ` Ġ= ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 1 }` Ġ=& gt ; Ġstop Ġand Ġpredict Ġ 1 ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* Ġ`( s , Ġ 1 , Ġx )`, Ġ`( s , Ġ 2 , Ġx )`, Ġ`( s ', Ġ 1 , Ġy )`, ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s ', Ġ 2 , Ġy )` Ġyields Ġconflicting , Ġreduced Ġsets Ġ`{ 1 }` ĠU ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 1 }` Ġ= Ġ`{ 1 }` Ġ=& gt ; Ġstop Ġand Ġpredict Ġ 1 , Ġcan Ġannounce ĊĠĠĠĠĠĠĠĠ Ġ* Ġamb iguity Ġ`{ 1 , 2 }` ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* Ġ`( s , Ġ 1 , Ġx )`, Ġ`( s , Ġ 2 , Ġx )`, Ġ`( s ', Ġ 2 , Ġy )`, ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s ', Ġ 3 , Ġy )` Ġyields Ġconflicting , Ġreduced Ġsets Ġ`{ 1 }` ĠU ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 2 }` Ġ= Ġ`{ 1 , 2 }` Ġ=& gt ; Ġcontinue ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ* Ġ`( s , Ġ 1 , Ġx )`, Ġ`( s , Ġ 2 , Ġx )`, Ġ`( s ', Ġ 3 , Ġy )`, ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`( s ', Ġ 4 , Ġy )` Ġyields Ġconflicting , Ġreduced Ġsets Ġ`{ 1 }` ĠU ĊĠĠĠĠĠĠĠĠ Ġ* Ġ`{ 3 }` Ġ= Ġ`{ 1 , 3 }` Ġ=& gt ; Ġcontinue ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ** EX ACT ĠA MB IG U ITY ĠDET E CTION ** ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠIf Ġall Ġstates Ġreport Ġthe Ġsame Ġconflicting Ġset Ġof Ġalternatives , Ġthen Ġwe ĊĠĠĠĠĠĠĠĠ Ġ* Ġknow Ġwe Ġhave Ġthe Ġexact Ġamb iguity Ġset . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` | A _* i * |> 1 ` Ġand ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` A _* i * Ġ= ĠA _* j *` Ġfor Ġall Ġ* i *, Ġ* j *. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* ĠIn Ġother Ġwords , Ġwe Ġcontinue Ġex amin ing Ġlook ahead Ġuntil Ġall Ġ` A _ i ` ĊĠĠĠĠĠĠĠĠ Ġ* Ġhave Ġmore Ġthan Ġone Ġalternative Ġand Ġall Ġ` A _ i ` Ġare Ġthe Ġsame . ĠIf ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` A ={{ 1 , 2 }, Ġ{ 1 , 3 }} `, Ġthen Ġregular ĠLL Ġprediction Ġwould Ġterminate ĊĠĠĠĠĠĠĠĠ Ġ* Ġbecause Ġthe Ġresolved Ġset Ġis Ġ`{ 1 }`. ĠTo Ġdetermine Ġwhat Ġthe Ġreal ĊĠĠĠĠĠĠĠĠ Ġ* Ġamb iguity Ġis , Ġwe Ġhave Ġto Ġknow Ġwhether Ġthe Ġamb iguity Ġis Ġbetween Ġone Ġand ĊĠĠĠĠĠĠĠĠ Ġ* Ġtwo Ġor Ġone Ġand Ġthree Ġso Ġwe Ġkeep Ġgoing . ĠWe Ġcan Ġonly Ġstop Ġprediction Ġwhen ĊĠĠĠĠĠĠĠĠ Ġ* Ġwe Ġneed Ġexact Ġamb iguity Ġdetection Ġwhen Ġthe Ġsets Ġlook Ġlike ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` A ={{ 1 , 2 }} ` Ġor Ġ` {{ 1 , 2 },{ 1 , 2 }} `, Ġetc ... ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġresolves To Just One V iable Alt ( alt sets : ĠCollection < Bit Set >): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġget Single V iable Alt ( alt sets ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠDetermines Ġif Ġevery Ġalternative Ġsubset Ġin Ġ` alt sets ` Ġcontains Ġmore ĊĠĠĠĠĠĠĠĠ Ġ* Ġthan Ġone Ġalternative . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġalt sets Ġa Ġcollection Ġof Ġalternative Ġsub sets ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return Ġ` true ` Ġif Ġevery Ġ[ Bit Set ] Ġin Ġ` alt sets ` Ġhas ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ cardinality ][ Bit Set . cardinality ] Ġ& gt ; Ġ 1 , Ġotherwise Ġ` false ` ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġall Sub sets Conflict ( alt sets : ĠCollection < Bit Set >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ! has Non Conflict ing Alt Set ( alt sets ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠDetermines Ġif Ġany Ġsingle Ġalternative Ġsubset Ġin Ġ` alt sets ` Ġcontains ĊĠĠĠĠĠĠĠĠ Ġ* Ġexactly Ġone Ġalternative . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġalt sets Ġa Ġcollection Ġof Ġalternative Ġsub sets ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return Ġ` true ` Ġif Ġ` alt sets ` Ġcontains Ġa Ġ[ Bit Set ] Ġwith ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ cardinality ][ Bit Set . cardinality ] Ġ 1 , Ġotherwise Ġ` false ` ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġhas Non Conflict ing Alt Set ( alt sets : ĠCollection < Bit Set >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( al ts Ġin Ġalt sets ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( al ts . cardinality () Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠDetermines Ġif Ġany Ġsingle Ġalternative Ġsubset Ġin Ġ` alt sets ` Ġcontains ĊĠĠĠĠĠĠĠĠ Ġ* Ġmore Ġthan Ġone Ġalternative . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġalt sets Ġa Ġcollection Ġof Ġalternative Ġsub sets ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return Ġ` true ` Ġif Ġ` alt sets ` Ġcontains Ġa Ġ[ Bit Set ] Ġwith ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ cardinality ][ Bit Set . cardinality ] Ġ& gt ; Ġ 1 , Ġotherwise Ġ` false ` ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġhas Conflict ing Alt Set ( alt sets : ĠCollection < Bit Set >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( al ts Ġin Ġalt sets ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( al ts . cardinality () Ġ> Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠDetermines Ġif Ġevery Ġalternative Ġsubset Ġin Ġ` alt sets ` Ġis Ġequivalent . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġalt sets Ġa Ġcollection Ġof Ġalternative Ġsub sets ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return Ġ` true ` Ġif Ġevery Ġmember Ġof Ġ` alt sets ` Ġis Ġequal Ġto Ġthe ĊĠĠĠĠĠĠĠĠ Ġ* Ġothers , Ġotherwise Ġ` false ` ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġall Sub sets Equal ( alt sets : ĠCollection < Bit Set >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġit Ġ= Ġalt sets . iterator () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfirst Ġ= Ġit . next () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( it . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext Ġ= Ġit . next () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next Ġ!= Ġfirst ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠReturns Ġthe Ġunique Ġalternative Ġpredicted Ġby Ġall Ġalternative Ġsub sets Ġin ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` alt sets `. ĠIf Ġno Ġsuch Ġalternative Ġexists , Ġthis Ġmethod Ġreturns ĊĠĠĠĠĠĠĠĠ Ġ* Ġ[ AT N . INVALID _ ALT _ NUMBER ]. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġalt sets Ġa Ġcollection Ġof Ġalternative Ġsub sets ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġget Unique Alt ( alt sets : ĠCollection < Bit Set >): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġall Ġ= Ġget Al ts ( alt sets ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( all . cardinality () Ġ== Ġ 1 ) Ġall . next Set Bit ( 0 ) Ġelse ĠAT N . INVALID _ ALT _ NUMBER ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠGets Ġthe Ġcomplete Ġset Ġof Ġrepresented Ġalternatives Ġfor Ġa Ġcollection Ġof ĊĠĠĠĠĠĠĠĠ Ġ* Ġalternative Ġsub sets . ĠThis Ġmethod Ġreturns Ġthe Ġunion Ġof Ġeach Ġ[ Bit Set ] ĊĠĠĠĠĠĠĠĠ Ġ* Ġin Ġ` alt sets `. ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġalt sets Ġa Ġcollection Ġof Ġalternative Ġsub sets ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return Ġthe Ġset Ġof Ġrepresented Ġalternatives Ġin Ġ` alt sets ` ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġget Al ts ( alt sets : ĠCollection < Bit Set >): ĠBit Set Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġall Ġ= ĠBit Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( al ts Ġin Ġalt sets ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġall . or ( al ts ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġall ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠGet Ġunion Ġof Ġall Ġal ts Ġfrom Ġconfigs . ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ since Ġ 4 . 5 . 1 ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġget Al ts ( configs : ĠAT N Config Set ): ĠBit Set Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġal ts Ġ= ĠBit Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( config Ġin Ġconfigs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġal ts . set ( config . alt ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġal ts ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠThis Ġfunction Ġgets Ġthe Ġconflicting Ġalt Ġsub sets Ġfrom Ġa Ġconfiguration Ġset . ĊĠĠĠĠĠĠĠĠ Ġ* ĠFor Ġeach Ġconfiguration Ġ` c ` Ġin Ġ` configs `: ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ< pre > ĊĠĠĠĠĠĠĠĠ Ġ* Ġmap [ c ] ĠU = Ġc .[ alt ][ AT N Config . alt ] Ġ# Ġmap Ġhash / equals Ġuses Ġs Ġand Ġx , Ġnot ĊĠĠĠĠĠĠĠĠ Ġ* Ġalt Ġand Ġnot Ġpred ĊĠĠĠĠĠĠĠ Ġ</ pre > Ġ* ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġget Conflict ing Alt Sub sets ( configs : ĠAT N Config Set ): ĠCollection < Bit Set > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġconfig To Al ts Ġ= ĠAlt And Context Map () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( c Ġin Ġconfigs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġal ts Ġ= Ġconfig To Al ts . get ( c ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( al ts Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġal ts Ġ= ĠBit Set () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġconfig To Al ts . put ( c , Ġal ts ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġal ts !!. set ( c . alt ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġconfig To Al ts . values ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠGet Ġa Ġmap Ġfrom Ġstate Ġto Ġalt Ġsubset Ġfrom Ġa Ġconfiguration Ġset . ĠFor Ġeach ĊĠĠĠĠĠĠĠĠ Ġ* Ġconfiguration Ġ` c ` Ġin Ġ` configs `: ĊĠĠĠĠĠĠĠĠ Ġ* ĊĠĠĠĠĠĠĠĠ Ġ* Ġ< pre > ĊĠĠĠĠĠĠĠĠ Ġ* Ġmap [ c .[ state ][ AT N Config . state ]] ĠU = Ġc .[ alt ][ AT N Config . alt ] ĊĠĠĠĠĠĠĠ Ġ</ pre > Ġ* ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun ĠgetState To Alt Map ( configs : ĠAT N Config Set ): ĠMap < AT N State , ĠBit Set > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġm Ġ= ĠHashMap < AT N State , ĠBit Set >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( c Ġin Ġconfigs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġal ts : ĠBit Set ? Ġ= Ġm [ c . state ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( al ts Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġal ts Ġ= ĠBit Set () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm . put ( c . state , Ġal ts ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġal ts . set ( c . alt ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġm ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġhas State Associated With One Alt ( configs : ĠAT N Config Set ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx Ġ= ĠgetState To Alt Map ( configs ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( al ts Ġin Ġx . values ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( al ts . cardinality () Ġ== Ġ 1 ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġget Single V iable Alt ( alt sets : ĠCollection < Bit Set >): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv iable Al ts Ġ= ĠBit Set () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( al ts Ġin Ġalt sets ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmin Alt Ġ= Ġal ts . next Set Bit ( 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv iable Al ts . set ( min Alt ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( v iable Al ts . cardinality () Ġ> Ġ 1 ) Ġ{ Ġ// Ġmore Ġthan Ġ 1 Ġv iable Ġalt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠAT N . INVALID _ ALT _ NUMBER ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġv iable Al ts . next Set Bit ( 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ Ċ } Ċ