//////////////////////////////////////////////////////////////////////
//
// MMemory.cpp: Implementation of the Morphic Memory classes
//
//////////////////////////////////////////////////////////////////////
/* 
This is FREE software  

Permission is hereby granted, free of charge,  to any person obtaining  a copy 
of this software and associated documentation files (the "Software"),  to deal 
in the Software without restriction, including without limitation  the  rights 
to use,  copy,  modify,  merge,  publish,  distribute, sublicense, and/or sell 
copies  of  the  Software,   and  to  permit  persons  to  whom  the  Software 
is furnished to do so, subject to the following conditions: 

There are no conditions imposed on the use of this software. 

THE SOFTWARE IS PROVIDED "AS IS",  WITHOUT  WARRANTY  OF ANY KIND,  EXPRESS OR 
IMPLIED,  INCLUDING  BUT  NOT  LIMITED  TO  THE  WARRANTIES OF MERCHANTABILITY, 
FITNESS  FOR  A  PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
AUTHORS  OR  COPYRIGHT  HOLDERS  BE  LIABLE  FOR  ANY CLAIM,  DAMAGES OR OTHER 
LIABILITY,  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,  ARISING FROM, 
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN  THE 
SOFTWARE. 
*/


#define _CREATE_MEMORY_ROOT_
#include "MMemory.h"
#include "MState.h"
#include "MLanguage.h"
#include "MRadastro.h"
#ifdef SUNSPEC
#include  "MConnection.h"
#include  "MView.h"
#endif



//////////////////////////////////////////////////////////////////////
// MException Class
//////////////////////////////////////////////////////////////////////
MException::MException()
{
    pData  = NULL;
    putError("General exception encountered");
}

MException::MException(void* _pData)
{
    pData = _pData;
    putError("Exception with data encountered");
}

MException::MException(char* _pError)
{
    pData = NULL;
    putError(_pError);
}

MException::MException(void* _pData,char* _pError)
{
    pData = _pData;
    putError(_pError);
}

MException::MException( const MException &E)
{
    pData = E.pData;
    putError(E.pError);
}

MException::~MException()
{
    delete pError;
}

void MException::putError(char* _pError)
{
    pError = new char[strlen(_pError)+1];
    strcpy(pError,_pError);
}

char* MException::showError()
{
    return pError;
}

void* MException::getData()
{
    return pData;
}



//////////////////////////////////////////////////////////////////////
// MNode Class
//////////////////////////////////////////////////////////////////////
MNode::MNode(MNode* const pNode)
{
    pChain = NULL;
    pBack  = NULL;
    pLess  = NULL;
    pMore  = NULL;
    pPrev  = NULL;
    pNext  = NULL;
    uData  = NULL;

    //Link new node into existing chain of nodes
    pChain = pNode->pChain;
    pNode->pChain = this;
}

MNode::MNode()
{
    pChain = NULL;
    pBack  = NULL;
    pLess  = NULL;
    pMore  = NULL;
    pPrev  = NULL;
    pNext  = NULL;
    uData  = NULL;
}

MNode::~MNode(){}

//Methods used when working on binary trees
void MNode::setWeight(unsigned uWeight){uData = uWeight;}
unsigned MNode::getWeight(){return uData;}
unsigned MNode::getCentre(){return 0x80000000;}
//Have a node become alive at start time (if applicable)
void MNode::go(){return;}
//Report if a member variable is used as a pointer (and has to be adjusted on memory restore)
bool MNode::isBackPtr(){return true;}
bool MNode::isLessPtr(){return true;}
bool MNode::isMorePtr(){return true;}
bool MNode::isPrevPtr(){return true;}
bool MNode::isNextPtr(){return true;}
bool MNode::isDataPtr(){return false;}
//Direct write functions of most member variables
MNode*  MNode::setChain(MNode* pNode){return pChain = pNode;}
MNode*  MNode::setBack (MNode* pNode){return pBack  = pNode;}
MNode*  MNode::setLess (MNode* pNode){return pLess  = pNode;}
MNode*  MNode::setMore (MNode* pNode){return pMore  = pNode;}
MNode*  MNode::setPrev (MNode* pNode){return pPrev  = pNode;}
MNode*  MNode::setNext (MNode* pNode){return pNext  = pNode;}
unsigned MNode::setData(unsigned _uData){return uData = _uData;}
//Direct read functions of all member variables
MNode*  MNode::getChain(){return pChain;}
MNode*  MNode::getBack(){return pBack;}
MNode*  MNode::getLess(){return pLess;}
MNode*  MNode::getMore(){return pMore;}
MNode*  MNode::getPrev(){return pPrev;}
MNode*  MNode::getNext(){return pNext;}
unsigned MNode::getData(){return uData;}
//Direct access to adresses of most member variables
MNode**  MNode::getAddrChain(){return &pChain;}
MNode**  MNode::getAddrBack (){return &pBack;}
MNode**  MNode::getAddrLess (){return &pLess;}
MNode**  MNode::getAddrMore (){return &pMore;}
MNode**  MNode::getAddrPrev (){return &pPrev;}
MNode**  MNode::getAddrNext (){return &pNext;}
unsigned* MNode::getAddrData(){return &uData;}
//Report special features and runtime type 
bool MNode::isRoot(){return false;}
bool MNode::isQuantity(){return false;}
MNodeType MNode::getNodeType(){return M_NODE;}

//Generate URI
void MNode::generateURI(MString& mURI,const MString&,unsigned* puIndex)
{
    mURI.setAt(-1+(*puIndex)--,(char)(getData()&0xFF));
}


