tstl

TypeScript-STL (Standard Template Library, migrated from C++)

MIT License

Downloads
65.6K
Stars
586
Committers
5
View Code on GitHub
Ecosystems: TypeScript

Bot releases are hidden (Show)

tstl - v3.0.0 Latest Release

Published by samchon 7 months ago

What's Changed

Full Changelog: https://github.com/samchon/tstl/compare/v2.5.13...v3.0.0

tstl - v2.5.13

Published by samchon almost 2 years ago

What's Changed

New Contributors

Full Changelog: https://github.com/samchon/tstl/compare/v2.5.12...v2.5.13

tstl - TypeScript-STL v2.5.12

Published by samchon about 2 years ago

What's Changed

New Contributors

Full Changelog: https://github.com/samchon/tstl/compare/v2.4.11...v2.5.12

tstl - TypeScript-STL v2.4.11

Published by samchon about 4 years ago

https://github.com/samchon/tstl/projects/7

tstl - TypeScript-STL v2.0.5

Published by samchon about 6 years ago

New Features

<numeric>

Module <numeric> has newly implemented in the TSTL by this v2.0 update. special_math features, who implemented in the v1.7 update, are also belonged to this <numeric> module.

export interface IComputable<Param, Ret = Param>
{
    plus(val: Param): Ret;
    minus(val: Param): Ret;
    negate(): Ret;

    multiplies(val: Param): Ret;
    divides(val: Param): Ret;
    modules(val: Param): Ret;
}

Mathmatical functions are also implemented in the <numeric> module. If you want to utilize the algorithm functions with your own computable class, then extends the IComputable interface and override the methods. Those methods would be used by below operators.

  • operations
    • gcm
    • lcd
    • iota
    • accumulate
    • inner_product
    • adjacent_difference
    • partial_sum
    • inclusive_scan & transform_inclusive_scan
    • exclusive_scan & transform_exclusive_scan
  • operators
    • plus & minus
    • multiplies & negate
    • divides & modules

<functional>

A global function get_uid has published.

export function get_uid(obj: Object): number;

You can get UID (unique identifier) of parameter Object by the function. The get_uid function has existed since the start of TSTL, however, it's the first time that the feature has published (exported) for users.

d.ts.map

https://github.com/Microsoft/TypeScript/wiki/What's-new-in-TypeScript#new---declarationmap

Since TypeScript v2.9 update, emitting declaration map files has been possible. To follow the TypeScript policy, TSTL also starts emitting the d.ts.map files.

Break Changes

Modular System

Unlike old versions who had merged source files (TS) into only a single JS file, v2.0 update does not merge them. Since the v2.0 update, output JS files are correspondent with each TS source file and they're connected by the the import statement who follows the modular system (CommonJS).

Thus, importing TSTL within browser level (<script src="tstl.js"></script>) is not possible more. When you want to use the TSTL in browser application, then you must use a bundler like browserify.

By the way, following the modular system, you can take an additional benefit. You can implement partial import by writing detailed path of the target feature like below:

// GLOBAL IMPORT
import * as std from "tstl";

// PARTIAL IMPORT IS ALSO POSSIBLE
import { Vector, TreeMap } from "tstl/container";
import a = require("tstl/iterator");
import b = require("tstl/algorithm");
import c = require("tstl/exception");
import d = require("tstl/functional");
import e = require("tstl/utility");
import sMath = require("tstl/numeric/special_math");
import { sleep_until, shared_timed_mutex } from "tstl/thread";

// SPECIAL FEATURES
import experimental = require("tstl/experimental");
import base = require("tstl/base");

Comparators

https://github.com/samchon/tstl/blob/master/src/functional/comparators.ts

Global comparators in TSTL (used in associative containers), they've changed to compare origin type of parameters using the valueOf() function since v2.0 update. Also, getting new type Bigint is also possible.

  • Functions
    • less
    • equal_to
    • not_equal_to, less_equal, greater, greater_equal
    • hash

Also, the comparable interface IComparable has changed its methods to be required (optional symbol ? is removed). If you need only partial feature of the IComparable, then utilize the Pick type.

interface IComparable<T>
{
    equals(obj: T): boolean;
    less(obj: T): boolean;
    hashCode(): number;
}

declare class Point2D implements Pick<IComparable<MyClass>, "equals"|"less">
{
    public x: number;
    public y: number;

    public equals(p: Point2D): boolean;
    public less(p: Point2D): boolean;
}

base.SetContainer & base.MapContainer

export abstract class MapContainer<Key, T, 
        Unique extends boolean, 
        Source extends MapContainer<Key, T, Unique, Source>>
    extends Container<Entry<Key, T>,
        Source,
        MapIterator<Key, T, Unique, Source>,
        MapReverseIterator<Key, T, Unique, Source>>
{
    public abstract insert(pair: IPair<Key, T>): MapContainer.InsertRet<Key, T, Unique, Source>;
    public abstract emplace(key: T, val: T): MapContainer.InsertRet<Key, T, Unique, Source>;
}

