#!/usr/bin/python

# tz_chooser.py
#       --copyright--                   Copyright 2010 (C) Tranzoa, Co. All rights reserved.    Warranty: You're free and on your own here. This code is not necessarily up-to-date or of public quality.
#       --url--                         http://www.tranzoa.net/tzpython/
#       --email--                       pycode is the name to send to. tranzoa.com is the place to send to.
#       --bodstamps--
#       December 25, 2010       bar
#       December 26, 2010       bar
#       November 29, 2011       bar     pyflake cleanup
#       May 27, 2012            bar     doxygen namespace
#       November 7, 2017        bar     maxint->maxsize
#       --eodstamps--
##      \file
#       \namespace              tzpython.tz_chooser
#
#
#       This thing incrementally sorts an array of things, telling the owner which things don't have information for comparison.
#       The owner tells the array of things how to compare each pair of things given to the owner.
#       The end result is an array of things roughly in order.
#       As time goes on, and the owner has told the array pair-comparisons, the things will be better ordered.
#
#       TODO:
#           pick pairs that will yield the biggest tree if they were decided - choices that when resolved will combine chains
#                find ends of chains and see about linking them - low end to high
#           pick pairs with far-apart names?
#
#

import  random
import  sys

import  tzlib



CHUNK_SIZE          = sys.maxsize   # do the choices in groups of this many building up to when we can sort them all

EXTEND_LEARNING     = False         # when we learn, we teach others that seem like they could know, too. Cuts down on the number of sorts needed to home in on a good distribution, but eats CPU.
EXTEND_COMPARE      = False         # can we look around for choices to link, given they have unambiguous links between them through other choices?


AGE                 = 0.5           # when aging, take out the older of this multiple of the memory


class   a_cmp(object) :
    def __init__(me, c, r) :
        me.c    = c
        me.r    = -1 if r < 0 else 1 if r > 0 else 0
    #   a_cmp


