kpeeters / tree.hh Goto Github PK

I try to merge two tree together but I'm not sure i properly understood what it says in the doc.

for instance with the siblings of the first level of two trees used as ranges for the merge function,
i expect something like:

a               a               a
└── a      +    └── b       =   ├── a
    └── a           └── b       │   └── a
                                └── b
                                    └── b

but the result is

┌── a
│   └── a
│       └── a
└── b
    └── b

code to demonstrate:

#include <trie.h>

using namespace std;

void print_branches(const tree<char>& tree) {
    tree<char>::leaf_iterator it = tree.begin_leaf();
    while(tree.is_valid(it)) {
        string branch;
        tree_node_<char>* node = it.node;
        while(node != tree.head && node != nullptr) {
            branch += ">-";
            branch.push_back(node->data);
            node = node->parent;
        }
        reverse(branch.begin(), branch.end());
        ++it;
        cout << branch << endl;
    }
}

int main(int argc, const char** argv) {
    tree<char> tree1, tree2;
    tree<char>::sibling_iterator it1, it2;
    it1 = tree1.insert(tree1.begin(), 'a');
    it1 = tree1.append_child(it1, 'a');
    it1 = tree1.append_child(it1, 'a');
    it2 = tree2.insert(tree2.begin(), 'a');
    it2 = tree2.append_child(it2, 'b');
    it2 = tree2.append_child(it2, 'b');

    it1 = tree1.begin();
    it2 = tree2.begin();
    tree1.merge(it1, it1.end(), it2, it2.end());
    print_branches(tree1);
}
    

output:

a->a->a->
b->b->

insead of

a->a->a->
a->b->b->

Am i correctly using the merge function in conjunction with the sibling_iterator?

It always returns an invalid iterator.

#include <algorithm>
#include "tree.hh"

int main(int argc, char* argv[]) {
    typedef tree<char> Tree;
    Tree my_tree;
    Tree::sibling_iterator it = my_tree.begin();
    it = my_tree.insert(it, 'x');
    it = my_tree.insert(it, 'y');
    it = my_tree.insert(it, 'z');

    it = std::find(it.begin(), it.end(), 'y');
    std::cout << "y is in tree ? " << my_tree.is_valid(it) << std::endl;

    it = my_tree.begin();
    it = std::lower_bound(it.begin(), it.end(), 'y');
    std::cout << "y is in tree ? " << my_tree.is_valid(it) << std::endl;

    it = my_tree.begin();
    while(my_tree.is_valid(it) && *it != 'y') ++it;
    std::cout << "y is in tree ? " << my_tree.is_valid(it) << std::endl;

    it = my_tree.begin();
    while(my_tree.is_valid(it) && *it != 'w') ++it;
    std::cout << "w is in tree ? " << my_tree.is_valid(it) << std::endl;

    return EXIT_SUCCESS;
}

gives:

y is in tree ? 0
y is in tree ? 0
y is in tree ? 1
w is in tree ? 0

Am i doing something wrong?

The lowest_common_ancestor function fails to spot when one node is the parent of the other.

When i try to use the fixed_depth iteration i am running into issues.

First of all this assertion always blocks my code from running:
assert(1==0); // FIXME: not correct yet: use is_valid() as a temporary workaround

Also i have issues when using the begin_fixed() and end_fixed() to define the range of my iteration.

could you maybe provide an example on how to properly iterate over all the nodes at a certain depth and within this iteration create a child for every node?

Any help is greatly appreciated!

It looks like the struct SwapChainDesc does not provide a member for "stereo support". Would it be possible to add it so that I can pass this feature to CreateSwapChainD3D11 and CreateSwapChainD3D12?

Thanks,
Jörn

Is this lib gonna see any updates or is it dead and abandoned? It would be nice to see the suggestions and PRs accepted at least and an update to C++20 would be awesome as well to improve performance.

"byte" is ambiguous C:\Program Files (x86)\Windows Kits\10\Include\10.0.22621.0\shared\rpcndr.h

Hello I'm wondering if you could provide an example of using your tree.hh class in a recursive manner for doing a pre-order traversal? I need a way to keep existing scope around for the current list while popping stuff off.

I've looked all over the internet for a method to do so, but have not found an example with your class.