//Generate multiple nodes in an array and return them one by one
//in order to reduce the overhead for memory allocation
MNode* MNode::createNode(enum MNodeType mNodeType)
{
    MNode* pNode;

    //Static node array
    static struct{
        int    nAvailableNodes;
        MNode* aNodes;
    }Repository[MaxMNodeType] = {{0,NULL}};

    //Check if an appropriate node is available in the repository
    if(Repository[mNodeType].nAvailableNodes == 0){
        //Generate an array of nodes accordingly to the requested node type
        switch(mNodeType){
        //MMemory
        case M_NODE:            Repository[mNodeType].aNodes = new MNode            [NODE_ARRAY_SIZE](); break;
        case M_ROOT:            Repository[mNodeType].aNodes = new MRoot            [NODE_ARRAY_SIZE](); break;
        case M_TAIL:            Repository[mNodeType].aNodes = new MTail            [NODE_ARRAY_SIZE](); break;
        case M_ROOT_MEMORY:     Repository[mNodeType].aNodes = new MRootMemory      [NODE_ARRAY_SIZE](); break;
        case M_TAIL_MEMORY:     Repository[mNodeType].aNodes = new MTailMemory      [NODE_ARRAY_SIZE](); break;
        case M_VAL:             Repository[mNodeType].aNodes = new MVal             [NODE_ARRAY_SIZE](); break;
        case M_REF:             Repository[mNodeType].aNodes = new MRef             [NODE_ARRAY_SIZE](); break;
        case M_ITEM:            Repository[mNodeType].aNodes = new MItem            [NODE_ARRAY_SIZE](); break;
        //MLanguage
        case M_DICTIONARY:      Repository[mNodeType].aNodes = new MDictionary      [NODE_ARRAY_SIZE](); break;
        //MState
        case M_SYSTIME:         Repository[mNodeType].aNodes = new MSysTime         [NODE_ARRAY_SIZE](); break;
        case M_SESSION:         Repository[mNodeType].aNodes = new MSession         [NODE_ARRAY_SIZE](); break;
        case M_CONCEPT:         Repository[mNodeType].aNodes = new MConcept         [NODE_ARRAY_SIZE](); break;
        case M_SPECIAL:         Repository[mNodeType].aNodes = new MSpecial         [NODE_ARRAY_SIZE](); break;
        case M_STATE:           Repository[mNodeType].aNodes = new MState           [NODE_ARRAY_SIZE](); break;
        case M_LINK:            Repository[mNodeType].aNodes = new MLink            [NODE_ARRAY_SIZE](); break;
        //MDisk
//      case M_DISK:            Repository[mNodeType].aNodes = new MDisk            [NODE_ARRAY_SIZE](); break;
        case M_BLOB:            Repository[mNodeType].aNodes = new MBlob            [NODE_ARRAY_SIZE](); break;
        case M_LOOP:            Repository[mNodeType].aNodes = new MLoop            [NODE_ARRAY_SIZE](); break;
#ifdef SUNSPEC
        //MConnection
        case M_CONNECTION:      Repository[mNodeType].aNodes = new MConnection      [NODE_ARRAY_SIZE](); break;
        case M_SERIAL:          Repository[mNodeType].aNodes = new MSerial          [NODE_ARRAY_SIZE](); break;
        //MDisplay
        case M_POS:             Repository[mNodeType].aNodes = new MPos             [NODE_ARRAY_SIZE](); break;
        case M_VIEW:            Repository[mNodeType].aNodes = new MView            [NODE_ARRAY_SIZE](); break;
        case M_SCREEN:          Repository[mNodeType].aNodes = new MScreen          [NODE_ARRAY_SIZE](); break;
        case M_COLOR:           Repository[mNodeType].aNodes = new MColor           [NODE_ARRAY_SIZE](); break;
#endif
        //MRadastro
        case M_QUANTITY:        Repository[mNodeType].aNodes = new MQuantity        [NODE_ARRAY_SIZE](); break;
        case M_FIELD:           Repository[mNodeType].aNodes = new MField           [NODE_ARRAY_SIZE](); break;
        case M_FLUX:            Repository[mNodeType].aNodes = new MFlux            [NODE_ARRAY_SIZE](); break;
        case M_TIME:            Repository[mNodeType].aNodes = new MTime            [NODE_ARRAY_SIZE](); break;
        case M_FREQUENCY:       Repository[mNodeType].aNodes = new MFrequency       [NODE_ARRAY_SIZE](); break;
        case M_OBSERVER:        Repository[mNodeType].aNodes = new MObserver        [NODE_ARRAY_SIZE](); break;
        case M_RIGHTASCENSION:  Repository[mNodeType].aNodes = new MRightAscension  [NODE_ARRAY_SIZE](); break;
        case M_DECLINATION:     Repository[mNodeType].aNodes = new MDeclination     [NODE_ARRAY_SIZE](); break;
        //Not implemented yet
        default:      return NULL;
        }
        Repository[mNodeType].nAvailableNodes = NODE_ARRAY_SIZE;
    }
    pNode = Repository[mNodeType].aNodes + --(Repository[mNodeType].nAvailableNodes);
    //Link new node into existing chain of nodes
    pNode->pChain = this->pChain;
    this->pChain = pNode;
    //Increment MMemory's node count
    pRootMemory->uData++;
    return pNode;
}


