<file_sep>#!/usr/bin/env python

import subprocess
import sys

# Command line parameters
dummy, mexp, calc_jump, characteristic_file, target_file = sys.argv

# Each generator can generate at lest SEP random numbers without overlaps
SEP = 10L**60

# Generate polynomials for both 1*SEP and FACTOR*SEP jumps
FACTOR = 100

def gen_jump(step):
    result = subprocess.check_output([calc_jump, str(step), characteristic_file])
    head, poly, empty = result.split("\n")
    assert head == 'jump polynomial:'
    assert empty == ''
    return poly

jump_one = gen_jump(SEP)
jump_many = gen_jump(FACTOR * SEP)

with open(target_file, 'w') as f:
    f.write('MEXP = %s\n' % mexp)
    f.write('JUMP_FACTOR = %d\n' % FACTOR)
    f.write('JUMP_ONE = %s\n' % repr(jump_one))
    f.write('JUMP_MANY = %s\n' % repr(jump_many))
<file_sep>#!/usr/bin/env python

import struct
import sys

DIR = "src"

#--- Utility functions ---

def dd(*l):
    result = dict()
    for x in l:
        result.update(x.d)
    return result

def indent(w, i):
    prefix = "    " * i;
    def w2(msg):
        w("".join([prefix + line for line in msg.splitlines(True)]))
    return w2

def gen_list(w, l, pat1, pat2):
    for a in l:
        w(pat1 % a.d)
        w("\n")
    w(pat2 % { "count": len(l) })
    w("\n\n")

def any_array(width, l):
    r = []
    tail = l
    while len(tail) > 0:
        head, tail = tail[:width], tail[width:]
        r.append(", ".join(head))
    return ",\n    ".join(r)

def char_array(s):
    return any_array(12, ["'%s'" % i for i in s] + ["0"])

def uint32_array(l):
    return any_array(6, ["0x%08x" % i for i in l])

#--------

def setup_all():
    for c in ("none", "curves", "permtest"):
        setup_class(Class(c))
    
    Y_TYPE = Y("type", True)
    Y_HAPAX = Y("hapax", False)
    Y_TOKEN = Y("token", True)

    X_WORD = X("word", ["WITH_WORD_COUNT"])
    X_TOKEN = X("token", [])

    for x in (X_WORD, X_TOKEN):
        setup_x(x)
    for y in (Y_TYPE, Y_HAPAX, Y_TOKEN):
        setup_y(y)
    for y in (Y_TYPE, Y_HAPAX):
        for x in (X_WORD, X_TOKEN):
            setup_yx(y, x)
    setup_yx(Y_TOKEN, X_WORD)

    YY_TYPE = YY((Y_TYPE,), "type", "vector", ["WITH_MATRIX_BINARY"])
    YY_HAPAX = YY((Y_HAPAX,), "hapax", "zom", ["WITH_MATRIX_ZOM"])
    YY_TYPE_HAPAX = YY((Y_TYPE, Y_HAPAX), "typehapax", "zom", ["WITH_MATRIX_ZOM"])
    YY_TOKEN = YY((Y_TOKEN,), "token", None, [])

    XX_TOKEN = XX((X_TOKEN,), "t", False)
    XX_WORD = XX((X_WORD,), "w", False)
    XX_WORD_TOKEN = XX((X_WORD, X_TOKEN), "wt", True)

    V_DENSE = V("dense")
    V_SPARSE = V("sparse")
    V_NORMAL = V(None)

    for yy in (YY_TYPE, YY_HAPAX, YY_TYPE_HAPAX):
        for xx in (XX_TOKEN, XX_WORD, XX_WORD_TOKEN):
            setup_variants(yy, xx, [V_DENSE, V_SPARSE])
    setup_variants(YY_TOKEN, XX_WORD, [V_NORMAL])

def record(w, y, x):
    # Store new per-slot bounds based on per-gap bounds.
    # Example:
    # - threshold is 0, 10, 20, etc.
    # - "xslot" is 2
    # Then:
    # - "b_prev_gap" is the bounds for the gap 10..20
    # - "b_this_gap is the bounds for the gap 20..30
    # - we update the bounds for the slot 20.
    w('''\
    {
''')
    if y.nondecreasing:
        w('''\
        assert(b_prev_gap_%(y)s_%(x)s.lower <= b_this_gap_%(y)s_%(x)s.lower);
        assert(b_prev_gap_%(y)s_%(x)s.upper <= b_this_gap_%(y)s_%(x)s.upper);
        const unsigned lower = b_prev_gap_%(y)s_%(x)s.lower;
        const unsigned upper = b_this_gap_%(y)s_%(x)s.upper;
''' % dd(y, x))
    else:
        w('''\
        const unsigned lower = MIN(b_prev_gap_%(y)s_%(x)s.lower, b_this_gap_%(y)s_%(x)s.lower);
        const unsigned upper = MAX(b_prev_gap_%(y)s_%(x)s.upper, b_this_gap_%(y)s_%(x)s.upper);
''' % dd(y, x))
    w('''\
        const unsigned yslot_lower = get_yslot(pgrid, Y%(Y)s, lower);
        const unsigned yslot_upper = get_yslot_up(pgrid, Y%(Y)s, upper);
        const unsigned index_lower = slot(pgrid, Y%(Y)s, X%(X)s, yslot_lower, xslot_%(x)s);
        const unsigned index_upper = slot(pgrid, Y%(Y)s, X%(X)s, yslot_upper, xslot_%(x)s);
        pyxstat->yx[YX_%(Y)s_%(X)s][index_lower].lower++;
        pyxstat->yx[YX_%(Y)s_%(X)s][index_upper].upper++;
    }
''' % dd(y, x))

def gen_summarise_collection_var(f, var):
    w = f.cw
    xx = var.alg.xx
    yy = var.alg.yy
    
    w('''\
static void
summarise_collection_%(yy)s_%(xx)s%(maybev)s(
    const input_t * restrict pinput,
    collection_t * restrict pcoll,
    const unsigned c)
{
''' % var.d)

    if yy.temp is not None:
        w('''\
    %(temp)s_t temp[pinput->types.nvector];
    %(temp)s_clear(temp, pinput->types.nvector);
''' % var.d)

    for x in xx.x:
        w('''\
    unsigned xaccum_%(x)s = 0;
''' % x.d)

    for y in yy.y:
        w('''\
    unsigned yaccum_%(y)s = 0;
''' % y.d)

    w('''\
    for (unsigned id = 0; id < pinput->types.nrow; id++) {
        if (matrix_element_b(&pinput->collections, id, c)) {
            calculate_bounds_%(yy)s%(maybev)s(
                pinput, id%(maybetemp)s, %(yaccumlist)s
            );
''' % var.d)
    for x in xx.x:
        w('''\
            xaccum_%(x)s += %(getsamples)s;
''' % { "x": x.key, "getsamples": xx.get_samples(x)})
    w('''\
        }
    }
''')

    for x in xx.x:
        w('''\
    pcoll[c].x.x[X%(X)s] = xaccum_%(x)s;
''' % x.d)

    for y in yy.y:
        w('''\
    pcoll[c].y.y[Y%(Y)s] = yaccum_%(y)s;
''' % y.d)

    w('''\
}

''')

def gen_calculate_permtest_one(f, var):
    w = f.cw
    xx = var.alg.xx
    yy = var.alg.yy
    
    w('''\
static void
calculate_permtest_%(yy)s_%(xx)s%(maybev)s_one(
    const input_t * restrict pinput,
    const collection_t * restrict pcoll,
    const yxstat_t * restrict pyxstat,
    const unsigned * restrict sample_order)
{
''' % var.d)

    w('''\
    for (unsigned c = 0; c < pinput->collections.ncol; c++) {
''')
    for x in xx.x:
        w('''\
        if (pcoll[c].x.x[X%(X)s] == 0) {
''' % x.d)
        for y in yy.y:
            w('''\
            pyxstat->yx[YX_%(Y)s_%(X)s][c].lower++;
            pyxstat->yx[YX_%(Y)s_%(X)s][c].upper++;
''' % dd(y, x))
        w('''\
        }
''')
    w('''\
    }
''')

    if yy.temp is not None:
        w('''\
    %(temp)s_t temp[pinput->types.nvector];
    %(temp)s_clear(temp, pinput->types.nvector);
''' % var.d)

    for x in xx.x:
        w('''\
    unsigned xaccum_%(x)s = 0;
''' % x.d)

    for y in yy.y:
        w('''\
    unsigned yaccum_%(y)s = 0;
''' % y.d)

    w('''\
    for (unsigned i = 0; i < pinput->types.nrow; i++) {
        const unsigned id = sample_order[i];
        const %(yy)s_bounds_t b_sample = calculate_bounds_%(yy)s%(maybev)s(
            pinput, id%(maybetemp)s, %(yaccumlist)s
        );
''' % var.d)

    for x in xx.x:
        w('''\
        const unsigned xprev_%(x)s = xaccum_%(x)s;
        xaccum_%(x)s += %(getsamples)s;
''' % { "x": x.key, "getsamples": xx.get_samples(x)})

    w('''\
        for (unsigned c = 0; c < pinput->collections.ncol; c++) {
''')
    for x in xx.x:
        w('''\
            if (xprev_%(x)s < pcoll[c].x.x[X%(X)s] && pcoll[c].x.x[X%(X)s] <= xaccum_%(x)s) {
''' % x.d)
        for y in yy.y:
            w('''\
                if (b_sample.y%(y)s.lower <= pcoll[c].y.y[Y%(Y)s]) {
                    pyxstat->yx[YX_%(Y)s_%(X)s][c].lower++;
                }
                if (b_sample.y%(y)s.upper >= pcoll[c].y.y[Y%(Y)s]) {
                    pyxstat->yx[YX_%(Y)s_%(X)s][c].upper++;
                }
''' % dd(y, x))
        w('''\
            }
''')
    w('''\
        }
    }
}

''')

def gen_calculate_curves_one(f, var):
    w = f.cw
    xx = var.alg.xx
    yy = var.alg.yy
    
    w('''\
static void
calculate_curves_%(yy)s_%(xx)s%(maybev)s_one(
    const input_t * restrict pinput,
    const grid_t * restrict pgrid,
    const yxstat_t * restrict pyxstat,
    const unsigned * restrict sample_order)
{
''' % var.d)

    if yy.temp is not None:
        w('''\
    %(temp)s_t temp[pinput->types.nvector];
    %(temp)s_clear(temp, pinput->types.nvector);
''' % var.d)

    for x in xx.x:
        w('''\
    unsigned xaccum_%(x)s = 0;
    unsigned xslot_%(x)s = 0;
''' % x.d)

    for y in yy.y:
        w('''\
    unsigned yaccum_%(y)s = 0;
''' % y.d)

    for x in xx.x:
        for y in yy.y:
            w('''\
    bounds_t b_prev_gap_%(y)s_%(x)s = BOUNDS_NULL;
    bounds_t b_this_gap_%(y)s_%(x)s = BOUNDS_NULL;
''' % dd(y, x))

    w('''\
    for (unsigned i = 0; i < pinput->types.nrow; i++) {
        const unsigned id = sample_order[i];
        const %(yy)s_bounds_t b_sample = calculate_bounds_%(yy)s%(maybev)s(
            pinput, id%(maybetemp)s, %(yaccumlist)s
        );
''' % var.d)

    for x in xx.x:
        w('''\

        xaccum_%(x)s += %(getsamples)s;
''' % { "x": x.key, "getsamples": xx.get_samples(x)})
        for y in yy.y:
            if y.nondecreasing:
                w('''\
        assert(b_this_gap_%(y)s_%(x)s.lower <= b_sample.y%(y)s.lower);
        assert(b_sample.y%(y)s.lower <= b_this_gap_%(y)s_%(x)s.upper);
        assert(b_this_gap_%(y)s_%(x)s.upper <= b_sample.y%(y)s.upper);
        b_this_gap_%(y)s_%(x)s.upper = b_sample.y%(y)s.upper;
''' % dd(y, x))
            else:
                w('''\
        b_this_gap_%(y)s_%(x)s.lower = MIN(b_sample.y%(y)s.lower, b_this_gap_%(y)s_%(x)s.lower);
        b_this_gap_%(y)s_%(x)s.upper = MAX(b_sample.y%(y)s.upper, b_this_gap_%(y)s_%(x)s.upper);
''' % dd(y, x))

        w('''\
        while (xaccum_%(x)s >= get_xthreshold(pgrid, X%(X)s, xslot_%(x)s+1)) {
''' % x.d)
        for y in yy.y:
            record(indent(w, 2), y, x)
            w('''\
            b_prev_gap_%(y)s_%(x)s = b_this_gap_%(y)s_%(x)s;
            b_this_gap_%(y)s_%(x)s = b_sample.y%(y)s;
''' % dd(y, x))
        w('''\
            xslot_%(x)s++;
        }
        if (xaccum_%(x)s == get_xthreshold(pgrid, X%(X)s, xslot_%(x)s)) {
''' % x.d)
        for y in yy.y:
            w('''\
            b_this_gap_%(y)s_%(x)s.lower = yaccum_%(y)s;
            b_this_gap_%(y)s_%(x)s.upper = yaccum_%(y)s;
''' % dd(y, x))
        w('''\
        }
''')

    w('''\
    }
''')

    for x in xx.x:
        w('''\
    assert(xslot_%(x)s == pgrid->xslots.x[X%(X)s] - 1);
''' % x.d)
        for y in yy.y:
            record(w, y, x)


    w('''\
}

''')

def gen_calculate_x_var(f, var, what, type1, var1):
    f.cw('''\
static void
calculate_%(what)s_%(yy)s_%(xx)s%(maybev)s(
    const input_t * restrict pinput,
    const rng_state_t * restrict rng_state_init,
    %(type1)s %(var1)s,
    const yxstat_t * restrict pyxstat,
    unsigned part)
{
    unsigned sample_order[pinput->types.nrow];
    unsigned from = get_iteration(pinput->iterations, part);
    unsigned to = get_iteration(pinput->iterations, part + 1);
    rng_state_t rng_state = rng_state_init[part];
    for (unsigned iteration = from; iteration < to; iteration++) {
        rand_permutation(&rng_state, pinput->types.nrow, sample_order);
        calculate_%(what)s_%(yy)s_%(xx)s%(maybev)s_one(pinput, %(var1)s, pyxstat, sample_order);
    }
}

''' % dict(var.d, what=what, type1=type1, var1=var1))