Problem
When calling insert with an empty sibling_iterator as the first parameter, it is expected that a new node will be inserted below that iterator's parent. This is indeed the case if the insert method is called using such a sibling_iterator and data passed by constant reference. However, when calling the method using std::move on the data instead, the new node is inserted at the end of the tree.

The following code snippet illustrates this:

#include <vector>

#include "tree.hh"
#include "tree_util.hh"

int main(int argc, char *argv[])
{
    std::vector<std::vector<int>> idxsVec = {{0, 0, 0}, {0, 0, 1}, {0, 1, 2}, {1, 1, 2}};

    tree<int> tr;
    for(auto &idxs : idxsVec)
    {
        tree<int>::sibling_iterator it = tr.begin();
        tree<int>::sibling_iterator endIt = tr.end();

        for (auto &idx : idxs)
        {
            auto currIt = std::find_if(it, endIt, [idx](int foundIdx){
                return idx == foundIdx;
            });
            if(currIt == endIt)
            {
                // Option 1
                currIt = tr.insert(endIt, idx);

                // Option 2
                // currIt = tr.insert(endIt, std::move(idx));
            }

            it = tr.begin(currIt);
            endIt = tr.end(currIt);
        }
    }

    kptree::print_tree_bracketed(tr);

    return 0;
}

Using Option 1 you get this output (expected):

0(0(0, 1), 1(2))
1(1(2))

Using Option 2, this happens:

0
0
0
0
1
1
2
1
2

Possible solution
It seems the problem comes from the fact that there is a specialization of the insert method accepting sibling_iterator objects and data passed by constant reference, but there isn't one accepting moved data. This forces the code in Option 2 above to default to the generic version of the insert method that does accept moved data. Solving it seems as simple as creating such a specialization.

Missing include "string" in which is std::to_string defined.

iter tree<T, tree_node_allocator>::append_child(iter position, T&& x) contains std::swap(tmp->data, x); which enforces the use of std::swap. In my instance I needed to control how the data fields are swapped based on information they contain.
By changing the std::swap call to these 2 statements, I can provide an override swap function:
using std::swap;
swap(tmp->data, x);
If no override function is provided, the default std::swap is used.

It appears that head and feet nodes has a data member which is not initialized in the case where tree is templated on primitives. In some cases those data seems to interfere with search algorithms based on value comparison (lower_bound, upper_bound) when they take 'head' level sibling_iterator (the algorithm then randomly returns what looks like a default iterators instead of an iterator at the end position). it can be fixed by manually initializing those data with proper values.

step to reproduce:

#include <algorithm>
#include "tree.hh"

int main(int argc, char* argv[]) {
    typedef tree<char> Tree;
    Tree tree;

    // replace min by max to avoid the segfault
    tree.head->data = std::numeric_limits<char>::min();
    tree.feet->data = std::numeric_limits<char>::min();

    Tree::sibling_iterator it = tree.begin();
    it = tree.insert(it, 0);
    for (char c = 0; ++c; c < std::numeric_limits<char>::max()) {
        std::cout << "inserting char: " << (int) c << std::endl;
        it = std::lower_bound(it, it.end(), std::numeric_limits<char>::max()); 
        // here depending of what is c and what are head->data and feet->data the returned iterator
        // may be a default one instead of an iterator at it.end().
        it = tree.insert(it, c);
    }
    return EXIT_SUCCESS;
}

Inspection of the iterator returned by std::lower_bound before the segfault:

it = {tree<char, std::allocator>::sibling_iterator} 
 tree<char, std::allocator<tree_node_<char> > >::iterator_base = {tree<char, std::allocator>::iterator_base} 
  node = {tree<char, std::allocator>::tree_node * | 0x0} NULL
  skip_current_children_ = {bool} false
 parent_ = {tree<char, std::allocator>::tree_node * | 0x0} NULL

I'm trying to understand the logic of the move assignment operator, because I'm experiencing a segfault annotated below:

template <class T, class tree_node_allocator>
tree<T,tree_node_allocator>& tree<T, tree_node_allocator>::operator=(tree<T, tree_node_allocator>&& x)
	{
	if(this != &x) {
		clear(); // clear any existing data.
		
		head->next_sibling=x.head->next_sibling;
		feet->prev_sibling=x.head->prev_sibling;
		x.head->next_sibling->prev_sibling=head;
		x.feet->prev_sibling->next_sibling=feet; // <- SEGFAULT
		x.head->next_sibling=x.feet;
		x.feet->prev_sibling=x.head;
		}
	return *this;
	}

