def test_islice():
    mapping = [(val, pos) for pos, val in enumerate(string.ascii_lowercase)]
    temp = SortedDict(7, mapping)

    for start in range(30):
        for stop in range(30):
            assert list(temp.islice(start, stop)) == list(string.ascii_lowercase[start:stop])

 def setUpClass(self):
     self._vocab = SortedDict({
         '1950_1959': [('w1', 1.0), ('w2', 1.0)],
         '1951_1960': [('w3', 1.0), ('w4', 1.0)],
         '1952_1961': [('w5', 1.0), ('w6', 1.0)],
         '1953_1962': [('w7', 1.0), ('w8', 1.0)]
     })
     self._links = SortedDict({
         '1950_1959': {'w1': [('w1', 0.0), ('w2', 1.0)]},
         '1951_1960': {'w3': [('w3', 0.0), ('w4', 1.0)]},
         '1952_1961': {'w5': [('w5', 0.0), ('w6', 1.0)]},
         '1953_1962': {'w7': [('w7', 0.0), ('w8', 1.0)]}
     })
     self._aggVocab = SortedDict({
         '1954': [('w1', 1.0), ('w2', 1.0)],
         '1955': [('w3', 1.0), ('w4', 1.0)],
         '1956': [('w5', 1.0), ('w6', 1.0)],
         '1957': [('w7', 1.0), ('w8', 1.0)]
     })
     self._aggPeriods = SortedDict({
         '1954': ['1950_1959'],
         '1955': ['1951_1960'],
         '1956': ['1952_1961'],
         '1957': ['1953_1962']
     })

def test_irange():
    mapping = [(val, pos) for pos, val in enumerate(string.ascii_lowercase)]
    temp = SortedDict(7, mapping)
    for start in range(26):
        for stop in range(start + 1, 26):
            result = list(string.ascii_lowercase[start:stop])
            assert list(temp.irange(result[0], result[-1])) == result

def test_pickle():
    import pickle
    alpha = SortedDict(negate, zip(range(10000), range(10000)))
    alpha._reset(500)
    beta = pickle.loads(pickle.dumps(alpha))
    assert alpha == beta
    assert alpha._key == beta._key

 def __init__(self, my_book):
     super().__init__(None)
     # Save reference to the book
     self.my_book = my_book
     # Save reference to the metamanager
     self.metamgr = my_book.get_meta_manager()
     # Save reference to the edited document
     self.document = my_book.get_edit_model()
     # Save reference to a speller, which will be the default
     # at this point.
     self.speller = my_book.get_speller()
     # The vocabulary list as a sorted dict.
     self.vocab = SortedDict()
     # Key and Values views on the vocab list for indexing by table row.
     self.vocab_kview = self.vocab.keys()
     self.vocab_vview = self.vocab.values()
     # The count of available words based on the latest sort
     self.active_word_count = 0
     # The good- and bad-words sets and the scannos set.
     self.good_words = set()
     self.bad_words = set()
     self.scannos = set()
     # A dict of words that use an alt-dict tag. The key is a word and the
     # value is the alt-dict tag string.
     self.alt_tags = SortedDict()
     # Cached sort vectors, see get_sort_vector()
     self.sort_up_vectors = [None, None, None]
     self.sort_down_vectors = [None, None, None]
     self.sort_key_funcs = [None, None, None]
     # Register metadata readers and writers.
     self.metamgr.register(C.MD_GW, self.good_read, self.good_save)
     self.metamgr.register(C.MD_BW, self.bad_read, self.bad_save)
     self.metamgr.register(C.MD_SC, self.scanno_read, self.scanno_save)
     self.metamgr.register(C.MD_VL, self.word_read, self.word_save)

    def __init__(self, hs):
        self.server_name = hs.hostname
        self.clock = hs.get_clock()
        self.notifier = hs.get_notifier()
        self.is_mine_id = hs.is_mine_id

        self.presence_map = {}  # Pending presence map user_id -> UserPresenceState
        self.presence_changed = SortedDict()  # Stream position -> user_id

        self.keyed_edu = {}  # (destination, key) -> EDU
        self.keyed_edu_changed = SortedDict()  # stream position -> (destination, key)

        self.edus = SortedDict()  # stream position -> Edu

        self.device_messages = SortedDict()  # stream position -> destination

        self.pos = 1
        self.pos_time = SortedDict()

        # EVERYTHING IS SAD. In particular, python only makes new scopes when
        # we make a new function, so we need to make a new function so the inner
        # lambda binds to the queue rather than to the name of the queue which
        # changes. ARGH.
        def register(name, queue):
            LaterGauge("synapse_federation_send_queue_%s_size" % (queue_name,),
                       "", [], lambda: len(queue))

        for queue_name in [
            "presence_map", "presence_changed", "keyed_edu", "keyed_edu_changed",
            "edus", "device_messages", "pos_time",
        ]:
            register(queue_name, getattr(self, queue_name))

        self.clock.looping_call(self._clear_queue, 30 * 1000)

    def dist_player_stats(cls, stats, strength=False):
        """Order the stats to create distribution
        previously 'hand strength'"""
        # logger.info('distributing the player stats')
        dist = SortedDict(pos, {0: 'f'})
        p = 0
        for o in ['f', 's', 'l', 'k', 'c', 'b', 'r', 'a']:
            if o in stats:
                dist[p] = o
                p += max(0.01, stats[o])
                dist[p - 0.001] = o
        dist[1] = 'a'
        logger.info(f'dist = {dist}')

        logger.debug(f'strength? {strength}')
        if strength is False:
            return dist

        r = ''
        logger.debug(f'dist = {type(dist)}')
        for _ in range(20):
            p = _ * 5 / 100
            i_pos = dist.bisect_key_left(p)
            logger.debug(f'i_pos {i_pos} / {len(dist)}')
            k = dist.iloc[i_pos]
            v = dist[k]
            r += v.upper() if (1 - strength) <= p <= 1 else v.lower()
            logger.debug(f'bisected {v} from {k} at {r}%')
        logger.debug(f'dist_stats {r}')
        return r

