def test_delitem():
    random.seed(0)
    slt = SortedList(range(100), load=17)
    while len(slt) > 0:
        pos = random.randrange(len(slt))
        del slt[pos]
        slt._check()

 def score_of_a_vacated_people(self, universo, work='translations'):
     factor = math.sqrt(len(universo))
     scores = SortedList(load=round(factor))
     for (people, score) in self.__scores__().items():
         if people in universo:
             scores.add(TranslatorScore(people, score[work]))
     return scores.pop(0)

def test_delitem_slice():
    slt = SortedList(range(100))
    slt._reset(17)
    del slt[10:40:1]
    del slt[10:40:-1]
    del slt[10:40:2]
    del slt[10:40:-2]

def test_copy_copy():
    import copy
    alpha = SortedList(range(100), load=7)
    beta = copy.copy(alpha)
    alpha.add(100)
    assert len(alpha) == 101
    assert len(beta) == 100

def test_setitem_extended_slice():
    slt = SortedList(range(0, 1000, 10), load=17)
    lst = list(range(0, 1000, 10))
    lst[10:90:10] = range(105, 905, 100)
    slt[10:90:10] = range(105, 905, 100)
    assert slt == lst
    slt._check()

    def extract_collocations(self, metric_class):
        assert issubclass(metric_class, Metric)
        metric = metric_class()
        collocations = SortedList(key=lambda x: -x[0])
        
        unigram_counts = self.language_model.get_unigrams()
        bigram_counts = self.language_model.get_bigrams()

        for (first, last), freq_bigram in bigram_counts.items():

            if self.exclude_punctuation:
                if first in self.PUNCT or last in self.PUNCT:
                    continue

            if self.exclude_conj:
                if first in self.CONJ_RU or last in self.CONJ_RU:
                    continue

            if self.exclude_props:
                if first in self.PROPOSITIONS_RU or last in self.PROPOSITIONS_RU:
                    continue

            freq_first, freq_last = unigram_counts[first], unigram_counts[last]
            
            metric_val = metric.evaluate(freq_first, freq_last, freq_bigram,
                                         self.language_model.get_vocab_size())
            collocations.add((metric_val, freq_first,
                              freq_last, freq_bigram,
                              first, last))
            
        return collocations

def test_eq():
    this = SortedList(range(10), load=4)
    that = SortedList(range(20), load=4)
    assert not (this == that)
    that.clear()
    that.update(range(10))
    assert this == that

def iana_rir_gen_ip_list(user_rir_list):

    # generates a list of networks that can be blocked by RIR

    # we use a SortedList so that elements are inserted in order. This allows cidr_merge to work
    rir_slash_eight_list = SortedList()

    with open('iana') as iana_file:

        iana_csv = csv.reader(iana_file)

        for line in iana_csv:

            for rir in user_rir_list:

                # case in which the whois line from our csv contains the RIR
                if rir in line[3]:

                    network = line[0].lstrip('0')
                    rir_slash_eight_list.add(netaddr.IPNetwork(network))

                    # if we find a match, there is no reason to see if the other RIRs are on the same line
                    break

        # run cidr_merge to summarize
        rir_slash_eight_list = netaddr.cidr_merge(rir_slash_eight_list)

    return rir_slash_eight_list

    def predict(self, X):
        y = np.zeros(len(X))
        for i,x in enumerate(X): # test points
            sl = SortedList(load=self.k) # stores (distance, class) tuples
            for j,xt in enumerate(self.X): # training points
                diff = x - xt
                d = diff.dot(diff)
                if len(sl) < self.k:
                    # don't need to check, just add
                    sl.add( (d, self.y[j]) )
                else:
                    if d < sl[-1][0]:
                        del sl[-1]
                        sl.add( (d, self.y[j]) )
            # print "input:", x
            # print "sl:", sl

            # vote
            votes = {}
            for _, v in sl:
                # 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

