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