The pointer swaps are identical to the move constructor.
In my case, the tree that was already constructed and being moved has x.feet->prev_sibling null,
leaving x.feet->prev_sibling->next_sibling=feet; undefined behavior.

I've tried different things like skipping when its null or allocating for x.feet->prev_sibling when null but this causes crashes later when calculating depth. Let me know if anything stands out to you. I'll need to make a minimal example and visualize the pointer swaps. I've also replaced the move implementation with the copy version:

template <class T, class tree_node_allocator>
tree<T,tree_node_allocator>& tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
	{
	if(this != &other)
		copy_(other);
	return *this;
	}

and this solved all my problems but obviously not taking advantage of move optimizations.

The doc says that for the tree:

root
  |
  +----A
  |    |
  |    +---B
  |    | 
  |    +---C
  |
  +----D
       |
	   +---E
	   |
	   +---F

The resulting order in which nodes are visited using breadth_first_iterator is: root A D B C E F.
But it's A B C

    tree<char> t;
    auto r = t.insert(t.begin(), 'A');
    auto it = t.append_child(r, 'B');
    it = t.insert_after(it, 'C');

    it = t.insert_after(r, 'D');
    it = t.append_child(it, 'E');
    it = t.insert_after(it, 'F');

    auto bfit = t.begin_breadth_first();
    cout << "breadthfirst from root: ";
    while(t.is_valid(bfit)) {
        cout << *bfit << " ";
        ++bfit;
    }
    cout << endl;

    tree<char>::sibling_iterator siit = t.begin();
    cout << "siblings from root: ";
    while(t.is_valid(siit)) {
        cout << *siit << " ";
        ++siit;
    }
    cout << endl;

output:

breadthfirst from root: A B C   // Not OK
siblings from root: A D         // OK

Hi,

I try to create a tree in an iterative way: I start with one head node and then make a loop for the depth of the tree. In each iteration I want to add child nodes to the leafs of the tree. My current approach is as follows:

#include "tree.h"

int main(){

  // Initialize the tree
  tree<int> tr = tree<int>(1);

  // Loop for the depth of the tree
  int node_counter = 1;
  for (int depth = 1; depth <= 3; ++depth)
  {
    // Iterate over the leaf nodes
    tree<int>::leaf_iterator leaf_node = tr.begin_leaf();
    while(leaf_node != tr.end_leaf())
    {
      // Add children to the leaf node
      for (int k = 1; k <= 3; ++k)
      {
        tr.append_child(leaf_node, node_counter);
        ++node_counter;
      }
      // Go to the next leaf node
      ++leaf_node;
    }
  }

  return 0;
}

However, the while-loop over the leaf nodes never terminates. Is this because I change the tree on the flight or is it a bug? If it is not a bug, how can one create a tree in an iterative way?

I cannot compile tree.hh under VS2019 and ISO C++17 Standard (/std:c++17):

Severity Code Description Project File Line Suppression State
Error C4996 'std::allocator<tree_node_>::destroy': warning STL4010: Various members of std::allocator are deprecated in C++17. Use std::allocator_traits instead of accessing these members directly. You can define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING or _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS to acknowledge that you have received this warning. 3DView C:\HamburgSVN\CurryWin\C100\include\tree.hh 566

(8 errors in total)

Regards,
Jörn

Is it possible to use this library with a custom algorithm like A*, minmax, etc?

Or is one forced to use pre-order, etc.?

Thank you

The lowest_common_ancestor currently supports two iterators. It might be nice to have a version which takes multiple iterators, e.g. a vector or set or range.

There is some rudimentary functionality to print trees in kptree::print_tree_bracketed, but it would be nice to have an import functionality as well (reading that bracketed format or perhaps the trees in newick format).

Thanks a lot for the tree library.
I noticed that 'move_in_below' is declared but seems not to be implemented, but it's in the doc.
It took me for a while to figure out what was really happening, lol.

(I think 'move_in' also works in my situation, and I'm just sending this for a reminder)