class   a_choice(object) :
    """
        This a one of the things to be ordered.
        'data' is anything you want it to be.
        The 'name' must be unique among all the choices known to the chooser.
    """

    def __init__(me, name, data) :
        me.name         = name
        me.data         = data

        me.cmps         = {}                                    # indexed by other a_choices we've been compared to. value of the a_cmp comparison (!= None)
        me.zero_order_total()
        me.ci           = 0                                     # for owner to track when we were last chosen
        me.si           = 0

        me.found_cnt    = 0


    def get_button_text(me) :
        return(me.name)


    def start_sort(me) :
        me.si   = random.randint(0, sys.maxsize / 2)


    def knows(me, om) :
        return((om.name in me.cmps) or (me.name in om.cmps))


    def cmp(me, om) :
        if  om.name in me.cmps :
            ca  = me.cmps[om.name]
            return(ca[me.si % len(ca)].r)
        return(None)                                    # we've never compared ourself to this other a_choice


    def _find_cmp(me, om, r, cd) :
        for c in me.cmps.get(om.name, []) :
            if  c.r == r :
                return(True)
            pass

        for ca in me.cmps.values() :
            c   = ca[0]
            if  c.c.name not in cd :
                for c in ca :
                    if  (c.r == r)      :
                        cd[c.c.name]    = True
                        if  c.c._find_cmp(om, r, cd) :
                            return(True)

                        break                               # go on to the next link
                    pass
                pass
            pass

        return(False)


    def find_cmp(me, om) :
        if  not me.knows(om) :
            m       = me._find_cmp(om, -1, { me.name : True, om.name : True, })
            p       = me._find_cmp(om,  1, { me.name : True, om.name : True, })
            if  not (m and p) :
                if  me._find_cmp(  om,  0, { me.name : True, om.name : True, }) :
                    if  not (m or p) :
                        return(0)

                    pass
                else :
                    return(-1 if m else 1 if p else None)

                pass
            pass

        return(None)


    def _find_tweens(me, fnd, path, om, r, cd) :
        """ Fill 'fnd' with key:choice name    value:choice     The choices are on between me and om on paths only of acceptable type 'r'. """

        longest = 0
        if  me.name == om.name :
            for c in path :
                fnd[c.name] = c
            pass
        else    :
            path.append(me)
            for n, ca in me.cmps.items() :
                if  n not in cd :
                    if  n != om.name :
                        cd[n]  = True
                    for c in ca :
                        if  c.r * r > 0 if r else not c.r :
                            longest = max(longest, c.c._find_tweens(fnd, path, om, r, cd))
                            break                               # go on to the next link
                        pass
                    pass
                pass
            path.pop()

        return(longest)

    def find_tweens(me, om, r) :
        fnd = {}
        cd  = { me.name : True, }
        me._find_tweens(fnd, [], om, r, cd)
        if  me.name in fnd :
            del(fnd[me.name])
        return(fnd.values())


    def _branch_out(me, fnd, r, cd) :
        """ Fill 'fnd' with key:choice name    value:choice     The choices are on the ends of paths only of acceptable type 'r'. """

        for n, ca in me.cmps.items() :
            if  n not in cd :
                cd[n]  = True
                for c in ca :
                    if  c.r * r > 0 if r else not c.r :
                        fnd[n] = c.c
                        c.c._branch_out(fnd, r, cd)
                        break                               # go on to the next link
                    pass
                pass
            pass
        pass

    def find_branches(me) :
        """
            Find any other choices that, by implication, we can link to.

            3 lists are returned:
                A list of choices that we have a negative relation to - that is, the choices that are better than us.
                A list of choices that are equal to us.
                A list of choices we are better than.

            The caller can call a_chooser.learn_only_if_new(), passing these lists and their relationships (-1, 0, 1).
        """

        m   = {}
        z   = {}
        p   = {}

        me._branch_out(m, -1, { me.name : True, })
        me._branch_out(z,  0, { me.name : True, })
        me._branch_out(p,  1, { me.name : True, })

        mk  = m.keys()
        pk  = p.keys()
        zk  = z.keys()
        for n in mk :
            if  n in p : del(p[n])
            if  n in z : del(z[n])
        for n in pk :
            if  n in m : del(m[n])
            if  n in z : del(z[n])
        for n in zk :
            if  n in m : del(m[n])
            if  n in p : del(p[n])

        return(m.keys(), z.keys(), p.keys())                # give the tell the caller all the learnable names (so he can add them under lock protection - while making sure that they don't have refs to us or vice versa)


    def _extend_learning(me, om, r, cd) :
        for ca in me.cmps.values() :
            c   = ca[0]
            if  (om.name not in c.c.cmps) and (c.c.name not in cd) :
                ambig   = False
                for c in ca :
                    if  (c.r != r) and (c.r != 0) :
                        ambig   = True                          # note: on the other hand, we could just zap things, or we could allow our learning when the majority of the links are the rite direction
                        break
                    pass
                if  not ambig :
                    for c in ca :
                        if  (c.r == r) or (c.r == 0) :
                            c.c.cmps[om.name]   = []
                            c.c.cmps[om.name].append(a_cmp(om, -r))
                            print "@@@@ xlearned", c.c.name, om.name, -r
                            cd[c.c.name]        = True
                            c.c._extend_learning(om, r, cd)
                            break                               # did the direction we search down, so we're done with this array of connections (all elements in the array have the same c.c)
                        pass
                    pass
                pass
            pass
        pass


    def extend_learning(me, om,  r) :
        me._extend_learning(om, -r, { me.name : True, om.name : True })


    def learn(me, om, r, extend = True) :
        if  r != None :
            me.cmps[om.name]    = me.cmps.get(om.name, [])
            me.cmps[om.name].append(a_cmp(om, r))

            if  extend and EXTEND_LEARNING :
                me.extend_learning(om, r)
            return(True)
        return(False)

    def learn_only_if_new(me, om, r) :
        if  r != None :
            if  om.name not in me.cmps :
                me.cmps[om.name]    = [ a_cmp(om, r), ]
                return(True)
            pass
        return(False)

    def zero_order_total(me) :
        me.otot = 0
        me.ocnt = 0

    def learn_order(me, o) :
        me.otot += o
        me.ocnt += 1

    def order(me) :
        return( me.otot / float(me.ocnt) if me.ocnt else 0)

    def age(me, n   = None) :
        if  n      != None  :
            n       = float(min(1.0, max(0, n)))
        t           = 0
        for name in me.cmps.keys() :
            ca      = me.cmps[name]
            if  (n != None) and len(ca) :
                ln  = len([ nn for nn in xrange(len(ca)) if random.random() >= n ])
                if  ln  :
                    ca  = ca[-ln:]
                else    :
                    ca  = []
                if  len(ca) :
                    me.cmps[name]   = ca
                else    :
                    del(me.cmps[name])
                pass
            t      += len(ca)
        return(t)

    #   a_choice



