<s> class R_NORELATION : <EOL> code = - <NUM_LIT:1> <EOL> r = None <EOL> def stra ( self , a ) : <EOL> return '<STR_LIT>' % a <EOL> class R_IDENTITY : <EOL> code = <NUM_LIT:0> <EOL> def stra ( self , a ) : <EOL> return a <EOL> class R_ATTRIBUTE : <EOL> code = <NUM_LIT:1> <EOL> strpat = '<STR_LIT>' <EOL> class R_INDEXVAL : <EOL> code = <NUM_LIT:2> <EOL> def stra ( self , a ) : <EOL> return '<STR_LIT>' % ( a , self . saferepr ( self . r ) ) <EOL> class R_INDEXKEY : <EOL> code = <NUM_LIT:3> <EOL> strpat = '<STR_LIT>' <EOL> class R_INTERATTR : <EOL> code = <NUM_LIT:4> <EOL> strpat = '<STR_LIT>' <EOL> class R_HASATTR : <EOL> code = <NUM_LIT:5> <EOL> strpat = '<STR_LIT>' <EOL> class R_LOCAL_VAR : <EOL> code = <NUM_LIT:6> <EOL> strpat = '<STR_LIT>' <EOL> class R_CELL : <EOL> code = <NUM_LIT:7> <EOL> strpat = '<STR_LIT>' <EOL> class R_STACK : <EOL> code = <NUM_LIT:8> <EOL> strpat = '<STR_LIT>' <EOL> class R_RELSRC : <EOL> code = <NUM_LIT:9> <EOL> def stra ( self , a ) : return self . r % ( a , ) <EOL> class R_LIMIT : <EOL> code = <NUM_LIT:10> <EOL> class RelationBase ( object ) : <EOL> __slots__ = '<STR_LIT:r>' , '<STR_LIT>' <EOL> def __init__ ( self , r , isinverted = <NUM_LIT:0> ) : <EOL> self . r = r <EOL> self . isinverted = isinverted <EOL> def __cmp__ ( self , other ) : <EOL> if isinstance ( other , RelationBase ) : <EOL> if self . code != other . code : <EOL> return cmp ( self . code , other . code ) <EOL> return cmp ( self . r , other . r ) <EOL> else : <EOL> return cmp ( type ( self ) , type ( other ) ) <EOL> def __str__ ( self ) : <EOL> return self . stra ( '<STR_LIT:%s>' ) <EOL> def inverted ( self ) : <EOL> x = self . __class__ ( self . r , not self . isinverted ) <EOL> def stra ( self , a ) : <EOL> return self . strpat % ( a , self . r ) <EOL> class MultiRelation ( RelationBase ) : <EOL> def __init__ ( self , rels ) : <EOL> self . rels = rels <EOL> def stra ( self , a ) : <EOL> return '<STR_LIT:<>' + '<STR_LIT:U+002C>' . join ( [ x . stra ( a ) for x in self . rels ] ) + '<STR_LIT:>>' <EOL> class Path : <EOL> def __init__ ( self , mod , path , index , output , srcname ) : <EOL> self . mod = mod <EOL> self . path = path [ <NUM_LIT:1> : ] <EOL> self . index = index <EOL> self . output = output <EOL> self . src = path [ <NUM_LIT:1> ] <EOL> self . tgt = path [ - <NUM_LIT:1> ] <EOL> self . strprefix = '<STR_LIT:%s>' <EOL> if srcname == '<STR_LIT>' : <EOL> srcname = self . src . brief <EOL> if callable ( srcname ) : <EOL> srcname = srcname ( self ) <EOL> self . srcname = srcname <EOL> def __cmp__ ( self , other ) : <EOL> return cmp ( str ( self ) , str ( other ) ) <EOL> def __len__ ( self ) : <EOL> return int ( ( len ( self . path ) - <NUM_LIT:1> ) / <NUM_LIT:2> ) <EOL> def __str__ ( self ) : <EOL> if self . path : <EOL> a = self . path [ <NUM_LIT:0> ] <EOL> s = self . strprefix <EOL> for i in range ( <NUM_LIT:1> , len ( self . path ) , <NUM_LIT:2> ) : <EOL> r = self . path [ i ] <EOL> s = r . stra ( s ) <EOL> else : <EOL> s = '<STR_LIT>' <EOL> return s <EOL> def __repr__ ( self ) : <EOL> return repr ( str ( self ) ) <EOL> def pp ( self , output = None ) : <EOL> if output is None : <EOL> output = self . output <EOL> print >> output , '<STR_LIT>' % self . index , str ( self ) % self . srcname <EOL> def types ( self ) : <EOL> return [ type ( x ) for x in self . path ] <EOL> class PathsIter : <EOL> def __init__ ( self , paths , start = None , stop = None ) : <EOL> self . paths = paths <EOL> self . mod = paths . mod <EOL> self . stop = stop <EOL> self . reset ( start ) <EOL> def __iter__ ( self ) : <EOL> return self <EOL> def reset ( self , idx = None ) : <EOL> if idx is None : <EOL> idx = <NUM_LIT:0> <EOL> if idx != <NUM_LIT:0> : <EOL> ln = self . paths . numpaths <EOL> if idx < <NUM_LIT:0> : <EOL> idx = ln + idx <EOL> if not ( <NUM_LIT:0> <= idx < ln ) : <EOL> self . isatend = <NUM_LIT:1> <EOL> return <EOL> Src = self . paths . Src <EOL> sr = [ ( '<STR_LIT:%s>' , src . by ( Src . er ) ) for src in Src . byid . parts ] <EOL> srs = [ ] <EOL> idxs = [ ] <EOL> np = <NUM_LIT:0> <EOL> while sr : <EOL> if idx == <NUM_LIT:0> : <EOL> i , ( rel , src ) = <NUM_LIT:0> , sr [ <NUM_LIT:0> ] <EOL> else : <EOL> for i , ( rel , src ) in enumerate ( sr ) : <EOL> npnext = np + self . paths . numpaths_from ( src ) <EOL> if idx < npnext : <EOL> break <EOL> np = npnext <EOL> else : <EOL> assert <NUM_LIT:0> <EOL> idxs . append ( i ) <EOL> srs . append ( sr ) <EOL> sr = self . mod . sortedrels ( self . paths . IG , src ) <EOL> self . pos = idx <EOL> self . idxs = idxs <EOL> self . srs = srs <EOL> self . isatend = not idxs <EOL> def next ( self ) : <EOL> paths = self . paths <EOL> if ( self . isatend or <EOL> self . stop is not None and self . pos >= self . stop ) : <EOL> raise StopIteration <EOL> path = [ ] <EOL> for row , col in enumerate ( self . idxs ) : <EOL> sr = self . srs [ row ] <EOL> if sr is None : <EOL> sr = self . mod . sortedrels ( paths . IG , path [ - <NUM_LIT:1> ] ) <EOL> self . srs [ row ] = sr <EOL> rel , dst = sr [ col ] <EOL> path . append ( rel ) <EOL> path . append ( dst ) <EOL> rp = self . mod . Path ( paths , path , self . pos , paths . output , paths . srcname ) <EOL> self . pos += <NUM_LIT:1> <EOL> while row >= <NUM_LIT:0> : <EOL> self . idxs [ row ] += <NUM_LIT:1> <EOL> if self . idxs [ row ] < len ( self . srs [ row ] ) : <EOL> break <EOL> if row > <NUM_LIT:0> : <EOL> self . srs [ row ] = None <EOL> self . idxs [ row ] = <NUM_LIT:0> <EOL> row -= <NUM_LIT:1> <EOL> else : <EOL> self . isatend = <NUM_LIT:1> <EOL> self . pos = <NUM_LIT:0> <EOL> return rp <EOL> class MorePrinter : <EOL> def __init__ ( self , top , prev = None ) : <EOL> self . top = top <EOL> if prev is None : <EOL> prev = top <EOL> self . prev = prev <EOL> self . mod = top . mod <EOL> self . firstpath = self . prev . firstpath + self . maxpaths <EOL> self . _hiding_tag_ = self . mod . _hiding_tag_ <EOL> def __call__ ( self , start = None , output = None ) : <EOL> it = self . moreiterator <EOL> if it is None : <EOL> it = self . iter ( start ) <EOL> else : <EOL> if start is not None : <EOL> it . reset ( start ) <EOL> self . printiter ( it , output ) <EOL> def __getattr__ ( self , attr ) : <EOL> if attr == '<STR_LIT>' : <EOL> return MorePrinter ( self . top , self ) <EOL> else : <EOL> return getattr ( self . top , attr ) <EOL> def __repr__ ( self ) : <EOL> it = self . iter ( self . firstpath ) <EOL> output = self . top . mod . _root . StringIO . StringIO ( ) <EOL> self . printiter ( it , output ) <EOL> x = output . getvalue ( ) . rstrip ( ) <EOL> if not x : <EOL> x = '<STR_LIT>' <EOL> return x <EOL> def __str__ ( self ) : <EOL> return self . __repr__ ( ) <EOL> class ShortestPaths : <EOL> firstpath = <NUM_LIT:0> <EOL> maxpaths = <NUM_LIT:10> <EOL> def __init__ ( self , sg , Dst ) : <EOL> self . sg = sg <EOL> self . Dst = Dst <EOL> self . mod = mod = sg . mod <EOL> self . _hiding_tag_ = mod . _hiding_tag_ <EOL> self . srcname = sg . srcname <EOL> self . output = mod . output <EOL> self . moreiterator = None <EOL> self . top = self <EOL> self . IG = IG = mod . nodegraph ( ) <EOL> Edges = [ ] <EOL> Y = Dst . nodes <EOL> while Y : <EOL> R = sg . G . domain_restricted ( Y ) <EOL> R . invert ( ) <EOL> IG . update ( R ) <EOL> Edges . append ( R ) <EOL> Y = R . get_domain ( ) <EOL> if Edges : <EOL> Edges . pop ( ) <EOL> Edges . reverse ( ) <EOL> self . Src = mod . idset ( Edges [ <NUM_LIT:0> ] . get_domain ( ) ) <EOL> else : <EOL> self . Src = mod . iso ( ) <EOL> self . edges = tuple ( Edges ) <EOL> sets = [ ] <EOL> for i , e in enumerate ( Edges ) : <EOL> if i == <NUM_LIT:0> : <EOL> sets . append ( mod . idset ( e . get_domain ( ) ) ) <EOL> sets . append ( mod . idset ( e . get_range ( ) ) ) <EOL> self . sets = tuple ( sets ) <EOL> self . more = MorePrinter ( self ) <EOL> def __getitem__ ( self , idx ) : <EOL> try : <EOL> return self . iter ( start = idx ) . next ( ) <EOL> except StopIteration : <EOL> raise IndexError <EOL> def __iter__ ( self ) : <EOL> return self . iter ( ) <EOL> def __repr__ ( self ) : <EOL> f = self . mod . _root . StringIO . StringIO ( ) <EOL> self . pp ( output = f ) <EOL> return f . getvalue ( ) . rstrip ( ) <EOL> def __str__ ( self ) : <EOL> return self . __repr__ ( ) <EOL> def iter ( self , start = <NUM_LIT:0> , stop = None ) : <EOL> return PathsIter ( self , start , stop ) <EOL> def aslist ( self , maxpaths = None , firstpath = None ) : <EOL> if maxpaths is None : <EOL> maxpaths = self . maxpaths <EOL> if firstpath is None : <EOL> firstpath = self . firstpath <EOL> li = list ( self . iter ( firstpath , firstpath + maxpaths ) ) <EOL> if len ( li ) >= maxpaths : <EOL> more = ( self . numpaths - ( firstpath + len ( li ) ) ) <EOL> if more : <EOL> li . append ( '<STR_LIT>' % more ) <EOL> return li <EOL> def copy_but_avoid_edges_at_levels ( self , * args ) : <EOL> avoid = self . edges_at ( * args ) . updated ( self . sg . AvoidEdges ) <EOL> assert avoid . _hiding_tag_ is self . mod . _hiding_tag_ <EOL> return self . mod . shpaths ( self . Dst , self . Src , avoid_edges = avoid ) <EOL> avoided = copy_but_avoid_edges_at_levels <EOL> def depth ( self ) : <EOL> pass <EOL> def edges_at ( self , * args ) : <EOL> E = self . mod . nodegraph ( ) <EOL> for col in args : <EOL> E . update ( self . edges [ col ] ) <EOL> assert E . _hiding_tag_ == self . mod . _parent . View . _hiding_tag_ <EOL> return E <EOL> def numpaths_from ( self , Src ) : <EOL> try : <EOL> NP = self . NP <EOL> except AttributeError : <EOL> NP = self . mod . nodegraph ( is_mapping = True ) <EOL> NP . add_edges_n1 ( self . IG . get_domain ( ) , None ) <EOL> for dst in self . Dst . nodes : <EOL> NP . add_edge ( dst , <NUM_LIT:1> ) <EOL> self . NP = NP <EOL> numedges = self . mod . hv . numedges <EOL> IG = self . IG <EOL> def np ( y ) : <EOL> n = NP [ y ] <EOL> if n is None : <EOL> n = <NUM_LIT:0> <EOL> for z in IG [ y ] : <EOL> sn = NP [ z ] <EOL> if sn is None : <EOL> sn = np ( z ) <EOL> n += sn * numedges ( y , z ) <EOL> NP [ y ] = n <EOL> return n <EOL> num = <NUM_LIT:0> <EOL> for src in Src . nodes : <EOL> num += np ( src ) <EOL> return num <EOL> def _get_numpaths ( self ) : <EOL> num = self . numpaths_from ( self . Src ) <EOL> self . numpaths = num <EOL> return num <EOL> numpaths = property ( fget = _get_numpaths ) <EOL> def pp ( self , start = None , output = None ) : <EOL> self . moreiterator = None <EOL> self . more ( start , output = output ) <EOL> def printiter ( self , it , output = None ) : <EOL> if output is None : <EOL> output = self . output <EOL> self . moreiterator = it <EOL> i = <NUM_LIT:0> <EOL> lastindex = None <EOL> while i < self . maxpaths : <EOL> try : <EOL> el = it . next ( ) <EOL> except StopIteration : <EOL> it . reset ( <NUM_LIT:0> ) <EOL> break <EOL> el . pp ( output = output ) <EOL> i += <NUM_LIT:1> <EOL> lastindex = el . index <EOL> else : <EOL> if lastindex is not None : <EOL> nummore = self . numpaths - ( lastindex + <NUM_LIT:1> ) <EOL> if nummore == <NUM_LIT:1> : <EOL> it . next ( ) . pp ( output = output ) <EOL> elif nummore > <NUM_LIT:1> : <EOL> print >> output , '<STR_LIT>' % nummore <EOL> class ShortestGraph : <EOL> def __init__ ( self , mod , G , DstSets , Src , AvoidEdges , <EOL> srcname = None , dstname = None ) : <EOL> self . mod = mod <EOL> self . G = G <EOL> self . Src = Src <EOL> self . DstSets = DstSets <EOL> self . AvoidEdges = AvoidEdges <EOL> if srcname is None : <EOL> if Src . count == <NUM_LIT:1> : <EOL> srcname = mod . srcname_1 <EOL> else : <EOL> srcname = mod . srcname_n <EOL> self . srcname = srcname <EOL> if dstname is None : <EOL> dstname = mod . dstname <EOL> self . dstname = dstname <EOL> def __getitem__ ( self , idx ) : <EOL> return self . mod . ShortestPaths ( self , self . DstSets [ idx ] ) <EOL> def __len__ ( self ) : <EOL> return len ( self . DstSets ) <EOL> def __str__ ( self ) : <EOL> f = self . mod . _root . StringIO . StringIO ( ) <EOL> self . pp ( f ) <EOL> return f . getvalue ( ) <EOL> def pp ( self , output = None ) : <EOL> if output is None : <EOL> output = self . mod . output <EOL> for i , p in enumerate ( self ) : <EOL> print >> output , '<STR_LIT>' % ( self . dstname , i ) <EOL> p . pp ( output = output ) <EOL> class _GLUECLAMP_ : <EOL> _preload_ = ( '<STR_LIT>' , ) <EOL> _chgable_ = ( '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ) <EOL> srcname_1 = '<STR_LIT>' <EOL> srcname_n = '<STR_LIT>' <EOL> dstname = '<STR_LIT>' <EOL> _imports_ = ( <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> ) <EOL> def _get_rel_table ( self ) : <EOL> table = { } <EOL> for name in dir ( self . _module ) : <EOL> if name . startswith ( '<STR_LIT>' ) : <EOL> c = getattr ( self , name ) <EOL> class r ( c , self . RelationBase ) : <EOL> saferepr = self . saferepr <EOL> r . __name__ = '<STR_LIT>' + name <EOL> table [ c . code ] = r <EOL> return table <EOL> def _get__hiding_tag_ ( self ) : return self . _parent . View . _hiding_tag_ <EOL> def _get_identity ( self ) : return R_IDENTITY ( ) <EOL> def _get_norelation ( self ) : return R_NORELATION ( ) <EOL> def _get_output ( self ) : return self . _parent . OutputHandling . stdout <EOL> def _get_saferepr ( self ) : return self . _root . repr . repr <EOL> def _get_shpathstep ( self ) : return self . hv . shpathstep <EOL> def sortedrels ( self , IG , Src ) : <EOL> t = [ ] <EOL> iso = self . iso <EOL> for src in Src . nodes : <EOL> for dst in IG [ src ] : <EOL> Dst = iso ( dst ) <EOL> for rel in self . relations ( src , dst ) : <EOL> t . append ( ( rel , Dst ) ) <EOL> t . sort ( lambda ( rel1 , dst1 ) , ( rel2 , dst2 ) : cmp ( rel1 , rel2 ) ) <EOL> return t <EOL> def prunedinverted ( self , G , Y ) : <EOL> IG = self . nodegraph ( ) <EOL> while Y : <EOL> R = G . domain_restricted ( Y ) <EOL> R . invert ( ) <EOL> IG . update ( R ) <EOL> Y = R . get_domain ( ) <EOL> return IG <EOL> def relation ( self , src , dst ) : <EOL> tab = self . relations ( src , dst ) <EOL> if len ( tab ) > <NUM_LIT:1> : <EOL> r = MultiRelation ( tab ) <EOL> elif not tab : <EOL> r = self . norelation <EOL> else : <EOL> r = tab [ <NUM_LIT:0> ] <EOL> return r <EOL> def relations ( self , src , dst ) : <EOL> tab = [ ] <EOL> if src is dst : <EOL> tab . append ( self . identity ) <EOL> rawrel = self . hv . relate ( src , dst ) <EOL> for i , rs in enumerate ( rawrel ) : <EOL> for r in rs : <EOL> tab . append ( self . rel_table [ i ] ( r ) ) <EOL> if not tab : <EOL> tab = [ self . norelation ] <EOL> return tab <EOL> def shpaths ( self , dst , src = None , avoid_nodes = None , avoid_edges = ( ) ) : <EOL> return self . shpgraph ( [ dst ] , src , avoid_nodes , avoid_edges ) [ <NUM_LIT:0> ] <EOL> def shpgraph ( self , DstSets , src = None , avoid_nodes = None , avoid_edges = ( ) , <EOL> srcname = None , dstname = None ) : <EOL> if src is None : <EOL> Src = self . iso ( self . View . root ) <EOL> if srcname is None and self . View . root is self . View . heapyc . RootState : <EOL> srcname = '<STR_LIT>' % self . reprefix <EOL> else : <EOL> Src = self . idset_adapt ( src ) <EOL> if avoid_nodes is None : <EOL> AvoidNodes = self . Nothing <EOL> else : <EOL> AvoidNodes = self . idset_adapt ( avoid_nodes ) <EOL> AvoidEdges = self . nodegraph ( avoid_edges ) <EOL> G , DstSets = self . shpgraph_algorithm ( DstSets , Src , AvoidNodes , AvoidEdges ) <EOL> return self . ShortestGraph ( self , G , DstSets , Src , AvoidEdges , <EOL> srcname , dstname ) <EOL> def shpgraph_algorithm ( self , DstSets , Src , AvoidNodes , AvoidEdges ) : <EOL> U = ( Src - AvoidNodes ) . nodes <EOL> S = self . mutnodeset ( AvoidNodes . nodes ) <EOL> G = self . nodegraph ( ) <EOL> unseen = list ( enumerate ( DstSets ) ) <EOL> DstSets = [ self . Nothing ] * len ( DstSets ) <EOL> while U and unseen : <EOL> S |= U <EOL> U = self . shpathstep ( G , U , S , AvoidEdges ) <EOL> unseen_ = [ ] <EOL> for i , D in unseen : <EOL> D_ = D & U <EOL> if D_ : <EOL> DstSets [ i ] = D_ <EOL> else : <EOL> unseen_ . append ( ( i , D ) ) <EOL> unseen = unseen_ <EOL> return G , [ self . idset_adapt ( D ) for D in DstSets ] <EOL> class _Specification_ : <EOL> class GlueTypeExpr : <EOL> exec ( """<STR_LIT>""" . replace ( '<STR_LIT>' , '<STR_LIT>' ) ) </s>