export namespace MapContainer
{
    export type InsertRet<Key, T,
                Unique extends boolean,
                Source extends MapContainer<Key, T, Unique, Source>>
        = Unique extends true
            ? Pair<MapIterator<Key, T, Unique, Source>, boolean> 
            : MapIterator<Key, T, Unique, Source>;
}

Since v2.0 update, new generic parameter Unique has newly added in the base SetContainer and MapContainer. Those base containers also have new abstract methods insert and emplace had not existed in the earlier versions.

The Unique parameter would be specified in their sub-class level like UniqueMap (TreeMap and HashMap) or MultiSet (TreeMultiSet and HashMultiSet). Those specifications determine the return types of insert and emplace methods, using the conditional type, new feature of TS v2.9.

Fixed Errors

  • Error on copy_backward in <algorithm> has been fixed.
  • Error on empty in <iterator>, returning opposite result, has been fixed
tstl - TypeScript-STL v1.7.10

Published by samchon over 6 years ago

New Features

ECOL

Extension of TSTL Containers dispatching Events.

With TSTL v1.7 update, I've published a supplementary extension module which is named ECOL, too. ECOL is an extension module of this TSTL, providing special collections dispatching events. The special collections are almost similar with the original STL Containers, but you also can observe elements' I/O events with the special collections.

Types of the event dispatched by the special collections are "insert", "erase" and "refresh".

import {TreeMapCollection} from "ecol";

function listener(event: TreeMapCollection.Event<number, string>): void
{
    console.log("Event type is: " + event.type);

    for (let it = event.first; !it.equals(event.last); it = it.next())
        console.log("\t", "An element by that event:", it.value);
}

function main(): void
{
    // CONSTRUCT EVENT TREE-MAP
    let map: TreeMapCollection<number, string> = new TreeMapCollection();
    map.addEventListener("insert", listener);
    map.addEventListener("erase", listener);

    // DISPATCHES INSERT EVENT
    map.set(1, "One");
    map.set(2, "Two");
    map.set(3, "Three");

    // DISPATCHES ERASE EVENT
    map.erase(2);
    map.erase(3);

    // DISPATCHES REFRESH EVENT
    map.set(2, "Second"); // DUPLICATED -> UPDATE
    map.refresh(); // BY USER
}
main();

Special Math

The Mathematical Special Functions have adopted in STL, since C++17 revise. Following the STL revise, TSTL also adapts the Mathematical Special Functions since v1.7 update.

List of Mathematical Special Functions are such below:

Insert Iterators

Insert Iterators are special output iterators, who have value setter (writeonly). They're very suitable for global functions in <algorith> module, espcialy whose name is ended as _copy postfix.

Class Name Global Factory Method Required Method
InsertIterator inserter(Container) Container.insert(Iterator, Value)
FrontInsertInserter front_inserter(Container) Container.push_front(Value)
BackInsertIterator back_inserter(Container) Container.push_back(Vaue)

The Insert Iteratores are type of forward iterators providing next() method, however notice that, their next() methods return only themseles (this). They're adaptor classes calling insertion methods of their source containers repeatedly.

import std = require("tstl");

function main(): void
{
    // 100, 99, 98, ..., 1
    let list: std.List<number> = new std.List();
    for (let i: number = 1; i <= 100; ++i)
        list.push_front(i);
        
    // INSERT ELEMENTS BY BACK_INSERTER
    let vec: std.Vector<number> = new std.Vector();
    std.copy(list.begin(), list.end(), std.back_inserter(vec));
    
    // ELEMENTS IN `list` & `vec` ARE EQUAL.
    console.log(std.equal(vec.rbegin(), vec.rend(), list.begin()));
}
main();

std.sample & std.randint

Two global functions are newly added on the <algorithm> module since C++17 revise.

The sample is a sampling function picks up random n elements between [first, last) for inserts them to output. The picked up values (count: n) who would be inserted to the output iterator, they'll keep the origin sequence of [first, last).

The randint is a function returns a random integer value between x and y. If x and y are integer, then the returned value can be one of them: x or y. Remember that, x must be less than y.

namespace std
{
    export function sample<T, 
        InputIterator extends Readonly<IForwardIterator<T, InputIterator>>, 
        OutputIterator extends Writeonly<IForwardItertor<T, OutputIterator>>>
        (
            first: InputIterator, last: InputIterator, 
            output: OutputIterator, n: number
        ): OutputIterator;

    export function randint(x: number, y: number): number;
}

Heap functions in <algorithm>

New global functions handling the heap have newly added.

toJSON method on Containers

Since v1.7 update, all containers in TSTL have toJSON() method for JSON.stringify(). By the method, you can serialize container to JSON-string, as a form of Array storing its elements.

import std = require("tstl");

