/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
 *
 * The contents of this file are subject to the terms of either the GNU Lesser
 * General Public License Version 2.1 only ("LGPL") or the Common Development and
 * Distribution License ("CDDL")(collectively, the "License"). You may not use this
 * file except in compliance with the License. You can obtain a copy of the CDDL at
 * http://www.opensource.org/licenses/cddl1.php and a copy of the LGPLv2.1 at
 * http://www.opensource.org/licenses/lgpl-license.php. See the License for the
 * specific language governing permissions and limitations under the License. When
 * distributing the software, include this License Header Notice in each file and
 * include the full text of the License in the License file as well as the
 * following notice:
 *
 * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
 * (CDDL)
 * For Covered Software in this distribution, this License shall be governed by the
 * laws of the State of California (excluding conflict-of-law provisions).
 * Any litigation relating to this License shall be subject to the jurisdiction of
 * the Federal Courts of the Northern District of California and the state courts
 * of the State of California, with venue lying in Santa Clara County, California.
 *
 * Contributor(s):
 *
 * If you wish your version of this file to be governed by only the CDDL or only
 * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
 * include this software in this distribution under the [CDDL or LGPL Version 2.1]
 * license." If you don't indicate a single choice of license, a recipient has the
 * option to distribute your version of this file under either the CDDL or the LGPL
 * Version 2.1, or to extend the choice of license to its licensees as provided
 * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
 * Version 2 license, then the option applies only if the new code is made subject
 * to such option by the copyright holder.
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef HAVE_ASSERT_H
#include <assert.h>
#endif

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#include <vector>
#include <map>
#include <cmath>

#include "../sim_slm.h"
#include "../slm.h"

#include "ValueCompress.h"

using std::log;
using std::log2;
using std::exp;
using std::exp2;

class CSIMSlmWithIteration : public CSIMSlm {
public:
    struct TLevelIterator {
        std::vector<int>    m_history;
    };

public:
    int
    getLevelSize(int lvl)
    {
        return sz[lvl];
    }

    int
    getN()
    {
        return N;
    }

    void
    getIdString(TLevelIterator& it, std::vector<TSIMWordId>& history);

    void
    beginLevelIteration(int lvl, TLevelIterator& it);

    void
    next(TLevelIterator& it);

    bool
    isEnd(TLevelIterator& it);

    TLeaf*
    getNodePtr(TLevelIterator& it);

    int
    findState(int n, TSIMWordId*hw);

    void
    findBackOffState(int n, TSIMWordId*hw, unsigned & bol, unsigned& bon);


protected:
    void
    adjustIterator(TLevelIterator& it);
};

int
CSIMSlmWithIteration::findState(int n, TSIMWordId*hw)
{
    if (n == 0) return 0;

    int m = -1;
    while (n > N) {
        --n; ++hw;
    }

    void* pstate = ((TNode*)level[0]);
    for (int lvl = 0; lvl < n && pstate != NULL; ++lvl) {
        int h = ((TNode*)pstate)->child;
        int t = (((TNode*)pstate) + 1)->child;
        if (lvl == N - 1) {
            TLeaf* p = (TLeaf*)level[lvl + 1];
            pstate = (void*)binary_find_id(p + h, p + t, hw[lvl]);
            m = (pstate != NULL) ? (((TLeaf*)pstate) - p) : (-1);
        } else {
            TNode* p = (TNode*)level[lvl + 1];
            pstate = (void*)binary_find_id(p + h, p + t, hw[lvl]);
            m = (pstate != NULL) ? (((TNode*)pstate) - p) : (-1);
        }
    }
    return m;
}

void
CSIMSlmWithIteration::findBackOffState(int n,
                                       TSIMWordId*hw,
                                       unsigned & bol,
                                       unsigned& bon)
{
    while (n > 1) {
        --n; ++hw;
        int idx = findState(n, hw);
        if (idx >= 0 && ((TNode*)(level[n]))[idx].child <
            ((TNode*)(level[n]))[idx + 1].child) {
            bol = n; bon = idx; return;
        }
    }
    bol = bon = 0;
    return;
}

