void ConvertFilterIntoIntVector(const yvector<CFilterPair>& r_Filter, yvector<int>& v_Filter)
{
    for (int i = 0; i < (int)r_Filter.size(); i++) {
        v_Filter.push_back(r_Filter[i].m_iItemID);
        v_Filter.push_back(r_Filter[i].m_iWordDistance);
    }
}

void CMultiWordCreator::SubstituteByMultiWord(SWordHomonymNum& WordHomonymNum, yvector<SWordHomonymNum>& WordIndexes)
{
    const CWord& multi_word = m_Words.GetWord(WordHomonymNum);

    int k1 = -1, k2 = -1;
    for (size_t i = 0; i < WordIndexes.size(); i++) {
        const CWord& w = m_Words.GetWord(WordIndexes[i]);
        if ((w.IsOriginalWord()) &&
            (w.GetSourcePair().FirstWord() == multi_word.GetSourcePair().FirstWord()))
            k1 = i;

        if (k1 != -1) {
            if (!w.IsOriginalWord())
                break;

            if (w.GetSourcePair().FirstWord() == multi_word.GetSourcePair().LastWord()) {
                k2 = i;
                break;
            }
        }
    }

    if ((k1 != -1) && (k2 != -1))
        for (int j = k2; j >= k1; j--)
            WordIndexes.erase(WordIndexes.begin() + j);

    if (k1 != -1)
        WordIndexes.insert(WordIndexes.begin() + k1, WordHomonymNum);
}

void CFilterCheck::ConvertToOriginalWords(ymap< int, yset<int> >& FilterItemToWords,
                                          const yvector<SWordHomonymNum>& ItemWrds, int iID)
{
    if (0 == ItemWrds.size()) return;
    yset<int>& rWrdIds = FilterItemToWords[iID];
    for (size_t i = 0; i < ItemWrds.size(); i++)
        rWrdIds.insert(m_MultiWordCreator.m_Words.GetWord(ItemWrds.at(i)).GetSourcePair().LastWord());
}

void CTopClauses::BuildClauseVariants(yvector<CClauseVariant>& ClauseVars)
{
    CClauseVariant ClauseVar(m_Words);
    ClauseVars.push_back(ClauseVar);
    BuildClauseVariantsRec(ClauseVars, m_FirstNode);
    for (size_t i = 0; i < ClauseVars.size(); i++)
        ClauseVars[i].CalculateBadWeight();
}

void ConvertRuleIntoIntVector(const CWorkRule& r_Rule, yvector<int>& v_Rule)
{
    v_Rule.push_back(r_Rule.m_OriginalRuleNo);
    v_Rule.push_back(r_Rule.m_LeftPart);
    v_Rule.push_back(r_Rule.m_RightPart.m_SynMainItemNo);
    for (int i = 0; i < (int)r_Rule.m_RightPart.m_Items.size(); i++)
        v_Rule.push_back(r_Rule.m_RightPart.m_Items[i]);
}

void TSurnamePredictor::SaveParadigma(TSurnameLemma& surnameLemma, yvector<TTempForm>& paradigma)
{
    if (surnameLemma.SurnameFlex.empty() ||
        (surnameLemma.Weight == 0))
        return;

    TGramBitSet stemGram;

    SurnameLemmasFlex.push_back(surnameLemma);

    unsigned char c = gBefore + 1;
    for (; c < gMax ; c++)
    {
        int i;
        for (i = 0 ; i < paradigma.ysize() ; i++)
        {
            if (!paradigma[i].Grammars.Test(NTGrammarProcessing::ch2tg(c)))
                break;
        }
        if (i >= paradigma.ysize())
            stemGram.Set(NTGrammarProcessing::ch2tg(c));
    }

    Stroka ss = stemGram.ToString(",");

    for (int i = 0 ; i < paradigma.ysize() ; i++)
    {
        TSurnameFlexMap::iterator it = SurnameFlex2Paradigmas.find(paradigma[i].Flex);

        if (it == SurnameFlex2Paradigmas.end())
        {
            TFormInfo formInfo;
            formInfo.SurnameLemmaFlexNo = SurnameLemmasFlex.ysize() - 1;
            formInfo.StemGrammar = stemGram;
            ss = TGramBitSet(paradigma[i].Grammars & ~stemGram).ToString(",");
            formInfo.FlexGrammars.push_back(paradigma[i].Grammars & ~stemGram);
            SurnameFlex2Paradigmas[paradigma[i].Flex] = yvector<TFormInfo>(1,formInfo);
        } else {
            yvector<TFormInfo>& infos = it->second;
            int j;
            for (j = 0; j < infos.ysize(); j++) {
                if (infos[j].SurnameLemmaFlexNo == (SurnameLemmasFlex.ysize() - 1)) {
                    ss = TGramBitSet(paradigma[i].Grammars & ~stemGram).ToString(",");
                    infos[j].FlexGrammars.push_back(paradigma[i].Grammars & ~stemGram);
                    break;
                }
            }
            if (j >= infos.ysize()) {
                TFormInfo formInfo;
                formInfo.SurnameLemmaFlexNo = SurnameLemmasFlex.ysize() - 1;
                formInfo.StemGrammar = stemGram;
                ss = TGramBitSet(paradigma[i].Grammars & ~stemGram).ToString(",");
                formInfo.FlexGrammars.push_back(paradigma[i].Grammars & ~stemGram);
                infos.push_back(formInfo);
            }
        }
    }
}