function main(): void
{
    //----
    // CONTAINER -> JSON
    //----
    let list: std.List<number> = new std.List();
    for (let i: number = 0; i < 10; ++i)
        list.push_back(i);

    let str: string = JSON.stringify(list);
    console.log(str); // "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"

    //----
    // JSON -> CONTAINER
    //----
    let array: Array<number> = JSON.parse(str);
    let deq: std.Deque<number> = new std.Deque(...array);

    // ELEMENTS IN `list` & `deq` ARE SAME
    console.log(std.equal(list.begin(), list.end(), deq.begin()));
}
main();

Improvements

<algorithm> & <iterator> to be much more generic

Since v1.7 update, global functions in <algorithm> and <iterator> have been much more generic.

Until the v1.6, global functions in the <algorithm> and <iterator> modules had forced that parameters of output-iterators and general-iterators to extend an abstract class [base.Iterator], which occurs critical dependency. It was possible to utilizing built-in iterators, however, user-made customer iterators were not.

Since v1.7 update, all iterator parameters of global functions in the <algorithm> and <iterator> modules, they require objects to extend not a class, but an interface. From now on, you can utilize your own-made iterators.

namespace std
{
    export function copy<T,
        InputIterator extends Readonly<IForwardIterator<T, InputIterator>>,
        OutputIterator extends Writeonly<IForwardIterator<T, OutputIterator>>>
        (
            first: InputIterator, last: InputIterator, 
            output: OutputIterator
        ): OutputIterator;
}

Much strong typed Base Containers & Iterators

This is a background story which is not important for users. This content is only for developers or participants of the TSTL project.

Until v1.6, abstract classes for containers and iterators were not enough strong within framework of type restriction and compilation. For example, abstract classes base.Container and base.Iterator, they've dependency relationships between themselves on their abstract methods. However, derived classes may override the abstract methods with derived types. Parameter and returned types are changed when overriding; it's danger, not safe for development.

Older Version

In contrary, since v1.7 update, it's not danger more. Developing the v1.7 update, I've learned a solution to avoid such danger by implementing Circular Dependency Relationships in Generics. By the solution, abstract classes of containers and iterators have been much stronger and proper in type checking.

Since v1.7 Update

Fixed Errors

Fixed errors in this v1.7 update, Most of them are caused by my misunderstandings about the STL features, defined by C++ standard committee. I'm sorry for these mistakes. Such mistakes are fixed since this v1.7 update and I promise to be careful for these mistakes.

Logic of PriorityQueue

When PriorityQueue.top() and PriorityQueue.pop() are called, then the largest value (when custom comparison function is specified, then the last value) must be returned and popped. However, old version of TSTL had returned and popped not the largest value, but the lowest value. Such critical problem has fixed since this v1.7 update.

Return type of Vector.pop_back()

Return type of Vector<T>.pop_back() is deinfed to return void, by the C++ standard committee. However, I'd done a mistake returning T type (returned value is the last element that popped by the method) for a long time. Of course, it has fixed since this v1.7 update.

erase(Key) methods in Multi Associative Containers

When erase(Key) method, in associative containers allowing duplicated keys, is called, then all the matched key elements must be erased. However, I'd defined the method to erase only an element, the first one.

Such mis-features are fixed by this v1.7 update. From now on, the erase(Key) method erases not only an element, but entire elements with the matched key and returns number of elements erased.

experimental is correct

A namespace storing experimental objects is experimental. It's the standard and exact name. Naming the namespace as experiments, it was my mistake. I've recified my mistake since v1.7 update.

Objects allocated in the experimental are such below:

Reverse iterators are no more

The regular STL doesn't support utilizing reverse iterators in containers for directing position for inserting, updating or erasing elements. However, I'd misunderstood that it was possible. By the misunderstanding, I've developed TSTL to allow directing position by reverse iterators in containers are possible.

Since v1.7 update, such mistake has recified. Using reverse iterators in containers for directing position are impossible. Utilize the ReverseIterator.base() method instead.

import std = require("tstl");

function main(): void
{
    let list: std.List<number> = new std.List();
    for (let i: number = 1; i <= 10; ++i)
        list.push_back(i);

    let r1: std.List.ReverseIterator<number> = list.rbegin();
    let r2: std.List.ReverseIterator<number> = list.rend();

    list.erase(r1, r2); // IMPOSSIBLE, BE ERROR SINCE V1.7
    list.erase(r2.base(), r1.base()); // UTILIZE `base()` INSTEAD
}
main();

Error on swap() methods on List based Containers

When swap() method is called in a List based Container, then its reverse iterators (rbegin(), rend()) were broken. This error is fixed in v1.7 update. List based containers mean:

  • List
  • Set Containers
  • Map Containers

Iterators of Set Containers were miss-linked.

Iterators of Set Containers, they'were miss-linked. Type definitions were correct, but reference links were all incorrect. It wasn't a critical problem as users of TSTL can't create Iterators of Set Containers by themselves. However, such error causes invalid invalid inspection using typeof statement. This error has fixed in v1.7 update.

