Mercurial > traipse_dev
annotate upmana/mercurial/ancestor.py @ 179:5609ac142298 alpha
Traipse Alpha 'OpenRPG' {100114-03}
Traipse is a distribution of OpenRPG that is designed to be easy to
setup and go. Traipse also makes it easy for developers to work on code
without fear of sacrifice. 'Ornery-Orc' continues the trend of 'Grumpy'
and adds fixes to the code. 'Ornery-Orc's main goal is to offer more
advanced features and enhance the productivity of the user.
Update Summary (Keeping up with Beta)
New Features:
Added Bookmarks
Added 'boot' command to remote admin
Added confirmation window for sent nodes
Minor changes to allow for portability to an OpenSUSE linux OS
Miniatures Layer pop up box allows users to turn off Mini labels, from
FlexiRPG
Zoom Mouse plugin added
Images added to Plugin UI
Switching to Element Tree
Map efficiency, from FlexiRPG
Added Status Bar to Update Manager
New TrueDebug Class in orpg_log (See documentation for usage)
Portable Mercurial
Tip of the Day added, from Core and community
New Reference Syntax added for custom PC sheets
New Child Reference for gametree
New Parent Reference for gametree
New Gametree Recursion method, mapping, context sensitivity, and
effeciency..
New Features node with bonus nodes and Node Referencing help added
Dieroller structure from Core
New DieRoller portability for odd Dice
Added 7th Sea die roller; ie [7k3] = [7d10.takeHighest(3).open(10)]
New 'Mythos' System die roller added
Added new vs. die roller method for WoD; ie [3v3] = [3d10.vs(3)].
Included for Mythos roller also
New Warhammer FRPG Die Roller (Special thanks to Puu-san for the
support)
New EZ_Tree Reference system. Push a button, Traipse the tree, get a
reference (Beta!)
Fixes:
Fix to Text based Server
Fix to Remote Admin Commands
Fix to Pretty Print, from Core
Fix to Splitter Nodes not being created
Fix to massive amounts of images loading, from Core
Fix to Map from gametree not showing to all clients
Fix to gametree about menus
Fix to Password Manager check on startup
Fix to PC Sheets from tool nodes. They now use the tabber_panel
Fix to Whiteboard ID to prevent random line or text deleting.
Fixes to Server, Remote Server, and Server GUI
Fix to Update Manager; cleaner clode for saved repositories
Fixes made to Settings Panel and now reactive settings when Ok is
pressed
Fixes to Alternity roller's attack roll. Uses a simple Tuple instead of
a Splice
Fix to Use panel of Forms and Tabbers. Now longer enters design mode
Fix made Image Fetching. New fetching image and new failed image
Modified ID's to prevent non updated clients from ruining the fix.
default_manifest.xml renamed to default_upmana.xml
| author | sirebral |
|---|---|
| date | Thu, 14 Jan 2010 21:22:21 -0600 |
| parents | 496dbf12a6cb |
| children |
| rev | line source |
|---|---|
| 121 | 1 # ancestor.py - generic DAG ancestor algorithm for mercurial |
| 2 # | |
| 3 # Copyright 2006 Matt Mackall <mpm@selenic.com> | |
| 4 # | |
| 5 # This software may be used and distributed according to the terms of the | |
| 6 # GNU General Public License version 2, incorporated herein by reference. | |
| 7 | |
| 8 import heapq | |
| 9 | |
| 10 def ancestor(a, b, pfunc): | |
| 11 """ | |
| 12 return the least common ancestor of nodes a and b or None if there | |
| 13 is no such ancestor. | |
| 14 | |
| 15 pfunc must return a list of parent vertices | |
| 16 """ | |
| 17 | |
| 18 if a == b: | |
| 19 return a | |
| 20 | |
| 21 # find depth from root of all ancestors | |
| 22 parentcache = {} | |
| 23 visit = [a, b] | |
| 24 depth = {} | |
| 25 while visit: | |
| 26 vertex = visit[-1] | |
| 27 pl = pfunc(vertex) | |
| 28 parentcache[vertex] = pl | |
| 29 if not pl: | |
| 30 depth[vertex] = 0 | |
| 31 visit.pop() | |
| 32 else: | |
| 33 for p in pl: | |
| 34 if p == a or p == b: # did we find a or b as a parent? | |
| 35 return p # we're done | |
| 36 if p not in depth: | |
| 37 visit.append(p) | |
| 38 if visit[-1] == vertex: | |
| 39 depth[vertex] = min([depth[p] for p in pl]) - 1 | |
| 40 visit.pop() | |
| 41 | |
| 42 # traverse ancestors in order of decreasing distance from root | |
| 43 def ancestors(vertex): | |
| 44 h = [(depth[vertex], vertex)] | |
| 45 seen = set() | |
| 46 while h: | |
| 47 d, n = heapq.heappop(h) | |
| 48 if n not in seen: | |
| 49 seen.add(n) | |
| 50 yield (d, n) | |
| 51 for p in parentcache[n]: | |
| 52 heapq.heappush(h, (depth[p], p)) | |
| 53 | |
| 54 def generations(vertex): | |
| 55 sg, s = None, set() | |
| 56 for g, v in ancestors(vertex): | |
| 57 if g != sg: | |
| 58 if sg: | |
| 59 yield sg, s | |
| 60 sg, s = g, set((v,)) | |
| 61 else: | |
| 62 s.add(v) | |
| 63 yield sg, s | |
| 64 | |
| 65 x = generations(a) | |
| 66 y = generations(b) | |
| 67 gx = x.next() | |
| 68 gy = y.next() | |
| 69 | |
| 70 # increment each ancestor list until it is closer to root than | |
| 71 # the other, or they match | |
| 72 try: | |
| 73 while 1: | |
| 74 if gx[0] == gy[0]: | |
| 75 for v in gx[1]: | |
| 76 if v in gy[1]: | |
| 77 return v | |
| 78 gy = y.next() | |
| 79 gx = x.next() | |
| 80 elif gx[0] > gy[0]: | |
| 81 gy = y.next() | |
| 82 else: | |
| 83 gx = x.next() | |
| 84 except StopIteration: | |
| 85 return None |