TypeScript-STL v1.4.3
TreeMultiSet & TreeMultiMap
Faster key access
Until the v1.4 update, time complexity of key access on TreeSet and TreeMap had been O(log N) ~ O(N). When keys are not duplicated (unique), then those time complexity had been O(log N), however, the more duplicated key exists and you try to access to the duplicated key, then the time complexity had been more converged to the O(N).
However, since the v1.4 update, even how much duplicated key exists, time complexity of key access on TreeSet and TreeMap are exactly O(log N). Thus, key access on TreeSet and TreeMap are much faster than before.
Exact arrangement
Until the v1.4 update, when lots of duplicated key are inserted, then arrangement of the elements had been twisted and it even had caused the mis-structuration on the RB-Tree.
Since this v1.4 update, the mis-arrangement problem is clearly fixed. The RB-Tree doesn't be mis-structured more. Duplicated key elements, their sequence follows the word: "Enter first, then be the front". The principle is always be kept without reference to the relationships of nodes at the RB-Tree.
- Of course, you can twister the sequence manually by the insertion hint.
Allow comparisons function who covers the equal.
The default comparison function of Tree-based containers are std.less and you also can specify the comparison function as you want.
However, the C++ (original) STL doesn't allow to specifying the comparison function who covers the equal. The specified comparison function must not cover the equal and if you violate the rule, then it causes not compile error, but the run-time error.
The violation doesn't be detected on compile level. Thus, when you specify a comparison function who covers the equal and you try to insert some duplicated key elements, then you may understand that you'd violated the rule by meeting the critical run-time error. I think it is very dangerous and it's a type of wrong design in C++/STL.
- I can understand the violation of comparison function who cover
equalin TreeSet and TreeMap is right who doesn't allow the duplicated key element. However, they also can't detect the violation in the compilation level, thus it's still dangerous. - However, the TreeMultiSet and TreeMultiMap, who allow duplicated key, I don't understand the reason why.
In my TypeScript-STL, I allow you to specifying the comparison function to cover the equal. Some expert developers, who know the RB-Tree well, may have a question: "If the comparison function can cover the equal, then how you prevent the twistering problem in the RB-Tree?" I solved the problem like below code:
Development Environments
Visual Code
Since the v1.4 update, TypeScript-STL uses Visual Studio Code (VSCode) instead of the previous Visual Studio. Configuration file for the Visual Code is placed on the vscode/launch.json
Builder
Since v1.4 update, instead of Visual Studio compiles, tests and prepares distribution by one click, build.js will substitute the automation role.
By executing the build.js with the command node build, below steps will be proceeded:
- Compile TypeScript sources
1.1. At first, compile with (API) comments and generates the definition (d.ts) file.
1.2. Re-compile, excluding (API) comments and the definition file (jsonly).- When compile error occurs, then the builder will be halted.
- Execute testing unit.
- The testing unit will validate source codes with some testing functions.
- When error occurs, then the builder will be halted, too.
- Prepare distribution.
- Arrange built files to release.
Comments are only placed in the header (d.ts)
I decided to shrink body (js) file's size, by removing comments, even though it needs the duplicated compilation.
Thus, since the v1.4 update, (API) comments are only wrote on header, the definition (d.ts) file. The body (js) file does not contain any comment from now on, to shrink its file size.