namespace std.TreeSet // (TreeSet, TreeMultiSet, HashSet, HashMultiSet)
{
    // TYPE DEFINITIONS WERE CORRECT
    export type Iterator<T> = std.base.SetIterator<T, TreeSet<T>>;
    export type ReverseIterator<T> = std.base.SetReverseIterator<T, TreeSet<T>>;

    // HOWEVER, LINKAGES WERE INCORRECT
    export const Iterator = std.base.ArrayIterator;
    export const ReverseIterator = std.base.ArrayReverseIterator;
}

Break Changes

Return type of ILockable.try_lock has changed.

To pursue consistency and avoid reversal calling between other promise typed methods, return type of the ILockable.try_lock() has changed from boolean to Promise<boolean> like ILockable.lock() and ILockable.unlock() who return Promise<void>.

Function Old Return Type New Return Type
try_lock number Promise<number>
ILockable.try_lock boolean Promise<boolean>
SharedMutex.try_lock_shared boolean Promise<boolean>

random_shuffle is removed

Global function random_shuffle is deprecated from C++14 and removed clearly since C++17 revise. To follow the standard, TSTL also removes the random_shuffle function since v1.7 update. If you want the same feature, then utilize the shuffle function.

No more provide tstl.min.js

In HTML, do not include tstl by <script> tag. Use bundler like browserify instead. If you need a minified JS file, then utilize the bundler or minifier.

tstl - TypeScript-STL v1.6.9

Published by samchon over 6 years ago

New Features

Iterator Pattern

STL (Standard Template Library) is composed with 4 modules;

  • containers
  • iterators
  • algorithms
  • functors

C++ standard committee has defined lots of STL features to use Iterator Pattern with generic and functional programming; especially, global functions of algorithms. However, until v1.5, TSTL had a restriction on using the iterator pattern; only built-in iterators are allowed. All of the global functions in the algorithms module, they had allowed only built-in iterators on their parameters of the iterator pattern. Customized iterator defined by user never could not be used.

Since v1.6 update, such restriction is cleared. TSTL provides common interfaces for the iterator pattern. You can put your customized iterators on the global functions of algorithms or other STL features following the iterator pattern. Just implements below interfaces and enjoy the iterator pattern of STL.

namespace std
{
    export interface IForwardIterator<T>
    {
        equals(obj: IForwardIterator<T>): boolean;
        
        next(): IForwardIterator<T>;
        advance(n: number): IForwardIterator<T>;
    }

    export interface IBidirectionalIterator<T> extends IForwardIterator<T>
    {
        prev(): IBidirectionalIterator<T>;
    }
    
    export interface IRandomAccessIterator<T> extends IBidirectionalIterator<T>
    {
        index(): IRandomAccessIterator<T>;
    }
}

namespace std.JSArray
{
    declare class Iterator<T> implements IRandomAccessIterator<T>;
    declare class ReverseIterator<T> implements IRandomAccessIterator<T>;
}

namespace std
{
    declare function count<T, InputIterator extends IForwardIterator<T>>
        (first: InputIterator, last: InputItrator): number;
    declare function is_sorted_until<T, InputIterator extends IForwardIterator<T>>
        (first: InputIterator, last: InputItrator): InputIterator;
    
    declare class Deque<Key, T>
    {
        public assign<InputIterator extends IForwradIterator<T>>
            (first: InputIterator, last: InputIterator);
    }
}

You also can take advantage of STL's iterator pattern with JS-Array. Create iterators for JS-Array with below functions.

import std = require("tstl");

let array: Array<number> = [1, 2, 3, 4, 5, 6, 7];
let first = std.begin(array); // std.JSArray.Iterator<number>
let last = std.end(array);

std.foreach(first, last, function (val: number): void
{
    console.log(val);
});

ForwardList

<forward_list> has implemented.

Unlike std.List who represents doubly linked list and shares same interfaces with other linear containers, std.ForwardList represents the singly linked list and does not share same interface with other linear containers. The std.ForwardList container has its own specific insertion and deletion methods.

Name Data Structure Common Interface
std.ForwardList Singly Linked List O
std.List Doubly Linked List X

ConditionVariable

Since v1.6 update, <condition_variable>, a class of supporting critical section in C++, has implemented in the TSTL.

namespace std
{
    export class ConditionVariable
    {
        // DO NOT NEED unique_lock
        public constructor();

        public wait(): Promise<void>;
        public wait_for(ms: number): Promise<boolean>;
        public wait_until(at: Date): Promise<boolean>;

        public notify_one(): void;
        public notify_all(): void;
    }
    export type condition_variable = ConditionVariable;
}

experiments.Semaphore

Since v1.6 update, experiments.semaphore and experiments.timed_semaphore has implemented. Note that, they're just experimental classes defined in the experiments namespace, not defined in the regular STL; defined by C++ standard committe.

