/* ================================================================= *
 *  qlist.h : Header file with supporting class definitions          *
 *                                                                   *
 *  E-MEM: An efficient (MUMmer-like) tool to retrieve Maximum Exact *
 *         Matches using hashing based algorithm                     *
 *                                                                   *
 *  Copyright (c) 2014, Nilesh Khiste                                *
 *  All rights reserved                                              *
 *                                                                   * 
 *  This program is free software: you can redistribute it and/or    *
 *  modify it under the terms of the GNU General Public License as   *
 *  published by the Free Software Foundation, either version 3 of   *
 *  the License, or (at your option) any later version.              *
 *                                                                   *
 *  This program 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 General Public License for more details.                     *
 *                                                                   *
 *  You should have received a copy of the GNU General Public        *
 *  License along with this program.                                 *
 *                                                                   *
 *  This file is subject to the terms and conditions defined in the  *
 *  file 'LICENSE', which is part of this source code package.       *
 * ================================================================= */

class qneryList; 
 
class MEMS_LIST {
    friend class queryList;
    uint64_t key;
    MEMS_LIST *next;
};

class queryList { 
    uint64_t left; 
    uint64_t right; 
    class queryList* next;
    class MEMS_LIST* mems;

    queryList *queryList_Alloc (uint64_t a=0, uint64_t b=0, uint64_t key=0)
    {
        queryList *q = new queryList;
        q->left = a;
        q->right = b;
        q->next=NULL;
        q->mems=new MEMS_LIST;
        q->mems->key = key;
        q->mems->next = NULL;
        return q;
    }
  
 public:
    void ListFree(queryList** listRef)
    {
        if (!*listRef)
            return;
        while(*listRef)
        {    
            // Free all MEMs node found using this this Kmer
            MEMS_LIST *remMems = (*listRef)->mems, *remMemNext=NULL;
            while(remMems) {
                remMemNext = remMems->next;
                delete remMems;
                remMems = remMemNext;
            }
            queryList *tmp = (*listRef)->next;
            delete *listRef;
            *listRef=tmp;
        }
    }

    void ListAdd(queryList** listRef, uint64_t l, uint64_t r, uint64_t key)
    {
        queryList *prev_node=*listRef;
        queryList *node=*listRef;

        if (*listRef == NULL) {
            *listRef = queryList_Alloc (l, r, key);
            return;
        }

        while(node)
        {
            if (node->right > r) {
                queryList *p = queryList_Alloc(l, r, key);
                p->next = node;
                if (node == this)
                   *listRef = p;
                else
                   prev_node->next = p;
                return;
            }else if (node->right == r) {
                if(node->left == l){
                    //Add MEM_LIST item
                    MEMS_LIST *mems=new MEMS_LIST;
                    mems->key = key;
                    mems->next = node->mems;
                    node->mems =mems;
                    return; //node already in the list
                }
            }

            prev_node = node;
            node=node->next;
            if (!node) { // end of list
                queryList *p = queryList_Alloc(l, r, key);
                prev_node->next = p;
                return;
            }
         }
         return;
    }

    int checkRedundantMEM(queryList ** listRef, uint64_t refKmerPos, uint64_t QueryKmerPos, uint64_t totalRBits, std::unordered_multimap <uint64_t, uint64_t> &currMEMs)
    {
        // Find MEM positions from currQueryMEMs list
        queryList *p = *listRef; 
        while (p) {
            if (QueryKmerPos >= p->left && (QueryKmerPos+commonData::kmerSize-2) <= p->right) {//Found MEM
                uint64_t relLeft = QueryKmerPos - p->left;
                uint64_t relRight = p->right - QueryKmerPos;
                uint64_t refRightPos=refKmerPos+relRight;
                if(refRightPos > totalRBits)
                    refRightPos=totalRBits;
    
                if ((refKmerPos >= relLeft) ){
                    uint64_t key = ((refKmerPos-relLeft) << 32 | (refRightPos));
                    uint64_t value = ((p->left << 32) | p->right);
                    auto range = currMEMs.equal_range(key);
                    for (auto it = range.first; it != range.second; ++it) { // Element found
                        if (it->second == value)
                            return true;
                    }
                 }
            }else if ((QueryKmerPos+commonData::kmerSize-2) > p->right) {
                // Free all MEMs node found using this this Kmer
                MEMS_LIST *remMems = p->mems, *remMemNext=NULL;
                uint64_t value = ((p->left << 32) | p->right);
                p->mems = NULL;
                while(remMems) {
                    remMemNext = remMems->next;
                    auto range = currMEMs.equal_range(remMems->key);
                    for (auto it = range.first; it != range.second; ++it) { // Element found
                        if (it->second == value){
                            currMEMs.erase(it);
                            break;
                        }
                    }
                    delete remMems;
                    remMems = remMemNext;
                }
                *listRef = p->next;
                delete p;
                p = *listRef;
                continue;
            }
            p=p->next;
        }
        return false;
    }
};