static void BuildRuleInfo(const yset<CWorkRule>& rules, yvector<CGLRRuleInfo>& res)
{
    res.clear();
    for (yset<CWorkRule>::const_iterator it = rules.begin(); it != rules.end(); ++it) {
        res.push_back();
        res.back().Init(&*it);
    }
    std::sort(res.begin(), res.end());
}

void TMixedDescriptorPool::CollectFiles(yvector<const TFileDescriptor*>& files) {
    files.clear();
    const yset<Stroka>& fileNames = Database.RequestedFiles();
    for (yset<Stroka>::const_iterator it = fileNames.begin(); it != fileNames.end(); ++it) {
        const TFileDescriptor* fd = FindFileByName(*it);
        if (fd)
            files.push_back(fd);
    }
}

void ConvertIntVectorIntoRule(const yvector<int>& v_Rule, CWorkRule& r_Rule)
{
    assert(v_Rule.size() > 3);

    r_Rule.m_OriginalRuleNo = v_Rule[0];
    r_Rule.m_LeftPart = v_Rule[1];
    r_Rule.m_RightPart.m_SynMainItemNo = v_Rule[2];
    for (int i = 3; i < (int)v_Rule.size(); i++)
        r_Rule.m_RightPart.m_Items.push_back(v_Rule[i]);
}

void SolveAmbiguity(yvector<COccurrence>& Occurrences)
{
    yvector<size_t> res;
    SolveAmbiguity(Occurrences, res);
    if (res.size() != Occurrences.size()) {
        yvector<COccurrence> tmp(res.size());
        for (size_t i = 0; i < res.size(); ++i)
            tmp[i] = Occurrences[res[i]];
        Occurrences.swap(tmp);
    }
}

void CGLRTable::Compact(const yvector< yvector<CSLRCell> >& table)
{
    Mask.clear();
    if (table.empty())
        return;

    Rows = table.size();
    Columns = table[0].size();
    YASSERT(Columns != 0);

    NGzt::TCompactStorageBuilder<ui32> ruleIndexStorageBuilder;
    yvector<ui32> tmp;

    Mask.resize((Rows * Columns - 1)/8 + 1);
    for (size_t row = 0; row < table.size(); ++row) {
        for (size_t column = 0; column < table[row].size(); ++column) {
            const CSLRCell& cell = table[row][column];
            if (cell.IsEmpty())
                continue;

            size_t index = row*Columns + column;
            Mask[index >> 3] |= 1 << (index & 7);
            if (cell.m_ReduceRules.size() == 1 && !cell.m_bShift && cell.m_GotoLine == -1)
                // lowest bit 0 means the rest value is already rule index (without encoding in RuleIndexStorage)
                //SimpleCells.push_back(MakePair(MakePair(row, column), GetRuleIndex(cell.m_ReduceRules[0]) << 1));
                SimpleCells.Add(row, column, GetRuleIndex(cell.m_ReduceRules[0]) << 1);
            else {
                tmp.clear();
                for (size_t i = 0; i < cell.m_ReduceRules.size(); ++i)
                    tmp.push_back(GetRuleIndex(cell.m_ReduceRules[i]));
                ui32 rulesIndex = ruleIndexStorageBuilder.AddRange(tmp.begin(), tmp.end());

                // lowest bit 1 means the rest value is already rule index
                //SimpleCells.push_back(MakePair(MakePair(row, column), (ComplexCells.size() << 1) + 1));    // overflow check will be done later
                SimpleCells.Add(row, column, (ComplexCells.size() << 1) + 1);
                ComplexCells.push_back(TCompactSLRCell(cell.m_bShift, cell.m_GotoLine, rulesIndex));
            }
        }
    }
    TBufferStream tmpbuf;
    ruleIndexStorageBuilder.Save(&tmpbuf);
    RuleIndexStorage.Load(&tmpbuf);

    // make sure we are not out of index space:
    CheckIndexOverflow(ComplexCells.size());

    //assert that reverse conversion produces original data
    YASSERT(Verify(table));
}