def gen_calculate_permtest_var(f, var):
    gen_calculate_x_var(f, var, "permtest", "const collection_t * restrict", "pcoll")

def gen_calculate_curves_var(f, var):
    gen_calculate_x_var(f, var, "curves", "const grid_t * restrict", "pgrid")

def gen_array(f):
    for v in ("sparse", "dense"):
        f.cw('''\
const algv_t ALG_%(V)s[NALG] = {
''' % { "V": v.upper() }  )
        for alg in ALGORITHMS:
            maybev1 = ("_" + v if alg.has_variants else "")
            maybev2 = (v if alg.has_variants else "")
            f.cw('''\
    {
        summarise_collection_%(yy)s_%(xx)s%(maybev1)s,
        calculate_permtest_%(yy)s_%(xx)s%(maybev1)s,
        calculate_curves_%(yy)s_%(xx)s%(maybev1)s,
        "%(yy)s-%(xx)s", "%(maybev2)s"
    },
''' % dict(alg.d.items(), maybev1=maybev1, maybev2=maybev2))
        f.cw('''\
};

''')

    f.cw('''\
const alg_t ALG[NALG] = {
''')
    for alg in ALGORITHMS:
        f.cw('''\
    {
        %(featurelist)s,
        { { %(outputlist)s } }
    },
''' % alg.d)
    f.cw('''\
};

''')

def gen_jump_h(f):
    import JumpTable
    d = {
        "JUMP_FACTOR": JumpTable.JUMP_FACTOR,
        "MEXP": JumpTable.MEXP,
    }
    
    f.hw('''\
#define JUMP_FACTOR %(JUMP_FACTOR)d

extern const char JUMP_ONE[];
extern const char JUMP_MANY[];

''' % d)

def gen_jump_c(f):
    import JumpTable
    d = {
        "MEXP": JumpTable.MEXP,
        "JUMP_ONE": char_array(JumpTable.JUMP_ONE),
        "JUMP_MANY": char_array(JumpTable.JUMP_MANY),
    }
    
    f.cw('''\

#if !defined(SFMT_MEXP)
#error "SFMT_MEXP is not defined"
#endif

#if SFMT_MEXP != %(MEXP)d
#error "this file assumes SFMT_MEXT = %(MEXP)d"
#endif

const char JUMP_ONE[] = {
    %(JUMP_ONE)s
};
const char JUMP_MANY[] = {
    %(JUMP_MANY)s
};
''' % d)

def get_seed():
    FORMAT = '<L'
    LEN = struct.calcsize(FORMAT)
    assert LEN == 4
    seed = []
    with open('etc/seed') as f:
        while True:
            s = f.read(LEN)
            if s == '':
                break
            seed.append(struct.unpack(FORMAT, s))
    return {
        "SEED_LENGTH": len(seed),
        "SEED": uint32_array(seed),
    }

def gen_seed_h(f):
    d = get_seed()

    f.hw('''\
#include <stdint.h>

#define SEED_LENGTH %(SEED_LENGTH)d

extern const uint32_t SEED[SEED_LENGTH];

''' % d)

def gen_seed_c(f):
    d = get_seed()

    f.cw('''\

const uint32_t SEED[SEED_LENGTH] = {
    %(SEED)s
};
''' % d)

def gen_yx_h(f):
    f.hw('''\
#include <stdbool.h>
#include "io.h"

''')

    gen_list(f.hw, CLASS_LIST, "#define CLASS_%(CLASS)s %(index)d", "#define NCLASS %(count)d")
    gen_list(f.hw, X_LIST, "#define X%(X)s %(index)d", "#define NX %(count)d")
    gen_list(f.hw, Y_LIST, "#define Y%(Y)s %(index)d", "#define NY %(count)d")
    gen_list(f.hw, YX_LIST, "#define YX_%(Y)s_%(X)s %(index)d", "#define NYX %(count)d")

    d = {
        "forx":  ", ".join(["a" for x in X_LIST]),
        "fory":  ", ".join(["a" for y in Y_LIST]),
        "foryx": ", ".join(["a" for yx in YX_LIST]),
    }

    f.hw('''\
typedef struct {
    unsigned y;
    unsigned x;
    const char * label;
    const char * cswitch;
    const char * pswitch;
} yxmap_t;

extern const yxmap_t YX[NYX];

typedef struct { unsigned x[NX];   } x_t;
typedef struct { unsigned y[NY];   } y_t;
typedef struct { unsigned yx[NYX]; } yx_t;
typedef struct { double   x[NX];   } xd_t;
typedef struct { double   y[NY];   } yd_t;
typedef struct { bool     yx[NYX]; } yxbool_t;

#define FOREACH_X(a) %(forx)s
#define FOREACH_Y(a) %(forx)s
#define FOREACH_YX(a) %(forx)s

#define X_NULL      { { FOREACH_X(0) } }
#define Y_NULL      { { FOREACH_Y(0) } }
#define YX_NULL     { { FOREACH_YX(0) } }
#define XD_NULL     { { FOREACH_X(0.0) } }
#define YD_NULL     { { FOREACH_Y(0.0) } }
#define YXBOOL_NULL { { FOREACH_YX(false) } }

extern const x_t X_NULL_C;
extern const y_t Y_NULL_C;
extern const yx_t YX_NULL_C;

''' % d)


def gen_yx_c(f):
    f.cw('''\
const yxmap_t YX[NYX] = {
''')
    for yx in YX_LIST:
        f.cw('''\
    { Y%(Y)s, X%(X)s, "%(y)s-%(x)s", "--%(y)s-%(x)s", "--p-%(y)s-%(x)s" },
''' % yx.d)
    f.cw('''\
};

const x_t X_NULL_C = X_NULL;
const y_t Y_NULL_C = Y_NULL;
const yx_t YX_NULL_C = YX_NULL;
''')

def gen_alg_h(f):
    gen_list(f.hw, ALGORITHMS, "#define ALG_%(YY)s_%(XX)s %(index)d", "#define NALG %(count)d")

def gen_calculate_h(f):
    f.hw('''\
#include "collections.h"
#include "curves.h"
#include "input.h"
#include "random.h"
#include "stat.h"

typedef void (*summarise_collection_t)(const input_t * restrict pinput,
                                       collection_t * restrict pcoll,
                                       unsigned c);

typedef void (*calculate_permtest_t)(const input_t * restrict pinput,
                                     const rng_state_t * restrict rng_state_init,
                                     const collection_t * restrict pcoll,
                                     const yxstat_t * restrict pyxstat,
                                     unsigned part);

typedef void (*calculate_curves_t)(const input_t * restrict pinput,
                                   const rng_state_t * restrict rng_state_init,
                                   const grid_t * restrict pgrid,
                                   const yxstat_t * restrict pyxstat,
                                   unsigned part);

typedef struct {
    summarise_collection_t summarise_collection;
    calculate_permtest_t calculate_permtest;
    calculate_curves_t calculate_curves;
    const char *msg1;
    const char *msg2;
} algv_t;

typedef struct {
    unsigned requirements;
    yxbool_t outputs;
} alg_t;

''')
    f.hw('''\
extern const alg_t ALG[];
extern const algv_t ALG_SPARSE[];
extern const algv_t ALG_DENSE[];

''')

def gen_calculate_c(f):
    f.cw('''\
#include "alg.h"
#include "calcutil.h"
#include "plan.h"
#include "malloc.h"
#include <assert.h>

''')
    for var in VARIANTS:
        gen_summarise_collection_var(f, var)
    for var in VARIANTS:
        gen_calculate_permtest_one(f, var)
    for var in VARIANTS:
        gen_calculate_curves_one(f, var)
    for var in VARIANTS:
        gen_calculate_permtest_var(f, var)
    for var in VARIANTS:
        gen_calculate_curves_var(f, var)
    gen_array(f)
    f.close()

class Indexed:
    def put_to_list(self, l):
        self.set_index(len(l))
        l.append(self)
    
    def set_index(self, index):
        self.index = index
        self.d["index"] = index

class Class(Indexed):
    def __init__(self, key):
        self.key = key
        self.d = {
            "class": self.key,
            "CLASS": self.key.upper(),
        }

class Y(Indexed):
    def __init__(self, key, nondecreasing):
        self.key = key
        self.nondecreasing = nondecreasing
        self.d = {
            "y": self.key,
            "Y": self.key.upper(),
        }

class X(Indexed):
    def __init__(self, key, features):
        self.key = key
        self.features = features
        self.d = {
            "x": self.key,
            "X": self.key.upper(),
        }

class YX(Indexed):
    def __init__(self, y, x):
        self.y = y
        self.x = x
        self.d = dd(y, x)

class YY:
    def __init__(self, y, key, temp, features):
        self.y = y
        self.key = key
        self.temp = temp
        self.features = features

class XX:
    def __init__(self, x, suffix, interleaved):
        self.x = x
        self.suffix = suffix
        self.interleaved = interleaved
        self.features = []
        for x_ in x:
            self.features.extend(x_.features)
        if interleaved:
            self.features.append("WITH_INTERLEAVING")
        
    def get_samples(self, x):
        if self.interleaved:
            return "pinput->samples_word_token[id].%s" % x.key
        else:
            return "pinput->SAMPLES_%s[id]" % x.key.upper()

class V:
    def __init__(self, key):
        self.key = key

class Algorithm(Indexed):
    def __init__(self, yy, xx, has_variants):
        self.xx = xx
        self.yy = yy
        self.has_variants = has_variants
        self.features = xx.features + yy.features
        self.yx_set = set()
        for y in yy.y:
            for x in xx.x:
                yx = YX_MAP[(y.key, x.key)]
                self.yx_set.add(yx)
        self.yx_outputs = [ yx in self.yx_set for yx in YX_LIST ]
        self.d = {
            "yy": yy.key,
            "xx": xx.suffix,
            "YY": yy.key.upper(),
            "XX": xx.suffix.upper(),
            "temp": yy.temp,
            "maybetemp": (", temp" if yy.temp is not None else ""),
            "yaccumlist": ", ".join(["&yaccum_%s" % y.key for y in yy.y]),
            "featurelist": " | ".join(self.features),
            "outputlist": ", ".join(["true" if a else "false" for a in self.yx_outputs]),
            "zeros": ", ".join(["0" for x in xx.x] + ["0" for y in yy.y]),
        }

class Variant(Indexed):
    def __init__(self, alg, v):
        self.alg = alg
        self.v = v
        self.d = dict(alg.d)
        self.d["maybev"] = "" if v.key is None else "_%s" % v.key

class Header:
    def __init__(self, prefix):
        self.d = { "n": prefix, "N": prefix.upper() }
        self.h = open("%s/%s.h" % (DIR, prefix), "w")
        self.hw = self.h.write
        self.hw('''\
#ifndef TYPES_%(N)s_H
#define TYPES_%(N)s_H

// This file is machine-generated.

''' % self.d)

    def close(self):
        self.hw('''\
#endif
''')
        self.h.close()

class Source:
    def __init__(self, prefix):
        self.d = { "n": prefix, "N": prefix.upper() }
        self.c = open("%s/%s.c" % (DIR, prefix), "w")
        self.cw = self.c.write
        self.cw('''\
// This file is machine-generated.

#include "%(n)s.h"
''' % self.d)

    def close(self):
        self.c.close()

CLASS_LIST = []
Y_LIST = []
X_LIST = []
YX_LIST = []
YX_MAP = dict()
ALGORITHMS = []
VARIANTS = []

def setup_variants(yy, xx, vlist):
    has_variants = len(vlist) > 1
    alg = Algorithm(yy, xx, has_variants)
    alg.put_to_list(ALGORITHMS)
    for v in vlist:
        var = Variant(alg, v)
        var.put_to_list(VARIANTS)

def setup_class(c):
    c.put_to_list(CLASS_LIST)

def setup_y(y):
    y.put_to_list(Y_LIST)

def setup_x(x):
    x.put_to_list(X_LIST)

def setup_yx(y, x):
    yx = YX(y, x)
    yx.put_to_list(YX_LIST)
    YX_MAP[(y.key, x.key)] = yx

def gen(what):
    l = what.split("/")
    assert len(l) == 2, l
    assert l[0] == DIR, l
    what = l[1]
    if what == "alg.h":
        f = Header("alg")
        gen_alg_h(f)
        f.close()
    elif what == "calculate.h":
        f = Header("calculate")
        gen_calculate_h(f)
        f.close()
    elif what == "calculate.c":
        f = Source("calculate")
        gen_calculate_c(f)
        f.close()
    elif what == "jump.h":
        import JumpTable
        f = Header("jump")
        gen_jump_h(f)
        f.close()
    elif what == "jump.c":
        import JumpTable
        f = Source("jump")
        gen_jump_c(f)
        f.close()
    elif what == "seed.h":
        f = Header("seed")
        gen_seed_h(f)
        f.close()
    elif what == "seed.c":
        f = Source("seed")
        gen_seed_c(f)
        f.close()
    elif what == "yx.h":
        f = Header("yx")
        gen_yx_h(f)
        f.close()
    elif what == "yx.c":
        f = Source("yx")
        gen_yx_c(f)
        f.close()
    else:
        raise ValueError(what)
    
setup_all()
for what in sys.argv[1:]:
    gen(what)
<file_sep>#!/usr/bin/env python

import optparse
import os
import os.path
import re
import subprocess
import sys

MEXP = 19937

FLAGS_RE = re.compile('flags\s*:')

def tryrun2(cmd):
    try:
        p = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    except:
        return None
    output, error = p.communicate()
    if p.returncode:
        return None
    else:
        return (output, error)
        
