Multiply linked list - implementation

Question

I don't know what is the common name for this data structure I named it like this due to a definition in wikipedia that states the following:

In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data records in a different order (e.g., by name, by department, by date of birth, etc.). While doubly linked lists can be seen as special cases of multiply linked list, the fact that the two orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.

I would like to know if this is a proper implementation of this data structure. Also any kind of improvements are welcome.

Implementation:

#pragma once
#include <functional>
#include <stdexcept>
namespace dts 
{
 template < typename T >
 class MultiplyList
 {
 public:
 using Comparator = std::function < int(const T&, const T&)>;
 private:
 class MultiNode
 {
 public:
 T data;
 MultiNode** nexts;
 MultiNode** prevs;
 unsigned size;
 MultiNode(unsigned psize, const T& pdata) 
 : data(pdata), nexts(new MultiNode*[psize]), 
 prevs(new MultiNode*[psize]), size(psize)
 { }
 MultiNode(unsigned psize, T&& pdata)
 :data(std::move(pdata)), nexts(new MultiNode*[psize]), 
 prevs(new MultiNode*[psize]), size(psize)
 { }
 MultiNode(unsigned psize)
 :MultiNode(psize, T())
 { }
 ~MultiNode() 
 {
 delete[] nexts;
 delete[] prevs;
 }
 MultiNode* getNext(unsigned index) const
 {
 check(index);
 return nexts[index];
 }
 void setNext(unsigned index, MultiNode* node)
 {
 check(index);
 nexts[index] = node;
 }
 MultiNode* getPrev(unsigned index) const
 {
 check(index);
 return prevs[index];
 }
 void setPrev(unsigned index, MultiNode* node)
 {
 check(index);
 prevs[index] = node;
 }
 void check(unsigned index) const 
 {
 if ( index >= size)
 throw new std::out_of_range("out of range");
 }
 };
 Comparator* arrayCmp;
 unsigned sizeCmp;
 int keyIndex;
 MultiNode* sentinel;
 unsigned size;
 void addNodeBefore(unsigned, MultiNode* newNode, MultiNode* node);
 bool findTightBoundary(unsigned, const T&, MultiNode*&) const;
 void deleteNode(MultiNode*);
 void resetSentinel();
 template<typename TT>
 bool genericAdd(TT&&);
 public:
 MultiplyList(std::initializer_list<Comparator>, int);
 MultiplyList(std::initializer_list<Comparator>);
 ~MultiplyList();
 bool add(const T&); //override T&&
 bool add(T&&);
 template<typename Predicate>
 bool remove(const Predicate&);
 template<typename Predicate>
 bool remove(const Predicate&, T&);
 bool empty() const;
 unsigned length() const;
 template<typename Func>
 void foreach(Func, unsigned index)const;
 template<typename Func>
 void foreach(Func)const;
 template<typename Predicate>
 bool find(Predicate, T&);
 void clear();
 bool hasKey();
 int paths();
 T getMax(int) const;
 T getMin(int) const;
 };
 template<typename T>
 MultiplyList<T>::MultiplyList(std::initializer_list<Comparator> cmps) 
 :MultiplyList(cmps, -1)
 { }
 template<typename T>
 MultiplyList<T>::MultiplyList(std::initializer_list<Comparator> cmps, int key)
 : sizeCmp(cmps.size()), size(0), arrayCmp(new Comparator[cmps.size()]),
 sentinel(new MultiNode(cmps.size() + 1)), keyIndex(key)
 {
 unsigned index = 0;
 for (const Comparator& e : cmps)
 arrayCmp[index++] = e;
 resetSentinel();
 if (0 <= key && key < sizeCmp)
 std::swap(arrayCmp[key], arrayCmp[0]);
 else key = -1;
 }
 template<typename T>
 MultiplyList<T>::~MultiplyList()
 {
 clear();
 delete[] arrayCmp;
 delete sentinel;
 }
 //O(sizeCmp*n)
 template<typename T>
 template<typename TT>
 bool MultiplyList<T>::genericAdd(TT&& e)
 {
 MultiNode *node = nullptr;
 bool isUnique = findTightBoundary(0, e, node);
 if (hasKey() && !isUnique) return false;
 auto newNode = new MultiNode(sizeCmp + 1, std::forward<TT>(e));
 addNodeBefore(0, newNode, node);
 for (unsigned i = 1; i < sizeCmp; ++i)
 {
 findTightBoundary(i, e, node);
 addNodeBefore(i, newNode, node);
 }
 addNodeBefore(sizeCmp, newNode, sentinel);
 ++size;
 return true;
 }
 template<typename T>
 bool MultiplyList<T>::add(T&& e)
 {
 genericAdd(std::move(e));
 }
 template<typename T>
 bool MultiplyList<T>::add(const T& e)
 {
 genericAdd(e);
 }
 template<typename T>
 template<typename Predicate>
 bool MultiplyList<T>::remove(const Predicate& pre)
 {
 T out;
 return remove(pre, out);
 }
 template<typename T>
 template<typename Predicate>
 bool MultiplyList<T>::remove(const Predicate& pre, T& out)
 {
 const unsigned path = 0;
 auto node = sentinel->getNext(path);
 while (node != sentinel && !pre(node->data))
 node = node->getNext(path);
 bool exist = node != sentinel;
 if (exist)
 {
 out = node->data;
 deleteNode(node);
 }
 return exist;
 }
 template<typename T>
 bool MultiplyList<T>::empty() const
 {
 return size == 0;
 }
 template<typename T>
 unsigned MultiplyList<T>::length() const
 {
 return size;
 }
 template<typename T>
 template<typename Func>
 void MultiplyList<T>::foreach(Func func, unsigned cmpIndex) const
 {
 auto node = sentinel->getNext(cmpIndex);
 while (node != sentinel)
 {
 func(node->data);
 node = node->getNext(cmpIndex);
 }
 }
 template <typename T>
 template<typename Func>
 void MultiplyList<T>::foreach(Func f) const
 {
 foreach(f, sizeCmp);
 }
 template<typename T>
 template<typename Predicate>
 bool MultiplyList<T>::find(Predicate pre, T& e)
 {
 const unsigned index = sizeCmp;
 auto node = sentinel->getNext(index);
 while (node != sentinel && !pre(node->data))
 node = node->getNext(index);
 bool found = node != sentinel;
 if (found) e = node->data;
 return found;
 }
 template<typename T>
 void MultiplyList<T>::addNodeBefore(unsigned cmpIndex, MultiNode* newNode, MultiNode* node)
 {
 newNode->setNext(cmpIndex, node);
 newNode->setPrev(cmpIndex, node->getPrev(cmpIndex));
 node->getPrev(cmpIndex)->setNext(cmpIndex, newNode);
 node->setPrev(cmpIndex, newNode);
 }
 template<typename T>
 bool MultiplyList<T>::findTightBoundary(unsigned cmpIndex, const T& e, MultiNode*& node) const
 {
 auto ig = 1;
 node = sentinel->getNext(cmpIndex);
 while (node != sentinel && (ig = arrayCmp[cmpIndex](e, node->data)) > 0)
 node = node->getNext(cmpIndex);
 return ig != 0;
 }
 template<typename T>
 void MultiplyList<T>::deleteNode(MultiNode* node)
 {
 for (unsigned i = 0; i <= sizeCmp; ++i)
 {
 node->getPrev(i)->setNext(i, node->getNext(i));
 node->getNext(i)->setPrev(i, node->getPrev(i));
 }
 delete node;
 --size;
 }
 template<typename T>
 void MultiplyList<T>::clear()
 {
 const unsigned path = 0;
 auto node = sentinel->getNext(path);
 while (node != sentinel)
 {
 auto borrar = node;
 node = node->getNext(path);
 delete borrar;
 }
 resetSentinel();
 }
 template <typename T>
 void MultiplyList<T>::resetSentinel()
 {
 for (unsigned i = 0; i <= sizeCmp; ++i)
 {
 sentinel->setNext(i, sentinel);
 sentinel->setPrev(i, sentinel);
 }
 }
 template <typename T>
 bool MultiplyList<T>::hasKey()
 {
 return keyIndex >= 0;
 }
 template <typename T>
 int MultiplyList<T>::paths()
 {
 return sizeCmp + 1;
 }
 template<typename T> 
 T MultiplyList<T>::getMax(int index) const
 {
 if (empty()) throw std::underflow_error("underflow");
 return sentinel->getPrev(index)->data;
 }
 template<typename T>
 T MultiplyList<T>::getMin(int index) const
 {
 if (empty()) throw std::underflow_error("underflow");
 return sentinel->getNext(index)->data;
 }
}

