1mdds 1.7.0 2 3* trie_map 4 5 * added copy and move constructors. 6 7 * added a variant of find() method that returns a mutable iterator object. 8 The user can now update the value associated with the key directly via the 9 iterator object. 10 11* packed_trie_map 12 13 * added copy and move constructors. 14 15 * added load_state() and save_state() methods to allow loading state from 16 and saving state to binary files. 17 18mdds 1.6.0 19 20* multi_type_vector 21 22 * switched to using binary search on block position lookup, which 23 significantly improves element access performance in general, at the 24 expense of slight performance degradation on block shifting. 25 26* added support for lcov, to visualize test coverage. 27 28mdds 1.5.0 29 30* documentation 31 32 * moved the documentation hosting to readthedocs.io, and adjusted the build 33 steps. 34 35 * moved the API incompatibility notes from README to the rst doc. 36 37 * added the overview section for flat_segment_tree. 38 39* multi_type_vector 40 41 * fixed the static get(const const_position_type& pos) method for the 42 boolean_element_block, by adding specialization for it to work around the 43 issue with std::vector<bool> not having the at() method. 44 45 * fixed an issue with the const position() method not returning a valid end 46 position the same way the non-const variant does. 47 48 * added steps to traverse blocks backward from the postiion specified in the 49 position hint. This may result in improved performance in some 50 situations. 51 52 * the standard integer blocks now use fixed size integer types i.e. 53 54 * (u)int8_t 55 56 * (u)int16_t 57 58 * (u)int32_t 59 60 * (u)int64_t 61 62 * The numeric_element_block has been renamed to double_element_block. 63 64 * added new block type to store float element values. 65 66* general 67 68 * added gdb pretty printers that prints the contents of the data structures. 69 70mdds 1.4.3 71 72* documentation 73 74 * added details on how to use two type of iterators with 75 flat_segment_tree. 76 77 * added new section to describe how to use mtv::collection to iterate 78 through multiple multi_type_vector instances as a single collection 79 in the direction orthogonal to the direction of the individual 80 vectors. 81 82 * added new page for R-tree. 83 84* flat_segment_tree 85 86 * fixed invalid memory access issue related to the swap() method which 87 previously did not swap the non-leaf node pool store. The invalid 88 memory access may occur after the contents of two instances get 89 swapped, one instance get destroyed then the caller calls 90 search_tree() on the other instance still alive. 91 92mdds 1.4.2 93 94* all 95 96 * fixed CXXFLAGS incorrectly being overwritten. 97 98 * addressed a number of Coverity issues. 99 100mdds 1.4.1 101 102* all 103 104 * fixed all warnings on shadowed variables. 105 106* multi_type_matrix 107 108 * all of its walk() methods now return either a copied or moved 109 instance of the function object passed in as an input argument. 110 Previously these methods had no return values. 111 112mdds 1.4.0 113 114* rtree (new) 115 116 * new data structure designed for optimal storage and query 117 performance on multi-dimensional spatial data. The structure allows 118 storage of both point and extent-based boundaries as keys associated 119 with values. 120 121* multi_type_vector 122 123 * mtv::elemnt_block now has the following methods: data(), cbegin(), 124 cend(), crbegin() and crend(). 125 126 * multi_type_vector now has cbegin(), cend(), crbegin(), and crend() 127 methods. 128 129 * some unnecessary user-provided special members have been removed to 130 avoid warnings with -Wdeprecated-copy with GCC 9. 131 132* multi_type_matrix 133 134 * all of its walk() methods now allow in-line lambdas to be used, by 135 not taking a reference of the function object parameters. 136 137mdds 1.3.1 138 139* flat_segment_tree 140 141 * fixed a bug that caused an assertion error when inserting a 142 out-of-bound segment whose start value equals the max key value. 143 144mdds 1.3.0 145 146* multi_type_vector 147 148 * changed the primary block array storage to remove additional 149 indirection, for improved memory locality. 150 151mdds 1.2.3 152 153* all 154 155 * changed the configure script to use --docdir unmodified. 156 157* flat_segment_tree 158 159 * added a segment iterator whose node value consists of the start 160 and end keys and the value associated with each segment. its 161 start and end positions can be retrieved via begin_segment() and 162 end_segment() methods. 163 164mdds 1.2.2 165 166* flat_segment_tree 167 168 * fixed a bug that would cause segmentation faults with the insert() 169 method with out-of-bound segment value pair. 170 171mdds 1.2.1 172 173* multi_type_vector 174 175 * added size() method to the element block type, which returns the 176 actual size of the element block, instead of the cached size value 177 stored in the parent structure that stores the element block. 178 179 * fixed a double-deletion bug in the swap() method which would 180 triggered when used with a managed element block. 181 182* mtv::collection 183 184 * fixed collection iterator's get() method to properly return values 185 from the boolean element block. 186 187mdds 1.2.0 188 189* packed_trie_map 190 191 * added begin() and end() methods that return read-only iterators. 192 193 * find() method now returns a const_iterator instance. 194 195 * prefix_search() method now returns a search_results instance that 196 can be iterated. 197 198 * null value no longer needs to be passed to the constructor. 199 200 * find() and prefix_search() now have a variant that can take a key 201 value that is of key_type directly. 202 203* trie_map 204 205 * added begin() and end() methods that return read-only iterators. 206 207 * find() method now returns a const_iterator instance. 208 209 * prefix_search() method now returns a search_results instance that 210 can be iterated. 211 212 * null value no longer needs to be passed to the constructor. 213 214 * find(), insert, and prefix_search() now have a variant that can 215 take a key value that is of key_type directly. 216 217* sorted_string_map 218 219 * fix build failure with _GLIBCXX_DEBUG defined. 220 221* multi_type_vector 222 223 * remove compiler warning about shadowed variable. 224 225 * added a supplemental class mdds::mtv::collection which allows 226 multiple multi_type_vector instances of the same length to be 227 grouped together in order to iterate through their elements 228 sideways. 229 230 * a variant of advance_position() static method that takes 231 const_position_type has been added. 232 233 * const_position_type advance_position(const const_position_type& pos, int steps) 234 235* multi_type_matrix 236 237 * matrix_position() is now a const method. 238 239 * the sub-matrix variant of walk() method now throws size_error 240 exception when invalid start and end positions are passed. 241 242 * slight performance improvement with the sub-matrix variant of 243 walk() method that involves multiple column traversal. 244 245 * added 2 new variants of walk() methods that allow parallel walking 246 with another matrix instance. 247 248 * template<typename _Func> 249 void walk(_Func& func, const multi_type_matrix& right) const 250 251 * template<typename _Func> 252 void walk(_Func& func, const multi_type_matrix& right, const size_pair_type& start, const size_pair_type& end) const 253 254 * improved performance of copy() and resize() methods. 255 256 * added a variant of copy() that takes an array of values. 257 258 * template<typename _T> 259 void copy(size_type rows, size_type cols, const _T& it_begin, const _T& it_end) 260 261 * integer type has been added to the list of types the matrix can 262 store. In conjunction with this change, what was formerly known 263 as the string trait structure is now known as the matrix trait, 264 which specifies the actual integer type the matrix stores. 265 266* point_quad_tree 267 268 * search_result has been renamed to search_results. 269 270mdds 1.1.0 271 272* all 273 274 * switched our build system to using automake. 275 276* packed_trie_map (new) 277 278 * new data structure that implements a trie also known as a prefix 279 tree. This implementation requires all key values be known at 280 construction time, after which its content is considered 281 immutable. Internally it packs all its nodes in a single 282 contiguous array for space and lookup efficiencies. 283 284* trie_map (new) 285 286 * new data structure that implements a trie. It works similar to 287 packed_trie_map except that this version is mutable. 288 289* multi_type_matrix 290 291 * added a variant of walk() that takes the upper-left and 292 lower-right corners to allow walking through a subset of the 293 original matrix. 294 295* multi_type_vector 296 297 * fixed incorrect return values of the increment and decrement 298 operators of in-block iterators. They would previously return a 299 value_type pointer which did not conform to the behaviors of STL 300 iterators. 301 302 * added support for custom event handlers for element block 303 acquisitions and releases. 304 305* flat_segment_tree 306 307 * fixed incorrect return values of the increment and decrement 308 operators of its leaf-node iterators as in multi_type_vector's 309 fix. 310 311* sorted_string_map 312 313 * significantly improved the performance of its find() method by 314 switching from using linear search to using binary search. The 315 improvement is especially visible with a large number of elements. 316 317mdds 1.0.0 318 319* all 320 321 * introduced API versioning to ease parallel installation of API 322 incompatible versions. Version 1.0.0 will have an API versoin of 323 1.0. 324 325 * C++11 is now a hard requirement. 326 327 * added API documentation via Doxygen, Sphinx and Breathe. 328 329* mixed_type_matrix 330 331 * officially removed for good in favor of multi_type_matrix. 332 333* multi_type_vector 334 335 * added memory usage reduction by conditionally shrinking the 336 capacity of the underlying vector containers. 337 338 * added slight performance gain by revising block adjustment policy 339 during splitting of blocks. 340 341* sorted_string_map 342 343 * fixed a bug where a non-matching key was incorrectly returned as a 344 matching key. 345 346mdds 0.12.1 347 348* flat_segment_tree 349 350 * removed construction-from-int requirement from value_type to allow 351 non-numeric types to be stored. 352 353* multi_type_vector 354 355 * added static method advance_position() to allow incrementing or 356 decrementing the logical position of a position_type object: 357 358 * position_type advance_position(const position_type& pos, int steps) 359 360mdds 0.12.0 361 362* segment_tree 363 364 * removed pointer requirement from value_type to allow non-pointer 365 type to be stored. 366 367* multi_type_vector 368 369 * fixed a bug in the equality operator method. 370 371mdds 0.11.2 372 373* multi_type_vector 374 375 * fixed various memory leaks associated with the set() method when a 376 value overwrites an existing element in a managed block. 377 378mdds 0.11.1 379 380* all 381 382 * fixed a large number of outstanding defects reported by Coverity 383 Scan. 384 385* multi_type_vector 386 387 * fixed 2 cases of double-free bug in the variant of swap() that 388 allows segmented swapping. 389 390mdds 0.11.0 391 392* sorted_string_map (new) 393 394 * new data structure to support efficient mapping of textural keys 395 to numeric values when the key values are known at compile time. 396 397* multi_type_vector 398 399 * fixed a bug in transfer() where two adjacent blocks of identical 400 type would fail to be merged in some circumstances. 401 402 * added shrink_to_fit() to allow trimming of any excess capacity 403 from all non-empty blocks. 404 405 * fixed a double-free bug in the variant of swap() that allows 406 segmented swapping. 407 408 * improved the exception message when the block position lookup 409 fails to find valid block position, to make it easier to debug. 410 411mdds 0.10.3 412 413* multi_type_vector 414 415 * added 2 variants of release_range() that take start and end positions, 416 to allow releasing of elements in specified interval. One of the 417 variants takes iterator as a block position hint. 418 419 * iterator release_range(size_type start_pos, size_type end_pos) 420 421 * iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos) 422 423 * added push_back() and push_back_empty(), to allow efficient way to 424 append new values to the end of the container. 425 426 * template<typename _T> 427 iterator push_back(const _T& value) 428 429 * iterator push_back_empty() 430 431mdds 0.10.2 432 433* multi_type_vector 434 435 * fixed a bug in transfer() that would trigger an assertion and 436 eventually lead to a crash. The problem occurred when a range of 437 data to be transferred spanned over 2 blocks and consisted of the 438 lower part of an upper block and the upper part of a lower block. 439 440mdds 0.10.1 441 442* multi_type_matrix 443 444 * added a variant of set_empty() that takes an additional length 445 parameter. 446 447 * void set_empty(size_type row, size_type col, size_type length) 448 449mdds 0.10.0 450 451* flat_segment_tree 452 453 * significant performance improvement on build_tree() and 454 search_tree(), by optimizing the non-leaf node object generation 455 and storage to achieve better locality of reference. 456 457* segment_tree 458 459 * slight performance improvement on build_tree(), as a result of the 460 optimization done for flat_segment_tree since these two structures 461 share the same tree generation code. 462 463* multi_type_vector 464 465 * improved debug message on mis-matched block types (only when 466 MDDS_MULTI_TYPE_VECTOR_DEBUG is defined). 467 468mdds 0.9.1 469 470* multi_type_vector 471 472 * added several convenience methods for position objects. 473 474 * performance improvement on setting array values. 475 476 * added new constructor that takes an array of values as initial 477 element values. 478 479* multi_type_matrix 480 481 * setter methods that take a position object to also return a 482 position object. 483 484 * added several convenience methods for position objects. 485 486 * added new constructor that takes an array of values as initial 487 element values. 488 489mdds 0.9.0 490 491* multi_type_vector 492 493 * added another block function template to make it easier to declare 494 container with 3 custom element types. 495 496 * added two variants of release(): 497 498 * template<typename _T> iterator 499 release(size_type pos, _T& value) 500 501 * template<typename _T> iterator 502 release(const iterator& pos_hint, size_type pos, _T& value) 503 504 * added a variant of release() that takes no arguments. This one 505 releases all elements and makes the container empty afterward. 506 507 * added a new variant of position() that takes const_iterator as 508 position hint. 509 510 * std::pair<const_iterator, size_type> 511 position(const const_iterator& pos_hint, size_type pos) const 512 513 * fixed a memory leak in 514 515 * set(size_type pos, const _T& it_begin, const _T& it_end). 516 517 * added compile-time macro MDDS_MULTI_TYPE_VECTOR_USE_DEQUE to allow 518 users to specify std::deque as the underlying data array. By 519 default, multi_type_vector uses std::vector as the underlying data 520 array container. 521 522 * added a new variant of swap() that allows partial swapping of 523 content with another container. 524 525 * added static block type identifier so that the numeric block type 526 ID can be deduced from the block type directly. 527 528 * value_type (which is a type of object returned when dereferencing 529 an iterator) now stores 'position' which is the logical position 530 of the first element of a block. 531 532 * added position_type and const_position_type which are typedefs to 533 the return types of position() methods. 534 535* multi_type_matrix: 536 537 * get_numeric(), get_boolean(), and get_string() are made more 538 efficient. 539 540 * added position() method that returns a reference object to an 541 element (position object). 542 543 * added variants of get_numeric(), get_boolean() and get_string() 544 that retrieves elements from position objects. 545 546 * added variants of set() that sets new element values via position 547 objects. 548 549mdds 0.8.1 550 551* multi_type_vector 552 553 * fixed a bug in the erase() method where adjacent blocks of the 554 same type would fail to merge after the erase() call. 555 556 * add a variant of the position() method that takes an iterator as 557 positional hint. Note that there is no variant of position() that 558 takes const_iterator. 559 560mdds 0.8.0 561 562* all 563 564 * added .pc file for pkg-config. 565 566* flat_segment_tree 567 568 * changed the return type of search_tree from bool to 569 std::pair<const_iterator,bool>, to make it consistent with the 570 search() method. Note that this is an API-incompatible change. 571 572* multi_type_vector 573 574 * added char and unsigned char types to the standard types supported 575 by default. 576 577 * added position() member method that takes a logical element 578 position and returns a pair of block iterator where the element 579 resides and its offset within that block. 580 581 * added at() static member method to the data block, which calls the 582 at() method of the underlying std::vector container. 583 584 * added release() member method to allow caller to release an object 585 stored inside a managed block. 586 587 * added two templates to ease creation of custom element block 588 functions when using one or two custom element types. 589 590 * added transfer() member method to allow elements in a specified 591 range to be transferred from one container to another. When 592 transferring elements stored in a managed element block, the 593 ownership of those elements is also transferred. 594 595mdds 0.7.1 596 597* multi_type_vector 598 599 * fixed a bug in set_empty() where emptying a whole or partial block 600 would fail to merge its adjacent block(s) even when they are also 601 empty. 602 603mdds 0.7.0 604 605* multi_type_vector 606 607 * add variants of set() methods (both single- and multi-value) 608 insert(), set_empty() and insert_empty() methods that take an 609 iterator as an additional position hint parameter for block lookup 610 speed optimization. 611 612 * add support for non-const iterators which allow the client code to 613 modify values directly from the iterators. 614 615 * set() methods (both single- and multi-parameter variants), 616 set_empty(), insert() and insert_empty() methods now return 617 iterator that references the block to which the values are set or 618 inserted. 619 620 * fixed bugs in set() method (single-parameter variant) which would 621 insert a new block at incorrect position. 622 623 * fixed bugs in set() method (multi-parameter variant) which would 624 fail to merge neighboring blocks of identical type under certain 625 conditions. 626 627mdds 0.6.1 628 629* all 630 631 * use property files in the Visual Studio project files, to share 632 some of the common custom build variables across all projects. 633 634 * various build fixes and compiler warning eliminations. 635 636 * fixed link error with boost 1.50. 637 638 * fixed make installer script which previously would not install 639 mdds/compat headers. 640 641* flat_segment_tree 642 643 * fixed a bug in its iterator implementation, which previously would 644 always treat the last valid position before the end position as 645 the end position. This fix affects both in const_iterator and 646 const_reverse_iterator. 647 648mdds 0.6.0 649 650* all 651 652 * added MSVS Solution file, to make it easier to build unit test 653 programs on Windows. 654 655* mixed_type_matrix 656 657 * improved performance of size() method by caching it. 658 659* multi_type_vector (new) 660 661 * new data structure to support efficient storage of data of different 662 types. 663 664* multi_type_matrix (new) 665 666 * new data structure to eventually replace mixed_type_matrix. It uses 667 multi_type_vector as its backend storage. 668 669mdds 0.5.4 670 671* segment_tree 672 673 * fixed build breakage, to allow it to be buildable when UNIT_TEST 674 is not defined. 675 676 * fixed a crasher with MSVC when comparing iterators of empty 677 search_result instances. 678 679* point_quad_tree 680 681 * fixed a bug where de-referencing copied search_result iterators 682 would return an uninitialized node data. 683 684mdds 0.5.3 685 686* mixed_type_matrix 687 688 * re-implemented the filled storage for better performance, with two 689 separate implementations for zero and emtpy matrix types. The 690 newer implementation should improve object creation time 691 considerably. 692 693mdds 0.5.2 694 695* flat_segment_tree 696 697 * fixed a crash on assignment by properly implementing assignment 698 operator(). 699 700 * fixed several bugs in shift_right(): 701 702 * shifting of all existing nodes was not handled properly. 703 704 * leaf nodes were not properly linked under certain conditions. 705 706 * shifting with skip node option was not properly skipping the 707 node at insertion position when the insertion position was at 708 the leftmost node. 709 710 * implemented min_key(), max_key(), default_value(), clear() and 711 swap(). 712 713 * fixed a bug in operator==() where two different containers were 714 incorrectly evaluated to be equal. 715 716 * added quickcheck test code. 717 718mdds 0.5.1 719 720 * fixed build issues on Windows, using MSVC compilers. 721 722mdds 0.5.0 723 724 * flat_segment_tree's search methods now return a std::pair of 725 const_iterator and bool, instead of just returning bool. 726 727 * fixed a weird enum value mis-handling with mixed_type_matrix when 728 compiled with MSVC++. 729 730 * added new insert() method to flat_segment_tree that takes a 731 positional hint in order to speed up insertion speed. Also, all 732 three insert() methods now return the start position of the 733 segment that an inserted segment belongs to. 734 735 * slight performance improvement on the insert methods of 736 flat_segment_tree. 737 738 * slight performance improvement on the iterators of 739 flat_segment_tree. 740 741 * re-organized the structure of flat_segment_tree to split it into 742 multiple headers. 743 744 * properly support prefix, docdir, includedir configure options. 745 746 * support DESTDIR environment variable for make install. 747 748mdds 0.4.0 749 750 * implemented mixed_type_matrix. 751 752mdds 0.3.1 753 754 * added support for boost::unordered_map (boost) and std::hash_map 755 (stlport) in addition to C++0x's std::unordered_map. 756 757mdds 0.3.0 758 759 * implemented point_quad_tree. 760 761mdds 0.2.1 762 763 * added example files on how to use these data structures. 764 765 * fixed a bug in segment_tree::search_result object, to make it work 766 with empty result set. 767 768 * fixed segment_tree to make it really usable outside of unit test 769 code. 770 771mdds 0.2.0 772 773 * other general performance improvements. 774 775 * lots of code cleanups. 776 777 * support for search result iterator in segment_tree and 778 rectangle_set, for better search performance. 779 780 * implemented rectnagle_set. 781 782 * fixed lots of bugs in the segment_tree implementation. 783 784mdds 0.1.2 785 786 * implemented segment_tree. 787 788 * node_base class is now without virtual methods to avoid vtable 789 generation. 790