linked_list.h

Go to the documentation of this file.

//   Copyright 2016-2023 Jean-Francois Poilpret
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.
 
 
#ifndef LINKEDLIST_HH
#define LINKEDLIST_HH
 
#include "utilities.h"
#include "types_traits.h"
 
namespace containers
{
    class LinkImpl
    {
    public:
        LinkImpl() INLINE = default;
        LinkImpl(const LinkImpl&) = delete;
        LinkImpl& operator=(const LinkImpl&) = delete;
 
    protected:
        LinkImpl* next_ = nullptr;
        friend class LinkedListImpl;
        template<class T, class B> friend struct types_traits::derives_from;
    };
 
    class LinkedListImpl
    {
    public:
        LinkedListImpl() INLINE = default;
        LinkedListImpl(const LinkedListImpl&) = delete;
        LinkedListImpl& operator=(const LinkedListImpl&) = delete;
        void insert(LinkImpl* item);
        bool remove(LinkImpl* item);
        template<typename F> void traverse(F f);
 
    protected:
        LinkImpl* head_ = nullptr;
    };
 
    template<typename T_> class LinkedList : private LinkedListImpl
    {
    public:
        LinkedList()
        {
            // Check that T_ is a LinkImpl subclass
            using DERIVES_FROM_LINK = types_traits::derives_from<T_, LinkImpl>;
            UNUSED DERIVES_FROM_LINK dummy = DERIVES_FROM_LINK();
        }
 
        using T = T_;
 
        void insert(T& item) INLINE
        {
            LinkedListImpl::insert(&item);
        }
 
        bool remove(T& item) INLINE
        {
            return LinkedListImpl::remove(&item);
        }
 
        template<typename F> void traverse(F func)
        {
            T* current = head();
            while (current != nullptr)
            {
                T* next = current->next();
                if (func(*current)) remove(*current);
                current = next;
            }
        }
 
    private:
        T* head() INLINE
        {
            return (T*) head_;
        }
    };
 
    template<typename T_> class Link : private LinkImpl
    {
    public:
        using T = T_;
    
    protected:
        Link() = default;
 
    private:
        T* next() INLINE
        {
            return (T*) next_;
        }
        friend class LinkedList<T>;
        template<class T, class B> friend struct types_traits::derives_from;
    };
 
    template<typename T_, typename TREF_ = T_&, typename CTREF_ = const T_&>
    class LinkWrapper : private LinkImpl
    {
    public:
        LinkWrapper(const LinkWrapper&) = delete;
        LinkWrapper& operator=(const LinkWrapper&) = delete;
 
        using T = T_;
 
        using TREF = TREF_;
 
        using CTREF = CTREF_;
 
        LinkWrapper(CTREF item) : item_{item} {}
 
        TREF item()
        {
            return item_;
        }
 
        CTREF item() const
        {
            return item_;
        }
 
    private:
        using TYPE = LinkWrapper<T, TREF, CTREF>;
 
        TYPE* next() INLINE
        {
            return (TYPE*) next_;
        }
 
        T item_;
 
        friend class LinkedList<TYPE>;
        template<class T, class B> friend struct types_traits::derives_from;
    };
}
 
#endif /* LINKEDLIST_HH */