Help with dependency inversion

Question

I'm learning about Binary Trees in school and I'm trying to apply the SOLID principles to it.

My problem is in my BinaryTree::insert() method I'm creating a new BinaryNode, and from what I've understood that's bad dependency direction because higher level abstractions (a tree) should not depend on lower level details (a node). How would I go about making both the tree and node depend on an abstraction instead?

template <typename T>
class BinaryTree {
public:
    void insert(const T value) { _root = insert(_root, value); }
private:
    BinaryNode<T>* insert(BinaryNode<T>* node, const T value)
    {
        if (node == nullptr)
            return new BinaryNode<T>(value);
        else if (value < node->getValue())
            node->setLeft(insert(node->getLeft(), value));
        else
            node->setRight(insert(node->getRight(), value));
        return node;
    }
private:
    BinaryNode<T>* _root;
};

I specifically want to get rid of the object creation new BinaryNode inside the private insert method.

Answer 1

Let's lay out two things. The first is that it's good to hide implementation details from the user of your code, but it's not necessary to abstract them away entirely. In other words, it's fine to use new in your implementation of your BinaryTree, so long as your user doesn't need to see it.

That being said, it is possible to make things more generic. Below is a very, very generic implementation of a binary tree, complete with Allocators, Deleters, and automatic memory management (there's no need to write a destructor for the tree).

Allocators

Allocators provide a generic way of getting memory. It could be from a memory pool, or it could be from the heap with new, or it could even be something more exotic.

The key idea here is that all your allocators provide a common interface. To keep things simple, we'll use a function called make_new which gets the memory, and constructs the type using the given arguments.

A default allocator and a default deleter would look something like this:

template<class T>
struct DefaultAllocator {
    // Get some memory from somewhere
    template<class... Args>
    T* make_new(Args&&... args) const { 
        return new T(std::forward<decltype(args)>(args)...); 
    }
};
struct DefaultDeleter {
    //This lets us call Deleter like it's a function
    template<class Type>
    void operator()(Type* ptr) const { 
        delete ptr; 
    }
};

unique_ptr: a class for automatically managing memory

If we want to ensure that there aren't any memory leaks, we should probably use a class like std::unique_ptr. When a class containing unique_ptr is destroyed, whatever unique_ptr points too will automatically be destroyed too.

We can write our own unique_ptr pretty easily. The key is that a unique_ptr should always be unique: we can move it, but we can't make a copy.

template<class T, class Deleter = DefaultDeleter>
class unique_ptr : Deleter {
    T* ptr; 

   public:
    Deleter const& get_deleter() const {
        return *this;
    }
    unique_ptr() 
      : Deleter()
      , ptr(nullptr) 
    {}
    unique_ptr(T* ptr) 
      : Deleter()
      , ptr(ptr) 
    {}
    unique_ptr(T* ptr, Deleter const& d) 
      : Deleter(d), 
      ptr(ptr) 
    {}

    //It can't be copied, so we're deleting the copy constructor
    unique_ptr(unique_ptr const&) = delete; 

    //It's fine to move a unique_ptr
    unique_ptr(unique_ptr && other) 
      : Deleter(other.get_deleter())
      , ptr(other.ptr) 
    {
        //Set other.ptr to null so that it doesn't get deleted twice
        other.ptr = nullptr; 
    }

    //Again, no copying allowed
    unique_ptr& operator=(unique_ptr const&) = delete;
    //But like always, we can move it. 
    unique_ptr& operator=(unique_ptr&& other) {
        //Delete the current pointer
        get_deleter()(ptr); 
        //Assign new ptr:
        ptr = other.ptr; 
        //Set other ptr to null so it doesn't get deleted twice
        other.ptr = nullptr; 
        //Return self
        return *this;
    }
    unique_ptr& operator=(T* new_ptr) {
        //Delete current ptr
        get_deleter()(ptr); 
        //Assign new ptr
        ptr = new_ptr; 
        //return self
        return *this;
    }
    ~unique_ptr() {
        //Call the deleter on the pointer
        //if ptr is null, nothing should happen
        get_deleter()(ptr); 
    }
    void swap(unique_ptr& other) {
        //The standard library provides a swap function
        std::swap(ptr, other.ptr); 
    }
    //Overloading -> allows us to use unique_ptr
    //as though it were a regular pointer
    T* operator->() {
        return ptr; 
    }
    T const* operator->() const {
        return ptr; 
    }
    //We can also overload the dereference operator
    //so that it behaves like a regular pointer
    T& operator*() {
        return *ptr; 
    }
    T const& operator*() const {
        return *ptr; 
    }

    //We can also enable checking if it's null:
    bool isNull() const {
        return ptr == nullptr;
    }
    //And we can enable direct comparisons against nullptr
    using nullptr_t = decltype(nullptr); 
    bool operator==(nullptr_t) const {
        return ptr == nullptr; 
    }

    //Let's also have a method to get the raw pointer:
    T* get() { return ptr; }
    T const* get() const { return ptr; }
};

BinaryNode class based on unique_ptr:

Because it's a tree, each node should appear in the tree exactly once. This is a good thing. It means we can use our unique_ptr class, and everything like destruction will get handled automatically: no chance of memory leaks.

template<class T, class Deleter = DefaultDeleter>
class BinaryNode {
    T value;
    unique_ptr<BinaryNode, Deleter> left;
    unique_ptr<BinaryNode, Deleter> right; 
   public:
    BinaryNode(T const& value) 
      : value(value) 
      , left()
      , right()
    {}
    BinaryNode(T&& value)
      : value(std::move(value))
      , left()
      , right()
    {}

    T& get_value() { 
        return value; 
    }
    T const& get_value() const {
        return value;
    }
    //Let's typedef to give it a shorter name:
    using pointer_t = unique_ptr<BinaryNode, Deleter>;         
    //Because we return a reference, we don't have to 
    //write a set_left or set_right method
    pointer_t& get_left() {
        return left;
    }
    pointer_t& get_right() {
        return right; 
    }
    //Writing a const overload is a good idea
    pointer_t const& get_left() const {
        return left;
    }
    pointer_t const& get_right() const {
        return right; 
    }
};

BinaryTree class with find and insert

Let's look at the BinaryTree class now. This will actually be one of the most simple to write, because the other classes already take care of stuff like memory management. We've been using Deleters throughout, but now allocators finally come into play.

The interface for insert will be a little different, and the only thing that's changed is that we'll be passing the pointer by reference, instead of value. This allows us to make insert tail-recursive, which makes it more efficient. It also makes insert a little shorter and simpler.

template <class T,
          class Deleter = DefaultDeleter,
          class Allocator = DefaultAllocator<BinaryNode<T, Deleter>>>
class BinaryTree : Allocator, Deleter {
    // Let's declare node_pointer_t
    // so that we don't have to type out unique_ptr<...> every time
    using node_pointer_t = typename BinaryNode<T, Deleter>::pointer_t;

    // If we take the node pointer by reference
    // Then we don't have to return anything
    // Also our function becomes tail-recursive
    // Which means that it won't segfault when called
    // no matter how deep the recursion gets
    // as long as you have optimization turned on
    void insert(node_pointer_t& node, const T& value)
    {
        if (node == nullptr) {
            node = get_allocator().make_new(value); 
        }
        else if (value < node->get_value()) {
            insert(node->get_left(), value);
        }
        else {
            insert(node->get_right(), value); 
        }
    }
    bool find(node_pointer_t& node, const T& value) {
        if (node == nullptr) {
            return false; 
        }
        else if(value == node->get_value()) {
            return true; 
        }
        else if (value < node->get_value()) {
            return find(node->get_left(), value);
        }
        else {
            return find(node->get_right(), value); 
        }
    }
    // It'll automatically delete itself
    node_pointer_t _root;
   public:
    BinaryTree()
      : Allocator() //Init allocator
      , Deleter()   //Init deleter
      , _root()     //Init root
    {}

    Allocator const& get_allocator() {
        return *this; 
    }
    Deleter const& get_deleter() {
        return *this; 
    }

    void insert(T const& value) { insert(_root, value); }
    bool find(T const& value) { return find(_root, value); }
};

Conclusion

We did it, y'all. HMU if you have any questions.

Answer 2

DI is not an end in itself, it is a means to an end. I have my doubts about the usefulness of applying DI to this binary tree with something else than the "canonical" binary node, or even a necessity to write unit tests for this kind of tree with "mock nodes". So I don't see any sensible application of DI in this example.

However, if you just want to try out DI here for learning purposes, to apply DI formally, sensible or not, one needs to inject a BinaryNodeFactory object into the binary tree at construction time through an IBinaryNodeFactory interface, create an interface IBinaryNode and replace new BinaryNode<T>(value) by binNodeFactory<T>.CreateNew(). That would allow to replace the factory easily by a different one which can produce alternative IBinaryNode objects.

(Note, in C++ a well-known alternative design is to use template meta programming for "injecting" dependencies at compile time, as shown in Jorge Perez' answer).

But be aware this may easily become a perfect example of overengineering - so please don't do it in real-world code if you do not have a real need for it.