[Checkins] SVN: hurry.resource/trunk/src/hurry/resource/ Actually add a working topological sort algorithm with test.
Martijn Faassen
faassen at infrae.com
Tue Sep 23 14:14:10 EDT 2008
Log message for revision 91402:
Actually add a working topological sort algorithm with test.
Changed:
U hurry.resource/trunk/src/hurry/resource/README.txt
U hurry.resource/trunk/src/hurry/resource/__init__.py
U hurry.resource/trunk/src/hurry/resource/core.py
-=-
Modified: hurry.resource/trunk/src/hurry/resource/README.txt
===================================================================
--- hurry.resource/trunk/src/hurry/resource/README.txt 2008-09-23 17:30:19 UTC (rev 91401)
+++ hurry.resource/trunk/src/hurry/resource/README.txt 2008-09-23 18:14:10 UTC (rev 91402)
@@ -233,7 +233,6 @@
>>> a2 = ResourceInclusion(foo, 'a2.js', depends=[a1])
>>> a3 = ResourceInclusion(foo, 'a3.js', depends=[a2])
>>> a4 = ResourceInclusion(foo, 'a4.js', depends=[a1])
- >>> a5 = ResourceInclusion(foo, 'a5.js', depends=[a4, a3])
>>> needed.need(a3)
>>> needed.inclusions()
[<ResourceInclusion 'a1.js' in library 'foo'>,
@@ -292,42 +291,42 @@
a minified and a debug version. Let's define a resource that exists in
two modes (a main one and a debug alternative)::
- >>> a1 = ResourceInclusion(foo, 'a.js', debug='a-debug.js')
+ >>> k1 = ResourceInclusion(foo, 'k.js', debug='k-debug.js')
Let's need this resource::
>>> needed = NeededInclusions()
- >>> needed.need(a1)
+ >>> needed.need(k1)
-By default, we get ``a.js``::
+By default, we get ``k.js``::
>>> needed.inclusions()
- [<ResourceInclusion 'a.js' in library 'foo'>]
+ [<ResourceInclusion 'k.js' in library 'foo'>]
We can however also get the resource for mode ``debug`` and get
-``a-debug.js``::
+``k-debug.js``::
>>> needed.inclusions(mode='debug')
- [<ResourceInclusion 'a-debug.js' in library 'foo'>]
+ [<ResourceInclusion 'k-debug.js' in library 'foo'>]
Modes can also be specified fully with a resource inclusion, which allows
you to specify a different ``library`` and ``part_of`` argumnent::
- >>> a2 = ResourceInclusion(foo, 'a2.js',
- ... debug=ResourceInclusion(foo, 'a2-debug.js'))
+ >>> k2 = ResourceInclusion(foo, 'k2.js',
+ ... debug=ResourceInclusion(foo, 'k2-debug.js'))
>>> needed = NeededInclusions()
- >>> needed.need(a2)
+ >>> needed.need(k2)
-By default we get ``a2.js``::
+By default we get ``k2.js``::
>>> needed.inclusions()
- [<ResourceInclusion 'a2.js' in library 'foo'>]
+ [<ResourceInclusion 'k2.js' in library 'foo'>]
We can however also get the resource for mode ``debug`` and get
``a2-debug.js``::
>>> needed.inclusions(mode='debug')
- [<ResourceInclusion 'a2-debug.js' in library 'foo'>]
+ [<ResourceInclusion 'k2-debug.js' in library 'foo'>]
Note that modes are assumed to be identical in dependency structure;
they functionally should do the same.
@@ -452,3 +451,24 @@
<link rel="stylesheet" type="text/css" href="http://localhost/static/foo/b.css" />
<script type="text/javascript" src="http://localhost/static/foo/a.js"></script>
<script type="text/javascript" src="http://localhost/static/foo/c.js"></script>
+
+Sorting inclusions by dependency
+--------------------------------
+
+This is more a footnote than something that you should be concerned
+about. In case assumptions in this library are wrong or there are
+other reasons you would like to sort resource inclusions that come in
+some arbitrary order into one where the dependency relation makes
+sense, you can use ``sort_inclusions_topological``::
+
+ >>> from hurry.resource import sort_inclusions_topological
+
+Let's make a list of resource inclusions not sorted by dependency::
+
+ >>> i = [a5, a3, a1, a2, a4]
+ >>> sort_inclusions_topological(i)
+ [<ResourceInclusion 'a1.js' in library 'foo'>,
+ <ResourceInclusion 'a4.js' in library 'foo'>,
+ <ResourceInclusion 'a2.js' in library 'foo'>,
+ <ResourceInclusion 'a3.js' in library 'foo'>,
+ <ResourceInclusion 'a5.js' in library 'foo'>]
Modified: hurry.resource/trunk/src/hurry/resource/__init__.py
===================================================================
--- hurry.resource/trunk/src/hurry/resource/__init__.py 2008-09-23 17:30:19 UTC (rev 91401)
+++ hurry.resource/trunk/src/hurry/resource/__init__.py 2008-09-23 18:14:10 UTC (rev 91402)
@@ -1 +1,2 @@
-from hurry.resource.core import (Library, ResourceInclusion, NeededInclusions)
+from hurry.resource.core import (Library, ResourceInclusion, NeededInclusions,
+ sort_inclusions_topological)
Modified: hurry.resource/trunk/src/hurry/resource/core.py
===================================================================
--- hurry.resource/trunk/src/hurry/resource/core.py 2008-09-23 17:30:19 UTC (rev 91401)
+++ hurry.resource/trunk/src/hurry/resource/core.py 2008-09-23 18:14:10 UTC (rev 91402)
@@ -121,7 +121,9 @@
inclusions = apply_mode(inclusions, mode)
inclusions = consolidate(inclusions)
- inclusions = sort_inclusions(inclusions)
+ # sort only by extension, not dependency, as we can rely on
+ # python's stable sort to keep inclusion order intact
+ inclusions = sort_inclusions_by_extension(inclusions)
inclusions = remove_duplicates(inclusions)
return inclusions
@@ -176,32 +178,37 @@
result.append(inclusion)
return result
-def sort_inclusions(inclusions):
-# XXX this is not necessary as we can rely on Python's stable
-# sort to get the right order for inclusions.
+def sort_inclusions_by_extension(inclusions):
-# depend_sortkey = {}
-# for inclusion in inclusions:
-# for d in inclusion.depends:
-# c = depend_sortkey.get(d.key(), 0)
-# c += 1
-# depend_sortkey[d.key()] = c
-
-# depend_sortkey2 = {}
-# for inclusion in inclusions:
-# v = depend_sortkey.get(inclusion.key(), 0)
-# for d in inclusion.depends:
-# c = depend_sortkey2.get(d.key(), 0)
-# c += v
-# depend_sortkey2[d.key()] = c
-
def key(inclusion):
return EXTENSIONS.index(inclusion.ext())
- #, -depend_sortkey2.get(inclusion.key(), 0))
- # this relies on stable sorting in Python
return sorted(inclusions, key=key)
+def sort_inclusions_topological(inclusions):
+ """Sort inclusions by dependency.
+
+ Note that this is not actually used in the system, but can be used
+ to resort inclusions in case sorting order is lost - or if the
+ assumptions in this library turn out to be incorrect.
+ """
+ dead = {}
+ result = []
+ for inclusion in inclusions:
+ dead[inclusion.key()] = False
+
+ for inclusion in inclusions:
+ _visit(inclusion, result, dead)
+ return result
+
+def _visit(inclusion, result, dead):
+ if dead[inclusion.key()]:
+ return
+ dead[inclusion.key()] = True
+ for depend in inclusion.depends:
+ _visit(depend, result, dead)
+ result.append(inclusion)
+
def render_css(url):
return ('<link rel="stylesheet" type="text/css" href="%s" />' %
url)
More information about the Checkins
mailing list