class DijkstraFixedPoint:
	def __init__(self, automaton, initial_set, accepted_set):
		self.automaton = automaton
		self.set_to_visit = SortedList(initial_set,key= lambda d: -len(d))
		self.accepted_set = accepted_set

	def iter_fix_point_set(self,max_size=10):
		if len(self.set_to_visit)==0:
			raise StopIteration()

		F = self.set_to_visit.pop()

		nF = {k:[v] for k,v in F.items()}
		new_size_of_fp = len(nF)
		reach_accepted_set = False
		for u,lu in F.items():
			labelled_edges = self.automaton.get_labelled_successors(u)
			succ = labelled_edges[lu]
			for s in succ:
				if s in self.accepted_set:
					reach_accepted_set = True
				if (s not in nF) and (s not in self.accepted_set):
					nF[s] = list(self.automaton.get_successor_labels(s))
					new_size_of_fp = len(nF)
					if new_size_of_fp>max_size:
						return False,F


		newF = self.expand_successor_set(nF)
		if F in newF:
			newF.remove(F)
		self.set_to_visit.update(newF)
		accept_fix_point = (len(newF)==0) and reach_accepted_set
		return accept_fix_point,F


	def expand_successor_set(self,nF):
		sF = []
		# import operator
		# size = reduce(operator.mul, [len(v) for v in nF.values()], 1)
		for conf in itertools.product(*nF.values()):
			sF.append({k:v for k,v in zip(nF.keys(),conf)})
		return sF

	def __iter__(self):
		return self

	def next(self):
		return self.iter_fix_point_set()

	def next_fixed_point(self,max_size):
		fp_found = 0
		try:
			while fp_found==False:
					fp_found,fp = self.iter_fix_point_set(max_size)
					#print "#"*len(fp)
		except StopIteration:
			return False,None
		return fp_found,fp

def test_pickle():
    import pickle
    alpha = SortedList(range(10000))
    alpha._reset(500)
    beta = pickle.loads(pickle.dumps(alpha))
    assert alpha == beta
    assert alpha._load == 500
    assert beta._load == 1000

 def find_latest(self):
     sorted = SortedList()
     for i in self.bucket.list(prefix=self.db_name):
         parts = i.name.split('/')
         if len(parts) == 3:
             d = datetime.datetime.strptime(parts[1], "%m%d%Y").date()
             sorted.add(d)
     return sorted[len(sorted)-1].strftime('%m%d%Y')

def read_rirs(country_list, permit, rir_list=RIR_NAMES):

    # list containing our file objects
    file_list = []

    # we use a SortedList so that elements are inserted in order. This allows cidr_merge to work
    rir_ips = SortedList()

    # Open the files we downloaded earlier and store the file object
    for rir in rir_list:
        file_list.append(open(rir))

    for f in file_list:

        for line in f:

            curr_line = line.split('|')

            try:

                # we want only the ipv4 lines that are for a specific country
                # also only want countries that we are going to block
                if (curr_line[2] == "ipv4" and curr_line[1] != "*") and \
                    ((permit and curr_line[1] not in country_list) or
                     (not permit and curr_line[1] in country_list)):

                    country_code = curr_line[1]
                    network_id = curr_line[3]
                    wildcard = int(curr_line[4])-1

                    try:

                        # Add network to list, if the number of IPs was not a
                        # power of 2 (wildcard is not valid).
                        # AddrFormatError is thrown
                        rir_ips.add(netaddr.IPNetwork(network_id + "/" + str(netaddr.IPAddress(wildcard))))

                    # Handle case in where our mask is invalid by rounding DOWN
                    except netaddr.AddrFormatError:

                        print "rounded network " + network_id + " with " + str(wildcard) + \
                              " hosts up to nearest power of 2"
                        wildcard = next_power_of_2(wildcard) - 1
                        print wildcard + 1
                        rir_ips.add(netaddr.IPNetwork(network_id + "/" + str(netaddr.IPAddress(wildcard))))

            # IndexErrors only occur when parsing columns we don't need
            except IndexError:

                pass

        f.close()

    # cidr_merge takes our list of IPs and summarizes subnets where possible
    # this greatly decreases the number of ACL entries
    rir_ips = netaddr.cidr_merge(rir_ips)

    return rir_ips

