Mercurial > traipse_dev
annotate upmana/mercurial/ancestor.py @ 190:15488fe94f52 beta
Traipse Beta 'OpenRPG' {100125-01}
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 (Beta)
New Features:
New Bookmarks Feature
New 'boot' command to remote admin
New confirmation window for sent nodes
Miniatures Layer pop up box allows users to turn off Mini labels, from
FlexiRPG
New Zoom Mouse plugin added
New Images added to Plugin UI
Switching to Element Tree
New Map efficiency, from FlexiRPG
New Status Bar to Update Manager
New TrueDebug Class in orpg_log (See documentation for usage)
New Portable Mercurial
New Tip of the Day, 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
New Dieroller structure from Core
New DieRoller portability for odd Dice
New 7th Sea die roller; ie [7k3] = [7d10.takeHighest(3).open(10)]
New 'Mythos' System die roller 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!)
New Grids act more like Spreadsheets in Use mode, with Auto Calc
Fixes:
Fix to allow for portability to an OpenSUSE linux OS
Fix to mplay_client for Fedora and OpenSUSE
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
Fix to whiteboard ID's to prevent non updated clients from ruining the
fix.
default_manifest.xml renamed to default_upmana.xml
| author | sirebral |
|---|---|
| date | Mon, 25 Jan 2010 12:07:48 -0600 |
| parents | dcf4fbe09b70 |
| children |
| rev | line source |
|---|---|
| 135 | 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 |