bool MNode::expandBTree(MNode** ppNewNode,unsigned uWeight, enum MNodeType mNodeType, MNode** ppPred)
{
    unsigned uCentre = getCentre();
    unsigned uLevel  = uCentre >> 1;
    MNode* pNode = *ppPred;
    MNode* pRoot = this;
    MNode* pFree = NULL;

//////////////////////////////////////////////////////////////////////
// Macros used for expanding a BTree
//////////////////////////////////////////////////////////////////////
#define CREATE_NODE  \
    /* Create a new node */\
    if(NULL == pFree){ \
        if(M_VAL == mNodeType){ \
            /*Adjust current root node */ \
            while(NULL != pRoot && false == pRoot->isRoot()){ \
                pRoot = pRoot->pPrev; \
            } \
            pRoot = pRoot->pBack->pNext; \
        } \
        pFree = pRoot->createNode(mNodeType); \
        *ppNewNode = pFree; \
        (*ppNewNode)->uData = uWeight; \
        (*ppNewNode)->pPrev = this; \
    }

#define REPLACE_NODE \
    /* Replace existing node */\
    CREATE_NODE \
    *ppPred = pFree; \
    if(NULL != (pFree->pLess = pNode->pLess)){ \
        pFree->pLess->pBack = pFree;} \
    if(NULL != (pFree->pMore = pNode->pMore)){ \
        pFree->pMore->pBack = pFree;} \
    pFree->pBack = pNode->pBack; \
    pFree = pNode; \
    pFree->pBack = NULL; \
    pFree->pLess = NULL; \
    pFree->pMore = NULL; \
    uWeight = pFree->getWeight(); \
    pNode = *ppPred;

#define FOLLOW_MORE \
    /* Follow the More pointer */\
    ppPred = pNode->getAddrMore(); \
    if(NULL == *ppPred){ \
        CREATE_NODE \
        *ppPred = pFree; \
        pFree->pBack = pNode; \
        break; \
    }else{ \
        pNode = *ppPred; \
        uCentre += uLevel; \
    }

#define FOLLOW_LESS \
    /* Follow the Less pointer */\
    ppPred = pNode->getAddrLess(); \
    if(NULL == *ppPred){ \
        CREATE_NODE \
        *ppPred = pFree; \
        pFree->pBack = pNode; \
        break; \
    }else{ \
        pNode = *ppPred; \
        uCentre -= uLevel; \
    }
//////////////////////////////////////////////////////////////////////

    //Reset return value
    *ppNewNode = NULL;

    //Determine if first element has to be created
    if(NULL == pNode){
        CREATE_NODE
        *ppPred = pFree;
        *ppNewNode = pFree;
        return true;
    }

    //Generate BTree with pre-defined depth  
    for(;;){
        if(uWeight == pNode->getWeight()){
            *ppNewNode = pNode;
            return false;    //Existing node has been found
        }else if(uWeight < pNode->getWeight()){
            if(uCentre <= uWeight){
                REPLACE_NODE
                FOLLOW_MORE
            }else if(uCentre >= pNode->getWeight()){
                FOLLOW_LESS
            }else{ // uWeight < uCentre < pNode->getWeight()
                if(uCentre - uWeight < pNode->getWeight() - uCentre){
                    REPLACE_NODE
                    FOLLOW_MORE
                }else{
                    FOLLOW_LESS
                }
            }
        }else{  //uWeight > pNode->getWeight()
            if(uCentre >= uWeight){
                REPLACE_NODE
                FOLLOW_LESS
            }else if(uCentre <= pNode->getWeight()){
                FOLLOW_MORE
            }else{ //uWeight > uCentre > pNode->getWeight()
                if(uWeight - uCentre < uCentre - pNode->getWeight()){
                    REPLACE_NODE
                    FOLLOW_LESS
                }else{
                    FOLLOW_MORE
                }
            }
        }
        uLevel >>= 1;
    }
    return true;
}


unsigned MNode::getHashValue(MNode* pNode)
{
    int64 n64Hash  = 0;
    static int64 a64Prime[32] = {0};

    int64   n64Bit32 =
#ifdef WIN32
    0x0000000100000000;
#else
    0x0000000100000000LL;
#endif

    if(a64Prime[31] == 0){
        a64Prime[0] = 0xf3f77d6c;
        for(int i=1;i<32;i++){
            a64Prime[i] = 2*a64Prime[i-1];
        }
    }
    for(;;){
        if(true == pNode->isRoot()){
            break;
        }
        if(n64Hash < 0){
            n64Hash = -n64Hash;
        }
        if(n64Hash > n64Bit32/2){
            n64Hash = n64Hash/2;
        }
        n64Hash = (n64Hash * n64Bit32 + pNode->uData);
        for(int i=0;i<32;i++){
            if(n64Hash > a64Prime[31-i]){
                n64Hash = n64Hash - a64Prime[31-i];
            }
        }
        pNode = pNode->pPrev;
    }
    return (unsigned) n64Hash;
}



//////////////////////////////////////////////////////////////////////
// MRoot Class
//////////////////////////////////////////////////////////////////////
MRoot::MRoot(){}
MRoot::~MRoot(){}

//Obtain tail
MNode* MRoot::getTail(){return pBack;};
//Remove weight and return original value
unsigned MRoot::getData(){return uData;};
//Add a weight to uData's upper part used later for sorting purposes
unsigned MRoot::addSortWeight(unsigned uVal){return uVal;};
//Report special features and runtime type 
bool MRoot::isRoot(){return true;};
MNodeType MRoot::getNodeType(){return M_ROOT;};

MRef* MRoot::getRef(const MString& mString)
{
    MItem* pStringItem = pRootMemory->getStringItem(mString);
    return pStringItem->addRef(this);
}

MRoot* MRoot::getRoot(const MString& mString)
{
    MRef* pRef   = pRootMemory->getRef(mString);
    MItem* pItem = getItem(pRef);

    return pItem->getRoot();
}

MNode* MRoot::createRoot(MNodeType _mNodeType)
{
    switch(_mNodeType){
    case M_ROOT:        return new MRoot();
    case M_ROOT_MEMORY: return new MRootMemory();
    default:            return NULL;
    }
}

MItem* MRoot::getItem(MVal* pVal)
{
    MItem* pItem;
    unsigned uHash;

    //Check if a item has been inserted already before
    if(NULL != pVal->pChain && M_ITEM == pVal->pChain->getNodeType()){
        //Take existing item
        pItem = (MItem*)pVal->pChain;
    }else{
        //Calculate item's hash value
        uHash = getHashValue(pVal);
        //Generate new item
        while(false == pVal->expandBTree((MNode**)&pItem,uHash,M_ITEM,pRootMemory->getAddrMore())){
            uHash++; //Take increment in case an uHash is already in use
        }
        if(NULL != pItem){
            pItem->pPrev = pVal;
            //Increment dictionary count and total item count
            getTail()->uData++;
            pRootMemory->getTail()->pMore = (MNode*)(1+(unsigned)(pRootMemory->getTail()->pMore));
        }
    }
    return pItem;
}

