Dictionary.h

/*********************************************************************** Author: Zihan Chen (vczh) Licensed under https://github.com/vczh-libraries/License ***********************************************************************/

#ifndef VCZH_COLLECTIONS_DICTIONARY

#define VCZH_COLLECTIONS_DICTIONARY

#include "List.h"

namespace

{

namespace

collections

{

/// <summary>Dictionary: one to one map container.</summary>

/// <typeparam name="KT">Type of keys.</typeparam>

/// <typeparam name="VT">Type of values.</typeparam>

/// <typeparam name="KK">Type of the key type of keys. It is recommended to use the default value.</typeparam>

/// <typeparam name="VK">Type of the key type of values. It is recommended to use the default value.</typeparam>

template

typename

KeyType

>::

Type

typename

KeyType

>::

Type

class

Dictionary

public

Object

public

virtual

IEnumerable

Pair

>> {

public

typedef

SortedList

KeyContainer

;

typedef

List

ValueContainer

;

protected

class

Enumerator

public

Object

public

virtual

IEnumerator

Pair

>> {

private

const

Dictionary

container

;

vint

index

;

Pair

current

;

void

UpdateCurrent

() {

(

index

container

Count

()) {

current

key

container

Keys

().

Get

(

index

);

current

value

container

Values

().

Get

(

index

); } }

public

Enumerator

(

const

Dictionary

_container

vint

_index

) {

container

_container

;

index

_index

; }

IEnumerator

Pair

>>*

Clone

()

const

override

{

return

new

Enumerator

(

container

index

); }

const

Pair

Current

()

const

override

{

return

current

; }

vint

Index

()

const

override

{

return

index

; }

bool

()

override

{

index

++;

UpdateCurrent

();

return

index

container

Count

(); }

void

Reset

()

override

{

index

;

UpdateCurrent

(); }

bool

Evaluated

()

const

override

{

return

true

; } };

KeyContainer

keys

;

ValueContainer

values

;

public

/// <summary>Create an empty dictionary.</summary>

Dictionary

() =

default

;

IEnumerator

Pair

>>*

CreateEnumerator

()

const

{

return

new

Enumerator

(

this

); }

/// <summary>Set a preference of using memory.</summary>

/// <param name="mode">

/// Set to true (by default) to let the container actively reduce memories when there is too much room for unused elements.

/// This could happen after removing a lot of elements.

/// </param>

void

SetLessMemoryMode

(

bool

mode

) {

keys

SetLessMemoryMode

(

mode

);

values

SetLessMemoryMode

(

mode

); }

/// <summary>Get all keys.</summary>

/// <returns>All keys.</returns>

const

KeyContainer

Keys

()

const

{

return

keys

; }

/// <summary>Get all values.</summary>

/// <returns>All values.</returns>

const

ValueContainer

Values

()

const

{

return

values

; }

/// <summary>Get the number of keys.</summary>

/// <returns>The number of keys. It is also the number of values.</returns>

vint

Count

()

const

{

return

keys

Count

(); }

/// <summary>Get the reference to the value associated to a specified key.</summary>

/// <returns>The reference to the value. It will crash if the key does not exist.</returns>

/// <param name="key">The key to find.</param>

const

Get

(

const

key

)

const

{

return

values

Get

(

keys

IndexOf

(

key

)); }

/// <summary>Get the reference to the value associated to a specified key.</summary>

/// <returns>The reference to the value. It will crash if the key does not exist.</returns>

/// <param name="key">The key to find.</param>

const

operator

[

]

(

const

key

)

const

{

return

values

Get

(

keys

IndexOf

(

key

)); }

/// <summary>Replace the value associated to a specified key.</summary>

/// <returns>Returns true if the value is replaced.</returns>

/// <param name="key">The key to find. If the key does not exist, it will be added to the dictionary.</param>

/// <param name="value">The associated value to replace.</param>

bool

Set

(

const

key

const

value

) {

vint

index

keys

IndexOf

(

KeyType

>::

GetKeyValue

(

key

));

(

index

==-

) {

index

keys

Add

(

key

);

values

Insert

(

index

value

); }

else

{

values

[

index

value

; }

return

true

; }

/// <summary>Add a key with an associated value.</summary>

/// <returns>Returns true if the pair is added. If will crash if the key exists.</returns>

/// <param name="value">The pair of key and value.</param>

bool

Add

(

const

Pair

value

) {

return

Add

(

value

key

value

); }

/// <summary>Add a key with an associated value.</summary>

/// <returns>Returns true if the pair is added. If will crash if the key exists.</returns>

/// <param name="key">The key to add.</param>

/// <param name="value">The value to add.</param>

bool

Add

(

const

key

const

value

) {

CHECK_ERROR(!keys.Contains(KeyType<KT>::GetKeyValue(key)), L"Dictionary<KT, KK, ValueContainer, VT, VK>::Add(const KT&, const VT&)#Key already exists.");

{

(!(!

keys

Contains

(

KeyType

>::

GetKeyValue

(

key

))))

throw

Error

(

L"Dictionary<KT, KK, ValueContainer, VT, VK>::Add(const KT&, const VT&)#Key already exists."

);}

while

(

);

vint

index

keys

Add

(

key

);

values

Insert

(

index

value

);

return

true

; }

/// <summary>Remove a key with the associated value.</summary>

/// <returns>Returns true if the key and the value is removed.</returns>

/// <param name="key">The key to find.</param>

bool

Remove

(

const

key

) {

vint

index

keys

IndexOf

(

key

);

(

index

!=-

) {

keys

RemoveAt

(

index

);

values

RemoveAt

(

index

);

return

true

; }

else

{

return

false

; } }

/// <summary>Remove all elements.</summary>

/// <returns>Returns true if all elements are removed.</returns>

bool

Clear

() {

keys

Clear

();

values

Clear

();

return

true

; } };

/// <summary>Group: one to many map container.</summary>

/// <typeparam name="KT">Type of keys.</typeparam>

/// <typeparam name="VT">Type of values.</typeparam>

/// <typeparam name="KK">Type of the key type of keys. It is recommended to use the default value.</typeparam>

/// <typeparam name="VK">Type of the key type of values. It is recommended to use the default value.</typeparam>

template

typename

KeyType

>::

Type

typename

KeyType

>::

Type

class

Group

public

Object

public

virtual

IEnumerable

Pair

>> {

public

typedef

SortedList

KeyContainer

;

typedef

List

ValueContainer

;

protected

class

Enumerator

public

Object

public

virtual

IEnumerator

Pair

>> {

private

const

Group

container

;

vint

keyIndex

;

vint

valueIndex

;

Pair

current

;

void

UpdateCurrent

() {

(

keyIndex

container

Count

()) {

const

ValueContainer

values

container

GetByIndex

(

keyIndex

);

(

valueIndex

values

Count

()) {

current

key

container

Keys

().

Get

(

keyIndex

);

current

value

values

Get

(

valueIndex

); } } }

public

Enumerator

(

const

Group

_container

vint

_keyIndex

vint

_valueIndex

) {

container

_container

;

keyIndex

_keyIndex

;

valueIndex

_valueIndex

; }

IEnumerator

Pair

>>*

Clone

()

const

override

{

return

new

Enumerator

(

container

keyIndex

valueIndex

); }

const

Pair

Current

()

const

override

{

return

current

; }

vint

Index

()

const

override

{

(

keyIndex

container

Count

()) {

vint

index

;

for

(

vint

;

keyIndex

;

++) {

index

container

GetByIndex

(

Count

(); }

return

index

valueIndex

; }

else

{

return

; } }

bool

()

override

{

(

keyIndex

==-

) {

keyIndex

; }

while

(

keyIndex

container

Count

()) {

valueIndex

++;

const

ValueContainer

values

container

GetByIndex

(

keyIndex

);

(

valueIndex

values

Count

()) {

UpdateCurrent

();

return

true

; }

else

{

keyIndex

++;

valueIndex

; } }

return

false

; }

void

Reset

()

override

{

keyIndex

;

valueIndex

;

UpdateCurrent

(); }

bool

Evaluated

()

const

override

{

return

true

; } };

KeyContainer

keys

;

List

ValueContainer

values

;

public

/// <summary>Create an empty group.</summary>

Group

() =

default

;

Group

() {

Clear

(); }

IEnumerator

Pair

>>*

CreateEnumerator

()

const

{

return

new

Enumerator

(

this

); }

/// <summary>Get all keys.</summary>

/// <returns>All keys.</returns>

const

KeyContainer

Keys

()

const

{

return

keys

; }

/// <summary>Get the number of keys.</summary>

/// <returns>The number of keys.</returns>

vint

Count

()

const

{

return

keys

Count

(); }

/// <summary>Get all values associated to a specified key.</summary>

/// <returns>All associated values. It will crash if the key does not exist.</returns>

/// <param name="key">The key to find.</param>

const

ValueContainer

Get

(

const

key

)

const

{

return

values

Get

(

keys

IndexOf

(

key

)); }

/// <summary>Get all values associated to a key at a specified index in <see cref="Keys"/>.</summary>

/// <returns>All associaged values. It will crash if the index is out of range.</returns>

/// <param name="index">The position of the key.</param>

const

ValueContainer

GetByIndex

(

vint

index

)

const

{

return

values

Get

(

index

); }

/// <summary>Get all values associated to a specified key.</summary>

/// <returns>All associated values. It will crash if the key does not exist.</returns>

/// <param name="key">The key to find.</param>

const

ValueContainer

operator

[

]

(

const

key

)

const

{

return

values

Get

(

keys

IndexOf

(

key

)); }

/// <summary>Test if there is any value associated to a specified key or not.</summary>

/// <returns>Returns true there is at least one value associated to this key.</returns>

/// <param name="key">The key to find.</param>

bool

Contains

(

const

key

)

const

{

return

keys

Contains

(

key

); }

/// <summary>Test if a value is associated to a specified key or not.</summary>

/// <returns>Returns true if the specified value is associated to the specified key.</returns>

/// <param name="key">The key to find.</param>

/// <param name="value">The value to find.</param>

bool

Contains

(

const

key

const

value

)

const

{

vint

index

keys

IndexOf

(

key

);

(

index

!=-

) {

return

values

Get

(

index

)->

Contains

(

value

); }

else

{

return

false

; } }

/// <summary>

/// Add a key with an associated value.

/// If the key already exists, the value will be associated to the key with other values.

/// If this value has already been associated to the key, it will still be duplicated.

/// </summary>

/// <returns>Returns true if the pair is added.</returns>

/// <param name="value">The pair of key and value to add.</param>

bool

Add

(

const

Pair

value

) {

return

Add

(

value

key

value

); }

/// <summary>

/// Add a key with an associated value.

/// If the key already exists, the value will be associated to the key with other values.

/// If this value has already been associated to the key, it will still be duplicated.

/// </summary>

/// <returns>Returns true if the key and the value are added.</returns>

/// <param name="key">The key to add.</param>

/// <param name="value">The value to add.</param>

bool

Add

(

const

key

const

value

) {

ValueContainer

target

;

vint

index

keys

IndexOf

(

KeyType

>::

GetKeyValue

(

key

));

(

index

==-

) {

target

new

ValueContainer

;

values

Insert

(

keys

Add

(

key

target

); }

else

{

target

values

[

index

]; }

target

Add

(

value

);

return

true

; }

/// <summary>Remove a key with all associated values.</summary>

/// <returns>Returns true if the key and all associated values are removed.</returns>

/// <param name="key">The key to find.</param>

bool

Remove

(

const

key

) {

vint

index

keys

IndexOf

(

key

);

(

index

!=-

) {

keys

RemoveAt

(

index

);

List

target

values

[

index

];

values

RemoveAt

(

index

);

delete

target

;

return

true

; }

else

{

return

false

; } }

/// <summary>Remove a value associated to a specified key.</summary>

/// <returns>

/// Returns true if the value is removed.

/// If this value is associated to the key for jultiple times, only the first one will be removed.

/// </returns>

/// <param name="key">The key to find.</param>

/// <param name="value">The value to remove.</param>

bool

Remove

(

const

key

const

value

) {

vint

index

keys

IndexOf

(

key

);

(

index

!=-

) {

List

target

values

[

index

];

target

Remove

(

value

);

(

target

Count

()==

) {

keys

RemoveAt

(

index

);

values

RemoveAt

(

index

);

delete

target

; }

return

true

; }

else

{

return

false

; } }

/// <summary>Remove everything.</summary>

/// <returns>Returns true if all keys and values are removed.</returns>

bool

Clear

() {

for

(

vint

;

values

Count

();

++) {

delete

values

[

]; }

keys

Clear

();

values

Clear

();

return

true

; } };

/*********************************************************************** GroupInnerJoin ***********************************************************************/

/// <summary>Perform inner join on two groups.</summary>

/// <typeparam name="TKey">The type of keys in two groups.</typeparam>

/// <typeparam name="TValueFirst">The type of values in the first group.</typeparam>

/// <typeparam name="TValueSecond">The type of values in the second group.</typeparam>

/// <typeparam name="TDiscardFirst">The type of the first callback.</typeparam>

/// <typeparam name="TDiscardSecond">The type of the second callback.</typeparam>

/// <typeparam name="TAccept">The type of the third callback.</typeparam>

/// <param name="first">The first group.</param>

/// <param name="second">The second group.</param>

/// <param name="discardFirst">

/// Callback that is called when a value in the first group is discarded.

/// This happens for values associated to a key in the first group, that no value is assocated to the same key in the second group.

/// The first argument is the key, the second argument is the discarded value list in the first group.

/// </param>

/// <param name="discardSecond">

/// Callback that is called when a value in the second group is discarded.

/// This happens for values associated to a key in the second group, that no value is assocated to the same key in the first group.

/// The first argument is the key, the second argument is the discarded value list in the first group.

/// </param>

/// <param name="accept">

/// Callback that is called when a match of values in both groups are found.

/// This happens for any key that, values are associated to this key in both group.

/// The first argument is the key, the second argument is the associated value list in the first group, the third argument list is the associated value in the second group.

/// </param>

/// <remarks>

/// This function does not change data in provided groups.

/// </remarks>

/// <example><![CDATA[

/// int main()

/// {

/// auto printList = [](const List<WString>& values)

/// {

/// return L"[" + From(values).Aggregate([](const WString& a, const WString& b) { return a + L", " + b; }) + L"]";

/// };

///

/// Group<vint, WString> as, bs;

/// as.Add(1 ,L"A"); as.Add(1 ,L"B"); as.Add(2 ,L"C"); as.Add(2 ,L"D");

/// bs.Add(1 ,L"X"); bs.Add(1 ,L"Y"); bs.Add(3 ,L"Z"); bs.Add(3 ,L"W");

/// GroupInnerJoin(

/// as,

/// bs,

/// [&](vint key, const List<WString>& values) { Console::WriteLine(L"Discarded in as: " + itow(key) + printList(values)); },

/// [&](vint key, const List<WString>& values) { Console::WriteLine(L"Discarded in bs: " + itow(key) + printList(values)); },

/// [&](vint key, const List<WString>& values1, const List<WString>& values2) { Console::WriteLine(L"Accepted: " + itow(key) + printList(values1) + printList(values2)); }

/// );

/// }

/// ]]></example>

template

typename

TKey

typename

TValueFirst

typename

TValueSecond

typename

TDiscardFirst

// TKey * [TValueFirst] -> void

typename

TDiscardSecond

// TKey * [TValueSecond] -> void

typename

TAccept

// TKey * [TValueFirst] * [TValueSecond] -> void

void

GroupInnerJoin

(

const

Group

TKey

TValueFirst

first

const

Group

TKey

TValueSecond

second

const

TDiscardFirst

discardFirst

const

TDiscardSecond

discardSecond

const

TAccept

) {

vint

firstIndex

;

vint

secondIndex

;

vint

firstCount

first

Keys

().

Count

();

vint

secondCount

second

Keys

().

Count

();

while

(

true

) {

(

firstIndex

firstCount

) {

auto

firstKey

first

Keys

()

[

firstIndex

];

const

List

TValueFirst

firstValues

first

GetByIndex

(

firstIndex

);

(

secondIndex

secondCount

) {

auto

secondKey

second

Keys

()

[

secondIndex

];

const

List

TValueSecond

secondValues

second

GetByIndex

(

secondIndex

);

(

firstKey

secondKey

) {

discardFirst

(

firstKey

firstValues

);

firstIndex

++; }

else

(

firstKey

secondKey

) {

discardSecond

(

secondKey

secondValues

);

secondIndex

++; }

else

{

(

firstKey

firstValues

secondValues

);

firstIndex

++;

secondIndex

++; } }

else

{

discardFirst

(

firstKey

firstValues

);

firstIndex

++; } }

else

{

(

secondIndex

secondCount

) {

auto

secondKey

second

Keys

()

[

secondIndex

];

const

List

TValueSecond

secondValues

second

GetByIndex

(

secondIndex

);

discardSecond

(

secondKey

secondValues

);

secondIndex

++; }

else

{

break

; } } } }

/*********************************************************************** Random Access ***********************************************************************/

namespace

randomaccess_internal

{

template

typename

struct

RandomAccessable

Dictionary

>> {

static

const

bool

CanRead

true

;

static

const

bool

CanResize

false

; };

template

typename

struct

RandomAccess

Dictionary

>> {

static

vint

GetCount

(

const

Dictionary

) {

return

Count

(); }

static

Pair

GetValue

(

const

Dictionary

vint

index

) {

return

Pair

Keys

().

Get

(

index

Values

().

Get

(

index

)); }

static

void

AppendValue

(

Dictionary

const

Pair

value

) {

Set

(

value

key

value

); } }; } } }

#endif