def tryrun(cmd):
    r = tryrun2(cmd)
    if r is None:
        return None
    output, error = r
    if error != '':
        return None
    else:
        return output

def tryrun_get_err(cmd):
    r = tryrun2(cmd)
    if r is None:
        return None
    output, error = r
    return error

def versionstring(version):
    return '.'.join([str(v) for v in version])

def test_cc(cc):
    BAD = (None, False)
    version = tryrun([cc, '-dumpversion'])
    if version is None:
        return BAD
    version = version.rstrip(' \n\r').split('.')
    for v in version:
        if not v.isdigit():
            return BAD
    version = [ int(v) for v in version ]
    ok = True
    return (version, ok)

PYTHON_TEST = 'src/test.py'
PYTHON_OK = 'OK\n'

def test_python(python):
    BAD = (None, False)
    version = tryrun_get_err([python, '--version'])
    if version is None:
        return BAD
    version = version.rstrip(' \n\r')
    if not version.startswith('Python '):
        return BAD
    version = version.split(' ')[1].split('.')
    for v in version:
        if not v.isdigit():
            return BAD
    version = [ int(v) for v in version ]
    r = tryrun2([python, PYTHON_TEST])
    if r is None:
        ok = False
    else:
        output, error = r
        if output != PYTHON_OK:
            ok = False
        elif error == '':
            ok = True
        else:
            # Both OK and error messages?
            # Might be first-time initialisation related to matplotlib:
            # try again...
            ok = tryrun([python, PYTHON_TEST]) == PYTHON_OK
    return (version, ok)

class Tool:
    def __init__(self, short, long, re, hook):
        self.short = short
        self.long = long
        self.re = re
        self.hook = hook
        self.msg = None

    def report(self, full, version, ok):
        okstring = "looks good" if ok else "test failed"
        if version is None:
            toolstring = "?"
        else:
            toolstring = "%s %s" % (self.short, versionstring(version))
        print "- %-30s %-20s %s" % (full, toolstring, okstring)

    def find_best(self):
        print "Trying to find %s..." % self.long
        if self.msg is not None:
            print self.msg
        print
        tool = None
        toolversion = None
        pathseen = set()
        for d in os.environ['PATH'].split(os.pathsep):
            if d in pathseen:
                continue
            pathseen.add(d)
            if os.path.isdir(d):
                for f in sorted(os.listdir(d)):
                    if self.re.match(f):
                        full = os.path.join(d, f)
                        (version, ok) = self.hook(full)
                        self.report(full, version, ok)
                        if ok and (toolversion is None or toolversion < version):
                            tool = full
                            toolversion = version
        print
        if tool is None:
            print "Error: could not find %s." % self.long
            sys.exit(1)
        return (tool, toolversion)

    def find_tool(self, hint):
        tool = None
        toolversion = None
        if hint is not None:
            print "Testing %s..." % hint
            if self.msg is not None:
                print self.msg
            print
            (version, ok) = self.hook(hint)
            self.report(hint, version, ok)
            print
            if ok:
                return (hint, version)
        if tool is None:
            return self.find_best()

GCC_RE = re.compile('gcc(-[0-9]+(\.[0-9]+)*)?(\.exe)?\Z')
PYTHON_RE = re.compile('python(-?2+(\.[0-9]+)+)?(\.exe)?\Z')

GCC = Tool('gcc', 'a C compiler', GCC_RE, test_cc)
PYTHON = Tool('python', 'a Python interpreter', PYTHON_RE, test_python)
PYTHON.msg = "I will try to run the test script %s" % PYTHON_TEST


class Config:
    def __init__(self):
        self.cc = None
        self.ccversion = None
        self.python = None
        self.cflags_prod = []
        self.cflags_debug = []
        self.cflags_dep = []
        self.cppflags_prod = []
        self.cppflags_debug = []
        self.cppflags_dep = []
        self.ldflags_prod = []
        self.ldflags_debug = []
        self.popcnt = False
        self.sse2 = False
        self.openmp = True

    def do_all(self):
        self.get_args()
        print
        self.find_platform()
        self.find_cc()
        self.find_python()
        self.find_sqlite()
        self.platform_features()
        self.compiler_flags()
        self.write_flags()

    def get_args(self):
        parser = optparse.OptionParser(description='Configure the system.')
        parser.add_option('--cc', metavar='X', dest='cc',
                          help='Which C compiler to use')
        parser.add_option('--python', metavar='X', dest='python',
                          help='Which Python interpreter to use (full path required)')
        parser.add_option('--enable-openmp', dest='enable_openmp',
                          action='store_true', default=False,
                          help='Use OpenMP even if it looks risky')
        parser.add_option('--disable-openmp', dest='disable_openmp',
                          action='store_true', default=False,
                          help='Do not try to use OpenMP')
        (options, args) = parser.parse_args()
        self.args = options

    def find_platform(self):
        self.osx = False
        self.linux = False
        if sys.platform.startswith('darwin'):
            print "This seems to be a Mac OS X system."
            self.osx = True
        elif sys.platform.startswith('linux'):
            print "This seems to be a Linux system."
            self.linux = True
        elif sys.platform.startswith('cygwin'):
            print "This seems to be a Windows / Cygwin system."
        else:
            print "I do not recognise platform '%s'." % sys.platform
            print "I will try to use reasonable default values."
        print

    def find_cc(self):
        (self.cc, self.ccversion) = GCC.find_tool(self.args.cc)
        print "I will use %s, which seems to be GCC version %s." % (self.cc, versionstring(self.ccversion))
        print "You can override it with the --cc flag."
        print

    def find_python(self):
        (self.python, self.pythonversion) = PYTHON.find_tool(self.args.python)
        print "I will use Python interpreter %s, version %s." % (self.python, versionstring(self.pythonversion))
        print "You can override it with the --python flag."
        print

    def find_sqlite(self):
        print "Making sure that sqlite3 is installed..."
        print
        result = tryrun(['sqlite3', '-version'])
        if result is None:
            print "Error: could not find sqlite3."
            sys.exit(1)

    def platform_features(self):
        print "Inspecting the platform..."
        print
        if self.linux and os.path.isfile('/proc/cpuinfo'):
            print "- reading processor features..."
            print
            with open('/proc/cpuinfo') as f:
                for l in f:
                    if FLAGS_RE.match(l):
                        flags = set(l.split(':')[1].split())
                        if 'sse2' in flags:
                            self.sse2 = True
                        if 'popcnt' in flags:
                            self.popcnt = True
        elif self.osx:
            print "- reading processor features..."
            print
            r = tryrun(['sysctl', '-n', 'machdep.cpu.features'])
            if r is not None:
                flags = set(r.strip().split(' '))
                if 'SSE2' in flags:
                    self.sse2 = True
                if 'POPCNT' in flags:
                    self.popcnt = True
            else:
                # all Intel Macs should have SSE2
                self.sse2 = True

        if self.args.disable_openmp:
            print "- not using OpenMP as requested"
            print
            self.openmp = False
        elif self.osx and self.ccversion < [4,3,0]:
            print "- most likely this compiler does not work reliably with OpenMP"
            print "  (consider installing gcc from Homebrew)"
            print
            self.openmp = False
        elif self.ccversion < [4,2,0]:
            print "- the C compiler is too old to support OpenMP"
            print
            self.openmp = False
        if self.args.enable_openmp and self.openmp == False:
            print "- using OpenMP as requested"
            print
            self.openmp = True

        features = []
        features.append("OpenMP" if self.openmp else "no OpenMP")
        features.append("SSE2" if self.sse2 else "no SSE2")
        features.append("POPCNT" if self.popcnt else "no POPCNT")

        print "- summary:", ', '.join(features)
        print


    def compiler_flags(self):
        for cppflags in (self.cppflags_prod, self.cppflags_debug, self.cppflags_dep):
            cppflags.append("-DSFMT_MEXP=%s" % MEXP)

        self.cppflags_prod.append("-DNDEBUG")

        if self.ccversion >= [4,2,4]:
            self.cflags_prod.append("-march=native")
            if self.osx:
                # http://stackoverflow.com/questions/9840207/how-to-use-avx-pclmulqdq-on-mac-os-x-lion
                self.cflags_prod.append("-Wa,-q")

        if self.openmp:
            self.cflags_prod.append("-fopenmp")
            self.ldflags_prod.append("-fopenmp")

        if self.sse2:
            self.cppflags_prod.append("-DHAVE_SSE2")

        if self.popcnt:
            self.cppflags_prod.append("-DUSE_BUILTIN_POPCOUNT")

        self.cflags_prod.append("-O3")

        if self.ccversion >= [4,7,0]:
            for cflags in (self.cflags_prod, self.cflags_debug, self.cflags_dep):
                cflags.extend(("-std=c11", "-g", "-pedantic",
                               "-Werror", "-Wall", "-Wextra",
                               "-Wformat=2", "-Winit-self", "-Wswitch-enum", "-Wstrict-aliasing",
                               "-Wundef", "-Wshadow", "-Wpointer-arith", "-Wbad-function-cast",
                               "-Wcast-qual", "-Wcast-align", "-Wwrite-strings", "-Wstrict-prototypes",
                               "-Wold-style-definition", "-Wmissing-prototypes", "-Wmissing-declarations",
                               "-Wredundant-decls", "-Wnested-externs", "-Wdisabled-optimization",
                               "-Wno-maybe-uninitialized", "-Wno-sign-compare"))
            self.cflags_prod.append("-Wno-unused")
            if self.ccversion >= [4,8,0]:
                self.cflags_prod.append("-Wno-unused-parameter")
            self.cflags_debug.append("-Wunused-macros")
        else:
            for cflags in (self.cflags_prod, self.cflags_debug, self.cflags_dep):
                cflags.extend(("-std=c99", "-g", "-Wall", "-Wextra", "-Wno-unused", "-Wno-sign-compare"))
            for cppflags in (self.cppflags_prod, self.cppflags_debug, self.cppflags_dep):
                cppflags.append("-D_Noreturn='__attribute__((noreturn))'")

        if not self.openmp:
            self.cflags_prod.append("-Wno-unknown-pragmas")
        self.cflags_debug.append("-Wno-unknown-pragmas")


    def write_flags(self):
        print "Writing configuration..."
        print
        with open('etc/config.inc', 'w') as f:
            def setval(what, val):
                l = "%s = %s" % (what, val)
                print l
                f.write(l)
                f.write("\n")
            def setlist(what, l):
                setval(what, ' '.join(l))

            setval('PYTHON', self.python)
            setval('CC', self.cc)
            setlist('CPPFLAGS',  self.cppflags_prod)
            setlist('CPPFLAGSD', self.cppflags_debug)
            setlist('CPPFLAGSM', self.cppflags_dep)
            setlist('CFLAGS',    self.cflags_prod)
            setlist('CFLAGSD',   self.cflags_debug)
            setlist('CFLAGSM',   self.cflags_dep)
            setlist('LDFLAGS',   self.ldflags_prod)
            setlist('LDFLAGSD',  self.ldflags_debug)
            setlist('LDLIBSDB',  ['-lsqlite3'])
            setval('MEXP', str(MEXP))

        print

Config().do_all()
<file_sep>#!/usr/bin/env python

import datetime

description = "Type and hapax accumulation curves"
author = "<NAME>"
now = datetime.date.today()
version = now.isoformat()
year = now.year

with open('src/version.c', 'w') as f:
    f.write('''\
#include "version.h"

const char * const DESCRIPTION = "%s";
const char * const AUTHOR = "%s";
const char * const VERSION = "%s";
const char * const YEAR = "%d";
''' % (description, author, version, year))

with open('src/TypesVersion.py', 'w') as f:
    f.write('''\
DESCRIPTION = "%s"
AUTHOR = "%s"
VERSION = "%s"
YEAR = "%d"
''' % (description, author, version, year))
<file_sep>#include "version.h"

const char * const DESCRIPTION = "Type and hapax accumulation curves";
const char * const AUTHOR = "<NAME>";
const char * const VERSION = "2014-05-15";
const char * const YEAR = "2014";
<file_sep>Type and hapax accumulation curves
==================================

This is a tool for analysing textual diversity, richness, and
productivity in text corpora and other data sets.

For more information, see
http://users.ics.aalto.fi/suomela/types2/


Downloading and compilation
---------------------------

See the section *Installing dependencies* below for information on how
to set the compilation environment. Then open a terminal and run:

    git clone git://github.com/suomela/types.git
    cd types
    
    ./config
    make
    make check


Examples
--------

See https://github.com/suomela/types-examples for examples.


Installing dependencies
-----------------------

### Ubuntu 15.04

Open a terminal and run:

    sudo apt-get install git python-matplotlib python-lxml sqlite3 libsqlite3-dev


### Ubuntu 12.04

Open a terminal and run:

    sudo apt-get install git python-matplotlib sqlite3 libsqlite3-dev


### Ubuntu 10.04

Open a terminal and run:

    sudo apt-get install git-core python-lxml python-matplotlib sqlite3 libsqlite3-dev


### OS X Yosemite

These instructions should work on OS X 10.10 (Yosemite):

  - Open Terminal.

  - Install Homebrew: http://brew.sh/

        ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
        brew doctor
        brew update

  - Run the following commands to install recent versions of *GCC*,
    *Python*, and the Python modules that we need:

        brew install python
        brew install freetype
        pip install --upgrade pip setuptools
        pip install numpy
        pip install matplotlib
        pip install lxml
        brew install gcc

Once you have followed the above instructions, `./config` should finish
successfully. In particular, it should find the following tools:

        PYTHON = /usr/local/bin/python
        CC = /usr/local/bin/gcc-5


### Windows 7

Download the Cygwin installation program (setup.exe): http://cygwin.com/

Run setup.exe. The default settings are usually fine:

  - "Install from Internet"
  - Root directory: C:\cygwin
  - Local Package Directory: for example, C:\cygwinpkg
  - "Direct Connection"
  - Select a mirror site that is near you
  - Do not select any packages yet
  - "Create icon on Desktop", "Add icon to Start Menu"