MItem* MRoot::getItem(const MString& mString)
{
    return getItem(getRef(mString));
}

MVal* MRoot::getFirstItem()
{
    return getFirstItem(this);
}

MVal* MRoot::getFirstItem(MNode* pNode)
{
    //Search for first item in the binary tree
    for(;;){
        //Check if this is the last value in the string
        if(NULL == pNode->pNext){
            //Check if an item is generally available
            if(true == pNode->isRoot()){
                return NULL;
            }
            return (MVal*)pNode; //YES: Return item's last MVal
        }else{
            //Step to next MVal in the string
            pNode = pNode->pNext;
        }
        //Go to least value in binary tree
        while(NULL != pNode->pLess){
            pNode = pNode->pLess;
        }
        //Check if an item tag is present
        if(M_ITEM==pNode->pChain->getNodeType()){
            return (MVal*)pNode; //YES: Return item's last MVal
        }
    }
}


MVal* MRoot::getNextItem(MNode* pNode)
{
    MVal* pOldVal;

    //Check if current item can be extended
    if(NULL != pNode->pNext){
        //Find first item from extension
        return getFirstItem(pNode);
    }
    for(;;){
        //Step backwards to last junction
        while(false == pNode->isRoot() &&
              pNode->pPrev->pNext==pNode &&
            NULL==pNode->pLess &&
              NULL==pNode->pMore ){
            pNode = pNode->pPrev;
        }
        //Adjust successor MVal object
        pOldVal = (MVal*)pNode;
        if(NULL != pNode->pMore){
            //Approach old value from higher values until the successor has been found
            pNode = pNode->pMore;
            while(NULL != pNode->pLess){
                pNode = pNode->pLess;
            }
            //Check if an item tag is present
            if(M_ITEM == pNode->pChain->getNodeType()){
                return (MVal*)pNode; //YES: Return item's last MVal
            }
        }else{
            //Skip all values less than old value
            while(NULL != pNode->pBack && pNode == pNode->pBack->pMore){
                pNode = pNode->pBack;
            }
            if(NULL == pNode->pBack){
                //Check if the root has been reached
                if(false == (pNode = pNode->pPrev)->isRoot()){
                    continue;
                }else{
                    return NULL;  //Ready, no more items left in current dictionary
                }
            }else{
                pNode = pNode->pBack; //Successor found
                //Check if an item tag is present
                if(M_ITEM == pNode->pChain->getNodeType()){
                    return (MVal*)pNode; //YES: Return item's last MVal
                }
            }
        }
        break;
    }
    //The first item from this starting point is the desired result
    return getFirstItem(pNode);
}

unsigned MRoot::getDictionaryItems()
{
    //Return total item number in current dictionary
    if(NULL != getTail()){
        return getTail()->uData;
    }else{
        return 0;
    }
}

MNode* MRoot::addNode(MNodeType mNodeType)
{
    //Use pNext in MTail as pointer to new node's predecessor 
    MNode* pNode = getBack()->getNext()->createNode(mNodeType);

    return pNode;
}

MRoot* MRoot::addRoot(const MString& mPath, MNodeType mRootType)
{
    MItem* pItem;
    MRoot* pRoot = this;
    MString mSubString;
    MString mDelimiter = MString(M_PATH_DELIMITERS);
    unsigned int uIndex = 0;

    //Generate subsequent substrings
    while(NULL != mPath.getDelimitedString(mDelimiter,&mSubString,&uIndex)){

        if (0!=mSubString.getLength()){
            //Add item to existing root respectively adjust it
            if(NULL != (pItem = pRoot->getItem(mSubString))){
                //Check if a root has been attached already before and create it if not
                pRoot = pItem->getRoot(mRootType);
            }
        }
    }
    return pRoot;
}

MItem* MRoot::reportLength(unsigned* uLength,const MString& mDelimiter)
{
    *uLength += mDelimiter.getLength();

    return (MItem*)pPrev;
}

void MRoot::generateURI(MString& mURI,const MString& mDelimiter,unsigned* puIndex)
{
    unsigned uBegin = *puIndex-mDelimiter.getLength();
    for(;*puIndex>uBegin;(*puIndex)--){
        mURI.setAt((*puIndex)-1,mDelimiter[*puIndex-uBegin-1]);
    }
    ((MItem*)pPrev)->generateURI(mURI,mDelimiter,puIndex);
}

MString& MRoot::getURI(MString& mURI,const MString& mDelimiter)
{
    unsigned uLength = 0;
    MRoot* pRoot = this;
    MItem* pItem;
    //Determine URI's total length
    while(NULL!=(pItem = pRoot->reportLength(&uLength,mDelimiter))){
        pRoot = pItem->reportLength(&uLength);
    }
    mURI.setLength(uLength);
    //Generate URI
    generateURI(mURI,mDelimiter,&uLength);
    return mURI;
}


//////////////////////////////////////////////////////////////////////
// MTail Class
//////////////////////////////////////////////////////////////////////
MTail::MTail(){}
MTail::~MTail(){}

//Report if a member variable is used as a pointer (and has to be adjusted on memory restore)
bool MTail::isPrevPtr(){return false;};
//Report runtime type information
MNodeType MTail::getNodeType(){return M_TAIL;};



//////////////////////////////////////////////////////////////////////
// MRootMemory Class
//////////////////////////////////////////////////////////////////////
MRootMemory::MRootMemory()
{
#ifdef _DEBUG
    //Initialize Debug file
    if(NULL == pDebugFile){
        if(NULL != (pDebugFile = fopen(DEBUG_FILE,"w"))){
            fwrite(FILE_HEADER1,strlen(FILE_HEADER1),1,pDebugFile);
            fwrite(NEW_LINE,2,1,pDebugFile);
            fwrite(FILE_HEADER2,strlen(FILE_HEADER2),1,pDebugFile);
            fwrite(NEW_LINE,2,1,pDebugFile);
            fwrite(FILE_HEADER3,strlen(FILE_HEADER3),1,pDebugFile);
            fwrite(NEW_LINE,2,1,pDebugFile);
            fwrite(NEW_LINE,2,1,pDebugFile);
        }
    }
#endif
}