void
CSIMSlmWithIteration::getIdString(TLevelIterator& it,
                                  std::vector<TSIMWordId>& history)
{
    history.clear();
    for (int i = 1, tmp_sz = it.m_history.size(); i < tmp_sz; ++i) {
        int idx = it.m_history[i];
        if (i == N)
            history.push_back(((TLeaf*)(level[i]))[idx].id);
        else
            history.push_back(((TNode*)(level[i]))[idx].id);
    }
}

void
CSIMSlmWithIteration::beginLevelIteration(int lvl, TLevelIterator& it)
{
    it.m_history.clear();
    for (int i = 0, tmp_sz = lvl; i <= tmp_sz; ++i)
        it.m_history.push_back(0);
    adjustIterator(it);
}

void
CSIMSlmWithIteration::next(TLevelIterator& it)
{
    ++(it.m_history.back());
    adjustIterator(it);
}

bool
CSIMSlmWithIteration::isEnd(TLevelIterator& it)
{
    return((it.m_history.back() + 1 >= sz[it.m_history.size() - 1]));
}

void
CSIMSlmWithIteration::adjustIterator(TLevelIterator& it)
{
    int ch = it.m_history.back();
    for (int i = it.m_history.size() - 2; i >= 0; --i) {
        int len = sz[i];
        int& parent = it.m_history[i];
        TNode* pn = (TNode*)(level[i]);
        while (parent < len && pn[parent + 1].child <= ch)
            ++parent;
        ch = parent;
    }
}

CSIMSlm::TLeaf*
CSIMSlmWithIteration::getNodePtr(TLevelIterator& it)
{
    int lvl = it.m_history.size() - 1;
    int idx = it.m_history.back();
    if (lvl == N)
        return(((TLeaf*)(level[lvl])) + idx);
    else
        return(((TNode*)(level[lvl])) + idx);
}



void
ShowUsage()
{
    printf("Usage:\n");
    printf("    slmthread primitive_slm threaded_slm\n");
    printf("\nDescription:\n");
    printf(
        "    slmthread add back-off-state for each slm node in the primitive_slm. ");
    printf("Also it compresses 32-bit float into 16 bit representation.\n\n");
    exit(100);
}

FILE* fp = NULL;
CThreadSlm::TNode* levels[16];
CThreadSlm::TLeaf* lastLevel;

