MoinMoin: attachment:SortBy.py of MacroMarket/SortBy

   1 """
   2     MoinMoin - SortBy Macro
   3     Copyright (c) 2001 by Fred Bremmer <Fred.Bremmer@ubc.ca>
   4     Modified (c) 2007 by Lane Rettig <Lane.Rettig@deshaw.com>
   5 
   6     Based on an earlier SortBy Macro
   7     Copyright (c) 2001 by Tim Bird <tbird@lineo.com>
   8     All rights reserved, see COPYING for details.
   9 
  10 DESCRIPTION: Sort a table by one or more columns and sort types/orders
  11 
  12 SortBy(page,num_headers,column,sort_type[,othercolumn,sort_type]...)
  13 
  14 Examples:
  15 
  16     [[SortBy(TablePage,1,3,alpha)]]
  17 
  18 This would return the first table on TablePage sorted by column 3
  19 (column 1 is the leftmost column).  The rows would be sorted using a
  20 lexicographic (alpha) sort.  It would preserve 1 header row of the
  21 table, without sorting it.
  22 
  23     [[SortBy(TablePage,0,2,reversenumber,1,alpha)]]
  24 
  25 This would return the first table on TablePage sorted using a reverse
  26 numeric sort on column 2, but rows with identical values in column 2
  27 would be sorted in alpha order of their values in column 1.  It would
  28 not preserve the first row of the table.  The first row of the table 
  29 would be sorted also (zero header rows left unsorted).
  30 
  31 Supported sort types are: alpha, number, nocase, nosort, reversealpha,
  32 reversenumber, reversenocase, reversenosort
  33 
  34 'nosort' can be used to make the SortBy macro behave like an Include
  35 that only loads the first table from the page, not the whole page.
  36 Thus you can have comments on the table page that are not shown in the
  37 SortBy rendering on the including page.
  38 
  39 See SortByTest below for a more comprehensive list of examples.
  40 
  41 Utility functions:
  42     error()        - convert an error message to HTML
  43     read_table()   - read a file and return its first table's data
  44 
  45 Functions to convert a string into an appropriate sortable value:
  46     strip_fmt()    - remove wiki formatting and commas
  47     to_number()    - convert to a number if possible
  48     to_nocase()    - convert everything to the same case
  49     to_nosort()    - return ascending numbers regardless of arg
  50 
  51 Main loop functions:
  52     process_args() - parse args string and do some error checking
  53     sort_table()   - do the actual sorting of table rows
  54     format()       - generate the HTML output
  55     execute()      - the macro's main loop, called by MoinMoin
  56 
  57 """
  58 
  59 # After installing this macro, you can test it by creating a wiki page
  60 # named "SortByTest" which contains the following text:
  61 
  62 SortByTest = """
  63 [[TableOfContents]]
  64 
  65 == Original Table ==
  66 ||'''First'''	||'''Second'''	||'''Third'''	||
  67 ||A		||2,000,000	||zebra		||
  68 ||C		||1		||123		||
  69 ||b		||2		||word		||
  70 ||d		||30		||{{{word}}}	||
  71 ||A		||2		||Wordy		||
  72 ||B		||4.2		||23		||
  73 ||A		||2		||'''word'''	||
  74 
  75 == Column 1 No Sort ==
  76 {{{[[SortBy(SortByTest, 1, 1, nosort)]]}}}
  77 
  78 [[SortBy(SortByTest, 1, 1, nosort)]]
  79 
  80 This simply includes the first table on the source page at this point in the
  81 page containing the macro. Rows are in the same order as the original table.
  82 
  83 == Column 1 Reverse No Sort ==
  84 {{{[[SortBy(SortByTest, 1, 1, reversenosort)]]}}}
  85 
  86 [[SortBy(SortByTest, 1, 1, reversenosort)]]
  87 
  88 Similar to the previous example, but now all rows except the one header row
  89 are in reverse order.
  90 
  91 == Column 1 Alphabetical ==
  92 {{{[[SortBy(SortByTest, 1, 1, alpha)]]}}}
  93 
  94 [[SortBy(SortByTest, 1, 1, alpha)]]
  95 
  96 In alphabetical order all uppercase letters are sorted before lowercase
  97 letters.
  98 
  99 == Column 1 Reverse Alphabetical ==
 100 {{{[[SortBy(SortByTest, 1, 1, reversealpha)]]}}}
 101 
 102 [[SortBy(SortByTest, 1, 1, reversealpha)]]
 103 
 104 Prepending 'reverse' to the sort-type changes the order from ascending to
 105 descending.
 106 
 107 == Column 1 Case-Insensitive ==
 108 {{{[[SortBy(SortByTest, 1, 1, nocase)]]}}}
 109 
 110 [[SortBy(SortByTest, 1, 1, nocase)]]
 111 
 112 Now 'B' and 'b' are considered equal, and are presented in the order they
 113 appear in the original table.
 114 
 115 == Column 2 Numerical ==
 116 {{{[[SortBy(SortByTest, 1, 2, number)]]}}}
 117 
 118 [[SortBy(SortByTest, 1, 2, number)]]
 119 
 120 As you would expect, 30 comes before 2,000,000. Commas are ignored for
 121 sorting. Integers and floating point can both be used, and they sort
 122 correctly.
 123 
 124 == Column 2 Alphabetical ==
 125 {{{[[SortBy(SortByTest, 1, 2, alpha)]]}}}
 126 
 127 [[SortBy(SortByTest, 1, 2, alpha)]]
 128 
 129 In 'alphabetical' order, 2 comes before 3, so 2,000,000 sorts before 30.
 130 
 131 == Column 2 Reverse Numerical ==
 132 {{{[[SortBy(SortByTest, 1, 2, reversenumber)]]}}}
 133 
 134 [[SortBy(SortByTest, 1, 2, reversenumber)]]
 135 
 136 Again, prepending 'reverse' to the sort-type changes the order from ascending
 137 to descending.
 138 
 139 == Column 3 Alphabetical ==
 140 {{{[[SortBy(SortByTest, 1, 3, alpha)]]}}}
 141 
 142 [[SortBy(SortByTest, 1, 3, alpha)]]
 143 
 144 Wiki formatting is ignored, and the sort is stable. The variations of 'word'
 145 are simply listed in the same order as they appear in the original table.
 146 
 147 == Column 3 Numerical ==
 148 {{{[[SortBy(SortByTest, 1, 3, number)]]}}}
 149 
 150 [[SortBy(SortByTest, 1, 3, number)]]
 151 
 152 Now 23 comes before 123, and non-numeric values are sorted in alphabetical
 153 order as above.
 154 
 155 == Column 1 Alphabetical, Column 2 Numerical, Column 3 Alphabetical ==
 156 {{{[[SortBy(SortByTest, 1, 1, alpha, 2, number, 3, alpha)]]}}}
 157 
 158 [[SortBy(SortByTest, 1, 1, alpha, 2, number, 3, alpha)]]
 159 
 160 The main sort is on column 1, but within the duplicate 'A's the 2's and 
 161 2,000,000 are sorted, and within the 2's the values in column 3 are in 
 162 case-sensitive alphabetical order.
 163 
 164 == Column 1 Case-Insensitive, Column 2 Numerical, Column 3 Case-Insensitive ==
 165 {{{[[SortBy(SortByTest, 1, 1, nocase, 2, number, 3, nocase)]]}}}
 166 
 167 [[SortBy(SortByTest, 1, 1, nocase, 2, number, 3, nocase)]]
 168 
 169 The main sort is still on column 1, but within the case-insensitive duplicate
 170 'b's the values in column 2 are in numerical order. Also, within the duplicate
 171 A-2 rows, column 3 is case-insensitive, so now Wordy follows word.
 172 
 173 == Zero Header Rows, Case-Insensitive Sort on Column 1 ==
 174 {{{[[SortBy(SortByTest, 0, 1, nocase)]]}}}
 175 
 176 [[SortBy(SortByTest, 0, 1, nocase)]]
 177 
 178 The first row is sorted along with all the other rows.
 179 
 180 == Three Header Rows, Case-Insensitive Sort on Column 1 ==
 181 {{{[[SortBy(SortByTest, 3, 1, nocase)]]}}}
 182 
 183 [[SortBy(SortByTest, 3, 1, nocase)]]
 184 
 185 The first three rows are not sorted along with all the other rows.
 186 
 187 == Invalid Argument Examples ==
 188 
 189 [[SortBy(NonExistentPage, 1, 1, nocase)]]
 190 
 191 [[SortBy(SortByTest, 1, 1)]]
 192 
 193 [[SortBy(SortByTest, x, 1, alpha)]]
 194 
 195 [[SortBy(SortByTest, 1, x, alpha)]]
 196 
 197 [[SortBy(SortByTest, -1, 1, alpha)]]
 198 
 199 [[SortBy(SortByTest, 10, 1, alpha)]]
 200 
 201 [[SortBy(SortByTest, 1, 0, alpha)]]
 202 
 203 [[SortBy(SortByTest, 1, 10, alpha)]]
 204 
 205 [[SortBy(SortByTest, 1, 1, x)]]
 206 
 207 [[SortBy(SortByTest, 1, 1, alpha, 1)]]
 208 
 209 """
 210 
 211 import sys, re, StringIO, cgi
 212 from MoinMoin.Page import Page
 213 
 214 
 215 class SortByError(Exception):
 216     """Raised anywhere in the macro, caught outside the main loop."""
 217 
 218     def __init__(self, msg=''):
 219         """msg -- a string to be displayed to the user"""
 220         self.msg = msg
 221 
 222 
 223 def error(msg, args):
 224     """Return a message followed by usage information, all in HTML.
 225 
 226     msg  -- a string describing the error
 227     args -- the macro's original argument string
 228 
 229     """
 230     html = """
 231 <tt class="wiki">[[SortBy(%s)]]</tt><br>
 232 <strong class="error">SortBy: %s</strong><br>
 233 <small>%s<br>
 234 Valid sort types are: %s</small>"""
 235     msg = cgi.escape(msg)
 236     usage = cgi.escape("""Usage: SortBy(TablePage, <number of header rows>,
 237             <primary sort column number>, <sort type>
 238             [, <secondary sort column>, <sort type>] ... )""")
 239     sorts = ' '.join(valid_sorts)
 240     return html % (args, msg, usage, sorts)
 241 
 242 
 243 def read_table(page_file):
 244     """Read page_file and convert its first table's lines into row data"""
 245     file = open(page_file)
 246     intable = 0
 247     table_rows = []
 248     for line in file.xreadlines():
 249         if len(line) < 2 or line[0:2] != '||':
 250             if intable: break # We're done
 251             else: continue    # Skip non-table lines until we hit the table
 252         else:
 253             intable = 1
 254             table_rows.append(line[:-1]) # strip the \n while we're at it
 255     return table_rows
 256 
 257 
 258 def strip_fmt(arg):
 259     """Remove formatting characters and leading/trailing whitespace.
 260 
 261     Commas (such as in 1,000,000) are considered formatting chars."""
 262     for fmt_string in ["'''", "''", '{{{', '}}}', ',']:
 263         arg = arg.replace(fmt_string, '')
 264     return arg.strip()
 265 
 266 
 267 def to_number(arg):
 268     """Convert arg to int or float if possible, else return a string."""
 269     arg = strip_fmt(arg)
 270     try: return int(arg)
 271     except ValueError:
 272         try: return float(arg)
 273         except ValueError: return arg
 274 
 275 
 276 def to_nocase(arg):
 277     """Return arg in lowercase with no formatting characters."""
 278     return strip_fmt(arg).lower()
 279 
 280 
 281 def to_nosort(arg, count=[0]):
 282     """Return a higher integer each time so rows don't move when sorted."""
 283     count[0] += 1   # count is a default arg, so references the same list and
 284     return count[0] # incr's the same [0] every time the function is called.
 285 
 286 
 287 decorate_functions = {'alpha': strip_fmt,
 288                       'number': to_number,          
 289                       'nocase': to_nocase,
 290                       'nosort': to_nosort}
 291 valid_sorts = decorate_functions.keys()
 292 valid_sorts.sort()
 293 valid_sorts.extend(['reverse'+sort_name for sort_name in valid_sorts])
 294 
 295 
 296 def process_args(args, request):
 297     """Parse args string, return (sort_page, table, num_headers, sort_list)."""
 298     arglist = re.split(r'\s*,\s*', args.strip())
 299     if len(arglist) < 4:
 300         msg = """Not enough arguments (%s).
 301                  At least 4 are required.""" % len(arglist)
 302         raise SortByError, msg
 303     table_page, num_headers = arglist[0:2]
 304     try: num_headers = int(num_headers)
 305     except ValueError:
 306         msg = """Number of header rows (%s)
 307                  must be an integer""" % num_headers
 308         raise SortByError, msg
 309     if num_headers < 0:
 310         msg = """Number of header rows (%s)
 311                  must be a positive integer""" % num_headers
 312         raise SortByError, msg
 313     arglist[:2] = []  # Make arglist contain only column & sort_type pairs
 314     if len(arglist)%2 != 0:
 315         raise SortByError, 'Odd number of arguments (%s)' % (len(arglist)+2)
 316     sort_list = []
 317     while arglist:
 318 
 319         # Pop the sort_type and column from the end of the arglist.
 320         # They get stored in the sort_list in the opposite order
 321         # they were requested so the primary sort is done last.
 322 
 323         sort_type = arglist.pop().lower()
 324         sort_column = arglist.pop()
 325         try: sort_column = int(sort_column)
 326         except ValueError:
 327             msg = 'Column number (%s) must be an integer' % sort_column
 328             raise SortByError, msg
 329         if sort_column < 1:
 330             msg = """Column number (%s) must be 1 or higher.
 331                      1 = leftmost column""" % sort_column
 332             raise SortByError, msg
 333         sort_column -= 1  # Use zero-based column indexing internally
 334         if sort_type[:7] == 'reverse': # If the sort_type begins with 'reverse'
 335             reverse = 1                # set the reverse flag  
 336             sort_type = sort_type[7:]  # and strip 'reverse' from sort_type
 337         else: reverse = 0
 338         sort_list.append((sort_column, sort_type, reverse))  # Append a 3-tuple
 339     sort_page = Page(request, table_page)
 340     try: table_rows = read_table(sort_page._text_filename())
 341     except IOError:
 342         raise SortByError, 'Unable to open the table page "%s"' % table_page
 343     table = [row.split('||')[1:-1] for row in table_rows]
 344     if num_headers > len(table):
 345         msg = """Number of header rows (%s) is more than
 346                  the table length (%s)""" % (num_headers, len(table))
 347         raise SortByError, msg
 348     return (sort_page, table, num_headers, sort_list)
 349 
 350 
 351 def sort_table(table, num_headers, sort_column, sort_type, reverse):
 352     """Sort of the table (in-place), preserving num_headers rows at the top.
 353 
 354     Arguments:
 355     table       -- a list of lists representing rows of column entries
 356     num_headers -- an integer number of rows to keep at the top of the table
 357     sort_column -- the column number (zero-based) containing the sort values
 358     sort_type   -- which kind of sort to perform on the values being sorted
 359     reverse     -- 0 or 1, meaning an ascending or descending (reverse) sort
 360 
 361     """
 362     header = table[:num_headers]
 363     table[:num_headers] = []
 364 
 365     if table and sort_column > min([len(row) for row in table]):
 366         msg = """Column number (%s) is higher than
 367                  the length of one or more rows"""  % (sort_column+1)
 368         raise SortByError, msg
 369     if sort_type not in valid_sorts:
 370         raise SortByError, 'Invalid sort type "%s"' % sort_type
 371     decorate = decorate_functions[sort_type]
 372 
 373     # Use the 'decorate, sort, undecorate' pattern with ascending or
 374     # descending indices to ensure that the sort is stable.
 375 
 376     decorations = [decorate(row[sort_column]) for row in table]
 377     if reverse: indices = xrange(len(table), 0, -1)
 378     else: indices = xrange(len(table))
 379     decorated = zip(decorations, indices, table)
 380     decorated.sort()
 381     table[:] = [row for (decoration, index, row) in decorated]
 382 
 383     if reverse: table.reverse()
 384     table[:0] = header
 385     return
 386 
 387 
 388 def format(sort_page, macro, table):
 389     """Format the sorted table and return it as an HTML fragment.
 390 
 391     Arguments:
 392     sort_page -- a MoinMoin Page object representing the table page
 393     macro     -- the macro argument that was provided by MoinMoin
 394     table     -- a list of lists representing rows of column entries
 395 
 396     """
 397     ret = ''
 398     table_rows = ['||%s||' % '||'.join(row) for row in table]
 399     sort_page.set_raw_body('\n'.join(table_rows), 1)  # format the table
 400 
 401     # Here's some tricky stuff copied from Richard Jones' Include macro.
 402     stdout = sys.stdout
 403     sys.stdout = StringIO.StringIO()
 404     sort_page.send_page(macro.request, content_only=1)
 405     ret += sys.stdout.getvalue()
 406     sys.stdout = stdout
 407 
 408     # Output a helper link to get to the page with the table.
 409     name = sort_page.page_name
 410     ret += '<small>' + macro.formatter.url(1, name) + \
 411            macro.formatter.text('[goto %s]' % name) + macro.formatter.url(0) + \
 412            '</small>'
 413     return ret    
 414 
 415 
 416 def execute(macro, args):
 417     """Parse args, sort_table() repeatedly, return formatted table as HTML.
 418 
 419     Sort the table once for each column & sort_type in the sort_list
 420     beginning with the last (and least significant) sort in args
 421     because they were 'popped' from the end of the args. Since
 422     sort_table() uses a stable sort algorithm, the ordering of the
 423     earlier sorts is preserved in the later sorts when there are
 424     duplicates of the sort key.
 425 
 426     """
 427     try:
 428         sort_page, table, num_headers, sort_list = process_args(args, macro.request)
 429         for sort_column, sort_type, reverse in sort_list:
 430             sort_table(table, num_headers, sort_column, sort_type, reverse)
 431         return format(sort_page, macro, table)
 432     except SortByError, e: return error(e.msg, args)