If everything goes fine, you should have a "Cygwin Terminal" icon on
your desktop.

Next, we will install some packages. Run setup.exe again.
It should remember all settings that you have selected so far;
just hit "next" until you get the "Select Packages" dialog.
Then select the latest versions of the following packages:

    git
    gcc4
    make
    python
    python-numpy
    pkg-config
    sqlite3
    wget
    libsqlite3-devel
    libxslt-devel
    libfreetype-devel
    libpng-devel

Next, open Cygwin Terminal.

Run `python --version` to find your Python version. Go to
http://pypi.python.org/pypi/setuptools and download and install
the right version of setuptools ("Python Egg"). For example, if your
Python version is 2.6, then you can use the following commands:

    wget http://pypi.python.org/packages/2.6/s/setuptools/setuptools-0.6c11-py2.6.egg
    sh setuptools-0.6c11-py2.6.egg

Once you have installed setuptools, you can use easy_install to install
the remaining Python modules that we need:

    easy_install lxml
    easy_install matplotlib

If all goes fine, you are now ready to follow the usual installation
procedure: use `git` to download the software, run `./config`, etc.
Just keep in mind that you must do everything in Cygwin Terminal.
However, once the software finishes, you can of course browse the
results with more user-friendly tools.

---

If you see any error messages that suggest "... try running rebaseall",
follow the instructions here: http://cygwin.wikia.com/wiki/Rebaseall

In brief, you will need do the following and try again:

  - Exit Cygwin terminal
  - Run C:\cygwin\bin\ash.exe
  - In ash.exe, enter the following commands:

        /bin/rebaseall
        exit

  - Re-open Cygwin terminal

In our experiments, we encountered this issue during the installation
of matplotlib on Windows XP, but not on Windows 7.


License
-------

You can distribute everything under the BSD 3-clause license:
http://opensource.org/licenses/BSD-3-Clause

See below for details.


### SFMT and SFMTJump

Copyright (c) 2006,2007 <NAME>, <NAME> and Hiroshima
University.
Copyright (c) 2012 <NAME>, <NAME>, Hiroshima University
and The University of Tokyo.
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

* Redistributions of source code must retain the above copyright
  notice, this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above
  copyright notice, this list of conditions and the following
  disclaimer in the documentation and/or other materials provided
  with the distribution.
* Neither the names of Hiroshima University, The University of
  Tokyo nor the names of its contributors may be used to endorse
  or promote products derived from this software without specific
  prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


### Other parts

Copyright (c) 2014, <NAME>.

Enjoy, use at your own risk.

To contact the author, see http://users.ics.aalto.fi/suomela/

You can use any of the following licenses to distribute this software:

  - MIT license, http://opensource.org/licenses/MIT

  - BSD 2-clause license, http://opensource.org/licenses/BSD-2-Clause

  - BSD 3-clause license, http://opensource.org/licenses/BSD-3-Clause

The BSD 3-clause license might be most convenient, as it is the same
license under which SFMT is distributed.

For your convenience, here is the text of the MIT license.

----

Copyright (c) 2014 <NAME>

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
<file_sep># coding=utf-8

from collections import defaultdict, Counter, namedtuple
import math
import optparse
import cPickle
import os
import os.path
import re
import sqlite3
import string
import sys
import numpy as np
import TypesDatabase
import TypesParallel
import TypesPlot
from lxml.builder import E

TOOL = 'types-plot'

PLOT_DIR = 'plot'
HTML_DIR = 'html'
BIN_DIR = 'bin'
DATA_FILE = 'types-plot.pickle'

DEFAULT_GROUP = "default"

N_COMMON = 3

FDR = [0.001, 0.01, 0.1]

def msg(msg):
    sys.stderr.write("%s: %s\n" % (TOOL, msg))

def none_to_empty(x):
    return '' if x is None else x

def classes(l):
    if len(l) == 0:
        return {}
    else:
        return { "class": " ".join(l) }

def firstlast(i, rowlist):
    l = []
    if i == 0:
        l.append('first')
    if i == len(rowlist) - 1:
        l.append('last')
    return classes(l)

def get_args():
    parser = optparse.OptionParser(
        description='Update all plots.',
        version=TypesDatabase.version_string(TOOL),
    )
    parser.add_option('--db', metavar='FILE', dest='db',
                      help='which database to read [default: %default]',
                      default=TypesDatabase.DEFAULT_FILENAME)
    TypesParallel.add_options(parser)
    parser.add_option('--type-lists', dest='with_typelists', action='store_true',
                      help='produce type lists',
                      default=False)
    parser.add_option('--sample-lists', dest='with_samplelists', action='store_true',
                      help='produce sample lists',
                      default=False)
    parser.add_option('--slides', dest='slide_version', action='store_true',
                      help='presentation slide version',
                      default=False)
    parser.add_option('--plotdir', metavar='DIRECTORY', dest='plotdir',
                      help='where to store PDF plots [default: %default]',
                      default=PLOT_DIR)
    parser.add_option('--htmldir', metavar='DIRECTORY', dest='htmldir',
                      help='where to store SVG plots and HTML files [default: %default]',
                      default=HTML_DIR)
    (options, args) = parser.parse_args()
    return options

# seq() is a generator that produces
# a, b, ..., z, aa, ab, ..., zz, aaa, aab, ...

C = string.ascii_lowercase

def seqd(depth, prefix):
    if depth <= 0:
        yield prefix
    else:
        for c in C:
            for s in seqd(depth - 1, prefix + c):
                yield s

def seq():
    depth = 1
    while True:
        for s in seqd(depth, ''):
            yield s
        depth += 1


# Convert arbitrary strings to safe, unique filenames

OKCHAR = re.compile(r'[a-zA-Z0-9]+')

class Filenames:
    def __init__(self):
        self.map = dict()
        self.used = set()

    def generate(self, s):
        if s in self.map:
            return

        suffixes = seq()
        prefix = []
        for ok in OKCHAR.finditer(s):
            prefix.append(ok.group().lower())
        if len(prefix) == 0:
            suffix = [ suffixes.next() ]
        else:
            suffix = []
        while True:
            candidate = '-'.join(prefix + suffix)
            assert len(candidate) > 0
            if candidate not in self.used:
                break
            suffix = [ suffixes.next() ]

        self.used.add(candidate)
        self.map[s] = candidate


class SampleData:
    pass


Context = namedtuple('Context', [
    'corpuscode', 'samplecode', 'datasetcode', 'tokencode',
    'before', 'word', 'after', 'link'
])