namespace std.experiments
{
    export class Semaphore implements ILockable
    {
        public constructor(size: number);
        public size(): number;

        public lock(count: number = 1): Promise<void>;
        public try_lock(count: number = 1): boolean;
        public unlock(count: number = 1): Promise<void>;
    }

    export class TimedSemaphore implements Semaphore
    {
        public try_lock_for(ms: number, count: number = 1): Promise<boolean>;
        public try_lock_until(at: Date, count: number = 1): Promise<boolean>;
    }
}

Error Fixes

Equality Function on Tree Containers

Equlity function on the Tree Containers has changed to such below

  • Before: std.equal_to(x, y)
  • From now on: !comp(x, y) && !comp(y, x)

I had repeated a mistake on the equality function of Tree Containers.

  • TreeSet set
  • TreeMultiSet multiset
  • TreeMap map
  • TreeMultiMap multimap

It has been possible to specializing compare function on Tree Containers in construction level. However, the equality function on the Tree Containers had not utilized the compare function. I'd repeated a mistake that Tree Containers to use std.equal_to function instead of the specialized compare function.

Since this v1.6 update, the equality function of the Tree Containers has changed to utilizing the specialized compare function such below:

!comp(x, y) && !comp(y, x);

Specializations of Hash Containers

I'd forgotten some features, specifying custom hash & equality functions on the Hash Containers, for a long time. Since this v1.6 update, you can use your custom hash functions and equality functions on the Hash Containers:

  • HashSet unordered_set
  • HashMultiSet unordered_multiset
  • HashMap unordered_map
  • HashMultiMap unordered_multimap

Until this update, you couldn't use your specialized hash & equality function on the Hash Containers. The Hash Containers only used the std.hash and std.equal_to. However, from now on, you can specialize the hash & equality functions in the constructor level.

Reference the below code and create your specialize hash containers by inserting your custom functions as parameters on the constructor. If you do not specify the hash and equality functions, std.hash and std.equal_to functions will be used like before.

namespace std
{
   type HashFunction<T> = (val: T) => number;
   type EqualFunction<T> = (x: T, y: T) => boolean;

    export class HashMap<Key, T>
    {
        // DEFAULT CONSTRUCTOR
        public constructor(
            hash: HashFunction<Key> = std.hash, 
            equal: EqualFunction<Key> = std.equal_to
        );

        // COPY CONSTRUCTOR
        public constructor(
            obj: HashMap<Key, T>,
            hash: HashFunction<Key> = std.hash, 
            equal: EqualFunction<Key> = std.equal_to
        );

        // ASSIGN CONSTRUCTOR
        public constructor(
            first: IForwardIterator<IPair<Key, T>>,
            last: IForwardIterator<IPair<Key, T>>,
            hash: HashFunction<Key> = std.hash, 
            equal: EqualFunction<Key> = std.equal_to
        );
    }
}

let hash_fn = function (val: number): number { return val ^ 122174131 - val; }
let equal_fn = function (x: number, y: number): boolean { return x == y; }

let words: std.HashMap<number, string> = new std.HashMap(hash_fn, equal_fn);
words.emplace(1, "First");
words.emplace(2, "Second");

let it = std.HashMap.Iterator<number, string> = words.find(1);
console.log(it.first, it.second); // 1, "First"

By adding the specialization features, observer methods referencing the specialized functions and accessor functions for hash buckets are also added.

  • Observers
    • hash_function()
    • key_eq()
  • Accessors to Hash Buckets
    • bucket()
    • bucket_count()
    • bucket_size()
    • load_factor()
    • max_load_factor()
    • reserve()
    • rehash()

Break Changes

Iterators're placed into their containers.

// CONTAINERS AND
let v: std.Vector<number>;
let m: std.TreeMap<number, number>;
let s: std.unordered_multiset<string>;

// THEIR ITERATORS
let v_it: std.Vector.ReverseIterator<number> = v.rbegin();
let m_it: std.TreeMap.Iterator<number, number> = m.begin();
let s_it: std.unordered_multiset.reverse_iterator<string> = s.rend();

Since v1.6 update, built-in iterators are moved into their domain containers.

C++ standard committee defined built-in iterators to be placed in their owner containers. Most compiler vendors follow the rule by defining iterator classes to somewhere hidden and making shortcuts of them using the typedef statement.

#include <vector>

namespace std
{
    template <typename T>
    class vector
    {
        typedef _base::vector_iterator<T> iterator;
        typedef _base::vector_reverse_iterator<T> reverse_iterator;
    };
}

int main()
{
    std::vector<int> v = {1, 2, 3, 4};
    std::vector<int>::iterator it = v.begin();

    return 0;
}

Until v1.5, I had defined built-in iterator classes onto the same layer with their own containers and had provided type aliases of built-in iterators in their own containers. Placing containers and iterators onto same layer with similar name, it may had caused lots of confusing to TSTL users. Someone may had been more confused when using instanceof statement onto the type aliases that does not work.

