Tree.hpp

Go to the documentation of this file.

/*
   Copyright 2022 Rishi Challa
 
   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.
*/
 
#pragma once
 
#include <list>
#include <iterator>
#include <algorithm>
#include <memory>
 
namespace Kale {
 
    template <typename T> class Tree {
    public:
 
        struct Child {
        private:
 
            Child* next = nullptr;
 
            Child* previous = nullptr;
 
            Child* parent = nullptr;
 
            Tree& tree;
 
            std::list<Child> children;
 
            size_t horizontal;
 
            size_t vertical;
 
            T value;
 
            void setup() {
                // Create a pointer/iterator to use for misc searching purposes
                Child* it = nullptr;
                
                // Find the next child
                it = parent->next;
                while (it != nullptr) {
                    if (!it->children.empty()) {
                        next = &it->children.front();
                        break;
                    }
                    it = it->next;
                }
 
                // Find the previous child
                if (next != nullptr) previous = next->previous;
                else {
                    it = parent;
                    while (it != nullptr) {
                        if (!it->children.empty()) {
                            previous = &it->children.back();
                            break;
                        }
                        it = it->previous;
                    }
                }
 
                // Update the next/previous of surrounding children
                if (next != nullptr) next->previous = this;
                if (previous != nullptr) previous->next = this;
 
                // Set the horizontal & vertical indices based on the next/previous/parent
                horizontal = previous != nullptr ? previous->getHorizontalIndex() + 1 : 0;
                vertical = parent->vertical + 1;
 
                // Update the back if applicable
                if (vertical > tree.backPtr->vertical || (vertical == tree.backPtr->vertical && horizontal > tree.backPtr->horizontal))
                    tree.backPtr = this;
 
                // All children on the same vertical level with greater horizontal indices need to be updated
                it = next;
                while (it != nullptr) {
                    it->horizontal++;
                    it = it->next;
                }
            }
 
            friend class Tree<T>;
 
        public:
 
            Child(Tree& tree) : tree(tree), horizontal(0), vertical(0) {}
 
            Child(Tree& tree, const T& value) : tree(tree), horizontal(0), vertical(0), value(value) {}
 
            Child(Child& parent) : tree(parent.tree), parent(&parent) {
                setup();
            }
 
            Child(Child& parent, const T& value) : tree(parent.tree), parent(&parent), value(value) {
                setup();
            }
 
            ~Child() {
                if (previous != nullptr) previous->next = next;
                if (next != nullptr) next->previous = previous;
 
                Child* it = next;
                while (it != nullptr) {
                    it->horizontal--;
                    it = it->next;
                }
            }
 
            // Deleting moving/copying
            Child(const Child& other) = delete;
            Child(Child&& other) = delete;
            void operator=(const Child& other) = delete;
            void operator=(Child&& other) = delete;
 
            Child& addChild() {
                return children.emplace_back(*this);
            }
 
            Child& addChild(const T& value) {
                return children.emplace_back(*this, value);
            }
 
            void removeChild(size_t horizontal) {
                children.remove_if([&](const Child& child) { return child.getHorizontalIndex() == horizontal; });
            }
            
            const T* operator->() const {
                return &value;
            }
 
            T* operator->() {
                return &value;
            }
 
            const T& getValue() const {
                return value;
            }
 
            T& getValue() {
                return value;
            }
            
            const Child* getNext() const {
                return next;
            }
 
            Child* getNext() {
                return next;
            }
 
            const Child* getPrevious() const {
                return previous;
            }
 
            Child* getPrevious() {
                return previous;
            }
 
            const Child* getParent() const {
                return parent;
            }
 
            Child* getParent() {
                return parent;
            }
 
            size_t getHorizontalIndex() const {
                return horizontal;
            }
 
            size_t getVerticalIndex() const {
                return vertical;
            }
 
            const std::list<Child>& getChildren() const {
                return children;
            }
 
            std::list<Child>& getChildren() {
                return children;
            }
 
        };
 
        template <typename S> struct RawIterator {
        private:
 
            S* ptr;
 
            const Tree& tree;
 
        public:
 
            // Required information for custom iterators
            using iterator_category = std::bidirectional_iterator_tag;
            using value_type = S;
            using pointer = S*;
            using reference = S&;
 
            RawIterator(const Tree& tree, S* ptr = nullptr) : tree(tree), ptr(ptr) {}
 
            RawIterator<S>& operator=(S* ptr) { this->ptr = ptr; }
 
            operator bool() const { return ptr != nullptr; }
 
            bool operator==(const RawIterator<S> it) const { return it.ptr == ptr; }
 
            bool operator!=(const RawIterator<S> it) const { return it.ptr != ptr; }
 
            RawIterator<S>& operator++() {
                // The next isn't nullptr, we simply move on to the next in the same horizontal index
                if (ptr->getNext() != nullptr) {
                    ptr = ptr->getNext();
                    return *this;
                }
 
                // We need to move to the next vertical index, keep searching the previous nodes for children
                // If found, set it so we get the earliest one possible.
                S* it = ptr;
                ptr = nullptr;
                while (it != nullptr) {
                    if (!it->getChildren().empty()) ptr = &it->getChildren().front();
                    it = it->getPrevious();
                }
 
                // If ptr is nullptr, it means we've finished looping (this iterator is now the end)
                return *this;
            }
 
            RawIterator<S>& operator--() {
                if (ptr == nullptr) {
                    ptr = tree.backPtr;
                    return *this;
                }
 
                // This is the root, it can't be decremented
                if (ptr->getParent() == nullptr) return *this;
 
                // The previous isn't nullptr, we simply move on to the previous in the same horizontal index
                if (ptr->getPrevious() != nullptr) {
                    ptr = ptr->getPrevious();
                    return *this;
                }
 
                // We need to move to the previous vertical index, go to our parent then go to the last index possible
                ptr = ptr->getParent();
                while (ptr->getNext() != nullptr) ptr = ptr->getNext();
 
                // If ptr is nullptr, it means we've finished looping (this iterator is now the beginning)
                return *this;
            }
 
            RawIterator<S> operator++(int) {
                RawIterator<S> it = *this;
                ++(*this);
                return it;
            }
 
            RawIterator<S> operator--(int) {
                RawIterator<S> it = *this;
                --(*this);
                return it;
            }
 
            S& operator*() {
                return *ptr;
            }
 
            const S& operator*() const {
                return *ptr;
            }
 
            S* operator->() {
                return ptr;
            }
 
            const S* operator->() const {
                return ptr;
            }
 
            S* getPtr() const {
                return ptr;
            }
 
            const S* getConstPtr() const {
                return ptr;
            }
        };
 
    private:
 
        Child* backPtr;
 
        friend struct Child;
        friend struct RawIterator<Child>;
        friend struct RawIterator<const Child>;
 
    public:
 
        using Iterator = RawIterator<Child>;
 
        using ConstIterator = RawIterator<const Child>;
 
        std::unique_ptr<Child> root;
 
        Tree() : root(std::make_unique(*this)), backPtr(&root) {}
 
        Tree(const T& value) : root(std::make_unique(*this, value)), backPtr(&root) {}
 
        // Tree(const Tree& other);
        // void operator=(const Tree& other);
 
        // Trees don't support moving
        Tree(Tree&& other) = delete;
        void operator=(Tree&& other) = delete;
 
        Iterator begin() {
            return Iterator(*this, &root);
        }
 
        ConstIterator cbegin() const {
            return ConstIterator(*this, &root);
        }
 
        Iterator end() {
            return Iterator(*this, nullptr);
        }
 
        ConstIterator cend() const {
            return ConstIterator(*this, nullptr);
        }
 
        
        Child& front() {
            return *root;
        }
        
        const Child& front() const {
            return *root;
        }
        
        Child& back() {
            return *backPtr;
        }
        
        const Child& back() const {
            return *backPtr;
        }
 
        const Child& operator()(size_t horizontal, size_t vertical) const {
            return *std::find_if(cbegin(), cend(), [&](const Child& child) {
                return child.getHorizontalIndex() == horizontal && child.getVerticalIndex() == vertical;
            });
        }
 
        Child& operator()(size_t horizontal, size_t vertical) {
            return *std::find_if(begin(), end(), [&](const Child& child) {
                return child.getHorizontalIndex() == horizontal && child.getVerticalIndex() == vertical;
            });
        }
 
    };
 
}