class AllCurves:
    def __init__(self):
        self.curves = []
        self.statcode_stat = dict()
        self.statcode_label = dict()
        self.by_corpus = defaultdict(list)
        self.by_dataset = defaultdict(list)
        self.by_stat = defaultdict(list)
        self.by_corpus_dataset = defaultdict(list)
        self.by_corpus_stat = defaultdict(list)
        self.by_dataset_stat = defaultdict(list)
        self.by_dataset_stat_fallback = dict()
        self.by_corpus_dataset_stat = dict()
        self.result_q = []

    def read_curves(self, args, conn):
        sys.stderr.write('%s: read:' % TOOL)

        if args.slide_version:
            layout = TypesPlot.layout_slides
        else:
            layout = TypesPlot.layout_normal

        listings = [None]
        if args.with_typelists:
            listings += ['t']
        if args.with_samplelists:
            listings += ['s']
        self.with_lists = len(listings) > 1

        dirdict = {
            "pdf": args.plotdir,
            "svg": args.htmldir,
            "html": args.htmldir,
            "tmp.svg": args.htmldir,
        }

        self.file_corpus = Filenames()
        self.file_stat = Filenames()
        self.file_dataset = Filenames()
        self.file_group = Filenames()
        self.file_collection = Filenames()

        ### log

        timestamp_by_logid = dict()

        def get_timestamp(logid):
            if logid not in timestamp_by_logid:
                ts = [ r[0] for r in conn.execute("SELECT STRFTIME('%s', timestamp) FROM log WHERE id = ?", (logid,)) ]
                assert len(ts) == 1
                timestamp_by_logid[logid] = int(ts[0])
            return timestamp_by_logid[logid]

        ### stat

        sys.stderr.write(' stat')
        r = conn.execute('''
            SELECT statcode, x, y, xlabel.labeltext, ylabel.labeltext
            FROM stat
            JOIN label AS ylabel ON stat.y = ylabel.labelcode
            JOIN label AS xlabel ON stat.x = xlabel.labelcode
            ORDER BY statcode
        ''')
        for statcode, x, y, xlabel, ylabel in r:
            self.file_stat.generate(statcode)
            self.statcode_stat[statcode] = (x, y)
            self.statcode_label[statcode] = (xlabel, ylabel)

        ### corpus

        corpus_descr = dict()
        sys.stderr.write(' corpus')
        r = conn.execute('''
            SELECT corpuscode, description
            FROM corpus
            ORDER BY corpuscode
        ''')
        for corpuscode, description in r:
            self.file_corpus.generate(corpuscode)
            corpus_descr[corpuscode] = description

        ### dataset

        dataset_descr = dict()
        sys.stderr.write(' dataset')
        r = conn.execute('''
            SELECT corpuscode, datasetcode, description
            FROM dataset
            ORDER BY corpuscode, datasetcode
        ''')
        for corpuscode, datasetcode, description in r:
            self.file_dataset.generate(datasetcode)
            dataset_descr[(corpuscode, datasetcode)] = description

        ### sample

        corpus_size = dict()
        sys.stderr.write(' sample')
        r = conn.execute('''
            SELECT corpuscode, COUNT(*), SUM(wordcount)
            FROM sample
            GROUP BY corpuscode
        ''')
        for corpuscode, samplecount, wordcount in r:
            corpus_size[corpuscode] = (samplecount, wordcount)

        ### token

        dataset_size = dict()
        sys.stderr.write(' token')
        r = conn.execute('''
            SELECT corpuscode, datasetcode, COUNT(DISTINCT tokencode), SUM(tokencount)
            FROM token
            GROUP BY corpuscode, datasetcode
        ''')
        for corpuscode, datasetcode, typecount, tokencount in r:
            dataset_size[(corpuscode, datasetcode)] = (typecount, tokencount)

        ### result_curve

        sys.stderr.write(' result_curve')
        r = conn.execute('''
            SELECT corpuscode, statcode, datasetcode, id, level, side, logid
            FROM result_curve
            ORDER BY corpuscode, statcode, datasetcode
        ''')
        for corpuscode, statcode, datasetcode, curveid, level, side, logid in r:
            k = (corpuscode, datasetcode, statcode)

            totals = {
                'type':  dataset_size[(corpuscode,datasetcode)][0],
                'hapax': None,
                'token': dataset_size[(corpuscode,datasetcode)][1],
                'word':  corpus_size[corpuscode][1],
            }

            if k not in self.by_corpus_dataset_stat:
                xkey, ykey = self.statcode_stat[statcode]
                xlabel, ylabel = self.statcode_label[statcode]
                xtotal, ytotal = totals[xkey], totals[ykey]
                c = TypesPlot.Curve(
                        layout,
                        dirdict,
                        corpuscode, self.file_corpus.map[corpuscode],
                        corpus_descr[corpuscode],
                        statcode, self.file_stat.map[statcode],
                        xlabel, ylabel,
                        xtotal, ytotal,
                        datasetcode, self.file_dataset.map[datasetcode],
                        dataset_descr[(corpuscode, datasetcode)],
                        listings
                )
                c.levels = defaultdict(dict)
                self.curves.append(c)
                self.by_corpus[corpuscode].append(c)
                self.by_dataset[datasetcode].append(c)
                self.by_stat[statcode].append(c)
                self.by_corpus_stat[(corpuscode, statcode)].append(c)
                self.by_corpus_dataset[(corpuscode, datasetcode)].append(c)
                self.by_dataset_stat[(datasetcode, statcode)].append(c)
                self.by_corpus_dataset_stat[k] = c
            else:
                c = self.by_corpus_dataset_stat[k]
            c.add_timestamp(get_timestamp(logid))
            c.levels[level][side] = curveid

        ### result_curve_point

        sys.stderr.write(' result_curve_point')

        def get_one_path(curveid):
            return np.array(list(conn.execute('''
                SELECT x, y
                FROM result_curve_point
                WHERE curveid = ?
                ORDER BY x
            ''', (curveid,))), dtype=np.int32)

        for c in self.curves:
            for level in sorted(c.levels.keys()):
                d = c.levels[level]
                if 'upper' in d and 'lower' in d:
                    upper = get_one_path(d['upper'])
                    lower = get_one_path(d['lower'])
                    c.add_poly(level, upper, lower)

        ### collection

        sys.stderr.write(' collection')
        r = conn.execute('''
            SELECT corpuscode, groupcode, collectioncode, description
            FROM collection
            ORDER BY corpuscode, groupcode, collectioncode
        ''')
        for corpuscode, groupcode, collectioncode, description in r:
            if groupcode is None:
                groupcode = DEFAULT_GROUP
            self.file_group.generate(groupcode)
            self.file_collection.generate(collectioncode)
            if corpuscode in self.by_corpus:
                for c in self.by_corpus[corpuscode]:
                    c.add_collection(
                        groupcode, self.file_group.map[groupcode],
                        collectioncode, self.file_collection.map[collectioncode],
                        description
                    )

        ### result_p

        sys.stderr.write(' result_p')
        r = conn.execute('''
            SELECT corpuscode, collectioncode, datasetcode, statcode, y, x, above, below, total, logid
            FROM result_p
        ''')
        for corpuscode, collectioncode, datasetcode, statcode, y, x, above, below, total, logid in r:
            k1 = (corpuscode, datasetcode, statcode)
            p = TypesPlot.Point(collectioncode, y, x, above, below, total, -FDR[-1])
            self.by_corpus_dataset_stat[k1].add_point(p, get_timestamp(logid))

        ### result_q

        sys.stderr.write(' result_q')
        r = conn.execute('''
            SELECT corpuscode, collectioncode, datasetcode, statcode, side, p, q
            FROM result_q
            ORDER BY i
        ''')
        for row in r:
            self.result_q.append(row)

        if self.with_lists:

            self.typelist_cache = {}
            self.samplelist_cache = {}
            self.sample_cache = {}
            self.sampleset_by_collection = defaultdict(set)
            self.sampleset_by_corpus = defaultdict(set)
            self.collectionset_by_sample = defaultdict(set)
            self.collectionset_by_token = defaultdict(set)
            self.sampleset_by_token = defaultdict(set)
            self.tokenset_by_sample = defaultdict(set)
            self.sample_info = {}
            self.tokenset_by_dataset = defaultdict(set)
            self.token_short = {}
            self.tokencount_by_token = Counter()
            self.tokencount_by_sample = Counter()
            self.tokencount_by_sample_token = defaultdict(Counter)
            self.context_by_sample = defaultdict(list)
            self.context_by_token = defaultdict(list)

            self.file_sample = Filenames()
            self.file_token = Filenames()

            ### sample

            sys.stderr.write(' sample')
            try:
                r = conn.execute('''
                    SELECT corpuscode, samplecode, wordcount, description, link
                    FROM sample
                ''')
            except sqlite3.OperationalError:
                r = conn.execute('''
                        SELECT corpuscode, samplecode, wordcount, description, NULL
                        FROM sample
                    ''')
            for corpuscode, samplecode, wordcount, description, link in r:
                self.file_sample.generate(samplecode)
                self.sampleset_by_corpus[corpuscode].add(samplecode)
                self.sample_info[(corpuscode, samplecode)] = (wordcount, description, link)

            ### sample_collection

            sys.stderr.write(' sample_collection')
            r = conn.execute('''
                SELECT corpuscode, samplecode, collectioncode
                FROM sample_collection
            ''')
            for corpuscode, samplecode, collectioncode in r:
                self.sampleset_by_collection[(corpuscode, collectioncode)].add(samplecode)
                self.collectionset_by_sample[(corpuscode, samplecode)].add(collectioncode)

            ### token

            sys.stderr.write(' token')
            r = conn.execute('''
                SELECT corpuscode, samplecode, datasetcode, tokencode, tokencount
                FROM token
            ''')
            for corpuscode, samplecode, datasetcode, tokencode, tokencount in r:
                self.file_token.generate(tokencode)
                self.sampleset_by_token[(corpuscode, datasetcode, tokencode)].add(samplecode)
                self.tokenset_by_sample[(corpuscode, datasetcode, samplecode)].add(tokencode)
                self.tokenset_by_dataset[(corpuscode, datasetcode)].add(tokencode)
                self.token_short[(corpuscode, datasetcode, tokencode)] = tokencode
                self.tokencount_by_token[(corpuscode, datasetcode, tokencode)] += tokencount
                self.tokencount_by_sample[(corpuscode, datasetcode, samplecode)] += tokencount
                self.tokencount_by_sample_token[(corpuscode, datasetcode, samplecode)][tokencode] += tokencount
                collectioncodes = self.collectionset_by_sample[(corpuscode, samplecode)]
                for c in collectioncodes:
                    self.collectionset_by_token[(corpuscode, datasetcode, tokencode)].add(c)

            ### tokeninfo

            sys.stderr.write(' tokeninfo')
            r = list(conn.execute('''
                SELECT COUNT(*)
                FROM sqlite_master
                WHERE type='table' AND name='tokeninfo'
            '''))
            if r[0][0] > 0:
                r = conn.execute('''
                    SELECT corpuscode, datasetcode, tokencode, shortlabel, longlabel
                    FROM tokeninfo
                ''')
                for corpuscode, datasetcode, tokencode, shortlabel, longlabel in r:
                    self.token_short[(corpuscode, datasetcode, tokencode)] = shortlabel

            ### context

            sys.stderr.write(' context')
            r = list(conn.execute('''
                SELECT COUNT(*)
                FROM sqlite_master
                WHERE type='table' AND name='context'
            '''))
            if r[0][0] > 0:
                r = conn.execute('''
                    SELECT corpuscode, samplecode, datasetcode, tokencode,
                           before, word, after, link
                    FROM context
                ''')
                for row in r:
                    c = Context(*row)
                    self.context_by_token[(c.corpuscode, c.datasetcode, c.tokencode)].append(c)
                    self.context_by_sample[(c.corpuscode, c.datasetcode, c.samplecode)].append(c)

        sys.stderr.write('\n')

        ### fallbacks

        for datasetcode, statcode in self.by_dataset_stat.keys():
            l = []
            for corpuscode in sorted(self.by_corpus.keys()):
                if (corpuscode, datasetcode, statcode) in self.by_corpus_dataset_stat:
                    c = self.by_corpus_dataset_stat[(corpuscode, datasetcode, statcode)]
                elif (corpuscode, statcode) in self.by_corpus_stat:
                    c = self.by_corpus_stat[(corpuscode, statcode)][0]
                elif (corpuscode, datasetcode) in self.by_corpus_dataset:
                    c = self.by_corpus_dataset[(corpuscode, datasetcode)][0]
                else:
                    c = self.by_corpus[corpuscode][0]
                l.append(c)
            self.by_dataset_stat_fallback[(datasetcode, statcode)] = l

    def create_directories(self):
        directories = set()
        for c in self.curves:
            directories.update(c.get_directories())
        for d in directories:
            if not os.path.exists(d):
                os.makedirs(d)

    def generate_html(self):
        for c in self.curves:
            sys.stderr.write('.')
            c.generate_html(self)

    def generate_corpus_menu(self):
        tablerows = []
        cell = E.td("Corpora", colspan="2")
        tablerows.append(E.tr(cell, **classes(['head'])))
        corpuslist = sorted(self.by_corpus.keys())
        for i, corpuscode in enumerate(corpuslist):
            c = self.by_corpus[corpuscode][0]
            cells = [
                E.td(E.a(corpuscode, href=c.get_pointname_from_root('html', None))),
                E.td(none_to_empty(c.corpus_descr), **classes(['wrap', 'small'])),
            ]
            tablerows.append(E.tr(*cells, **firstlast(i, corpuslist)))
        return tablerows

    def generate_fdr_table(self):
        blocks = []
        current = None
        fdri = 0
        for row in self.result_q:
            corpuscode, collectioncode, datasetcode, statcode, side, p, q = row
            while fdri < len(FDR) and q > FDR[fdri]:
                fdri += 1
                current = None
            if fdri == len(FDR):
                break
            if current is None:
                current = []
                blocks.append((fdri, current))
            current.append(row)

        small = classes(['small'])
        tablerows = []
        for fdri, block in blocks:
            text = u"Findings — false discovery rate %s" % FDR[fdri]
            cell = E.td(text, colspan="6")
            l = ['head']
            if len(tablerows) > 0:
                l.append('sep')
            tablerows.append(E.tr(cell, **classes(l)))
            for i, row in enumerate(block):
                corpuscode, collectioncode, datasetcode, statcode, side, p, q = row
                c = self.by_corpus_dataset_stat[(corpuscode, datasetcode, statcode)]
                groupcode = c.group_by_collection[collectioncode]
                point = c.point_by_collection[collectioncode]
                point.fdr = FDR[fdri]
                desc = c.collection_descr[collectioncode]
                lh = u"−" if side == "below" else "+"
                x, y = self.statcode_label[statcode]
                attr = dict()
                if desc is not None:
                    attr["title"] = desc
                attr["href"] = c.get_pointname_from_root('html', groupcode, point)
                cells = [
                    E.td(E.a(collectioncode, **attr)),
                    E.td(lh),
                    E.td("%s/%s" % (y,x), **small),
                    E.td(datasetcode, **small),
                    E.td(corpuscode, **small),
                    E.td("%.5f" % p, **small),
                ]
                tablerows.append(E.tr(*cells, **firstlast(i, block)))
        return tablerows

    def generate_index(self, htmldir):
        sys.stderr.write('.')
        headblocks = []
        bodyblocks = []
        headblocks.append(E.title("Corpus menu"))
        headblocks.append(E.link(rel="stylesheet", href="types.css", type="text/css"))
        tablerows = self.generate_corpus_menu()
        bodyblocks.append(E.div(E.table(*tablerows), **classes(["mainmenu"])))
        tablerows = self.generate_fdr_table()
        if len(tablerows) > 0:
            bodyblocks.append(E.div(E.table(*tablerows), **classes(["findings"])))
        doc = E.html(E.head(*headblocks), E.body(*bodyblocks))
        with open(os.path.join(htmldir, "index.html"), 'w') as f:
            TypesPlot.write_html(f, doc)
        with open(os.path.join(htmldir, "types.css"), 'w') as f:
            f.write(CSS)

    def get_context_filename_sample(self, datasetcode, samplecode):
        b = TypesPlot.cleanlist([
            '',
            's',
            self.file_dataset.map[datasetcode],
            self.file_sample.map[samplecode],
        ])
        return '_'.join(b) + '.html'

    def get_context_filename_token(self, datasetcode, tokencode, collectioncode=None):
        b = TypesPlot.cleanlist([
            '',
            't',
            self.file_dataset.map[datasetcode],
            self.file_token.map[tokencode],
            None if collectioncode is None else self.file_collection.map[collectioncode],
        ])
        return '_'.join(b) + '.html'

    def sample_link(self, corpuscode, datasetcode, samplecode, tokencode=None):
        if (corpuscode, datasetcode, samplecode) not in self.context_by_sample:
            return samplecode
        else:
            link = self.get_context_filename_sample(datasetcode, samplecode)
            if tokencode is not None:
                link += "#t{}".format(self.file_token.map[tokencode])
            return E.a(samplecode, href=link)

    def token_link(self, corpuscode, datasetcode, tokencode, samplecode=None, collectioncode=None, shorten=True):
        token = self.token_short[(corpuscode, datasetcode, tokencode)] if shorten else tokencode
        flags = {}
        if token != tokencode:
            flags["title"] = tokencode
        if (corpuscode, datasetcode, tokencode) not in self.context_by_token:
            return E.span(token, **flags)
        else:
            link=self.get_context_filename_token(datasetcode, tokencode, collectioncode)
            if samplecode is not None:
                link += "#s{}".format(self.file_sample.map[samplecode])
            return E.a(token, href=link, **flags)

    def generate_context(self, htmldir):
        for key in sorted(self.context_by_sample.keys()):
            sys.stderr.write('.')
            corpuscode, datasetcode, samplecode = key
            title = samplecode
            wordcount, descr, link = self.sample_info[(corpuscode, samplecode)]
            if descr is None:
                if link is None:
                    headtext = [E.p(samplecode)]
                else:
                    headtext = [E.p(E.a(samplecode, href=link))]
            else:
                if link is None:
                    headtext = [E.p(samplecode, ": ", descr)]
                else:
                    headtext = [E.p(samplecode, ": ", E.a(descr, href=link))]
            filename = self.get_context_filename_sample(datasetcode, samplecode)
            filename = os.path.join(htmldir, self.file_corpus.map[corpuscode], filename)
            l = self.context_by_sample[(corpuscode, datasetcode, samplecode)]
            self.generate_context_one(l, filename, title, headtext, "sample")
        for key in sorted(self.context_by_token.keys()):
            sys.stderr.write('.')
            corpuscode, datasetcode, tokencode = key
            collectioncodes = sorted(self.collectionset_by_token[key])
            l_all = self.context_by_token[(corpuscode, datasetcode, tokencode)]
            for collectioncode in [None] + collectioncodes:
                if collectioncode is not None:
                    title = u'{} · {}'.format(tokencode, samplecode)
                    headtext = [E.p(
                        self.token_link(corpuscode, datasetcode, tokencode, shorten=False),
                        u' — ',
                        collectioncode
                    )]
                    sampleset = self.sampleset_by_collection[(corpuscode, collectioncode)]
                    l = [c for c in l_all if c.samplecode in sampleset]
                else:
                    title = tokencode
                    if len(collectioncodes) > 0:
                        links = [
                            E.a(c, href=self.get_context_filename_token(datasetcode, tokencode, c))
                            for c in collectioncodes
                        ]
                        headtext = [E.p(
                            tokencode,
                            u' — ',
                            *TypesPlot.add_sep(links, u' · ')
                        )]
                    else:
                        headtext = [E.p(tokencode)]
                    l = l_all
                filename = self.get_context_filename_token(datasetcode, tokencode, collectioncode)
                filename = os.path.join(htmldir, self.file_corpus.map[corpuscode], filename)
                self.generate_context_one(l, filename, title, headtext, "token")

    def generate_context_one(self, l, filename, title, headtext, what):
        headblocks = []
        bodyblocks = []
        headblocks.append(E.title(title))
        headblocks.append(E.link(rel="stylesheet", href="../types.css", type="text/css"))
        headrow = [
            E.td('Sample', colspan="2"),
            E.td('Token', **classes(["pad"])),
            E.td(E.span('Before'), **classes(["before"])),
            E.td(E.span('Word'), **classes(["word"])),
            E.td(E.span('After'), **classes(["after"])),
        ]
        bodyblocks.extend(headtext)
        tablerows = [E.tr(*headrow, **classes(["head"]))]
        grouped = defaultdict(list)
        for c in l:
            if what == "sample":
                key = "t{}".format(self.file_token.map[c.tokencode])
            elif what == "token":
                key = "s{}".format(self.file_sample.map[c.samplecode])
            else:
                assert False
            grouped[key].append(c)

        for key in sorted(grouped.keys()):
            ll = grouped[key]
            ll = sorted(ll, key=lambda c: (c.after, c.before, c.word))
            block = []
            for c in ll:
                row = []
                wordcount, descr, link = self.sample_info[(c.corpuscode, c.samplecode)]
                if descr is None:
                    if link is None:
                        dl = None
                    else:
                        dl = E.a('link', href=link)
                else:
                    if link is None:
                        dl = descr
                    else:
                        dl = E.a(descr, href=link)
                if what == "sample":
                    sample = c.samplecode
                    token = self.token_link(c.corpuscode, c.datasetcode, c.tokencode, c.samplecode)
                elif what == "token":
                    sample = self.sample_link(c.corpuscode, c.datasetcode, c.samplecode, c.tokencode)
                    token = self.token_short[(c.corpuscode, c.datasetcode, c.tokencode)]
                else:
                    assert False
                before = none_to_empty(c.before)
                word = none_to_empty(c.word)
                after = none_to_empty(c.after)
                if c.link is not None:
                    word = E.a(word, href=c.link)
                if dl is None:
                    row = [
                        E.td(sample, colspan="2")
                    ]
                else:
                    row = [
                        E.td(sample),
                        E.td(dl),
                    ]
                row += [
                    E.td(token, **classes(["pad"])),
                    E.td(E.span(before), **classes(["before"])),
                    E.td(E.span(word), **classes(["word"])),
                    E.td(E.span(after), **classes(["after"])),
                ]
                block.append(E.tr(*row))
            tablerows.append(E.tbody(*block, id=key))

        bodyblocks.append(E.div(E.table(*tablerows), **classes(["context"])))
        doc = E.html(E.head(*headblocks), E.body(*bodyblocks))
        with open(filename, 'w') as f:
            TypesPlot.write_html(f, doc)

    def find_outdated(self):
        redraw = []
        for c in self.curves:
            for outdated in c.get_outdated():
                redraw.append((c, outdated))
        return redraw

    def get_typelist(self, corpuscode, datasetcode, collectioncode):
        k = (corpuscode, datasetcode, collectioncode)
        if k not in self.typelist_cache:
            self.typelist_cache[k] = self.calc_typelist(*k)
        return self.typelist_cache[k]

    def get_samplelist(self, corpuscode, datasetcode, collectioncode):
        k = (corpuscode, datasetcode, collectioncode)
        if k not in self.samplelist_cache:
            self.samplelist_cache[k] = self.calc_samplelist(*k)
        return self.samplelist_cache[k]

    def get_sample(self, corpuscode, datasetcode, samplecode):
        k = (corpuscode, datasetcode, samplecode)
        if k not in self.sample_cache:
            self.sample_cache[k] = self.calc_sample(*k)
        return self.sample_cache[k]

    def calc_typelist(self, corpuscode, datasetcode, collectioncode):
        if collectioncode is None:
            typelist = sorted(self.tokenset_by_dataset[(corpuscode, datasetcode)])
            r = defaultdict(list)
            for t in typelist:
                tsamples = self.sampleset_by_token[(corpuscode, datasetcode, t)]
                total = len(tsamples)
                if total == 0:
                    continue
                bracket = int(math.log(total, 2))
                r[bracket].append((t, total))
            tables = []
            brackets = sorted(r.keys())
            for bracket in brackets:
                table = []
                l = sorted(r[bracket], key=lambda x: (-x[1], x[0]))
                for t, total in l:
                    table.append(E.tr(
                        bar(total, 'bara', bracket=bracket),
                        E.td(E.span(self.token_link(corpuscode, datasetcode, t))),
                        title=u"{}: {} samples".format(t, total)
                    ))
                tables.append(E.table(*table))
        else:
            csamples = self.sampleset_by_collection[(corpuscode, collectioncode)]
            typelist = sorted(self.tokenset_by_dataset[(corpuscode, datasetcode)])
            r = defaultdict(list)
            for t in typelist:
                tsamples = self.sampleset_by_token[(corpuscode, datasetcode, t)]
                here = len(tsamples & csamples)
                other = len(tsamples - csamples)
                total = here + other
                if total == 0:
                    continue
                bracket = int(math.log(total, 2))
                ratio = here / float(total)
                r[bracket].append((t, here, other, ratio))
            tables = []
            brackets = sorted(r.keys())
            for bracket in brackets:
                table = []
                l = sorted(r[bracket], key=lambda x: (-x[3], -x[1], x[2], x[0]))
                for t, here, other, ratio in l:
                    if here > 0:
                        tokenlink = self.token_link(corpuscode, datasetcode, t, collectioncode=collectioncode)
                    else:
                        tokenlink = self.token_short[(corpuscode, datasetcode, t)]
                    table.append(E.tr(
                        bar(here, 'bara', bracket=bracket),
                        bar(other, 'barb', bracket=bracket),
                        E.td(tokenlink),
                        title=u"{} — {}: {} samples, other: {} samples".format(t, collectioncode, here, other)
                    ))
                tables.append(E.table(*table))
        return [E.table(
            E.tr(E.td(u"Types that occur in…", colspan="{}".format(len(brackets)))),
            E.tr(*[E.td(descr_bracket(bracket)) for bracket in brackets], **{"class": "head"}),
            E.tr(*[E.td(x) for x in tables], **{"class": "first last"}),
        )]

    def calc_sample(self, corpuscode, datasetcode, samplecode):
        s = SampleData()
        s.samplecode = samplecode
        skey = (corpuscode, datasetcode, samplecode)
        s.wordcount, s.descr, s.link = self.sample_info[(corpuscode, samplecode)]
        typelist = sorted(self.tokenset_by_sample[skey])
        s.collections = sorted(self.collectionset_by_sample[(corpuscode, samplecode)])
        s.hapaxlist = []
        s.otherlist = []
        s.uniquelist = []
        for t in typelist:
            if self.tokencount_by_token[(corpuscode, datasetcode, t)] == 1:
                s.hapaxlist.append(t)
            elif len(self.sampleset_by_token[(corpuscode, datasetcode, t)]) == 1:
                s.uniquelist.append(t)
            else:
                s.otherlist.append(t)
        s.commonlist = self.tokencount_by_sample_token[skey].most_common(N_COMMON + 1)
        if len(s.commonlist) > 0:
            if len(s.commonlist) == N_COMMON + 1:
                threshold = max(s.commonlist[-1][1], 1)
            else:
                threshold = 1
            s.commonlist = [(x,c) for x,c in s.commonlist if c > threshold]
            s.commonlist = sorted(s.commonlist, key=lambda x: (-x[1], x[0]))
        s.tokencount = self.tokencount_by_sample[skey]
        s.typecount = len(typelist)
        s.uniquecount = len(s.uniquelist) + len(s.hapaxlist)
        s.hapaxcount = len(s.hapaxlist)
        return s

    def calc_samplelist(self, corpuscode, datasetcode, collectioncode):
        if collectioncode is not None:
            csamples = self.sampleset_by_collection[(corpuscode, collectioncode)]
        else:
            csamples = self.sampleset_by_corpus[corpuscode]
        l = []
        maxwords = 1
        maxtokens = 1
        maxtypes = 1
        for samplecode in csamples:
            s = self.get_sample(corpuscode, datasetcode, samplecode)
            l.append(s)
            maxwords = max(maxwords, s.wordcount)
            maxtokens = max(maxtokens, s.tokencount)
            maxtypes = max(maxtypes, s.typecount)

        l = sorted(l, key=lambda s: (-s.wordcount, s.samplecode))
        tablerows = []
        for s in l:
            clist = []
            for t,c in s.commonlist:
                if len(clist) > 0:
                    clist.append(', ')
                clist.append(self.token_link(corpuscode, datasetcode, t, s.samplecode))
                clist.append(u"\u202F×\u202F{}".format(c))
            ulist = [self.token_link(corpuscode, datasetcode, t, s.samplecode) for t in s.uniquelist + s.hapaxlist]
            tablerows.append([
                E.td(self.sample_link(corpuscode, datasetcode, s.samplecode)),
                E.td(none_to_empty(s.descr)),
                E.td(str(s.wordcount), **{"class": "right"}),
                bar(s.wordcount, 'bar', maxval=maxwords),
                E.td(str(s.tokencount), **{"class": "right"}),
                bar(s.tokencount, 'bar', maxval=maxtokens),
                E.td(str(s.typecount), **{"class": "right"}),
                bar(s.typecount, 'bar', maxval=maxtypes),
                E.td(str(s.uniquecount), **{"class": "right"}),
                bar(s.uniquecount, 'bar', maxval=maxtypes),
                E.td(str(s.hapaxcount), **{"class": "right"}),
                bar(s.hapaxcount, 'bar', maxval=maxtypes),
                E.td(*clist),
                E.td(*TypesPlot.add_sep(ulist, ', '), **{"class": "wrap"}),
            ])
        table = [
            E.tr(
                E.td('Sample', colspan="2"),
                E.td('Words', colspan="2"),
                E.td('Tokens', colspan="2"),
                E.td('Types', colspan="2"),
                E.td('Unique', colspan="2"),
                E.td('Hapaxes', colspan="2"),
                E.td('Common types'),
                E.td('Unique types', **{"class": "wide"}),
                **{"class": "head"}
            )
        ]
        for i, row in enumerate(tablerows):
            table.append(E.tr(*row, **firstlast(i, tablerows)))
        return [E.table(*table)]