void InitAmbiguousSlot(yvector< COccurrence >& Occurrences)
{
    /* quite slow implementation. could be done with single iteration through sorted array - i.e. in O(n), not O(n^2) */
    for (size_t i=0; i < Occurrences.size(); i++)
        Occurrences[i].m_bAmbiguous = false;

    for (size_t i=0; i < Occurrences.size(); i++) {
        for (size_t k=i+1; k < Occurrences.size(); k++)
            if (Occurrences[k].first < Occurrences[i].second) {
                Occurrences[k].m_bAmbiguous = true;
                Occurrences[i].m_bAmbiguous = true;
            } else
                break;
    }
}

bool TSurnamePredictor::Predict(const TWtringBuf& w, yvector<TPredictedSurname>& res) const
{
    int MinLemmaSize = 1;
    TGrammarBunch usedFlexGrammars;
    for (int i = Min<int>((int)w.length() - MinLemmaSize, MaxSurnameSuffixLength); i > 0; i--) {
        TWtringBuf Suffix = w.SubStr(w.size() - i);
        TSurnameFlexMap::const_iterator it = SurnameFlex2Paradigmas.find(Suffix);

        //храним те граммемы, которые мы уже приписывали, для того, чтобы когда мы предсказываем
        //по более короткому хвосту, не приписывать граммемы уже приписанного более длинного
        //например, "Балуевского" может предсказаться по АВДУЕВСКИЙ и ТОЛСТОЙ, у АВДУЕВСКИЙ
        //хвост длиннее, и все граммемы хвоста по ТОЛСТОЙ вкладываются в граммемы по АВДУЕВСКИЙ
        //значит вообще не добавляем омонима, предсказанного ТОЛСТОЙ

        yvector<TGramBitSet> grammemsForThisSuffix;
        if (it != SurnameFlex2Paradigmas.end())
        {
            const yvector<TFormInfo>& formInfos = it->second;
            for (int j=0; j < formInfos.ysize(); j++)
            {
                TPredictedSurname predictedSurname;
                for (int k = 0 ; k < formInfos[j].FlexGrammars.ysize() ; k ++)
                {
                    TGramBitSet gramBitSet = formInfos[j].FlexGrammars[k];
                    gramBitSet |= formInfos[j].StemGrammar & AllGenders;
                    if (usedFlexGrammars.find(gramBitSet) == usedFlexGrammars.end())
                        predictedSurname.FlexGrammars.push_back(formInfos[j].FlexGrammars[k]);
                }

                if (predictedSurname.FlexGrammars.size() == 0)
                    continue;
                predictedSurname.StemGrammar = formInfos[j].StemGrammar;
                grammemsForThisSuffix.insert(grammemsForThisSuffix.begin(), predictedSurname.FlexGrammars.begin(),
                                                                            predictedSurname.FlexGrammars.end());

                const TSurnameLemma& L = SurnameLemmasFlex[formInfos[j].SurnameLemmaFlexNo];

                predictedSurname.Lemma = ::ToWtring(w.SubStr(0, w.size() - i)) + L.SurnameFlex;
                predictedSurname.Weight = L.Weight;
                res.push_back(predictedSurname);
            }
        }
        for (int k = 0 ; k < grammemsForThisSuffix.ysize() ; k++)
            usedFlexGrammars.insert(grammemsForThisSuffix[k]);

    }
    return res.size() > 0;
}

void CMultiWordCreator::FindAuxKWWords(yvector<SDictIndex>& indexes, EDicType dicType)
{
    if (dicType == DICTYPE_COUNT)
        return;

    bool bHasTextKW = false;
    yvector<SDictIndex> tomitaKWArticles;
    SDictIndex algArticleIndex;//считатеся, что у одного kw_type не больше одного alg
    for (size_t i = 0; i < indexes.size(); ++i) {
        SDictIndex index = indexes[i];
        YASSERT(dicType == index.m_DicType);    //словарь должен быть для всех одинаковый

        const article_t* pArt = GlobalDictsHolder->GetAuxArticle(index);
        if (m_FoundArticles.find(SArtPointer(pArt->get_title())) != m_FoundArticles.end())
            continue;

        if (pArt->has_text_content()) // значит поле СОСТАВ состоит из обычных слов
            bHasTextKW = true;
        else if (pArt->has_gram_file_name())
            tomitaKWArticles.push_back(index);
        else if (pArt->has_alg())
            algArticleIndex = index;
    }

    if (bHasTextKW || dicType == KW_DICT)
        FindKeyWords(dicType);

    for (size_t i = 0; i < tomitaKWArticles.size(); ++i)
        ProcessTomitaAuxArticle(tomitaKWArticles[i]);

    if (algArticleIndex.IsValid())
        ProcessAlgArticle(TArticleRef(algArticleIndex));
}

