QueryNode.h

Go to the documentation of this file.

//-*- Mode: C++ -*-
//  DDC originally by Alexey Sokirko
//  Changes and modifications 2011-2020 by Bryan Jurish
//
//  This file is part of DDC.
// 
//  DDC is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
// 
//  DDC is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU Lesser General Public License for more details.
// 
//  You should have received a copy of the GNU Lesser General Public License
//  along with DDC.  If not, see <http://www.gnu.org/licenses/>.
//
// QNode.h: interface for the CQNode class.
//

#ifndef QUERY_NODE_H
#define QUERY_NODE_H

#include "ConcHolder.h"

extern const size_t MaxDistanceForNear;

//----------------------------------------------------------------------
class CQueryNode  
{
public:
    bool m_bAtomic;  

    bool m_bNegated;

    string m_Source;

    vector<CTokenNo> m_Occurrences;

    bool m_bUseNodeIndices;

    vector<BYTE> m_OccurrenceNodeIndices;

    bool m_bUseMatchIds;

    vector<BYTE> m_OccurrenceMatchIds;

    vector<CHit> m_Hits;

    const CConcHolder* m_pHolder;

    vector<DWORD> m_ChunkLengths;

    vector<DWORD> m_ChunkOffsets;

    vector<int> m_CacheIds;


    CQueryNode(bool bUseNodeIndices=false, bool bUseMatchIds=false, const CConcHolder *holder=NULL)
        : m_bAtomic(false),
          m_bNegated(false),
          m_bUseNodeIndices(bUseNodeIndices),
          m_bUseMatchIds(bUseMatchIds),
          m_pHolder(holder)
    {};

    virtual ~CQueryNode();

    virtual void Evaluate(bool bSeparateHits=false);

    virtual void EvaluateWithoutHits();

    void SetNegation(bool Value);

    bool GetNegation() const;

    inline void AddOccurrence(const CQueryNode& FromNode, int FromOcc)
    {
        m_Occurrences.push_back(FromNode.m_Occurrences[FromOcc]);
        if (m_bUseNodeIndices)
            m_OccurrenceNodeIndices.push_back(FromNode.m_OccurrenceNodeIndices[FromOcc]);
        if (m_bUseMatchIds)
            m_OccurrenceMatchIds.push_back(FromNode.m_OccurrenceMatchIds[FromOcc]);
    };

    void AddOccurrences(const CQueryNode& FromNode, int start, int end);

    void AddOccurrences2(const CQueryNode& FromNode1, int start1, int end1,
                         const CQueryNode& FromNode2, int start2, int end2);

    void AddOccurrences3(const CQueryNode& FromNode1, int start1, int end1,
                         const CQueryNode& FromNode2, int start2, int end2,
                         const CQueryNode& FromNode3, int start3, int end3);

    void ClearAndReserveOccurrences(int size);

    void SwapOccurrences(CQueryNode& Node, bool swapChunkLengths=false);

    void ConvertOccurrencesToHits (bool bSeparateHits);

    void ConvertOccurrencesToHitsForPatterns (bool bSeparateHits);

    void EnsureChunkOffsets();

    void SetHolder(const CConcHolder* pHolder);

    virtual bool IsUniversalWildcard() const;
        
    virtual size_t GetNodeFrequencyByNodeIndex(size_t NodeIndex) const;

    inline DWORD HitOccurrencesBegin(DWORD HitNo) const
    { return (HitNo == 0) ? 0 : m_Hits[HitNo-1].m_HighlightOccurrenceEnd; };

    inline DWORD HitOccurrencesEnd(DWORD HitNo) const
    { return m_Hits[HitNo].m_HighlightOccurrenceEnd >= m_Occurrences.size() ? m_Occurrences.size() : m_Hits[HitNo].m_HighlightOccurrenceEnd; };

    DWORD GetFirstOccurrenceInHit(DWORD HitNo, BYTE MatchId) const;

    DWORD GetLastOccurrenceInHit(DWORD HitNo, BYTE MatchId) const;

    DWORD GetMiddleOccurrenceInHit(DWORD HitNo, BYTE MatchId) const;

    inline DWORD BreakStride() const
    { return m_Hits.empty() ? 1 : max((size_t)1, (m_Hits.back().m_BreakNo-m_Hits.front().m_BreakNo)/m_Hits.size()); };
};