Thus, I moved the built-in iterator classes into their domain containers. It may much convenient and reasonable.

v1.5 Old v1.6; PascalNotation v1.6; snake_notation
VectorIterator Vector.Iterator vector.iterator
DequeIterator Deque.Iterator deque.iterator
ListIterator List.Iterator list.iterator
- ForwardList.Iterator forward_list.iterator
SetIterator TreeSet.Iterator set.iterator
'' MultiTreeSet.Iterator multiset.iterator
'' HashSet.Iterator unordered_set.iterator
'' HashMultiSet.Iterator unordered_multiset.iterator
MapIterator TreeMap.Iterator map.iterator
'' MultiTreeMap.Iterator multimap.iterator
'' HashMap.Iterator unordered_map.iterator
'' HashMultiMap.Iterator unordered_multimap.iterator

Reverse Iterators

v1.5 Old v1.6; PascalNotation v1.6; snake_notation
VectorReverseIterator Vector.ReverseIterator vector.reverse_iterator
DequeReverseIterator Deque.ReverseIterator deque.reverse_iterator
ListIReverseterator List.ReverseIterator list.reverse_iterator
SetReverseIterator TreeSet.ReverseIterator set.reverse_iterator
'' MultiTreeSet.ReverseIterator multiset.reverse_iterator
'' HashSet.ReverseIterator unordered_set.reverse_iterator
'' HashMultiSet.ReverseIterator unordered_multiset.reverse_iterator
MapReverseIterator TreeMap.ReverseIterator map.reverse_iterator
'' MultiTreeMap.ReverseIterator multimap.reverse_iterator
'' HashMap.ReverseIterator unordered_map.reverse_iterator
'' HashMultiMap.ReverseIterator unordered_multimap.reverse_iterator7

Map, Entry instead of Pair

namespace std
{
    declare class Pair<First, Second>
    {
        public first: First;
        public second: Second;
    }
    
    declare class Entry<Key, T>
    {
        public readonly first: Key;
        public second: T;
    }
}

namespace std.base
{
    declare class MapContainer<Key, T, Source> extends Container<Entry<Key, T>>;
    declare class MapIterator<Key, T, Source> extends Iterator<Entry<Key, T>>
}

Until v1.5, Map containers had stored their elements (keys and values) using Pair. It had a risk to changing key element by user manually. When user tries to access Pair object manually by MapIterator.value and fixes the first member manually, then the Map container lost its integrity. Keys between 1. Pair object and 2. Indexes like B+Tree or Hash buckets are mismtached.

Since v1.6 update, to prevent the manual risk, Map container stores elements in the Entry objects. Entry has same interface with Pair, only safety option is added. By the update, user can't modify key element by manually more.

import std = require("tstl");

let m: std.TreeMap<number, string>;

for (let elem of m) // elem: std.TreeMap.Iterator<number, string>
{
    console.log(elem.first, elem.second);

    // Had possible until v1.5
    // Be error since v1.6
    elem.value.first = -1;
}

ILockable.unlock()

Since v1.6 update, ILockable.unlock() and alike functions releasing critical sections, they're all changed to asynchronous functions, returning Promise objects.

Old TSTL until v1.5, ILockable.unlock() functions had returned void, who can't assure sequences and priorities of critical sections. To assure those concepts, I changed them to return not void but Promise<void>.

namespace std
{
    interface ILockable
    {
        lock(): Promise<void>;
        try_lock(): boolean;
        
        unlock(): Promise<void>;
    }

    export class Mutex implements ILocakble;
    export class SharedMutex implements Mutex
    {
        lock_shared(): Promise<void>;
        try_lock_shared(): boolean;

        unlock_shared(): Promise<void>;
    }
}
tstl - TypeScript-STL v1.5.6

Published by samchon about 7 years ago

New Features

For ... of iteration

Until the v1.4, there had been only a generic iterator pattern using the begin() and end() methods. However, since this v1.5 update, you also can utilize the for ... of iteration statement.

When you need to iterate full elements of a STL-container, then the for ... of iteration would be much convenient.

function old_iteration(): void
{
    let v = new std.Vector<number>();
    for (let i: number = 0; i < 10; ++i)
        v.push_back(i);

    // NEW FEATURE - FOR OF ITERATION
    for (let it = v.begin(); !it.equal_to(v.end()); it = it.next())
        console.log(it.value);
}

function for_of_vector(): void
{
    let v = new std.Vector<number>();
    for (let i: number = 0; i < 10; ++i)
        v.push_back(i);

    // NEW FEATURE - FOR OF ITERATION
    for (let elem of v)
        console.log(elem);
}

function for_of_map(): void
{
    let m = new std.Map<string, number>();
    m.emplace("First", 1);
    m.emplace("Second", 2);
    m.emplace("Third", 3);

    for (let pair of m)
        console.log(pair.first, pair.second);
}

<thread>

