def test_eq():
    this = SortedListWithKey(range(10), load=4, key=modulo, value_orderable=False)
    that = SortedListWithKey(range(20), load=4, key=modulo, value_orderable=False)
    assert not (this == that)
    that.clear()
    that.update(range(10))
    assert this == that

def _characterize_signal(beg, end):
    """
    Characterizes the available signal in a specific time interval.

    Parameters
    ----------
    beg:
        Starting time point of the interval.
    end:
        Last time point of the interval.

    Returns
    -------
    out:
        sortedlist with one entry by lead. Each entry is a 5-size tuple with
        the lead, the signal samples, the relevant points to represent the
        samples, the baseline level estimation for the fragment, and the
        quality of the fragment in that lead.
    """
    siginfo = SortedListWithKey(key=lambda v: -v.quality)
    for lead in sig_buf.get_available_leads():
        baseline, quality = characterize_baseline(lead, beg, end)
        sig = sig_buf.get_signal_fragment(beg, end, lead=lead)[0]
        if len(sig) == 0:
            return None
        #We build a signal simplification taking at most 9 points, and with
        #a minimum relevant deviation of 50 uV.
        points = RDP.arrayRDP(sig, C.RDP_MIN_DIST, C.RDP_NPOINTS)
        siginfo.add(LeadInfo(lead, sig, points, baseline, quality))
    return siginfo

def test_key():
    slt = SortedListWithKey(range(10000), key=lambda val: val % 10)
    slt._check()

    values = sorted(range(10000), key=lambda val: (val % 10, val))
    assert slt == values
    assert all(val in slt for val in range(10000))

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

    def _find_course_asset(self, asset_key):
        """
        Returns same as _find_course_assets plus the index to the given asset or None. Does not convert
        to AssetMetadata; thus, is internal.

        Arguments:
            asset_key (AssetKey): what to look for

        Returns:
            AssetMetadata[] for all assets of the given asset_key's type, & the index of asset in list
            (None if asset does not exist)
        """
        course_assets = self._find_course_assets(asset_key.course_key)
        if course_assets is None:
            return None, None

        all_assets = SortedListWithKey([], key=itemgetter('filename'))
        # Assets should be pre-sorted, so add them efficiently without sorting.
        # extend() will raise a ValueError if the passed-in list is not sorted.
        all_assets.extend(course_assets.setdefault(asset_key.block_type, []))
        # See if this asset already exists by checking the external_filename.
        # Studio doesn't currently support using multiple course assets with the same filename.
        # So use the filename as the unique identifier.
        idx = None
        idx_left = all_assets.bisect_left({'filename': asset_key.block_id})
        idx_right = all_assets.bisect_right({'filename': asset_key.block_id})
        if idx_left != idx_right:
            # Asset was found in the list.
            idx = idx_left

        return course_assets, idx

def test_copy_copy():
    import copy
    slt = SortedListWithKey(range(100), load=7, key=modulo)
    two = copy.copy(slt)
    slt.add(100)
    assert len(slt) == 101
    assert len(two) == 100

def test_key2():
    class Incomparable:
        pass
    a = Incomparable()
    b = Incomparable()
    slt = SortedListWithKey(key=lambda val: 1)
    slt.add(a)
    slt.add(b)
    assert slt == [a, b]

def test_bisect_left():
    slt = SortedListWithKey(key=negate)
    assert slt.bisect_left(0) == 0
    slt = SortedListWithKey(range(100), load=17, key=negate)
    slt.update(range(100))
    slt._check()
    assert slt.bisect_left(50) == 98
    assert slt.bisect_left(0) == 198
    assert slt.bisect_left(-1) == 200

    def get_feasible_next_customers(self, vehicles, count=None):
        next_pairs = [ (vehicle, customer, Cost.gnnh(self.delta, vehicle, customer)) \
                        for vehicle in vehicles \
                        for customer in self.customers \
                        if vehicle.isFeasible(customer) ]

        cs = SortedListWithKey(key=itemgetter(2))
        cs.update(next_pairs)
        return cs[:count]

 def __mul__(self, other):
     assert isinstance(other, Set)
     if len(self.list) == 0:
         return Set()
     list = SortedListWithKey(key=self.list._key)
     for x in self.list:
         if x in other.list:
             list.add(x)
     s = Set(list=list)
     return s