MRootMemory::~MRootMemory()
{
#ifdef _DEBUG
    //Close Debug file
    if(NULL != pDebugFile){
        fclose(pDebugFile);
        pDebugFile = NULL;
    }
#endif
}

//Access functions
MNode* MRootMemory::getChain1(){return getChain();}
//Statistic functions related to nodes, items and dictionaries in the Morphic Memory
unsigned MRootMemory::getTotalNodes(){return uData;};
unsigned MRootMemory::getTotalItems(){return (unsigned)(getTail()->pMore);};
unsigned MRootMemory::getTotalDictionaries(){return (unsigned)(getTail()->pLess);};
//Report runtime type information
MNodeType MRootMemory::getNodeType(){return M_ROOT_MEMORY;};

void MRootMemory::generateURI(MString&,const MString&,unsigned*)
{
    return;
}

MItem* MRootMemory::reportLength(unsigned*,const MString&)
{
    return NULL;
}


MItem* MRootMemory::getStringItem(const MString& mString)
{
    //Insert subsequent characters into ternary tree and connect all in a chain (by pNext)
    MNode* pNode = this;
    for(int i=0; 0!=mString[i] && NULL!=pNode; i++){
        pNode->expandBTree(&pNode,mString[i],M_VAL,pNode->getAddrNext());
    }

    return getItem((MVal*)pNode);
}

MSysTime* MRootMemory::attachSession(MSession* pSession)
{
    MSysTime* pSysTime = getSysTime();
    pSession->setLess(pSysTime->getLess());
    pSysTime->setLess(pSession);

    return pSysTime;
}

MSysTime* MRootMemory::getSysTime()
{
    if (M_SYSTIME==pChain->getNodeType()){
        return (MSysTime*)pChain;
    }else{
        return adjustSysTime(0);
    }
}

int64 MRootMemory::getSysClock()
{
#ifndef WIN32
    struct timeval  stTimeValue;
    struct timezone stTimeZone;
    gettimeofday(&stTimeValue,&stTimeZone);
    return ((1000000*stTimeValue.tv_sec)+stTimeValue.tv_usec);
#else
   struct timeb timebuffer;
   _ftime( &timebuffer );
   return (int64)1000*(((int64)1000*timebuffer.time)+timebuffer.millitm);
#endif
}

MSysTime* MRootMemory::adjustSysTime(int64 n64Correction)
{
    //Generate and adjust a new MSysTime node
    MSysTime* pSysTime = (MSysTime*)pRootMemory->createNode(M_SYSTIME);
    if (M_SYSTIME==pSysTime->pChain->getNodeType()){
        pSysTime->pChain->pPrev = pSysTime;
    }
    pSysTime->pPrev = this;
    //Store corrections
    pSysTime->setBack((MNode*)(n64Correction&0xFFFFFFFF));
    pSysTime->setNext((MNode*)(n64Correction>>32));
    //Store timestamp
    int64 n64SysClock = getSysClock();
    pSysTime->setData((unsigned)n64SysClock&0xFFFFFFFF);
    pSysTime->setMore((MNode*)(n64SysClock>>32));

    return pSysTime;
}

MRootMemory* MRootMemory::createTop()
{
    MNode*  pTailMemory;

    //Generate initial couple of MRoot/MTail
    if(NULL != (pRootMemory = new MRootMemory())){
        if( NULL != (pTailMemory = pRootMemory->createNode(M_TAIL_MEMORY))){
            //Connect root and tail
            pRootMemory->pBack = pTailMemory;
            pTailMemory->pBack = pRootMemory;
            pTailMemory->pNext = pRootMemory; //empty chain of references
            //Set initial node and root count
            pRootMemory->uData = 2;
            pTailMemory->pLess = (MNode*)1;
        }
    }
    return pRootMemory;
}

unsigned MRootMemory::getNodeSize()
{
    MNode* pNode1 = new MNode[2];

    //Calculate a node's memory consumption
    return ((unsigned)(pNode1+1) - (unsigned)pNode1);
}

unsigned MRootMemory::getDictionaryLemmas(char* pPath)
{
    MRoot* pDictionary;

    if(NULL != (pDictionary = pRootMemory->getDictionary(pPath))){
        if(NULL != pDictionary->pBack){
            return (unsigned)pDictionary->pBack->pPrev;
        }
    }
    return 0;
}

unsigned MRootMemory::getDictionaryItems(char* pPath)
{
    MRoot* pDictionary;

    if(NULL != (pDictionary = pRootMemory->getDictionary(pPath))){
        if(NULL != pDictionary->pBack){
            return pDictionary->pBack->uData;
        }
    }
    return 0;
}

MRoot* MRootMemory::getDictionary(char* _szPath)
{
    return addRoot(MString(_szPath),M_DICTIONARY);
}