Example: (This example is just to show some client code I have no particular interest in getting a review of this part)

#include <tuple>
#include <vector>
#include <algorithm>
#include <iostream>
#include "MultiplyList.h"
using str = std::tuple < int, char, std::string >;
using namespace dts;
void pruebaListaMultiply(MultiplyList<str>* list)
{
 std::vector<std::string> vecS = 
 { 
 "bb", 
 "aa",
 "ccc",
 "dfsf", 
 "atsdfds", 
 "ggg", 
 "hhh", 
 "qqq", 
 "sdad", 
 "asdda", 
 "dsfdsf", 
 "dsffsf" 
 };
 std::vector<char> vecC = 
 { 
 'a','b',
 'c','r', 
 'o', 'l', 
 'u', 'f', 
 'r', 'p', 
 'w', 'k' 
 };
 unsigned min = std::min(vecS.size(), vecC.size());
 for (unsigned i = min-1; i !=0; --i)
 { 
 list->add(str(i, vecC[i], vecS[i]));
 }
 for (unsigned i = 0; i < 4; ++i)
 {
 std::cout << "Criterio # " << i << std::endl;
 list->foreach(
 [](str x)
 {
 std::cout << std::get<0>(x)
 << " " << std::get<1>(x)
 << " " << std::get<2>(x).c_str()
 << " " << std::endl;
 },i);
 } 
 list->remove([](str x){ return std::get<0>(x) == 6; });
 std::cout << "Despues" << std::endl << std::endl;
 for (unsigned i = 0; i < 3; ++i)
 {
 std::cout << "Criterio # " << i << std::endl;
 list->foreach(
 [](str x)
 {
 std::cout << std::get<0>(x)
 << " " << std::get<1>(x)
 << " " << std::get<2>(x).c_str()
 << " " << std::endl;
 },i);
 }
}
void example()
{
 auto list = new MultiplyList<str>
 ({
 [](str x, str y)
 {
 if (std::get<1>(y) < std::get<1>(x))return 1;
 if (std::get<1>(x) < std::get<1>(y))return -1;
 return 0;
 },
 [](str x, str y)
 {
 if (std::get<0>(y) < std::get<0>(x))return 1;
 if (std::get<0>(x) < std::get<0>(y))return -1;
 return 0;
 },
 [](str x, str y)
 {
 if (std::get<2>(y) < std::get<2>(x))return 1;
 if (std::get<2>(x) < std::get<2>(y))return -1;
 return 0;
 }
 },1);
 pruebaListaMultiply(list);
 list->clear();
 pruebaListaMultiply(list);
}
int main(int argc, char** argv) {
 example();
}

