Release TypeScript-STL v1.6.9 · samchon/tstl

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.

Formal Iterators
- std.begin()
- std.end()
Reverse Iterators
- std.rbegin()
- std.rend()

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.

API Document
- insert_after
- erase_after

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

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

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>;
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

TypeScript-STL v1.6.9