//Initialize the Morphic Memory from a backup file
MRootMemory* MRootMemory::initMMemory(char* _szMemoryFile)
{
    FILE*    pBackup;
    int      nLen;
    MBackup  stBackup;
    MNode*   pNode;
    unsigned uMin = (unsigned)(-1L);
    unsigned uMax = 0;
    unsigned uMinPtr = (unsigned)(-1L);
    unsigned uMaxPtr = 0;
    unsigned uMask = 0;
    unsigned uAlignment = 0;
    unsigned uDimension;
    unsigned uTotalNodes = 0;
    MNode**  pAddrTable;
    struct stat buf;
    int      fh;
    unsigned uFileSize = 0;

    //Determine file size
    if (-1!=(fh = open( _szMemoryFile,O_RDONLY))){
        if (0==fstat(fh,&buf)){
            uFileSize = buf.st_size;
        }else{
            throw MException("File status not accessible:");
        }
        close( fh );
    }else{
        throw MException("Data file not found:");
    }

    pBackup = fopen( _szMemoryFile,"rb");
    if (0==uFileSize || NULL==pBackup || 0x00000000==pBackup){
        throw MException("Data file not accessible:");
    }else{
        //Read root data
        nLen = fread(&stBackup, sizeof(stBackup), 1, pBackup);
        if(nLen != 1){
            throw MException("Data file was damaged (0-File):");
        }else{
            if (M_ROOT_MEMORY!=stBackup.mNodeType){
                throw MException("Data file was damaged (1-Root):");
            }
            pRootMemory = (MRootMemory*)MRootMemory::createRoot(M_ROOT_MEMORY);
            pNode = pRootMemory;
            uTotalNodes = stBackup.uData;
            //Check total nodes against file size
            if (uTotalNodes!=(uFileSize/32)){
                throw MException("Data file was damaged (2-Size):");
            }
            uMin = (unsigned)stBackup.pThis;
            uMax = (unsigned)stBackup.pThis;
        }
        //Regenerate all nodes
        while(pNode != NULL && nLen == 1){
            //Restore pointers and values
            pNode->pBack = stBackup.pBack;
            pNode->pLess = stBackup.pLess;
            pNode->pMore = stBackup.pMore;
            pNode->pPrev = stBackup.pPrev;
            pNode->pNext = stBackup.pNext;
            pNode->uData = stBackup.uData;
            //Determine adress characteristics
            if((unsigned)stBackup.pThis < uMin){
                uMin = (unsigned)stBackup.pThis;
            }
            if((unsigned)stBackup.pThis > uMax){
                uMax = (unsigned)stBackup.pThis;
            }
            uMask |= (unsigned)stBackup.pThis;
            //Read next node backup
            nLen = fread(&stBackup, sizeof(stBackup), 1, pBackup);
            if(nLen == 1){
                pNode = pNode->createNode(stBackup.mNodeType);
            }
            //Check against implemented set of node types
            if (NULL==pNode){
                throw MException("Data file was damaged (3-Type):");
            }
            //Determine extrem pointers
            if(pNode->isBackPtr()){
                if(0!=stBackup.pBack && (unsigned)stBackup.pBack<uMinPtr){
                    uMinPtr = (unsigned)stBackup.pBack;}
                if((unsigned)stBackup.pBack>uMaxPtr){
                    uMaxPtr = (unsigned)stBackup.pBack;}
            }
            if(pNode->isLessPtr()){
                if(0!=stBackup.pLess && (unsigned)stBackup.pLess<uMinPtr){
                    uMinPtr = (unsigned)stBackup.pLess;}
                if((unsigned)stBackup.pLess>uMaxPtr){
                    uMaxPtr = (unsigned)stBackup.pLess;}
            }
            if(pNode->isMorePtr()){
                if(0!=stBackup.pMore && (unsigned)stBackup.pMore<uMinPtr){
                    uMinPtr = (unsigned)stBackup.pMore;}
                if((unsigned)stBackup.pMore>uMaxPtr){
                    uMaxPtr = (unsigned)stBackup.pMore;}
            }
            if(pNode->isPrevPtr()){
                if(0!=stBackup.pPrev && (unsigned)stBackup.pPrev<uMinPtr){
                    uMinPtr = (unsigned)stBackup.pPrev;}
                if((unsigned)stBackup.pPrev>uMaxPtr){
                    uMaxPtr = (unsigned)stBackup.pPrev;}
            }
            if(pNode->isNextPtr()){
                if(0!=stBackup.pNext && (unsigned)stBackup.pNext<uMinPtr){
                    uMinPtr = (unsigned)stBackup.pNext;}
                if((unsigned)stBackup.pNext>uMaxPtr){
                    uMaxPtr = (unsigned)stBackup.pNext;}
            }
            if(pNode->isDataPtr()){
                if(0!=stBackup.uData && stBackup.uData<uMinPtr){
                    uMinPtr = stBackup.uData;}
                if(stBackup.uData>uMaxPtr){
                    uMaxPtr = stBackup.uData;}
            }
        }
        //Check pointers against range of node addresses
        if (uMinPtr<uMin){
            throw MException("Data file was damaged (4-Ptr<):");
        }
        if (uMaxPtr>uMax){
            throw MException("Data file was damaged (4-Ptr>):");
        }
        //Restore total node count
        pRootMemory->uData = uTotalNodes;
        //Calculate minimal  dimension of an address translation table
        uDimension = uMax - uMin;
        while( (uMask & 0x00000001) == 0){
            uMask >>= 1;
            uDimension >>= 1;
            uAlignment++;
        }
        pAddrTable = new MNode*[uDimension+1];
        for(unsigned i=0;i<uDimension;i++){
            pAddrTable[i] = NULL;
        }
        //Generate address translation table
        rewind(pBackup);
        pNode = pRootMemory;
        while(pNode != NULL &&
              1 == (nLen = fread(&stBackup, sizeof(stBackup), 1, pBackup))){
            pAddrTable[((unsigned)stBackup.pThis-uMin)>>uAlignment] = pNode;
            pNode = pNode->pChain;
        }
        fclose(pBackup);
        //Adjust all node's pointers
        pNode = pRootMemory;
        do{
            if(NULL != pNode->pBack && pNode->isBackPtr()){
                if (NULL==(pNode->pBack = pAddrTable[((unsigned)pNode->pBack-uMin)>>uAlignment])){
                    throw MException("Data file was damaged (4-Back):");
                }
            }
            if(NULL != pNode->pLess && pNode->isLessPtr()){
                if (NULL==(pNode->pLess = pAddrTable[((unsigned)pNode->pLess-uMin)>>uAlignment])){
                    throw MException("Data file was damaged (5-Less):");
                }
            }
            if(NULL != pNode->pMore && pNode->isMorePtr()){
                if (NULL==(pNode->pMore = pAddrTable[((unsigned)pNode->pMore-uMin)>>uAlignment])){
                    throw MException("Data file was damaged (6-More):");
                }
            }
            if(NULL != pNode->pPrev && pNode->isPrevPtr()){
                if (NULL==(pNode->pPrev = pAddrTable[((unsigned)pNode->pPrev-uMin)>>uAlignment])){
                    throw MException("Data file was damaged (7-Prev):");
                }
            }
            if(NULL != pNode->pNext && pNode->isNextPtr()){
                if (NULL==(pNode->pNext = pAddrTable[((unsigned)pNode->pNext-uMin)>>uAlignment])){
                    throw MException("Data file was damaged (8-Next):");
                }
            }
            if(NULL != pNode->uData && pNode->isDataPtr()){
                if (NULL==(pNode->uData = (unsigned)pAddrTable[((unsigned)pNode->uData-uMin)>>uAlignment])){
                    throw MException("Data file was damaged (9-Data):");
                }
            }
        }while(NULL != (pNode = pNode->pChain));
        delete pAddrTable;
        //Make all nodes become alive
        pNode = pRootMemory;
        while(NULL != pNode->pChain && M_TAIL_MEMORY != pNode->getNodeType()){
            pNode->go();
            pNode = pNode->pChain;
        }
    }
    return pRootMemory;
}


