"""intervals
Union, intersection, set difference and symmetric difference
of possibly overlapping or touching integer intervals.
Intervals are defined right-open. (1, 4) -> 1, 2, 3
e.g.
union([(1, 4), (7, 9)], (3, 5)) -> [(1, 5), (7, 9)]
intersection([(1, 4), (7, 9)], (3, 5)) -> [(3, 4)]
set_difference([(1, 4), (7, 9)], (3, 5)) -> [(1, 3), (7, 9)]
set_difference([(3, 5)], [(1, 4), (7, 9)]) -> [(4, 5)]
symmetric_difference([(1, 4), (7, 9)], (3, 5)) -> [(1, 3), (4, 5), (7, 9)]
see: http://e...content-available-to-author-only...a.org/wiki/Set_theory#Basic_concepts_and_notation
"""
import copy
from collections import namedtuple
from itertools import accumulate, chain, islice, repeat
from operator import itemgetter
import unittest
class Intervals( object ) :
"""Holds a non overlapping list of intervals.
One single interval is just a pair.
Overlapping or touching intervals are automatically merged.
"""
def __init__ ( self , interval_list= ( ) ) :
"""Raises a ValueError if the length of one of the
intervals in the list is negative.
"""
if any ( begin > end for begin, end in interval_list) :
raise ValueError ( 'Invalid interval' )
self ._interval_list = _merge_interval_lists(
interval_list, [ ] , OP_UNION)
def __repr__ ( self ) :
"""Just write out all included intervals.
"""
return 'Intervals ' + str ( self ._interval_list)
def get( self , copy_content= True ) :
"""Return the list of intervals.
"""
return copy .copy ( self ._interval_list) if copy_content\
else self ._interval_list
def union( a, b) :
"""Merge a and b (union).
"""
return Intervals( _merge_interval_lists(
a.get ( False ) , b.get ( False ) , OP_UNION) )
def intersections( a, b) :
"""Intersects a and b.
"""
return Intervals( _merge_interval_lists(
a.get ( False ) , b.get ( False ) , merge_type= OP_INTERSECTIONS) )
def set_difference( a, b) :
"""Removes b from a.
Set difference is not commutative.
"""
return Intervals( _merge_interval_lists(
a.get ( False ) , b.get ( False ) , merge_type= OP_SET_DIFFERENCE) )
def symmetric_difference( a, b) :
"""Symmetric difference of a and b.
"""
return Intervals( _merge_interval_lists(
a.get ( False ) , b.get ( False ) , merge_type= OP_SYMMETRIC_DIFFERENCE) )
def compose( func_1, func_2, unpack= False ) :
"""
compose(func_1, func_2, unpack=False) -> function
The function returned by compose is a composition of func_1 and func_2.
That is, compose(func_1, func_2)(5) == func_1(func_2(5)).
"""
if not callable ( func_1) :
raise TypeError ( "First argument to compose must be callable." )
if not callable ( func_2) :
raise TypeError ( "Second argument to compose must be callable." )
if unpack:
def composition( *args, **kwargs) :
return func_1( *func_2( *args, **kwargs) )
else :
def composition( *args, **kwargs) :
return func_1( func_2( *args, **kwargs) )
return composition
# Helper to avoid repetitive lambdas.
def check_for( cond) :
return lambda val: val == cond
# http://e...content-available-to-author-only...a.org/wiki/Identity_function
identity = lambda x: x
# Depending on the operation carried out,
# the criteria for interval begins and ends in the result differ.
# E.g:
# a = | - - - - | | - - - |
# b = | - - - - |
# counts = 1 2 1 0 1 0 (union, intersection, sym diff)
# counts = 1 0 -1 0 1 0 (set diff)
# union = | - - - - - - | | - - - |
# inter = | - - - - |
# sym d = | - |
# set d = | - | | - - - |
#
# One can see that union begins if the count changes from 0 to 1
# and ends if the count changes from 1 to 0
# An intersection begins at a change from 1 to 2 and ends with 2 to 1.
# A symmetric difference begins at every change to one
# and ends at every change away from one.
# The conditions for the set difference are the same as for the union.
set_op = namedtuple( 'set_op' , [ 'transform' , 'begin' , 'end' ] )
OP_UNION = set_op(
transform = identity,
begin = check_for( ( 0 , 1 ) ) ,
end = check_for( ( 1 , 0 ) ) )
OP_INTERSECTIONS = set_op(
transform = identity,
begin = check_for( ( 1 , 2 ) ) ,
end = check_for( ( 2 , 1 ) ) )
OP_SYMMETRIC_DIFFERENCE = set_op(
transform = identity,
begin = lambda change: change[ 1 ] == 1 ,
end = lambda change: change[ 1 ] != 1 )
OP_SET_DIFFERENCE = set_op(
# If we want to calculate the set difference
# we invert the second interval list,
# i.e. swap begin and end.
transform = compose( tuple , reversed ) ,
begin = check_for( ( 0 , 1 ) ) ,
end = check_for( ( 1 , 0 ) ) )
# class Intervals makes sure, by always building the union first,
# that no invalid a's or b's are fed here.
def _merge_interval_lists( a, b, merge_type) :
"""Merges two lists of intervals in O(n*log(n)).
Overlapping or touching intervals are simplified to one.
Arguments:
a and b -- The interval lists to merge.
merge_type -- Can be:
OP_UNION,
OP_INTERSECTIONS,
OP_SYMMETRIC_DIFFERENCE, or
OP_SET_DIFFERENCE.
Return the sorted result as a list.
"""
# Adjust the operand for the selected operator.
b = map ( merge_type.transform , b)
# Separately sort begins and ends
# and pair them with the implied change
# of the count of currently open intervals.
# e.g. (1, 4), (7, 9), (3, 5) ->
# begins = [(1, 1), (3, 1), (7, 1)]
# ends = [(4, -1), (5, -1), (9, -1)]
both = list ( chain( a, b) )
begins = zip ( sorted ( map ( itemgetter( 0 ) , both) ) ,
repeat( 1 ) )
ends = zip ( sorted ( map ( itemgetter( 1 ) , both) ) ,
repeat( -1 ) )
# Sort begins and ends together.
# If the value is the same, begins come before ends
# to ensure touching intervals being merged to one.
# In our example above this means:
# edges = [(1, 4), (3, 1), (4, -1), (5, -1), (7, 1), (9, -1)]
edges = sorted ( chain( begins, ends) , key= lambda x: ( x[ 0 ] , -x[ 1 ] ) )
# The number of opened intervals after each edge.
counts = list ( accumulate( map ( itemgetter( 1 ) , edges) ) )
# The changes of opened intervals at each edge.
changes = zip ( chain( [ 0 ] , counts) , counts)
# Just the x positions of the edges.
xs = map ( itemgetter( 0 ) , edges)
xs_and_changes = list ( zip ( xs, changes) )
# Now we filter out the begins and ends from the changes
# and get their x positions.
res_begins = map ( itemgetter( 0 ) ,
starfilter( lambda x, change: merge_type.begin ( change) ,
xs_and_changes) )
res_ends = map ( itemgetter( 0 ) ,
starfilter( lambda x, change: merge_type.end ( change) ,
xs_and_changes) )
# The result is then just pairing up the sorted begins and ends.
result = pairwise( sorted ( chain( res_begins, res_ends) ) , False )
# No empty intervals in the result.
def length_greater_than_zero( interval) :
return interval[ 0 ] < interval[ 1 ]
return list ( filter ( length_greater_than_zero, result) )
class TestIntervals( unittest .TestCase ) :
def test_ctor( self ) :
# Check ctors sanity check.
self .assertRaises ( ValueError , Intervals, [ ( 2 , 4 ) , ( 3 , 1 ) ] )
def test_add_behind( self ) :
# Check adding right of the last interval.
intervals = Intervals( [ ( 0 , 2 ) ] )
intervals = union( intervals, Intervals( [ ( 3 , 4 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 0 , 2 ) , ( 3 , 4 ) ] )
def test_add_in_front( self ) :
# Check adding left to the first interval.
intervals = Intervals( [ ( 3 , 4 ) ] )
intervals = union( intervals, Intervals( [ ( 1 , 2 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 1 , 2 ) , ( 3 , 4 ) ] )
def test_add_in_between( self ) :
# Check adding between two intervals.
intervals = Intervals( [ ( 1 , 2 ) ] )
intervals = union( intervals, Intervals( [ ( 6 , 9 ) ] ) )
intervals = union( intervals, Intervals( [ ( 3 , 5 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 1 , 2 ) , ( 3 , 5 ) , ( 6 , 9 ) ] )
def test_add_touching( self ) :
# Check adding a interval touching an existing one.
intervals = Intervals( [ ( 1 , 3 ) ] )
intervals = union( intervals, Intervals( [ ( 3 , 5 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 1 , 5 ) ] )
def test_add_overlapping( self ) :
# Check adding a interval overlapping an existing one.
intervals = Intervals( [ ( 1 , 4 ) ] )
intervals = union( intervals, Intervals( [ ( 3 , 5 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 1 , 5 ) ] )
def test_add_overlapping_multiple( self ) :
# Check adding a interval overlapping multiple existing ones.
intervals = Intervals( [ ( 1 , 4 ) ] )
intervals = union( intervals, Intervals( [ ( 5 , 7 ) ] ) )
intervals = union( intervals, Intervals( [ ( 8 , 10 ) ] ) )
intervals = union( intervals, Intervals( [ ( 3 , 9 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 1 , 10 ) ] )
def test_add_swallow( self ) :
# Check adding a interval completely covering an existing one.
intervals = Intervals( [ ( 2 , 3 ) ] )
intervals = union( intervals, Intervals( [ ( 1 , 4 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 1 , 4 ) ] )
def test_sub( self ) :
# Check removing an interval
intervals = Intervals( [ ( 0 , 3 ) ] )
intervals = union( intervals, Intervals( [ ( 5 , 7 ) ] ) )
intervals = set_difference( intervals, Intervals( [ ( 2 , 6 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 0 , 2 ) , ( 6 , 7 ) ] )
def test_intersections( self ) :
# Check adding right of the last interval.
intervals = Intervals( [ ( 0 , 3 ) ] )
intervals = union( intervals, Intervals( [ ( 5 , 7 ) ] ) )
intervals = intersections( intervals, Intervals( [ ( 2 , 6 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 2 , 3 ) , ( 5 , 6 ) ] )
def test_symmetric_difference( self ) :
# Check symmetric difference
intervals = Intervals( [ ( 0 , 3 ) ] )
intervals = union( intervals, Intervals( [ ( 5 , 7 ) ] ) )
intervals = symmetric_difference( intervals, Intervals( [ ( 2 , 6 ) ] ) )
self .assertEqual ( intervals.get ( ) , [ ( 0 , 2 ) , ( 3 , 5 ) , ( 6 , 7 ) ] )
def tuple_wise( iterable, size, step) :
"""Tuples up the elements of iterable.
Arguments:
iterable -- source data
size -- size of the destination tuples
step -- step to do in iterable per destination tuple
tuple_wise(s, 3, 1): "s -> (s0,s1,s2), (s1,s2,s3), (s3,s4,s5), ...
tuple_wise(s, 2, 4): "s -> (s0,s1), (s4,s5), (s8,s9), ...
"""
return zip (
*( islice( iterable, start, None , step)
for start in range ( size) ) )
def pairwise( iterable, overlapping) :
"""Pairs up the elements of iterable.
overlapping: "s -> (s0,s1), (s2,s3), (s4,s5), ...
not overlapping: "s -> (s0,s1), (s1,s2), (s2,s3), ...
"""
return tuple_wise( iterable, 2 , 1 if overlapping else 2 )
def starfilter( function, iterable) :
"""starfilter <--> filter == starmap <--> map"""
return ( item for item in iterable if function( *item) )
if __name__ == '__main__' :
unittest .main ( verbosity= 2 )
IiIiaW50ZXJ2YWxzCgpVbmlvbiwgaW50ZXJzZWN0aW9uLCBzZXQgZGlmZmVyZW5jZSBhbmQgc3ltbWV0cmljIGRpZmZlcmVuY2UKb2YgcG9zc2libHkgb3ZlcmxhcHBpbmcgb3IgdG91Y2hpbmcgaW50ZWdlciBpbnRlcnZhbHMuCkludGVydmFscyBhcmUgZGVmaW5lZCByaWdodC1vcGVuLiAoMSwgNCkgLT4gMSwgMiwgMwoKZS5nLgp1bmlvbihbKDEsIDQpLCAoNywgOSldLCAoMywgNSkpIC0+IFsoMSwgNSksICg3LCA5KV0KaW50ZXJzZWN0aW9uKFsoMSwgNCksICg3LCA5KV0sICgzLCA1KSkgLT4gWygzLCA0KV0Kc2V0X2RpZmZlcmVuY2UoWygxLCA0KSwgKDcsIDkpXSwgKDMsIDUpKSAtPiBbKDEsIDMpLCAoNywgOSldCnNldF9kaWZmZXJlbmNlKFsoMywgNSldLCBbKDEsIDQpLCAoNywgOSldKSAtPiBbKDQsIDUpXQpzeW1tZXRyaWNfZGlmZmVyZW5jZShbKDEsIDQpLCAoNywgOSldLCAoMywgNSkpIC0+IFsoMSwgMyksICg0LCA1KSwgKDcsIDkpXQoKc2VlOiBodHRwOi8vZS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYS5vcmcvd2lraS9TZXRfdGhlb3J5I0Jhc2ljX2NvbmNlcHRzX2FuZF9ub3RhdGlvbgoiIiIKCmltcG9ydCBjb3B5CmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IG5hbWVkdHVwbGUKZnJvbSBpdGVydG9vbHMgaW1wb3J0IGFjY3VtdWxhdGUsIGNoYWluLCBpc2xpY2UsIHJlcGVhdApmcm9tIG9wZXJhdG9yIGltcG9ydCBpdGVtZ2V0dGVyCmltcG9ydCB1bml0dGVzdAoKY2xhc3MgSW50ZXJ2YWxzKG9iamVjdCk6CiAgICAiIiJIb2xkcyBhIG5vbiBvdmVybGFwcGluZyBsaXN0IG9mIGludGVydmFscy4KICAgIE9uZSBzaW5nbGUgaW50ZXJ2YWwgaXMganVzdCBhIHBhaXIuCiAgICBPdmVybGFwcGluZyBvciB0b3VjaGluZyBpbnRlcnZhbHMgYXJlIGF1dG9tYXRpY2FsbHkgbWVyZ2VkLgogICAgIiIiCgogICAgZGVmIF9faW5pdF9fKHNlbGYsIGludGVydmFsX2xpc3Q9KCkpOgogICAgICAgICIiIlJhaXNlcyBhIFZhbHVlRXJyb3IgaWYgdGhlIGxlbmd0aCBvZiBvbmUgb2YgdGhlCiAgICAgICAgaW50ZXJ2YWxzIGluIHRoZSBsaXN0IGlzIG5lZ2F0aXZlLgogICAgICAgICIiIgogICAgICAgIGlmIGFueShiZWdpbiA+IGVuZCBmb3IgYmVnaW4sIGVuZCBpbiBpbnRlcnZhbF9saXN0KToKICAgICAgICAgICAgICAgIHJhaXNlIFZhbHVlRXJyb3IoJ0ludmFsaWQgaW50ZXJ2YWwnKQogICAgICAgIHNlbGYuX2ludGVydmFsX2xpc3QgPSBfbWVyZ2VfaW50ZXJ2YWxfbGlzdHMoCiAgICAgICAgICAgICAgICBpbnRlcnZhbF9saXN0LCBbXSwgT1BfVU5JT04pCgogICAgZGVmIF9fcmVwcl9fKHNlbGYpOgogICAgICAgICIiIkp1c3Qgd3JpdGUgb3V0IGFsbCBpbmNsdWRlZCBpbnRlcnZhbHMuCiAgICAgICAgIiIiCiAgICAgICAgcmV0dXJuICdJbnRlcnZhbHMgJyArIHN0cihzZWxmLl9pbnRlcnZhbF9saXN0KQoKICAgIGRlZiBnZXQoc2VsZiwgY29weV9jb250ZW50PVRydWUpOgogICAgICAgICIiIlJldHVybiB0aGUgbGlzdCBvZiBpbnRlcnZhbHMuCiAgICAgICAgIiIiCiAgICAgICAgcmV0dXJuIGNvcHkuY29weShzZWxmLl9pbnRlcnZhbF9saXN0KSBpZiBjb3B5X2NvbnRlbnRcCiAgICAgICAgICAgICAgICBlbHNlIHNlbGYuX2ludGVydmFsX2xpc3QKCgpkZWYgdW5pb24oYSwgYik6CiAgICAiIiJNZXJnZSBhIGFuZCBiICh1bmlvbikuCiAgICAiIiIKICAgIHJldHVybiBJbnRlcnZhbHMoX21lcmdlX2ludGVydmFsX2xpc3RzKAogICAgICAgIGEuZ2V0KEZhbHNlKSwgYi5nZXQoRmFsc2UpLCBPUF9VTklPTikpCgpkZWYgaW50ZXJzZWN0aW9ucyhhLCBiKToKICAgICIiIkludGVyc2VjdHMgYSBhbmQgYi4KICAgICIiIgogICAgcmV0dXJuIEludGVydmFscyhfbWVyZ2VfaW50ZXJ2YWxfbGlzdHMoCiAgICAgICAgIGEuZ2V0KEZhbHNlKSwgYi5nZXQoRmFsc2UpLCBtZXJnZV90eXBlPU9QX0lOVEVSU0VDVElPTlMpKQoKZGVmIHNldF9kaWZmZXJlbmNlKGEsIGIpOgogICAgIiIiUmVtb3ZlcyBiIGZyb20gYS4KICAgIFNldCBkaWZmZXJlbmNlIGlzIG5vdCBjb21tdXRhdGl2ZS4KICAgICIiIgogICAgcmV0dXJuIEludGVydmFscyhfbWVyZ2VfaW50ZXJ2YWxfbGlzdHMoCiAgICAgICAgICAgIGEuZ2V0KEZhbHNlKSwgYi5nZXQoRmFsc2UpLCBtZXJnZV90eXBlPU9QX1NFVF9ESUZGRVJFTkNFKSkKCmRlZiBzeW1tZXRyaWNfZGlmZmVyZW5jZShhLCBiKToKICAgICIiIlN5bW1ldHJpYyBkaWZmZXJlbmNlIG9mIGEgYW5kIGIuCiAgICAiIiIKICAgIHJldHVybiBJbnRlcnZhbHMoX21lcmdlX2ludGVydmFsX2xpc3RzKAogICAgICAgICAgICBhLmdldChGYWxzZSksIGIuZ2V0KEZhbHNlKSwgbWVyZ2VfdHlwZT1PUF9TWU1NRVRSSUNfRElGRkVSRU5DRSkpCgoKZGVmIGNvbXBvc2UoZnVuY18xLCBmdW5jXzIsIHVucGFjaz1GYWxzZSk6CiAgICAiIiIKICAgIGNvbXBvc2UoZnVuY18xLCBmdW5jXzIsIHVucGFjaz1GYWxzZSkgLT4gZnVuY3Rpb24KCiAgICBUaGUgZnVuY3Rpb24gcmV0dXJuZWQgYnkgY29tcG9zZSBpcyBhIGNvbXBvc2l0aW9uIG9mIGZ1bmNfMSBhbmQgZnVuY18yLgogICAgVGhhdCBpcywgY29tcG9zZShmdW5jXzEsIGZ1bmNfMikoNSkgPT0gZnVuY18xKGZ1bmNfMig1KSkuCiAgICAiIiIKICAgIGlmIG5vdCBjYWxsYWJsZShmdW5jXzEpOgogICAgICAgIHJhaXNlIFR5cGVFcnJvcigiRmlyc3QgYXJndW1lbnQgdG8gY29tcG9zZSBtdXN0IGJlIGNhbGxhYmxlLiIpCiAgICBpZiBub3QgY2FsbGFibGUoZnVuY18yKToKICAgICAgICByYWlzZSBUeXBlRXJyb3IoIlNlY29uZCBhcmd1bWVudCB0byBjb21wb3NlIG11c3QgYmUgY2FsbGFibGUuIikKCiAgICBpZiB1bnBhY2s6CiAgICAgICAgZGVmIGNvbXBvc2l0aW9uKCphcmdzLCAqKmt3YXJncyk6CiAgICAgICAgICAgIHJldHVybiBmdW5jXzEoKmZ1bmNfMigqYXJncywgKiprd2FyZ3MpKQogICAgZWxzZToKICAgICAgICBkZWYgY29tcG9zaXRpb24oKmFyZ3MsICoqa3dhcmdzKToKICAgICAgICAgICAgcmV0dXJuIGZ1bmNfMShmdW5jXzIoKmFyZ3MsICoqa3dhcmdzKSkKICAgIHJldHVybiBjb21wb3NpdGlvbgoKCiMgSGVscGVyIHRvIGF2b2lkIHJlcGV0aXRpdmUgbGFtYmRhcy4KZGVmIGNoZWNrX2Zvcihjb25kKToKICAgIHJldHVybiBsYW1iZGEgdmFsOiB2YWwgPT0gY29uZAoKIyBodHRwOi8vZS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYS5vcmcvd2lraS9JZGVudGl0eV9mdW5jdGlvbgppZGVudGl0eSA9IGxhbWJkYSB4OiB4CgoKIyBEZXBlbmRpbmcgb24gdGhlIG9wZXJhdGlvbiBjYXJyaWVkIG91dCwKIyB0aGUgY3JpdGVyaWEgZm9yIGludGVydmFsIGJlZ2lucyBhbmQgZW5kcyBpbiB0aGUgcmVzdWx0IGRpZmZlci4KIyBFLmc6CiMgICAgICBhID0gfCAtIC0gLSAtIHwgICAgICB8IC0gLSAtIHwKIyAgICAgIGIgPSAgICAgfCAtIC0gLSAtIHwKIyBjb3VudHMgPSAxICAgMiAgICAgMSAgIDAgIDEgICAgICAgMCAgICh1bmlvbiwgaW50ZXJzZWN0aW9uLCBzeW0gZGlmZikKIyBjb3VudHMgPSAxICAgMCAgICAtMSAgIDAgIDEgICAgICAgMCAgIChzZXQgZGlmZikKIyB1bmlvbiAgPSB8IC0gLSAtIC0gLSAtIHwgIHwgLSAtIC0gfAojIGludGVyICA9ICAgICB8IC0gLSAtIC0gfAojIHN5bSBkICA9ICAgICAgICAgICB8IC0gfAojIHNldCBkICA9IHwgLSB8ICAgICAgICAgICAgfCAtIC0gLSB8CiMKIyBPbmUgY2FuIHNlZSB0aGF0IHVuaW9uIGJlZ2lucyBpZiB0aGUgY291bnQgY2hhbmdlcyBmcm9tIDAgdG8gMQojIGFuZCBlbmRzIGlmIHRoZSBjb3VudCBjaGFuZ2VzIGZyb20gMSB0byAwCiMgQW4gaW50ZXJzZWN0aW9uIGJlZ2lucyBhdCBhIGNoYW5nZSBmcm9tIDEgdG8gMiBhbmQgZW5kcyB3aXRoIDIgdG8gMS4KIyBBIHN5bW1ldHJpYyBkaWZmZXJlbmNlIGJlZ2lucyBhdCBldmVyeSBjaGFuZ2UgdG8gb25lCiMgYW5kIGVuZHMgYXQgZXZlcnkgY2hhbmdlIGF3YXkgZnJvbSBvbmUuCiMgVGhlIGNvbmRpdGlvbnMgZm9yIHRoZSBzZXQgZGlmZmVyZW5jZSBhcmUgdGhlIHNhbWUgYXMgZm9yIHRoZSB1bmlvbi4Kc2V0X29wID0gbmFtZWR0dXBsZSgnc2V0X29wJywgWyd0cmFuc2Zvcm0nLCAnYmVnaW4nLCAnZW5kJ10pCgpPUF9VTklPTiA9IHNldF9vcCgKICAgIHRyYW5zZm9ybSA9IGlkZW50aXR5LAogICAgYmVnaW4gPSBjaGVja19mb3IoKDAsIDEpKSwKICAgIGVuZCA9IGNoZWNrX2ZvcigoMSwgMCkpKQoKT1BfSU5URVJTRUNUSU9OUyA9IHNldF9vcCgKICAgIHRyYW5zZm9ybSA9IGlkZW50aXR5LAogICAgYmVnaW4gPSBjaGVja19mb3IoKDEsIDIpKSwKICAgIGVuZCA9IGNoZWNrX2ZvcigoMiwgMSkpKQoKT1BfU1lNTUVUUklDX0RJRkZFUkVOQ0UgPSBzZXRfb3AoCiAgICB0cmFuc2Zvcm0gPSBpZGVudGl0eSwKICAgIGJlZ2luID0gbGFtYmRhIGNoYW5nZTogY2hhbmdlWzFdID09IDEsCiAgICBlbmQgPSBsYW1iZGEgY2hhbmdlOiBjaGFuZ2VbMV0gIT0gMSkKCk9QX1NFVF9ESUZGRVJFTkNFID0gc2V0X29wKAogICAgIyBJZiB3ZSB3YW50IHRvIGNhbGN1bGF0ZSB0aGUgc2V0IGRpZmZlcmVuY2UKICAgICMgd2UgaW52ZXJ0IHRoZSBzZWNvbmQgaW50ZXJ2YWwgbGlzdCwKICAgICMgaS5lLiBzd2FwIGJlZ2luIGFuZCBlbmQuCiAgICB0cmFuc2Zvcm0gPSBjb21wb3NlKHR1cGxlLCByZXZlcnNlZCksCiAgICBiZWdpbiA9IGNoZWNrX2ZvcigoMCwgMSkpLAogICAgZW5kID0gY2hlY2tfZm9yKCgxLCAwKSkpCgoKIyBjbGFzcyBJbnRlcnZhbHMgbWFrZXMgc3VyZSwgYnkgYWx3YXlzIGJ1aWxkaW5nIHRoZSB1bmlvbiBmaXJzdCwKIyB0aGF0IG5vIGludmFsaWQgYSdzIG9yIGIncyBhcmUgZmVkIGhlcmUuCmRlZiBfbWVyZ2VfaW50ZXJ2YWxfbGlzdHMoYSwgYiwgbWVyZ2VfdHlwZSk6CiAgICAiIiJNZXJnZXMgdHdvIGxpc3RzIG9mIGludGVydmFscyBpbiBPKG4qbG9nKG4pKS4KICAgIE92ZXJsYXBwaW5nIG9yIHRvdWNoaW5nIGludGVydmFscyBhcmUgc2ltcGxpZmllZCB0byBvbmUuCgogICAgQXJndW1lbnRzOgogICAgYSBhbmQgYiAtLSBUaGUgaW50ZXJ2YWwgbGlzdHMgdG8gbWVyZ2UuCiAgICBtZXJnZV90eXBlIC0tIENhbiBiZToKICAgICAgICAgICAgICAgICAgT1BfVU5JT04sCiAgICAgICAgICAgICAgICAgIE9QX0lOVEVSU0VDVElPTlMsCiAgICAgICAgICAgICAgICAgIE9QX1NZTU1FVFJJQ19ESUZGRVJFTkNFLCBvcgogICAgICAgICAgICAgICAgICBPUF9TRVRfRElGRkVSRU5DRS4KCiAgICBSZXR1cm4gdGhlIHNvcnRlZCByZXN1bHQgYXMgYSBsaXN0LgogICAgIiIiCgogICAgIyBBZGp1c3QgdGhlIG9wZXJhbmQgZm9yIHRoZSBzZWxlY3RlZCBvcGVyYXRvci4KICAgIGIgPSBtYXAobWVyZ2VfdHlwZS50cmFuc2Zvcm0sIGIpCgogICAgIyBTZXBhcmF0ZWx5IHNvcnQgYmVnaW5zIGFuZCBlbmRzCiAgICAjIGFuZCBwYWlyIHRoZW0gd2l0aCB0aGUgaW1wbGllZCBjaGFuZ2UKICAgICMgb2YgdGhlIGNvdW50IG9mIGN1cnJlbnRseSBvcGVuIGludGVydmFscy4KICAgICMgZS5nLiAoMSwgNCksICg3LCA5KSwgKDMsIDUpIC0+CiAgICAjICAgICBiZWdpbnMgPSBbKDEsIDEpLCAoMywgMSksICg3LCAxKV0KICAgICMgICAgIGVuZHMgPSBbKDQsIC0xKSwgKDUsIC0xKSwgKDksIC0xKV0KICAgIGJvdGggPSBsaXN0KGNoYWluKGEsIGIpKQogICAgYmVnaW5zID0gemlwKHNvcnRlZChtYXAoaXRlbWdldHRlcigwKSwgYm90aCkpLAogICAgICAgICAgICByZXBlYXQoMSkpCiAgICBlbmRzID0gemlwKHNvcnRlZChtYXAoaXRlbWdldHRlcigxKSwgYm90aCkpLAogICAgICAgICAgICByZXBlYXQoLTEpKQoKICAgICMgU29ydCBiZWdpbnMgYW5kIGVuZHMgdG9nZXRoZXIuCiAgICAjIElmIHRoZSB2YWx1ZSBpcyB0aGUgc2FtZSwgYmVnaW5zIGNvbWUgYmVmb3JlIGVuZHMKICAgICMgdG8gZW5zdXJlIHRvdWNoaW5nIGludGVydmFscyBiZWluZyBtZXJnZWQgdG8gb25lLgogICAgIyBJbiBvdXIgZXhhbXBsZSBhYm92ZSB0aGlzIG1lYW5zOgogICAgIyBlZGdlcyA9IFsoMSwgNCksICgzLCAxKSwgKDQsIC0xKSwgKDUsIC0xKSwgKDcsIDEpLCAoOSwgLTEpXQogICAgZWRnZXMgPSBzb3J0ZWQoY2hhaW4oYmVnaW5zLCBlbmRzKSwga2V5PWxhbWJkYSB4OiAoeFswXSwgLXhbMV0pKQoKICAgICMgVGhlIG51bWJlciBvZiBvcGVuZWQgaW50ZXJ2YWxzIGFmdGVyIGVhY2ggZWRnZS4KICAgIGNvdW50cyA9IGxpc3QoYWNjdW11bGF0ZShtYXAoaXRlbWdldHRlcigxKSwgZWRnZXMpKSkKICAgICMgVGhlIGNoYW5nZXMgb2Ygb3BlbmVkIGludGVydmFscyBhdCBlYWNoIGVkZ2UuCiAgICBjaGFuZ2VzID0gemlwKGNoYWluKFswXSwgY291bnRzKSwgY291bnRzKQogICAgIyBKdXN0IHRoZSB4IHBvc2l0aW9ucyBvZiB0aGUgZWRnZXMuCiAgICB4cyA9IG1hcChpdGVtZ2V0dGVyKDApLCBlZGdlcykKICAgIHhzX2FuZF9jaGFuZ2VzID0gbGlzdCh6aXAoeHMsIGNoYW5nZXMpKQoKICAgICMgTm93IHdlIGZpbHRlciBvdXQgdGhlIGJlZ2lucyBhbmQgZW5kcyBmcm9tIHRoZSBjaGFuZ2VzCiAgICAjIGFuZCBnZXQgdGhlaXIgeCBwb3NpdGlvbnMuCiAgICByZXNfYmVnaW5zID0gbWFwKGl0ZW1nZXR0ZXIoMCksCiAgICAgICAgICAgIHN0YXJmaWx0ZXIobGFtYmRhIHgsIGNoYW5nZTogbWVyZ2VfdHlwZS5iZWdpbihjaGFuZ2UpLAogICAgICAgICAgICAgICAgeHNfYW5kX2NoYW5nZXMpKQogICAgcmVzX2VuZHMgPSBtYXAoaXRlbWdldHRlcigwKSwKICAgICAgICAgICAgc3RhcmZpbHRlcihsYW1iZGEgeCwgY2hhbmdlOiBtZXJnZV90eXBlLmVuZChjaGFuZ2UpLAogICAgICAgICAgICAgICAgeHNfYW5kX2NoYW5nZXMpKQoKICAgICMgVGhlIHJlc3VsdCBpcyB0aGVuIGp1c3QgcGFpcmluZyB1cCB0aGUgc29ydGVkIGJlZ2lucyBhbmQgZW5kcy4KICAgIHJlc3VsdCA9IHBhaXJ3aXNlKHNvcnRlZChjaGFpbihyZXNfYmVnaW5zLCByZXNfZW5kcykpLCBGYWxzZSkKCiAgICAjIE5vIGVtcHR5IGludGVydmFscyBpbiB0aGUgcmVzdWx0LgogICAgZGVmIGxlbmd0aF9ncmVhdGVyX3RoYW5femVybyhpbnRlcnZhbCk6CiAgICAgICAgcmV0dXJuIGludGVydmFsWzBdIDwgaW50ZXJ2YWxbMV0KCiAgICByZXR1cm4gbGlzdChmaWx0ZXIobGVuZ3RoX2dyZWF0ZXJfdGhhbl96ZXJvLCByZXN1bHQpKQoKCmNsYXNzIFRlc3RJbnRlcnZhbHModW5pdHRlc3QuVGVzdENhc2UpOgoKICAgIGRlZiB0ZXN0X2N0b3Ioc2VsZik6CiAgICAgICAgIyBDaGVjayBjdG9ycyBzYW5pdHkgY2hlY2suCiAgICAgICAgc2VsZi5hc3NlcnRSYWlzZXMoVmFsdWVFcnJvciwgSW50ZXJ2YWxzLCBbKDIsIDQpLCAoMywgMSldKQoKICAgIGRlZiB0ZXN0X2FkZF9iZWhpbmQoc2VsZik6CiAgICAgICAgIyBDaGVjayBhZGRpbmcgcmlnaHQgb2YgdGhlIGxhc3QgaW50ZXJ2YWwuCiAgICAgICAgaW50ZXJ2YWxzID0gSW50ZXJ2YWxzKFsoMCwgMildKQogICAgICAgIGludGVydmFscyA9IHVuaW9uKGludGVydmFscywgSW50ZXJ2YWxzKFsoMywgNCldKSkKICAgICAgICBzZWxmLmFzc2VydEVxdWFsKGludGVydmFscy5nZXQoKSwgWygwLCAyKSwgKDMsIDQpXSkKCiAgICBkZWYgdGVzdF9hZGRfaW5fZnJvbnQoc2VsZik6CiAgICAgICAgIyBDaGVjayBhZGRpbmcgbGVmdCB0byB0aGUgZmlyc3QgaW50ZXJ2YWwuCiAgICAgICAgaW50ZXJ2YWxzID0gSW50ZXJ2YWxzKFsoMywgNCldKQogICAgICAgIGludGVydmFscyA9IHVuaW9uKGludGVydmFscywgSW50ZXJ2YWxzKFsoMSwgMildKSkKICAgICAgICBzZWxmLmFzc2VydEVxdWFsKGludGVydmFscy5nZXQoKSwgWygxLCAyKSwgKDMsIDQpXSkKCiAgICBkZWYgdGVzdF9hZGRfaW5fYmV0d2VlbihzZWxmKToKICAgICAgICAjIENoZWNrIGFkZGluZyBiZXR3ZWVuIHR3byBpbnRlcnZhbHMuCiAgICAgICAgaW50ZXJ2YWxzID0gSW50ZXJ2YWxzKFsoMSwgMildKQogICAgICAgIGludGVydmFscyA9IHVuaW9uKGludGVydmFscywgSW50ZXJ2YWxzKFsoNiwgOSldKSkKICAgICAgICBpbnRlcnZhbHMgPSB1bmlvbihpbnRlcnZhbHMsIEludGVydmFscyhbKDMsIDUpXSkpCiAgICAgICAgc2VsZi5hc3NlcnRFcXVhbChpbnRlcnZhbHMuZ2V0KCksIFsoMSwgMiksICgzLCA1KSwgKDYsIDkpXSkKCiAgICBkZWYgdGVzdF9hZGRfdG91Y2hpbmcoc2VsZik6CiAgICAgICAgIyBDaGVjayBhZGRpbmcgYSBpbnRlcnZhbCB0b3VjaGluZyBhbiBleGlzdGluZyBvbmUuCiAgICAgICAgaW50ZXJ2YWxzID0gSW50ZXJ2YWxzKFsoMSwgMyldKQogICAgICAgIGludGVydmFscyA9IHVuaW9uKGludGVydmFscywgSW50ZXJ2YWxzKFsoMywgNSldKSkKICAgICAgICBzZWxmLmFzc2VydEVxdWFsKGludGVydmFscy5nZXQoKSwgWygxLCA1KV0pCgogICAgZGVmIHRlc3RfYWRkX292ZXJsYXBwaW5nKHNlbGYpOgogICAgICAgICMgQ2hlY2sgYWRkaW5nIGEgaW50ZXJ2YWwgb3ZlcmxhcHBpbmcgYW4gZXhpc3Rpbmcgb25lLgogICAgICAgIGludGVydmFscyA9IEludGVydmFscyhbKDEsIDQpXSkKICAgICAgICBpbnRlcnZhbHMgPSB1bmlvbihpbnRlcnZhbHMsIEludGVydmFscyhbKDMsIDUpXSkpCiAgICAgICAgc2VsZi5hc3NlcnRFcXVhbChpbnRlcnZhbHMuZ2V0KCksIFsoMSwgNSldKQoKICAgIGRlZiB0ZXN0X2FkZF9vdmVybGFwcGluZ19tdWx0aXBsZShzZWxmKToKICAgICAgICAjIENoZWNrIGFkZGluZyBhIGludGVydmFsIG92ZXJsYXBwaW5nIG11bHRpcGxlIGV4aXN0aW5nIG9uZXMuCiAgICAgICAgaW50ZXJ2YWxzID0gSW50ZXJ2YWxzKFsoMSwgNCldKQogICAgICAgIGludGVydmFscyA9IHVuaW9uKGludGVydmFscywgSW50ZXJ2YWxzKFsoNSwgNyldKSkKICAgICAgICBpbnRlcnZhbHMgPSB1bmlvbihpbnRlcnZhbHMsIEludGVydmFscyhbKDgsIDEwKV0pKQogICAgICAgIGludGVydmFscyA9IHVuaW9uKGludGVydmFscywgSW50ZXJ2YWxzKFsoMywgOSldKSkKICAgICAgICBzZWxmLmFzc2VydEVxdWFsKGludGVydmFscy5nZXQoKSwgWygxLCAxMCldKQoKICAgIGRlZiB0ZXN0X2FkZF9zd2FsbG93KHNlbGYpOgogICAgICAgICMgQ2hlY2sgYWRkaW5nIGEgaW50ZXJ2YWwgY29tcGxldGVseSBjb3ZlcmluZyBhbiBleGlzdGluZyBvbmUuCiAgICAgICAgaW50ZXJ2YWxzID0gSW50ZXJ2YWxzKFsoMiwgMyldKQogICAgICAgIGludGVydmFscyA9IHVuaW9uKGludGVydmFscywgSW50ZXJ2YWxzKFsoMSwgNCldKSkKICAgICAgICBzZWxmLmFzc2VydEVxdWFsKGludGVydmFscy5nZXQoKSwgWygxLCA0KV0pCgogICAgZGVmIHRlc3Rfc3ViKHNlbGYpOgogICAgICAgICMgQ2hlY2sgcmVtb3ZpbmcgYW4gaW50ZXJ2YWwKICAgICAgICBpbnRlcnZhbHMgPSBJbnRlcnZhbHMoWygwLCAzKV0pCiAgICAgICAgaW50ZXJ2YWxzID0gdW5pb24oaW50ZXJ2YWxzLCBJbnRlcnZhbHMoWyg1LCA3KV0pKQogICAgICAgIGludGVydmFscyA9IHNldF9kaWZmZXJlbmNlKGludGVydmFscywgSW50ZXJ2YWxzKFsoMiwgNildKSkKICAgICAgICBzZWxmLmFzc2VydEVxdWFsKGludGVydmFscy5nZXQoKSwgWygwLCAyKSwgKDYsIDcpXSkKCiAgICBkZWYgdGVzdF9pbnRlcnNlY3Rpb25zKHNlbGYpOgogICAgICAgICMgQ2hlY2sgYWRkaW5nIHJpZ2h0IG9mIHRoZSBsYXN0IGludGVydmFsLgogICAgICAgIGludGVydmFscyA9IEludGVydmFscyhbKDAsIDMpXSkKICAgICAgICBpbnRlcnZhbHMgPSB1bmlvbihpbnRlcnZhbHMsIEludGVydmFscyhbKDUsIDcpXSkpCiAgICAgICAgaW50ZXJ2YWxzID0gaW50ZXJzZWN0aW9ucyhpbnRlcnZhbHMsIEludGVydmFscyhbKDIsIDYpXSkpCiAgICAgICAgc2VsZi5hc3NlcnRFcXVhbChpbnRlcnZhbHMuZ2V0KCksIFsoMiwgMyksICg1LCA2KV0pCgogICAgZGVmIHRlc3Rfc3ltbWV0cmljX2RpZmZlcmVuY2Uoc2VsZik6CiAgICAgICAgIyBDaGVjayBzeW1tZXRyaWMgZGlmZmVyZW5jZQogICAgICAgIGludGVydmFscyA9IEludGVydmFscyhbKDAsIDMpXSkKICAgICAgICBpbnRlcnZhbHMgPSB1bmlvbihpbnRlcnZhbHMsIEludGVydmFscyhbKDUsIDcpXSkpCiAgICAgICAgaW50ZXJ2YWxzID0gc3ltbWV0cmljX2RpZmZlcmVuY2UoaW50ZXJ2YWxzLCBJbnRlcnZhbHMoWygyLCA2KV0pKQogICAgICAgIHNlbGYuYXNzZXJ0RXF1YWwoaW50ZXJ2YWxzLmdldCgpLCBbKDAsIDIpLCAoMywgNSksICg2LCA3KV0pCgoKCmRlZiB0dXBsZV93aXNlKGl0ZXJhYmxlLCBzaXplLCBzdGVwKToKICAgICIiIlR1cGxlcyB1cCB0aGUgZWxlbWVudHMgb2YgaXRlcmFibGUuCgogICAgQXJndW1lbnRzOgogICAgaXRlcmFibGUgLS0gc291cmNlIGRhdGEKICAgIHNpemUgLS0gc2l6ZSBvZiB0aGUgZGVzdGluYXRpb24gdHVwbGVzCiAgICBzdGVwIC0tIHN0ZXAgdG8gZG8gaW4gaXRlcmFibGUgcGVyIGRlc3RpbmF0aW9uIHR1cGxlCgogICAgdHVwbGVfd2lzZShzLCAzLCAxKTogInMgLT4gKHMwLHMxLHMyKSwgKHMxLHMyLHMzKSwgKHMzLHM0LHM1KSwgLi4uCiAgICB0dXBsZV93aXNlKHMsIDIsIDQpOiAicyAtPiAoczAsczEpLCAoczQsczUpLCAoczgsczkpLCAuLi4KICAgICIiIgogICAgcmV0dXJuIHppcCgKICAgICAgICAgICAgKihpc2xpY2UoaXRlcmFibGUsIHN0YXJ0LCBOb25lLCBzdGVwKQogICAgICAgICAgICBmb3Igc3RhcnQgaW4gcmFuZ2Uoc2l6ZSkpKQoKZGVmIHBhaXJ3aXNlKGl0ZXJhYmxlLCBvdmVybGFwcGluZyk6CiAgICAiIiJQYWlycyB1cCB0aGUgZWxlbWVudHMgb2YgaXRlcmFibGUuCiAgICBvdmVybGFwcGluZzogInMgLT4gKHMwLHMxKSwgKHMyLHMzKSwgKHM0LHM1KSwgLi4uCiAgICBub3Qgb3ZlcmxhcHBpbmc6ICJzIC0+IChzMCxzMSksIChzMSxzMiksIChzMixzMyksIC4uLgogICAgIiIiCiAgICByZXR1cm4gdHVwbGVfd2lzZShpdGVyYWJsZSwgMiwgMSBpZiBvdmVybGFwcGluZyBlbHNlIDIpCgpkZWYgc3RhcmZpbHRlcihmdW5jdGlvbiwgaXRlcmFibGUpOgogICAgIiIic3RhcmZpbHRlciA8LS0+IGZpbHRlciAgPT0gIHN0YXJtYXAgPC0tPiBtYXAiIiIKICAgIHJldHVybiAoaXRlbSBmb3IgaXRlbSBpbiBpdGVyYWJsZSBpZiBmdW5jdGlvbigqaXRlbSkpCgoKaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoKICAgIHVuaXR0ZXN0Lm1haW4odmVyYm9zaXR5PTIp