class   a_chooser(object) :
    """
        This is an array of choices.
        At any time, you can get the best guess of the order they should be in by calling sort_as_best_we_can().
        But, until you've called and handled the results of find_pair() a lot, the order will be pretty random.
        You call find_pair() and it returns a tuple telling you whether it has successfully sorted the choices (twice) without needing a pair comparison value.
            It also tells you a pair of choices that it would like you to provide a comparison between.
            You call learn() passing the two choices and the comparison value (an int, like the python cmp() function would give for them).
            That cmp() value does not need to be the same each time you provide it.
                (Each time a_chooser is sorted, it uses just one of the results you have returned at one time or another for each pair of choices.)
    """

    def __init__(me, chunk_size = CHUNK_SIZE, *kargs, **kwargs) :
        super(a_chooser, me).__init__(*kargs, **kwargs)

        me.set_chunk_size(chunk_size)
        me.known_cnt    = 0
        me.hurry_up     = 0
        me.next_abs     = []
        me.all_done     = False
        me.learn_cnt    = 0
        me.found_cnt    = 0
        me.learned      = {}
        me.choices      = []


    def __len__(me)     :
        return(len(me.choices))

    def __iter__(me)    :
        return(iter(me.choices))

    def __getitem__(me, ky) :
        return(me.choices.__getitem__(ky))
    def __setitem__(me, ky, v) :
        r               = me.choices.__setitem__(ky, v)
        me.all_done     = False
        return(r)
    def __delitem__(me, ky) :
        r               = me.choices.__delitem__(ky)
        me.all_done     = False
        return(r)

    def __getslice__(me, i, j) :
        return(me.choices.__getslice__(i, j))

    def __setslice__(me, i, j, seq) :
        r               = me.choices.__setslice__(i, j, seq)
        me.all_done     = False
        return(r)

    def __delslice__(me, i, j) :
        r               = me.choices.__delslice__(i, j)
        me.all_done     = False
        return(r)

    def __add__(me, om) :
        if  isinstance(om, a_chooser) :
            me.choices += om.choices
        else            :
            me.choices += om
        me.all_done     = False
        return(me)

    def append(me, c)   :
        me.choices.append(c)
        me.all_done     = False


    def choices_cmp(me, a, b) :
        if  a.name     <= b.name :                      # so we have a stable sort
            neg         = False
            ( aa, bb )  = ( a, b )
        else            :
            neg         = True
            ( bb, aa )  = ( a, b )

        r               = aa.cmp(bb)
        if  r          == None :
            me.next_abs.append([ a, b ])
            r           = 0

        if  neg :
            r   = -r

        return(r)


    def set_chunk_size(me, chunk_size = None) :
        ov  = getattr(me, 'chunk_size', 16)
        if  chunk_size != None  :
            me.chunk_size       = 16 if chunk_size <= 1 else chunk_size
        return(ov)


    def set_hurry_up(me, v) :
        ov      = me.hurry_up
        if  v  != None :
            me.hurry_up = v
        return(ov)



    def find_best_ab(me) :
        me.alldone  = False

        random.shuffle(me.next_abs)                             # so that equal ones will come in different orders each time
        i           = tzlib.min_index([ max(ab[0].found_cnt, ab[1].found_cnt) for ab in me.next_abs ])
        ab          = me.next_abs[i]

        # print "@@@@", ab[0].found_cnt, ab[1].found_cnt, me.found_cnt, "\n  " + "\n  ".join([ str([ba[0].found_cnt, ba[1].found_cnt ]) for ba in me.next_abs ])

        ab[0].found_cnt = me.found_cnt
        ab[1].found_cnt = me.found_cnt

        return(False, ab[0], ab[1])


    def find_pair(me) :
        """ Return:
                bool whether we managed to do a full sort without any ambiguity (not necessarily implying that all things are known in relation to all other things.
                two items whose comparison we don't know or that seem to be pretty ambiguously rated.
        """

        if  len(me) < 2 :
            me.alldone  = False
            return(True, None, None)

        me.found_cnt   += 1

        if  me.known_cnt < len(me) :
            bi          = max(0, min(len(me) - me.chunk_size, me.known_cnt))
            ei          = min(len(me), bi + me.chunk_size)
            me.all_done = False
        else            :
            bi          = 0
            ei          = len(me)

        me.next_abs     = []
        if  (bi != 0) or (ei != len(me)) :
            me.all_done = False
            a           = list(me.choices[bi:ei])
            for c in me.choices[bi:ei] : c.start_sort()
            a.sort(me.choices_cmp)
            for ci, c in enumerate(a) : c.learn_order(ci * len(me) / float(ei - bi))
            me.choices[bi:ei]   = a
        if  not len(me.next_abs)  :
            random.shuffle(me.choices)
            for c in me.choices :   c.start_sort()
            me.choices.sort(me.choices_cmp)
            for ci, c in enumerate(me.choices) : c.learn_order(ci)

        if  len(me.next_abs) :
            return(me.find_best_ab())

        if  me.known_cnt    < ei :
            me.known_cnt    = ei
            me.alldone      = False
            return(me.find_pair())                  # find a pair in the next chunk or the whole thing

        if  bi  != 0        :
            me.alldone      = False
            return(me.find_pair())                  # find a pair in the whole thing

        nd1 = tzlib.make_index_dictionary([ c.name for c in me.choices ])

        random.shuffle(me.choices)
        for c in me.choices :   c.start_sort()
        me.choices.sort(me.choices_cmp)

        if  len(me.next_abs) :
            return(me.find_best_ab())

        if  not me.all_done :
            for c in me.choices :
                c.zero_order_total()
            me.all_done = True
        for ci, c in enumerate(me.choices) : c.learn_order(ci)

        nd2  = tzlib.make_index_dictionary([ c.name for c in me.choices ])

        da  = [ [ abs(nd1[n] - nd2[n]) * (me.found_cnt - me.choices[nd2[n]].found_cnt + 4), n ] for n in nd1.keys() ]       # find how far away from itself in the two sorts each item is
        da.sort()

        a       = me.choices[nd2[da[-2][1]]]
        b       = me.choices[nd2[da[-1][1]]]
        a.found_cnt = me.found_cnt
        b.found_cnt = me.found_cnt
        return(True, a, b)                                                                          # return the two items that sorted most differently in array index scaled by how recently they've been chosen


    def make_old(me, a = None, b = None) :
        me.found_cnt   += 1
        if  a           :
            a.found_cnt = me.found_cnt
        if  b           :
            b.found_cnt = me.found_cnt
        pass


    def make_choice_dict(me) :
        cd  = {}
        for cc in me.choices :
            cd[cc.name]  = cc
        return(cd)


    def learn(me, a, b, r, extend = True) :
        me.all_done = False
        if  r != None :
            a.learn(b,  r, extend = extend)
            b.learn(a, -r, extend = extend)
            me.learn_cnt       += 1
            me.put_choice_to_extend_learning(a)
            me.put_choice_to_extend_learning(b)
            return(True)
        return(False)


    def _learn_only_if_new(me, c, names, r, cd) :
        lnames  = []
        for n in names :
            if  n in cd :
                om  = cd[n]
                if  c.learn_only_if_new(om,  r) :
                    me.put_choice_to_extend_learning(om)
                    lnames.append(n)
                    if  not om.learn_only_if_new(c, -r) :
                        raise ValueError("%s %s" % ( c.name, om.name ) )
                    pass
                pass
            pass
        return(lnames)

    def learn_only_if_new(me, c, m, z, p) :
        cd  = me.make_choice_dict()
        m   = me._learn_only_if_new(c, m, -1, cd)
        z   = me._learn_only_if_new(c, z,  0, cd)
        p   = me._learn_only_if_new(c, p,  1, cd)
        return(m, z, p)

    def queue_newly_learned(me, m, z, p) :
        """ Put the choices in the return value from learn_only_if_new() to the learning queue. """

        cd          = me.make_choice_dict()
        for n in m  :   me.put_choice_to_extend_learning(cd[n].find_tweens(cd[n], -1))
        for n in z  :   me.put_choice_to_extend_learning(cd[n].find_tweens(cd[n],  0))
        for n in p  :   me.put_choice_to_extend_learning(cd[n].find_tweens(cd[n],  1))


    def get_choice_to_extend_learning(me) :
        if  len(me.learned) :
            n   = random.choice(me.learned.keys())
            c   = me.learned[n]
            del(me.learned[n])
            return(c)
        return(None)

    def put_choice_to_extend_learning(me, c_or_ca) :
        if  not isinstance(c_or_ca, ( tuple, list )) :
            c_or_ca             = [ c_or_ca ]
        for c in c_or_ca        :
            me.learned[c.name]  = c
        pass


    def find_tweens(me, cnm, onm, r) :
        ca  = []
        cd  = me.make_choice_dict()
        if  (cnm in cd) and (onm in cd) :
            ca  = cd[cnm].find_tweens(cd[onm], r)
        return(ca)


    def find_distant_pair(me) :
        if  (not me.all_done) and (len(me.choices) >= 8) :
            ( aa, bb )  = random.sample(me.choices, 2)
            r           = aa.find_cmp(bb)                   # search aa's tree for a path to bb
            if  (not me.hurry_up) and (r != None) :
                return(r, aa, bb)

            pass

        return(None, None, None)



    def sort_as_best_we_can(me) :
        ( r, a, b ) = me.find_pair()
        me.choices.sort(lambda a, b : cmp(a.order(), b.order()))
        return(r)


    def relearn_order(me, cnt = None) :
        r   = True
        cnt = cnt if cnt > 0 else 10
        for c in me.choices :
            c.zero_order_total()
        for i in xrange(cnt) :
            random.shuffle(me.choices)
            me.next_abs = []
            for c in me.choices :   c.start_sort()
            me.choices.sort(me.choices_cmp)
            if  len(me.next_abs) :
                r   = False
            for ci, c in enumerate(me.choices) : c.learn_order(ci)

        r  &= me.sort_as_best_we_can()

        return(r)


    def age(me, n = None) :
        t       = 0
        for c in me.choices :
            t  += c.age(n)
        if  n  != None :
            me.all_done = False
        return(t)



    #   a_chooser