//----------------------------------------------------------------------
class CQueryBinaryOperationNode : public CQueryNode 
{
    void hits_add(const CQueryNode& NodeFrom, vector<CHit>::const_iterator First);

public:
    CQueryNode*     m_pChild1;  

    CQueryNode*     m_pChild2;  

public:
    CQueryBinaryOperationNode() : m_pChild1(NULL), m_pChild2(NULL)
    {};

    CQueryBinaryOperationNode(CQueryNode *dtr1, CQueryNode *dtr2)
        : CQueryNode(false), m_pChild1(dtr1), m_pChild2(dtr2)
    {};

    void Create(const CConcHolder*  pHolder, CQueryNode* child1, CQueryNode* child2, string Operation);

    virtual ~CQueryBinaryOperationNode();

    inline void pushHit(DWORD BreakNo)
    {
        CHit H(BreakNo);
        H.m_HighlightOccurrenceEnd = m_Occurrences.size();
        m_Hits.push_back(H);
    };

    void hits_and_positions_assign(const CQueryNode &NodeFrom);

    void hits_and_positions_swap(CQueryNode &NodeFrom);
        
    void hits_and_positions_union(bool bSeparateHits=false);

    void hits_and_positions_intersection(bool bSeparateHits=false);

    void hits_and_positions_difference(bool bSeparateHits=false);

    size_t GetNodeFrequencyByNodeIndex(size_t NodeIndex) const;
};

//----------------------------------------------------------------------
class CQueryAndOperation        : public CQueryBinaryOperationNode  
{
public:
    CQueryAndOperation();
    virtual ~CQueryAndOperation() {};
    void Evaluate(bool bSeparateHits=false);
};

//----------------------------------------------------------------------
class CQueryOrOperation : public CQueryBinaryOperationNode 
{
public:
    CQueryOrOperation();
    virtual ~CQueryOrOperation() {};
    void Evaluate(bool bSeparateHits=false);
};

//----------------------------------------------------------------------
class CQueryTokenNode : public CQueryNode
{
public:
    vector<DWORD> m_IndexItems;

    string m_IndexName;

    bool m_bChunk;

    bool m_bAnchor;

    bool m_bAny;

    int m_AnchorOffset;

public:
    BYTE m_NodeIndex;

    BYTE m_MatchId;
        
    CQueryTokenNode(int NodeIndex, BYTE MatchId=0);
    virtual ~CQueryTokenNode();

    void SetMatchId(BYTE MatchId);

    virtual bool IsUniversalWildcard() const;

    CStringIndexSet* GetIndex(const CConcHolder* pHolder, const string &IndexName);

    void MakeUnique(void);

    bool CreateStringPattern(const CConcHolder* pHolder, const string& IndexName, const string& Value);

    bool CreateRegexPattern(const CConcHolder* pHolder, const string& IndexName, const string& Regex, bool negated=false);

    bool CreateSetPattern(const CConcHolder* pHolder, const string& IndexName, const set<string>& Values);

    bool CreatePrefixSetPattern(const CConcHolder* pHolder, const string& IndexName, const set<string>& Prefixes);

    bool CreatePrefixPattern(const CConcHolder* pHolder, const string& IndexName, const string& Prefix);

    bool CreateSuffixSetPattern(const CConcHolder* pHolder, const string& IndexName, const set<string>& Suffixes);

    bool CreateSuffixPattern(const CConcHolder* pHolder, const string& IndexName, const string& Suffix);

    bool CreateInfixSetPattern(const CConcHolder* pHolder, const string& IndexName, const set<string>& Infixes);

    bool CreateInfixPattern(const CConcHolder* pHolder, const string& IndexName, const string& Infix);

    bool CreateUniversalPattern(const CConcHolder *pHolder, const string& SourceStr="*");

    bool CreateNullPattern(const CConcHolder *pHolder, const string& IndexName="Token");

    bool CreateLemmaPattern(const CConcHolder* pHolder, const string& Value);

    bool CreateThesPattern(const CConcHolder* pHolder, const string& IndexName, const string& src);

    bool CreateMorphAnnotationPattern(const CConcHolder* pHolder, const string& IndexName, const vector<string> &Items);

    bool CreateFileList(const CConcHolder* pHolder, const string &IndexName, const string& FileName);

    bool CreateChunkPattern(const CConcHolder* pHolder, const string& IndexName, const string& ChunkTypeStr);

    bool CreateAnchorPattern(const CConcHolder *pHolder, const string& BreakName, int anchor);

    bool BuildRegExp(string RegExpStr, vector<DWORD>& IndexItems, bool negated=false);

