test

range_map: new container class for C++

Page 1 of 2 [ 25 posts ] Go to page 1, 2 Next

Previous topic | Next topic

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

23 May 2014, 8:20 pm

This is a new container template class which stores ranges on a map, built on a modified rb-tree. I've been working on this for more than a year. Basically, instead of storing points in the class, you store ranges in the form of [left, right). (Note the bracket next to left, which means it falls in the range, but the parenthesis next to right, which means it falls just outside the range. Basically, the value x falls in the range [left, right) if left <= x < right, so by extension if x == right were true then x would fall outside the range.) The range is stored in the basic class range_map_item (with key_type and mapped_type needing to be specified), which contains the bounds and mapped value of the range; it is also the range_map member class type range_type, which already has its template filled out with key_type and mapped_type specified in the template of range_map. (Note that left must be less than right. The range needs to have a width of at least the minimum non-zero value.)

The name of the class is range_map and it falls in the namespace beneficii. Its template takes at least 2 and up to 4 arguments, the key_type (which is the type that would determine the location of each bounding end point on the range, defining the range's location and extent), the mapped_type (which is what is the type of object mapped to the range and unlike C++11 map can be modified). Further, there are 2 optional arguments, the comparator_type (which is the functor type that overloads its () operator as a const method, with the following 2 parameters: left and right, both of the type const key_type& or key_type; the return value is of type bool: true is to be returned if left comes before right in the set of values of key_type; false otherwise): the comparator_type defaults to std::less<key_type> which merely checks if the value left is less than the value right, with both as key_type or const key_type&; and the allocator_type, which defaults to std::allocator<range_map_item<key_type, mapped_type> >.

Skip to BLAH if you don't care about using a custom allocator.

If you want to use a custom allocator, the requirements are similar to those of the Standard Template Library of C++. It must be a class template that takes one class (let's call it my_type). There must be a rebind member class type that takes one template member (let's call it T), and which has as its own member class type other defined as such:

Code:

typedef custom_allocator<T> other;

(Of course, custom_allocator refers to the name of the class of the custom allocator.)

The allocator must specify a size_type and a difference_type, which is probably best to typedef the type std::size_t as both. In addition, the following must be declared and defined as public methods (or otherwise accessible to range_map). my_type of the allocator you pass should be beneficii::range_map_item<key_type, mapped_type>. Note that you should not have to use these functions yourself; these are the functions used by the range_map class template to manage its memory:

Code:

size_type max_size() const;  //returns the maximum number of items 
                                                       //that can be allocated
my_type* allocate(size_type);  //allocates memory for my_type, with the 
                                                // total number to allocate
                                                // specified by size_type; returns pointer to 
                                                // start of my_type array.  If allocation fails,
                                                // then it needs to throw std::bad_alloc
                                                // Note that range_map always passes 1 to 
                                                //size_type parameter.
void construct(my_type*, const my_type&);  //constructs my_type object in
                                                             // place by copying the second
                                                             // parameter to the location pointer
                                                             // to by the first parameter
void destroy(my_type*);  //destroys the my_type object in the place 
                                       // pointed to by the parameter
void deallocate(my_type*, size_type);  //deallocates the memory used; 
                                                             // my_type* is the pointer and 
                                                             // size_type specifies the number of
                                                             // items to be deallocated 
                                                             // (always 1 in range_map).

//Also, with C++11, you can overload construct, but this won't work in/
// VC++ 2012, because it doesn't fully support C++11:

template<class ...args> void construct(my_type*, args&&...);  //like the 
                  // other construct, except that you can pass a variable number
                  // of arguments directly to my_type's constructor; again 
                  // my_type refers to the range_map_item's pointer.

//With VC++ 2012, you can perhaps overload it like this:

void construct<my_type*, my_type&&);

//In C++11, you need to overload the == operator:

bool operator==(custom_allocator<my_type> right) const;

