PartialOrdering.cpp

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

#include "PartialOrdering.h"

namespace

{

namespace

collections

{

using

namespace

;

/*********************************************************************** PartialOrderingProcessor ***********************************************************************/

void

PartialOrderingProcessor

InitNodes

(

vint

itemCount

) {

nodes

Resize

(

itemCount

);

for

(

vint

;

itemCount

;

++) {

auto

node

nodes

[

];

node

ins

= &

emptyList

;

node

outs

= &

emptyList

;

vint

inIndex

ins

Keys

().

IndexOf

(

);

vint

outIndex

outs

Keys

().

IndexOf

(

);

(

inIndex

!= -

) {

node

ins

= &

ins

GetByIndex

(

inIndex

); }

(

outIndex

!= -

) {

node

outs

= &

outs

GetByIndex

(

outIndex

); } } }

void

PartialOrderingProcessor

VisitUnvisitedNode

(

Node

node

Array

vint

reversedOrder

vint

used

) {

node

visited

true

;

for

(

vint

node

outs

Count

() -

;

--) {

auto

outNode

nodes

[

node

outs

Get

(

)];

outNode

visited

) {

VisitUnvisitedNode

(

outNode

reversedOrder

used

); } }

reversedOrder

[

used

++] = (

vint

)(&

node

- &

nodes

[

]); }

void

PartialOrderingProcessor

AssignUnassignedNode

(

Node

node

vint

componentIndex

vint

used

) {

node

component

componentIndex

;

firstNodesBuffer

[

used

++] = (

vint

)(&

node

- &

nodes

[

]);

for

(

vint

;

node

ins

Count

();

++) {

auto

inNode

nodes

[

node

ins

Get

(

)];

(

inNode

component

== -

) {

AssignUnassignedNode

(

inNode

componentIndex

used

); } } }

void

PartialOrderingProcessor

Sort

() {

// Kosaraju's Algorithm

CHECK_ERROR(components.Count() == 0, L"PartialOrdering::Sort()#Sorting twice is not allowed.");

{

(!(

components

Count

() ==

))

throw

Error

(

L"PartialOrdering::Sort()#Sorting twice is not allowed."

);}

while

(

);

Array

vint

reversedOrder

(

nodes

Count

()); {

vint

used

;

for

(

vint

nodes

Count

() -

;

--) {

auto

node

nodes

[

];

node

visited

) {

VisitUnvisitedNode

(

node

reversedOrder

used

); } } }

firstNodesBuffer

Resize

(

nodes

Count

()); {

vint

lastUsed

;

vint

used

;

for

(

vint

reversedOrder

Count

() -

;

--) {

auto

node

nodes

[

reversedOrder

[

]];

(

node

component

== -

) {

AssignUnassignedNode

(

node

components

Count

(),

used

);

Component

component

;

component

firstNode

= &

firstNodesBuffer

[

lastUsed

];

component

nodeCount

used

lastUsed

;

lastUsed

used

;

components

Add

(

component

); } } } } } }