//Put the chain of nodes to disk
void MRootMemory::backupMMemory(char* _szMemoryFile)
{
    FILE*   pBackup;
    MBackup stBackup;
    MNode*  pNode = this;

    if( NULL != (pBackup = fopen( _szMemoryFile,"wb"))){

        do{
            stBackup.mNodeType  = pNode->getNodeType();
            stBackup.pThis      = pNode;
            stBackup.pBack      = pNode->pBack;
            stBackup.pLess      = pNode->pLess;
            stBackup.pMore      = pNode->pMore;
            stBackup.pPrev      = pNode->pPrev;
            stBackup.pNext      = pNode->pNext;
            stBackup.uData      = pNode->uData;

            fwrite(&stBackup, sizeof(stBackup), 1, pBackup);

        }while(NULL != (pNode = pNode->pChain));
        fclose(pBackup);
    }
}



//////////////////////////////////////////////////////////////////////
// MTailMemory Class
//////////////////////////////////////////////////////////////////////
MTailMemory::MTailMemory(){}
MTailMemory::~MTailMemory(){}

//Report if a member variable is used as a pointer (and has to be adjusted on memory restore)
bool MTailMemory::isLessPtr(){return false;}
bool MTailMemory::isMorePtr(){return false;}
bool MTailMemory::isPrevPtr(){return false;}
//Report runtime type information
MNodeType MTailMemory::getNodeType(){return M_TAIL_MEMORY;};



//////////////////////////////////////////////////////////////////////
// MVal Class
//////////////////////////////////////////////////////////////////////
MVal::MVal(){}
MVal::~MVal(){}

//Obtain item's hash value
unsigned MVal::getHash(){return pChain->uData;};
//Report runtime type information
MNodeType MVal::getNodeType(){return M_VAL;};

void MVal::reportLength(unsigned* puLength)
{
    (*puLength)++;
}

void MVal::getString(MString* pString)
{
    //Determine resulting string length
    unsigned nLength = 0;
    MNode*   pNode = this;
    while(false == pNode->isRoot()){
        nLength++;
        pNode = pNode->pPrev;
    }
    //Generate target string
    pString->setLength(nLength);
    pNode = this;
    int i=nLength-1;
    while(false == pNode->isRoot()){
        pString->setAt(i--, pNode->uData);
        pNode = pNode->pPrev;
    }
}

#ifdef _DEBUG
MVal::talk(char* pszInfo)
{
    MString mString;

    if(NULL != pDebugFile){
        getString(&mString);
        fwrite(pszInfo,strlen(pszInfo),1,pDebugFile);
        fwrite(mString.getText(),mString.getLength(),1,pDebugFile);
        fwrite(NEW_LINE,2,1,pDebugFile);
    }
}
#endif



//////////////////////////////////////////////////////////////////////
// MRef Class
//////////////////////////////////////////////////////////////////////
MRef::MRef(){}
MRef::~MRef(){}

bool MRef::isDataPtr(){return true;}

MItem* MRef::getItem()
{
    //Obain root node
    MNode* pRoot = this;
    while (false==(pRoot = pRoot->getPrev())->isRoot());

    return ((MRoot*)pRoot)->getItem(this);
}

MRef* MRef::getRef(const MString& mString)
{
    MItem* pItem = pRootMemory->getItem(mString);
    return pItem->addRef(this);
}

void MRef::reportLength(unsigned* puLength)
{
    ((MItem*)uData)->reportLength(puLength);
}

void MRef::generateURI(MString& mURI,const MString& mDelimiter,unsigned* puIndex)
{
    ((MItem*)uData)->generateURI(mURI,mDelimiter,puIndex);
}

unsigned MRef::getWeight()
{
    return ((MItem*)getData())->getData();
}

//Report runtime type information
MNodeType MRef::getNodeType(){return M_REF;};



//////////////////////////////////////////////////////////////////////
// MItem Class
//////////////////////////////////////////////////////////////////////
MItem::MItem(){}
MItem::~MItem(){}

//Report special features and runtime type   
MNodeType MItem::getNodeType(){return M_ITEM;};

MItem* MItem::getItem(const MString& mType)
{
    return getRoot()->getItem(mType);
}

MString& MItem::getReferent(MString& mReferent)
{
    //Obtain most recent concept
    MNode* pNode = this;
    while(NULL!=pNode&&(M_CONCEPT!=pNode->getNodeType())){
        pNode = pNode->getNext();
    }
    if (NULL==pNode){
        throw MException("concept not available");
    }else{
        ((MConcept*)pNode)->getReferent()->getString(mReferent);
    }
    return mReferent;
}

MString& MItem::getReferent(MString& mReferent,const MString& mType)
{
    return getItem(mType)->getReferent(mReferent);
}