Of course, if using C++11 you can also set the propagate typedefs (either tyepdef false_type or true_type as the propagator type to achieve the effect you want, though I believe if you don't put them in they default to false_type). range_map attempts to fully support the use of the propagator types.

BLAH

(Please be aware that if you use C++11-supported functions that they are written with the full capabilities of C++11 in mind; note that in IDE's like Visual C++ 2012, some features are still not supported, including true variadic templates. So emplace, for example (which uses a true variadic template), would be off limits to you in VC++ 2012.)

Anyway, you can keep inserting ranges, but there are restrictions. The insert/emplace function returns a std::pair with an iterator first and a bool second being members, just like with the std::map class's insert/emplace function. The first parameter of the insert/emplace functions is bool; if it's set to true, then any existing ranges that are subsets of the range to be inserted will be made sub-ranges of the range to be inserted, otherwise all existing ranges that are subsets of the range to be inserted will be destroyed and deallocated. If the range to be inserted does not intersect any existing ranges or is a perfect subset or perfect superset--but the range to be inserted cannot be coterminous with an existing range--of any and all existing ranges it intersects, then insertion will succeed and iterator will point to the left end point of the range that was inserted and bool will be set to true. Otherwise, bool is set to false, and iterator will point to past-the-end returned by end(), unless the range that was to be inserted was coterminous with an existing range, in which case iterator will point to the left end point of that existing coterminous range.

(You cannot insert a range that only partially intersects one or more existing ranges, unless the range to be inserted is a perfect superset of each range that the range to be inserted partially intersects. For example, if you have existing an range [15, 35), then you may insert [20, 30), as that would be a perfect subset of the first (or vice versa), and the latter would become a sub-range of the former. But if you have an existing range [15, 35), and you try to insert [25, 45), then insertion will fail because the latter would only partially intersect the former, without being a perfect superset of the former. If you have existing range [15, 35), then put in range [0, 50), that would work too, as the latter is a perfect superset of the former (whether this results in the deletion or the encapsulation of the former as a sub-range of the latter depends on the argument passed to the first parameter of the insert/emplace function; if true, then encapsulation occurs, but if false, then deletion of all sub-ranges of the range to be inserted occurs). One more thing, to allow for the creation of ranges that follow immediately one after another, since the right end point does not actually fall within its range, you could have an existing range [15, 35), and then successfully insert range [35, 55), for example, as the latter does NOT intersect the former, with 35 not falling within the range of the former.)

value_type in the class range_map is an end point (either the left end point or the right end point of a range_type object). Iterators in range_map point to value_type objects instead of range_type objects. The following public methods are available for use in value_type:

Code:

bool is_end_pt() const;  //tests whether this is the right end point
                                                // of the range; returns true if it is, false otherwise.
const key_type& cur_pt() const;  // returns const reference to key_type object of 
                                                    //this end point on the range.
const key_type& opp_pt() const;  // returns const reference to key_type object of
                                                     // the opposite end point on the range.
const key_type& start_pt() const;  // returns const reference to key_type object of
                                                      // left end point on the range.
const key_type& end_pt() const;  // returns const reference to key_type object of
                                                     // right end point on the range.
mapped_type& mapped();       // returns reference to mapped_type object of range
const mapped_type& mapped() const; // returns const reference to mapped_type 
                                                 // object of range
value_type& opposite_pt(); // returns reference to the end point opposite of the 
                                            //current point.
const value_type& opposite_pt() const; // returns const reference to the end 
                                                               //point opposite of the current point.
range_type& range(); // returns reference to the range_type object the current
                                                              // point is on.
const range_type& range() const; // returns const reference to the range_type 
                                                      //object the current point is on.

Like std::map, the iterators of range_map are bidirectional (i.e. you can increment and decrement, but you cannot do random access). Iteration goes in sequential order of the points that are in the range_map. For example, you are at the left end point of a range that has a sub-range, then when you increment, you will go to the left end point of that sub-range; otherwise, if the range does not have a sub-range, then incrementing would take you to the right end point of the range. Iteration that starts at the point returned by begin(), which is the left point of the highest level range with lowest left value, and goes through toward the end will go through the sequence of all the end points of all the existing ranges in order and will go up and down the ranges and sub-ranges as it moves through the end points; the next point you increment to will always have the cur_pt() return value that is greater than or equal to that of the previous point.

Anyway, how's that for an explanation?

EDIT: Fixed first paragraph

EDIT 2: Fixed line limitations on comments to make the method declarations more readable and to better organize the text.

EDIT 3: More fixing.

_________________
My blog:

http://beneficii.blogspot.com/

Last edited by beneficii on 25 May 2014, 5:04 pm, edited 5 times in total.

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 12:40 am

For those that read through this. Was my explanation helpful at all? I know I am bad at explaining my programming projects, especially if they are complex.

Perhaps, you'd like to see some code with the output to demonstrate range_map? Heck, maybe even get something that can write to a PNG file, and create imagery output like on a chart, to demonstrate how the ranges build up?

_________________
My blog:

http://beneficii.blogspot.com/

drh1138
Veteran
Veteran

Joined: 2 Dec 2012
Posts: 522

24 May 2014, 2:04 am

The opening paragraph was a little hard to navigate; I think if you had left out that entire parenthetical clause, explained the behavior as a right-open interval, and left it at that, it would have been a lot simpler. Anyone intelligent enough to make use of this and read the interval notation is going to know what that is, or is capable of finding out with minimal effort. One thing I learned when I was in school, was that when writing verbally, often simpler is better, and sometimes counter-intuitively, lets you explain complex ideas with greater ease. I certainly struggle with trying to be succinct (a good deal of any essay I write ends up trimmed).

What you've got is pretty good. The only other thing I would have added as an explanatory aid would have been the class' header. Some people (myself) are better with the "just show me the code" approach. Though I understand your explanation may have been an exercise in itself.

I'd certainly like to see a visual demonstration.

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 8:25 am

Sure. Here is inserting ranges into the container and then iterating through the end points of the ranges as well as giving the mapped value of the range each end point is on. The code (C++11):

Code:

#include "range_map.hpp"
#include <iostream>
#include <string>

int main() {

        using beneficii::range_map;   //range_map is in namespace beneficii
        typedef range_map<int, std::string>::range_type use_item;   //this is to 
                                  // typedef the range_type/range_map_item into something
                                  // simpler and compatible with range_map we're using;
        
        range_map<int, std::string> rm;  //creates range_map container object "rm", 
                                                            // which starts off empty; its key_type is
                                                            // int and its mapped_type is std::string
                                           // (we use default comparator and allocator)
        
        use_item my_item(0, 100, "aaa");  //creating range_map_item object
        rm.insert(true, my_item);               //inserting reference to it which will be
                                              //copied into the container.
        
        use_item my_item2(25, 75, "bbb");  //creating 2nd range_map_item object
        rm.insert(true, std::move(my_item2));  //here we move it into container
//note that this 2nd range is a perfect subset of the first, so it will be inserted.
        
        rm.insert(true, use_item(15, 85, "ccc"));//creating rvalue range_map_item object
//note that this is a perfect superset of the last item that was inserted.  Whether the
//last item is encapsulated as a sub-range of this item or is deleted depends on the
//value of the first argument.  Since it's true here, it is encapsulated as a sub-range
//of this item.  Were it false, however, then the last item and any other sub-range,
//including sub-ranges of the sub-ranges and so on and so forth, would have been
//deleted.
        
//below, we emplace the arguments to construct range_map_item directly in container.
        rm.emplace(true, 2, 13, "ddd"); 

//below, we use std::piecewise_construct to forward the arguments to the range_map_item.
//notice how there are 2 arguments for the mapped_type (std::string) constructor.
        rm.emplace(true, std::piecewise_construct, std::forward_as_tuple(75),
                   std::forward_as_tuple(85), std::forward_as_tuple(3, 'e'));

//before, all items inserted either did not intersect any ranges or were perfect subsets or
//perfect supersets of all previous items.  Here, though, [74, 84) partially intersects with
//the previous ranges [25, 75) and [75, 85) without being a perfect superset, so insertion will fail.  
        rm.emplace(true, 74, 84, "fff");
        
//looping through the end points of the ranges from the beginning till the end.  This is
//a special for loop for iterators of container classes that became available with C++11.
        for(auto& x : rm) {
             //print current end point and mapped value of this end point's range.
             //the mapped value will appear twice, letting you link the 2 end
             //points together as the range.
            std::cout << x.cur_pt () << "\t" << x.mapped() << std::endl;
        }

        return 0;
}

Output (note the absence of the fff range):

Code:

0       aaa
2       ddd
13      ddd
15      ccc
25      bbb
75      bbb
75      eee
85      eee
85      ccc
100     aaa

How's this?

_________________
My blog:

http://beneficii.blogspot.com/

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 10:54 am

Note, too, that for the question of the deletion of the sub-ranges, and the deletion of the sub-ranges of those sub-ranges, and so on and so forth, the class is designed to make sure, in its implementation, that if the sub-ranges are to be deleted, that continuous recursive function calling with no preexisting limits is not used (as that could cause the stack to overflow), while making sure to get into all the nooks and crannies of all the sub-ranges, all their sub-ranges, and all their sub-ranges and so on and so forth to ensure that all sub-range objects are destroyed and deallocated, and that none get lost in space leaking memory, so to speak.

The code to ensure this is a bit complicated (and has taken a lot of thinking, testing, and correction), but it's worth it, and since it's hidden in the implementation, performed primarily by private methods, other parts of the program don't need to worry about it, except that it simply works when they call public methods like clear() and erase() (when passing false to the second parameter) or when the range_map container goes out of scope and its destructor is called.

EDIT: Added important update for custom allocators in C++11 above (they need to overload the == operator).

_________________
My blog:

http://beneficii.blogspot.com/

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 2:20 pm

Anyway, does anyone want to give it a beta try?

It comes with 4 header files (with the code fully implemented in the header files; I know you're looking at me real angry-like): range_map.hpp, rm_iter.hpp, rm_node.hpp, and rm_base.hpp. Just put the header files in the same folder as your source files and use:

Code:

#include "range_map.hpp"

You don't need to directly include any of the other range files. The functions are meant to work a lot like map. There is the range_map public method erase:

Code:

iterator erase(const_iterator iter, bool decapsulate);

iter: const_iterator (iterator implicitly converts to this type) that points to either of the end points of the range to be erased.
decapsulate: If true, then all sub-ranges of the range to be erased are preserved and will be "rescued" from the range to be deleted; otherwise, all sub-ranges, all their sub-ranges, and so on and so forth are also erased.
Return value: iterator to next end point following the right end point of the range erased, if there is one; otherwise, an iterator equivalent to end() is returned.

If decapsulate were set to true, then any iterator that pointed to either end point of the range erased or any of its sub-ranges (whether they were erased or not) becomes invalid; all other iterators are left untouched. The same is true for the iterators pointing to any points of the ranges that become sub-ranges (or are deleted) when an item is inserted or emplaced.

_________________
My blog:

http://beneficii.blogspot.com/

Last edited by beneficii on 24 May 2014, 2:47 pm, edited 1 time in total.

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 2:33 pm

Here are some methods that take a single point and work the ranges with it:

There are upper_bound methods:

Code:

iterator upper_bound(const key_type& value);
const_iterator upper_bound(const key_type& value) const;

value: Value to find the upper bound of.
Return value: an iterator that points to the least end point, be it a left end point or a right end point, that is greater than value (the "upper bound"). Returns iterator equal to end() if no such end point exists.

There are lower_bound methods:

Code:

iterator lower_bound(const key_type& value);
const_iterator lower_bound(const key_type& value) const;

value: Value to find the lower bound of.
Return value: an iterator that points to the least end point, be it a left end point or a right end point, that is greater than or equal to value (the "lower bound"). Returns iterator equal to end() if no such end point exists.

There are also intersecting_ranges methods:

Code:

std::stack<iterator> intersecting_ranges(const key_type& value);
std::stack<const_iterator> intersecting_ranges(const key_type& value) const;

value: Value to find all the ranges that intersect it.
Return value: Stack of iterators that point to the left end points of all existing ranges that intersect value; the deepest sub-range is placed at the top of the stack, and as you pop each iterator off the stack, you get the next less deep range until you come to the highest level at the bottom of the stack. Stack will be empty if no ranges intersecting value are found.

_________________
My blog:

http://beneficii.blogspot.com/

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 6:51 pm

Made modification of class so that iterators to end points of sub-ranges do not become invalid when the sub-ranges are encapsulated or decapsulated.

_________________
My blog:

http://beneficii.blogspot.com/

Last edited by beneficii on 24 May 2014, 7:58 pm, edited 1 time in total.

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 7:57 pm

Does anyone know the best place to post the header files? Post them here on this board? Only problem is that while 3 of the header files are fairly short, range_map.hpp has 1270 lines, so that would probably be problematic.

Anyone know where I can store it?

_________________
My blog:

http://beneficii.blogspot.com/

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

24 May 2014, 11:36 pm

OK, new thing about range_type. Once it's in the container, you can only get a const reference to it. I realized this when I wanted to allow range_type to use move semantics, which opens a problem:

If you can get a non-const reference to it, then you could move the range from the container to another range_type object, thus causing the destructor getting called on the range in the container and messing everything up in the container.

Once it's in the container, you cannot modify range_type other than to erase it.

EDIT: On second thought, I will still let you get a non-const reference of the mapped_type object; if you move that out, oh well. As long as the 2 key_type objects stay as they are, the container will still function.

_________________
My blog:

http://beneficii.blogspot.com/

LoveNotHate
Veteran
Veteran

Joined: 12 Oct 2013
Age:44
Posts: 2,002
Location: Northern USA

25 May 2014, 3:41 am

range maps ...
allocators ...
containers ....

My head is spinning :compress:

I would of done it much less eloquently with arrays

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

25 May 2014, 4:49 pm

Created visual representation of range_map by putting in random ranges (most of which were rejected). (EDIT: Will also edit first post to say that left < right must be true for the range to be valid.) The code mentioned in this thread is what I used to produce the original BMP image:

http://www.wrongplanet.net/postt259693.html

Here's the code:

Code:

#include "range_map.hpp"
#include "bmp_24.hpp"
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <random>
#include <string>
#include <ctime>

//for brevity in later code, typedef'ing a lot of stuff
using beneficii::range_map;
using std::map;
using std::vector;
using std::default_random_engine;
using std::uniform_int_distribution;
typedef range_map<unsigned long, unsigned long> rm_type;
typedef map<int, std::string> map_type;
typedef default_random_engine gen_type;
typedef uniform_int_distribution<unsigned long> rand_type;
typedef rm_type::range_type range_type;
typedef rm_type::size_type size_type;

//stores the range that was attempted to be inserted and the result
//see below for lists
struct vec_test_struct {
    vec_test_struct(range_type range, int result) :
    range(range), result(result) {}
  
    range_type range;
    int result;
};

//sorts the vector first by result then by order in which test range was created
struct testing_comp : std::binary_function<vec_test_struct, vec_test_struct, bool> {
    bool operator()(const vec_test_struct& a, const vec_test_struct& b) {
        if(a.result < b.result) return true;
        if(b.result < a.result) return false;
        return a.range.mapped() < b.range.mapped();
    } 
};

typedef vector<vec_test_struct> v_type;

int main() {
        
        rm_type rm;

//these are the different types of results
        map_type results;
        results.emplace(0, "success!");
        results.emplace(1, "coterminous");
        results.emplace(2, "intersects but not subset/superset");
        results.emplace(3, "left key greater than or equal to right key");
                
//we're going to attempt insertion of 255 ranges, so go ahead and have vector
//reserve that many
        const size_type num_items = 255;
        v_type vec;
        vec.reserve(num_items);
        
//this is the absolute width of the range_map (and of the image)
//sets up pseudo-random number generator to generate numbers
//falling within the absolute width of the range_map (0, 1111)
        const unsigned long max_num = 1111;
        gen_type gen(std::time(nullptr));
        rand_type rand(0, max_num);
        
//create a range each time and attempt insertion
        for(size_type i = 0; i < num_items; ++i) {
            range_type my_range(rand(gen), rand(gen), i);

//if left doesn't come before right, then range is invalid
            if(my_range.get_left() >= my_range.get_right()) {
                vec.emplace_back(my_range, 3);  //keep it for statistics
                continue;
            }

//attempts to insert copy of range and gets back the result
//we enter a copy, because we still want to keep the range in this function
            std::pair<rm_type::iterator, bool> ret = rm.insert(true, my_range);
            if(ret.second) {
                vec.emplace_back(my_range, 0);  //was a success; keep for stats
                continue;
            }

//check if it wasn't inserted b/c of intersecting without being sub/superset.
            if(ret.first == rm.end()) {
                vec.emplace_back(my_range, 2); 
                continue;
            }
            vec.emplace_back(my_range, 1);
        }
        
//sort by results then order of creation, then print the statistics out
        std::sort(vec.begin(), vec.end(), testing_comp());
        int cur_result = -1;
        for(auto& x : vec) {
            if(x.result != cur_result) {
                cur_result = x.result;
                std::cout << std::endl << results[cur_result] << std::endl;
            }
            std::cout << x.range.mapped() << "\t(" << x.range.get_left() << ", "
                    << x.range.get_right() << ")" << std::endl; 
        }
        
//print number of items currently in range_map container
        std::cout << std::endl << "size: " << rm.size() << std::endl << std::endl;
        
        const unsigned long img_hgt = 1000;  //height of image
        const unsigned long rng_hgt = 40;      //height of each row of ranges
        const b24_rgb bkg = {0x00, 0x00, 0x00};  //background color (r,g,b)
        
        bmp_24 bm(max_num, img_hgt, bkg);   //create bmp object
        
//colors to use for each row, using a modulus to go back to the
//beginning once we've used the last color.
        const b24_rgb the_colors[] = {
            {0x88, 0x00, 0x00},
            {0x00, 0x88, 0x00},
            {0x00, 0x00, 0x88},
            {0x88, 0x88, 0x00},
            {0x88, 0x00, 0x88},
            {0x00, 0x88, 0x88}
        };
        
//to use for the modulus
        size_type colors_num = sizeof(the_colors) / sizeof(b24_rgb);
        
        b24_rgb lft_pt_c = {0xff, 0xff, 0xff};   //color for the left end point of range
        b24_rgb rgt_pt_c = {0x55, 0x55, 0x55};  //color for the right end point of range
        
//keep going up and down the ranges with the iterator to the points; current row increases when
//we get to a left end point; it decreases when we get to a right end point;
//draw the current range on the appropriate row when we get to left end point, with its x position
//in pixels being equivalent to its left end point and its width in pixels being equivalent to the 
//difference of the right and left end points.  Also draw starting and ending point.
        unsigned long cur_level = -1;
        for(auto& x : rm) {
            std::cout << x.cur_pt() << '\t' << x.mapped() << std::endl;
            if(!x.is_end_pt()) {
                ++cur_level;
                unsigned long cur_hgt = rng_hgt * cur_level;
                unsigned long cur_wid = x.end_pt() - x.start_pt();
                bm.rect(x.start_pt(), cur_hgt, cur_wid, rng_hgt,
                        the_colors[cur_level % colors_num]);
                bm.rect(x.start_pt(), cur_hgt, 1, rng_hgt, lft_pt_c);
                bm.rect(x.end_pt(), cur_hgt, 1, rng_hgt, rgt_pt_c);
            } else {
                --cur_level;
            }
        }
        
        bm.save("c:\\gg\\tester.bmp");   //save bitmap to file
        
        return 0;
}

A lot of other stuff gets done, too.

But this is what one image of the ranges started as. Notice how the super-ranges go before the sub-ranges. I converted the image to PNG in MSPaint:

[img][800:1000]http://i62.tinypic.com/6sw4qs.png[/img]

_________________
My blog:

http://beneficii.blogspot.com/

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

25 May 2014, 7:37 pm

OMG. Just fixed a total insidious bug that's not a bug in a regular map but is in a range_map.

It's this set of statements in this order:

Code:

               _node_replace(_n, _child);
               if(_node::_is_root(_n) && _child != nullptr) {
                   _child->_color = _node::_black;
               }

This replaces _n node pointer with child node pointer; if _n is the root and child is not a null pointer, then child should be set to color black, due to being the new root now.

Now in map this works because the only thing that will make _node::_is_root(_n) return true is if _n's parent is a null pointer. But in range_map, there is another situation where _n would be the root: where _n == _n->_parent->_subtree, basically, where _n is the root of its parent's subtree. You see, map don't got nothing like subtrees so it's not a concern, but in range_map, it's the source of our error. Why? Because if _n == _n->_parent->_subtree was true before _node_replace was called, then it will be false after it is called, because now _n->_parent->_subtree == child, instead of _n, so _child won't be set to black, even though it's at the root of its subtree--the node at the root of each tree, subtree or not, needs to be black, or stuff don't work.

So it's necessary to have _node_replace come after testing if _n is the root, not before:

Code:

               if(_node::_is_root(_n) && _child != nullptr) {
                   _child->_color = _node::_black;
               }
               _node_replace(_n, _child);

Problem solved. Before this fix, with the generation of tons of random ranges, about a fourth of the time the program will fail. Now I keep running and have not seen any failures since then.

_________________
My blog:

http://beneficii.blogspot.com/

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

26 May 2014, 6:56 pm

Alright! You may download a version of the range_map class here:

http://www.beneficii.net/rm_test.zip

The 4 header files should go in the same folder as your project files, for the project you're working on. They're not an "official" library yet, so that's why. All of the code is implemented in the header files, so no there are no other files to worry about.

The program should simply include "range_map.hpp" and create range_map which is in namespace beneficii.

Ask me any questions about using it.

Also, if you wanted to use the bmp_24 class as mentioned in that other thread, you can download it here:

http://www.beneficii.net/bmp_24.zip

All code is implemented in the 2 header files. Simply put in your project's folder and include "bmp_24.hpp" and you can use the POD-struct b24_rgb to set up the colors and the class bmp_24 to implement the bitmap.

EDIT: You can also download this test (which I posted an earlier version of up this page) to demonstrate the class for yourself:

http://www.beneficii.net/rmbmp_test.cpp

Remember that you need the headers from rm_test.zip and bmp_24.zip in the same directory for it to work. You also need to be using C++11 for it to work. You can edit info like the bmp_filename at the top to suit it for your purposes.

_________________
My blog:

http://beneficii.blogspot.com/

beneficii
Veteran
Veteran

Joined: 10 May 2005
Age:31
Posts: 4,766

27 May 2014, 9:27 am

Does anyone have any feedback?

_________________
My blog:

http://beneficii.blogspot.com/

Page 1 of 2 [ 25 posts ] Go to page 1, 2 Next

Jump to:

range_map: new container class for C++ Post Reply New Topic

range_map: new container class for C++