int
main(int argc, char* argv[])
{
    CValueCompressor vc;
    unsigned int bol, bon;
    CSIMSlmWithIteration slm;
    std::vector<TSIMWordId> history;
    float real_pr, eff_pr, real_bow, eff_bow;

    std::map<float, float> pr_eff, bow_eff;     // effval --> val
    std::map<float, int> pr_values, bow_values; // effval --> freq
    std::map<float, int> pr_map, bow_map;       // result: val --> int
    std::vector<float>   pr_table, bow_table;   // result: val vector
    std::vector<float>::iterator itt, itte;

    if (argc != 3)
        ShowUsage();

    printf("Loading original slm..."); fflush(stdout);
    if (!slm.Load(argv[1]))
        ShowUsage();

    bool usingLogPr = slm.isUseLogPr();

    #define EffectivePr(a)  (usingLogPr ? ((a) / log(2.0f)) : -log2((a)))
    #define OriginalPr(b)   (usingLogPr ? ((b) * log(2.0f)) : exp2(-(b)))
    #define EffectiveBow(a) (usingLogPr ? exp(-(a)) : (a))
    #define OriginalBow(b)  (usingLogPr ? -log((b)) : (b))

    printf("\nfirst pass..."); fflush(stdout);
    for (int lvl = 0; lvl <= slm.getN(); ++lvl) {
        CSIMSlmWithIteration::TLevelIterator it;
        slm.beginLevelIteration(lvl, it);
        for (; !slm.isEnd(it); slm.next(it)) {
            CSIMSlm::TLeaf* pl = slm.getNodePtr(it);
            real_pr = pl->pr;
            eff_pr = EffectivePr(real_pr);
            if (pr_eff.find(eff_pr) == pr_eff.end()) {
                pr_eff[eff_pr] = real_pr;
            } else { // precision error cause non 1:1 mapping
                pr_eff[eff_pr] = OriginalPr(eff_pr);
            }
            ++(pr_values[eff_pr]);
            if (lvl < slm.getN()) {
                real_bow = ((CSIMSlm::TNode*)pl)->bow;
                eff_bow = EffectiveBow(real_bow);
                if (bow_eff.find(eff_bow) == bow_eff.end()) {
                    bow_eff[eff_bow] = real_bow;
                } else { // two values map to same distance value due to precision error
                    bow_eff[eff_bow] = OriginalBow(eff_bow);
                }
                ++(bow_values[eff_bow]);
            }
        }
    }

    // Following pr value should not be grouped, or as milestone values.
    static float msprs[] = {
        0.9, 0.8, 0.7, 0.6,
        1.0 / 2, 1.0 / 4, 1.0 / 8, 1.0 / 16, 1.0 / 32, 1.0 / 64, 1.0 / 128,
        1.0 / 256, 1.0 / 512, 1.0 / 1024, 1.0 / 2048, 1.0 / 4096, 1.0 / 8192,
        1.0 / 16384, 1.0 / 32768, 1.0 / 65536
    };

    for (unsigned i = 0, sz = sizeof(msprs) / sizeof(float); i < sz; ++i) {
        float real_pr = usingLogPr ? -log(msprs[i]) : msprs[i];
        float eff_pr = EffectivePr(real_pr);
        if (pr_eff.find(eff_pr) == pr_eff.end()) {
            pr_eff[eff_pr] = real_pr;
        } else { // precision error cause non 1:1 mapping
            pr_eff[eff_pr] = OriginalPr(eff_pr);
        }
        pr_values[eff_pr] = 0;
    }

    // Following bow value should not be grouped, or as milestone values.
    static float msbows[] = {
        1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2,
        0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001,
        0.00005, 0.00001, 0.000005, 0.000001, 0.0000005, 0.0000001
    };

    for (unsigned i = 0, sz = sizeof(msbows) / sizeof(float); i < sz; ++i) {
        float real_bow = usingLogPr ? -log(msbows[i]) : msbows[i];
        float eff_bow = EffectiveBow(real_bow);
        if (bow_eff.find(eff_bow) == bow_eff.end()) {
            bow_eff[eff_bow] = real_bow;
        } else { // two values map to same distance value due to precision error
            bow_eff[eff_bow] = OriginalBow(eff_bow);
        }
        bow_values[eff_bow] = 0;
    }

    printf("\nCompressing pr values..."); fflush(stdout);
    vc(pr_eff, pr_values, pr_map, pr_table, (1 << CThreadSlm::BITS_PR));
    pr_values.clear();
    itte = pr_table.end();
    for (itt = pr_table.begin(); itt != itte; ++itt) {
        *itt = OriginalPr(*itt);
        assert(usingLogPr || (*itt > 0.0 && *itt < 1.0));
        assert(!usingLogPr || *itt > 0.0);
    }
    printf("%lu float values ==> %lu values", pr_eff.size(), pr_table.size());

    printf("\nCompressing bow values..."); fflush(stdout);
    vc(bow_eff, bow_values, bow_map, bow_table, (1 << CThreadSlm::BITS_BOW));
    bow_values.clear();
    itte = bow_table.end();
    for (itt = bow_table.begin(); itt != itte; ++itt)
        *itt = OriginalBow(*itt);
    printf("%lu float values ==> %lu values", bow_eff.size(), bow_table.size());


    printf("\nThreading the new model..."); fflush(stdout);
    for (int lvl = 0; lvl < slm.getN(); ++lvl) {
        levels[lvl] = new CThreadSlm::TNode[slm.getLevelSize(lvl)];

        CSIMSlmWithIteration::TLevelIterator it;
        slm.beginLevelIteration(lvl, it);
        for (; !slm.isEnd(it); slm.next(it)) {
            slm.getIdString(it, history);
            if (history.size() == 0) {
                slm.findBackOffState(lvl, NULL, bol, bon);
            } else {
                slm.findBackOffState(lvl, &history[0], bol, bon);
            }

            CSIMSlm::TNode* pn = (CSIMSlm::TNode*)slm.getNodePtr(it);
            CThreadSlm::TNode& nn = levels[lvl][it.m_history.back()];

            std::map<float, int>::iterator prit = pr_map.find(pn->pr);
            if (prit == pr_map.end()) { // This would be cause by precision error
                float val = EffectivePr(pn->pr);
                val = OriginalPr(val);
                prit = pr_map.find(val);
                assert(prit != pr_map.end());
            }
            int idx_pr = prit->second;
            nn.set_pr(idx_pr);

            nn.set_wid(pn->id);
            nn.set_bon(bon);
            nn.set_bol(bol);

            std::map<float, int>::iterator bowit = bow_map.find(pn->bow);
            if (bowit == bow_map.end()) { // precision error
                double val = EffectiveBow(pn->bow);
                val = OriginalBow(val);
                bowit = bow_map.find(val);
                assert(bowit != bow_map.end());
            }
            int idx_bow = bowit->second;
            nn.set_bow(idx_bow);

            nn.set_ch(pn->child);

            assert(usingLogPr ||
                   (pr_table[idx_pr] > 0.0 && pr_table[idx_pr] < 1.0));
            assert(!usingLogPr || pr_table[idx_pr] > 0.0);
        }
        CSIMSlm::TNode* pn = (CSIMSlm::TNode*)slm.getNodePtr(it);
        CThreadSlm::TNode& nn = levels[lvl][it.m_history.back()];
        nn.set_ch(pn->child);
    }
    ;


    lastLevel = new CThreadSlm::TLeaf [slm.getLevelSize(slm.getN())];
    CSIMSlmWithIteration::TLevelIterator it;
    slm.beginLevelIteration(slm.getN(), it);
    for (int lvl = slm.getN(); !slm.isEnd(it); slm.next(it)) {
        CSIMSlm::TLeaf* pn = slm.getNodePtr(it);
        slm.getIdString(it, history);
        slm.findBackOffState(lvl, &history[0], bol, bon);

        CThreadSlm::TLeaf& nn = lastLevel[it.m_history.back()];

        std::map<float, int>::iterator prit = pr_map.find(pn->pr);
        if (prit == pr_map.end()) { // This would be cause by precision error
            float val = EffectivePr(pn->pr);
            val = OriginalPr(val);
            prit = pr_map.find(val);
            assert(prit != pr_map.end());
        }
        int idx_pr = prit->second;
        nn.set_pr(idx_pr);

        nn.set_wid(pn->id);
        nn.set_bon(bon);
        nn.set_bol(bol);
    }


    printf("\nWriting out..."); fflush(stdout);

    float dummy = 0.0;
    fp = fopen(argv[2], "wb");
    int N = slm.getN();
    fwrite(&N, sizeof(int), 1, fp);
    unsigned ulp = slm.isUseLogPr();
    fwrite(&ulp, sizeof(unsigned), 1, fp);

    for (int lvl = 0; lvl <= N; ++lvl) {
        int len = slm.getLevelSize(lvl);
        fwrite(&len, sizeof(int), 1, fp);
    }
    fwrite(&pr_table[0], sizeof(float), pr_table.size(), fp);
    for (int i = pr_table.size(), sz = (1 << CThreadSlm::BITS_PR); i < sz; ++i)
        fwrite(&dummy, sizeof(float), 1, fp);

    fwrite(&bow_table[0], sizeof(float), bow_table.size(), fp);
    for (int i = bow_table.size(), sz = (1 << CThreadSlm::BITS_BOW);
         i < sz;
         ++i)
        fwrite(&dummy, sizeof(float), 1, fp);

    for (int lvl = 0; lvl < N; ++lvl)
        fwrite(levels[lvl], sizeof(CThreadSlm::TNode), slm.getLevelSize(
                   lvl), fp);
    fwrite(lastLevel, sizeof(CThreadSlm::TLeaf), slm.getLevelSize(N), fp);
    fclose(fp);

    printf("done!\n"); fflush(stdout);

    delete [] lastLevel;
    for (int lvl = 0; lvl < N; ++lvl)
        delete [] levels[lvl];

    bow_values.clear();
    bow_map.clear();
    bow_table.clear();

    pr_values.clear();
    pr_map.clear();
    pr_table.clear();

    slm.Free();


    return 0;
}

// -*- indent-tabs-mode: nil -*- vim:et:ts=4