package Ġverify . serial Ċ Ċ import Ġjava . util .* Ċ Ċ /** Ċ Ġ* ĠA ĠLong Ġimplementation Ġof Ġa ĠRev ocation ĠTree Ċ Ġ* Ċ Ġ* ĠCreated Ġon Ġ 8 / 3 / 2 0 1 6 Ċ Ġ* Ġ@ see ĠRev ocation Tree Ċ Ġ* Ġ@ author ĠDan ĠKon dr at y uk Ċ Ġ*/ Ċ class ĠLong Rev ocation Tree ( interval Map : ĠNavig able Map < Long , ĠLong >) Ġ: ĠRev ocation Tree < Long >( interval Map ) Ġ{ ĊĊĠĠĠ Ġconstructor ( interval Map : ĠNavig able Map < Long , ĠLong >, Ġoffset : ĠLong ) Ġ: Ġthis ( interval Map ) Ġ{ ĊĠĠĠĠĠĠĠ Ġinterval Map . put ( offset , Ġoffset ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Synchron ized Ġoverride Ġfun Ġadd ( range : ĠLong ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( range Ġ< Ġ 1 ) Ġ{ Ġthrow ĠIllegalArgumentException (" Added Ġrange Ġmust Ġbe Ġ>= Ġ 1 ") Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġlast Ġ= Ġinterval Map . poll Last Entry () ĊĠĠĠĠĠĠĠ Ġinterval Map . put ( last . key , Ġlast . value Ġ+ Ġrange ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Synchron ized Ġoverride Ġfun Ġremove ( value : ĠLong ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠExtract Ġthe Ġinterval ĊĠĠĠĠĠĠĠ Ġval Ġ( min , Ġmax ) Ġ= Ġinterval Map . floor Entry ( value ) Ġ?: Ġthrow ĠIllegalArgumentException (" value Ġmust Ġnot Ġbe Ġsmaller Ġthan Ġthe Ġminimum ") ĊĊĠĠĠĠĠĠĠ Ġif Ġ( value Ġ>= Ġmax ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalArgumentException (" value Ġmust Ġbe Ġwithin Ġan Ġinterval ") ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġinterval , Ġsince Ġit Ġis Ġread Ġonly ĊĠĠĠĠĠĠĠ Ġinterval Map . remove ( min ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠThere Ġare Ġ 4 Ġcases Ġto Ġconsider : ĊĠĠĠĠĠĠĠ Ġif Ġ( value Ġ== Ġmin ) Ġ{ ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ 1 . Ġmin Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ== Ġmax Ġ- Ġ 1 ) Ġ{ Ġreturn ; Ġ} Ġ Ġ// Ġ 2 . Ġsingle Ġelement Ġ( already Ġremoved ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinterval Map . put ( min Ġ+ Ġ 1 , Ġmax ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( value Ġ== Ġmax Ġ- Ġ 1 ) Ġ{ ĠĠĠĠĠĠĠĠ Ġ// Ġ 3 . Ġmax Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinterval Map . put ( min , Ġmax Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ 4 . Ġvalue Ġinside Ġinterval ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinterval Map . put ( min , Ġvalue ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinterval Map . put ( value Ġ+ Ġ 1 , Ġmax ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcontains ( value : ĠLong ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠReturn Ġtrue Ġif Ġwithin Ġbounds Ġof Ġthe Ġnearest Ġinterval , Ġfalse Ġotherwise ĊĠĠĠĠĠĠĠ Ġval Ġinterval Ġ= Ġinterval Map . floor Entry ( value ) Ġ?: Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġreturn Ġvalue Ġ< Ġinterval . value ĊĠĠĠ Ġ} Ċ } Ċ