    void    EvaluateWithoutHits();
    void    Evaluate(bool bSeparateHits=false);
    size_t  GetNodeFrequencyByNodeIndex(size_t NodeIndex) const;

};


//----------------------------------------------------------------------
class CQuerySequenceNode : public CQueryNode
{
public:
    vector<BYTE>                    m_DistanceOps;  
    vector<BYTE>                    m_Distances;    
    vector<CQueryTokenNode*>        m_Items;

    bool AddDistance(const string& s, char op='<');
        
public:
        
    CQuerySequenceNode();
    virtual ~CQuerySequenceNode();

    bool    Create(const CConcHolder* pHolder, const vector<const CQueryNode*>& SequenceObj, const vector<string>& DistanceStrings);

    bool    Create(const CConcHolder* pHolder, const vector<CQueryTokenNode*>& Items, const vector<BYTE>& Distances, const vector<BYTE>& DistanceOps);

    void    EvaluateWithoutHits();
    void    Evaluate(bool bSeparateHits=false);
    size_t  GetNodeFrequencyByNodeIndex(size_t NodeIndex) const;
};

//----------------------------------------------------------------------
class CQueryNearNode : public CQueryNode 
{
public:
    CQueryNode*             m_pChild1;  

    CQueryNode*             m_pChild2;  

    CQueryNode*             m_pChild3;   

    BYTE                    m_Distance;

public:
    CQueryNearNode();
    virtual ~CQueryNearNode();

    bool Create(const CConcHolder* pHolder, BYTE distance, CQueryNode* child1, CQueryNode* child2, CQueryNode* child3 = NULL);

    void FindOccurrences2();
    void FindOccurrences3();
    void Evaluate(bool bSeparateHits=false);
    size_t GetNodeFrequencyByNodeIndex(size_t NodeIndex) const;
};

//----------------------------------------------------------------------
class CQueryWithNode : public CQueryBinaryOperationNode
{
public:
    BYTE m_MatchId;

public:
    CQueryWithNode();
    virtual ~CQueryWithNode() {};

    bool Create(const CConcHolder*  pHolder, CQueryNode* child1, CQueryNode* child2, BYTE matchId=0);

    void EvaluateWithoutHits();
    void Evaluate(bool bSeparateHits=false);
};

//----------------------------------------------------------------------
class CQueryWithoutNode : public CQueryWithNode
{
public:
    CQueryWithoutNode()
    {};
    virtual ~CQueryWithoutNode() {};

    bool Create(const CConcHolder*  pHolder, CQueryNode* child1, CQueryNode* child2, BYTE matchId=0);

    void EvaluateWithoutHits();
};

//----------------------------------------------------------------------
class CQueryWithorNode : public CQueryWithNode
{
public:
    CQueryWithorNode()
    {};
    virtual ~CQueryWithorNode() {};

    bool Create(const CConcHolder*  pHolder, CQueryNode* child1, CQueryNode* child2, BYTE matchId=0);

    void EvaluateWithoutHits();
};

//----------------------------------------------------------------------


struct CQOccurrenceIterator {
    CQueryNode *node; 
    int cnt;          
    int cur;          
    DWORD chpos;      

    CQOccurrenceIterator(CQueryNode *node_=NULL)
    { assign(node_); };

    CQOccurrenceIterator(const CQOccurrenceIterator &b)
    { operator=(b); };

    virtual ~CQOccurrenceIterator() {};

    void bind(CQueryTokenNode *node_, const CQOccurrenceIterator &src, int minOffset, int maxOffset);

    inline CQOccurrenceIterator& operator=(const CQOccurrenceIterator &b)
    {
        node = b.node;
        cnt = b.cnt;
        cur = b.cur;
        chpos = b.chpos;
        return *this;
    };

    inline void assign(CQueryNode *node_)
    {
        node  = node_;
        cnt   = 0;
        cur   = 0;
        chpos = 0;
        if (node) cnt = node->m_Occurrences.size();
    };

    /* node-assignment operator; wraps assign() */
    inline CQOccurrenceIterator& operator=(CQueryNode *node_)
    {
        assign(node_);
        return *this;
    };

    inline bool valid() const
    { return cur < cnt; };

    inline void invalidate()
    { cur = cnt; };

    inline operator bool() const
    { return valid(); };

    inline size_t chunksize() const
    {  return node->m_ChunkLengths[chpos]; };