Since this TypeScript-STL v1.5 update, the <thread> has implemented in. However, notice that; JavaScript code runs in only a thread. The function and classes in the <thread> are all fake instances, based on the Promise. They just imitate the <thread>'s behaviors.

async function test_sleep_for(): Promise<void>
{
    await std.sleep_for(2000); // sleep for 2 seconds.
}

When you call the std.sleep_until() function, then it doesn't lock your program. It just returns a Promise object that calling the call-back function at the specified datetime.

<thread> features implemented in the TypeScript-STL v1.5 are such below:

global functions

namespace std
{
    export function sleep_for(ms: number): Promise<void>;
    export function sleep_until(at: Date): Promise<void>;
    
    export function lock(...items: ILockable[]): Promise<void>;
    export function try_lock(...items: ILockable[]): number;

    export interface ILockable
    {
        public lock(): Promise<void>;
        public try_lock(): boolean;
    }
}

mutex & timed_mutex

namespace std
{
    export class Mutex implements ILockable
    {
        public lock(): Promise<void>;
        public try_lock(): boolean;
        public unlock(): void;
    }

    export class TimedMutex implements Mutex
    {
        public try_lock_for(ms: number): Promise<boolean>;
        public try_lock_until(at: Date): Promise<boolean>;
    }
}

shared_mutex

namespace std
{
    export class SharedMutex implements Mutex
    {
        public lock_shared(): Promise<void>;
        public try_lock_shared(): boolean;
        public unlock_shared(): void;
    }

    export class SharedTimedMutex implements SharedMutex, TimedMutex
    {
        public try_lock_shared_for(ms: number): Promise<boolean>;
        public try_lock_shared_until(at: Date): Promise<boolean>;
    }
}

Break Changes

Exception extends Error

Due to the transpiler problem (Extending built-ins like Error, Array, and Map may no longer work), I determined Exception not to extends the Error class, the built-in-class of JavaScript.

However, not extending the Error class, tracing call stack had been difficult such below:

So I determined to roll back the Exception class to extends the Error again.

namespace std
{
    export class Exception extends Error;

    export class LogicError extends Exception;
    export class RuntimeError extends Exception;
}

Container.swap

Until the v1.5 update, calling Container.swap() function between heterogeneous containers was possible. However, since this v1.5 update, the Container.swap() function works only for the homogeneous containers.

Additionally, until the v1.5 update, when the Container.swap() is called, Iterator.source() doesn't point the swapped container, but the old container. Such bug also has been fixed since this v1.5 update.

namespace std
{
    export class List<T>
    {
        public swap(obj: List<T>); // ONLY SAME TYPE IS ALLOWED
        // public swap(obj: base.Container<T>); -> HETEROGENEOUS -> IT IS TRUNCATED
    }
}
tstl - TypeScript-STL v1.4.3

Published by samchon over 7 years ago

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.

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 equal in 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:

  1. 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 (js only).
    • When compile error occurs, then the builder will be halted.
  2. Execute testing unit.
    • The testing unit will validate source codes with some testing functions.
    • When error occurs, then the builder will be halted, too.
  3. 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.

New Features

<algorithm>

tstl - TypeScript-STL v1.3.8

Published by samchon almost 8 years ago

Breaking Changes

Vector no longer extends the Array

As the ES2015 has newly approached, It's hard to extend built-in classes with the transpilers like TypeScript. The only way to extend those built-in classes are using setPrototypeOf statement, which is not supported in IE10 and priors.

class Vector<T> extends Array<T>
{
    constructor(...args: any[])
    {
        super();
        Object.setPrototypeOf(this, Vector.prototype);
    }
}

In such reason, TypeScript-STL's Vector and Exception do not extend Array and Error, the built-in classes, more. As the same reason, base.IContainer is deprecated

//----
// ORDINARY VECTOR AND EXCEPTION, THEY HAD EXTENDED THE BUILT-IN CLASSES
//----
namespace std 
{
    export class Vector<T> extends Array<T> implements base.IContainer<T>;
    export class Exception extends Error;
}

//----
// HOWEVER, IT DOES NOT EXTEND BUILT-INS MORE
//----
namespace std 
{
    export class Vector<T> extends base.Container<T>;
    export class Exception;
}

Unnecessary comments are all deprecated

Unnecessary comments for API documentation are all deprecated. Private members and some methods start from the _ prefix, their symbols are all changed to the @hidden.

namespace std.base
{
    export abstract class MapContainer<Key, T>
    {
        /**
         * @hidden
         */
        private data_: _MapElementList<Key, T>;

        /**
         * @hidden
         */
        protected _Handle_insert(first: MapIterator<Key, T>, last: MapIterator<Key, T>): void;
    }
}

Error Fix

std.shuffle & std.random_shuffle

There was an error on std.shuffle and std.random_shuffle when the range iterators are pointing to the end.

let container: std.Vector<number> = new std.Vector<number>();
containers.push(1 , 2, 3, 4, 5);

