Adds item to DEPQ with given priority by performing a binary
        search on the concurrently rotating deque. Amount rotated R of
        DEPQ of length n would be n <= R <= 3n/2. Performance: O(n)

def insert(self, item, priority):
        """Adds item to DEPQ with given priority by performing a binary
        search on the concurrently rotating deque. Amount rotated R of
        DEPQ of length n would be n <= R <= 3n/2. Performance: O(n)"""

        with self.lock:

            self_data = self.data
            rotate = self_data.rotate
            self_items = self.items
            maxlen = self._maxlen

            try:

                if priority <= self_data[-1][1]:
                    self_data.append((item, priority))
                elif priority > self_data[0][1]:
                    self_data.appendleft((item, priority))
                else:

                    length = len(self_data) + 1
                    mid = length // 2
                    shift = 0

                    while True:

                        if priority <= self_data[0][1]:
                            rotate(-mid)
                            shift += mid
                            mid //= 2
                            if mid == 0:
                                mid += 1

                        else:
                            rotate(mid)
                            shift -= mid
                            mid //= 2
                            if mid == 0:
                                mid += 1

                        if self_data[-1][1] >= priority > self_data[0][1]:
                            self_data.appendleft((item, priority))

                            # When returning to original position, never shift
                            # more than half length of DEPQ i.e. if length is
                            # 100 and we rotated -75, rotate -25, not 75
                            if shift > length // 2:
                                shift = length % shift
                                rotate(-shift)
                            else:
                                rotate(shift)

                            break

                try:
                    self_items[item] += 1
                except TypeError:
                    self_items[repr(item)] += 1

            except IndexError:
                self_data.append((item, priority))
                try:
                    self_items[item] = 1
                except TypeError:
                    self_items[repr(item)] = 1

            if maxlen is not None and maxlen < len(self_data):
                self._poplast()