def _sort(rs,sortSpecs):
  '''sort result set *rs* according to *sortSpecs*.

  *sortSpecs* is a sequence of pairs *sortIndex*,*sortReverse*.
  '''
  if not sortSpecs: return rs
  l= []; append= l.append
  sortSpec= sortSpecs[0]; sortSpecs= sortSpecs[1:]
  sortIndex, sortReverse= sortSpec
  # copy code from "ZCatalog.Catalog.Catalog._indexedSearch"
  if len(rs) > 4*len(sortIndex):
    # result large compared to "sort_index"
    for k,docs in sortIndex.items():
      docs= intersection(rs,docs)
      l.append((k,_sort(docs,sortspecs)))
    #l.sort() # this is not necessary, as "BTrees.items()" returns sorted results
  else:
    keyFor= sortIndex.keyForDocument
    for doc in rs.keys():
      k= keyFor(doc)
      l.append((k,[doc]))
    l.sort()
    if sortSpecs:
      # fold equal keys
      i= 1
      while i < len(l):
        if l[i][0] == l[i-1][0]: l[i-1][1].append(l[i][1][0]); del l[i]
        else: i+= 1
      # sort subsequent levels
      i= 0; n= len(l)
      while i < n:
        l[i]= (None,_sort(IISet(l[i][1]),sortSpecs));
        i+= 1
  # remove sorting keys
  l= [docs for k,docs in l]
  # now reverse, if necessary
  if sortReverse: l.reverse()
  # flatten the result - tbis might get more efficient, when done lazyly.
  # but, probably, it is of lower order...
  r= []
  for docs in l: r.extend(docs)
  return r

def _normSortSpecs(Specs,cat):
  '''normalize *sortSpecs*.'''
  l= []
  for s in Specs:
    if type(s) is TupleType: si,so= s
    else: si=s; so= 'asc'
    i= cat.indexes[si]
    # ensure, the index supports sorting
    if not hasattr(i,'keyForDocument'):
      raise ValueError,'Index not adequate for sorting: %s' % si
    # check whether we should reverse the order
    so= so.lower()
    if so in ('asc', 'ascending'): sr= 0
    elif so in ('desc', 'descending', 'reverse'): sr= 1
    l.append((i,sr))
  return l


#######################################################################
## Module function
def evalQuery(catalog,query,sortSpecs=()):
  '''evaluate *query* in the context of *catalog* and sort the result
  according to *sortSpecs*.

  *sortSpecs* is a sequence of sort specifictions. A sort specification
  is either an index name or a pair consisting of an index name and
  a sort order ('asc/desc').
  '''
  cat= catalog._catalog
  rs= query._eval(_QueryContext(cat))
  if not rs: return LazyCat(rs)
  if sortSpecs:
    rs= _sort(rs,_normSortSpecs(sortSpecs,cat))
  return LazyMap(cat.__getitem__,rs)