package Ġcombo . sat . constraints Ċ Ċ import Ġcombo . model . Int Var Ċ import Ġcombo . sat .* Ċ import Ġcombo . sat . constraints . Relation .* Ċ import Ġcombo . util .* Ċ import Ġkotlin . math . abs Ċ import Ġkotlin . math . absolute Value Ċ import Ġkotlin . math . max Ċ import Ġkotlin . math . min Ċ import Ġkotlin . random . Random Ċ Ċ /** Ċ Ġ* ĠLinear Ġconstraint Ġen codes Ġa Ġlinear Ġsum Ġ[ relation ] Ġwith Ġa Ġ[ degree ], Ġe . g . Ġ 2 * x 2 Ġ- Ġ 3 * x 4 Ġ<= Ġ 2 . Ċ Ġ* ĠSome Ġsol vers Ġcannot Ġhandle Ġ[ Relation . NE ] Ġbecause Ġit Ġcannot Ġbe Ġexpressed Ġas Ġa Ġlinear Ġrelation . Ċ Ġ* ĠInter mediate Ġresults Ġare Ġstored Ġin Ġa Ġ 3 2 Ġbit Ġinteger Ġso Ġthere Ġis Ġa Ġreal Ġrisk Ġof Ġinteger Ġoverflow Ġfor Ġlarge Ġweights . Ċ Ġ*/ Ċ class ĠLinear ( override Ġval Ġliterals : ĠInt HashMap , Ġval Ġweights : ĠInt Array , Ġval Ġdegree : ĠInt , Ġval Ġrelation : ĠRelation ) Ġ: ĠPro positional Constraint Ġ{ ĊĊĠĠĠ Ġoverride Ġval Ġpriority : ĠInt Ġget () Ġ= Ġ 5 0 0 Ġ- Ġliterals . size ĊĊĠĠĠ Ġval Ġlower Bound Ġ= Ġweights . sum By Ġ{ Ġmin ( 0 , Ġit ) Ġ} ĊĠĠĠ Ġval Ġupper Bound Ġ= Ġweights . sum By Ġ{ Ġmax ( 0 , Ġit ) Ġ} ĊĠĠĠ Ġprivate Ġval Ġaverage Ġ= Ġmax ( 1 , Ġweights . sum By Ġ{ Ġit . absolute Value Ġ} Ġ/ Ġweights . size ) ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġassert ( weights . size Ġ== Ġliterals . size ) ĊĠĠĠĠĠĠĠ Ġassert ( literals . isNotEmpty ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġoperator Ġfun Ġnot () Ġ= ĠLinear ( literals , Ġweights , Ġdegree , Ġ! relation ) ĊĊĠĠĠ Ġoverride Ġfun Ġcache Update ( cache Result : ĠInt , Ġnew Lit : ĠInt ) Ġ= Ġcache Result Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Lit Ġin Ġliterals ) Ġweights [ literals [ new Lit ]] Ġelse Ġ- weights [ literals [! new Lit ]] ĊĊĠĠĠ Ġoverride Ġfun Ġcache ( instance : ĠInstance ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġsum Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( entry Ġin Ġliterals . entry Iterator ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlit Ġ= Ġentry . key () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġentry . value () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( instance . literal ( lit . to Ix ()) Ġ== Ġlit ) Ġsum Ġ+= Ġweights [ index ] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġsum ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġviolations ( instance : ĠInstance , Ġcache Result : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġabsolute Vi olations Ġ= Ġrelation . vi olations ( cache Result , Ġdegree ) ĊĠĠĠĠĠĠĠ Ġval Ġapproximate Vi olations Ġ= Ġabsolute Vi olations Ġ/ Ġaverage ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( approx imate Vi olations Ġ== Ġ 0 Ġ&& Ġabsolute Vi olations Ġ!= Ġ 0 ) Ġ 1 ĊĠĠĠĠĠĠĠ Ġelse Ġapproximate Vi olations . coerce At Most ( literals . size ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġunit Propagation ( unit : ĠInt ): ĠPro positional Constraint Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġix 1 Ġ= Ġliterals [ unit , Ġ- 1 ] ĊĠĠĠĠĠĠĠ Ġval Ġix 2 Ġ= Ġliterals [! unit , Ġ- 1 ] ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( ix 1 Ġ>= Ġ 0 Ġ|| Ġix 2 Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlit Copy Ġ= Ġliterals . copy (). apply Ġ{ Ġif Ġ( ix 1 Ġ>= Ġ 0 ) Ġremove ( unit ) Ġelse Ġremove (! unit ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġweight Ix Ġ= Ġif Ġ( ix 1 Ġ>= Ġ 0 ) Ġliterals [ unit ] Ġelse Ġliterals [! unit ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġdegree Ġ- Ġif Ġ( ix 1 Ġ>= Ġ 0 ) Ġweights [ weight Ix ] Ġelse Ġ 0 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġadjusted Lower Ġ= Ġlower Bound Ġ- Ġmin ( 0 , Ġweights [ weight Ix ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġadjusted Upper Ġ= Ġupper Bound Ġ- Ġmax ( 0 , Ġweights [ weight Ix ]) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( lit Copy . size Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( adjusted Lower Ġ== Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( adjusted Upper Ġ== Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( relation . vi olations ( 0 , Ġd ) Ġ== Ġ 0 ) ĠT auto logy ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse ĠEmpty ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( relation . isEmpty ( adjusted Lower , Ġadjusted Upper , Ġd )) ĠEmpty ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġif Ġ( relation . is T auto logy ( adjusted Lower , Ġadjusted Upper , Ġd )) ĠT auto logy ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġweight Copy Ġ= Ġweights . remove At ( weight Ix ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( lit Ġin Ġlit Copy ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( lit Copy [ lit ] Ġ> Ġweight Ix ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThis Ġdoes Ġnot Ġchange Ġhash Ġposition Ġso Ġis Ġsafe Ġfrom Ġconcurrent Ġmodification ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlit Copy [ lit ] Ġ= Ġlit Copy [ lit ] Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠLinear ( lit Copy , Ġweight Copy , Ġd , Ġrelation ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġthis ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠUnit Ġliterals Ġfor ĠArithmetic Ġconstraint Ġis Ġtricky Ġbecause Ġthere Ġcan Ġbe Ġfree Ġliterals Ġin Ġa Ġconstraint Ġcontaining ĊĠĠĠĠ Ġ* Ġunit Ġliterals . ĠFor Ġexample Ġif Ġsome Ġweights Ġare Ġ 0 . ĠOr Ġ- 1 x 1 Ġ+ Ġ 1 0 x 2 Ġ> Ġ 8 , Ġhere Ġx 2 = 1 Ġand Ġx 1 Ġcan Ġbe Ġ 0 Ġor Ġ 1 . ĊĠĠĠĠ Ġ* ĠFor Ġthis Ġreason Ġwe Ġskip Ġunit Ġliterals Ġfor ĠArithmetic Ġconstraint . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġunit L iterals () Ġ= Ġthrow ĠUnsupportedOperationException () ĊĊĠĠĠ Ġoverride Ġfun Ġis Unit () Ġ= Ġfalse ĊĊĠĠĠ Ġoverride Ġfun Ġco erce ( instance : ĠInstance , Ġrng : ĠRandom ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcard Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġvar Ġvalue Ġ= Ġcache ( instance ) ĊĠĠĠĠĠĠĠ Ġval Ġperm Ġ= Ġcard . literals . permutation ( rng ) ĊĠĠĠĠĠĠĠ Ġif Ġ( card . relation Ġ== ĠLE Ġ|| Ġcard . relation Ġ== ĠLT Ġ|| Ġcard . relation Ġ== ĠE Q ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġif Ġ( card . relation Ġ== ĠLT ) Ġcard . degree Ġ- Ġ 1 Ġelse Ġcard . degree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( value Ġ> Ġd Ġ&& Ġperm . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlit Ġ= Ġperm . nextInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( instance . literal ( lit . to Ix ()) Ġ== Ġlit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinstance . flip ( lit . to Ix ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( card . relation Ġ== ĠGE Ġ|| Ġcard . relation Ġ== ĠGT Ġ|| Ġcard . relation Ġ== ĠE Q ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġif Ġ( card . relation Ġ== ĠGT ) Ġcard . degree Ġ+ Ġ 1 Ġelse Ġcard . degree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( value Ġ< Ġd Ġ&& Ġperm . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlit Ġ= Ġperm . nextInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( instance . literal ( lit . to Ix ()) Ġ!= Ġlit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinstance . flip ( lit . to Ix ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( card . relation Ġ== ĠNE Ġ&& Ġvalue Ġ== Ġcard . degree Ġ&& Ġperm . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinstance . flip ( perm . nextInt (). to Ix ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġliterals . join ToString (", Ġ", Ġ" Linear (", Ġ" Ġ${ relation . operator } Ġ$ degree )") Ġ{ ĊĠĠĠĠĠĠĠ Ġ"${ weights [ literals [ it ]] } x $ it " ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠCard inality Ġconstraint Ġen codes Ġa Ġlinear Ġequality Ġ[ relation ] Ġwith Ġa Ġ[ degree ]. Ċ Ġ* ĠSome Ġsol vers Ġcannot Ġhandle Ġ[ Relation . NE ] Ġbecause Ġit Ġcannot Ġbe Ġexpressed Ġas Ġa Ġlinear Ġrelation . Ċ Ġ*/ Ċ class ĠCard inality ( override Ġval Ġliterals : ĠInt Collection , Ġval Ġdegree : ĠInt , Ġval Ġrelation : ĠRelation ) Ġ: ĠPro positional Constraint Ġ{ ĊĊĠĠĠ Ġoverride Ġval Ġpriority : ĠInt Ġget () Ġ= Ġ 4 0 0 Ġ- Ġliterals . size ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġassert ( degree Ġ>= Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġassert ( literals . isNotEmpty ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġoperator Ġfun Ġnot () Ġ= ĠCard inality ( literals , Ġdegree , Ġ! relation ) ĊĊĠĠĠ Ġoverride Ġfun Ġviolations ( instance : ĠInstance , Ġcache Result : ĠInt ) Ġ= Ġrelation . vi olations ( cache Result , Ġdegree ). coerce At Most ( literals . size ) ĊĊĠĠĠ Ġoverride Ġfun Ġunit Propagation ( unit : ĠInt ): ĠPro positional Constraint Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmatch Ġ= Ġunit Ġin Ġliterals ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( match Ġ|| Ġ! unit Ġin Ġliterals ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcopy Ġ= Ġliterals . mutable Copy ( null Value Ġ= Ġ 0 ). apply Ġ{ Ġif Ġ( match ) Ġremove ( unit ) Ġelse Ġremove (! unit ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġdegree Ġ- Ġif Ġ( match ) Ġ 1 Ġelse Ġ 0 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( relation . isEmpty ( 0 , Ġcopy . size , Ġd )) ĠEmpty ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġif Ġ( relation . is T auto logy ( 0 , Ġcopy . size , Ġd )) ĠT auto logy ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcard Ġ= ĠCard inality ( copy , Ġd , Ġrelation ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( card . is Unit ()) ĠCon junction ( collection Of (* card . unit L iterals ())) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġcard ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġthis ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġis Unit () Ġ= Ġrelation . is Unit ( 0 , Ġliterals . size , Ġdegree ) ĊĊĠĠĠ Ġoverride Ġfun Ġunit L iterals (): ĠInt Array Ġ{ ĊĠĠĠĠĠĠĠ Ġassert ( is Unit ()) ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( relation ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠGT Ġ-> Ġliterals . toArray () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠGE Ġ-> Ġliterals . toArray () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠLE Ġ-> Ġliterals . toArray (). map Array Ġ{ Ġ! it Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠLT Ġ-> Ġliterals . toArray (). map Array Ġ{ Ġ! it Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠNE Ġ-> Ġthrow ĠIllegalArgumentException () ĊĠĠĠĠĠĠĠĠĠĠĠ ĠE Q Ġ-> Ġif Ġ( degree Ġ== Ġ 0 ) Ġliterals . toArray (). map Array Ġ{ Ġ! it Ġ} Ġelse Ġliterals . toArray () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġco erce ( instance : ĠInstance , Ġrng : ĠRandom ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcard Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġvar Ġvalue Ġ= Ġcache ( instance ) ĊĠĠĠĠĠĠĠ Ġval Ġperm Ġ= Ġcard . literals . permutation ( rng ) ĊĠĠĠĠĠĠĠ Ġif Ġ( card . relation Ġ== ĠLE Ġ|| Ġcard . relation Ġ== ĠLT Ġ|| Ġcard . relation Ġ== ĠE Q ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġif Ġ( card . relation Ġ== ĠLT ) Ġcard . degree Ġ- Ġ 1 Ġelse Ġcard . degree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( value Ġ> Ġd Ġ&& Ġperm . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlit Ġ= Ġperm . nextInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( instance . literal ( lit . to Ix ()) Ġ== Ġlit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinstance . flip ( lit . to Ix ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( card . relation Ġ== ĠGE Ġ|| Ġcard . relation Ġ== ĠGT Ġ|| Ġcard . relation Ġ== ĠE Q ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġif Ġ( card . relation Ġ== ĠGT ) Ġcard . degree Ġ+ Ġ 1 Ġelse Ġcard . degree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( value Ġ< Ġd Ġ&& Ġperm . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlit Ġ= Ġperm . nextInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( instance . literal ( lit . to Ix ()) Ġ!= Ġlit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinstance . flip ( lit . to Ix ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( card . relation Ġ== ĠNE Ġ&& Ġvalue Ġ== Ġcard . degree Ġ&& Ġperm . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinstance . flip ( perm . nextInt (). to Ix ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġliterals . join ToString (", Ġ", Ġ" Cardinality (", Ġ" Ġ${ relation . operator } Ġ$ degree )") Ġ{ Ġit . toString () Ġ} Ċ } Ċ Ċ class ĠCard inality Var ( value L iterals : ĠInt Collection , Ġval Ġdegree Var : ĠInt Var , Ġval Ġvar Index : ĠInt , Ġval Ġparent Literal : ĠInt , Ġval Ġrelation : ĠRelation ) Ġ: ĠPro positional Constraint Ġ{ ĊĊĠĠĠ Ġoverride Ġval Ġpriority : ĠInt Ġget () Ġ= Ġ 4 0 0 Ġ- Ġliterals . size ĊĠĠĠ Ġoverride Ġval Ġliterals : ĠInt Union Collection ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġassert ( value L iterals . isNotEmpty ()) ĊĠĠĠĠĠĠĠ Ġval Ġl Ġ= Ġvar Index . to Literal ( true ) ĊĠĠĠĠĠĠĠ Ġval Ġdegree L iterals Ġ= ĠInt Range Collection ( l , Ġl Ġ+ Ġdegree Var . nbr Values Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġliterals Ġ= Ġif Ġ( parent Literal Ġ== Ġ 0 ) ĠInt Union Collection ( value L iterals , Ġdegree L iterals ) ĊĠĠĠĠĠĠĠ Ġelse ĠInt Union Collection ( value L iterals , ĠInt Union Collection ( degree L iterals , Ġcollection Of ( parent Literal ))) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġval Ġbase Cardinality Ġ= ĠCard inality ( literals . a , Ġ 0 , Ġrelation ) ĊĊĠĠĠ Ġoverride Ġfun Ġcache Update ( cache Result : ĠInt , Ġnew Lit : ĠInt ) Ġ= Ġcache Result Ġ+ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠ Ġnew Lit Ġin Ġliterals . a Ġ-> Ġ 1 ĊĠĠĠĠĠĠĠ Ġ! new Lit Ġin Ġliterals . a Ġ-> Ġ- 1 ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcache ( instance : ĠInstance ) Ġ= Ġbase Cardinality . cache ( instance ) ĊĊĠĠĠ Ġoverride Ġoperator Ġfun Ġnot () Ġ= ĠCard inality Var ( literals . a , Ġdegree Var , Ġvar Index , Ġparent Literal , Ġ! relation ) ĊĊĠĠĠ Ġ// ĠTODO Ġunit Propagation Ġby Ġhaving Ġa Ġunits Ġas Ġfield ĊĊĠĠĠ Ġoverride Ġfun Ġviolations ( instance : ĠInstance , Ġcache Result : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdegree Ġ= Ġdegree Var . valueOf ( instance , Ġvar Index , Ġparent Literal ) Ġ?: Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġreturn Ġrelation . vi olations ( cache Result , Ġdegree ). coerce At Most ( literals . a . size ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġco erce ( instance : ĠInstance , Ġrng : ĠRandom ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdegree Ġ= Ġdegree Var . valueOf ( instance , Ġvar Index , Ġparent Literal ) Ġ?: Ġreturn ĊĠĠĠĠĠĠĠ ĠCard inality ( literals . a , Ġdegree , Ġrelation ). coerce ( instance , Ġrng ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġliterals . a . join ToString (", Ġ", Ġ" Cardinality Var (", Ġ" Ġ${ relation . operator } Ġ$ var Index )") Ġ{ Ġit . toString () Ġ} Ċ } Ċ Ċ class ĠLinear Var ( value L iterals : ĠInt HashMap , Ġval Ġweights : ĠInt Array , Ġval Ġdegree Var : ĠInt Var , Ġval Ġvar Index : ĠInt , Ġval Ġparent Literal : ĠInt , Ġval Ġrelation : ĠRelation ) Ġ: ĠPro positional Constraint Ġ{ ĊĊĠĠĠ Ġoverride Ġval Ġpriority : ĠInt Ġget () Ġ= Ġ 5 0 0 Ġ- Ġliterals . size ĊĠĠĠ Ġoverride Ġval Ġliterals : ĠInt Union Collection ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġassert ( value L iterals . isNotEmpty ()) ĊĠĠĠĠĠĠĠ Ġval Ġl Ġ= Ġvar Index . to Literal ( true ) ĊĠĠĠĠĠĠĠ Ġval Ġdegree L iterals Ġ= ĠInt Range Collection ( l , Ġl Ġ+ Ġdegree Var . nbr Values Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġliterals Ġ= Ġif Ġ( parent Literal Ġ== Ġ 0 ) ĠInt Union Collection ( value L iterals , Ġdegree L iterals ) ĊĠĠĠĠĠĠĠ Ġelse ĠInt Union Collection ( value L iterals , ĠInt Union Collection ( degree L iterals , Ġcollection Of ( parent Literal ))) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġval Ġbase Linear Ġ= ĠLinear ( literals . a Ġas ĠInt HashMap , Ġweights , Ġ 0 , Ġrelation ) ĊĊĠĠĠ Ġoverride Ġfun Ġcache Update ( cache Result : ĠInt , Ġnew Lit : ĠInt ) Ġ= Ġcache Result Ġ+ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠ Ġnew Lit Ġin Ġliterals . a Ġ-> Ġ 1 ĊĠĠĠĠĠĠĠ Ġ! new Lit Ġin Ġliterals . a Ġ-> Ġ- 1 ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcache ( instance : ĠInstance ) Ġ= Ġbase Linear . cache ( instance ) ĊĊĠĠĠ Ġoverride Ġoperator Ġfun Ġnot () Ġ= ĠLinear Var ( literals . a Ġas ĠInt HashMap , Ġweights , Ġdegree Var , Ġvar Index , Ġparent Literal , Ġ! relation ) ĊĊĠĠĠ Ġ// ĠTODO Ġunit Propagation Ġby Ġhaving Ġa Ġunits Ġas Ġfield ĊĊĠĠĠ Ġoverride Ġfun Ġviolations ( instance : ĠInstance , Ġcache Result : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdegree Ġ= Ġdegree Var . valueOf ( instance , Ġvar Index , Ġparent Literal ) Ġ?: Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġreturn Ġrelation . vi olations ( cache Result , Ġdegree ). coerce At Most ( literals . a . size ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġco erce ( instance : ĠInstance , Ġrng : ĠRandom ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdegree Ġ= Ġdegree Var . valueOf ( instance , Ġvar Index , Ġparent Literal ) Ġ?: Ġreturn ĊĠĠĠĠĠĠĠ ĠLinear ( literals . a Ġas ĠInt HashMap , Ġweights , Ġdegree , Ġrelation ). coerce ( instance , Ġrng ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġliterals . a . join ToString (", Ġ", Ġ" Linear Var (", Ġ" Ġ${ relation . operator } Ġ$ var Index )") Ġ{ ĊĠĠĠĠĠĠĠ Ġ"${ weights [( literals . a Ġas ĠInt HashMap )[ it ]] } x $ it " ĊĠĠĠ Ġ} Ċ } Ċ Ċ enum Ġclass ĠRelation ( val Ġoperator : ĠString ) Ġ{ ĊĠĠĠ ĠGT ("> ") Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġviolations ( value : ĠInt , Ġdegree : ĠInt ) Ġ= Ġmax ( 0 , Ġ 1 Ġ+ Ġdegree Ġ- Ġvalue ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis T auto logy ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ< Ġlower Bound ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis Unit ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ== Ġupper Bound Ġ- Ġ 1 ĊĠĠĠ Ġ}, ĊĠĠĠ ĠGE ("> =") Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġviolations ( value : ĠInt , Ġdegree : ĠInt ) Ġ= Ġmax ( 0 , Ġdegree Ġ- Ġvalue ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis T auto logy ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ<= Ġlower Bound ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis Unit ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ== Ġupper Bound ĊĠĠĠ Ġ}, ĊĠĠĠ ĠLE ("< =") Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġviolations ( value : ĠInt , Ġdegree : ĠInt ) Ġ= Ġmax ( 0 , Ġvalue Ġ- Ġdegree ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis T auto logy ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ>= Ġupper Bound ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis Unit ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ== Ġlower Bound ĊĠĠĠ Ġ}, ĊĠĠĠ ĠLT ("< ") Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġviolations ( value : ĠInt , Ġdegree : ĠInt ) Ġ= Ġmax ( 0 , Ġ 1 Ġ+ Ġvalue Ġ- Ġdegree ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis T auto logy ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ> Ġupper Bound ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis Unit ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ== Ġlower Bound Ġ+ Ġ 1 ĊĠĠĠ Ġ}, ĊĠĠĠ ĠNE (" ! =") Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġviolations ( value : ĠInt , Ġdegree : ĠInt ) Ġ= Ġif Ġ( value Ġ== Ġdegree ) Ġ 1 Ġelse Ġ 0 ĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠisEmpty ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġ( lower Bound Ġ== Ġupper Bound Ġ&& Ġlower Bound Ġ== Ġdegree ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis T auto logy ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ! in Ġlower Bound .. upper Bound ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis Unit ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġfalse ĊĠĠĠ Ġ}, ĊĠĠĠ ĠE Q (" =") Ġ{ ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġviolations ( value : ĠInt , Ġdegree : ĠInt ) Ġ= Ġabs ( value Ġ- Ġdegree ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠisEmpty ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ! in Ġlower Bound .. upper Bound ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis T auto logy ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġ( lower Bound Ġ== Ġupper Bound Ġ&& Ġlower Bound Ġ== Ġdegree ) ĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġis Unit ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġdegree Ġ== Ġlower Bound Ġ|| Ġdegree Ġ== Ġupper Bound ĊĠĠĠ Ġ}; ĊĊĠĠĠ Ġoperator Ġfun Ġnot (): ĠRelation Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( this ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠGT Ġ-> ĠLE ĊĠĠĠĠĠĠĠĠĠĠĠ ĠGE Ġ-> ĠLT ĊĠĠĠĠĠĠĠĠĠĠĠ ĠLE Ġ-> ĠGT ĊĠĠĠĠĠĠĠĠĠĠĠ ĠLT Ġ-> ĠGE ĊĠĠĠĠĠĠĠĠĠĠĠ ĠNE Ġ-> ĠE Q ĊĠĠĠĠĠĠĠĠĠĠĠ ĠE Q Ġ-> ĠNE ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġabstract Ġfun Ġviolations ( value : ĠInt , Ġdegree : ĠInt ): ĠInt ĊĠĠĠ Ġopen Ġfun ĠisEmpty ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ) Ġ= Ġviolations ( upper Bound , Ġdegree ) Ġ!= Ġ 0 Ġ&& Ġviolations ( lower Bound , Ġdegree ) Ġ!= Ġ 0 ĊĠĠĠ Ġabstract Ġfun Ġis T auto logy ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ): ĠBoolean ĊĠĠĠ Ġabstract Ġfun Ġis Unit ( lower Bound : ĠInt , Ġupper Bound : ĠInt , Ġdegree : ĠInt ): ĠBoolean Ċ }