class InMemoryBackend(object):
    """
    The backend that keeps the results in the memory.
    """
    def __init__(self, *args, **kwargs):
        def get_timestamp(result):
            return timestamp_parser.parse(result['timestamp'])

        self._results = dict()
        self._sorted = SortedList(key=get_timestamp)

    def disconnect(self):
        return succeed(None)

    def store(self, result):
        """
        Store a single benchmarking result and return its identifier.

        :param dict result: The result in the JSON compatible format.
        :return: A Deferred that produces an identifier for the stored
            result.
        """
        id = uuid4().hex
        self._results[id] = result
        self._sorted.add(result)
        return succeed(id)

    def retrieve(self, id):
        """
        Retrive a result by the given identifier.
        """
        try:
            return succeed(self._results[id])
        except KeyError:
            return fail(ResultNotFound(id))

    def query(self, filter, limit=None):
        """
        Return matching results.
        """
        matching = []
        for result in reversed(self._sorted):
            if len(matching) == limit:
                break
            if filter.viewitems() <= result.viewitems():
                matching.append(result)
        return succeed(matching)

    def delete(self, id):
        """
        Delete a result by the given identifier.
        """
        try:
            result = self._results.pop(id)
            self._sorted.remove(result)
            return succeed(None)
        except KeyError:
            return fail(ResultNotFound(id))

 def dir(self, file_pattern):
     attrs = self.sftp.listdir_attr(self.remote_dir)
     filtered = SortedList()
     for attr in attrs:
         if hasattr(attr, "filename"):
             filename = attr.filename
             if re.match(file_pattern, filename):
                 remote_file = RemoteFile(filename, attr.st_mtime)
                 filtered.add(remote_file)
     return filtered

def test_op_add():
    this = SortedList(range(10))
    this._reset(4)
    assert (this + this + this) == (this * 3)

    that = SortedList(range(10))
    that._reset(4)
    that += that
    that += that
    assert that == (this * 4)

def test_setitem():
    random.seed(0)
    slt = SortedList(range(0, 100, 10), load=4)

    values = list(enumerate(range(5, 105, 10)))
    random.shuffle(values)
    for pos, val in values:
        slt[pos] = val

    slt[-2] = 85
    slt._check()

def test_bisect_right():
    slt = SortedList()
    assert slt.bisect_right(10) == 0
    slt = SortedList(range(100), load=17)
    slt.update(range(100))
    slt._check()
    assert slt.bisect_right(10) == 22
    assert slt.bisect_right(200) == 200

def test_bisect_left():
    slt = SortedList()
    assert slt.bisect_left(0) == 0
    slt = SortedList(range(100), load=17)
    slt.update(range(100))
    slt._check()
    assert slt.bisect_left(50) == 100
    assert slt.bisect_left(200) == 200

def arrayRDP(arr, epsilon=0.0, n=None):
    """
    This is a slightly modified version of the _aRDP function, that accepts
    as arguments the tolerance in the distance and the maximum number of points
    the algorithm can select.
    **Note:** The results of this algoritm should be identical to the arrayRDP
    function if the *n* parameter is not specified. In that case, the
    performance is slightly worse, although the asymptotic complexity is the
    same. For this reason, this function internally delegates the solution in
    that function if the *n* parameter is missing.

    Parameters
    ----------
    arr:
        Array of values of consecutive points.
    epsilon:
        Maximum difference allowed in the simplification process.
    n:
        Maximum number of points of the resulted simplificated array.

    Returns
    -------
    out:
        Array of indices of the selected points.
    """
    if n is None:
        return _aRDP(arr, epsilon)
    if epsilon <= 0.0:
        raise ValueError('Epsilon must be > 0.0')
    n = n or len(arr)
    if n < 3:
        return arr
    fragments = SortedDict()
    #We store the distances as negative values due to the default order of
    #sorteddict
    dist, idx = max_vdist(arr, 0, len(arr) - 1)
    fragments[(-dist, idx)] = (0, len(arr) - 1)
    while len(fragments) < n-1:
        (dist, idx), (first, last) = fragments.popitem(last=False)
        if -dist <= epsilon:
            #We have to put again the last item to prevent loss
            fragments[(dist, idx)] = (first, last)
            break
        else:
            #We have to break the fragment in the selected index
            dist, newidx = max_vdist(arr, first, idx)
            fragments[(-dist, newidx)] = (first, idx)
            dist, newidx = max_vdist(arr, idx, last)
            fragments[(-dist, newidx)] = (idx, last)
    #Now we have to get all the indices in the keys of the fragments in order.
    result = SortedList(i[0] for i in fragments.itervalues())
    result.add(len(arr) - 1)
    return np.array(result)