    /* get token-id for occurrence-id \a occ */
    inline CTokenNo tocc(DWORD occ) const
    { return node->m_Occurrences[occ]; };
        
    /* get first token-id of current occurrence; assumes iterator is valid */
    inline CTokenNo tmin() const
    { return node->m_Occurrences[cur]; };

    /* get last token-id of current occurrence (inclusive); assumes iterator is valid */
    inline CTokenNo tmax() const
    { return node->m_Occurrences[cur + node->m_ChunkLengths[chpos] - 1]; };

    /* get last token-id of previous occurrence; assumes iterator is valid and cur>0 */
    inline CTokenNo tmax_prev() const
    { return node->m_Occurrences[cur-1]; };

    /* increment operator updates the iterator to point to the next available occurrence, or to an invalid state if no such occurrence exists */
    inline void operator++()
    { 
        if (!valid()) return;
        cur += node->m_ChunkLengths[chpos];
        chpos++;
    };

    /* seek iterator to the first occurrence greater-than-or-equal-to Tok */
    inline void seek(const CTokenNo Tok)
    {
        while (valid() && tmin() < Tok) operator++();
    };

    /* equality operator tests whether calling object and argument \a b point to exactly the same tokens */
    bool operator==(const CQOccurrenceIterator &b) const;
};

#define DDC_OCCITER_LB_COEF 4

struct CQTokenOccurrenceIterator : public CQOccurrenceIterator
{
    DWORD stride; 
        
    CQTokenOccurrenceIterator(CQueryNode *node_=NULL)
    { assign(node_); };

    CQTokenOccurrenceIterator(const CQTokenOccurrenceIterator &b)
    { operator=(b); };

    virtual ~CQTokenOccurrenceIterator() {};
    
    void bind(CQueryTokenNode *node_, const CQTokenOccurrenceIterator &src, int minOffset, int maxOffset);

    inline CQTokenOccurrenceIterator& operator=(const CQTokenOccurrenceIterator &b)
    {
        CQOccurrenceIterator::operator=(b);
        stride = b.stride;
        return *this;
    };


    inline void assign(CQueryNode *node_)
    {
        CQOccurrenceIterator::assign(node_);
        stride = node && cnt ? max((CTokenNo)1, (node->m_Occurrences.back()-node->m_Occurrences.front())/cnt) : 1;
    };

    /* node-assignment operator; wraps assign() */
    inline CQTokenOccurrenceIterator& operator=(CQueryTokenNode *node_)
    {
        assign((CQueryNode*)node_);
        return *this;
    };

    //-- inherited
    //inline bool valid() const
    //inline operator bool() const
        
    inline size_t chunksize() const
    { return 1; };

    //-- inherited
    //inline CTokenNo tocc(DWORD occ) const

    //-- inherited
    inline CTokenNo tmin() const
    { return node->m_Occurrences[cur]; };

    /* get last token-id of current occurrence (inclusive); assumes iterator is valid: override just returns tmin() */
    inline CTokenNo tmax() const
    { return tmin(); };

    //-- inherited
    //inline CTokenNo tmax_prev() const

    /* increment operator updates the iterator to point to the next available occurrence, or to an invalid state if no such occurrence exists */
    inline void operator++()
    { 
        if (!valid()) return;
        ++cur;
    };

    /* seek iterator to the first occurrence greater-than-or-equal-to Tok */
    inline void seek(const CTokenNo Tok)
    {
        if (valid() && tmin() < Tok) {
            if ((Tok-tmin())/stride > DDC_OCCITER_LB_COEF*log2u32(cnt-cur)) {
                cur = lower_bound(node->m_Occurrences.begin()+cur, node->m_Occurrences.end(), Tok) - node->m_Occurrences.begin();
            } else {
                do { ++cur; } while (valid() && tmin() < Tok);
            }
        }
    };

    /* equality operator tests whether calling object and argument \a b point to exactly the same tokens : override */
    inline bool operator==(const CQTokenOccurrenceIterator &b) const
    {
        return node->m_Occurrences[cur] == b.node->m_Occurrences[b.cur];
    };
};

//----------------------------------------------------------------------
extern void GetWordForms (const MorphLanguageEnum Langua, const string& src, set<string>& WordForms);

#endif /* QUERY_NODE_H */

/*--- emacs style variables ---
 * Local Variables:
 *  mode: C++
 *  c-file-style: "ellemtel"
 *  c-basic-offset: 4
 *  tab-width: 8
 *  indent-tabs-mode: nil
 * End:
 */