class List;

class ListItem {
    public:
        constexpr ListItem(): m_next(nullptr), m_prev(nullptr), m_list(nullptr) {
        }

        ~ListItem() {
            assert(m_list == nullptr);
        }

        bool remove();

        ListItem* next() const {
            return m_next;
        }

        List* list() const {
            return m_list;
        }

        bool inList() const {
            return list() != nullptr;
        }

        bool inList(List* l) const {
            return list() == l;
        }

    private:
        friend class List;

        ListItem* m_next;

        ListItem* m_prev;

        List* m_list;

};

class List {
    public:
        constexpr List(): m_head(nullptr), m_tail(nullptr), m_count(0) {
        }

        ~List() {
            assert(m_count == 0);
        }

        bool insertAfter(ListItem* item, ListItem* after);

        bool insertBefore(ListItem* item, ListItem* before);

        bool insertHead(ListItem* item) {
            return insertBefore(item, nullptr);
        }

        bool insertTail(ListItem* item) {
            return insertAfter(item, nullptr);
        }

        bool remove(ListItem* item) {
            if (item->m_list == this) {
                return item->remove();
            }
            return false;
        }

        ListItem* removeHead() {
            ListItem* item = m_head;
            if (item) {
                item->remove();
            }
            return item;
        }

        ListItem* removeTail() {
            ListItem* item = m_tail;
            if (item) {
                bool retval = item->remove();
                assert(retval);
            }
            return item;
        }

        ListItem* head() const {
            return m_head;
        }

        ListItem* tail() const {
            return m_tail;
        }

        unsigned int count() const {
            return m_count;
        }

        bool empty() const {
            return count() == 0;
        }

    private:
        friend class ListItem;

        ListItem* m_head;

        ListItem* m_tail;

        unsigned int m_count;

};

inline bool List::insertAfter(ListItem* item, ListItem* after) {
    assert(item != nullptr);
    if (after && (after->m_list != this)) {
        return false;
    }
    if (after) {
        item->m_prev = after;
        item->m_next = after->m_next;
        after->m_next = item;
        if (item->m_next) {
            item->m_next->m_prev = item;
        } else {
            m_tail = item;
        }
    } else {
        item->m_next = nullptr;
        item->m_prev = m_tail;
        if (item->m_prev) {
            item->m_prev->m_next = item;
        } else {
            m_head = item;
        }
        m_tail = item;
    }
    item->m_list = this;
    m_count++;
    return true;
}

inline bool List::insertBefore(ListItem* item, ListItem* before) {
    assert(item != nullptr);
    if (before && (before->m_list != this)) {
        return false;
    }
    if (before) {
        item->m_next = before;
        item->m_prev = before->m_prev;
        before->m_prev = item;
        if (item->m_prev) {
            item->m_prev->m_next = item;
        } else {
            m_head = item;
        }
    } else {
        item->m_prev = nullptr;
        item->m_next = m_head;
        if (item->m_next) {
            item->m_next->m_prev = item;
        } else {
            m_tail = item;
        }
        m_head = item;
    }
    item->m_list = this;
    m_count++;
    return true;
}

inline bool ListItem::remove() {
    List* list = m_list;
    if (list == nullptr) {
        return false;
    }
    if (m_next) {
        m_next->m_prev = m_prev;
    } else {
        list->m_tail = m_prev;
    }
    if (m_prev) {
        m_prev->m_next = m_next;
    } else {
        list->m_head = m_next;
    }
    list->m_count--;
    m_list = nullptr;
    return true;
}