• smac89: From the definition and from what I understand, I expect a multiply linked list to be able to do: list.onNameField().next().next().onDepartmentField().next(). In the end, I should get another list that has the same value in the name and department as the list I started with. If this is what yours does, then I believe you've done it correctly. Your code is hard to read, especially with the use of tuples and lambda functions. Also this sounds more like a graph problem than just about linkedlists
• MAG: You mean return an iterator for each criteria?. Also since it is a generic implementation I don't think I can have a descriptive function for each one. Also feel free to post an answer. It will be nice to see how can I make my code more readable. The example doesn't do anything relevant is just some code that put together for the sake of the review (to show some client code)

Answer 1

Pointers And Double Pointers, Oh My

Let's start with the composition of your Node. You have:

MultiNode** nexts;
MultiNode** prevs;
unsigned size;

Two issues I have here. First, according to the problem description, the list is multiply linked - but nowhere is it stipulated that each link is bidirectional. Given that it is stated that doubly linked list is a special case of multiply linked list, that suggests that we just want a bunch of links. And furthermore, let's use C++ here and stick them in a vector:

std::vector<MultiNode*> links;

This lets you do things like drop the destructor, always a plus.

Comparators

Similarly, your comparators should be:

std::vector<Comparator> comparators;

And typically, comparators return bool. Yours return int. I see what you're getting at, but that means I can't use operator< as a comparator - which may be surprising to many users.

Add iterators

You need iterators. I'd recommend adding overloads for begin() and end() that take a comparator index. So something like;

iterator begin() { return begin(0); }
iterator begin(size_t idx) { /* return iterator based on this index */ }

Insertion

Why does genericAdd() check for uniqueness? It's pretty reasonable to want a list of repeated objects - you should allow that. And adding the iterators allows for a much more pleasant search.

void add(T const& elem)
{
 auto new_node = new MultiNode(comparators.size(), elem);
 for (size_t i = 0; i < comparators.size(); ++i) {
 auto loc = std::lower_bound(begin(i), end(i), elem, comparators[i]);
 insert_one(loc, new_node);
 }
 ++size;
}

Where insert_one is a private member function that will stick that new node in front of that iterator. Each iterator should be aware of which comparator index it's updating. The above is much easier to follow in my opinion.

Unnecessary code bloat

You have a find() member function and a foreach() member function. Both of those go away if you add iterators, since your users can just use std::find_if() and std::for_each(), not to mention all the other algorithms.

Naming

length() should be named size().

remove() should be named erase() and should have an overload that removes a single iterator and an overload that takes an iterator range. Try getting the erase-remove idiom to work with your class.

KeyIndex

What is the purpose of this variable?

• MAG: I can select a keyIndex and that comparator would be check first for uniqueness if none is provided then it wont. But yea I am not very happy how I did that. Thanks for the great review.
• 5gon12eder: Is the overload on begin needed for some SFINAE trickery to work or could is be just as simple as iterator begin(std::size_t idx = 0);? Not that the overload would be terribly complicated, though.

Answer 2

If you have a destructor you should also have a copy constructor and assignment operator (and the move variants).

For a container I expect a set of begin() and end() functions so the classic STL for loop can be used with it.

The iterator type could be a struct with a pointer to a MultiNode and a int for the index passed to getNext(int) on operator++.

I would expect bool find(Predicate, T&); bool hasKey(); and int paths(); to be const as well.