MState* MItem::getState()
{
    //Obtain most recent state
    MNode* pNode = this;
    while(NULL!=pNode&&(M_STATE!=pNode->getNodeType())){
        pNode = pNode->getNext();
    }
    if (NULL==pNode){
        throw MException("state not available");
    }
    return (MState*)pNode;
}

MState* MItem::getState(const MString& mType)
{
    return getItem(mType)->getState();
}

MSpecial* MItem::getSpecial(MNodeType mNodeType)
{
    //Search for specified special node type
    MNode* pNode = this;
    while(NULL!=pNode){
        pNode = pNode->getNext();
        if ((NULL!=pNode)&&(M_SPECIAL==pNode->getNodeType())){
            if (mNodeType==pNode->getMore()->getNodeType()){
                break;
            }
        }
    }
    if (NULL==pNode){
        throw MException("special not available");
    }
    return (MSpecial*)pNode;
}

MConcept* MItem::setReferent(MSession* pSession,MItem* pDst)
{
    MConcept* pConcept = (MConcept*)pDst->createNode(M_CONCEPT);
    pSession->attachConcept(pConcept);
    pConcept->setMore(pDst);
    pConcept->setNext(pNext);
    pNext = pConcept;
    pConcept->setPrev(this);

    return pConcept;
}

MSpecial* MItem::addSpecial(MSession* pSession,MNodeType mNodeType)
{
    //Obtain current root
    MNode* pNode = this;
    while(false==(pNode = pNode->getPrev())->isRoot());
    //Generate MSpecial and an arbitrary MNode type that will be referenced by MSpecial
    MSpecial* pSpecial = (MSpecial*)(((MRoot*)pNode)->addNode(M_SPECIAL));
    pSession->attachConcept(pSpecial);
    pSpecial->setMore(((MRoot*)pNode)->addNode(mNodeType));
    pSpecial->setNext(pNext);
    pNext = pSpecial;
    pSpecial->setPrev(this);
    return pSpecial;
}

MState* MItem::setState(MSession* pSession,int nState)
{
    MState* pState = (MState*)pRootMemory->getBack()->getNext()->createNode(M_STATE);
    pSession->attachConcept(pState);
    pState->setMore((MNode*)nState);
    pState->setNext(pNext);
    pNext = pState;
    pState->setPrev(this);

    return pState;
}

MSession* MItem::getSession()
{
    MNode* pNode = this;
    while (NULL!=(pNode = pNode->getNext())){
        if (M_SESSION==pNode->getNodeType()){
            return (MSession*)pNode;
        }
    }
    return addSession();
}

MSession* MItem::addSession()
{
    MSession* pSession = (MSession*)this->createNode(M_SESSION);
    int64 n64SysTime = pRootMemory->getSysClock();
    pSession->setData(LO64(n64SysTime));
    pSession->setMore((MNode*)HI64(n64SysTime));
    pSession->setBack(pSession);
    pSession->setNext(pNext);
    pSession->setPrev(this);
    pNext = pSession;
    pRootMemory->attachSession(pSession);

    return pSession;
}

MConcept* MItem::getConcept()
{
    MNode* pNode = this;
    while (NULL!=pNode && M_CONCEPT!=pNode->getNodeType()){
        pNode = pNode->getNext();
    }
    return (MConcept*)pNode;
}

MRoot* MItem::getRoot()
{
    return getRoot(M_ROOT);
}

MRoot* MItem::getRoot(MNodeType mRootType)
{
    MRoot* pRoot;
    //Check if a MRoot/MTail couple exists already
    if (true==pChain->isRoot()){
        pRoot = (MRoot*)pChain;
    }else{
        //Generate a new couple of MRoot/MTail
        MTail* pTail;
        if(NULL != (pRoot = (MRoot*)createNode(mRootType))){
            if( NULL != (pTail = (MTail*)(pRoot->createNode(M_TAIL)))){
                pRoot->pPrev = this;
                pRoot->pBack = pTail;
                pTail->pBack = pRoot;
                pTail->pNext = pRoot;
                //Increment dictionary pointer
                pRootMemory->getTail()->pLess = (MNode*)(1+(unsigned)pRootMemory->getTail()->pLess);
            }
        }
    }
    return pRoot;
}

MVal* MItem::getNextItem()
{
    MNode* pNode = this->pPrev;

    //Adjust dictionary's root
    while(false == pNode->isRoot()){
        pNode = pNode->pPrev;
    }
    //The dictionary knows how to get to the next item
    return ((MRoot*)pNode)->getNextItem(this);
}

MRef* MItem::addRef(MNode* pPred)
{
    //Generate (if non-existent) and connect new MRef to desired dictionary
    MRef*  pRef;
    MRoot* pRoot = getRoot();
    if (true==pRoot->expandBTree((MNode**)&pRef,uData,M_REF,pPred->getAddrNext())){
        //New MRef
        pRef->setWeight((unsigned)this); //MItem* is put to uData, but MItem's hash value will be returned by MRef as weight
        pRef->setPrev(pPred);
        //Adjust if necessary the pointer to first reference (= predecessor for new nodes)
        if (pRoot == pRoot->getBack()->getNext()){
            pRoot->getBack()->setNext(pRef);
        }
    }
    return pRef;
}

MRoot* MItem::reportLength(unsigned* puLength)
{
    MNode* pNode = pPrev;
    while (false==pNode->isRoot()){
        ((MVal*)pNode)->reportLength(puLength);
        pNode = pNode->pPrev;
    }
    return (MRoot*)pNode;
}

void MItem::generateURI(MString& mURI,const MString& mDelimiter,unsigned* puIndex)
{
    MNode* pNode = pPrev;
    while (false==pNode->isRoot()){
        pNode->generateURI(mURI,mDelimiter,puIndex);
        pNode = pNode->pPrev;
    }
    ((MRoot*)pNode)->generateURI(mURI,mDelimiter,puIndex);
}


void MItem::getString(MString& mString)
{
    //Determine MString's total length
    unsigned uLength = 0;
    reportLength(&uLength);
    //Complete string
    mString.setLength(uLength);
    generateURI(mString,MString(""),&uLength);
}