def descr_bracket(bracket):
    a = 2 ** bracket
    b = 2 * a
    if a == 1:
        assert b == 2
        return '{} sample'.format(a)
    else:
        return '< {} samples'.format(b)

def bar(x, label, bracket=None, maxval=None):
    x = bar_scale(x, bracket, maxval)
    return E.td(
        E.span(
            '',
            style="border-left-width: {}px;".format(x)
        ),
        **classes([label])
    )

def bar_scale(x, bracket=None, maxval=None):
    if bracket is not None:
        scale = math.sqrt(2 ** bracket)
        return int(round(5.0 * x / scale))
    elif maxval is not None:
        return int(round(25.0 * x / maxval))
    else:
        return x

def get_datafile(args):
    return os.path.join(args.tmpdir, DATA_FILE)

def write_data(args, redraw):
    with open(get_datafile(args), 'w') as f:
        cPickle.dump(redraw, f, -1)

def run(args, nredraw):
    cmds = []
    for j in range(args.parts):
        cmd = [ get_datafile(args), nredraw, args.parts, j+1 ]
        cmds.append(cmd)
    TypesParallel.Parallel(TOOL, 'types-draw-curves', cmds, args).run()

def main():
    args = get_args()
    if not os.path.exists(args.tmpdir):
        os.makedirs(args.tmpdir)
    conn = TypesDatabase.open_db(args.db)
    ac = AllCurves()
    ac.read_curves(args, conn)
    conn.commit()
    if len(ac.curves) == 0:
        msg('there are no results in the database')
        return
    ac.create_directories()
    sys.stderr.write('%s: write: (' % TOOL)
    ac.generate_index(args.htmldir)
    if ac.with_lists:
        ac.generate_context(args.htmldir)
    ac.generate_html()
    sys.stderr.write(')\n')
    redraw = ac.find_outdated()
    nredraw = len(redraw)
    if nredraw == 0:
        msg('all files up to date')
    else:
        msg('outdated: %d files' % nredraw)
        write_data(args, redraw)
        run(args, nredraw)
        os.remove(get_datafile(args))
        msg('all done')

CSS = """
BODY {
    color: #000;
    background-color: #fff;
    font-family: Helvetica, Arial, sans-serif;
    padding: 0px;
    margin: 15px;
}

.listing, .stats, .context {
    font-size: 85%;
}

.menuitem {
    font-size: 90%;
}

.small, .menudesc, .menudescinline {
    font-size: 80%;
}

A:link {
    color: <DARK>;
    text-decoration: none;
}

A:visited {
    color: <DARK>;
    text-decoration: none;
}

A:hover, A:active {
    text-decoration: underline;
}

TABLE {
    border-collapse: collapse;
}

.mainmenu, .findings, .listing, .stats {
    margin-left: 4px;
    margin-bottom: 20px;
}

.findings, .listing, .stats, .context {
    margin-top: 20px;
}

TD {
    padding: 0px;
    padding-top: 1px;
    padding-bottom: 1px;
    text-align: left;
    vertical-align: top;
    white-space: nowrap;
}

TD.right {
    text-align: right;
}

TD+TD {
    padding-left: 15px;
}

TD.pad {
    padding-right: 15px;
}

TD.wrap {
    white-space: normal;
}

TR.head>TD {
    padding-top: 5px;
    padding-bottom: 5px;
    border-bottom: 1px solid #888;
}

TR.head.sep>TD {
    padding-top: 30px;
}

TR.first>TD, .context TBODY>TR:first-child>TD {
    padding-top: 5px;
}

TR.last>TD, .context TBODY>TR:last-child>TD {
    padding-bottom: 5px;
    border-bottom: 1px solid #888;
}

P {
    margin: 0px;
    margin-top: 3px;
    margin-bottom: 3px;
    padding: 0px;
}

.plot {
    margin-top: 20px;
    margin-bottom: 10px;
}

.menudesc {
    margin-left: 30px;
}

.menuitem, .menutitle, .menudescinline {
    display: inline-block;
    padding-top: 1px;
    padding-bottom: 1px;
    padding-left: 2px;
    padding-right: 2px;
    border: 1px solid #fff;
    margin-top: 1px;
    margin-bottom: 1px;
    margin-left: 1px;
    margin-right: 1px;
}

.menuitem, .menutitle {
    white-space: nowrap;
}

.menu A:hover, .menu A:link, .menu A:visited {
    text-decoration: none;
}

.menusel {
    border: 1px solid #000;
    background-color: #fff;
}

A.menuitem:hover, A.menutitle:hover {
    border: 1px dotted #000;
    background-color: #eee;
}

TD.bar {
    padding-left: 5px;
}

TD.bara {
    text-align: right;
}

TD.barb {
    padding-left: 1px;
}

TD.barb+TD {
    padding-left: 5px;
}

TD.bar>SPAN, TD.bara>SPAN {
    border-left: 0px solid <DARK>;
}

TD.barb>SPAN {
    border-left: 0px solid <LIGHT>;
}

TD.wide {
    min-width: 40ex;
}

TD.before {
    text-align: right;
}

TD.word {
    text-align: center;
}

TD.after {
    text-align: left;
}

TD.before, TD.after {
    overflow: hidden;
    position: relative;
    width: 50%;
}

TD.before SPAN {
    position: absolute;
    right: 0px;
}

TD.after SPAN {
    position: absolute;
    left: 15px;
}

.menusel {
    color: #000;
}

A.menusame, A.menutitle {
    color: <DARK>;
}

A.menuother {
    color: #888;
}

TBODY:target {
    background-color: #eee;
}
"""