if __name__ == '__main__' :
    t   = tzlib.elapsed_time()

    how_many        = 65
    if  len(sys.argv) > 1 :
        how_many    = int(sys.argv[1])
    until_relearn   = False

    me  = a_chooser()
    me += [ a_choice(str(n), "") for n in range(how_many) ]
    random.shuffle(me)
    print [ n.name for n in me ]
    cnt = 0
    while True :
        ( r, a, b ) = me.find_pair()
        if  EXTEND_LEARNING and r :
            break
        if  r :
            print "Trying"
            if  (until_relearn and me.relearn_order()) or ((not until_relearn) and me.find_pair()[0]) :
                break
            pass


        if  not r :
            if  b.name in a.cmps :  print "BUG!", b.name, a.name
            if  a.name in b.cmps :  print "BUG!", a.name, b.name
            # print a.name, b.name
            rr  = int(a.name) - int(b.name)
            # rr  = int(sys.stdin.readline().strip())
            me.learn(a, b, rr)

        if  not EXTEND_LEARNING :
            cds = {}
            while True :
                c   = me.get_choice_to_extend_learning()
                if  not c : break
                if  c not in cds :
                    cds[c]      = True
                    ( m, z, p ) = c.find_branches()
                    if  m or z or p :
                        # if  m   :   print "learning", c.name, m, -1
                        # if  z   :   print "learning", c.name, z,  0
                        # if  p   :   print "learning", c.name, p,  1
                        ( m, z, p ) = me.learn_only_if_new(c, m, z, p)
                        me.queue_newly_learned(m, z, p)
                        # print "learned", c.name, m, z, p
                    pass
                pass
            pass
        cnt    += 1

    es  = ""
    pn  = -1
    for c in me :
        i   = int(c.name)
        if  i <= pn :
            es += "BUG not in order %s %d\n" % ( c.name, pn )
        pn  = i

    t   = tzlib.elapsed_time()
    print "results", cnt, me.age(), r, "\n  " + "\n  ".join([ "%5s %7s %5s" % ( c.name, str(round(c.order(), 1)), str(c.ocnt) ) for c in me ])     # note: they may not be in order because all comparisons between all items aren't necessarily known
    r   = me.sort_as_best_we_can()
    print round(tzlib.elapsed_time() - t, 2)
    r   = me.relearn_order()
    print "relearn", cnt, me.age(), r, "\n  " + "\n  ".join([ "%5s %7s %5s" % ( c.name, str(round(c.order(), 1)), str(c.ocnt) ) for c in me ])     # note: they may not be in order because all comparisons between all items aren't necessarily known
    print cnt, me.age()

    if  es :
        print es

    for c in me :
        for ca in c.cmps.values() :
            if  len(ca) > 1 :
                print "BUG ca len > 1", c.name, [ str([cc.c.name, cc.r ]) for cc in ca ]
            pass
        pass
    pass

    for c in me :
        for ca in c.cmps.values() :
            om  = ca[0].c
            if  c.name not in om.cmps :
                print "BUG unreciprical", c.name, om.name
            elif ca[0].r != -om.cmps[c.name][0].r :
                print "BUG disagree", c.name, om.name, ca[0].r, om.cmps[c.name][0].r
            pass
        pass
    pass


#
#
#
# eof