// NO PROBLEM IN THAT CASE
std.sort(container.begin(), container.end().prev());

//--------
// WHEN END() OR REND() IS POINTED, THEN ERROR HAD OCCURED
//--------
// HOWEVER, THE ERROR DOES NOT OCCURE MORE
std.sort(container.begin(), container.end());
std.sort(container.rbegin(), container.rend());
tstl - TypeScript-STL v1.2.4

Published by samchon almost 8 years ago

IComparable has changed

  • IComparable.equal_to -> IComparable.equals
  • IComparable.hash -> IComparable.hashCode? 
namespace std
{
    export interface IComparable<T>
    {
        less(obj: T): boolean;
        equals(obj: T): boolean;
        hashCode?(): number;
    }
}

Iteration of Associative Containers

Iteration of associative containers are much faster than before.

Associative Containers

Permutation Algorithm

Three functions about permutation algorithm are newly added.

tstl - TypeScript-STL v1.1.0

Published by samchon about 8 years ago

A minor update v1.1 has released.

New Features

std.for_each_n

  • New feature of C++17

std.base.UniqueMap.extract

  • New feature of C++17.
  • Extract an element (Pair) from a UniqueMap container.
  • Removes an element from a UniqueMap and returns the elemnet.

std.base.UniqueMap.insert_or_assign

  • New feature of C++17
  • Find matched key. If exists, change the mapped value. If not, then inserts the new element.
  • It's same with the base.UniqueMap.set(). I have predicted that such function will be added in C++17, however, failed to predict its name.

std.base.UniqueMap.emplace

In C++ STL, emplace() is a method who calls insert() with new T object, constructed from arguments of varadic template in the emplace(). Using paraeterms in emplace() to creating a new T object, it's possible because the characteristics of C++ template system. Implementing it is not possible in the JavaScript.

However, the map containers, they are storing elements with capsulizing key and mapped value into a std.Pair object. It means that the map containers, their value type is specified exactly (as std.Pair). Thus only the map containers, realizing emplace() is feasible.

template <typename T, typename Alloc = std::allocator<T>, typename Compare = std::less<T>> 
class unordered_set
{
public:
    template <typename ...Args>
    void emplace(Args&&... args)
    {
        // VARADIC TEMPLATE, IT'S ONLY POSSIBLE IN C++
        T &element(args...);
        insert(element);
    }
}

std.base.MultiMap.emplace

  • Same with the std.base.UniqueMap.emplace

std.base.MapContainer.emplace_hint

  • Same with the std.base.UniqueMap.emplace

std.base.UniqueSet.extract

  • Same with the std.base.UniqueMap.extract

std.base.UniqueSet.insert_or_assign

  • Same with the std.base.UniqueMap.insert_or_assign

Fixed Errors

std.Vector.iterator.advance

  • Calling advance() with minus value had ignored.
  • When the iterator is pointing to the Vector.end().

std.Deque.iterator.advance

  • Same with the std.Vector.iterator.advance

std.Deque.erase

  • There had been an error that a Deque is being locked.
  • When only an element was existed in a Deque and the last element is deleted, the last row in the matrix (who is storing Deque's elements in) is also deleted. Thus any row exists in the matrix and it causes any element can be inserted into the Deque.

std.reverse

  • It had not worked at all.

Refactoring

Sorting algorithm on the std.List.sort() has changed.

Until before, std.sort() had subrogated the std.List.sort().

  • Elements in std.List are copied into a new std.Vector
  • After sorting via std.sort(), elements in the std.Vector are assigned the the std.List.
class List<T>
{
    public sort(): void
    {
        // UNTIL BEFORE, STD.SORT HAD SUBROGATED
        let vector: Vector<T> = new Vector<T>(this.begin(), this.end());
        std.sort(vector.begin(), vector.end());

        this.assign(vector.begin(), vector.end());
    }
}

From now on, the sorting is done by std.List itself.

Protected methods are renamed.

tstl - TypeScript v1.0.0

Published by samchon about 8 years ago

Finally, TypeScript-STL has fully implemented and released to v1.0.

TypeScript-STL supports all type of STL containers and algorithms

Containers

Global Functions

Package Rankings
Top 1.88% on Npmjs.org
Top 15.56% on Deno.land
Top 9.55% on Proxy.golang.org
Badges
Extracted from project README
GitHub license npm version Downloads Build Status FOSSA Status Chat on Gitter
Related Projects
ecol

Event Collections

08 Mar 2018 9
mutex

Mutex Server using WebSocket

26 May 2020 29
astl

Standard Template Library for AssemblyScript

09 Oct 2020 36
awesome-typescript

A collection of awesome TypeScript resources for client-side and server-side development

16 Sep 2018 3,880
prelude-ts

Functional programming, immutable collections and FP constructs for typescript and javascript

31 Aug 2017 376
tgrid

TypeScript RPC (Remote Procedure Call) for WebSocket and Worker protocols

12 Oct 2018 141