CSS = CSS.replace('<DARK>', '#' + TypesPlot.REGIONS_RGB[0])
CSS = CSS.replace('<LIGHT>', '#' + TypesPlot.REGIONS_RGB[2])

main()
<file_sep>import sys
if len(sys.argv) > 1:
    sys.stderr.write('(')

import cPickle
import os
import os.path
import multiprocessing
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot
import TypesPlot

if len(sys.argv) == 1:
    print "This tool is for internal use only."
    print "See 'types-plot' for the user-friendly interface."
    sys.exit(0)

def get_limit(nredraw, nproc, id):
    assert 0 <= id <= nproc
    if nredraw == nproc:
        return id
    elif id == 0:
        return 0
    elif id == nproc:
        return nredraw
    else:
        frac = float(id) / float(nproc)
        return int(nredraw * frac)

def load():
    with open(datafile) as f:
        redraw = cPickle.load(f)
    return redraw

def do_plot(i):
    c, outdated = redraw[i]
    c.plot_group(matplotlib, outdated)
    sys.stderr.write('.')
    return True

dummy, datafile, nredraw, nproc, id = sys.argv
nredraw, nproc, id = [ int(a) for a in [ nredraw, nproc, id ]]
assert 1 <= id <= nproc
id -= 1

fro = get_limit(nredraw, nproc, id)
to = get_limit(nredraw, nproc, id+1)
if fro == to:
    sys.exit(0)

redraw = load()
sys.stderr.write('!')

if sys.platform.startswith('cygwin'):
    # Multiprocessing causes are DLL address conflicts
    # that cannot be solved with "rebaseall".
    # Workaround: disable parallelism on cygwin platforms
    for i in range(fro, to):
        assert do_plot(i)
else:
    pool = multiprocessing.Pool()
    results = []
    for i in range(fro, to):
        results.append(pool.apply_async(do_plot, [i]))
    pool.close()
    pool.join()
    for r in results:
        assert r.get()

sys.stderr.write(')')
<file_sep># coding=utf-8

from collections import namedtuple
import itertools
import os
import numpy as np
from lxml.builder import E
from lxml import etree

def colour(c):
    return tuple([ int(c[2*i:2*i+2], 16)/float(255) for i in range(3) ])

def colours(l):
    return [ colour(c) for c in l ]

# Colour scheme from:
# http://colorbrewer2.org/?type=sequential&scheme=PuBu&n=4
REGIONS_RGB = ('0570b0', '74a9cf', 'bdc9e1', 'f1eef6')

WHITE  = colour('ffffff')
GREY   = colour('999999')
DARK   = colour('333333')
BLACK  = colour('000000')
REGIONS = colours(REGIONS_RGB)

class CPoint:
    def __init__(self, ec, fc, lw):
        self.ec = ec
        self.fc = fc
        self.lw = lw

Layout = namedtuple('Layout', [
    'width', 'height', 'dpi',
    'label_sep', 'label_area', 'xsep',
    'sel', 'unsel',
    'xbins', 'spp',
])

layout_slides = Layout(
    width = 6,
    height = 3,
    dpi = 96,
    label_sep = 0.12,
    label_area = (0.03, 0.97),
    xsep = 0.05,
    sel = CPoint( BLACK, WHITE, 1.5 ),
    unsel = CPoint( GREY,  WHITE, 1.0 ),
    xbins = 5,
    spp = {'left': 0.15, 'right': 0.77, 'bottom': 0.1, 'top': 0.98},
)

layout_normal = Layout(
    width = 9,
    height = 6,
    dpi = 96,
    label_sep = 0.06,
    label_area = (0.03, 0.97),
    xsep = 0.03,
    sel = CPoint( BLACK, WHITE, 1.5 ),
    unsel = CPoint( GREY,  WHITE, 0.5 ),
    xbins = None,
    spp = {'left': 0.1, 'right': 0.85, 'bottom': 0.1, 'top': 0.98},
)

LISTING_LABEL = { None: 'summary', 't': 'type list', 's': 'sample list' }

AXIS_PAD = 0.02

def lim(maxval):
    return (-AXIS_PAD * maxval, (1.0 + AXIS_PAD) * maxval)

def ucfirst(s):
    if s == '':
        return s
    else:
        return s[0].upper() + s[1:]

def add_sep(l, sep):
    # [1,2,3] -> [1,sep,2,sep,3]
    return [x for y in l for x in (y, sep)][:-1]

def write_html(f, doc):
    f.write('<!DOCTYPE html>\n')
    f.write(etree.tostring(doc, method='html', pretty_print=True))

def longest_common_prefix(a, b):
    i = 0
    while i < len(a) and i < len(b) and a[i] == b[i]:
        i += 1
    return i

def wrap_svg_link(el, url, title=None):
    link = etree.Element("a")
    link.set('{http://www.w3.org/1999/xlink}href', url)
    if title is not None:
        link.set('{http://www.w3.org/1999/xlink}title', title)
    link.set('target', '_top')
    parent = el.getparent()
    assert parent is not None
    parent.replace(el, link)
    link.append(el)

def cleanlist(l):
    l = ['' if x is None else x for x in l]
    while len(l) > 0 and l[-1] == '':
        l = l[:-1]
    return l


class LabelPlacement:
    def __init__(self, layout):
        self.layout = layout
        self.freelist = set()
        self.freelist.add(self.layout.label_area)

    def place(self, y):
        closest = None
        bestdist = None
        bestplace = None
        for free in self.freelist:
            a, b = free
            if y < a:
                dist = a - y
                place = a
            elif a <= y <= b:
                dist = 0.0
                place = y
            elif b < y:
                dist = y - b
                place = b
            else:
                assert False
            if bestdist is None or bestdist > dist or (bestdist == dist and free < closest):
                closest = free
                bestdist = dist
                bestplace = place
        if closest is None:
            return None
        self.freelist.remove(closest)
        y1, y4 = closest
        y2 = bestplace - self.layout.label_sep
        y3 = bestplace + self.layout.label_sep
        if y1 < y2:
            self.freelist.add((y1, y2))
        if y3 < y4:
            self.freelist.add((y3, y4))
        return bestplace

class Point:
    def __init__(self, collectioncode, y, x, above, below, total, fdr):
        self.collectioncode = collectioncode
        self.y = y
        self.x = x
        if above < below:
            is_above = True
            self.side = 'above'
            self.pvalue = float(above)/float(total)
        else:
            is_above = False
            self.side = 'below'
            self.pvalue = float(below)/float(total)
        # negative if larger
        self.fdr = fdr

        self.ms = 7
        self.marker = 'o'

        if self.side is None:
            pass
        elif self.pvalue > 0.01:
            pass
        elif is_above:
            self.ms = 10
            self.marker = '^'
        else:
            self.ms = 10
            self.marker = 'v'

        self.ec = BLACK
        self.fc = WHITE
        self.lw = 1.0


