#!/usr/bin/env python
# vim:ts=4:sw=4:expandtab

"""experiments to improve werkzeug.routing.Rule sorting.

Instead of sort(cmp=match_compare) we construct a sort key
which gives equivalent sorting order.  This appears to run
slightly faster on small list of rules.  On larger lists
of rules perhaps the speed improvement will be more substantial.

It is not possible to construct a sort key which can substitute
for build_compare, because the method Rule.provides_defaults_for(other)
cannot be reduced to an autonomous value.
An attempt was made to devise a faster implementation of build_compare,
but it proved to be slower than the current build_compare().
"""

from itertools import izip

class Rule (object):
    def __init__(self, endpoint, arguments, defaults, greediness, weights):
        self.endpoint = endpoint
        self.arguments = arguments
        self.defaults = defaults
        self.greediness = greediness
        self._weights = weights

    def provides_defaults_for(self, rule):
        """Check if this rule has defaults for a given rule.

        :internal:
        """
        return self.defaults is not None and \
               self.endpoint == rule.endpoint and self != rule and \
               self.arguments == rule.arguments

    def build_compare(self, other):
        """Compare this object with another one for building.

        :internal:
        """
        if not other.arguments and self.arguments:
            return -1
        elif other.arguments and not self.arguments:
            return 1
        elif other.defaults is None and self.defaults is not None:
            return -1
        elif other.defaults is not None and self.defaults is None:
            return 1
        elif self.provides_defaults_for(other):
            return -1
        elif other.provides_defaults_for(self):
            return 1
        elif self.greediness > other.greediness:
            return -1
        elif self.greediness < other.greediness:
            return 1
        elif len(self.arguments) > len(other.arguments):
            return -1
        elif len(self.arguments) < len(other.arguments):
            return 1
        return -1


    def build_compare2(self, othr):
        # a higher score means sort order is less than
        # having args is lower order
        #self_score = ((self.arguments and 8) or 0) + \
        #             ((self.defaults is not None and 4) or 0) + \
        #             ((self.provides_defaults_for(othr) and 2) or 0)
        #othr_score = ((othr.arguments or 0) and 8) + \
        #             ((othr.defaults is not None or 0) and 4) + \
        #             ((othr.provides_defaults_for(self) or 0) and 2)
        self_score = 0
        if self.arguments:
            self_score += 8
        if self.defaults is not None:
            self_score += 4
        if self.provides_defaults_for(othr):
            self_score += 2

        othr_score = 0
        if othr.arguments:
            othr_score += 8
        if othr.defaults is not None:
            othr_score += 4
        if othr.provides_defaults_for(self):
            othr_score += 2

        r = cmp(othr_score, self_score) or \
            cmp(othr.greediness, self.greediness) or \
            cmp(len(othr.arguments), len(self.arguments))

        self.score = self_score
        othr.score = othr_score
        return r or -1


    def match_compare(self, other):
        """Compare this object with another one for matching.

        :internal:
        """
        for sw, ow in izip(self._weights, other._weights):
            if sw > ow:
                return -1
            elif sw < ow:
                return 1
        if len(self._weights) > len(other._weights):
            return -1
        if len(self._weights) < len(other._weights):
            return 1
        if not other.arguments and self.arguments:
            return 1
        elif other.arguments and not self.arguments:
            return -1
        elif other.defaults is None and self.defaults is not None:
            return 1
        elif other.defaults is not None and self.defaults is None:
            return -1
        elif self.greediness > other.greediness:
            return -1
        elif self.greediness < other.greediness:
            return 1
        elif len(self.arguments) > len(other.arguments):
            return 1
        elif len(self.arguments) < len(other.arguments):
            return -1
        return 1


def match_key(rule):
    # higher score means "less than" in sort order
    score = [ rule._weights,
              len(rule._weights),
              (rule.arguments and -1) or 0,
              (rule.defaults and -1) or 0,
              rule.greediness,
              0 - len(rule.arguments),
             ]
    #rule.score = score # for testing
    #print 'match_key', rule.endpoint, rule.score
    return score


def calc_score(rule):
    # higher score means "less than" in sort order
    rule.score = [ rule._weights,
                   len(rule._weights),
                   (rule.arguments and -1) or 0,
                   (rule.defaults and -1) or 0,
                   rule.greediness,
                   0 - len(rule.arguments),
                  ]


if __name__ == '__main__':
    rules = [
        Rule('noargs_nodefs_A', [], None, 0, [3, 2, 1]),
        Rule('noargs_nodefs_B', [], None, 0, [2, 1, 3]),
        Rule('args2_nodefs', ['a', 'b'], None, 0, []),
        Rule('args3_nodefs', ['a', 'b', 'c'], None, 0, []),
        Rule('noargs_defs2', [], ['x', 'y'], 0, [5, 3, 1]),
        Rule('noargs_defs3', [], ['x', 'y', 'z'], 0, [5, 3, 1]),
        Rule('args2_defs2', ['a', 'b'], ['x', 'y', 'z'], 0, [5, 3, 1]),
        Rule('greedy5', [], None, 5, [5, 3, 1]),
        Rule('greedy6', [], None, 6, [5, 3, 1]),
        Rule('providesdefs', [], None, 0, [5, 3, 1]),
    ]

    import time

    def test_build_compare():
        print 'sorted with build_compare()'
        rules_a = rules[:]
        rules_a.sort(lambda a, b: a.build_compare(b))
        for r in rules_a:
            print r.endpoint

        print
        print 'sorted with build_compare2()'
        rules_b = rules[:]
        rules_b.sort(lambda a, b: a.build_compare2(b))
        for r in rules_b:
            print r.endpoint, r.score

    def time_build_compare():
        # now that we know the results are equivalent, see if it's any faster
        rules_a = rules[:]
        a_start = time.time()
        for i in range(10000):
            rules_a.sort(lambda a, b: a.build_compare(b))
        a_elapsed = time.time() - a_start

        rules_b = rules[:]
        b_start = time.time()
        for i in range(10000):
            rules_b.sort(lambda a, b: a.build_compare2(b))
        b_elapsed = time.time() - b_start

        print 'build_compare() time: %s' % a_elapsed
        print 'build_compare2() time: %s' % b_elapsed

        # build_compare() time: 0.885596990585
        # build_compare2() time: 1.3441491127

    def test_match():
        for r in rules:
            calc_score(r)

        print 'sorted with match_compare()'
        rules_a = rules[:]
        rules_a.sort(lambda a, b: a.match_compare(b))
        for r in rules_a:
            print r.endpoint

        print
        rules_b = rules[:]
        print 'sorted with key=match_key'
        rules_b.sort(key=match_key, reverse=True)
        #print 'sorted with key=rule.score'
        #rules_b.sort(key=lambda a: a.score, reverse=True)
        for r in rules_b:
            print r.endpoint, r.score

    def time_match():
        # now that we know the results are equivalent, see if it's any faster
        rules_a = rules[:]
        a_start = time.time()
        for i in range(10000):
            rules_a.sort(lambda a, b: a.match_compare(b))
        a_elapsed = time.time() - a_start

        rules_b = rules[:]
        b_start = time.time()
        for i in range(10000):
            rules_b.sort(key=match_key, reverse=True)
            #rules_b.sort(key=lambda a: a.score, reverse=True)
        b_elapsed = time.time() - b_start

        print
        print 'match_compare() time: %s' % a_elapsed
        print 'match_key() time: %s' % b_elapsed


    test_match()
    time_match()
    # match_compare() time: 0.594125986099
    # match_key() time: 0.377090930939