PartialOrdering.h

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

#ifndef VCZH_COLLECTIONS_PARTIALORDERING

#define VCZH_COLLECTIONS_PARTIALORDERING

#include "Dictionary.h"

namespace

{

namespace

collections

{

/*********************************************************************** Partial Ordering ***********************************************************************/

namespace

{

/// <summary>

/// Node contains extra information for sorted objects.

/// </summary>

struct

Node

{

bool

visited

false

;

/// <summary>The index used in [F:vl.collections.PartialOrderingProcessor.components], specifying the component that contain this node.</summary>

vint

component

= -

;

/// <summary>All nodes that this node depends on.</summary>

const

List

vint

ins

nullptr

;

/// <summary>All nodes that this node is depended by.</summary>

const

List

vint

outs

nullptr

;

/// <summary>

/// If [M:vl.collections.PartialOrderingProcessor.InitWithSubClass`2] is used,

/// a node becomes a sub class representing objects.

/// An object will not be shared by different sub classes.

/// In this case, this field is a pointer to an array of indexes of objects.

/// The index is used in "items" argument in [M:vl.collections.PartialOrderingProcessor.InitWithSubClass`2]

/// </summary>

const

vint

firstSubClassItem

nullptr

;

/// <summary>

/// When <see cref="firstSubClassItem"/> is available,

/// this field is the number of indexes in the array.

/// </summary>

vint

subClassItemCount

; };

/// <summary>

/// Component is a unit in sorting result.

/// If a component contains more than one node,

/// it means that nodes in this component depend on each other by the given relationship.

/// It is not possible to tell which node should be place before others for all nodes in this component.

/// If all nodes are completely partial ordered,

/// there should be only one node in all components.

/// </summary>

struct

Component

{

/// <summary>

/// Pointer to the array of all indexes of nodes in this component.

/// Index is used in [F:vl.collections.PartialOrderingProcessor.nodes].

/// </summary>

const

vint

firstNode

nullptr

;

/// <summary>The number of nodes in this component.</summary>

vint

nodeCount

; }; } }

namespace

collections

{

/// <summary>

/// PartialOrderingProcessor is used to sort objects by given relationships among them.

/// The relationship is defined by dependance.

/// If A depends on B, then B will be place before A after sorting.

/// If a group of objects depends on each other by the given relationship,

/// they will be grouped together in the sorting result.

/// </summary>

class

PartialOrderingProcessor

public

Object

{

template

typename

TList

using

GroupOf

Group

typename

TList

::ElementType,

typename

TList

::ElementType>;

protected

List

vint

emptyList

;

// make a pointer to an empty list available

Group

vint

ins

;

// if a depends on b, ins.Contains(a, b)

Group

vint

outs

;

// if a depends on b, outs.Contains(b, a)

Array

vint

firstNodesBuffer

;

// one buffer for all Component::firstNode

Array

vint

subClassItemsBuffer

;

// one buffer for all Node::firstSubClassItem

void

InitNodes

(

vint

itemCount

);

void

VisitUnvisitedNode

(

Node

node

Array

vint

reversedOrder

vint

used

);

void

AssignUnassignedNode

(

Node

node

vint

componentIndex

vint

used

);

public

/// <summary>After <see cref="Sort"/> is called, this field stores all nodes referenced by sorted components.</summary>

/// <remarks>

/// The same order is kept as the "items" argument in <see cref="InitWithGroup`1"/>, and <see cref="InitWithFunc`2"/>.

/// If sub classing is enabled by calling <see cref="InitWithSubClass`2"/>,

/// a node represents a sub class of objects.

/// In this case, the order in this field does not matter,

/// [F:vl.collections.po.Node.firstSubClassItem] stores indexes of objects in this sub class.

/// </remarks>

Array

Node

nodes

;

/// <summary>After <see cref="Sort"/> is called, this field stores all sorted components in order.</summary>

List

Component

components

;

/// <summary>

/// Sort objects by given relationships. It will crash if this method is called for more than once.

/// </summary>

/// <remarks>

/// One and only one of <see cref="InitWithGroup`1"/>, <see cref="InitWithFunc`2"/> or <see cref="InitWithSubClass`2"/> must be called to set data for sorting.

/// And then call <see cref="Sort"/> to sort objects and store the result in <see cref="components"/>.

/// </remarks>

void

Sort

();

/// <summary>Set data for sorting, by providing a list for objects, and a group for their relationship.</summary>

/// <typeparam name="TList">Type of the list for objects. <see cref="Array`*"/>, <see cref="List`*"/> or <see cref="SortedList`*"/> are recommended.</typeparam>

/// <param name="items">List of objects for sorting.</param>

/// <param name="depGroup">Relationship of objects for sorting in <see cref="Group`*"/>. Both keys and values are elements in "items". To say that a depends on b, do depGroup.Add(a, b).</param>

/// <example><![CDATA[

/// int main()

/// {

/// // apple

/// // ^

/// // |

/// // ball

/// // ^ \

/// // / V

/// // cat <-- dog

/// // ^ ^

/// // / \

/// // elephant fish

///

/// List<WString> items;

/// items.Add(L"elephant");

/// items.Add(L"fish");

/// items.Add(L"ball");

/// items.Add(L"cat");

/// items.Add(L"dog");

/// items.Add(L"apple");

///

/// Group<WString, WString> depGroup;

/// depGroup.Add(L"ball", L"apple");

/// depGroup.Add(L"cat", L"ball");

/// depGroup.Add(L"ball", L"dog");

/// depGroup.Add(L"dog", L"cat");

/// depGroup.Add(L"elephant", L"cat");

/// depGroup.Add(L"fish", L"dog");

///

/// PartialOrderingProcessor pop;

/// pop.InitWithGroup(items, depGroup);

/// pop.Sort();

///

/// for (vint i = 0; i < pop.components.Count(); i++)

/// {

/// auto& c = pop.components[i];

/// Console::WriteLine(

/// L"Component " + itow(i) + L": " +

/// Range<vint>(0, c.nodeCount)

/// .Select([&](vint ni){ return items[c.firstNode[ni]]; })

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

/// );

/// }

///

/// for (vint i = 0; i < pop.nodes.Count(); i++)

/// {

/// auto& n = pop.nodes[i];

/// if(n.outs->Count() > 0)

/// {

/// Console::WriteLine(

/// L"Node " + items[i] + L" <- " +

/// From(*n.outs)

/// .Select([&](vint ni){ return items[ni]; })

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

/// );

/// }

/// ]]></example>

template

typename

TList

void

InitWithGroup

(

const

TList

items

const

GroupOf

TList

depGroup

) {

CHECK_ERROR(nodes.Count() == 0, L"PartialOrdering::InitWithGroup(items, depGroup)#Initializing twice is not allowed.");

{

(!(

nodes

Count

() ==

))

throw

Error

(

L"PartialOrdering::InitWithGroup(items, depGroup)#Initializing twice is not allowed."

);}

while

(

);

for

(

vint

;

depGroup

Count

();

++) {

vint

fromNode

items

.IndexOf(

KeyType

typename

TList

::ElementType>::

GetKeyValue

(

depGroup

Keys

()

[

]));

CHECK_ERROR(fromNode != -1, L"PartialOrdering::InitWithGroup(items, depGroup)#The key in outsGroup does not exist in items.");

{

(!(

fromNode

!= -

))

throw

Error

(

L"PartialOrdering::InitWithGroup(items, depGroup)#The key in outsGroup does not exist in items."

);}

while

(

);

auto

edges

depGroup

GetByIndex

(

);

for

(

vint

;

edges

Count

();

++) {

vint

toNode

items

.IndexOf(

KeyType

typename

TList

::ElementType>::

GetKeyValue

(

edges

[

]));

CHECK_ERROR(toNode != -1, L"PartialOrdering::InitWithGroup(items, depGroup)#The value in outsGroup does not exist in items.");

{

(!(

toNode

!= -

))

throw

Error

(

L"PartialOrdering::InitWithGroup(items, depGroup)#The value in outsGroup does not exist in items."

);}

while

(

);

ins

Add

(

fromNode

toNode

);

outs

Add

(

toNode

fromNode

); } }

InitNodes

(

items

.Count()); }

/// <summary>Set data for sorting, by providing a list for objects, and a function for their relationship.</summary>

/// <typeparam name="TList">Type of the list for objects. <see cref="Array`*"/>, <see cref="List`*"/> or <see cref="SortedList`*"/> are recommended.</typeparam>

/// <typeparam name="TFunc">Type of the function that defines relationships of objects.</typeparam>

/// <param name="items">List of objects for sorting.</param>

/// <param name="depFunc">Relationship of objects for sorting, both arguments are elements in "items". To say that a depends on b, depFunc(a, b) must returns true.</param>

/// <example><![CDATA[

/// int main()

/// {

/// // apple

/// // ^

/// // |

/// // ball

/// // ^ \

/// // / V

/// // cat <-- dog

/// // ^ ^

/// // / \

/// // elephant fish

///

/// List<WString> items;

/// items.Add(L"elephant");

/// items.Add(L"fish");

/// items.Add(L"ball");

/// items.Add(L"cat");

/// items.Add(L"dog");

/// items.Add(L"apple");

///

/// auto depFunc = [](const WString& a, const WString& b)

/// {

/// return

/// (a == L"ball" && b == L"apple") ||

/// (a == L"cat" && b == L"ball") ||

/// (a == L"ball" && b == L"dog") ||

/// (a == L"dog" && b == L"cat") ||

/// (a == L"elephant" && b == L"cat") ||

/// (a == L"fish" && b == L"dog")

/// ;

/// };

///

/// PartialOrderingProcessor pop;

/// pop.InitWithFunc(items, depFunc);

/// pop.Sort();

///

/// for (vint i = 0; i < pop.components.Count(); i++)

/// {

/// auto& c = pop.components[i];

/// Console::WriteLine(

/// L"Component " + itow(i) + L": " +

/// Range<vint>(0, c.nodeCount)

/// .Select([&](vint ni){ return items[c.firstNode[ni]]; })

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

/// );

/// }

///

/// for (vint i = 0; i < pop.nodes.Count(); i++)

/// {

/// auto& n = pop.nodes[i];

/// if(n.outs->Count() > 0)

/// {

/// Console::WriteLine(

/// L"Node " + items[i] + L" <- " +

/// From(*n.outs)

/// .Select([&](vint ni){ return items[ni]; })

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

/// );

/// }

/// ]]></example>

template

typename

TList

typename

TFunc

void

InitWithFunc

(

const

TList

items

TFunc

depFunc

) {

GroupOf

TList

depGroup

;

for

(

vint

;

items

.Count();

++) {

for

(

vint

;

items

.Count();

++) {

(

depFunc

(

items

[

items

[

])) {

depGroup

Add

(

items

[

items

[

]); } } }

InitWithGroup

(

items

depGroup

); }

/// <summary>Set data for sorting, by providing a list for objects, and a group for their relationship, and a dictionary for sub classing objects.</summary>

/// <typeparam name="TList">Type of the list for objects. <see cref="Array`*"/>, <see cref="List`*"/> or <see cref="SortedList`*"/> are recommended.</typeparam>

/// <typeparam name="TSubClass">Type of a sub class.</typeparam>

/// <param name="items">List of objects for sorting.</param>

/// <param name="depGroup">Relationship of objects for sorting in <see cref="Group`*"/>. Both keys and values are elements in "items". To say that a depends on b, do depGroup.Add(a, b).</param>

/// <param name="subClasses">Sub classing objects. Keys are elements in "items". If multiple keys have the same value in this dictionary, then these objects are in the same sub class.</param>

/// <remarks>

/// Relationships are defined on objects.

/// By sub classing objects,

/// relationships of sub classes are calculated from "depGroup".

/// If object A in sub class X depends on object B in sub class Y, then sub class X depends on sub class Y.

/// It is allowed that relatipnships on sub classes are not completely partial ordered,

/// in this case, some components may contain multiple sub classes.

/// </remarks>

/// <example><![CDATA[

/// int main()

/// {

/// // apple

/// // ^

/// // |

/// // ball

/// // ^ \

/// // / V

/// // cat <-- dog

/// // ^ ^

/// // / \

/// // elephant fish

///

/// List<WString> items;

/// for (vint i = 1; i <= 2; i++)

/// {

/// items.Add(L"apple_" + itow(i));

/// items.Add(L"ball_" + itow(i));

/// items.Add(L"cat_" + itow(i));

/// items.Add(L"dog_" + itow(i));

/// items.Add(L"elephant_" + itow(i));

/// items.Add(L"fish_" + itow(i));

/// }

///

/// Group<WString, WString> depGroup;

/// depGroup.Add(L"ball_2", L"apple_1");

/// depGroup.Add(L"cat_2", L"ball_1");

/// depGroup.Add(L"ball_2", L"dog_1");

/// depGroup.Add(L"dog_2", L"cat_1");

/// depGroup.Add(L"elephant_2", L"cat_1");

/// depGroup.Add(L"fish_2", L"dog_1");

///

/// Dictionary<WString, vint> subClass;

/// for (vint i = 1; i <= 2; i++)

/// {

/// subClass.Add(L"apple_" + itow(i), 1);

/// subClass.Add(L"ball_" + itow(i), 2);

/// subClass.Add(L"cat_" + itow(i), 3);

/// subClass.Add(L"dog_" + itow(i), 4);

/// subClass.Add(L"elephant_" + itow(i), 5);

/// subClass.Add(L"fish_" + itow(i), 6);

/// }

///

/// PartialOrderingProcessor pop;

/// pop.InitWithSubClass(items, depGroup, subClass);

/// pop.Sort();

///

/// for (vint i = 0; i < pop.components.Count(); i++)

/// {

/// auto& c = pop.components[i];

/// Console::WriteLine(

/// L"Component " + itow(i) + L": sub classes" +

/// Range<vint>(0, c.nodeCount)

/// .Select([&](vint ni) { return c.firstNode[ni]; })

/// .Aggregate<WString>(L"", [](const WString& a, vint b) { return a + L" " + itow(b); })

/// );

/// }

///

/// for (vint i = 0; i < pop.nodes.Count(); i++)

/// {

/// auto& n = pop.nodes[i];

/// Console::WriteLine(L"Sub class " + itow(i));

///

/// Console::WriteLine(

/// Range<vint>(0, n.subClassItemCount)

/// .Select([&](vint si) { return n.firstSubClassItem[si]; })

/// .Aggregate<WString>(L" :", [&](const WString& a, vint b) { return a + L" " + items[b]; })

/// );

///

/// if (n.outs->Count() > 0)

/// {

/// Console::WriteLine(

/// From(*n.outs)

/// .Aggregate<WString>(L" <- sub classes", [](const WString& a, vint b) { return a + L" " + itow(b); })

/// );

/// }

/// ]]></example>

template

typename

TList

typename

TSubClass

void

InitWithSubClass

(

const

TList

items

const

GroupOf

TList

depGroup

const

Dictionary

typename

TList

::ElementType,

TSubClass

subClasses

) {

CHECK_ERROR(nodes.Count() == 0, L"PartialOrdering::InitWithSubClass(items, degGroup, subClasses)#Initializing twice is not allowed.");

{

(!(

nodes

Count

() ==

))

throw

Error

(

L"PartialOrdering::InitWithSubClass(items, degGroup, subClasses)#Initializing twice is not allowed."

);}

while

(

);

using

ElementType

typename

TList

::ElementType;

using

ElementKeyType

KeyType

ElementType

Group

TSubClass

ElementType

scItems

;

SortedList

ElementType

singleItems

;

for

(

vint

;

subClasses

Count

();

++) {

const

auto

key

subClasses

Keys

()

[

];

const

auto

value

subClasses

Values

()

[

];

scItems

Add

(

value

key

); }

for

(

vint

;

items

.Count();

++) {

const

auto

item

items

[

];

subClasses

Keys

().

Contains

(

ElementKeyType

GetKeyValue

(

item

))) {

singleItems

Add

(

item

); } }

auto

getSubClass

= [&](

const

ElementType

item

) {

vint

index

subClasses

Keys

().

IndexOf

(

ElementKeyType

GetKeyValue

(

item

));

(

index

!= -

) {

index

scItems

Keys

().

IndexOf

(

KeyType

TSubClass

>::

GetKeyValue

(

subClasses

Values

()

[

index

]));

CHECK_ERROR(index != -1, L"PartialOrdering::InitWithSubClass(items, degGroup, subClasses)#Internal Error.");

{

(!(

index

!= -

))

throw

Error

(

L"PartialOrdering::InitWithSubClass(items, degGroup, subClasses)#Internal Error."

);}

while

(

);

return

index

; }

else

{

index

singleItems

IndexOf

(

ElementKeyType

GetKeyValue

(

item

));

CHECK_ERROR(index != -1, L"PartialOrdering::InitWithSubClass(items, degGroup, subClasses)#Internal Error.");

{

(!(

index

!= -

))

throw

Error

(

L"PartialOrdering::InitWithSubClass(items, degGroup, subClasses)#Internal Error."

);}

while

(

);

return

scItems

Count

() +

index

; } };

for

(

vint

;

depGroup

Count

();

++) {

const

auto

key

depGroup

Keys

()

[

];

vint

keyIndex

getSubClass

(

key

);

const

auto

values

depGroup

GetByIndex

(

);

for

(

vint

;

values

Count

();

++) {

const

auto

value

values

[

];

vint

valueIndex

getSubClass

(

value

);

ins

Contains

(

keyIndex

valueIndex

)) {

ins

Add

(

keyIndex

valueIndex

); } } }

for

(

vint

;

ins

Count

();

++) {

vint

key

ins

Keys

()

[

];

const

auto

values

ins

GetByIndex

(

);

for

(

vint

;

values

Count

();

++) {

outs

Add

(

values

[

key

); } }

InitNodes

(

scItems

Count

() +

singleItems

Count

());

subClassItemsBuffer

Resize

(

items

.Count());

vint

used

;

vint

scItemCount

scItems

Keys

().

Count

();

for

(

vint

;

nodes

Count

();

++) {

auto

node

nodes

[

];

node

firstSubClassItem

= &

subClassItemsBuffer

[

used

];

(

scItemCount

) {

const

auto

values

scItems

GetByIndex

(

);

for

(

vint

;

values

Count

();

++) {

subClassItemsBuffer

[

used

++] =

items

.IndexOf(

ElementKeyType

GetKeyValue

(

values

[

])); }

node

subClassItemCount

values

Count

(); }

else

{

subClassItemsBuffer

[

used

++] =

items

.IndexOf(

ElementKeyType

GetKeyValue

(

singleItems

[

scItemCount

]));

node

subClassItemCount

; } } } }; } }

#endif