/***************************************************************************
 *   Copyright (C) 2005 by Andreas Pokorny                                 *
 *   andreas.pokorny@biozentrum.uni-wuerzburg.de                           *
 *                                                                         *
 *   This file is part of profdist and cbcanalyzer                         *
 *                                                                         *
 *   Both profdist and cbcanalyzer are 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 2 of the * 
 *   License, or (at your option) any later version.                       *
 *                                                                         *
 *   Profdist and cbcanalyzer are 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; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/

#ifndef COUNTED_SETS_HEADER_INCLUDED
#define COUNTED_SETS_HEADER_INCLUDED

#include <set>
#include <map>
#include <iostream>



/**
 * This class counts sets of subtrees, by using a std::map, that maps from 
 * std::set<unsigned int>, which represents the set of all sequences in a subtree,
 * onto its count in the full tree.
 */
class CountedSets
{
  public:
    typedef std::set<unsigned int> set_type;
    
    struct SizedLexicographyOrder
    {
      bool operator()( set_type const& A, set_type const& B ) const
      {
        if ( A.size() < B.size() )
          return true;
        else if ( A.size() > B.size() )
          return false;
        else
          return A < B;
      }
    };

    typedef std::map<set_type, std::size_t, SizedLexicographyOrder> set_counter_type;
    typedef set_counter_type::const_iterator const_iterator;
    typedef set_counter_type::const_reverse_iterator const_reverse_iterator;
  private:
    set_counter_type set_counter;
    
    std::size_t count_difference( set_type const& a, set_type const& b ) const;
    bool is_compatible( set_counter_type const& base, set_type const& a ) const;
      
  public:

    /**
     * Provides debug printouts of countedsets
     */
    std::ostream& print( std::ostream & out ) const;

    /**
     * Remove all split sets from internal container
     */
    void clear();

    /**
     * @brief Creates a consensus tree from all subsets
     * @param num_seqs the number of sequences in the alignment
     */
    void consense( std::size_t num_seqs );

    /**
     * @brief adds count subtree(s) to the container
     * @param subtree the subtree to add to the container
     * @param count the number of subtrees that should be added
     */
    void add_set( set_type const& subtree, std::size_t count = 1);
   
    /**
     * @brief checks the contents of a split set. 
     * @param a the split set
     * @param num_seq number of sequences processed currently
     */
    void check_set( set_type const& a, size_t num_seq ) const;

    /**
     * @brief returns the number of subtree in this container
     * @param subtree the subtree to find
     * @returns number of subtrees equal to the parameter that are in that container
     */
    std::size_t get_count( set_type const& subtree ) const;
    
    const_iterator begin() const;
    const_iterator end() const;

    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const;

    /**
     * @brief nomber of distinct sets
     */
    inline std::size_t size() const  { return set_counter.size(); };

};

std::ostream& operator<< ( std::ostream & out, CountedSets const& obj );

void print_split_set( std::ostream & out, CountedSets::set_type const& split );

#endif