class Curve:
    def __init__(self, layout, dirdict,
                 corpuscode, corpus_filename, corpus_descr,
                 statcode, stat_filename,
                 xlabel, ylabel, xtotal, ytotal,
                 datasetcode, dataset_filename, dataset_descr,
                 listings):
        self.layout = layout
        self.dirdict = dirdict
        self.corpuscode = corpuscode
        self.corpus_filename = corpus_filename
        self.corpus_descr = corpus_descr
        self.statcode = statcode
        self.stat_filename = stat_filename
        self.xlabel = xlabel
        self.ylabel = ylabel
        self.xtotal = xtotal
        self.ytotal = ytotal
        self.datasetcode = datasetcode
        self.dataset_filename = dataset_filename
        self.dataset_descr = dataset_descr
        self.timestamp = None
        self.collection_descr = dict()
        self.collection_filenames = dict()
        self.group_by_collection = dict()
        self.group_filenames = dict()
        self.point_by_collection = dict()
        self.points_by_group = dict()
        self.groups = []
        self.group_set = set()
        self.timestamp_by_group = dict()
        self.polys = []
        self.maxx = 0
        self.maxy = 0
        self.group_seen(None)
        self.listings = listings

    def group_seen(self, groupcode):
        if groupcode not in self.group_set:
            self.points_by_group[groupcode] = []
            self.groups.append(groupcode)
            self.group_set.add(groupcode)
            self.points_by_group[groupcode] = []

    def add_timestamp(self, timestamp):
        if self.timestamp is None:
            self.timestamp = timestamp
        else:
            self.timestamp = max(self.timestamp, timestamp)

    def add_timestamp_group(self, timestamp, groupcode):
        if groupcode not in self.timestamp_by_group:
            self.timestamp_by_group[groupcode] = timestamp
        else:
            self.timestamp_by_group[groupcode] = max(self.timestamp_by_group[groupcode], timestamp)

    def add_poly(self, level, upper, lower):
        poly = np.concatenate((upper, np.flipud(lower)))
        maxs = np.amax(poly, axis=0)
        self.polys.append(poly)
        self.maxx = max(self.maxx, maxs[0])
        self.maxy = max(self.maxy, maxs[1])

    def add_collection(self, groupcode, group_filename,
                       collectioncode, collection_filename, description):
        self.group_filenames[groupcode] = group_filename
        self.group_by_collection[collectioncode] = groupcode
        self.collection_filenames[collectioncode] = collection_filename
        self.collection_descr[collectioncode] = description

    def add_point(self, p, timestamp):
        assert p.collectioncode not in self.point_by_collection
        self.point_by_collection[p.collectioncode] = p
        groupcode = self.group_by_collection[p.collectioncode]
        self.group_seen(groupcode)
        self.points_by_group[groupcode].append(p)
        self.add_timestamp_group(timestamp, groupcode)

    def get_suffixes(self, p=None):
        if p is None:
            return ['pdf', 'svg']
        else:
            return ['svg']

    def get_pointname(self, suffix, groupcode, p=None, l=None):
        b = cleanlist([
            self.stat_filename,
            self.dataset_filename,
            None if groupcode is None else self.group_filenames[groupcode],
            None if p is None else self.collection_filenames[p.collectioncode],
            None if l is None else l,
        ])
        return '_'.join(b) + '.' + suffix

    def get_pointname_from_root(self, suffix, groupcode, p=None, l=None):
        return self.corpus_filename + "/" + self.get_pointname(suffix, groupcode, p, l)

    def get_pointname_relative(self, other, suffix, groupcode, collectioncode=None, l=None):
        changed = False
        if groupcode is not None and groupcode not in self.group_set:
            groupcode = None
            changed = True
        if groupcode is None and collectioncode is not None:
            collectioncode = None
            changed = True
        if collectioncode is not None and collectioncode not in self.point_by_collection:
            collectioncode = None
            changed = True
        if collectioncode is not None:
            exp = self.group_by_collection[collectioncode]
            if exp != groupcode:
                changed = True
                collectioncode = None
        if collectioncode is not None:
            p = self.point_by_collection[collectioncode]
        else:
            p = None
        name = self.get_pointname(suffix, groupcode, p, l)
        if self.corpuscode == other.corpuscode:
            full = name
        else:
            full = "../" + self.corpus_filename + "/" + name
        return full, changed

    def get_directory(self, suffix):
        return os.path.join(self.dirdict[suffix], self.corpus_filename)

    def get_filename(self, suffix, groupcode, p=None, l=None):
        return os.path.join(self.get_directory(suffix), self.get_pointname(suffix, groupcode, p, l))

    def get_directories(self):
        return [ self.get_directory(suffix) for suffix in self.get_suffixes() ]

    def get_filenames(self, groupcode, p=None):
        return [ self.get_filename(suffix, groupcode, p) for suffix in self.get_suffixes(p) ]

    def is_outdated(self, groupcode):
        for filename in self.get_filenames(groupcode):
            if not os.path.exists(filename):
                return True
            mtime = os.path.getmtime(filename)
            if mtime < self.timestamp:
                return True
            if groupcode in self.timestamp_by_group and mtime < self.timestamp_by_group[groupcode]:
                return True
        return False

    def get_outdated(self):
        outdated = []
        for groupcode in sorted(self.points_by_group.keys()):
            if self.is_outdated(groupcode):
                outdated.append(groupcode)
        return outdated

    def plot_group(self, matplotlib, groupcode):
        self.plot_group_points(matplotlib, groupcode, None)
        for point in self.points_by_group[groupcode]:
            self.plot_group_points(matplotlib, groupcode, point)

    def plot_group_points(self, matplotlib, groupcode, point):
        points = sorted(self.points_by_group[groupcode], key=lambda p: p.x, reverse=True)
        fig = matplotlib.pyplot.figure(
            figsize=(self.layout.width, self.layout.height),
            subplotpars=matplotlib.figure.SubplotParams(**self.layout.spp)
        )
        ax = fig.add_subplot(111)
        ax.set_autoscalex_on(False)
        ax.set_autoscaley_on(False)
        ax.set_xlim(lim(self.maxx))
        ax.set_ylim(lim(self.maxy))
        if self.layout.xbins != None:
            ax.locator_params(axis='x', nbins=self.layout.xbins)
        self.plot_polys(ax)
        self.plot_points(ax, points, groupcode, point)
        self.plot_labels(ax)
        for suffix in self.get_suffixes(point):
            if suffix == 'svg':
                suffix2 = 'tmp.svg'
            else:
                suffix2 = suffix
            filename = self.get_filename(suffix2, groupcode, point)
            fig.savefig(filename)
            if suffix == 'svg':
                for listing in self.listings:
                    target = self.get_filename(suffix, groupcode, point, listing)
                    self.add_svg_links(filename, target, points, groupcode, point, listing)
                os.remove(filename)
        matplotlib.pyplot.close(fig)

    def plot_polys(self, ax):
        for i, poly in enumerate(self.polys):
            f = i/(len(self.polys)-1.0)
            j = min(i, len(REGIONS)-1)
            fill = REGIONS[-(j+1)]
            ax.fill(poly[:,0], poly[:,1], fc=fill, ec=BLACK, linewidth=0.2, zorder=100 + f)

    def plot_points(self, ax, points, groupcode, point):
        placement = LabelPlacement(self.layout)
        for i, p in enumerate(points):
            scx, scy = float(p.x)/self.maxx, float(p.y)/self.maxy
            stx = scx + self.layout.xsep
            sty = placement.place(scy)
            zbase = 201.0 - p.pvalue
            if point is None:
                cp = p
            elif point == p:
                cp = self.layout.sel
                zbase += 100
            else:
                cp = self.layout.unsel
            if sty is not None:
                tx = stx * self.maxx
                ty = sty * self.maxy
                ax.plot(
                    [p.x, p.x, tx],
                    [p.y, ty,  ty],
                    color=cp.ec,
                    linewidth=cp.lw,
                    clip_on=False,
                    zorder=zbase,
                    gid='types_pl_%d' % i,
                )
            ax.plot(
                p.x, p.y,
                marker=p.marker,
                mec=cp.ec,
                mfc=cp.fc,
                mew=cp.lw,
                ms=p.ms,
                zorder=zbase + 2,
                gid='types_pm_%d' % i,
            )
            if sty is not None:
                ax.text(
                    tx, ty,
                    p.collectioncode,
                    color=cp.ec,
                    va='center',
                    bbox=dict(
                        boxstyle="round,pad=0.3",
                        fc=cp.fc,
                        ec=cp.ec,
                        linewidth=cp.lw,
                    ),
                    zorder=zbase + 1,
                    gid='types_pt_%d' % i,
                )

    def plot_labels(self, ax):
        ax.set_xlabel(ucfirst(self.xlabel), labelpad=10)
        ax.set_ylabel(ucfirst(self.ylabel), labelpad=15)

    def add_svg_links(self, filename, target, points, groupcode, point, listing):
        with open(filename) as f:
            svg = etree.parse(f)
        for i, p in enumerate(points):
            if point is not None and point == p:
                url = self.get_pointname('html', groupcode)
            else:
                url = self.get_pointname('html', groupcode, p, listing)
            title = self.collection_descr[p.collectioncode]
            if title is None:
                title = p.collectioncode
            for what in ['pl', 'pm', 'pt']:
                gid = 'types_%s_%d' % (what, i)
                path = ".//{http://www.w3.org/2000/svg}g[@id='%s']" % gid
                el = svg.find(path)
                if el is not None:
                    wrap_svg_link(el, url, title)
        with open(target, 'w') as f:
            svg.write(f)

    def generate_html(self, ac):
        for groupcode in sorted(self.points_by_group.keys()):
            ps = [None] + self.points_by_group[groupcode]
            for p in ps:
                for l in self.listings:
                    filename = self.get_filename('html', groupcode, p, l)
                    with open(filename, 'w') as f:
                        self.generate_html_one(f, groupcode, p, l, ac)

    def generate_html_one(self, f, groupcode, point, listing, ac):
        collectioncode = point.collectioncode if point is not None else None

        headblocks = []
        bodyblocks = []

        t = [ self.corpuscode, self.datasetcode, groupcode, collectioncode, self.statcode ]
        t = u" — ".join([a for a in t if a is not None])
        headblocks.append(E.title(t))
        headblocks.append(E.link(rel="stylesheet", href="../types.css", type="text/css"))

        def add_menu(title, cl, gl, xl, ll, labelhook, titlelink=None, groupby=None, stat=None):
            prev = []
            prevj = 0
            result = []
            count = len(cl) * len(gl) * len(xl) * len(ll)
            for c, g, x, l in itertools.product(cl, gl, xl, ll):
                addbreak = False
                label, desc = labelhook(c, g, x, l)
                selected = c == self and g is groupcode and x is collectioncode and l is listing
                if groupby is not None and count >= 5:
                    cur = label.split(groupby)
                    # A heuristic rule that tries to produce reasonable abbreviations
                    j = longest_common_prefix(prev, cur)
                    if j == len(prev):
                        j -= 1
                    if j < prevj:
                        j = 0
                    if 0 < prevj < j:
                        j = prevj
                    if j > 0:
                        label = u"…" + groupby.join(cur[j:])
                    if j == 0 and prevj > 0:
                        addbreak = True
                    prev = cur
                    prevj = j
                attr = dict()
                if desc is not None:
                    attr["title"] = desc
                if selected:
                    attr["class"] = "menuitem menusel"
                    e = E.span(label, **attr)
                else:
                    href, changed = c.get_pointname_relative(self, 'html', g, x, l)
                    attr["class"] = "menuitem menuother" if changed else "menuitem menusame"
                    e = E.a(label, href=href, **attr)
                if addbreak:
                    result.append(E.br())
                result.append(e)
            t = title + ":"
            if titlelink is None:
                t = E.span(t, **{"class": "menutitle"})
            else:
                t = E.a(t, href=titlelink, **{"class": "menutitle"})
            menu = E.p(*add_sep([t] + result, " "), **{"class": "menurow"})
            menublocks.append(menu)

        menublocks = []
        add_menu(
            "Corpus",
            ac.by_dataset_stat_fallback[(self.datasetcode, self.statcode)],
            [ groupcode ],
            [ collectioncode ],
            [ listing ],
            lambda c, g, x, l: (c.corpuscode, c.corpus_descr),
            titlelink="../index.html",
            groupby='-'
        )
        add_menu(
            "Dataset",
            ac.by_corpus_stat[(self.corpuscode, self.statcode)],
            [ groupcode ],
            [ collectioncode ],
            [ listing ],
            lambda c, g, x, l: (c.datasetcode, c.dataset_descr)
        )
        add_menu(
            "Points",
            [ self ],
            sorted(self.groups),
            [ collectioncode ],
            [ listing ],
            lambda c, g, x, l: ("none", None) if g is None else (g, None)
        )
        add_menu(
            "Axes",
            ac.by_corpus_dataset[(self.corpuscode, self.datasetcode)],
            [ groupcode ],
            [ collectioncode ],
            [ listing ],
            lambda c, g, x, l: (
                "%s/%s" % (c.ylabel, c.xlabel),
                "y = %s, x = %s" % (c.ylabel, c.xlabel)
            )
        )
        bodyblocks.append(E.div(*menublocks, **{"class": "menu"}))

        fig = E.p(E.object(
            data=self.get_pointname('svg', groupcode, point, listing),
            type="image/svg+xml",
            width=str(self.layout.width * self.layout.dpi),
            height=str(self.layout.height * self.layout.dpi),
        ), **{"class": "plot"})
        bodyblocks.append(fig)

        menublocks = []
        add_menu(
            "Collection",
            [ self ],
            [ groupcode ],
            [ None ] + [ p.collectioncode for p in self.points_by_group[groupcode] ],
            [ listing ],
            lambda c, g, x, l: ("none", None) if x is None else (x, self.collection_descr[x])
        )
        if collectioncode is not None and self.collection_descr[collectioncode] is not None:
            menublocks.append(E.p(self.collection_descr[collectioncode], **{"class": "menudesc"}))

        if len(self.listings) > 1:
            add_menu(
                "Show",
                [ self ],
                [ groupcode ],
                [ collectioncode ],
                self.listings,
                lambda c, g, x, l: (LISTING_LABEL[l], None)
            )

        bodyblocks.append(E.div(*menublocks, **{"class": "menu"}))

        if listing is None:
            stat = []
            if collectioncode is None:
                what = []
                for total, label in [
                    (self.xtotal, self.xlabel),
                    (self.ytotal, self.ylabel),
                ]:
                    if total is not None:
                        what.append('{} {}'.format(total, label))
                if len(what) > 0:
                    stat.append(E.p("This corpus contains {}.".format(
                        ' and '.join(what)
                    )))
                bodyblocks.append(E.div(*stat, **{"class": "stats"}))
            else:
                stat.append(E.p("This collection contains {} {} and {} {}.".format(
                    point.x, self.xlabel,
                    point.y, self.ylabel
                )))
                w = "at most" if point.side == "below" else "at least"
                if point.pvalue > 0.1:
                    ppvalue = "{:.1f}%".format(100 * point.pvalue)
                elif point.pvalue > 0.01:
                    ppvalue = "{:.2f}%".format(100 * point.pvalue)
                else:
                    ppvalue = "{:.3f}%".format(100 * point.pvalue)
                stat.append(E.p(
                    ("Only approx. " if point.pvalue < 0.1 else "Approx. "),
                    E.strong(ppvalue),
                    " of random collections with {} {} contain {} {} {}.".format(
                        point.x, self.xlabel, w, point.y, self.ylabel
                    )
                ))
                if point.pvalue > 0.1:
                    stat.append(E.p(
                        "This seems to be a fairly typical collection."
                    ))
                elif point.fdr < 0:
                    stat.append(E.p(
                        "This finding is probably not interesting: ",
                        "the false discovery rate is larger than {}".format(-point.fdr)
                    ))
                else:
                    stat.append(E.p(
                        "This finding is probably interesting: ",
                        "the false discovery rate is ",
                        E.strong("smaller than {}".format(point.fdr)),
                        "."
                    ))
            bodyblocks.append(E.div(*stat, **{"class": "stats"}))
        elif listing == 't':
            typelist = ac.get_typelist(self.corpuscode, self.datasetcode, collectioncode)
            bodyblocks.append(E.div(*typelist, **{"class": "listing"}))
        elif listing == 's':
            samplelist = ac.get_samplelist(self.corpuscode, self.datasetcode, collectioncode)
            bodyblocks.append(E.div(*samplelist, **{"class": "listing"}))
        else:
            assert False

        doc = E.html(E.head(*headblocks), E.body(*bodyblocks))
        write_html(f, doc)
<file_sep>DESCRIPTION = "Type and hapax accumulation curves"
AUTHOR = "<NAME>"
VERSION = "2014-05-15"
YEAR = "2014"
<file_sep>import os
import os.path
import subprocess
import sys

BIN_DIR = 'bin'
TMP_DIR = 'tmp'
LOGIN_FILE = 'loginfile'
PARTS=1

PARALLEL = 'parallel'
MINVERSION = '20120222'


def add_options(parser):
    parser.add_option('--bindir', metavar='DIRECTORY', dest='bindir',
                      help='where to find program files [default: %default]',
                      default=BIN_DIR)
    parser.add_option('--tmpdir', metavar='FILE', dest='tmpdir',
                      help='where to store temporary files [default: %default]',
                      default=TMP_DIR)
    parser.add_option('--local', dest='locally', action='store_true',
                      help='run locally',
                      default=False)
    parser.add_option('--loginfile', metavar='FILE', dest='loginfile',
                      help='SSH login file if you want to distribute computation on multiple machines, see "parallel --sshloginfile" for more information on the file format [default: %default]',
                      default=LOGIN_FILE)
    parser.add_option('--parts', metavar='N', dest='parts', type=int,
                      help='split each execution in how many independent parts [default: %default]',
                      default=PARTS)


class Parallel:
    def __init__(self, tool, bin, cmds, args):
        self.tool = tool
        self.bin = bin
        self.fullpath = os.path.join(args.bindir, bin)
        self.cmds = cmds
        self.locally = args.locally
        self.loginfile = args.loginfile

    def msg(self, msg):
        sys.stderr.write("%s: %s\n" % (self.tool, msg))

    def error(self, msg):
        sys.stderr.write("%s: error: %s\n" % (self.tool, msg))
        sys.exit(1)

    def run_serial(self):
        sys.stderr.write('%s (%d): ' % (self.bin, len(self.cmds)))
        for a in self.cmds:
            cmd = [ self.fullpath ] + [ str(i) for i in a ]
            # self.msg("run: %s" % ' '.join(cmd))
            process = subprocess.Popen(cmd)
            process.wait()
            if process.returncode != 0:
                if process.returncode > 0:
                    self.error("%s returned %d" % (self.bin, process.returncode))
                else:
                    self.error("%s received signal %d" % (self.bin, -process.returncode))
        sys.stderr.write('\n')

    def run_parallel(self):
        sys.stderr.write('%s [%d]: ' % (self.bin, len(self.cmds)))
        cwd = os.getcwd()
        cmd0 = [
            PARALLEL,
            '--ungroup',
            '--workdir', cwd,
            '--sshloginfile', self.loginfile,
            '--delim', '\\n',
            '--colsep', '\\t',
            '--trim', 'n',
            self.fullpath
        ]
        # self.msg("run: %s" % ' '.join(cmd0))
        process = subprocess.Popen(cmd0, stdin=subprocess.PIPE)
        for a in self.cmds:
            b = [ str(i) for i in a ]
            # self.msg("queue: %s" % ' '.join(b))
            process.stdin.write('\t'.join(b))
            process.stdin.write('\n')
        process.stdin.close()
        process.wait()
        sys.stderr.write('\n')
        if process.returncode != 0:
            if process.returncode > 0:
                self.error("%d child processes failed" % process.returncode)
            else:
                self.error("%s received signal %d" % (PARALLEL, -process.returncode))

    def parallel_ok(self):
        cmd = [ PARALLEL, '--minversion', MINVERSION ]
        try:
            process = subprocess.Popen(cmd, stdout=subprocess.PIPE)
        except:
            return False
        process.communicate()
        return process.returncode == 0

    def run(self):
        if self.locally:
            self.run_serial()
        elif not os.path.exists(self.loginfile):
            if self.loginfile != LOGIN_FILE:
                self.msg("login file %s missing, running locally" % self.loginfile)
            self.run_serial()
        elif not self.parallel_ok():
            self.msg("could not find GNU parallel version %s or later, running locally" % MINVERSION)
            self.run_serial()
        else:
            self.run_parallel()
<file_sep>import sys
import codecs
import cPickle
import multiprocessing
import optparse
import sqlite3
import lxml
import numpy
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot

assert sys.version_info >= (2,6)
print "OK"