//все клаузы, которые непосредственно включаются в главную
void CClauseSubTree::GetIncludedClauses(yvector<CClause*>& clauses)
{
    yvector<CWordsPair*> periods;
    GetIncludedPeriodsBase(periods);
    for (size_t i = 0; i < periods.size(); i++)
        clauses.push_back((CClause*)periods[i]);
}

void CMultiWordCreator::CreateWordIndexes(const yset<SArtPointer>&  artPointers, yvector<SWordHomonymNum>& WordIndexes, bool bAddEndOfStreamSymbol)
{
    for (yset<SArtPointer>::const_iterator it = artPointers.begin(); it != artPointers.end(); ++it)
        FindKWWords(*it, KW_DICT);

    InitWordIndexes(WordIndexes);
    //использую алгоритм SolveAmbiguity и соответственно структуру COccurrence
    //COccurrence.m_GrammarRuleNo - номер multiWord
    yvector<COccurrence> multiWordsOccurrences;
    for (size_t i = 0; i < m_Words.GetMultiWordsCount(); ++i) {
        const CWord& pW = m_Words.GetMultiWord(i);

        yset<SArtPointer>::const_iterator it;
        for (it = artPointers.begin(); it != artPointers.end(); ++it)
            if (pW.HasArticle(*it))
                break;

        if (it == artPointers.end())
            continue;

        COccurrence o(pW.GetSourcePair().FirstWord(), pW.GetSourcePair().LastWord() + 1, i);
        multiWordsOccurrences.push_back(o);
    }

    SolveAmbiguity(multiWordsOccurrences);
    yvector<SWordHomonymNum> multiWords;
    for (size_t i = 0; i < multiWordsOccurrences.size(); i++) {
        SWordHomonymNum tmp(multiWordsOccurrences[i].m_GrammarRuleNo,-1, false);
        SubstituteByMultiWord(tmp, WordIndexes);
    }
    if (bAddEndOfStreamSymbol)
        WordIndexes.push_back(m_Words.GetEndWordWH());
}

void CTopClauses::AddClauseVariants(yvector<CClauseVariant>& ClauseVars)
{
    m_FirstNode->m_outNodes.clear();
    m_FirstNode->m_inNodes.clear();

    m_LastNode->m_outNodes.clear();
    m_LastNode->m_inNodes.clear();

    yvector<CClause*> deleted_clause;
    for (size_t i = 0; i < ClauseVars.size(); i++) {
        const_clause_it it;
        CClauseNode* pLastNode = m_FirstNode;
        for (it = ClauseVars[i].GetFirstClause(LeftToRight); it != ClauseVars[i].GetEndClause(); it = ClauseVars[i].GetNextClause(LeftToRight, it))
            pLastNode = AddInitialClause(*it, pLastNode, deleted_clause);
        bool bAdd = true;
        for (size_t j = 0; j < pLastNode->m_outNodes.size(); j++)
            if (pLastNode->m_outNodes[j].m_pNode == m_LastNode) {
                bAdd = false;
                break;
            }
        if (bAdd) {
            pLastNode->m_outNodes.push_back(SClauseRelation(m_LastNode));
            m_LastNode->m_inNodes.push_back(SClauseRelation(pLastNode));
        }
    }
    for (size_t j = 0; j < deleted_clause.size(); j++)
        delete deleted_clause[j];/**/
}

static void BuildTerminalIndex(const yvector<CGrammarItem> grammarItems, const ITerminalDictionary& terminals,
                               ymap<int, eTerminals>& index) {
    for (size_t i = 0; i < grammarItems.size(); ++i) {
        const CGrammarItem& item = grammarItems[i];
        if (siString == item.m_Type || siAnyWord == item.m_Type || siFileList == item.m_Type)
            index[i] = terminals.FindTerminal(item.m_ItemStrId);
    }
}

Stroka CSentence::ToHTMLColorString(const yvector<CWordsPair>& wp, const Stroka& sColor, ECharset encoding) const
{
    Stroka str;
    for (size_t i = 0; i + 1 <= m_words.size(); ++i) {
        CWord* pW = m_words[i].Get();
        for (size_t j = 0; j < wp.size(); ++j)
            if (wp[j].FirstWord() == (int)i)
                str += Substitute("<font color=\"$0\">", sColor);
        if (i > 0 && (!pW->IsPunct() || pW->IsOpenBracket() || pW->IsCloseBracket()))
            str += " ";
        str += NStr::Encode(pW->GetOriginalText(), encoding);
        for (size_t j = 0; j < wp.size(); ++j)
            if (wp[j].LastWord() == (int)i)
                str += "</font>";
    }
    return StripString(str);
}

void CTrieHolder::GetOccurrences (const TerminalString& Text, yvector< COccurrence >& Occurrences) const
{
    int r = 0;
    Occurrences.clear();
    for (size_t i=0; i<Text.size(); i++) {
        r = NextState(r, i, Text[i], Occurrences);
    };
};