#!/usr/bin/env python
from itertools import groupby
from dateutil.rrule import *
from operator import itemgetter
import bisect
from uuid import uuid4
from colorsys import hsv_to_rgb
from etmParsers import *

#  key, task, day, event, action, note
#  o (optional/permitted), r (required), space (not allowed)
#  ? (required for an event if extent is given, otherwise optional)
#  RR (rrule)
#   k   t   e   a   n
# ---------------------------------------------------
#  @-   o   o   o       exclude (NEW was o) RR
#  @+   o   o   o       include (NEW was l) RR
#  @a       o           alerts
#  @A       o           alternate alert command
#  @b   o               begin by
#  @c   o   o   o       optional   context
#  @C   o   o   o       count (NEW) RR
#  @d   o   r   r   o   date
#  @e   o   o   r       extent
#  @f   o               finished date
#  @g   o   o   o       goto
#  @i   o   o   o       interval RR
#  @k   o   o   o   o   keyword
#  @t   o   o   o   o   tags
#  @l   o   o   o   o   location (NEW)
#  @M   o   o   o       month number RR
#  @m   o   o   o       month day number RR
#  @n   o   o   o       note
#  @o   o               overdue RR
#  @p   o               priority
#  @r   o   o   o       repeat RR
#  @s       ?           starting time
#  @S   o   o   o       setpos (NEW) RR
#  @u   o   o   o       until  RR
#  @U   o   o   o   o   user (recently added)
#  @W   o   o   o       week number (in year) RR
#  @w   o   o   o       week day number or abbrev RR
#  @z   o   o   o   o   time zone
#
#  @S example: a bysetpos of -1 if combined with a MONTHLY frequency, and a
#  byweekday of (MO, TU, WE, TH, FR), will result in the last work day of every
#  month.
#
# SORT/COLOR/OMIT/INCLUDE NUMBER include/omit codes
#   0. d) day   event without starting time and with zero extent (all day)
#               no @s and no @e.
#   1. r) rem   event with starting time(s) but zero extent (reminder)
#               @s but no @e
#   2. a) act   action (event without starting time but with positive extent
#               - @e but no @s)
#   3. e) 10:50a event with starting time(s) and positive extent (each)
#               @s and @e
#   4. p)       due before today w/o prereqs - show on due date and today
#   5. w)       task with prerequisites and due on or after today
#   6. t)       task without prerequisites and due on or after today
#   7. u)       undated with or w/o prereqs - show today
#   8. b)       with begin date
#                   if begin date <= soondate and due > today
#                       show under Today with days until due
#                   elif begin date = tomorrow and due > tomorrow
#                       show under Tomorrow with days until due
#                   elif begin date <= soon and due > soon
#                       show under date with days until due
#   9. f)   X   finished (shows on date finished)
#  10.      !   note
#
#           tuple indices: agenda and items
#  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
# |YR|MN|DY|SO|SM|EM|PR|WN|QN|CO|K1|K2|K3|LC|WA|MA|ST|DS|DT|ID|SN|US|PJ|TG|NT
#  y  m  d  s     e  p  w  q  c  k1 k2 k3 l           t     i
#                groupby codes
#
#   YR, MN, DY      integer year, month and month day '_d': 0, 1 and 2
#   SO              sort code in [0,...,9] (see above)
#   SM              integer start minutes
#   EM              extent minutes
#   PR              priority
#   WN              week number in year [0,...,53]
#   QN              quarter number ['1st quarter',..., '4th quarter']
#   CO              context
#   K1, K2, K3      keyword 0, 1, 2:
#   LC              location
#   WA              locale weekday abbreviation ['Mon', ...]
#   MA              locale month abbreviation ['Jan', ...]
#   ST              locale formated (am/pm) start time integer days or ''
#   DS              item description (title)
#   DT              item details
#   ID              ID: relpath:starting_line:ending_line
#   SN              sortNames[SO]
#   US              user
#   PJ              project
#   TG              tags
#   NT              note
#   LR              leader

tracing_level = 0
#  enable_tracing = True
enable_tracing = False

cwd = os.getcwd()

oneday = datetime.timedelta(days = 1)
oneminute = datetime.timedelta(minutes = 1)

status_fmt = "%a %b %d"

id2hash = {}

if use_ampm:
    tdyfmt = "%I:%M:%S%p %a, %b %d"
    timefmt = "%I:%M%p"
    datetime_fmt = "%Y-%m-%d %I:%M%p"
    weekday_fmt = "%a %b %d"
    col_wdth = 6 # 11:45a
    c_fmt = "{0:^6}"
    r_fmt = "{0:>6}"
else:
    tdyfmt = "%H:%M:%S %a, %b %d"
    timefmt = "%H:%M"
    datetime_fmt = "%Y-%m-%d %H:%M"
    weekday_fmt = "%a %b %d"
    col_wdth = 5 # 11:45
    c_fmt = "{0:^5}"
    r_fmt = "{0:>5}"


# TODO: chech this for redundancy with those in etmParsers
comment_regex = re.compile(r'\s*#')
item_regex = re.compile(r'^\s*(\*|\!|\~|\++|\-+)\s+(\S.*)\s*$')
rel_date_regex = re.compile(r'^([-+])([0-9]+)')
extent_regex = re.compile(r'\+((\d+)([:\.]|h\s*))?((\d*)m?)?')
parens_regex = re.compile(r'^\s*\((.*)\),?\s*$')
leadingzero = re.compile(r'(?<!(:|\d))0+(?=\d)')
year_regex = re.compile(r'\!(\d{4})\!')

date_fmt = "%a %b %d"
beg_date_fmt = '''%a %b %d (week %W day %j)'''
end_date_fmt = '''%a %b %d, %Y'''

frequency_names = {
   u'M' : 'MINUTELY', # NEW
   u'H' : 'HOURLY',   # NEW
   u'd' : 'DAILY',
   u'w' : 'WEEKLY',
   u'm' : 'MONTHLY',
   u'y' : 'YEARLY',
   u'l' : 'LIST'
}

by_names = {
   u'w' : 'weekday',
   u'W' : 'weekno',
   u'm' : 'monthday',
   u'M' : 'month',
   u'S' : 'setpos'    # NEW
}

sortNames = {
        sortOrder['allday'] : 'all day events',
        sortOrder['reminder'] : 'reminders',
        sortOrder['event'] : 'events',
        sortOrder['action'] : 'actions',
        sortOrder['pastdue'] : 'past due tasks',
        sortOrder['waiting'] : 'tasks with unfinished prerequisites',
        sortOrder['task'] : 'tasks without unfinished prerequisites',
        sortOrder['undated'] : 'undated tasks',
        sortOrder['begin'] : 'begin by warnings',
        sortOrder['finished'] : 'finished tasks',
        sortOrder['note'] : 'notes'
        }

includeAbbr = {}

group_hash = {
            #  (0,1,2): (13, 14, 2, 0),
            (0,1,2): (14, 15, 2, 0),
            (0,7,1): (7, 0, 15),
            (0,6): (6, 0),
            (1,6): (15, 6),
            (0, 1, 6): (6, 0),
            #  (0,8): (8,0),
            (0,6,1): (6, 15, 0),
            (0,1): (15, 0),
            2: (14, 2),
            (2,14): (14,2,15),
            0: (0,),
            1: (15,),
            3: (20,),
            (1,2): (14, 15, 2)
            }

#  item_type = {'+': 'tasks', '-': 'tasks', '*': 'events', '~': 'actions', '!': 'notes'}

filterKeys = {
        'search'    : (17, 18),
        'context'   : (9,),
        'keyword'   : (10, 11, 12),
        'user'      : (21,),
        'location'  : (13,),
        'priority'  : (6,),
        'project'   : (22,),
        'tag'       : (23,),
        'file'      : (19,)
        }

tupleKeys=\
        u'YR|MN|DY|SO|SM|EM|PR|WN|QN|CO|K1|K2|K3|LC|WA|MA|ST|DS|DT|ID|SN|US|PJ|TG|NT|LR'.split('|')

#  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
# |YR|MN|DY|SO|SM|EM|PR|WN|QN|CO|K1|K2|K3|LC|WA|MA|ST|DS|DT|ID|SN|US|PJ|TG|NT|LR
#  yr mn dy so    em wn qn co k1 k2 k3 lc          ds    id    us pr t  n
#  y  m  d  s     e  w  q  c  k1 k2 k3 l           T     f     u  p  t

#            0  1  2  3
busyKeys = u'YR|MN|DY'.split('|')
#  busyKeys = u'YR|WN|MN|DY'.split('|')

autoKeys = [u'leader', u'P', u'DS', u'DT', u'ID', u'LR']

allowedKeys = {
        u'-' : [x for x in u'-+bcCdefgiklmMnoprsStuUwWz']+autoKeys+[u'preq'],
        u'+' : [x for x in u'-+bcCdefgiklmMnoprsStuUwWz']+autoKeys+[u'preq'],
        u'*' : [x for x in u'-+aAcCdegiklmMnrsStuUwWz'] + autoKeys,
        u'~' : [x for x in u'cdegklntUz'] + autoKeys,
        u'!' : [x for x in u'cdgklntUz'] + autoKeys,
        }

#  sort_str = u'dbsezaAgckltpUriCSWwMm-+uonf'
#  sort_keys = [x for x in sort_str]

omitKeys = { # letter key -> SO integer
        'a' : (sortOrder['action'],),       # action
        'b' : (sortOrder['begin'],),        # begin by
        'd' : (sortOrder['allday'],),       # all day event
        'e' : (sortOrder['event'],),        # event scheduled
        'f' : (sortOrder['finished'],),     # finished task
        'r' : (sortOrder['reminder'],),     # reminder
        'p' : (sortOrder['pastdue'],),      # past due task
        'w' : (sortOrder['waiting'],),      # waiting task (unfinished prereqs)
        't' : (sortOrder['task'],),         # task
        'u' : (sortOrder['undated'],),      # undated task
        'n' : (sortOrder['note'],),         # note
        }

abbreviations = {}
expand_abbrev = None
if abbreviationsFile and os.path.isfile(abbreviationsFile):
    fo = codecs.open(abbreviationsFile, 'r', file_encoding)
    lines = fo.readlines()
    fo.close()
    if lines:
        for line in lines:
            l = line.strip()
            if l:
                abbrv, replacement = l.split('|')
                if abbrv and replacement:
                    abbreviations[":%s:" % abbrv] = replacement
        expand_abbrev = make_xlat(abbreviations)

def add2list(lst, item):
    """Add item to lst if not already present using bisect to maintain order."""
    i = bisect.bisect_left(lst, item)
    if i != len(lst) and lst[i] == item:
        return()
    bisect.insort(lst, item)

contexts = []
keywords = []
locations = []

def getCompletions():
    global contexts, keywords, locations
    contexts = []
    keywords = []
    locations = []

    if contextsFile and os.path.isfile(contextsFile):
        fo = codecs.open(contextsFile, 'r', file_encoding)
        lines = fo.readlines()
        fo.close()
        if lines:
            for line in lines:
                l = line.strip()
                if l:
                    add2list(contexts, l)

    if keywordsFile and os.path.isfile(keywordsFile):
        fo = codecs.open(keywordsFile, 'r', file_encoding)
        lines = fo.readlines()
        fo.close()
        if lines:
            for line in lines:
                l = line.strip()
                if l:
                    add2list(keywords, l)

    if locationsFile and os.path.isfile(locationsFile):
        fo = codecs.open(locationsFile, 'r', file_encoding)
        lines = fo.readlines()
        fo.close()
        if lines:
            for line in lines:
                l = line.strip()
                if l:
                    add2list(locations, l)

    return(contexts, keywords, locations)

try:
    from os.path import relpath