def test_stress(repeat=1000):
    sdict = SortedDict((val, -val) for val in range(1000))

    for rpt in range(repeat):
        action = random.choice(actions)
        action(sdict)

        try:
            sdict._check()
        except AssertionError:
            print(action)
            raise

        start_len = len(sdict)

        while len(sdict) < 500:
            key = random.randrange(0, 2000)
            sdict[key] = -key

        while len(sdict) > 2000:
            key = random.randrange(0, 2000)
            if key in sdict:
                del sdict[key]

        if start_len != len(sdict):
            sdict._check()

def _adaptiveAggregation(V, n, yIntervals, weightF, param, freq):
    '''Apply adaptive aggregation algorithm to the given vocabulary.
    Algorithm 2 from paper.
    '''
    # Initialize returned parameters
    finalVocabs = SortedDict()
    periodGroups = SortedDict()

    # Select weighting function
    f = _selectWeightingFunction(weightF, param)

    # Iterate over time frames
    for t in _arrangeIntervals(V, yIntervals, freq):
        mu_t = getRangeMiddle(t[0], t[-1])
        V_prime = SortedDict({tx: V[tx] for tx in t})

        score = defaultdict(float)
        for years_v, words_v in V_prime.iteritems():
            mu_v = getRangeMiddle(years_v)
            fvt = f(mu_v, mu_t)
            for word, score_wv in words_v:
                score[word] += fvt * score_wv

        # Top n terms w sorted by score_w
        scoreList = [(k, v) for k, v in score.iteritems()]
        scoreList = sorted(scoreList, key=lambda pair: pair[1], reverse=True)
        topN = scoreList[:n]

        finalVocabs[str(int(mu_t))] = topN
        periodGroups[str(int(mu_t))] = t
    return finalVocabs, periodGroups

class PrioritizedIntensity(object):
    _MIN_VALUE = 0.005

    def __init__(self):
        self._values = SortedDict()

    def set(self, value, priority=100):
        value = float(value)
        if value < self._MIN_VALUE and priority in self._values:
            del self._values[priority]
        else:
            self._values[priority] = value

    def eval(self):
        if not self._values:
            return 0.0
        return self._values[self._values.iloc[- 1]]

    def top_priority(self):
        if not self._values:
            return 0
        return self._values.keys()[len(self._values) - 1]

    def reset(self):
        self._values.clear()