def test_getitem():
    random.seed(0)
    slt = SortedListWithKey(load=17, key=modulo, value_orderable=False)

    lst = list(random.random() for rpt in range(100))
    slt.update(lst)
    lst.sort(key=modulo)

    assert all(slt[idx] == lst[idx] for idx in range(100))
    assert all(slt[idx - 99] == lst[idx - 99] for idx in range(100))

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

    slt[-3] = 20
    slt._check()

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

def test_extend():
    slt = SortedListWithKey(load=4, key=modulo)

    slt.extend(range(5))
    slt._check()

    slt.extend(range(6, 10))
    slt._check()

def test_extend():
    slt = SortedListWithKey(load=4, key=modulo, value_orderable=False)

    slt.extend(range(5))
    slt._check()

    slt.extend(range(6, 10))
    slt._check()

def test_bisect():
    slt = SortedListWithKey(key=modulo, value_orderable=False)
    assert slt.bisect(10) == 0
    slt = SortedListWithKey(range(100), load=17, key=modulo, value_orderable=False)
    slt.update(range(100))
    slt._check()
    assert slt.bisect(10) == 20
    assert slt.bisect(0) == 20

def test_bisect_right():
    slt = SortedListWithKey(key=modulo)
    assert slt.bisect_right(10) == 0
    slt = SortedListWithKey(range(100), load=17, key=modulo)
    slt.update(range(100))
    slt._check()
    assert slt.bisect_right(10) == 20
    assert slt.bisect_right(0) == 20

class LRUCache:
    READ = 'read'
    WRITE = 'write'

    def __init__(self, size, mode):
        self._size = size
        self._mode = mode
        self._cache = {}
        self._used = {}
        if mode == self.READ:
            self._time = 0
        elif mode == self.WRITE:
            self._times = SortedListWithKey(key=self._used.get)

    def _use(self, key):
        if self._mode == self.READ:
            self._used[key] = self._time
            self._time += 1
        elif self._mode == self.WRITE:
            if self._times:
                if key in self._used:
                    self._times.discard(key)
                self._used[key] = self._used[self._times[-1]] + 1
            else:
                self._used[key] = 0
            self._times.add(key)

    def _remove(self):
        if self._mode == self.READ:
            lru = min(self._used, key=self._used.get)
            del self._cache[lru]
            del self._used[lru]
        elif self._mode == self.WRITE:
            lru = self._times.pop(0)
            del self._cache[lru]
            del self._used[lru]

    def get(self, key):
        item = self._cache.get(key)
        if item is None:
            return None
        self._use(key)
        return item

    def set(self, key, value):
        if key not in self._cache:
            if len(self._cache) == self._size:
                self._remove()
        self._cache[key] = value
        self._use(key)

    def __repr__(self):
        return repr(self._cache)

def test_contains():
    slt = SortedListWithKey(key=negate)
    assert 0 not in slt

    slt.update(range(10000))

    for val in range(10000):
        assert val in slt

    assert 10000 not in slt

    slt._check()

def test_contains():
    slt = SortedListWithKey(key=modulo, value_orderable=False)
    assert 0 not in slt

    slt.update(range(10000))

    for val in range(10000):
        assert val in slt

    assert 10000 not in slt

    slt._check()

def create_palette(color_depth=8):
    """ Create palette of all colors for color_depth bit rate.  """
    palette = SortedListWithKey(load=1000, key=lambda c: c.avg)
    scale = (MAX_COLOR_DEPTH / 2**color_depth)

    for x in range(0, 2**color_depth):
        for y in range(0, 2**color_depth):
            for z in range(0, 2**color_depth):
                r = x*scale
                g = y*scale
                b = z*scale
                palette.add( Color(r=r, g=g, b=b, avg=int(avg([r,g,b]))) )

    return palette