except ImportError: # python < 2.6
    from os.path import curdir, abspath, sep, commonprefix, pardir, join
    def relpath(path, start=curdir):
        """Return a relative version of a path"""
        if not path:
            raise ValueError("no path specified")
        start_list = abspath(start).split(sep)
        path_list = abspath(path).split(sep)
        # Work out how much of the filepath is shared by start and path.
        i = len(commonprefix([start_list, path_list]))
        rel_list = [pardir] * (len(start_list)-i) + path_list[i:]
        if not rel_list:
            return curdir
        return join(*rel_list)

def logaction(file, logentry):
    pathname, ext = os.path.splitext(file)
    directory, name = os.path.split(pathname)
    logfile = os.path.join(directory, ".%s.log" % name)
    now = datetime.datetime.now().strftime("%Y-%m-%d %H:%M:%S")
    fo = codecs.open(logfile, 'a', file_encoding, 'replace')
    fo.write("### %s ### %s\n\n" % (now, logentry.rstrip()))
    fo.close()
    return(True)

def backup(file):
    pathname, ext = os.path.splitext(file)
    directory, name = os.path.split(pathname)
    bak = os.path.join(directory, ".%s-bk1.text" % name)
    if os.path.exists(bak):
        m_secs = os.path.getmtime(bak)
        m_date = datetime.date.fromtimestamp(m_secs)
    else:
        m_date = None
    # only backup if there is no backup or it is at least one day old
    if not m_date or m_date < datetime.date.today():
        for i in range(1, numbaks):
            baknum = numbaks - i
            nextnum = baknum + 1
            bakname = os.path.join(directory,".%s-bk%d.text" % (name, baknum))
            if os.path.exists(bakname):
                nextname = os.path.join(directory,".%s-bk%d.text" % (name,
                    nextnum))
                shutil.move(bakname, nextname)
        shutil.copy2(file, bak)
        return(True)
    return(False)

def linesGet(num_beg, num_end, file):
    fo = codecs.open(file, 'r', file_encoding, 'replace')
    lines = fo.readlines()
    fo.close()
    if num_end <= len(lines):
        return("\n".join([x.rstrip() for x in lines[num_beg-1:num_end]]))
    else:
        return('')

def linesAdd(lines, file):
    backup(file)
    new_lines = lines.split("\n")
    fo = codecs.open(file, 'r', file_encoding, 'replace')
    cur_lines = fo.readlines()
    fo.close()
    l = ["%s\n" % x.rstrip() for x in cur_lines]
    l.extend(["%s\n" % x.rstrip() for x in new_lines])
    fo = codecs.open(file, 'w', file_encoding, 'replace')
    fo.writelines(l)
    fo.close()
    changes = ["\n[+] %s\n" % new_lines[0]]
    for x in new_lines[1:]:
        changes.append("    %s\n" % x)
    logaction(file, "".join(changes))
    return(True)

def linesReplace(num_beg, num_end, lines, file):
    num_beg = int(num_beg)
    num_end = int(num_end)
    backup(file)
    new_lines = lines.split("\n")
    fo = codecs.open(file, 'r', file_encoding, 'replace')
    cur_lines = fo.readlines()
    fo.close()
    # leave any blank lines here to keep line numbers correct
    l = ["%s\n" % x.rstrip() for x in cur_lines]
    orig_lines = [x.rstrip() for x in l[num_beg - 1:num_end]]
    changes = ["\n[-] %s\n" % orig_lines[0]]
    for x in orig_lines[1:]:
        changes.append("    %s\n" % x)
    changes.append("[+] %s\n" % new_lines[0])
    for x in new_lines[1:]:
        changes.append("    %s\n" % x)
    del l[num_beg-1:num_end]
    new_lines.reverse()
    for x in new_lines:
        l.insert(num_beg - 1, "%s\n" % x.rstrip())
    fo = codecs.open(file, 'w', file_encoding, 'replace')
    fo.writelines(l)
    fo.close()
    logaction(file, "".join(changes))
    return(True)

def linesDelete(num_beg, num_end, file):
    backup(file)
    fo = codecs.open(file, 'r', file_encoding, 'replace')
    lines = fo.readlines()
    fo.close()
    l = ["%s\n" % x.rstrip() for x in lines]
    orig_lines = [x.strip() for x in l[int(num_beg) - 1:int(num_end)]]
    changes = ["\n[-] %s\n" % orig_lines[0]]
    for x in orig_lines[1:]:
        changes.append("    %s\n" % x)
    del l[int(num_beg)-1:int(num_end)]
    fo = codecs.open(file, 'w', file_encoding, 'replace')
    fo.writelines(l)
    fo.close()
    logaction(file, "".join(changes))
    return(True)


def daycolor(num_mins):
    "vary brightness according to num_mins between min_b and max_b, holding saturation and hue constant and return the corresponding rgb color triple"
    hue = 0         # use red
    saturation = 1
    min_b = 0
    max_b = 1
    #  max_minutes = 480
    max_minutes = 330
    brightness = min(max_b, min_b + (max_b-min_b)* num_mins/float(max_minutes))
    r,g,b = hsv_to_rgb(hue, saturation, brightness)
    r = int(r*255)
    g = int(g*255)
    b = int(b*255)
    return((r,g,b))

def checkKeys(hsh):
    ok = True
    msgs = []
    itemtype = hsh['leader'][0]
    for key in hsh:
        if key not in allowedKeys[itemtype]:
            ok = False
            msgs.append("    Unrecognized key '@%s'" % key)
            # probably OK to continue
    if itemtype in [u'-', u'+', u'!']:
        pass
    elif itemtype == u'*':
        if not ('d' in hsh or 'r' in hsh and hsh['r'] == 'l'):
            ok = False
            msgs.append("    'd' required but missing")
        if ('e' in hsh and 's' not in hsh):
            ok = False
            msgs.append(
                    "    either both 's' and 'e' or neither must be present in an item with type '%s'" % itemtype)
    return(ok, msgs)

dateKeys = [u'd', u'u']
listdateKeys = [u'+', u'-', u'f']
listintegerKeys = [u'a']
integerKeys = [u'b', u'C', u'i']

def insertItems(lst, tup, today):
    tmp = [x for x in tup]
    if tmp[0:3] != list(today) and tmp[3] in [4,5,6]:
        tmp[16] = c_fmt.format('')
    bisect.insort(lst, tuple(tmp))

