/*
  $Id: filtertreenode.h 4025 2008-10-01 00:01:14Z abehm $

  Copyright (C) 2008 by The Regents of the University of California
	
  Redistribution of this file is permitted under
  the terms of the BSD license
    
  Date: 04/04/2008
  Author: Alexander Behm <abehm (at) ics.uci.edu>
*/

#ifndef _filtertreenode_h_
#define _filtertreenode_h_

#include <tr1/unordered_map>
#include <vector>
#include <set>

#include "gramlist.h"
#include "common/gramgen.h"
#include "util/array.h"

template <class InvList = Array<unsigned> >
class FilterTreeNode {
 public:
  // maps from gram code to gram list (that contains the inverted list)
  typedef unordered_map<unsigned, GramList<InvList>* > GramMap;

  GramMap gramMap;
  // for leaves keep track of the distinct string ids belonging to this leaf
  GramList<InvList>* distinctStringIDs;
  vector<pair<unsigned, FilterTreeNode*> > children;
  bool isLeaf;

  FilterTreeNode(bool leaf) { 
    isLeaf = leaf; 
    distinctStringIDs = NULL;  
  }  

  void getInvertedLists(const string& query, 
			GramGen& gramGen,
			vector<InvList*> &invertedLists) {
    vector<unsigned> gramCodes;
    gramGen.decompose(query, gramCodes);      
    getInvertedLists(gramCodes, invertedLists);       
  }
  
  void getInvertedLists(const vector<unsigned>& gramCodes, 
			vector<InvList*> &invertedLists) {
    for(unsigned i = 0; i < gramCodes.size(); i++) {
      unsigned gramCode = gramCodes.at(i);
      if(gramMap.find(gramCode) != gramMap.end()) {
	Array<unsigned>* tmp = gramMap[gramCode]->getArray();
	invertedLists.push_back(tmp);
      }
    }  
  }
  
  void getGramLists(const string& query, 
		    GramGen& gramGen,
		    vector<pair<unsigned, GramList<InvList>* > >& gramLists) {
    vector<unsigned> gramCodes;
    gramGen.decompose(query, gramCodes);      
    getGramLists(gramCodes, gramLists);       
  }
  
  void getGramLists(const vector<unsigned>& gramCodes, 
		    vector<pair<unsigned, GramList<InvList>* > >& gramLists) {
    for(unsigned i = 0; i < gramCodes.size(); i++) {
      unsigned gramCode = gramCodes.at(i);
      if(gramMap.find(gramCode) != gramMap.end()) {
	pair<unsigned, GramList<InvList>* > p;
	p.first = gramCode;
	p.second = gramMap[gramCode];
	gramLists.push_back(p);
      }
    }
  }

  static void getSubTreeLeaves(FilterTreeNode<InvList>* node, vector<FilterTreeNode<InvList>* >& leaves) {
    if(node->isLeaf) leaves.push_back(node);
    else {    
      vector<pair<unsigned, FilterTreeNode*> >& children = node->children;
      for(unsigned i = 0; i < children.size(); i++)
	FilterTreeNode::getSubTreeLeaves(children.at(i).second, leaves);
    }    
  }
  
  static unsigned getTotalInvertedListsSize(FilterTreeNode* node) {
    unsigned sum = 0;
    typename GramMap::const_iterator citer;
    for(citer = node->gramMap.begin(); citer != node->gramMap.end(); citer++)
      sum += citer->second->getArray()->size();
    return sum;
  }
 
  unsigned long getBytes() const {
    unsigned long total = 0;
    total += sizeof(vector<pair<unsigned, FilterTreeNode*> >);
    total += sizeof(pair<unsigned, FilterTreeNode>) * children.size(); 
    total += sizeof(GramMap);
    total += sizeof(Array<unsigned>);
    total += sizeof(unsigned) * distinctStringIDs.size();
    return total;    
  }

  ~FilterTreeNode() {
    for(typename GramMap::iterator iter = gramMap.begin();
	iter != gramMap.end();
	iter++) {
      GramList<InvList>* tmp = iter->second;
      if(tmp) tmp->free();
    }
    if(distinctStringIDs) delete distinctStringIDs;
  }
};


#endif