def signal_crosses(short_moving_averages, long_moving_averages):
    short_moving_averages = SortedDict(short_moving_averages)
    long_moving_averages = SortedDict(long_moving_averages)

    short_len = len(short_moving_averages.values())
    long_len  = len(long_moving_averages.values())

    if(short_len != long_len):
        print "[Error] signal_crosses: inputs must be same size"
        return {}

    signal_crosses = {}
    last_diff_dir = 0
    for date, short_average in short_moving_averages.iteritems():
        long_average = long_moving_averages[date]
        diff = short_average - long_average

        if(last_diff_dir == 0):
            signal_crosses[date] = HOLD
            if(diff != 0):
                last_diff_dir = sign(diff)
            continue

        if(sign(diff) != last_diff_dir):
            signal_crosses[date] = BUY if last_diff_dir < 0 else SELL
            last_diff_dir = -last_diff_dir
        else:
            signal_crosses[date] = HOLD

    return SortedDict(signal_crosses)

    def predict(self, X):
        y = np.zeros(len(X))
        for i,x in enumerate(X): # test points
            sd = SortedDict() # distance -> class
            for j,xt in enumerate(self.X): # training points
                d = np.linalg.norm(x - xt)
                # print d, sd
                if len(sd) < self.k:
                        sd[d] = self.y[j]
                else:
                    last = sd.viewkeys()[-1]
                    if d < last:
                        del sd[last]
                        sd[d] = self.y[j]
            # print "sd:", sd

            # vote
            votes = {}
            # print "viewvalues:", sd.viewvalues()
            for v in sd.viewvalues():
                # print "v:", v
                votes[v] = votes.get(v,0) + 1
            # print "votes:", votes, "true:", Ytest[i]
            max_votes = 0
            max_votes_class = -1
            for v,count in votes.iteritems():
                if count > max_votes:
                    max_votes = count
                    max_votes_class = v
            y[i] = max_votes_class
        return y

def test_copy():
    mapping = [(val, pos) for pos, val in enumerate(string.ascii_lowercase)]
    temp = SortedDict(mapping)
    dup = temp.copy()
    assert len(temp) == 26
    dup.clear()
    assert len(temp) == 0

def test_valuesview():
    if hexversion < 0x02070000: return

    mapping = [(val, pos) for pos, val in enumerate(string.ascii_lowercase)]
    temp = SortedDict(mapping[:13])
    values = get_valuesview(temp)

    assert len(values) == 13
    assert 0 in values
    assert list(values) == [pos for val, pos in mapping[:13]]
    assert values[0] == 0
    assert values[-3:] == [10, 11, 12]
    assert list(reversed(values)) == list(reversed(range(13)))
    assert values.index(5) == 5
    assert values.count(10) == 1

    temp.update(mapping[13:])

    assert len(values) == 26
    assert 25 in values
    assert list(values) == [pos for val, pos in mapping]

    that = dict(mapping)
    that_values = get_valuesview(that)

    values = get_valuesview(SortedDict(mapping[:2]))
    assert repr(values) == "SortedDict_values([0, 1])"