def getTuples(begin_date, end_date):
    dtz_today, today, soondate = getToday()
    contexts, keywords, locations = getCompletions()
    currentHash = checkRotating()
    newVersion(currentHash)
    common_prefix, id2hash, lastModified, msgs = getAllHashes()
    sy,sm,sd = begin_date
    ey,em,ed = end_date
    ty,tm,td = today
    sdt = datetime.datetime(sy, sm, sd, due_hour, 0)
    edt = datetime.datetime(ey,em,ed,due_hour,0)
    tdt = datetime.datetime(ty,tm,td,due_hour,0)
    tupleList = []
    busyTimes = {} # date -> list of busy intervals
    busyList = []
    alertList = [] # (description, tuple of starttimes)
    pastdueIds = []
    next_due = {}
    for id, hsh in id2hash.items():
        f_dates = []
        u_dates = []
        f_hash = {}
        u_hash = {}
        if u'preq' in hsh and hsh[u'preq']:
            #  print "preq for:", hsh[u'DS']
            for item in hsh[u'preq']:
                itmHsh = id2hash[item]
                #  print "  ", item, itmHsh[u'DS'], itmHsh[u'rr'][0]
        for key in hsh:
            f_hash[key] = hsh[key]
            u_hash[key] = hsh[key]
        dates = []
        if u'o' in hsh and hsh[u'o'] == 's':
            if u'_f' in hsh:
                for fy,fm,fd in hsh[u'_f']:
                    f_dates.append(datetime.datetime(fy,fm,fd,due_hour,0))
            u_dates = hsh[u'rr'].between(tdt, edt, inc=True)
        elif u'_f' in hsh:
            if u'r' in hsh:
                # @o k is the default
                if u'o' not in hsh or hsh[u'o'] == 'k':
                    # keep - we should pop a date for each element in 'f'
                    for fy,fm,fd in hsh[u'_f']:
                        f_dates.append(datetime.datetime(fy,fm,fd,due_hour,0))
                    num_f = len(hsh[u'_f'])
                    next_date = hsh[u'rr'][num_f]
                    u_dates = hsh[u'rr'].between(next_date, edt, inc=True)
                elif hsh[u'o'] == 'r':
                    # restart - we want to reset the starting date to follow
                    # the last element from 'f'
                    for fy,fm,fd in hsh[u'_f']:
                        f_dates.append(datetime.datetime(fy,fm,fd,due_hour,0))
                    ny,nm,nd = hsh[u'_f'][-1]
                    last_date = datetime.datetime(ny,nm,nd,due_hour,0)
                    u_dates = hsh[u'rr'].between(last_date, edt)
            else:
                for fy,fm,fd in hsh[u'_f']:
                    f_dates.append(datetime.datetime(fy,fm,fd,due_hour,0))
        else:
            u_dates = hsh[u'rr'].between(sdt, edt, inc=True)
            if not u_dates:
                if hsh[u'rr'].after(sdt):
                    u_dates.append(hsh[u'rr'].after(sdt))
                if hsh[u'rr'].before(edt):
                    u_dates.append(hsh[u'rr'].before(edt))
        if f_dates:
            f_hash[u'SO'] = sortOrder['finished']   # 9
            f_hash[u'ST'] = c_fmt.format(' X')
        if u_dates:
            if u'f' in u_hash:
                del u_hash[u'f']
            if u'_f' in u_hash:
                del u_hash[u'_f']
            date = u_dates[0].replace(tzinfo=tzlocal())
            next_due[hsh[u'ID']] = date
            #  if u_hash[u'leader'] in [u'+', u'-']:
            if u_hash[u'leader'][0] in [u'+', u'-']:
                if date < dtz_today:
                    u_hash[u'SO'] = sortOrder['pastdue']  # 4
                else: # due after today
                    if u_hash['SO'] == sortOrder['undated']:
                        pass
                    elif u_hash[u'preq']:
                        u_hash[u'SO'] = sortOrder['waiting']   # 5
                    else:
                        u_hash[u'SO'] = sortOrder['task']   # 6

        if u'preq' in u_hash and id in next_due:
            # this task id is unfinished, not pastdue and has prereqs
            startingSO = u_hash[u'SO']
            waiting = False
            if startingSO == sortOrder['undated']:
                so = startingSO
                u_hash['SO'] = so
            else:
                so = sortOrder['waiting']
                if next_due[id] < dtz_today:
                    # This item is past due
                    so = sortOrder['pastdue']
                else:
                    so = sortOrder['task']
                for item in u_hash[u'preq']:
                    # check when the prereq is next due. If this is on or before
                    # the due date for the task, then the prereq is unfinished
                    if item in next_due:
                        if next_due[item] <= next_due[id]:
                            waiting = True
                            break
                    elif u'_f' not in id2hash[item]:
                        waiting = True
                if waiting:
                    # there must be at least one unfinished prereq
                    u_hash[u'SO'] = sortOrder['waiting']
                else:
                    u_hash[u'SO'] = so
        for (dates, itemHash) in [(f_dates, f_hash), (u_dates, u_hash)]:
            for date in dates:
                date = date.replace(tzinfo=tzlocal())
                tup = []
                begW = (date - (date.weekday()) * oneday).strftime(date_fmt)
                endW = (date + (6-date.weekday()) * oneday).strftime(date_fmt)
                yr, mn, dy, h, m, wn, wd = map(int, date.strftime(\
                        "%Y,%m,%d,%H,%M,%W,%w").split(','))
                # sunday first implies wd = 0 = sunday should be col 0
                if not sundayfirst:
                    # wd = 0 sunday should col 6
                    # wd = 1 = monday should be col 0
                    wd -= 1
                    if wd < 0:
                        wd = 6
                due = datetime.datetime(
                        yr,mn,dy,due_hour,0).replace(tzinfo=tzlocal())

                duedate = tuple(map(int, due.strftime("%Y,%m,%d").split(',')))
                if duedate == today and u'_a' in itemHash:
                    parts = itemHash[u'_a']
                    for item in parts:
                        try:
                            num_mins = int(item)
                            if num_mins > 1:
                                msg = minutes_msg % num_mins
                                #  msg = "%s %s" % (num_mins, minutes)
                                warn = "(%s %s)" % (num_mins, early_warning)
                            elif num_mins == 1:
                                msg = oneminute_msg
                                #  msg = "1 %s" % (minute)
                                warn = "(%s %s)" % (num_mins, early_warning)
                            else:
                                msg = "%s" % (rightnow_msg)
                                warn = "(%s)" % (event_beginning)
                            alert_time = date - num_mins * oneminute
                            alert_timefmt = alert_time.strftime(timefmt)
                            if use_ampm:
                                alert_timefmt = leadingzero.sub('',
                                        alert_timefmt)
                                alert_timefmt = r_fmt.format(
                                        (alert_timefmt[:-1]).lower())
                            alert = tuple((alert_time, alert_timefmt,
                                itemHash['DS'], warn, msg))
                            bisect.insort(alertList, alert)
                        except:
                            msgs.append("   %s" % itemHash[u'DT'])
                            msgs.append("    Could not convert '@a %s'"
                                    % itemHash['a'])
                days = (due - dtz_today).days
                wa, ma = date.strftime("%a,%b").split(',')
                itemHash[u'YR'] = yr
                itemHash[u'MN'] = mn
                itemHash[u'DY'] = dy
                if itemHash[u'SO'] == sortOrder['allday']:   #  0
                    itemHash[u'SM'] = None
                    itemHash[u'ST'] = c_fmt.format(' ===')
                elif itemHash[u'SO'] in [
                        sortOrder['action'], sortOrder['note'], 11]:
                    itemHash[u'SM'] = None
                    itemHash[u'ST'] = c_fmt.format('')
                elif itemHash[u'SO'] in [sortOrder['pastdue'],
                        sortOrder['waiting'], sortOrder['task'],
                        sortOrder['undated'], sortOrder['begin']]:
                    itemHash[u'SM'] = days
                    itemHash[u'ST'] = ' ' * col_wdth
                elif itemHash[u'SO'] == sortOrder['finished']:   # 9
                    itemHash[u'SM'] = None
                    itemHash[u'ST'] = c_fmt.format(' X')
                elif itemHash[u'SO'] == sortOrder['reminder']:  # 1
                    itemHash[u'SM'] = h*60+m
                    itemHash[u'ST'] = ' ' * col_wdth
                elif itemHash[u'SO'] == sortOrder['event']:   # 3
                    itemHash[u'SM'] = h*60+m
                    st = date.strftime(timefmt)
                    if use_ampm:
                        st = leadingzero.sub(' ', st[:-1].lower())
                    itemHash[u'ST'] = r_fmt.format(st)
                itemHash[u'SN'] = sortNames[itemHash[u'SO']]
                itemHash[u'WN'] = "week %2s: %s - %s" % (wn, begW, endW)
                itemHash[u'QN'] = "%s quarter" % \
                        ['1st', '2nd', '3rd', '4th'][(mn-1)//3]
                itemHash[u'WA'] = wa
                itemHash[u'MA'] = ma
                for key in tupleKeys:
                    if key not in itemHash:
                        msgs.append("    Error: missing key, '%s', in %s" %
                                (key, itemHash[u'DT']))
                        break
                    tup.append(itemHash[key])
                b = tup[17]
                mtch = year_regex.search(b)
                if mtch:
                    startyear = mtch.group(1)
                    numyrs = year2string(startyear, yr)
                    b = year_regex.sub(numyrs, b)
                    tup[17] = b
                if itemHash[u'SO'] != sortOrder['undated']:   # 7
                    insertItems(tupleList, tup, today)
                if itemHash[u'SO'] in [sortOrder['pastdue'],
                        sortOrder['undated']]:   # [4,7]
                    if itemHash[u'SO'] == sortOrder['pastdue']:  # 4
                        if u'o' in itemHash and itemHash[u'o'] == u's':
                            continue
                    if itemHash[u'ID'] in pastdueIds:
                        # only show one instance of past due tasks
                        continue
                    else:
                        pastdueIds.append(itemHash[u'ID'])
                    tup[0:3] = today
                    tup[14], tup[15] = dtz_today.strftime("%a,%b").split(',')
                    if duedate <= soondate:
                        tup[4] = days
                        if days != 0:
                            dstr = "%+d" % days
                        else:
                            dstr = ''
                        tup[16] = c_fmt.format(dstr)
                        itemHash[u'ST'] = c_fmt.format(unicode(days))
                        insertItems(tupleList, tup, today)
                if itemHash[u'SO'] in [sortOrder['waiting'],
                        sortOrder['task']] and u'_b' in itemHash:
                    beg_by = max(dtz_today, due - itemHash[u'_b'] * oneday)
                    days = (due - beg_by).days
                    begdate = tuple(map(int,
                        beg_by.strftime("%Y,%m,%d").split(',')))
                    if begdate <= soondate and days > 0:
                        tup[4] = days
                        dstr = "%+d" % days
                        tup[16] = c_fmt.format(dstr)
                        tup[3] = sortOrder['begin']  # 8
                        tup[20] = sortNames[sortOrder['begin']]
                        tup[0:3] = map(int, beg_by.strftime(
                            "%Y,%m,%d").split(','))
                        insertItems(tupleList, tup, today)
                # add busy intervals
    return(common_prefix, tupleList, alertList, id2hash, lastModified, currentHash, contexts, keywords, locations, msgs)

def newVersion(currentHash):
    v_file = os.path.join(etmdir, 'etm_version.txt')
    if os.path.isfile(v_file):
        fo = codecs.open(v_file, 'r', file_encoding)
        try:
            current_version = int(fo.readline().strip())
        except:
            current_version = 0
        fo.close()
    else:
        current_version = 0
    if current_version and 'x' not in version and int(version) > current_version:
        fo = codecs.open(v_file, 'w', file_encoding)
        fo.write("%s" % version)
        fo.close()
        actn = "~ installed etm version %s @e +0 @d %s @g http://www.duke.edu/~dgraham/ETM/CHANGES @n press 'g' with this action selected to display CHANGES." % (version, get_today().strftime("%Y-%m-%d"))
        cur_actn = currentHash['actions']
        linesAdd(actn, cur_actn)
        return(True)
    else:
        return(False)

def checkLines(lines):
    """
        Take a string with newline chars and return the corresponding hash
        and a new, possibly modified string.
    """
    dtz_today, today, soondate = getToday()
    hsh = lines2hsh(lines)
    if not hsh:
        return(['missing entry'], {}, '')
    if hsh[u'leader'] in ['*', '~'] and u'd' not in hsh:
        hsh[u'd'] = "%d-%02d-%02d" % today
    msg = checkHash(hsh, today)
    s = hash2Str(hsh)
    return(msg, hsh, s)

def hash2Str(hsh):
    if u'DS' not in hsh: hsh[u'DS'] = ''
    sl = ["%s %s" % (hsh['leader'], hsh['DS'])]
    for key in sort_keys:
        if key in hsh and hsh[key]:
            value = hsh[key]
            sl.append("@%s %s" % (key, value))
    return(" ".join(sl))

# def hash2NewStr(hsh):
#     if u'DS' not in hsh: hsh[u'DS'] = ''
#     sl = ["%s %s" % (hsh['leader'], hsh['DS'])]
#     for key in sort_keys:
#         if key in hsh and hsh[key]:
#             value = hsh[key]
#             sl.append("@%s %s" % (key, value))
#     return(" ".join(sl))

def checkHash(itemHash, today):
    """
        Check itemHash for presence of required fields and unknown fields and
        parse @d, @s and @z for local time. Compute and add tuple requirements
        to returned hash.
    """
    global contexts, keywords, locations
    msgs = []
    if u'leader' in itemHash:
        # item
        #  itemHash[u'LR'] = "{0:>4}".format(itemHash[u'leader'])
        itemHash[u'LR'] = itemHash[u'leader']
        itemType = itemHash[u'leader'][0]
    else:
        # not OK
        msgs.append('    Bad item entry, missing type leader. Skipping item.')
        # bail out, we need the type to continue
        return(msgs)
    undated = False

    ok, ms = checkKeys(itemHash)
    if not ok:
        msgs.extend(ms)
        ms = []

    # fix action extent entered without a '+'
    if itemType == '~' and u'e' in itemHash and int_regex.match(itemHash[u'e']):
        # add the missing '+'
        itemHash[u'e'] = "+%s" % itemHash[u'e']

    if u'P' in itemHash:
        itemHash[u'PJ'] = itemHash[u'P']
    else:
        msgs.append("    missing project name")
        itemHash[u'PJ'] = None

    if u'p' in itemHash:
        if itemHash[u'p']:
            try:
                p = int(itemHash[u'p'])
                assert(p >= 1 and p <= 9)
                itemHash[u'PR'] = "Priority %s" % itemHash[u'p']
            except:
                msgs.append("    An integer argument between 1 and 9 is needed in '@p %s'" % itemHash[u'p'])
    else:
        itemHash[u'PR'] = 'no priority'

    if u'U' in itemHash:
        itemHash[u'US'] = itemHash[u'U']
    else:
        itemHash[u'US'] = 'no user'

    if u'n' in itemHash:
        itemHash[u'NT'] = itemHash[u'n']
    else:
        itemHash[u'NT'] = ''

    if u't' in itemHash:
        itemHash[u'TG'] = itemHash[u't']
    else:
        itemHash[u'TG'] = 'no tags'

    # fix integers
    for key in listintegerKeys:
        if key in itemHash:
            upkey = unicode("_%s" % key)
            lst = []
            m = parens_regex.match(itemHash[key])
            try:
                if m:
                    parts = m.group(1).split(',')
                    for item in parts:
                        lst.append(int(item))
                else:
                    lst.append(int(itemHash[key]))
            except:
                msgs.append("    Could not convert '@%s %s' to integers"
                        % (key, itemHash[key]))
            itemHash[upkey] = tuple(lst)

    for key in integerKeys:
        if key in itemHash:
            upkey = unicode("_%s" % key)
            try:
                itemHash[upkey] = int(itemHash[key])
            except:
                msgs.append("    An integer argument is needed in '@%s %s'" %
                        (key, itemHash[key]))

    timezone = None
    if u'z' in itemHash:
        if itemHash[u'z'] != 'none':
            timezone = gettz(itemHash[u'z'])
            if not timezone:
                msgs.append("    Unrecognized value for time zone in '@z %s'" %
                    itemHash[u'z'])
                del itemHash[u'z']
            else:
                itemHash[u'_z'] = timezone
    elif auto_set_timezone and possible_timezones:
        itemHash[u'z'] = possible_timezones[0][0]
        itemHash[u'_z'] = gettz(itemHash[u'z'])

    start_minutes = []
    if u's' in itemHash:
        s_str = itemHash[u's']
        items = []
        m = parens_regex.match(s_str)
        if m:
            items = m.group(1).split(',')
        else:
            items.append(s_str)
        ftimes = []
        for item in items:
            try:
                st = duparse(item)
                startingtime = st.strftime("%H,%M")
                ftimes.append(st.strftime(timefmt))
                h, m = map(int, startingtime.split(','))
                start_minutes.append(h*60+m)
            except:
                ftimes = []
                msgs.append("    Could not parse '@s %s'" % item)
                del itemHash[u's']
        if ftimes:
            s = "(%s)" % ', '.join(ftimes)
            if use_ampm:
                s = embeddedzero.sub('', s)
                s = embeddedampm.sub('', s)
                s = s.lower()
            itemHash[u's'] = s
    else:
        start_minutes.append(due_hour*60)
    itemHash[u'_s'] = tuple(start_minutes)

    d_str = None
    for key in dateKeys:  # [u'd', u'u']:
        if key in itemHash:
            date_str = itemHash[key]
            m = rel_date_regex.match(date_str)
            if m:
                # we have a relative date in the form '+|- integer'.
                if m.group(1) == "+":
                    date = datetime.date.today() + int(m.group(2))*oneday
                else: # m.group(1) == "-":
                    date = datetime.date.today() - int(m.group(2))*oneday
                d_str = date.strftime("%Y-%m-%d")
                itemHash[key] = d_str
            else:
                # we presumably have a date to parse
                d_str = itemHash[key]
            try:
                dt = duparse(d_str)
                upkey = u'_%s' % key
                itemHash[upkey] = tuple(map(int,
                    dt.strftime("%Y,%m,%d").split(',')))
                itemHash[key] = dt.strftime("%Y-%m-%d")
            except:
                msgs.append("    error parsing date '@%s %s'."
                        % (key, date_str))
                del itemHash[key]

    for key in listdateKeys: #  [u'+', u'-', u'f']
        if key in itemHash:
            dates = []
            items = []
            d_str = itemHash[key]
            m = parens_regex.match(d_str)
            if m:
                items = [x.strip() for x in m.group(1).split(',')]
            else:
                items.append(d_str)
            fdates = []
            for item in items:
                try:
                    dt = duparse(item)
                    fdates.append(dt.strftime("%Y-%m-%d"))
                    dates.append(tuple(map(int,
                        dt.strftime("%Y,%m,%d").split(','))))
                except:
                    dates = []
                    msgs.append("    Could not parse '%s' in '@%s'"
                            % (item, key))
            if dates:
                upkey = unicode("_%s" % key)
                itemHash[upkey] = tuple(dates)
                itemHash[key] = "(%s)" % ", ".join(fdates)

    if u'_d' in itemHash:
        undated = False
    else:
        if u'_f' in itemHash and itemHash[u'_f']:
            itemHash[u'_d'] = itemHash[u'_f'][-1]
        else:
            itemHash[u'_d'] = today
            undated = True

    itemHash[u'EM'] = 0

    if u'e' in itemHash:
        e_str = itemHash[u'e']
        m = extent_regex.match(e_str)
        if m:
            # minutes or hours and minutes +3h; +3:30
            minutes = 0
            hrs = m.group(2)
            if hrs:
                minutes += int(hrs)*60
            mins = m.group(5)
            if mins:
                if '.' in e_str:
                    minutes += int(mins) * 6
                else:
                    minutes += int(mins)
            itemHash[u'EM'] = minutes
        else: # must be a time, we must have a single starting time
            if len(itemHash[u'_s']) > 1:
                msgs.append("    Integer minutes should be used with multiple starting times, '@e %s' %s" %
                        (e_str, itemHash['s']))
            if u's' in itemHash:
                try:
                    dt = duparse(e_str)
                    h,m = map(int, dt.strftime("%H,%M").split(','))
                    itemHash[u'EM'] = h*60+m - itemHash[u'_s'][0]
                    if itemHash['EM'] < 0:
                        msgs.append("    Negative extent or an ending time  earlier than starting time.")
                        del itemHash[u'e']
                        del itemHash[u'EM']
                except:
                    esn = None
                    msgs.append("    Could not parse '@e %s'" % e_str)
                    del itemHash[u'e']
                    del itemHash[u'EM']
        if u'EM' in itemHash:
            minutes = itemHash[u'EM']
            if file_totals_fmt == 1:
                # hours and tenths
               itemHash[u'e'] = "+%s" % (((minutes//6+(minutes%6 > 0))*6)/60.0)
            elif file_totals_fmt == 2:
                # hours and minutes
                itemHash[u'e'] = "+%d:%02d" %  (minutes//60, minutes%60)
            else:
                itemHash[u'e'] = "+%d" %  (minutes)
    if u'l' in itemHash:
        itemHash[u'LC'] = itemHash[u'l']
        if addFileLocations:
            add2list(locations, itemHash[u'l'])
    else:
        itemHash[u'LC'] = 'no location'

    if u'c' in itemHash:
        itemHash[u'CO'] = itemHash[u'c']
        if addFileContexts:
            add2list(contexts, itemHash[u'c'])
    else:
        itemHash[u'CO'] = 'no context'

    itemHash[u'K1'] = u'no keyword'
    itemHash[u'K2'] = u''
    itemHash[u'K3'] = u''
    if u'k' in itemHash:
        if addFileKeywords:
            add2list(keywords, itemHash[u'k'])
        parts = itemHash[u'k'].split(':')
        if len(parts) >= 1:
            itemHash[u'K1'] = unicode(parts[0])
        if len(parts) >= 2:
            itemHash[u'K2']  = unicode(parts[1])
        if len(parts) >=3:
            itemHash[u'K3']  = unicode(':'.join(parts[2:]))

    # hash / tuple SO entries
    if itemType == u'*':
        if u's' in itemHash:
            if u'e' in itemHash:
                itemHash[u'SO'] = sortOrder['event']        # 3
            else:
                itemHash[u'SO'] = sortOrder['reminder']     # 1
                itemHash[u'EM'] = sortOrder['allday']       # 0
        else:
            itemHash[u'SO'] = sortOrder['allday']           # 0
    elif itemType == u'~':
        itemHash[u'SO'] = sortOrder['action']               # 2
    elif itemType in [u'+', u'-']:
        itemHash[u'EM'] = 0
        if undated:
            itemHash[u'SO'] = sortOrder['undated']          # 7
        elif u'_d' in itemHash:
            if itemHash[u'_d'] < today:
                    itemHash[u'SO'] = sortOrder['pastdue']  # 4
            elif not undated: # and due on or after today
                # if there is a relevant begin by date, handle it in getTuples
                if u'preq' in itemHash and itemHash[u'preq']:
                    itemHash[u'SO'] = sortOrder['waiting']  # 5
                else:
                    itemHash[u'SO'] = sortOrder['task']     # 6
        else:
            # if there are finish dates, handle them in getTuples
            if itemHash[u'preq']:
                itemHash[u'SO'] = sortOrder['waiting']      # 5
            else:
                itemHash[u'SO'] = sortOrder['task']         # 6

    elif itemType == u'!':
        itemHash[u'SO'] = sortOrder['note']                 # 10
    else:
        print "missing SO", itemHash['DT']
    msgs.extend(getRuleSet(itemHash))

    dt = [itemHash[u'leader'], itemHash[u'DS']]
    for key in sort_keys:
        if key in itemHash:
            dt.append("@%s %s" % (key, itemHash[key]))
    return(msgs)

def getRuleSet(itemHash):
    """Return the rrule for the repeated itemHash."""
    # The duedate for repeated tasks will be reset each time the task
    # is finished so the duedate should be for the next unfinished
    # repetition. For events (e.g. birthdays, faculty meetings, etc),
    # the duedate should be for the first event.
    msgs = []
    itemHash[u'rr'] = None

    # create an empty ruleset
    rr = rruleset(cache=True)

    if u'r' in itemHash:
        if itemHash[u'r'] in frequency_names:
            frequency = frequency_names[itemHash[u'r']]
        else:
            msgs.append("    Unrecognized frequency '@r %s'" % itemHash['r'])
            # no point in continuing
            return(msgs)
        if u'_f' in itemHash and itemHash[u'_f'] and 'o' in itemHash and\
                itemHash[u'o'] == 'r':
            itemHash[u'_d'] = itemHash[u'_f'][-1]

    else:
        if u'_f' in itemHash and itemHash[u'_f']:
            itemHash[u'_d'] = itemHash[u'_f'][-1]
        elif u'_d' not in itemHash:
            itemHash[u'_d'] = today
        y,m,d = itemHash[u'_d']
        local_dm = []
        for s in itemHash[u'_s']:
            H = s//60
            M = s%60
            if u'_z' in itemHash:
                d = datetime.date(y,m,d)
                t = datetime.time(H, M)
                dt = datetime.datetime.combine(d,t)
                dtz = dt.replace(tzinfo = itemHash[u'_z'])
                dtl = dtz.astimezone(tzlocal())
                y,m,d,H,M = map(int, dtl.strftime("%Y,%m,%d,%H,%M").split(','))
                local_dm.append((y,m,d,H*60+M))

            rr.rdate(datetime.datetime(y,m,d,H,M))
        if local_dm:
            # this should not be necessary - we will get local dates and SM from
            # the rrule
            itemHash[u'_ldm'] = tuple(local_dm)
        itemHash[u'rr'] = rr
        return(msgs)

    #  until = itemHash.setdefault(u'_u', None)

    include = itemHash.setdefault(u'_+', None)

    exclude = itemHash.setdefault(u'_-', None)

    first_d = None

    if u'_d' in itemHash:
        try:
            duedate = datetime.datetime(*itemHash[u'_d'])
        except:
            duedate = None
            msgs.append("    Could not parse '@d %s'" % itemHash[u'_d'])

    if u'w' in itemHash:
        # fix three character weekday abbreviations
        weekdays = itemHash[u'w'].upper()
        for x in ['MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT', 'SUN']:
            weekdays = re.sub(x, x[:2], weekdays)
        itemHash[u'_w'] = itemHash[u'w'] = weekdays

    try:
        frequency
    except:
        frequency = 'LIST'
    if frequency == 'LIST':
        # listonly
        if u'_+' not in itemHash:
            msgs.append("   Missing but required key '@+")
            return(msgs)
        elif itemHash[u'_+']:
            for date in itemHash[u'_+']:
                for s in itemHash[u'_s']:
                    y,m,d = date
                    H = s//60
                    M = s%60
                    if u'_z' in itemHash:
                        dt = datetime.datetime(y,m,d,H,M)
                        dtz = dt.replace(tzinfo=itemHash[u'_z'])
                        dtl = dtz.astimezone(tzlocal())
                        y,m,d,H,M = map(int,
                                dtl.strftime("%Y,%m,%d,%H,%M").split(','))
                    rr.rdate(datetime.datetime(y,m,d,H,M))
            itemHash[u'rr'] = rr
            return(msgs)

    # if we get here we're not list-only so we must have key '_d'
    if u'_d'  not in itemHash:
        msgs.append("    Missing but required key '@d")
        return(msgs)

    # start accumulating the rrule components
    rule = [frequency]

    if u'_i' in itemHash:
        rule.append("interval=%s" % itemHash[u'_i'])

    if u'_C' in itemHash:
        rule.append("count=%s" % itemHash[u'_C'])

    if u'_u' in itemHash and itemHash[u'_u']:
        y,m,d = itemHash[u'_u']
        dt = datetime.datetime(y,m,d,due_hour,0)
        if u'_z' in itemHash:
            dtz = dt.replace(tzinfo=itemHash[u'_z'])
            dt = dtz.astimezone(tzlocal())
        y,m,d,H,M = map(int, dt.strftime("%Y,%m,%d,%H,%M").split(','))
        utl = ",".join(map(unicode, [y,m,d,H,M]))
        rule.append("until=datetime.datetime(%s)" % utl)

    # we need a list of rules which are clones save for starting time
    rules = []
    y,m,d = itemHash[u'_d']
    #  this_rule = [x for x in rule]
    for s in itemHash[u'_s']:
        start_rule = deepcopy(rule)
        H = s//60
        M = s%60
        if u'_z' in itemHash:
            dt = datetime.datetime(y,m,d,H,M)
            dtz = dt.replace(tzinfo=itemHash[u'_z'])
            dtl = dtz.astimezone(tzlocal())
            y,m,d,H,M = map(int, dtl.strftime("%Y,%m,%d,%H,%M").split(','))
        dtstart = ",".join(map(unicode, [y,m,d,H,M]))
        start_rule.append("dtstart=datetime.datetime(%s)" % dtstart)

        for key in by_names.keys():
            if key in itemHash:
                start_rule.append("by%s=%s" % (by_names[key],
                    itemHash[key]))

        this_rule = ', '.join(start_rule)

        try:
            eval("rr.rrule(rrule(%s))" % this_rule)
        except:
            msgs.append("    Could not parse rule: '%s'" % this_rule)

        includedates = []
        if include != None:
            for date in include:
                y,m,d = date
                dt = ",".join(map(unicode, [y,m,d,H,M]))
                includedates.append(dt)

        excludedates = []
        if exclude != None:
            for date in exclude:
                y,m,d = date
                dt = ",".join(map(unicode, [y,m,d,H,M]))
                excludedates.append(dt)

        if includedates:
            for dt in includedates:
                try:
                    eval("rr.rdate(datetime.datetime(%s))" % dt)
                except:
                    msgs.append("    Could not parse '@+ %s'" % itemHash[u'+'])
                    return(False)
        if excludedates:
            for dt in excludedates:
                try:
                    eval("rr.exdate(datetime.datetime(%s))" % dt)
                except:
                    msgs.append("    Could not parse '@- %s'" % itemHash[u'-'])
    if len(msgs) > 0:
        itemHash['rr'] = None
    else:
        itemHash['rr'] = rr
    return(msgs)


def proj2hsh(s):
    """
        Returns a hash corresponding to the project line s.
    """
    hsh = {}
    msgs = []
    parts = [x.strip() for x in s.split('@')]
    if len(parts) > 0:
        proj = parts.pop(0).strip()
    else:
        msgs.append("    Could not parse project line '%s'" % s)
        return(msgs, {})
    if len(proj) > 0 and proj[0] in ['~', '*', '!', '-', '+']:
        hsh[u'P'] = ''
    else:
        hsh[u'P'] = proj
    for part in parts:
        hsh[part[0]] = part[1:].strip()
    return(msgs, hsh)

def lines2hsh(s, l=None, f=None, r=None, dfltHash={}):
    """
        Take a string with newline chars and return a corresponding hash with
        an id based on the lines, l, and the file's relative path, f, using the
        hash r to store prerequisites.
    """
    hsh = {}
    # handle abbreviations
    if expand_abbrev:
        s = expand_abbrev(s)

    parts = at_regex.split(s)
    #  print "newlines2hsh", parts
    if l and f and r:
        try:
            id = "%s:%s:%s" % (f, l[0], l[-1])
            hsh[u'ID'] = id
        except:
            print "\nline2hsh except\n  ", "'%s'" % s.strip(), \
                    "l:", l, "f:", f, "r:", r
            return {}
    else:
        # we're creating a new item
        id = None
        hsh[u'P'] = None
        hsh[u'ID'] = id

    m = item_regex.match(parts.pop(0))
    if m:
        leader = m.group(1)
        level = len(leader)
        itemType = leader[0]
        hsh[u'leader'] = leader
        # only use defaults for keys allowed for the item type
        for key in dfltHash:
            if key in allowedKeys[itemType]:
                hsh[key] = dfltHash[key]
        hsh[u'DT'] = s.strip()
        hsh[u'DS'] = m.group(2)
        if id and itemType in ['-', '+']:
            if itemType == '-':
                r[level] = [id]
            elif itemType == '+':
                r.setdefault(level, []).append(id)
            for key in r:
                if key > level:
                    r[key] = []
            if level-1 in r:
                tmp = []
                for i in range(level):
                    tmp.extend(r[i])
                hsh[u'preq'] = tmp
    else:
        return({})
    for part in parts:
        if len(part) >= 2:
            if part[0] == 'n':
                # remove leading spaces and tabs but leave other leading whitespace
                # and remove all trailing whitespace
                content = leadingspace_regex.sub('', part[1:].rstrip())
            else:
                # replace consecutive whitespace characters with single space
                # for all fields other than notes
                content = " ".join([x for x in ws_regex.split(part[1:]) if x])
            hsh[part[0]] = content
    return(hsh)

def hashes(physical_lines, f, dfltHash):
    """A generator returning a hash for each physical line in physical lines
    each with an id based on the line numbers and the file's relative path, f.
    Prerequisites are computed for each task and added to the hash using the
    logic in which '+' adds the previous item to the current one as prerequisites
    for the next group of lower level tasks.
    """
    linenum = 1 # we removed the first project line
    logical_line = []
    linenums = []
    r = {}
    r[0] = []
    for line in physical_lines:
        linenums.append(linenum)
        linenum += 1
        if comment_regex.match(line):
            continue
        stripped = line.strip()
        if stripped and stripped[0] in ['*', '+', '-', '!', '~']:
            if logical_line:
                yield lines2hsh(''.join(logical_line), linenums, f, r, dfltHash)
            logical_line = []
            linenums = []
            logical_line.append(line)
        elif stripped:
            # a line which does not continue, end of logical line
            logical_line.append(line)
    if logical_line:
        # end of sequence implies end of last logical line
        yield lines2hsh(''.join(logical_line), linenums, f, r, dfltHash)


def getFileHashes(f, r, file2ids={}, id2hash={}, today=None):
    """
        Process the lines in file f into hashes and add the relevant entries
    """
    global contexts, keywords, locations
    fo = codecs.open(f, 'r', file_encoding)
    lines = fo.readlines()
    # make sure we have a trailing new-line
    fo.close()
    msgs = []
    lines.append('\n')
    dfltHash = {}
    ms, dfltHash = proj2hsh(lines.pop(0))
    if ms: msgs.extend(ms)
    if not dfltHash[u'P']:
        msgs.append("Bad project line: skipping %s" % f)
    # clear any existing entries from id2hash and then from file2ids[r]
    if r in file2ids:
        for id in file2ids[r]:
            if id in id2hash:
                del id2hash[id]
    file2ids[r] = []
    msgs = []
    for h in hashes(lines, r, dfltHash):
        if h:
            ms = checkHash(h, today)
            if ms:
                ms.insert(0,  "  '%s'" % h['DT'])
                ms.insert(0, "Skipping %s" % h['ID'])
            else:
                try:
                    id2hash[h['ID']] = h
                    file2ids[r].append(h['ID'])
                except:
                    ms.append("bad hash in %s: %s" % (r, repr(h)))
        msgs.extend(ms)
    return(msgs)

def getFiles(d=None):
    """yield the list of files in topdir and its subdirectories whose
    names match pattern."""
    pattern='[!.]*.text'
    filelist = []
    if d:
        paths = [d]
    else:
        paths = [etmActions, etmEvents, etmNotes, etmTasks, etmdata]
    common_prefix = os.path.commonprefix(paths)
    for d in paths:
        if d:
            for path, subdirs, names in os.walk(d, followlinks=True):
                for name in names:
                    if fnmatch.fnmatch(name, pattern):
                        full_path = os.path.join(path,name)
                        rel_path = relpath(full_path, common_prefix)
                        tup = (full_path, rel_path)
                        add2list(filelist, tup)
    return(common_prefix, filelist)

def needsUpdating(lastModified = {}):
    if lastModified:
        common_prefix, filelist = getFiles()
        for f, r in filelist:
            if (f, r) not in lastModified:
                #  print "needsUpdating", (f, r), "not in lastModified"
                return(True)
            if os.path.getmtime(f) != lastModified[(f, r)]:
                #  print "needsUpdating: mtime", os.path.getmtime(f), "for", f, \
                        #  "not equal to ", lastModified[(f,r)]
                return(True)
        for (f, r) in lastModified:
            if (f, r) not in filelist:
                #  print "needsUpdating", (f, r), "not in filelist"
                return(True)
    return(False)

def getAllHashes():
    dtz_today, today, soondate = getToday()
    numfiles = 0
    id2hash = {}
    file2ids = {}
    lastModified = {}
    common_prefix, filelist = getFiles()
    msgs = []
    for f,r in filelist:
        lastModified[(f,r)] =  os.path.getmtime(f)
        msgs.extend(getFileHashes(f, r, file2ids, id2hash, today))
    return(common_prefix, id2hash, lastModified, msgs)

def getQuarters(date):
    """
        Return the beginning date of the 1st quarter before the current
        quarter and the ending date of the 2nd quarter after the current
        quarter.
    """
    month = date.month
    year = date.year
    # the number of the current quarter in (1, 2, 3, 4)
    quarter = (month-1)//3+1
    # start 1 quarter back
    if quarter == 1:
        begQuarter = 4
        begYear = year - 1
    else:
        begQuarter = quarter - 1
        begYear  = year
    # end 2 quarters forward
    if begQuarter == 1:
        endQuarter = 4
        endYear = year
    else:
        endQuarter = (begQuarter+3)%4
        endYear = year + (begQuarter+3)//4
    # the month that begins the relevant quarter
    begMonth = (begQuarter-1)*3+1
    begDate = datetime.date(begYear, begMonth, 1)
    # the month that ends the relevant quarter
    nextMonth =((endQuarter-1)*3+4)%12
    if endQuarter == 4:
        endYear += 1
    endDate = datetime.date(endYear, nextMonth, 1) - oneday
    return(begDate, endDate)

def getView(tuples, opts, id2hash=id2hash):
    if not opts:
        return()
    if type(opts) == dict:
        options = opts
    else:
        if type(opts) == list:
            opt_lst = opts
            p = opt_lst.pop(0)
        else:
            opt_lst = []
            tmp = re.split('\s+-(?!\d)', opts)
            p = tmp.pop(0)
            for x in tmp:
                if not x:
                    continue
                opt_lst.extend(["-%s" % x[0], ("%s" % x[1:]).strip()])
        options = get_opts(nameHash[p], opt_lst)
    if 'cols' in options and 'F' in options['cols']:
        h, data, options, busy = make_tree(tuples, options, id2hash)

    else:
        tups, options, busy = opts2Tuples(tuples, options)
        begin_dt = duparse('%s-%s-%s' % options['begin_date'])
        end_dt = duparse('%s-%s-%s' % options['end_date']) - oneday

        data = ['', '', 5, options['cols'], 0, tups]
        h = "%s ~ %s" % (begin_dt.strftime(beg_date_fmt),
                end_dt.strftime(end_date_fmt))
    return(h, data, options, busy)

def getBusy(busytimes, opts):
    if not opts:
        return()
    if type(opts) == list:
        opt_lst = opts
        p = opt_lst.pop(0)
    else:
        opt_lst = []
        tmp = re.split('\s+-(?!\d)', opts)
        p = tmp.pop(0)
        for x in tmp:
            if not x:
                continue
            opt_lst.extend(["-%s" % x[0], ("%s" % x[1:]).strip()])
    options = get_opts(nameHash['b'], opt_lst)
    parse_opts(options)
    dt = data2Busy(busytimes, options)
    l = [htmlWrap(*l) for l in dt]
    l.insert(0, '<pre>')
    l.append('</pre>')
    return("\n".join(l))


def group_sort(list_of_tuples, column_numbers):
    """ Group tuples sharing the same 'column_number' elements and return
        a generator for (elements, corresponding list of tuples).
        """
    if type(column_numbers) == int:
        key = itemgetter(column_numbers)
    else:
        key=lambda cols: [cols[i] for i in column_numbers]

    lst = sorted(list_of_tuples, key=key)
    for k, group in groupby(lst, key):
        yield k, [g for g in group]

def expand_child(child, prefix, totalsfirst=False, show_leaves=True):
    """
        Each child is a tuple
            0: header str
            1: detail str
            2: summary_col
            3: groupby_cols (a list of tuples)
            4: starting col
            5: list of data tuples
        Group tuples by the contents of groupby_cols[starting_col] and return a
        list of the resulting children with starting_col incremented by 1.
    """
    if not has_children(child, show_leaves):
        return([])
    ret_lst = []
    if len(child) > 6:
        header, details, summary_col, groupby_cols, starting_col,\
                lst_of_tuples, so = child
    else:
        header, details, summary_col, groupby_cols, starting_col,\
                lst_of_tuples = child
        so = None

    len_tups = len(lst_of_tuples[-1])
    # 0 ... 25 are the normal tuple components
    #  print "gb1", groupby_cols, len_tups, lst_of_tuples[-1][26:]
    if len_tups > 26:
        groupby_cols = range(26, len_tups)
        len_tups -= 1
    groupby_cols = [groupby_cols[i] for i in range(len(groupby_cols)) if
        groupby_cols[i] if (type(groupby_cols[i]) == tuple or groupby_cols[i] < len_tups)]
    #  print "gb2", groupby_cols, len_tups, lst_of_tuples[-1][26:len_tups]

    if summary_col:
        field = itemgetter(summary_col)
    else:
        field = None
    #  print "starting col", starting_col, len(groupby_cols)
    if starting_col < len(groupby_cols):
        # there will be children of this child
        column_numbers = groupby_cols[starting_col]
        for k, group in group_sort(lst_of_tuples, column_numbers):
            # there may be children of this child
            if field:
                tot = sum(field(row) for row in group)
            else:
                tot = 0
            if column_numbers in group_hash:
                if type(group_hash[column_numbers]) == tuple:
                    tmp_lst = []
                    for i in group_hash[column_numbers]:
                        if type(group[0][i]) == int:
                            tmp_lst.append(str(group[0][i]))
                        else:
                            tmp_lst.append(unicode(group[0][i]))
                    h = ' '.join(tmp_lst)
                else:
                    h = unicode(group[0][group_hash[column_numbers]])
            else:
                if type(column_numbers) == tuple:
                    tmp_lst = []
                    for i in k:
                        if type(i) == int:
                            tmp_lst.append(str(i))
                        else:
                            tmp_lst.append(unicode(i))
                    h = ' '.join(tmp_lst)
                else:
                    if type(k) == int:
                        h = "%s" % k
                    else:
                        h = "%s" % unicode(k)
            if h:
                h = h.strip()
                if len(group) > 1:
                    lgroup = " (%d)" % len(group)
                else:
                    lgroup = ""
                if tot:
                    if display_totals_fmt == 1:
                        # hours and tenths
                        time = "%sh" % (((tot//6 + (tot%6 > 0))*6)/60.0)
                    elif display_totals_fmt == 2:
                        # hours and minutes
                        time = "%d:%02d" %  (tot//60, tot%60)
                    else:
                        time = "%dm" %  (tot)

                    if totalsfirst:
                        hdr = "%s) %s%s" % (time, h, lgroup)
                    else:
                        hdr = "%s%s %s" % (h, lgroup, time)
                else:
                    hdr = "%s%s" % (h, lgroup)
                ret_lst.append([hdr, ' ', summary_col, groupby_cols,
                    starting_col+1, group])
            else: # empty 'h' - this should be treated as a leaf
                if not show_leaves:
                    return([])
                for y in group:
                    if len(y) >=16:
                        if prefix >= 0:
                            ret_lst.append(["%s %s" % (y[prefix], y[17]),
                                (y[19], y[2], y[4]),
                                summary_col, groupby_cols, starting_col,
                                (), y[3], y])
                        else:
                            ret_lst.append(["%s" % y[17], y[19],
                                summary_col, groupby_cols, starting_col,
                                (), y[3], y])
                    else: # busy?
                        ret_lst.append([y[1],'', summary_col, groupby_cols,
                            starting_col, (), 0, y])
    else:
        # this is a leaf
        if not show_leaves:
            return(ret_lst)
        reminders = []
        if len_tups > 26:
            key=lambda cols: [cols[26:]]
            group = sorted(lst_of_tuples, key=key)
        else:
            group = sorted(lst_of_tuples)
        for y in group:
            y = y[:len_tups]
            if y[3] == sortOrder['reminder']:
                if y[18] in reminders:
                    # only display a given reminder once per group
                    continue
                else:
                    reminders.append(y[18])
            if len(y) >=16:
                if prefix >= 0:
                    ret_lst.append(["%s %s" % (y[prefix], y[17]), (y[19], y[2],
                        y[4]), summary_col, groupby_cols, starting_col, (),
                        y[3], y])
                else:
                    ret_lst.append(["%s" % y[17], (y[19], y[2], y[4]),
                        summary_col, groupby_cols, starting_col, (), y[3], y])
            else: # busy?
                ret_lst.append([y[1], ''])
    return(ret_lst)

def has_children(child, show_leaves=True):
    """ Each child is a tuple
            0: header str
            1: detail str
            2: summary_col
            3: groupby_cols (a list of tuples)
            4: starting col
            5: list of data tuples
        Return True if list_of_tuples is not empty and otherwise return
        False.
    """
    if child and len(child) > 5 and child[5]:
        if show_leaves:
            num_left = len(child[3]) - child[4] + 1
        else:
            num_left = len(child[3]) - child[4]
        return(num_left)
    return(0)

def m2t(num_mins):
    """
    Convert minutes after midnight to time in format determined by
    'use_ampm'.
    """
    try:
        num_mins = int(num_mins)
    except:
        return None
    h = num_mins/60
    m = num_mins%60
    if use_ampm:
        if h == 0:
            return  "%d:%02da" % (12, m)
        elif h < 12:
            return  "%d:%02da" % (h, m)
        elif h == 12:
            return  "%d:%02dp" % (h, m)
        else:
            return  "%d:%02dp" % (h-12, m)
    else:
        return "%d:%02d" % (h, m)

def SlotList(starthour, endhour, slotsize):
    l = []
    for x in range(starthour*60, endhour*60, slotsize):
        if x%60 == 0:
            l.append('.')
        else:
            l.append(' ')
    l.append('.')
    return l

def HourBar(starthour, endhour, slotsize):
    s = " "*12
    hour = starthour
    for x in range(starthour, endhour+1):
        if use_ampm and x > 12:
            x -= 12
        h = "%d" % x
        s += ("%-*s" % (60/slotsize, h))
    return "%s" % (s)

def l2s(lst):
    """
    Convert a list of time intervals to a string.
    """
    t = []
    for i in lst:
        t.append("%s-%s" % (m2t(i[0]),m2t(i[1])))
    return ", ".join(t)


def MarkInterval(slotlist, startminute, endminute, earliest_minute, latest_minute, char, slotsize):
    starthour = earliest_minute/60
    endhour = latest_minute/60
    if latest_minute%60 > 0:
        endhour += 1
    startminute = max(int(startminute), earliest_minute)
    endminute = min(int(endminute), latest_minute)
    # starting slot position of interval
    s = (startminute - 60*starthour)/slotsize
    # ending slot position of interval
    m = (endminute - 60*starthour)
    e = m/slotsize
    if m%slotsize > 0:
        e += 1
    for i in range(s,e+1):
        slotlist[i] = char
    return slotlist

def MarkList(list, earliest_minute, latest_minute, char, slotsize, c_list=[]):
    starthour = earliest_minute/60
    endhour = latest_minute/60
    if latest_minute%60 > 0:
        endhour += 1
    slotlist = SlotList(starthour, endhour, slotsize)
    for (b,e) in list:
        slotlist = MarkInterval(slotlist, b, e,
            earliest_minute, latest_minute, char, slotsize)
    if c_list:
        for (b,e) in c_list:
            slotlist = MarkInterval(slotlist, b, e,
                earliest_minute, latest_minute, conflictchar, slotsize)
    return slotlist

def processBusy(earliest_minute, latest_minute, minimum, wrap, busy):
    """
    Return both busy and free lists, the latter reflecting the values of
    earliest, latest and minimum.
    """
    f_lst = []
    f_tmp = []
    b_lst = []
    b_tmp = []
    c_lst = []
    notfree = []
    ff = earliest_minute  # the first potentially free minute
    if len(busy) > 0:
        bt = []
        # collect the begining and ending times in a sorted list of tuples
        for x in busy:
            bisect.insort(bt, (x[2], x[3]))
        f_tmp, l_tmp = bt[0]
        for (f, l) in bt[1:]:
            if f > l_tmp:
                notfree.append([f_tmp, l_tmp])
                f_tmp = f
            else:
                if f != l_tmp and [f, l_tmp] not in c_lst:
                    c_lst.append([f, l_tmp])
            l_tmp = l
        notfree.append([f_tmp, l_tmp])
        for (f, l) in notfree:
            fb = f  # first busy minute in interval
            lb = l  # last busy minute in interval
            b_lst.append([fb,lb])
            lf = min(fb - wrap, latest_minute) # last possible free minute
            if ff + minimum <= lf:
                f_lst.append([ff, lf])
            ff = lb + wrap
        if ff + minimum <= latest_minute:
            f_lst.append([ff,latest_minute])
        return b_lst, f_lst, c_lst
    else:
        return [], [[earliest_minute, lastest_minute]], []

def getChildren(child, level=-1, dt=[], prefix=-1, totalsfirst=False,
    details='', id2hash=id2hash):
    children = expand_child(child, prefix, totalsfirst)
    if children:
        level += 1
        attr = (level % 3) + 11
        for child in children:
            if has_children(child):
                dt.append(("%s%s" % (level*'  ', child[0]), '', attr, None))
            getChildren(child, level, dt, prefix, totalsfirst, details, id2hash)
        if level <= 1:
            dt.append(("", '', 11, None))
    elif details and len(child[-1]) > 3:
        try:
            attr = child[-1][3]
        except:
            return(dt)
        dt.append(("%s%s" % ((level)*'  ', child[0]), '', attr,
            child[-1][19]))
        if details not in [1]:
            if type(child[1]) == tuple:
                id = child[1][0]
            else:
                id = child[1]
            det_tup = list(details)
            if u'I' in det_tup:
                idx = det_tup.index(u'I')
                det_tup[idx] = u'ID'
            tups = [(x, unicode(id2hash[id][x]))
                    for x in det_tup if x in id2hash[id]]
            det = []
            for x,v in tups:
                if v and len(v) > 2 and not no_regex.match(v):
                    det.append("@%s %s" % (x, v))
            if det:
                if prefix:
                    if prefix == 25:
                        indent_num = 3
                    elif prefix > 0:
                        indent_num = 5
                else:
                    indent_num = 1
                twdth = 78-(level+indent_num)*2
                for d in det:
                    lines = d.split('\n')
                    for l in lines:
                        if len(l) <= twdth:
                            dt.append(("%s%s" % (
                                (level+indent_num)*'  ', l), '', 14, None))
                        else:
                            wlst = text_wrap(l, width=twdth)
                            for l in wlst:
                                dt.append(("%s%s" % (
                                    (level+indent_num)*'  ', l),
                                    '', 14, None))
    return(dt)

def getLeaf(hsh):
    det = []
    dt = [hsh[u'DS']]
    tups = [(x, hsh[x]) for x in sort_keys if x in hsh]
    for x, v in tups:
        #  if v and len(v) > 2 and not no_regex.match(v):
        if v and not no_regex.match(v):
            det.append("@%s %s" % (x, v))
    if det:
        twdth = 74
        for d in det:
            lines = d.split('\n')
            for l in lines:
                if len(l) <= twdth:
                    dt.append("%s%s" % ('  ', l))
                else:
                    wlst = text_wrap(l, width=twdth)
                    for l in wlst:
                        dt.append("%s%s" % ('  ', l))
    return(dt)

def setFilters(options):
    neg_fields = {}
    regex_fields = {}
    for field in ['search', 'context', 'keyword', 'user', 'location',
        'priority', 'project', 'file']:
        if field in options and options[field]:
            if options[field][0] == '!':
                neg_fields[field] = True
                regex_fields[field] = re.compile(r'%s' %
                    options[field][1:], re.IGNORECASE)
            else:
                neg_fields[field] = False
                regex_fields[field] = re.compile(r'%s' %
                options[field],
                    re.IGNORECASE)
        else:
            neg_fields[field] = False
            regex_fields[field] = None
    regex_fields['tag'] = []
    if 'tag' in options and options['tag']:
        for tag in options['tag']:
            if tag[0] == '!':
                neg_tag = True
                if type(tag) == str:
                    regex_fields['tag'].append((neg_tag, re.compile(r'%s' %
                        tag[1:], re.IGNORECASE)))
                        #  tag[1:].decode(encoding), re.IGNORECASE)))
                else:
                    regex_fields['tag'].append((neg_tag, re.compile(r'%s' %
                        tag[1:], re.IGNORECASE)))
            else:
                neg_tag = False
                if type(tag) == str:
                    regex_fields['tag'].append((neg_tag, re.compile(r'%s' %
                        tag, re.IGNORECASE)))
                        #  tag.decode(encoding), re.IGNORECASE)))
                else:
                    regex_fields['tag'].append((neg_tag, re.compile(r'%s' %
                        tag, re.IGNORECASE)))
    return(neg_fields, regex_fields)

def filterTuple(tup, neg_fields, regex_fields, omit):
    for field in ['search', 'context', 'keyword', 'user', 'location',
           'priority', 'project', 'file']:
        if field in regex_fields and regex_fields[field]:
            s = " ".join([unicode(tup[i])
                for i in filterKeys[field]])
            r = regex_fields[field].search(s)
            s_res = (r and r.group(0).strip())
            if (neg_fields[field] and s_res):
                return(False)
            if not neg_fields[field] and not s_res:
                return(False)
    if regex_fields['tag']:
        # this will be a list, each element must match
        t_res = False
        s = tup[23]
        m = parens_regex.match(s)
        if m:
            tags = m.group(1).split(',')
        else:
            tags = s
        if tags:
            for neg_tag, tag_regex in regex_fields['tag']:
                for tag in tags:
                    r = tag_regex.search(tag)
                    t_res = (r and r.group(0).strip())
                    if t_res:
                        break
                if (neg_tag and t_res):
                    return(False)
                if not neg_tag and not t_res:
                    return(False)
    if omit:
        if omit[0] == '!':
            neg_omit = True
            omit = omit[1:]
        else:
            neg_omit = False
        nums = []
        for s in omit:
            if s in omitKeys:
                for i in omitKeys[s]:
                    nums.append(i)
        if neg_omit:
            if tup[3] not in nums: return(False)
        else:
            if tup[3] in nums: return(False)
    return(True)

def getMatchingTuples(tuples, options):
    include_busy = True
    if 'begin_date' in options and 'end_date' in options:
        # print("getMatchingTuples", options['begin_date'], options['end_date'])
        td = parse("%s-%s-%s" % tuple(options['end_date'])) - parse("%s-%s-%s" % tuple(options['begin_date']))
        if td > 7*oneday:
            # print("not a week")
            include_busy = False
    if 'search' in options and options['search']:
        i1 = 0
        i2 = len(tuples)
    else:
        if 'begin_date' in options:
            i1 = bisect.bisect_left(tuples, options['begin_date'])
        else:
            i1 = None
        if 'end_date' in options:
            i2 = bisect.bisect_right(tuples, options['end_date'])
        else:
            i2 = None
    if i1 == i2:
        tups = []
    elif i1 and i2:
        tups = tuples[i1:i2]
    elif i1:
        tups = tuples[i1:]
    elif i2:
        tups = tuples[:i2]
    else:
        tups = tuples
    if 'omit' in options:
        omit = options['omit']
    else:
        omit = ''
    neg_fields, regex_fields = setFilters(options)
    matching = []
    busyTimes = {}
    for tup in tups:
        if filterTuple(tup, neg_fields, regex_fields, omit):
            matching.append(tup)
            if include_busy:
                if tup[3] == 1: # events with start time and extent
                    d_str = "%s-%s-%s" % tuple(tup[:3])
                    date = duparse(d_str)
                    wd = int(date.strftime("%w"))
                    if not sundayfirst:
                        wd -= 1
                        if wd < 0:
                            wd = 6
                    item = ((tup[19], tup[2], tup[4]), wd, tup[4], tup[4]+tup[5])
                    busyTimes.setdefault(tuple(tup[:3]), []).append(item)
    return(matching, neg_fields, regex_fields, busyTimes)

def opts2Tuples(tuples, options):
    parse_opts(options)
    tups, neg_fields, regex_fields, busyTimes = getMatchingTuples(tuples, options)
    return(tups, options, busyTimes)

def getWeek(tuples, begin_date, options={'omit': 'n'}):
    """
        Return a list of the items for the week.
    """
    d,m,y = begin_date
    i1 = bisect.bisect_left(tuples, begin_date)
    start_dt = datetime.datetime(d,m,y,0,0,0)
    start_dt.replace(tzinfo = tzlocal())
    if 'end_date' in options and options['end_date']:
        # print("getWeek end_date", options['end_date'])
        end_date = options['end_date']
        end_dt = datetime.datetime(*options['end_date'])
        last_dt = end_dt - oneday
    else:
        end_dt = start_dt + soon * oneday
        last_dt = start_dt + (soon-1) * oneday
        end_date = (end_dt.year, end_dt.month, end_dt.day)
    h = "%s ~ %s" % (start_dt.strftime(beg_date_fmt),
            last_dt.strftime(end_date_fmt))
    if not 'cols' in options or not options['cols']:
        options['cols'] = '((y,m,d),)'
    options['begin_date'] = (start_dt.year, start_dt.month, start_dt.day)

    matching, options, busytimes = opts2Tuples(tuples, options)
    busy_events = {}
    date = start_dt
    while date < end_dt:
        k = (date.year, date.month, date.day)
        if k in busytimes:
            busy_events[date] = busytimes[k]
        date = date + oneday

    data = ['', '', 5, options['cols'], 0, matching]
    return(h, data, busy_events)

def make_tree(tuples, opts=[], id2hash=id2hash):
    if not ('search' in opts and opts['search']):
        opts['search'] = '.*'
    tups, options, busy = opts2Tuples(tuples, opts)
    id2Tups = {}
    for t in tups:
        id2Tups[t[int(fieldNum['I'])]] = t
    ids = id2Tups.keys()
    e_tups = []
    if ids:
        # avoid duplicates by processing ids instead of tuples
        for id in ids:
            lst = list(id2Tups[id])
            rel_path, beg_line, end_line = id.split(':') # id
            #  lst.append(int(beg_line))
            #  lst.append("%4s" % beg_line)
            path = split_path(rel_path)
            path.append(int(beg_line))
            lst.extend(path)
            e_tups.append(tuple(lst))

    # 26:-1 the path components, -1 the beginning line number
    data = ['', '', 5, [26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36],
            0, e_tups]
    h = 'organized by file path'
    return(h, data, options, busy)

def split_path(rel_path):
    path = []
    head, ext = os.path.splitext(rel_path)
    while head:
        head, tail = os.path.split(head)
        path.insert(0, tail)
    return(path)

def term_print(s):
    print("%s" % s.encode(term_encoding))

def data2Report(tuples, opts=[], id2hash=id2hash):
    tups, options, busytimes = opts2Tuples(tuples, opts)
    data = ['', '', 5, options['cols'], 0, tups]
    if 'totalsfirst' in options:
        tot = options['totalsfirst']
    else:
        tot = True
    if 'details' in options:
        det = options['details']
    else:
        det = 1
    dt = getChildren(data, level=-1, dt=[], prefix=16,
            totalsfirst=tot, details=det,
            id2hash=id2hash)
    while dt and not dt[-1][0]:
        dt.pop(-1)
    return(dt)

def data2DayColors(begin_date, end_date, busy):
    """
    Input a hash of lists (datetime -> list of busy intervals) and return a
    hash (y,m,d) -> (r,g,b) bars.
    """
    dayColors = {}
    start = datetime.datetime(*begin_date)
    end = datetime.datetime(*end_date)
    date = start
    keys = busy.keys()
    while date <= end:
        ym = (date.year, date.month)
        k = (date.year, date.month, date.day)
        if k in busy:
            minutes = 0
            for (id, col, b, e) in busy[k]:
                minutes += e - b
        else:
            minutes = 0
        dayColors.setdefault(ym, []).append((date.day, daycolor(minutes)))
        date = date + oneday
    return(dayColors)

def data2Busy(busy, options):
    """
    Input a hash of lists (datetime -> list of busy intervals) and return busy
    bars and free lists, the latter reflecting the values of earliest (time),
    latest (time) and minimum (minutes).
    form a list using bisect
    starting key = YR|MN|DY|WN
       YR | WN | "busy|free|confict" | MN | DY | "bar|times"
    """
    start = duparse("%s-%s-%s" % options['begin_date'])
    end = duparse("%s-%s-%s" % options['end_date'])
    earliest = duparse(options['opening'])
    earliest_minute = earliest.hour * 60 + earliest.minute
    latest = duparse(options['closing'])
    latest_minute = latest.hour * 60 + latest.minute
    starthour = earliest.hour
    endhour = latest.hour
    if latest.minute > 0:
        endhour += 1
    if 'wrap' in options:
        wrap = int(options['wrap'])
    if 'minimum' in options:
        minimum = int(options['minimum'])
    cols = (endhour - starthour)*(60/slotsize) + 15
    busyTuples = []
    tmpList = []
    twdth = cols - 15
    date = start
    keys = busy.keys()
    while date < end:
        busy_times = []
        free_times = []
        conflict_times = []
        busy_bars = []
        free_bars = []
        begW = (date - (date.weekday()) * oneday).strftime(date_fmt)
        endW = (date + (6-date.weekday()) * oneday).strftime(end_date_fmt)
        yr, mn, dy, h, m, wn, wa, ma  = date.strftime(
                    "%Y,%m,%d,%H,%M,%W,%a,%b").split(',')
        ws = "week %2s: %s - %s" % (wn, begW, endW)
        ds = "%s %s %s" % (wa, ma, dy)
        date = date + oneday

        #  busy keys have the form (y,m,d)
        d = tuple(map(int, (yr,mn,dy)))
        if d in busy:
            b = busy[d]
        else:
            b = []
        if len(b) > 0:
            try:
                b_times, f_times, c_times = processBusy(
                        earliest_minute, latest_minute, minimum, wrap, b)
                bbar_str = "".join(MarkList(b_times, earliest_minute,
                    latest_minute, busychar, slotsize, c_times))
                s = l2s(b_times).strip()
                if s:
                    btime_lines = text_wrap("%s" % s, width = twdth)
                else:
                    btime_lines = ['']
                fbar_str = "".join(MarkList(f_times, earliest_minute,
                    latest_minute, freechar, slotsize))
                s = l2s(f_times).strip()
                if s:
                    ftime_lines = text_wrap("%s" % s, width = twdth)
                else:
                    ftime_lines = ['']
                s = l2s(c_times).strip()
                if s:
                    ctime_lines = text_wrap("%s" % s, width = twdth)
                else:
                    ctime_lines = []
                busy_bars = bbar_str
                if btime_lines:
                    lines = []
                    lines.append("%s" % (btime_lines.pop(0).strip()))
                    for line in btime_lines:
                        lines.append("%s%s" % (" "*14,
                            line.strip()))
                    busy_times = "\n".join(lines)
                free_bars = fbar_str
                if ftime_lines:
                    lines = []
                    lines.append("%s" % (ftime_lines.pop(0).strip()))
                    for line in ftime_lines:
                        lines.append("%s%s" % (" "*14,
                            line.strip()))
                    free_times = "\n".join(lines)
                if ctime_lines:
                    lines = []
                    lines.append(ctime_lines.pop(0).strip())
                    for line in ctime_lines:
                        lines.append("%s%s" % (" "*14,
                            line.strip()))
                    conflict_times = "\n".join(lines)
            except:
                print "except:", d, earliest, latest, minimum, b
                print sys.exc_info()
        else:
            busy_times = ""
            busy_bars = "".join(SlotList(starthour, endhour, slotsize))
            free_times = l2s([[earliest_minute, latest_minute]])
            free_bars = "".join(MarkList([[earliest_minute, latest_minute]],
                earliest_minute, latest_minute, freechar, slotsize))
        bisect.insort(tmpList, tuple((yr,ws,'bb',mn,dy,ds,busy_bars)))
        bisect.insort(tmpList, tuple((yr,ws,'bt',mn,dy,ds,busy_times)))
        bisect.insort(tmpList, tuple((yr,ws,'fb',mn,dy,ds,free_bars)))
        bisect.insort(tmpList, tuple((yr,ws,'ft',mn,dy,ds,free_times)))
        if conflict_times:
            bisect.insort(tmpList, tuple((yr,ws,'c',mn,dy,ds, conflict_times)))

    dt = []
    for k, g in group_sort(tmpList, (0,1)):
        dt.append((k[1], '', 'blue'))
        for l, h in group_sort(g, 2):
            if l == 'bb' and 'B' in options['include']:
                dt.append(('  Busy', 'em', 'green'))
                dt.append(("    %s" % HourBar(starthour, endhour, slotsize),))
                for i in h:
                    dt.append(("    %s: %s" % (i[5], i[6]),))
                dt.append(("",))
            elif l == 'bt' and 'b' in options['include']:
                dt.append(('  Busy Times', 'em', 'green'))
                for i in h:
                    dt.append(("    %s: %s" % (i[5], i[6]),))
                dt.append(("",))
            elif l == 'fb' and 'F' in options['include']:
                dt.append(('  Free', 'em', 'green'))
                dt.append(("    %s" % HourBar(starthour, endhour, slotsize),))
                for i in h:
                    dt.append(("    %s: %s" % (i[5], i[6]),))
                dt.append(("",))
            elif l == 'ft' and 'f' in options['include']:
                dt.append(('  Free Times', 'em', 'green'))
                for i in h:
                    dt.append(("    %s: %s" % (i[5], i[6]),))
                dt.append(("",))
            elif l == 'c' and 'c' in options['include']:
                dt.append(( '  Conflicts', 'em', 'red' ))
                for i in h:
                    dt.append(("    %s: %s" % (i[5], i[6]),))
                dt.append(("",))
    while dt and not dt[-1]:
        dt.pop(-1)
    return(dt)

def htmlWrap(s, f='', c=''):
    if c:
        s= '<font color="%s">%s</font>' % (c, s)
    if f:
        s = "<%s>%s</%s>" % (f, s, f)
    return(s)

def curWrap(s, f='', a=''):
    if c:
        s= '%s %s %s' % (attrs[a], s, all_off)
    return(s)

def make_csv(fname, tuples, options):
    if options:
        items, options = opts2Tuples(tuples, options)
    else:
        items = tuples
    include = re.split('\s*,\s*', options['values'])
    keys = [19, 3, 17] + [int(fieldNum[x]) for x in include]
    lines = []
    hdrlst = ['"%s"' % tupleKeys[x] for x in keys]
    lines.append(",".join(hdrlst))
    for item in items:
        line = []
        for key in keys:
            line.append('"%s"' % item[key])
        lines.append(",".join(line))
    out = "\n".join(lines)
    if fname:
        (name, ext) = os.path.splitext(fname)
        pname = os.path.join(export, "%s.csv" % name)
        fo = codecs.open(pname, 'wb', file_encoding)
        fo.write(out)
        fo.close()
        return('exported to %s' % fname)
    else:
        return(out)

def make_ical():
    cal = vobject.iCalendar()
    cal.add('prodid').value = '-//etm %s//dgraham.us//' % version
    cal.add('version').value = '2.0'
    for id, hsh in id2hash.items():
        now = datetime.datetime.now()
        now = now.replace(tzinfo=tzlocal()).astimezone(tzutc())
        if '_z' in hsh:
            timezone = hsh['_z']
        else:
            timezone = None

        itemType = hsh[u'leader'][0]
        if itemType in ['*']:
            element = cal.add('vevent')
        elif itemType in ['-', '+', '~']:
            # since actions do not have a starting time, we treat them as todos
            element = cal.add('vtodo')
        elif itemType in ['!']:
            element = cal.add('vjournal')
        element.add('uid').value = uuid4().hex
        element.add('dtstamp').value = now
        element.add('last_modified').value = now
        element.add('summary').value = hsh['DS']
        if 'l' in hsh:
            element.add('location').value = hsh['l']
        if 'n' in hsh:
            element.add('description').value = hsh['n']
        if 'p' in hsh:
            try:
                p = int(hsh['p'])
                assert(p >= 1 and p <= 9)
                element.add('priority').value = p
            except:
                pass
        if 't' in hsh:
            element.add('categories').value = hsh['t']

def make_vcal(fname, tuples, options):
    """
        Only filter tuples if options is non-null. Return calendar as string
        if fname is ''.
    """
    if not has_vobject:
        return('')
    ret_val = False
    if options:
        items, options = opts2Tuples(tuples, options)
    else:
        items = tuples
    cal = vobject.iCalendar()
    cal.add('prodid').value = '-//etm %s//dgraham.us//' % version
    cal.add('version').value = '2.0'
    for item in items:
        item = list(item)
        tmp = []
        for i in range(len(item)):
            if type(item[i]) == str:
                try:
                    tmp.append(unicode(item[i]))
                except:
                    print "except", item[i], type(item[i]), sys.exc_info()
        if item[3] == sortOrder['begin']:
            continue
        if item[0]:
            dtl = datetime.datetime(item[0],item[1],item[2], 0, 0,
                    tzinfo=tzlocal())
            dtu = dtl.astimezone(tzutc())
            dd = dtu.date()
        else:
            dtl = dtu = dd = ''
        if item[3] in [sortOrder['allday'],
                sortOrder['event'],
                sortOrder['reminder']]:
            dt = dtl
            element = cal.add('vevent')
        elif item[3] in [sortOrder['pastdue'],
                sortOrder['waiting'],
                sortOrder['waiting'],
                sortOrder['task'],
                sortOrder['undated'],
                sortOrder['finished']]:
            dt = dd
            element = cal.add('vtodo')
        elif item[3] in [sortOrder['action'], sortOrder['note']]:
            dt = dtu
            element = cal.add('vjournal')
        element.add('uid').value = uuid4().hex
        if item[6] and not no_regex.match(item[6]):
            element.add('priority').value = item[6][-1]
        if item[17]:
            element.add('summary').value = item[17]
        if item[13] and not no_regex.match(item[13]):
            element.add('location').value = item[13]
        if item[23] and not no_regex.match(item[23]):
            element.add('categories').value = item[23]
        if item[24]:
            #  element.add('description;CHARSET=UTF-8', item[24])
            element.add('description').value = item[24]
        if dt:
            #  if item[3] in [4,5,6,8,10]: # dated task or note
            if item[3] in [sortOrder['pastdue'],
                    sortOrder['task'],
                    sortOrder['waiting'],
                    sortOrder['begin'],
                    ]: # dated task
                element.add('due').value = dd
                allday =False
            elif item[3] in [sortOrder['finished']]: # completed task
                element.add('completed').value = dtu
                allday =False
            if item[3] in [sortOrder['undated']]: # undated task
                allday =False
            elif item[3] in [sortOrder['note']]: # note
                element.add('dtstart').value = dtu
            elif item[3] in [sortOrder['allday']]: # allday
                allday = True
                element.add('dtstart').value = dd
            elif item[3] in [sortOrder['action']]: # action
                element.add('comment').value = "%s minutes" % item[5]
                allday =False
            elif item[3] in [sortOrder['event'], sortOrder['reminder']]:
                allday = False
                minute = int(item[4])
                h = min(23, minute//60)
                m = minute%60
                try:
                    dtl = dt.replace(hour=h, minute=m, second=0)
                    dtu = dtl.astimezone(tzutc())
                except:
                    print "Exception", minute, h, m, item
                element.add('dtstart').value = dtu
                if item[5] and item[5] > 0:
                    p_min = int(item[5])
                    minute += p_min
                    h = min(23, minute//60)
                    m = minute%60
                    s = 0
                    if h >= 24:
                        h = 23
                        m = 59
                        s = 59

                    dtl = dt.replace(hour=h, minute=m, second=s)
                    dtu = dtl.astimezone(tzutc())
                    element.add('dtend').value = dtu
        ret_val = True
    if fname:
        (name, ext) = os.path.splitext(fname)
        pname = os.path.join(export, "%s.ics" % name)
        try:
            cal_str = cal.serialize()
        except:
            cal.prettyPrint()
            print sys.exc_info()
            sys.exit()
        fo = open(pname, 'wb')
        try:
            fo.write(cal_str)
        except:
            print "EXCEPTION", sys.exc_info()
        fo.close()
        return(ret_val, 'exported as vCal to %s' % fname)
    else:
        return(ret_val, cal.serialize())

def main():
    global id2hash, use_colors
    p = 'o'
    args = []
    if len(sys.argv) > 1:
        args = sys.argv[1:]
        if args[0] == '-h':
            print "Use 'o -h' for outline help and 'b -h' for busy help"
            return()
        p = args[0]
        if p not in ['o', 'b', 'O', 'B']:
            print "error"
            return()
    if use_colors and p in ['O', 'B']:
        use_colors = False
    if use_colors:
        all_off, attrs, codes = get_attrs()
        if not all_off:
            use_colors = False
    parser = nameHash[p.lower()]
    year = int(datetime.date.today().strftime("%Y"))
    beg_year = year - year_beg
    end_year = year + year_end
    data_beg = (beg_year, 1, 1)
    data_end = (end_year, 12, 31)

    common_prefix, all, alerts, id2hash, lastmodified,\
            currenthash, contexts, keywords, locations, msgs = \
            getTuples(data_beg, data_end)
    if msgs:
        for m in msgs:
            print m
    options = get_opts(parser, args)
    #  print "main", parser, options
    if p.lower() == 'b':
        parse_opts(options)
        matching, options, busytimes = opts2Tuples(all, options)
        lst = data2Busy(busytimes, options)
        if use_colors:
            for l in lst:
                if len(l) >= 3:
                    a = codes[l[2]]
                else:
                    a = ''
                print a, l[0], all_off
        else:
            for l in lst:
                print l[0]
    else:
        if 'cols' in options and 'F' in options['cols']:
            h, data, options = make_tree(all, options, id2hash)
            dt = getChildren(data, level=-1, dt=[], prefix=25,
                    totalsfirst=options['totalsfirst'],
                    details=options['details'],
                    id2hash=id2hash)
            while dt and not dt[-1][0]:
                dt.pop(-1)
            if use_colors:
                for s, f, a, i in dt:
                    print "%s%s%s" % (attrs[a], s, all_off)
            else:
                for s, f, a, i in dt:
                    print "%s" % (s)
        else:
            dt = data2Report(all, options, id2hash)
            if use_colors:
                for s, f, a, i in dt:
                    print "%s%s%s" % (attrs[a], s, all_off)
            else:
                for s, f, a, i in dt:
                    print "%s" % (s)
            if 'vcal' in options and options['vcal']:
                ret, s = make_vcal('export.ics', all, options)
                print("\n%s" % s)
            if 'values' in options and options['values']:
                s = make_csv('export.csv', all, options)
                print("\n%s" % s)

if __name__ == "__main__":
    main()

