# solution provided by GitHub user clean99
def make_deque():
    return pair(None, None)

def front_ptr(deque):
    return head(deque)

def rear_ptr(deque):
    return tail(deque)

def set_front_ptr(deque, item):
    set_head(deque, item)

def set_rear_ptr(deque, item):
    set_tail(deque, item)

def is_empty_deque(deque):
    return (True
            if is_none(front_ptr(deque))
            else True
            if is_none(rear_ptr(deque))
            else False)

def is_one_item_deque(deque):
    return front_ptr(deque) is rear_ptr(deque)

def front_insert_deque(deque, item):
    # use another pair to store a forward pointer
    new_pair = pair(pair(item, None), None)
    if is_empty_deque(deque):
        set_front_ptr(deque, new_pair)
        set_rear_ptr(deque, new_pair)
    else:
        set_tail(new_pair, front_ptr(deque))
        # set forward pointer to new_pair
        set_tail(head(front_ptr(deque)), new_pair)
        set_front_ptr(deque, new_pair)

def front_delete_deque(deque):
    if is_empty_deque(deque):
        error("front_delete_deque called with an empty deque", deque)
    elif is_one_item_deque(deque):
        set_front_ptr(deque, None)
        set_rear_ptr(deque, None)
        return deque
    else:
        set_front_ptr(deque, tail(front_ptr(deque)))
        return deque

def rear_insert_deque(deque, item):
    if is_empty_deque(deque):
        new_pair = pair(pair(item, None), None)
        set_front_ptr(deque, new_pair)
        set_rear_ptr(deque, new_pair)
    else:
        # set new_pair forward pointer to last item
        new_pair = pair(pair(item, rear_ptr(deque)), None)
        set_tail(rear_ptr(deque), new_pair)
        set_rear_ptr(deque, new_pair)

def rear_delete_deque(deque):
    if is_empty_deque(deque):
        error("rear_delete_deque called with an empty deque", deque)
    elif is_one_item_deque(deque):
        set_front_ptr(deque, None)
        set_rear_ptr(deque, None)
        return deque
    else:
        # update rear_ptr to last item's forward pointer
        set_rear_ptr(deque, tail(head(rear_ptr(deque))))
        return deque
