"""Heap queue algorithm (a.k.a. priority queue).
Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for
all k, counting elements from 0. For the sake of comparison,
non-existing elements are considered to be infinite. The interesting
property of a heap is that a[0] is always its smallest element.
Usage:
heap = [] # creates an empty heap
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
item = heap[0] # smallest item on the heap without popping it
heapify(x) # transforms list into a heap, in-place, in linear time
item = heapreplace(heap, item) # pops and returns smallest item, and adds
# new item; the heap size is unchanged
Our API differs from textbook heap algorithms as follows:
- We use 0-based indexing. This makes the relationship between the
index for a node and the indexes for its children slightly less
obvious, but is more suitable since Python uses 0-based indexing.
- Our heappop() method returns the smallest item, not the largest.
These two make it possible to view the heap as a regular Python list
without surprises: heap[0] is the smallest item, and heap.sort()
maintains the heap invariant!
"""
# Original code by Kevin O'Connor, augmented by Tim Peters and Raymond Hettinger
__about__ = """Heap queues
[explanation by François Pinard]
Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for
all k, counting elements from 0. For the sake of comparison,
non-existing elements are considered to be infinite. The interesting
property of a heap is that a[0] is always its smallest element.
The strange invariant above is meant to be an efficient memory
representation for a tournament. The numbers below are `k', not a[k]:
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In
a usual binary tournament we see in sports, each cell is the winner
over the two cells it tops, and we can trace the winner down the tree
to see all opponents s/he had. However, in many computer applications
of such tournaments, we do not need to trace the history of a winner.
To be more memory efficient, when a winner is promoted, we try to
replace it by something else at a lower level, and the rule becomes
that a cell and the two cells it tops contain three different items,
but the top cell "wins" over the two topped cells.
If this heap invariant is protected at all time, index 0 is clearly
the overall winner. The simplest algorithmic way to remove it and
find the "next" winner is to move some loser (let's say cell 30 in the
diagram above) into the 0 position, and then percolate this new 0 down
the tree, exchanging values, until the invariant is re-established.
This is clearly logarithmic on the total number of items in the tree.
By iterating over all items, you get an O(n ln n) sort.
A nice feature of this sort is that you can efficiently insert new
items while the sort is going on, provided that the inserted items are
not "better" than the last 0'th element you extracted. This is
especially useful in simulation contexts, where the tree holds all
incoming events, and the "win" condition means the smallest scheduled
time. When an event schedule other events for execution, they are
scheduled into the future, so they can easily go into the heap. So, a
heap is a good structure for implementing schedulers (this is what I
used for my MIDI sequencer :-).
Various structures for implementing schedulers have been extensively
studied, and heaps are good for this, as they are reasonably speedy,
the speed is almost constant, and the worst case is not much different
than the average case. However, there are other representations which
are more efficient overall, yet the worst cases might be terrible.
Heaps are also very useful in big disk sorts. You most probably all
know that a big sort implies producing "runs" (which are pre-sorted
sequences, which size is usually related to the amount of CPU memory),
followed by a merging passes for these runs, which merging is often
very cleverly organised[1]. It is very important that the initial
sort produces the longest runs possible. Tournaments are a good way
to that. If, using all the memory available to hold a tournament, you
replace and percolate items that happen to fit the current run, you'll
produce runs which are twice the size of the memory for random input,
and much better for input fuzzily ordered.
Moreover, if you output the 0'th item on disk and get an input which
may not fit in the current tournament (because the value "wins" over
the last output value), it cannot fit in the heap, so the size of the
heap decreases. The freed memory could be cleverly reused immediately
for progressively building a second heap, which grows at exactly the
same rate the first heap is melting. When the first heap completely
vanishes, you switch heaps and start a new run. Clever and quite
effective!
In a word, heaps are useful memory structures to know. I use them in
a few applications, and I think it is good to keep a `heap' module
around. :-)
--------------------
[1] The disk balancing algorithms which are current, nowadays, are
more annoying than clever, and this is a consequence of the seeking
capabilities of the disks. On devices which cannot seek, like big
tape drives, the story was quite different, and one had to be very
clever to ensure (far in advance) that each tape movement will be the
most effective possible (that is, will best participate at
"progressing" the merge). Some tapes were even able to read
backwards, and this was also used to avoid the rewinding time.
Believe me, real good tape sorts were quite spectacular to watch!
From all times, sorting has always been a Great Art! :-)
"""
__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
'nlargest', 'nsmallest', 'heappushpop']
def heappush(heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
_siftdown(heap, 0, len(heap)-1)
def heappop(heap):
"""Pop the smallest item off the heap, maintaining the heap invariant."""
lastelt = heap.pop() # raises appropriate IndexError if heap is empty
if heap:
returnitem = heap[0]
heap[0] = lastelt
_siftup(heap, 0)
return returnitem
return lastelt
def heapreplace(heap, item):
"""Pop and return the current smallest value, and add the new item.
This is more efficient than heappop() followed by heappush(), and can be
more appropriate when using a fixed-size heap. Note that the value
returned may be larger than item! That constrains reasonable uses of
this routine unless written as part of a conditional replacement:
if item > heap[0]:
item = heapreplace(heap, item)
"""
returnitem = heap[0] # raises appropriate IndexError if heap is empty
heap[0] = item
_siftup(heap, 0)
return returnitem
def heappushpop(heap, item):
"""Fast version of a heappush followed by a heappop."""
if heap and heap[0] < item:
item, heap[0] = heap[0], item
_siftup(heap, 0)
return item
def heapify(x):
"""Transform list into a heap, in-place, in O(len(x)) time."""
n = len(x)
# Transform bottom-up. The largest index there's any point to looking at
# is the largest with a child index in-range, so must have 2*i + 1 < n,
# or i < (n-1)/2. If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
# j-1 is the largest, which is n//2 - 1. If n is odd = 2*j+1, this is
# (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
for i in reversed(range(n//2)):
_siftup(x, i)
def _heappop_max(heap):
"""Maxheap version of a heappop."""
lastelt = heap.pop() # raises appropriate IndexError if heap is empty
if heap:
returnitem = heap[0]
heap[0] = lastelt
_siftup_max(heap, 0)
return returnitem
return lastelt
def _heapreplace_max(heap, item):
"""Maxheap version of a heappop followed by a heappush."""
returnitem = heap[0] # raises appropriate IndexError if heap is empty
heap[0] = item
_siftup_max(heap, 0)
return returnitem
def _heapify_max(x):
"""Transform list into a maxheap, in-place, in O(len(x)) time."""
n = len(x)
for i in reversed(range(n//2)):
_siftup_max(x, i)
# 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
# is the index of a leaf with a possibly out-of-order value. Restore the
# heap invariant.
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if newitem < parent:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
# The child indices of heap index pos are already heaps, and we want to make
# a heap at index pos too. We do this by bubbling the smaller child of
# pos up (and so on with that child's children, etc) until hitting a leaf,
# then using _siftdown to move the oddball originally at index pos into place.
#
# We *could* break out of the loop as soon as we find a pos where newitem <=
# both its children, but turns out that's not a good idea, and despite that
# many books write the algorithm that way. During a heap pop, the last array
# element is sifted in, and that tends to be large, so that comparing it
# against values starting from the root usually doesn't pay (= usually doesn't
# get us out of the loop early). See Knuth, Volume 3, where this is
# explained and quantified in an exercise.
#
# Cutting the # of comparisons is important, since these routines have no
# way to extract "the priority" from an array element, so that intelligence
# is likely to be hiding in custom comparison methods, or in array elements
# storing (priority, record) tuples. Comparisons are thus potentially
# expensive.
#
# On random arrays of length 1000, making this change cut the number of
# comparisons made by heapify() a little, and those made by exhaustive
# heappop() a lot, in accord with theory. Here are typical results from 3
# runs (3 just to demonstrate how small the variance is):
#
# Compares needed by heapify Compares needed by 1000 heappops
# -------------------------- --------------------------------
# 1837 cut to 1663 14996 cut to 8680
# 1855 cut to 1659 14966 cut to 8678
# 1847 cut to 1660 15024 cut to 8703
#
# Building the heap by using heappush() 1000 times instead required
# 2198, 2148, and 2219 compares: heapify() is more efficient, when
# you can use it.
#
# The total compares needed by list.sort() on the same lists were 8627,
# 8627, and 8632 (this should be compared to the sum of heapify() and
# heappop() compares): list.sort() is (unsurprisingly!) more efficient
# for sorting.
def _siftup(heap, pos):
endpos = len(heap)
startpos = pos
newitem = heap[pos]
# Bubble up the smaller child until hitting a leaf.
childpos = 2*pos + 1 # leftmost child position
while childpos < endpos:
# Set childpos to index of smaller child.
rightpos = childpos + 1
if rightpos < endpos and not heap[childpos] < heap[rightpos]:
childpos = rightpos
# Move the smaller child up.
heap[pos] = heap[childpos]
pos = childpos
childpos = 2*pos + 1
# The leaf at pos is empty now. Put newitem there, and bubble it up
# to its final resting place (by sifting its parents down).
heap[pos] = newitem
_siftdown(heap, startpos, pos)
def _siftdown_max(heap, startpos, pos):
'Maxheap variant of _siftdown'
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if parent < newitem:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
def _siftup_max(heap, pos):
'Maxheap variant of _siftup'
endpos = len(heap)
startpos = pos
newitem = heap[pos]
# Bubble up the larger child until hitting a leaf.
childpos = 2*pos + 1 # leftmost child position
while childpos < endpos:
# Set childpos to index of larger child.
rightpos = childpos + 1
if rightpos < endpos and not heap[rightpos] < heap[childpos]:
childpos = rightpos
# Move the larger child up.
heap[pos] = heap[childpos]
pos = childpos
childpos = 2*pos + 1
# The leaf at pos is empty now. Put newitem there, and bubble it up
# to its final resting place (by sifting its parents down).
heap[pos] = newitem
_siftdown_max(heap, startpos, pos)
def merge(*iterables, key=None, reverse=False):
'''Merge multiple sorted inputs into a single sorted output.
Similar to sorted(itertools.chain(*iterables)) but returns a generator,
does not pull the data into memory all at once, and assumes that each of
the input streams is already sorted (smallest to largest).
>>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
[0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]
If *key* is not None, applies a key function to each element to determine
its sort order.
>>> list(merge(['dog', 'horse'], ['cat', 'fish', 'kangaroo'], key=len))
['dog', 'cat', 'fish', 'horse', 'kangaroo']
'''
h = []
h_append = h.append
if reverse:
_heapify = _heapify_max
_heappop = _heappop_max
_heapreplace = _heapreplace_max
direction = -1
else:
_heapify = heapify
_heappop = heappop
_heapreplace = heapreplace
direction = 1
if key is None:
for order, it in enumerate(map(iter, iterables)):
try:
next = it.__next__
h_append([next(), order * direction, next])
except StopIteration:
pass
_heapify(h)
while len(h) > 1:
try:
while True:
value, order, next = s = h[0]
yield value
s[0] = next() # raises StopIteration when exhausted
_heapreplace(h, s) # restore heap condition
except StopIteration:
_heappop(h) # remove empty iterator
if h:
# fast case when only a single iterator remains
value, order, next = h[0]
yield value
yield from next.__self__
return
for order, it in enumerate(map(iter, iterables)):
try:
next = it.__next__
value = next()
h_append([key(value), order * direction, value, next])
except StopIteration:
pass
_heapify(h)
while len(h) > 1:
try:
while True:
key_value, order, value, next = s = h[0]
yield value
value = next()
s[0] = key(value)
s[2] = value
_heapreplace(h, s)
except StopIteration:
_heappop(h)
if h:
key_value, order, value, next = h[0]
yield value
yield from next.__self__
# Algorithm notes for nlargest() and nsmallest()
# ==============================================
#
# Make a single pass over the data while keeping the k most extreme values
# in a heap. Memory consumption is limited to keeping k values in a list.
#
# Measured performance for random inputs:
#
# number of comparisons
# n inputs k-extreme values (average of 5 trials) % more than min()
# ------------- ---------------- --------------------- -----------------
# 1,000 100 3,317 231.7%
# 10,000 100 14,046 40.5%
# 100,000 100 105,749 5.7%
# 1,000,000 100 1,007,751 0.8%
# 10,000,000 100 10,009,401 0.1%
#
# Theoretical number of comparisons for k smallest of n random inputs:
#
# Step Comparisons Action
# ---- -------------------------- ---------------------------
# 1 1.66 * k heapify the first k-inputs
# 2 n - k compare remaining elements to top of heap
# 3 k * (1 + lg2(k)) * ln(n/k) replace the topmost value on the heap
# 4 k * lg2(k) - (k/2) final sort of the k most extreme values
#
# Combining and simplifying for a rough estimate gives:
#
# comparisons = n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))
#
# Computing the number of comparisons for step 3:
# -----------------------------------------------
# * For the i-th new value from the iterable, the probability of being in the
# k most extreme values is k/i. For example, the probability of the 101st
# value seen being in the 100 most extreme values is 100/101.
# * If the value is a new extreme value, the cost of inserting it into the
# heap is 1 + log(k, 2).
# * The probability times the cost gives:
# (k/i) * (1 + log(k, 2))
# * Summing across the remaining n-k elements gives:
# sum((k/i) * (1 + log(k, 2)) for i in range(k+1, n+1))
# * This reduces to:
# (H(n) - H(k)) * k * (1 + log(k, 2))
# * Where H(n) is the n-th harmonic number estimated by:
# gamma = 0.5772156649
# H(n) = log(n, e) + gamma + 1 / (2 * n)
# http://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Rate_of_divergence
# * Substituting the H(n) formula:
# comparisons = k * (1 + log(k, 2)) * (log(n/k, e) + (1/n - 1/k) / 2)
#
# Worst-case for step 3:
# ----------------------
# In the worst case, the input data is reversed sorted so that every new element
# must be inserted in the heap:
#
# comparisons = 1.66 * k + log(k, 2) * (n - k)
#
# Alternative Algorithms
# ----------------------
# Other algorithms were not used because they:
# 1) Took much more auxiliary memory,
# 2) Made multiple passes over the data.
# 3) Made more comparisons in common cases (small k, large n, semi-random input).
# See the more detailed comparison of approach at:
# http://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest
def nsmallest(n, iterable, key=None):
"""Find the n smallest elements in a dataset.
Equivalent to: sorted(iterable, key=key)[:n]
"""
# Short-cut for n==1 is to use min()
if n == 1:
it = iter(iterable)
sentinel = object()
if key is None:
result = min(it, default=sentinel)
else:
result = min(it, default=sentinel, key=key)
return [] if result is sentinel else [result]
# When n>=size, it's faster to use sorted()
try:
size = len(iterable)
except (TypeError, AttributeError):
pass
else:
if n >= size:
return sorted(iterable, key=key)[:n]
# When key is none, use simpler decoration
if key is None:
it = iter(iterable)
# put the range(n) first so that zip() doesn't
# consume one too many elements from the iterator
result = [(elem, i) for i, elem in zip(range(n), it)]
if not result:
return result
_heapify_max(result)
top = result[0][0]
order = n
_heapreplace = _heapreplace_max
for elem in it:
if elem < top:
_heapreplace(result, (elem, order))
top = result[0][0]
order += 1
result.sort()
return [r[0] for r in result]
# General case, slowest method
it = iter(iterable)
result = [(key(elem), i, elem) for i, elem in zip(range(n), it)]
if not result:
return result
_heapify_max(result)
top = result[0][0]
order = n
_heapreplace = _heapreplace_max
for elem in it:
k = key(elem)
if k < top:
_heapreplace(result, (k, order, elem))
top = result[0][0]
order += 1
result.sort()
return [r[2] for r in result]
def nlargest(n, iterable, key=None):
"""Find the n largest elements in a dataset.
Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
"""
# Short-cut for n==1 is to use max()
if n == 1:
it = iter(iterable)
sentinel = object()
if key is None:
result = max(it, default=sentinel)
else:
result = max(it, default=sentinel, key=key)
return [] if result is sentinel else [result]
# When n>=size, it's faster to use sorted()
try:
size = len(iterable)
except (TypeError, AttributeError):
pass
else:
if n >= size:
return sorted(iterable, key=key, reverse=True)[:n]
# When key is none, use simpler decoration
if key is None:
it = iter(iterable)
result = [(elem, i) for i, elem in zip(range(0, -n, -1), it)]
if not result:
return result
heapify(result)
top = result[0][0]
order = -n
_heapreplace = heapreplace
for elem in it:
if top < elem:
_heapreplace(result, (elem, order))
top = result[0][0]
order -= 1
result.sort(reverse=True)
return [r[0] for r in result]
# General case, slowest method
it = iter(iterable)
result = [(key(elem), i, elem) for i, elem in zip(range(0, -n, -1), it)]
if not result:
return result
heapify(result)
top = result[0][0]
order = -n
_heapreplace = heapreplace
for elem in it:
k = key(elem)
if top < k:
_heapreplace(result, (k, order, elem))
top = result[0][0]
order -= 1
result.sort(reverse=True)
return [r[2] for r in result]
# If available, use C implementation
try:
from _heapq import *
except ImportError:
pass
try:
from _heapq import _heapreplace_max
except ImportError:
pass
try:
from _heapq import _heapify_max
except ImportError:
pass
try:
from _heapq import _heappop_max
except ImportError:
pass
if __name__ == "__main__":
import doctest
print(doctest.testmod())
v class='ctx'> Starts a block of text that will be verbatim included in the generated MAN documentation only. The block ends with a
- endmanonly command.
+ \ref cmdendmanonly "\\endmanonly" command.
This command can be used to include groff code directly into
MAN pages. You can use the \\htmlonly and \\latexonly and
\\endhtmlonly and \\endlatexonly pairs to provide proper
HTML and \f$\mbox{\LaTeX}\f$ alternatives.
- \sa section \ref cmdhtmlonly "\\htmlonly" and section
- \ref cmdlatexonly "\\latexonly".
+ \sa section \ref cmdhtmlonly "\\htmlonly",
+ section \ref cmdrtfonly "\\rtfonly", and
+ section \ref cmdlatexonly "\\latexonly".
<hr>
\section cmdli \\li { item-description }
@@ -2424,18 +2486,38 @@ class Receiver
Equivalent to \ref cmdc "\\c"
<hr>
+\section cmdrtfonly \\rtfonly
+
+ \addindex \\rtfonly
+ Starts a block of text that will be verbatim included in the
+ generated RTF documentation only. The block ends with a
+ \ref cmdendrtfonly "\\endrtfonly" command.
+
+ This command can be used to include RTF code that is too complex
+ for doxygen.
+
+ \b Note:
+ environment variables (like \$(HOME) ) are resolved inside a
+ RTF-only block.
+
+ \sa section \ref cmdmanonly "\\manonly", section
+ \ref cmdlatexonly "\\latexonly", and section
+ \ref cmdhtmlonly "\\htmlonly".
+
+<hr>
\section cmdverbatim \\verbatim
\addindex \\verbatim
- Starts a block of text that will be verbatim included in both the
- HTML and the
- \f$\mbox{\LaTeX}\f$ documentation. The block should end with a
- \\endverbatim block. All commands are disabled in a verbatim block.
+ Starts a block of text that will be verbatim included in
+ the documentation. The block should end with a
+ \ref cmdendverbatim "\\endverbatim" block.
+ All commands are disabled in a verbatim block.
\warning Make sure you include a \\endverbatim command for each
\\verbatim command or the parser will get confused!
- \sa section \ref cmdcode "\\code", and section \ref cmdverbinclude "\\verbinclude".
+ \sa section \ref cmdcode "\\code", and
+ section \ref cmdverbinclude "\\verbinclude".
<hr>
\section cmdxmlonly \\xmlonly
@@ -2454,16 +2536,16 @@ class Receiver
\section cmdbackslash \\\\
\addindex \\\\
- This command writes a backslash character (\\) to the HTML and
- \f$\mbox{\LaTeX}\f$ output. The backslash has to be escaped in some
+ This command writes a backslash character (\\) to the
+ output. The backslash has to be escaped in some
cases because doxygen uses it to detect commands.
<hr>
\section cmdat \\\@
\addindex \\\@
- This command writes an at-sign (\@) to the HTML and
- \f$\mbox{\LaTeX}\f$ output. The at-sign has to be escaped in some cases
+ This command writes an at-sign (\@) to the output.
+ The at-sign has to be escaped in some cases
because doxygen uses it to detect JavaDoc commands.
<hr>
@@ -67,6 +67,7 @@ followed by the descriptions of the tags grouped by category.
\refitem cfg_caller_graph CALLER_GRAPH
\refitem cfg_case_sense_names CASE_SENSE_NAMES
\refitem cfg_chm_file CHM_FILE
+\refitem cfg_chm_index_encoding CHM_INDEX_ENCODING
\refitem cfg_class_diagrams CLASS_DIAGRAMS
\refitem cfg_class_graph CLASS_GRAPH
\refitem cfg_collaboration_graph COLLABORATION_GRAPH
@@ -155,6 +156,9 @@ followed by the descriptions of the tags grouped by category.
\refitem cfg_hide_undoc_members HIDE_UNDOC_MEMBERS
\refitem cfg_hide_undoc_relations HIDE_UNDOC_RELATIONS
\refitem cfg_html_align_members HTML_ALIGN_MEMBERS
+\refitem cfg_html_colorstyle_gamma HTML_COLORSTYLE_GAMMA
+\refitem cfg_html_colorstyle_hue HTML_COLORSTYLE_HUE
+\refitem cfg_html_colorstyle_sat HTML_COLORSTYLE_SAT
\refitem cfg_html_dynamic_sections HTML_DYNAMIC_SECTIONS
\refitem cfg_html_file_extension HTML_FILE_EXTENSION
\refitem cfg_html_footer HTML_FOOTER
@@ -165,6 +169,7 @@ followed by the descriptions of the tags grouped by category.
\refitem cfg_idl_property_support IDL_PROPERTY_SUPPORT
\refitem cfg_ignore_prefix IGNORE_PREFIX
\refitem cfg_image_path IMAGE_PATH
+\refitem cfg_include_file_patterns INCLUDE_FILE_PATTERNS
\refitem cfg_include_graph INCLUDE_GRAPH
\refitem cfg_include_path INCLUDE_PATH
\refitem cfg_included_by_graph INCLUDED_BY_GRAPH
@@ -182,12 +187,14 @@ followed by the descriptions of the tags grouped by category.
\refitem cfg_latex_header LATEX_HEADER
\refitem cfg_latex_hide_indices LATEX_HIDE_INDICES
\refitem cfg_latex_output LATEX_OUTPUT
+\refitem cfg_latex_source_code LATEX_SOURCE_CODE
\refitem cfg_layout_file LAYOUT_FILE
\refitem cfg_macro_expansion MACRO_EXPANSION
\refitem cfg_makeindex_cmd_name MAKEINDEX_CMD_NAME
\refitem cfg_man_extension MAN_EXTENSION
\refitem cfg_man_links MAN_LINKS
\refitem cfg_man_output MAN_OUTPUT
+\refitem cfg_mathjax_relpath MATHJAX_RELPATH
\refitem cfg_max_dot_graph_depth MAX_DOT_GRAPH_DEPTH
\refitem cfg_max_initializer_lines MAX_INITIALIZER_LINES
\refitem cfg_mscfile_dirs MSCFILE_DIRS
@@ -257,6 +264,7 @@ followed by the descriptions of the tags grouped by category.
\refitem cfg_uml_look UML_LOOK
\refitem cfg_use_htags USE_HTAGS
\refitem cfg_use_inline_trees USE_INLINE_TREES
+\refitem cfg_use_mathjax USE_MATHJAX
\refitem cfg_use_pdflatex USE_PDFLATEX
\refitem cfg_verbatim_headers VERBATIM_HEADERS
\refitem cfg_warn_format WARN_FORMAT
@@ -401,18 +409,6 @@ followed by the descriptions of the tags grouped by category.
definition is used. Otherwise one should specify the include paths that
are normally passed to the compiler using the -I flag.
-
-
-\anchor cfg_case_sense_names
-<dt>\c CASE_SENSE_NAMES <dd>
- \addindex CASE_SENSE_NAMES
- If the \c CASE_SENSE_NAMES tag is set to \c NO then doxygen
- will only generate file names in lower-case letters. If set to
- \c YES upper-case letters are also allowed. This is useful if you have
- classes or files whose names only differ in case and if your file system
- supports case sensitive file names. Windows users are advised to set this
- option to NO.
-
\anchor cfg_short_names
<dt>\c SHORT_NAMES <dd>
\addindex SHORT_NAMES
@@ -710,6 +706,16 @@ function's detailed documentation block.
to \c NO (the default) then the documentation will be excluded.
Set it to \c YES to include the internal documentation.
+\anchor cfg_case_sense_names
+<dt>\c CASE_SENSE_NAMES <dd>
+ \addindex CASE_SENSE_NAMES
+ If the \c CASE_SENSE_NAMES tag is set to \c NO then doxygen
+ will only generate file names in lower-case letters. If set to
+ \c YES upper-case letters are also allowed. This is useful if you have
+ classes or files whose names only differ in case and if your file system
+ supports case sensitive file names. Windows users are advised to set this
+ option to NO.
+
\anchor cfg_hide_scope_names
<dt>\c HIDE_SCOPE_NAMES <dd>
\addindex HIDE_SCOPE_NAMES
@@ -861,6 +867,50 @@ function's detailed documentation block.
Namespaces page. This will remove the Namespaces entry from the Quick Index
and from the Folder Tree View (if specified). The default is \c YES.
+\anchor cfg_file_version_filter
+<dt>\c FILE_VERSION_FILTER <dd>
+ \addindex FILE_VERSION_FILTER
+ The \c FILE_VERSION_FILTER tag can be used to specify a program or script that
+ doxygen should invoke to get the current version for each file (typically from the
+ version control system). Doxygen will invoke the program by executing (via
+ popen()) the command <code>command input-file</code>, where \c command is
+ the value of the \c FILE_VERSION_FILTER tag, and \c input-file is the name
+ of an input file provided by doxygen.
+ Whatever the program writes to standard output is used as the file version.
+
+Example of using a shell script as a filter for Unix:
+\verbatim
+ FILE_VERSION_FILTER = "/bin/sh versionfilter.sh"
+\endverbatim
+
+Example shell script for CVS:
+\verbatim
+#!/bin/sh
+cvs status $1 | sed -n 's/^[ \]*Working revision:[ \t]*\([0-9][0-9\.]*\).*/\1/p'
+\endverbatim
+
+Example shell script for Subversion:
+\verbatim
+#!/bin/sh
+svn stat -v $1 | sed -n 's/^[ A-Z?\*|!]\{1,15\}/r/;s/ \{1,15\}/\/r/;s/ .*//p'
+\endverbatim
+
+Example filter for ClearCase:
+\verbatim
+FILE_VERSION_INFO = "cleartool desc -fmt \%Vn"
+\endverbatim
+
+\anchor cfg_layout_file
+<dt>\c LAYOUT_FILE <dd>
+ The \c LAYOUT_FILE tag can be used to specify a layout file which will be parsed by
+ doxygen. The layout file controls the global structure of the generated output files
+ in an output format independent way. The create the layout file that represents
+ doxygen's defaults, run doxygen with the -l option. You can optionally specify a
+ file name after the option, if omitted DoxygenLayout.xml will be used as the name
+ of the layout file. Note that if you run doxygen from a directory containing
+ a file called DoxygenLayout.xml, doxygen will parse it automatically even if
+ the \c LAYOUT_FILE tag is left empty.
+
</dl>
\section messages_input Options related to warning and progress messages
@@ -956,54 +1006,11 @@ function's detailed documentation block.
(like \c *.cpp and \c *.h ) to filter out the source-files
in the directories. If left blank the following patterns are tested:
<code>
- *.c *.cc *.cxx *.cpp *.c++ *.java *.ii *.ixx *.ipp *.i++ *.inl *.h *.hh *.hxx *.hpp
- *.h++ *.idl *.odl *.cs *.php *.php3 *.inc *.m *.mm
+ *.c *.cc *.cxx *.cpp *.c++ *.d *.java *.ii *.ixx *.ipp *.i++ *.inl *.h *.hh
+ *.hxx *.hpp *.h++ *.idl *.odl *.cs *.php *.php3 *.inc *.m *.mm *.dox *.py
+ *.f90 *.f *.vhd *.vhdl
</code>
-\anchor cfg_file_version_filter
-<dt>\c FILE_VERSION_FILTER <dd>
- \addindex FILE_VERSION_FILTER
- The \c FILE_VERSION_FILTER tag can be used to specify a program or script that
- doxygen should invoke to get the current version for each file (typically from the
- version control system). Doxygen will invoke the program by executing (via
- popen()) the command <code>command input-file</code>, where \c command is
- the value of the \c FILE_VERSION_FILTER tag, and \c input-file is the name
- of an input file provided by doxygen.
- Whatever the program writes to standard output is used as the file version.
-
-Example of using a shell script as a filter for Unix:
-\verbatim
- FILE_VERSION_FILTER = "/bin/sh versionfilter.sh"
-\endverbatim
-
-Example shell script for CVS:
-\verbatim
-#!/bin/sh
-cvs status $1 | sed -n 's/^[ \]*Working revision:[ \t]*\([0-9][0-9\.]*\).*/\1/p'
-\endverbatim
-
-Example shell script for Subversion:
-\verbatim
-#!/bin/sh
-svn stat -v $1 | sed -n 's/^[ A-Z?\*|!]\{1,15\}/r/;s/ \{1,15\}/\/r/;s/ .*//p'
-\endverbatim
-
-Example filter for ClearCase:
-\verbatim
-FILE_VERSION_INFO = "cleartool desc -fmt \%Vn"
-\endverbatim
-
-\anchor cfg_layout_file
-<dt>\c LAYOUT_FILE <dd>
- The \c LAYOUT_FILE tag can be used to specify a layout file which will be parsed by
- doxygen. The layout file controls the global structure of the generated output files
- in an output format independent way. The create the layout file that represents
- doxygen's defaults, run doxygen with the -l option. You can optionally specify a
- file name after the option, if omitted DoxygenLayout.xml will be used as the name
- of the layout file. Note that if you run doxygen from a directory containing
- a file called DoxygenLayout.xml, doxygen will parse it automatically even if
- the \c LAYOUT_FILE tag is left empty.
-
\anchor cfg_recursive
<dt>\c RECURSIVE <dd>
\addindex RECURSIVE
@@ -1307,6 +1314,33 @@ AClass::ANamespace, ANamespace::*Test
See also section \ref doxygen_usage for information on how to generate
the style sheet that doxygen normally uses.
+\anchor cfg_html_colorstyle_hue
+<dt>\c HTML_COLORSTYLE_HUE <dd>
+ \addindex HTML_COLOR_STYLE_HUE
+ The \c HTML_COLORSTYLE_HUE tag controls the color of the HTML output.
+ Doxygen will adjust the colors in the stylesheet and background images
+ according to this color. Hue is specified as an angle on a colorwheel,
+ see http://en.wikipedia.org/wiki/Hue for more information.
+ For instance the value 0 represents red, 60 is yellow, 120 is green,
+ 180 is cyan, 240 is blue, 300 purple, and 360 is red again.
+ The allowed range is 0 to 359.
+
+\anchor cfg_html_colorstyle_sat
+<dt>\c HTML_COLORSTYLE_SAT <dd>
+ \addindex HTML_COLORSTYLE_SAT
+ The \c HTML_COLORSTYLE_SAT tag controls the purity (or saturation) of
+ the colors in the HTML output. For a value of 0 the output will use
+ grayscales only. A value of 255 will produce the most vivid colors.
+
+\anchor cfg_html_colorstyle_gamma
+<dt>\c HTML_COLORSTYLE_GAMMA <dd>
+ The \c HTML_COLORSTYLE_GAMMA tag controls the gamma correction applied to
+ the luminance component of the colors in the HTML output. Values below
+ 100 gradually make the output lighter, whereas values above 100 make
+ the output darker. The value divided by 100 is the actual gamma applied,
+ so 80 represents a gamma of 0.8, The value 220 represents a gamma of 2.2,
+ and 100 does not change the gamma.
+
\anchor cfg_html_timestamp
<dt>\c HTML_TIMESTAMP <dd>
\addindex HTML_TIMESTAMP
@@ -1417,6 +1451,13 @@ The GENERATE_PUBLISHER_NAME tag identifies the documentation publisher.
controls if a separate .chi index file is generated (<code>YES</code>) or that
it should be included in the master .chm file (<code>NO</code>).
+\anchor cfg_chm_index_encoding
+<dt>\c CHM_INDEX_ENCODING <dd>
+ \addindex CHM_INDEX_ENCODING
+ If the \c GENERATE_HTMLHELP tag is set to \c YES, the \c CHM_INDEX_ENCODING
+ is used to encode HtmlHelp index (hhk), content (hhc) and project file
+ content.
+
\anchor cfg_binary_toc
<dt>\c BINARY_TOC <dd>
\addindex BINARY_TOC
@@ -1610,6 +1651,28 @@ and Class Hierarchy pages using a tree view instead of an ordered list.
not supported properly for IE 6.0, but are supported on all modern browsers.
Note that when changing this option you need to delete any form_*.png files
in the HTML output before the changes have effect.
+
+\anchor cfg_use_mathjax
+<dt>\c USE_MATHJAX <dd>
+ \addindex USE_MATHJAX
+ Enable the \c USE_MATHJAX option to render LaTeX formulas using MathJax
+ (see http://www.mathjax.org) which uses client side Javascript for the
+ rendering instead of using prerendered bitmaps. Use this if you do not
+ have LaTeX installed or if you want to formulas look prettier in the HTML
+ output. When enabled you also need to install MathJax separately and
+ configure the path to it using the \ref cfg_mathjax_relpath "MATHJAX_RELPATH" option.
+
+\anchor cfg_mathjax_relpath
+<dt>\c MATHJAX_RELPATH <dd>
+ \addindex MATHJAX_RELPATH
+ When MathJax is enabled you need to specify the location relative to the
+ HTML output directory using the \c MATHJAX_RELPATH option. The destination
+ directory should contain the MathJax.js script. For instance, if the mathjax
+ directory is located at the same level as the HTML output directory, then
+ \c MATHJAX_RELPATH should be <code>../mathjax</code>. The default value points to
+ the http://www.mathjax.org site, so you can quickly see the result without installing
+ MathJax, but it is strongly recommended to install a local copy of MathJax
+ before deployment.
</dl>
\section latex_output LaTeX related options
@@ -1735,6 +1798,13 @@ EXTRA_PACKAGES = times
include the index chapters (such as File Index, Compound Index, etc.)
in the output.
+\anchor cfg_latex_source_code
+ <dt>\c LATEX_SOURCE_CODE <dd>
+ If \c LATEX_SOURCE_CODE is set to \c YES then doxygen will include
+ source code with syntax highlighting in the LaTeX output.
+ Note that which sources are shown also depends on other settings
+ such as \ref cfg_source_browser "SOURCE_BROWSER".
+
</dl>
\section rtf_output RTF related options
\anchor cfg_generate_rtf
@@ -1957,6 +2027,14 @@ EXTRA_PACKAGES = times
contain include files that are not input files but should be processed by
the preprocessor.
+\anchor cfg_include_file_patterns
+<dt>\c INCLUDE_FILE_PATTERNS <dd>
+ \addindex INCLUDE_FILE_PATTERNS
+ You can use the \c INCLUDE_FILE_PATTERNS tag to specify one or more wildcard
+ patterns (like *.h and *.hpp) to filter out the header-files in the
+ directories. If left blank, the patterns specified with \c FILE_PATTERNS will
+ be used.
+
\anchor cfg_predefined
<dt>\c PREDEFINED <dd>
\addindex PREDEFINED
@@ -2109,24 +2187,6 @@ The default size is 10pt.
different font using \c DOT_FONTNAME you can set the path where dot
can find it using this tag.
-<dt>\c DOT_FONTNAME <dd>
- \addindex DOT_FONTNAME
- By default doxygen will write a font called FreeSans.ttf to the output
- directory and reference it in all dot files that doxygen generates. This
- font does not include all possible unicode characters however, so when you need
- these (or just want a differently looking font) you can specify the font name
- using \c DOT_FONTNAME. You need need to make sure dot is able to find the font,
- which can be done by putting it in a standard location or by setting the \c DOTFONTPATH
- environment variable or by setting \c DOT_FONTPATH to the directory containing
- the font.
-
-<dt>\c DOT_FONTPATH <dd>
- \addindex DOT_FONTPATH
- By default doxygen will tell dot to use the output directory to look for the
- FreeSans.ttf font (which doxygen will put there itself). If you specify a
- different font using \c DOT_FONTNAME you can set the path where dot
- can find it using this tag.
-
\anchor cfg_class_graph
<dt>\c CLASS_GRAPH <dd>
\addindex CLASS_GRAPH
@@ -75,7 +75,7 @@ doxygen -w latex header.tex doxygen.sty
\endverbatim
If you need non-default options (for instance to use pdflatex) you need
to make a config file with those options set correctly and then specify
-that config file as the forth argument.
+that config file as the third argument.
<li>For RTF output, you can generate the default style sheet file (see
\ref cfg_rtf_stylesheet_file "RTF_STYLESHEET_FILE") using:
\verbatim
@@ -29,6 +29,11 @@ have the following tools installed
<li>\c gs: the GhostScript interpreter for converting PostScript files
to bitmaps. I have used Aladdin GhostScript 8.0 for testing.
</ul>
+For the HTML output there is also an alternative solution using
+<a href="http://www.mathjax.org">MathJax</a> which does not
+require the above tools. If you enable \ref cfg_use_mathjax "USE_MATHJAX" in
+the config then the latex formulas will be copied to the HTML "as is" and a
+client side javascript will parse them and turn them into (interactive) images.
There are three ways to include formulas in the documentation.
<ol>
@@ -122,7 +122,7 @@ when the translator was updated.
<td>Esperanto</td>
<td>Ander Martinez</td>
<td>dwarfnauko at gmail dot com</td>
- <td>1.6.3</td>
+ <td>up-to-date</td>
</tr>
<tr bgcolor="#ffffff">
<td>Finnish</td>
@@ -222,8 +222,8 @@ when the translator was updated.
</tr>
<tr bgcolor="#ffffff">
<td>Portuguese</td>
- <td>Rui Godinho Lopes</td>
- <td><span style="color: brown">[resigned]</span></td>
+ <td>Rui Godinho Lopes<br/><span style="color: red; background-color: yellow">-- searching for the maintainer --</span></td>
+ <td><span style="color: brown">[resigned]</span><br/><span style="color: brown">[Please, try to help to find someone.]</span></td>
<td>1.3.3</td>
</tr>
<tr bgcolor="#ffffff">
@@ -334,7 +334,7 @@ when the translator was updated.
\hline
English & Dimitri van Heesch & {\tt\tiny dimitri at stack dot nl} & up-to-date \\
\hline
- Esperanto & Ander Martinez & {\tt\tiny dwarfnauko at gmail dot com} & 1.6.3 \\
+ Esperanto & Ander Martinez & {\tt\tiny dwarfnauko at gmail dot com} & up-to-date \\
\hline
Finnish & Antti Laine & {\tt\tiny antti dot a dot laine at tut dot fi} & 1.6.0 \\
\hline
@@ -377,10 +377,11 @@ when the translator was updated.
Persian & Ali Nadalizadeh & {\tt\tiny nadalizadeh at gmail dot com} & up-to-date \\
\hline
Polish & Piotr Kaminski & {\tt\tiny [unreachable] Piotr dot Kaminski at ctm dot gdynia dot pl} & 1.6.3 \\
- ~ & Grzegorz Kowal & {\tt\tiny [unreachable] g_kowal at poczta dot onet dot pl} & ~ \\
+ ~ & Grzegorz Kowal & {\tt\tiny [unreachable] g\_kowal at poczta dot onet dot pl} & ~ \\
~ & Krzysztof Kral & {\tt\tiny krzysztof dot kral at gmail dot com} & ~ \\
\hline
Portuguese & Rui Godinho Lopes & {\tt\tiny [resigned] rgl at ruilopes dot com} & 1.3.3 \\
+ ~ & -- searching for the maintainer -- & {\tt\tiny [Please, try to help to find someone.]} & ~ \\
\hline
Romanian & Ionut Dumitrascu & {\tt\tiny reddumy at yahoo dot com} & 1.6.0 \\
~ & Alexandru Iosup & {\tt\tiny aiosup at yahoo dot com} & ~ \\
@@ -111,6 +111,7 @@ Krzysztof Kral: krzysztof dot kral at gmail dot com
TranslatorPortuguese
Rui Godinho Lopes: [resigned] rgl at ruilopes dot com
+-- searching for the maintainer --: [Please, try to help to find someone.]
TranslatorRomanian
Ionut Dumitrascu: reddumy at yahoo dot com
diff --git a/doc/translator.py b/doc/translator.py