class PositionMapping:

    __slots__ = ('_pos', '_posmap')

    DUPLICATION_CHECK = True

    def __init__(self):
        self._pos = 0
        self._posmap = SortedDict()

    def items(self):
        return self._posmap.items()

    #
    # Properties
    #

    @property
    def pos(self):
        return self._pos

    @pos.setter
    def pos(self, v):
        self._pos = v

    #
    # Public methods
    #

    def add_mapping(self, start_pos, length, obj):
        # duplication check
        if self.DUPLICATION_CHECK:
            try:
                pre = next(self._posmap.irange(maximum=start_pos, reverse=True))
                if start_pos in self._posmap[pre]:
                    raise ValueError("New mapping is overlapping with an existing element.")
            except StopIteration:
                pass

        self._posmap[start_pos] = PositionMappingElement(start_pos, length, obj)

    def tick_pos(self, delta):
        self._pos += delta

    def get_node(self, pos):
        element = self.get_element(pos)
        if element is None:
            return None
        return element.obj

    def get_element(self, pos):
        try:
            pre = next(self._posmap.irange(maximum=pos, reverse=True))
        except StopIteration:
            return None

        element = self._posmap[pre]
        if pos in element:
            return element
        return None

 def get_sort_vector( self, col, order, key_func = None, filter_func = None ) :
     if filter_func : # is not None,
         # create a sort vector from scratch, filtered
         getter_func = self._make_key_getter( col )
         sorted_dict = SortedDict( key_func )
         for j in range( len( self.vocab ) ) :
             if filter_func( self.vocab_kview[j], self.vocab_vview[j][1] ) :
                 k = getter_func( j )
                 sorted_dict[ k ] = j
         vector = sorted_dict.values()
         if order != Qt.AscendingOrder :
             vector = [j for j in reversed( vector ) ]
     else : # no filter_func, try to reuse a cached vector
         vector = self.sort_up_vectors[ col ]
         if not vector or key_func is not self.sort_key_funcs[ col ] :
             # there is no ascending vector for this column, or there
             # is one but it was made with a different key_func.
             getter_func = self._make_key_getter( col )
             sorted_dict = SortedDict( key_func )
             for j in range( len( self.vocab ) ) :
                 k = getter_func( j )
                 sorted_dict[ k ] = j
             vector = self.sort_up_vectors[ col ] = sorted_dict.values()
             self.sort_key_funcs[ col ] = key_func
         if order != Qt.AscendingOrder :
             # what is wanted is a descending order vector, do we have one?
             if self.sort_down_vectors[ col ] is None :
                 # no, so create one from the asc. vector we now have
                 self.sort_down_vectors[ col ] = [ j for j in reversed( vector ) ]
             # yes we do (now)
             vector = self.sort_down_vectors[ col ]
     # one way or another, vector is a sort vector
     # note the actual word count available through that vector
     self.active_word_count = len(vector)
     return vector

def test_clear():
    mapping = [(val, pos) for pos, val in enumerate(string.ascii_lowercase)]
    temp = SortedDict(mapping)
    assert len(temp) == 26
    assert list(temp.items()) == mapping
    temp.clear()
    assert len(temp) == 0

 def sort( self, col, order ) :
     self.active_sort_vector = []
     if 0 == len(self.message_tuples) : # nothing to display
         return
     self.layoutAboutToBeChanged.emit([],QAbstractItemModel.VerticalSortHint)
     # treat columns 0 and 1 the same
     if col : # is 1 or 2
         col -= 1 # make it 0 or 1
     # we need an ascending vector in all cases.
     vector = self.sort_vectors_ascending[ col ]
     if vector is None : # we need to create the ascending vector
         sorted_dict = SortedDict()
         for j in range( len( self.message_tuples ) ) :
             line_col_msg_tuple = self.message_tuples[ j ]
             if col : # is 1, meaning sort on messages
                 key = line_col_msg_tuple[2]+line_col_msg_tuple[0]
             else : # col is 0, sort on line#+col#
                 key = line_col_msg_tuple[0]+line_col_msg_tuple[1]
             key += str(j) # ensure uniqueness
             sorted_dict[key] = j
             vector = self.sort_vectors_ascending[ col ] = sorted_dict.values()
     # vector now has an ascending sort vector which is cached..
     if order == Qt.DescendingOrder : # ..but we need the descending one
         if self.sort_vectors_descending[ col ] is None : # we need to make it
             self.sort_vectors_descending[ col ] = [ j for j in reversed( vector ) ]
         vector = self.sort_vectors_descending[ col ]
     self.active_sort_vector = vector
     self.layoutChanged.emit([],QAbstractItemModel.VerticalSortHint)

 def __init__(self):
     self.median = 0
     self.highMarker = TxGraph.WINDOW_SIZE
     self.lowMarker = 1
     self.txMap = SortedDict() #sorted by unix epoch (timestamp)
     self.edgeMap = SortedDict() #sorted by edge name
     self.nodeMap = SortedDict() #sorted by node name
     self.degreeList = SortedList() #sorted by degreeList

def test_update():
    mapping = [(val, pos) for pos, val in enumerate(string.ascii_lowercase)]
    temp = SortedDict()
    temp.update()
    temp.update(mapping)
    temp.update(dict(mapping))
    temp.update(mapping[5:7])
    assert list(temp.items()) == mapping