Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
Run.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <ext/algorithm>
9#include <ext/iterator>
10
11#include <string/LinearString.h>
14
15#include <automaton/FSM/DFA.h>
16#include <automaton/FSM/NFA.h>
18#include <automaton/TA/DFTA.h>
19#include <automaton/TA/NFTA.h>
25#include <automaton/PDA/DPDA.h>
26#include <automaton/PDA/NPDA.h>
27#include <automaton/PDA/NPDTA.h>
28#include <global/GlobalData.h>
29
31
32#include <alib/deque>
33
35
36namespace automaton {
37
38namespace run {
39
44class Run {
45
46 template < class SymbolType >
47 struct graphStructuredStack {
48 struct Element {
49 Element ( std::shared_ptr < Element > parent, SymbolType data ) : m_parent ( std::move ( parent) ), m_data ( std::move ( data ) ) {}
50 std::shared_ptr < Element > m_parent;
52 };
53
54 graphStructuredStack ( std::shared_ptr < Element > value ) : m_value ( std::move ( value ) ) { }
55
56 std::shared_ptr < Element > m_value;
57
58 static std::strong_ordering compareElements ( std::shared_ptr < Element > first, std::shared_ptr < Element > second ) {
59 if ( first == nullptr || second == nullptr )
60 return first <=> second;
61
62 std::strong_ordering res = first->m_data <=> second->m_data;
63 if ( res != 0 )
64 return res;
65
66 return compareElements ( first->m_parent, second->m_parent );
67 }
68
69 std::strong_ordering operator <=> ( const graphStructuredStack < SymbolType > & other ) const {
70 return compareElements ( m_value, other.m_value );
71 }
72 };
73
74 template < class Type >
75 static ext::deque < Type > reconstruct ( graphStructuredStack < Type > stack ) {
76 std::shared_ptr < typename graphStructuredStack < Type >::Element > stackNode = stack.m_value;
77 ext::deque < Type > finalContent;
78 while ( stackNode ) {
79 finalContent.push_front ( stackNode->m_data );
80 stackNode = stackNode->m_parent;
81 }
82 return finalContent;
83 }
84
101 template < class SymbolType, class StateType >
103
120 template < class SymbolType, class StateType >
122
123 template < class SymbolType, class StateType >
125
142 template < class SymbolType, class StateType >
144
155 template < class SymbolType >
156 static bool canPop ( const ext::deque < SymbolType > & pushdownStore, const ext::vector < SymbolType > & pop );
157
158 template < class Type >
159 static bool canPop ( graphStructuredStack < Type > pushdownStore, const ext::vector < Type > & pop );
160
161public:
176 template < class SymbolType, class StateType >
178
193 template < class SymbolType, class StateType >
195
210 template < class SymbolType, class StateType >
212
228 template < class SymbolType, class StateType >
230
246 template < class SymbolType, class StateType >
248
249 template < class SymbolType, class StateType >
251
267 template < class SymbolType, class StateType >
269
286 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
288
305 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
307
324 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
326
343 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
345
362 template < class InputSymbolType, class OutputSymbolType, class PushdownStoreSymbolType, class StateType >
364
380 template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
382};
383
384// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
385
386template < class SymbolType, class StateType >
388 unsigned i = 0;
389 ext::set < unsigned > occurrences;
390 StateType state = automaton.getInitialState ( );
391
392 for ( const SymbolType & symbol : string.getContent ( ) ) {
393 if ( automaton.getFinalStates ( ).contains ( state ) )
394 occurrences.insert ( i );
395
397 common::Streams::log << state << std::endl;
398
399 auto transition = automaton.getTransitions ( ).find ( ext::make_pair ( state, symbol ) );
400
401 if ( transition == automaton.getTransitions ( ).end ( ) )
402 return ext::make_tuple ( false, state, occurrences );
403
404 state = transition->second;
405 i++;
406 }
407
408 if ( automaton.getFinalStates ( ).contains ( state ) )
409 occurrences.insert ( i );
410
412 common::Streams::log << state << std::endl;
413
414 return ext::make_tuple ( true, state, occurrences );
415}
416
417// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
418
419template < class SymbolType, class StateType >
421 unsigned i = 0;
422 ext::set < unsigned > occurrences;
424 automaton.getInitialState ( )
425 };
426
427 for ( const StateType & state : states )
428 if ( automaton.getFinalStates ( ).contains ( state ) )
429 occurrences.insert ( i );
430
432 common::Streams::log << states << std::endl;
433
434 for ( const SymbolType & symbol : string.getContent ( ) ) {
436
437 for ( const StateType & state : states ) {
438 auto transitions = automaton.getTransitions ( ).equal_range ( ext::make_pair ( state, symbol ) );
439
440 for ( const auto & transition : transitions )
441 next.insert ( transition.second );
442 }
443
444 i++;
445 states = next;
446
447 for ( const StateType & state : states )
448 if ( automaton.getFinalStates ( ).contains ( state ) )
449 occurrences.insert ( i );
450
452 common::Streams::log << states << std::endl;
453 }
454
455 return ext::make_tuple ( true, states, occurrences );
456}
457
458// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
459
460template < class SymbolType, class StateType >
462 unsigned i = 0;
463 ext::set < unsigned > occurrences;
465 automaton.getInitialState ( )
466 };
467
468 for ( const StateType & state : states )
469 if ( automaton.getFinalStates ( ).contains ( state ) )
470 occurrences.insert ( i );
471
473 common::Streams::log << states << std::endl;
474
475 for ( const SymbolType & symbol : string.getContent ( ) ) {
477
478 for ( const StateType & state : states ) {
479 auto transitions = automaton.getTransitions ( ).equal_range ( ext::make_pair ( state, common::symbol_or_epsilon < SymbolType > ( symbol ) ) );
480
481 if ( transitions.empty ( ) ) continue;
482
483 for ( const auto & transition : transitions )
484 next.insert ( transition.second );
485 }
486
487 ext::set < StateType > epsilonNext;
488
489 for ( const StateType & state : next ) {
491 epsilonNext.insert ( closure.begin ( ), closure.end ( ) );
492 }
493
494 i++;
495 states = epsilonNext;
496
497 for ( const StateType & state : states )
498 if ( automaton.getFinalStates ( ).contains ( state ) )
499 occurrences.insert ( i );
500
502 common::Streams::log << states << std::endl;
503 }
504
505 return ext::make_tuple ( true, states, occurrences );
506}
507
508// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
509
510template < class SymbolType, class StateType >
513
514 states.reserve ( node.getData ( ).getRank ( ) );
515
516 unsigned tmp = i;
517 i++;
518
519 bool sign = true;
520
521 for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) ) {
522 ext::pair < bool, StateType > res = calculateState ( automaton, child, occ, i );
523
524 if ( ! res.first )
525 sign = false;
526 else
527 states.push_back ( res.second );
528 }
529
530 if ( ! sign )
531 return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
532
533 const auto & it = automaton.getTransitions ( ).find ( ext::make_pair ( node.getData ( ), states ) );
534
535 if ( it == automaton.getTransitions ( ).end ( ) ) return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
536
537 StateType state = it->second;
538
539 if ( automaton.getFinalStates ( ).contains ( state ) )
540 occ.insert ( tmp );
541
543 common::Streams::log << state << std::endl;
544
545 return ext::make_pair ( true, state );
546}
547
548template < class SymbolType, class StateType >
551 unsigned i = 0;
552 ext::pair < bool, StateType > res = calculateState ( automaton, tree.getContent ( ), occ, i );
553
554 return ext::make_tuple ( res.first, res.second, occ );
555}
556
557// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
558
559template < class SymbolType, class StateType >
561 ext::vector < StateType > childStates;
562
563 childStates.reserve ( node.getChildren ( ).size ( ) );
564
565 unsigned tmp = i ++;
566
567 for ( const ext::tree < SymbolType > & child : node.getChildren ( ) ) {
568 ext::pair < bool, StateType > res = calculateState ( automaton, child, occ, i );
569
570 if ( ! res.first )
571 return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
572 else
573 childStates.push_back ( res.second );
574 }
575
576 const auto & it = automaton.getTransitions ( ).find ( node.getData ( ) );
577
578 if ( it == automaton.getTransitions ( ).end ( ) )
579 return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
580
581 StateType state = it->second;
582
584 common::Streams::log << state << childStates;
585
586 for ( const StateType & childState : childStates ) {
587 const auto & itChildState = automaton.getTransitions ( ).find ( ext::make_pair ( state, childState ) );
588
589 if ( itChildState == automaton.getTransitions ( ).end ( ) ) {
591 common::Streams::log << "->" << label::FailStateLabel::instance < StateType > ( ) << std::endl;
592 return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
593 }
594
595 state = itChildState->second;
596
598 common::Streams::log << " -> " << state;
599 }
600
602 common::Streams::log << std::endl;
603
604 if ( automaton.getFinalStates ( ).contains ( state ) )
605 occ.insert ( tmp );
606
607 return ext::make_pair ( true, state );
608}
609
610template < class SymbolType, class StateType >
613 unsigned i = 0;
614 ext::pair < bool, StateType > res = calculateState ( automaton, tree.getContent ( ), occ, i );
615
616 return ext::make_tuple ( res.first, res.second, occ );
617}
618
619// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
620
621template < class SymbolType, class StateType >
624
625 unsigned tmp = i;
626 i++;
627
628 bool sign = true;
629
630 for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) ) {
631 ext::pair < bool, StateType > res = calculateState ( automaton, child, occ, i );
632
633 if ( ! res.first )
634 sign = false;
635 else
636 states.insert ( res.second );
637 }
638
639 if ( ! sign )
640 return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
641
642 const auto & it = automaton.getTransitions ( ).find ( ext::make_pair ( node.getData ( ), states ) );
643
644 if ( it == automaton.getTransitions ( ).end ( ) ) return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
645
646 StateType state = it->second;
647
648 if ( automaton.getFinalStates ( ).contains ( state ) )
649 occ.insert ( tmp );
650
652 common::Streams::log << state << std::endl;
653
654 return ext::make_pair ( true, state );
655}
656
657template < class SymbolType, class StateType >
660 unsigned i = 0;
661 ext::pair < bool, StateType > res = calculateState ( automaton, tree.getContent ( ), occ, i );
662
663 return ext::make_tuple ( res.first, res.second, occ );
664}
665
666// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
667
668template < class SymbolType, class StateType >
671
672 resStates.reserve ( node.getData ( ).getRank ( ) );
673
674 unsigned tmp = i;
675 i++;
676
677 bool sign = true;
678
679 for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) ) {
680 std::pair < bool, ext::set < StateType > > childStates = calculateStates ( automaton, child, occ, i );
681
682 if ( childStates.second.empty ( ) )
683 sign = false;
684
685 resStates.push_back ( childStates.second );
686 }
687
689
690 for ( const auto & transition : automaton.getTransitions ( ) ) {
691 if ( transition.first.first != node.getData ( ) )
692 continue;
693
694 unsigned rank = transition.first.first.getRank ( );
695 unsigned j;
696
697 for ( j = 0; j < rank; j++ )
698 if ( ! resStates [ j ].contains ( transition.first.second [ j ] ) )
699 break;
700
701 if ( j == rank )
702 states.insert ( transition.second );
703 }
704
705 for ( const StateType & state : states )
706 if ( automaton.getFinalStates ( ).contains ( state ) )
707 occ.insert ( tmp );
708
710 common::Streams::log << states << std::endl;
711
712 return ext::make_pair ( sign, states );
713}
714
715template < class SymbolType, class StateType >
718 unsigned i = 0;
719 ext::pair < bool, ext::set < StateType > > res = calculateStates ( automaton, tree.getContent ( ), occ, i );
720
721 return ext::make_tuple ( res.first, res.second, occ );
722}
723
724// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
725
726template < class SymbolType >
727bool Run::canPop ( const ext::deque < SymbolType > & pushdownStore, const ext::vector < SymbolType > & pop ) {
728 unsigned popSize = pop.size ( );
729 unsigned pushdownStoreSize = pushdownStore.size ( );
730
731 if ( pushdownStoreSize < popSize ) return false;
732
733 for ( unsigned i = 0; i < popSize; i++ )
734 if ( pop[i] != pushdownStore[pushdownStoreSize - i - 1] )
735 return false;
736
737 return true;
738}
739
740// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
741
742template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
744 StateType state = automaton.getInitialState ( );
746 automaton.getInitialSymbol ( )
747 };
748 unsigned i = 0;
750
751 for ( const InputSymbolType & symbol : string.getContent ( ) ) {
752 if ( automaton.getFinalStates ( ).contains ( state ) )
753 occ.insert ( i );
754
756 common::Streams::log << state << std::endl;
757
758 auto transition = automaton.getTransitions ( ).find ( ext::make_pair ( state, symbol ) );
759
760 if ( transition == automaton.getTransitions ( ).end ( ) )
761 return ext::make_tuple ( false, state, occ, pushdownStore );
762
763 const std::pair < ext::vector < PushdownStoreSymbolType >, ext::vector < PushdownStoreSymbolType > > & operation = automaton.getPushdownStoreOperations ( ).find ( symbol )->second;
764
765 if ( !canPop ( pushdownStore, operation.first ) )
766 return ext::make_tuple ( false, state, occ, pushdownStore );
767
768 for ( unsigned j = 0; j < operation.first.size ( ); j++ ) pushdownStore.pop_back ( );
769
770 for ( const auto & push : ext::make_reverse ( operation.second ) ) pushdownStore.push_back ( push );
771
772 state = transition->second;
773 i++;
774 }
775
776 if ( automaton.getFinalStates ( ).contains ( state ) )
777 occ.insert ( i );
778
780 common::Streams::log << state << std::endl;
781
782 return ext::make_tuple ( true, state, occ, pushdownStore );
783}
784
785// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
786
787template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
789 StateType state = automaton.getInitialState ( );
791 automaton.getBottomOfTheStackSymbol ( )
792 };
793 unsigned i = 0;
795
796 for ( const InputSymbolType & symbol : string.getContent ( ) ) {
797 if ( automaton.getFinalStates ( ).contains ( state ) )
798 occ.insert ( i );
799
801 common::Streams::log << state << std::endl;
802
803 if ( automaton.getCallInputAlphabet ( ).contains ( symbol ) ) {
804 auto transition = automaton.getCallTransitions ( ).find ( ext::make_pair ( state, symbol ) );
805
806 if ( transition == automaton.getCallTransitions ( ).end ( ) )
807 return ext::make_tuple ( false, state, occ, pushdownStore );
808
809 pushdownStore.push_back ( transition->second.second );
810 state = transition->second.first;
811 } else if ( automaton.getReturnInputAlphabet ( ).contains ( symbol ) ) {
812 auto transition = automaton.getReturnTransitions ( ).find ( ext::make_tuple ( state, symbol, pushdownStore.back ( ) ) );
813
814 if ( transition == automaton.getReturnTransitions ( ).end ( ) )
815 return ext::make_tuple ( false, state, occ, pushdownStore );
816
817 if ( pushdownStore.back ( ) != automaton.getBottomOfTheStackSymbol ( ) ) pushdownStore.pop_back ( );
818
819 state = transition->second;
820 } else if ( automaton.getLocalInputAlphabet ( ).contains ( symbol ) ) {
821 auto transition = automaton.getLocalTransitions ( ).find ( ext::make_pair ( state, symbol ) );
822
823 if ( transition == automaton.getLocalTransitions ( ).end ( ) )
824 return ext::make_tuple ( false, state, occ, pushdownStore );
825
826 state = transition->second;
827 } else {
828 return ext::make_tuple ( false, state, occ, pushdownStore );
829 }
830
831 i++;
832 }
833
834 if ( automaton.getFinalStates ( ).contains ( state ) )
835 occ.insert ( i );
836
838 common::Streams::log << state << std::endl;
839
840 return ext::make_tuple ( true, state, occ, pushdownStore );
841}
842
843// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
844
845template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
847 StateType state = automaton.getInitialState ( );
849 automaton.getBottomOfTheStackSymbol ( )
850 };
851 unsigned i = 0;
853
854 if ( automaton.getFinalStates ( ).contains ( state ) )
855 occ.insert ( i );
856
858 common::Streams::log << state << std::endl;
859
860 for ( auto symbolIter = string.getContent ( ).begin ( ); symbolIter != string.getContent ( ).end ( ); ) {
861
862 bool transitionFound = false;
863
864 auto callTransition = automaton.getCallTransitions ( ).find ( std::pair < StateType, common::symbol_or_epsilon < InputSymbolType > > ( state, * symbolIter ) );
865
866 if ( callTransition != automaton.getCallTransitions ( ).end ( ) ) {
867 symbolIter++;
868 i++;
869 } else {
870 callTransition = automaton.getCallTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
871 }
872
873 if ( callTransition != automaton.getCallTransitions ( ).end ( ) ) {
874 pushdownStore.push_back ( callTransition->second.second );
875 state = callTransition->second.first;
876 transitionFound = true;
877 }
878
879 if ( ! transitionFound ) {
880 auto returnTransition = automaton.getReturnTransitions ( ).find ( std::tuple < StateType, common::symbol_or_epsilon < InputSymbolType >, PushdownStoreSymbolType > ( state, * symbolIter, pushdownStore.back ( ) ) );
881
882 if ( returnTransition != automaton.getReturnTransitions ( ).end ( ) ) {
883 symbolIter++;
884 i++;
885 } else {
886 returnTransition = automaton.getReturnTransitions ( ).find ( std::make_tuple ( state, common::symbol_or_epsilon < InputSymbolType > ( ), pushdownStore.back ( ) ) );
887 }
888
889 if ( returnTransition != automaton.getReturnTransitions ( ).end ( ) ) {
890 pushdownStore.pop_back ( );
891 state = returnTransition->second;
892 transitionFound = true;
893 }
894 }
895
896 if ( ! transitionFound ) {
897 auto localTransition = automaton.getLocalTransitions ( ).find ( std::pair < StateType, common::symbol_or_epsilon < InputSymbolType > > ( state, * symbolIter ) );
898
899 if ( localTransition != automaton.getLocalTransitions ( ).end ( ) ) {
900 symbolIter++;
901 i++;
902 } else {
903 localTransition = automaton.getLocalTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
904 }
905
906 if ( localTransition != automaton.getLocalTransitions ( ).end ( ) ) {
907 state = localTransition->second;
908 transitionFound = true;
909 }
910 }
911
912 if ( ! transitionFound )
913 return ext::make_tuple ( false, state, occ, pushdownStore );
914
915 if ( automaton.getFinalStates ( ).contains ( state ) )
916 occ.insert ( i );
917
919 common::Streams::log << state << std::endl;
920 }
921
922 while ( true ) {
923
924 bool transitionFound = false;
925
926 auto callTransition = automaton.getCallTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
927
928 if ( callTransition != automaton.getCallTransitions ( ).end ( ) ) {
929 pushdownStore.push_back ( callTransition->second.second );
930 state = callTransition->second.first;
931 transitionFound = true;
932 }
933
934 if ( ! transitionFound ) {
935 auto returnTransition = automaton.getReturnTransitions ( ).find ( std::make_tuple ( state, common::symbol_or_epsilon < InputSymbolType > ( ), pushdownStore.back ( ) ) );
936
937 if ( returnTransition != automaton.getReturnTransitions ( ).end ( ) ) {
938 pushdownStore.pop_back ( );
939 state = returnTransition->second;
940 transitionFound = true;
941 }
942 }
943
944 if ( ! transitionFound ) {
945 auto localTransition = automaton.getLocalTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
946
947 if ( localTransition != automaton.getLocalTransitions ( ).end ( ) ) {
948 state = localTransition->second;
949 transitionFound = true;
950 }
951 }
952
953 if ( ! transitionFound )
954 break;
955
956 if ( automaton.getFinalStates ( ).contains ( state ) )
957 occ.insert ( i );
958
960 common::Streams::log << state << std::endl;
961 }
962
963 return ext::make_tuple ( true, state, occ, pushdownStore );
964}
965
966// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
967
968template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
970 StateType state = automaton.getInitialState ( );
972 automaton.getInitialSymbol ( )
973 };
975
976 for ( auto symbolIter = string.getContent ( ).begin ( ); symbolIter != string.getContent ( ).end ( ); ) {
977
978 if ( automaton.getFinalStates ( ).contains ( state ) )
979 occ.insert ( std::distance ( string.getContent ( ).begin ( ), symbolIter ) );
980
982 common::Streams::log << "State : " << state << std::endl;
983 common::Streams::log << "PushdownStore : " << pushdownStore << std::endl;
984 }
985
986 auto transitions = automaton.getTransitionsFromState ( state );
987 auto transition = transitions.begin ( );
988
989 for ( ; transition != transitions.end ( ); transition++ ) {
990 if ( ( std::get < 1 > ( transition->first ) != * symbolIter ) && !std::get < 1 > ( transition->first ).is_epsilon ( ) ) continue;
991
992 if ( canPop ( pushdownStore, std::get < 2 > ( transition->first ) ) ) break;
993 }
994
995 if ( transition == transitions.end ( ) )
996 return ext::make_tuple ( false, state, occ, pushdownStore );
997
999 common::Streams::log << "Transition: " << transition->first << " to " << transition->second << std::endl;
1000
1001 for ( unsigned j = 0; j < std::get < 2 > ( transition->first ).size ( ); j++ ) pushdownStore.pop_back ( );
1002
1003 for ( const auto & symbol : ext::make_reverse ( transition->second.second ) ) pushdownStore.push_back ( symbol );
1004
1005 state = transition->second.first;
1006
1007 if ( !std::get < 1 > ( transition->first ).is_epsilon ( ) ) {
1008 symbolIter++;
1009 }
1010 }
1011
1012 if ( automaton.getFinalStates ( ).contains ( state ) )
1013 occ.insert ( string.getContent ( ).size ( ) );
1014
1016 common::Streams::log << "State: " << state << std::endl;
1017 common::Streams::log << "PushdownStore: " << pushdownStore << std::endl;
1018 }
1019
1020 return ext::make_tuple ( true, state, occ, pushdownStore );
1021}
1022
1023// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1024
1025template < class Type >
1026bool Run::canPop ( graphStructuredStack < Type > pushdownStore, const ext::vector < Type > & pop ) {
1027 std::shared_ptr < typename graphStructuredStack < Type >::Element > node = pushdownStore.m_value;
1028 for ( const Type & symbol : pop ) {
1029 if ( node == nullptr || node->m_data != symbol )
1030 return false;
1031 node = node->m_parent;
1032 }
1033
1034 return true;
1035}
1036
1037// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1038
1039template < class InputSymbolType, class OutputSymbolType, class PushdownStoreSymbolType, class StateType >
1042
1043 ext::deque < ext::tuple < StateType, ext::set < unsigned >, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType >, graphStructuredStack < OutputSymbolType > > > bftQueue;
1044 graphStructuredStack < PushdownStoreSymbolType > initialStack ( std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( nullptr, automaton.getInitialSymbol ( ) ) );
1045 graphStructuredStack < OutputSymbolType > initialOutput ( nullptr );
1046 bftQueue . emplace_back ( automaton . getInitialState (), ext::set < unsigned > {}, string . getContent () . begin (), std::move ( initialStack ), std::move ( initialOutput ) );
1047
1048 ext::set < ext::tuple < StateType, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType > > > bftVisited;
1049
1050 while ( ! bftQueue . empty () ) {
1051 auto configuration = std::move ( bftQueue . front () );
1052 bftQueue . pop_front ();
1053
1054 StateType state = std::move ( std::get < 0 > ( configuration ) );
1055 ext::set < unsigned > occurrences = std::move ( std::get < 1 > ( configuration ) );
1056 typename ext::vector<InputSymbolType>::const_iterator symbolIter = std::get < 2 > ( configuration );
1057 graphStructuredStack < PushdownStoreSymbolType > stack = std::get < 3 > ( configuration );
1058 graphStructuredStack < OutputSymbolType > output = std::get < 4 > ( configuration );
1059
1060 if ( ! bftVisited.insert ( ext::make_tuple ( state, symbolIter, stack ) ).second )
1061 continue;
1062
1063 if ( symbolIter == string . getContent () . end () ) {
1064 if ( automaton . getFinalStates () . contains ( state ) || stack.m_value == nullptr ) {
1065 res.insert ( ext::make_tuple ( state, occurrences, reconstruct ( stack ), reconstruct ( output ) ) );
1066 }
1067 }
1068
1069 for ( const auto & transition : automaton . getTransitionsFromState ( state ) ) {
1070 if ( ( symbolIter == string.getContent ( ).end ( ) || std::get<1>(transition . first) != * symbolIter ) && ! std::get<1>(transition . first) . is_epsilon ( ) )
1071 continue;
1072
1073 const auto & pop = std::get<2>(transition . first);
1074
1075 if ( ! canPop ( stack, pop ) )
1076 continue;
1077
1078 std::shared_ptr < typename graphStructuredStack < PushdownStoreSymbolType >::Element > stackNodeCopy = stack.m_value;
1079 std::shared_ptr < typename graphStructuredStack < OutputSymbolType >::Element > outputNodeCopy = output.m_value;
1080
1081 for ( unsigned j = 0; j < pop . size (); j ++ ) {
1082 stackNodeCopy = stackNodeCopy -> m_parent;
1083 }
1084
1085 for ( const auto & elem : ext::make_reverse ( std::get<1>(transition . second ) ) ) {
1086 stackNodeCopy = std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( stackNodeCopy, elem );
1087 }
1088
1089 for ( const auto & elem : std::get<2>(transition . second) ) {
1090 outputNodeCopy = std::make_shared < typename graphStructuredStack < OutputSymbolType >::Element > ( outputNodeCopy, elem );
1091 }
1092
1093 typename ext::vector<InputSymbolType>::const_iterator nextSymbolIter = symbolIter;
1094 if ( ! std::get<1>(transition . first) . is_epsilon ( ) )
1095 ++ nextSymbolIter;
1096
1097 bftQueue . emplace_back ( std::get<0>(transition . second), occurrences, nextSymbolIter, graphStructuredStack < PushdownStoreSymbolType > ( stackNodeCopy ), graphStructuredStack < OutputSymbolType > ( outputNodeCopy ) );
1098 }
1099 }
1100
1101 return res;
1102}
1103
1104// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1105
1106template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1109
1110 ext::deque < ext::tuple < StateType, ext::set < unsigned >, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType > > > bftQueue;
1111 graphStructuredStack < PushdownStoreSymbolType > initialStack ( std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( nullptr, automaton.getInitialSymbol ( ) ) );
1112 bftQueue . emplace_back ( automaton . getInitialState (), ext::set < unsigned > {}, string . getContent () . begin (), std::move ( initialStack ) );
1113
1114 ext::set < ext::tuple < StateType, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType > > > bftVisited;
1115
1116 while ( ! bftQueue . empty () ) {
1117 auto configuration = std::move ( bftQueue . front () );
1118 bftQueue . pop_front ();
1119
1120 StateType state = std::move ( std::get < 0 > ( configuration ) );
1121 ext::set < unsigned > occurrences = std::move ( std::get < 1 > ( configuration ) );
1122 typename ext::vector<InputSymbolType>::const_iterator symbolIter = std::get < 2 > ( configuration );
1123 graphStructuredStack < PushdownStoreSymbolType > stack = std::get < 3 > ( configuration );
1124
1125 if ( ! bftVisited.insert ( ext::make_tuple ( state, symbolIter, stack ) ).second )
1126 continue;
1127
1128 if ( symbolIter == string . getContent () . end () ) {
1129 if ( automaton . getFinalStates () . contains ( state ) || stack.m_value == nullptr ) {
1130 res.insert ( ext::make_tuple ( state, occurrences, reconstruct ( stack ) ) );
1131 }
1132 }
1133
1134 for ( const auto & transition : automaton . getTransitionsFromState ( state ) ) {
1135 if ( ( symbolIter == string.getContent ( ).end ( ) || std::get<1>(transition . first) != * symbolIter ) && ! std::get<1>(transition . first) . is_epsilon ( ) )
1136 continue;
1137
1138 const auto & pop = std::get<2>(transition . first);
1139
1140 if ( ! canPop ( stack, pop ) )
1141 continue;
1142
1143 std::shared_ptr < typename graphStructuredStack < PushdownStoreSymbolType >::Element > stackNodeCopy = stack.m_value;
1144
1145 for ( unsigned j = 0; j < pop . size (); j ++ ) {
1146 stackNodeCopy = stackNodeCopy -> m_parent;
1147 }
1148
1149 for ( const auto & elem : ext::make_reverse ( std::get<1>(transition . second ) ) ) {
1150 stackNodeCopy = std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( stackNodeCopy, elem );
1151 }
1152
1153 typename ext::vector<InputSymbolType>::const_iterator nextSymbolIter = symbolIter;
1154 if ( ! std::get<1>(transition . first) . is_epsilon ( ) )
1155 ++ nextSymbolIter;
1156
1157 bftQueue . emplace_back ( std::get<0>(transition . second), occurrences, nextSymbolIter, graphStructuredStack < PushdownStoreSymbolType > ( stackNodeCopy ) );
1158 }
1159 }
1160
1161 return res;
1162}
1163
1164// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1165
1166} /* namespace run */
1167
1168} /* namespace automaton */
1169
Deterministic Z-Automaton in Arc-Factored Normal Form. Computation model for unranked regular tree la...
Definition: ArcFactoredDeterministicZAutomaton.h:65
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: DFTA.h:74
Deterministic pushdown automaton. Accepts subset of context free languages.
Definition: DPDA.h:78
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
Deterministic input driven pushdown automaton. Accepts subset of context free languages.
Definition: InputDrivenDPDA.h:79
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: NFTA.h:72
Definition: NPDA.h:74
Definition: NPDTA.h:75
Deterministic real time height deterministic pushdown automaton. Accepts subset of context free langu...
Definition: RealTimeHeightDeterministicDPDA.h:89
Deterministic unordered finite tree automaton without epsilon transitions. Accepts regular tree langu...
Definition: UnorderedDFTA.h:72
Deterministic visibly pushdown automaton. Accepts subset of context free languages.
Definition: VisiblyPushdownDPDA.h:86
static ext::set< StateType > epsilonClosure(const automaton::EpsilonNFA< SymbolType, StateType > &fsm, const StateType &q)
Definition: EpsilonClosure.h:125
Implementation of automaton run over its input.
Definition: Run.h:44
static bool verbose
Verbose flag. Some algorithms print additional runtime information about internal datastructures or t...
Definition: GlobalData.h:24
static ext::reference_wrapper< ext::ostream > log
Standard loging stream. Mapped to descriptor 4.
Definition: GlobalData.h:78
Definition: ranked_symbol.hpp:20
Definition: symbol_or_epsilon.hpp:24
Class extending the deque class from the standard library. Original reason is to allow printing of th...
Definition: deque.hpp:44
Definition: multiset.hpp:44
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Definition: set.hpp:44
Class introducing a tree with interface trying to be close to the interface of standard library conta...
Definition: tree.hpp:52
Class extending the tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
typename std::vector< T, Alloc >::const_iterator const_iterator
The type of constant values iterator.
Definition: vector.hpp:67
Linear string.
Definition: LinearString.h:57
Tree structure represented in its natural representation. The representation is so called ranked,...
Definition: RankedTree.h:72
Tree structure represented in its natural representation. The representation is so called ranked,...
Definition: UnorderedRankedTree.h:70
Tree represented in its natural representation. The representation is so called unranked,...
Definition: UnrankedTree.h:69
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
p second
Definition: ToRegExpAlgebraic.h:126
int i
Definition: AllEpsilonClosure.h:118
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
return closure
Definition: AllEpsilonClosure.h:142
return res
Definition: MinimizeByPartitioning.h:145
std::stack< ext::tuple< StateType, StateType, SymbolType > > stack
Definition: Compaction.h:83
Definition: ToGrammar.h:31
reverser< T > make_reverse(T &&container)
Reverese adaptor construction function.
Definition: iterator.hpp:544
bool contains(InputIt first, InputIt last, const Element &elem)
Linear version of search in a range of values.
Definition: algorithm.hpp:170
constexpr auto make_tuple(Elements &&... args)
Helper of extended tuple construction. The tuple is constructed from values pack, types are deduced.
Definition: tuple.hpp:203
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
auto begin(Container &&cont) -> decltype(std::forward(cont).begin())
Definition: iterator.hpp:900
void end()
Definition: measurements.cpp:19
Type
Definition: MeasurementTypes.hpp:20
Definition: Node.cpp:11
Definition: FordFulkerson.hpp:16
Definition: BackwardOccurrenceTest.h:17
std::shared_ptr< Element > m_parent
Definition: Run.h:50
Element(std::shared_ptr< Element > parent, SymbolType data)
Definition: Run.h:49