<commit_before>/* global utility: false, _: false */
'use strict';
if (!window.utility) {
  throw Error('dbtester requires utility to be defined in global scope first');
}

function isSubsetOf(item1,item2){ return (item1&item2)==item1; }

function setExclude(item1,item2){ return setIntersect(item1,~item2); }

function isProperSubsetOf(item1,item2){ return item1!=item2 && isSubsetOf(item1,item2);}

function setUnion(item1,item2){ return item1|item2; }

function setIntersect(item1,item2){ return item1&item2; }

function equivalent(elem1, elem2, closure){
  return isSubsetOf(elem1,closure[b]) && isSubsetOf(elem2,closure[a]);
}


function PII(elem1, elem2){
  this.left = elem1;
  this.right = elem2;
}


function getClosure(fd){
  var varNum=0;
  for(var i = 0; i < fd.size(); i++){
    var item = fd[i];
    varNum=max(varNum,highestBit(item.left)+1);
    varNum=max(varNum,highestBit(item.right)+1);
  }
  var n=1<<varNum;
  var g;
  for(var i=0;i<n;i++)g[i]=i;
  for(var i = 0; i < fd.size(); i++){
    var item = fd[i];
    g[item.left]=setUnion(g[item.left],item.right);
  }
  while(1){
    var update=0;
    for(var k=0;k<n;k++)
      for(var i=0;i<n;i++)
        for(var j=0;j<n;j++)
          if(CON(i,k) && CON(k,j) && !CON(i,j)){
            g[i] = setUnion(g[i],j);
            update=1;
          }
    if(!update)break;
  }
  return g;
}

function allSubsets(item){
  //  return vector of all subsets of a except empty set
  var t,res;
  while(item){
    t.push_back(item - ( item & ( item-1 ) ));
    item &= item-1;
  }
  var n=t.size();
  for(var i=1;i<(1<<n);i++){
    var k=0;
    for(var j=0;j<n;j++)
      if(i & (1<<j))
        k|=t[j];
    res.push_back(k);
  }
  sort(res.begin(),res.end(),bitNumCmp);
  return res;
}

function removeEmptyFD(fd){
  for(var j=0;j<fd.size();)
    if(fd[j].right==0)
      fd.erase(fd.begin()+j);
    else
      j++;
}
function bitNumCmp(a, b){
  var na=0,nb=0;
  while(a){
    a &= a-1;
    na++;
  }
  while(b){
    b &= b-1;
    nb++;
  }
  return na < nb;
}



var bernstein = (function () {
  var bernstein = {};
  bernstein.generateBernsteinAlgoResults = function (attrs, fds) {
    var attrSet = utility.removeDuplicates(attrs);
    var fdSet = utility.removeDuplicates(fds);
    var tables = [];
    var fd=fds;
    var closure=getClosure(fd);

    function removeExtraneousAttrs() {
      // TODO
      
      // step 1, for each A->B, find the smallest subset of A
      // such that A'->B is within the closure
      for(var i=0;i<fd.size();i++){
          var l=allSubsets(fd[i].left);
          for(var j=0;j<l.size();j++)
          if(isSubsetOf(fd[i].right,closure[l[j]])){
             fd[i].left=l[j];
             break;
            }
          }   


    }

    function findCovering() {
      // TODO
      for(var i=0;i<fd.size();i++){
          for(var j=0;(1<<j)<=fd[i].right;j++){
              if((1<<j) & fd[i].right){
                fd[i].right ^= (1<<j);
                var p = PII(fd[i].left,1<<j);
                if(!isMemberOf(p,fd))
                   fd[i].right |= (1<<j);
                }
              }
          }
          removeEmptyFD(fd);
    }

    function partition() {
      // TODO
      sort(fd.begin(),fd.end());
      for(var i=1;i<fd.size();){
          if(fd[i].left == fd[i-1].left){
             fd[i-1].right |= fd[i].right;
             fd.erase(fd.begin()+i);
            }else{
                 i++;
            }
         }
    }

    function mergeEquivalentKeys() {
      // TODO
      var J;
      var H;
      for(var i=0;i<fd.size();i++)
         for(var j=i+1;j<fd.size();j++)
         if(equivalent(fd[i].left,fd[j].left,closure)){
           J.push_back(PII(fd[i].left,fd[j].left));
           J.push_back(PII(fd[j].left,fd[i].left));
           }
         for(var i=0;i<fd.size();i++){
             var id=-1;
             for(var j=0;j<H.size();j++){
                if(equivalent(H[j][0].left,fd[i].left,closure)){
                   id=j;
                   break;
                  }
                }

          }
         for(var i=0;i<H.size();i++){
             var t=0;
             for(var j=0;j<H[i].size();j++)
                t|=H[i][j].left;
                for(var j=0;j<H[i].size();j++)
                    H[i][j].right=setExclude(H[i][j].right,t);
                    removeEmptyFD(H[i]);
            }

    }

    function eliminateTransitiveDependencies() {
      // TODO
      var HJ;
      for(var i=0;i<H.size();i++) HJ.insert(HJ.end(),H[i].begin(),H[i].end());
          HJ.insert(HJ.end(),J.begin(),J.end());
          var ct=0;
          for(var i=0;i<H.size();i++){
             for(var j=0;j<H[i].size();j++){
                 assert(HJ[ct].left==H[i][j].left);
                 assert(HJ[ct].right==H[i][j].right);
                 var rhs=H[i][j].right;
                 for(var k=1;k<=rhs;k<<=1){
                    if(rhs & k){
                      HJ[ct].right ^= k;
                      if(isMemberOf(PII(H[i][j].left,k),HJ)){
                         H[i][j].right ^= k;
                        }
                      else{
                          HJ[ct].right |= k;
                          }
                                }
                    }
                   ct++;
                }
             }
    }

    function generateTables() {
      // TODO
      for(var i=0;i<H.size();i++)
      for(var j=0;j<H[i].size();j++)
      for(var k=0;k<J.size();)
        if(J[k].left == H[i][j].left){
          H[i].push_back(J[k]);
          J.erase(J.begin()+k);
        }else{
          k++;
        }
        
      for(var i=0;i<H.size();i++) removeEmptyFD(H[i]);
      }



      //push into tables
      for(var i=0;i<H.size();i++){
    
          var attr=0;
          for(var j=0;j<H[i].size();j++){
             attr |= H[i][j].left;
             attr |= H[i][j].right;
          }
          //cout<<"Attributes: "<<set2str(attr)<<endl;
          var ckeys = getCandidateKeys(attr,closure);
          //cout<<"Candidate Keys: ";
          for(var i=0;i<ckeys.size();i++){
          if(i)cout<<", ";
             cout<<set2str(ckeys[i]);
        }
        cout<<endl;
        tables[i]=attr;
      }

    function addBackLostAttrs() {
      // TODO
    }

    removeExtraneousAttrs();
    findCovering();
    partition();
    mergeEquivalentKeys();
    eliminateTransitiveDependencies();
    generateTables();
    addBackLostAttrs();

    return tables;
  };
}());
<commit_msg>add LTK<commit_after>/* global utility: false, _: false */
'use strict';
if (!window.utility) {
  throw Error('dbtester requires utility to be defined in global scope first');
}

function isSubsetOf(item1,item2){ return (item1&item2)==item1; }

function setExclude(item1,item2){ return setIntersect(item1,~item2); }

function isProperSubsetOf(item1,item2){ return item1!=item2 && isSubsetOf(item1,item2);}

function setUnion(item1,item2){ return item1|item2; }

function setIntersect(item1,item2){ return item1&item2; }

function equivalent(elem1, elem2, closure){
  return isSubsetOf(elem1,closure[b]) && isSubsetOf(elem2,closure[a]);
}

function isMemberOf(p, fd){
  return isSubsetOf(p.right,getClosure(p.left,fd));
}



function PII(elem1, elem2){
  this.left = elem1;
  this.right = elem2;
}


function getClosure(fd){
  var varNum=0;
  for(var i = 0; i < fd.size(); i++){
    var item = fd[i];
    varNum=max(varNum,highestBit(item.left)+1);
    varNum=max(varNum,highestBit(item.right)+1);
  }
  var n=1<<varNum;
  var g;
  for(var i=0;i<n;i++)g[i]=i;
  for(var i = 0; i < fd.size(); i++){
    var item = fd[i];
    g[item.left]=setUnion(g[item.left],item.right);
  }
  while(1){
    var update=0;
    for(var k=0;k<n;k++)
      for(var i=0;i<n;i++)
        for(var j=0;j<n;j++)
          if(CON(i,k) && CON(k,j) && !CON(i,j)){
            g[i] = setUnion(g[i],j);
            update=1;
          }
    if(!update)break;
  }
  return g;
}

function allSubsets(item){
  //  return vector of all subsets of a except empty set
  var t,res;
  while(item){
    t.push_back(item - ( item & ( item-1 ) ));
    item &= item-1;
  }
  var n=t.size();
  for(var i=1;i<(1<<n);i++){
    var k=0;
    for(var j=0;j<n;j++)
      if(i & (1<<j))
        k|=t[j];
    res.push_back(k);
  }
  sort(res.begin(),res.end(),bitNumCmp);
  return res;
}

function removeEmptyFD(fd){
  for(var j=0;j<fd.size();)
    if(fd[j].right==0)
      fd.erase(fd.begin()+j);
    else
      j++;
}
function bitNumCmp(a, b){
  var na=0,nb=0;
  while(a){
    a &= a-1;
    na++;
  }
  while(b){
    b &= b-1;
    nb++;
  }
  return na < nb;
}


function Bernstein(_fd){
  var fd=_fd;
  var closure=getClosure(fd);
  // step 1, for each A->B, find the smallest subset of A
  // such that A'->B is within the closure
  for(var i=0;i<fd.size();i++){
    var l=allSubsets(fd[i].left);
    for(var j=0;j<l.size();j++)
      if(isSubsetOf(fd[i].right,closure[l[j]])){
        fd[i].left=l[j];
        break;
      }
  }
  //prvarFDs(fd,"Bernstein step 1");
  // step 2, for each A->B, find the minimal subset of B such that
  // replacing it with A->B' doesn't change closure
  for(var i=0;i<fd.size();i++){
    for(var j=0;(1<<j)<=fd[i].right;j++){
      if((1<<j) & fd[i].right){
        fd[i].right ^= (1<<j);
        var p = PII(fd[i].left,1<<j);
        if(!isMemberOf(p,fd))
          fd[i].right |= (1<<j);
      }
    }
  }
  removeEmptyFD(fd);
  //prvarf("----------\n");
  //prvarFDs(fd,"Bernstein step 2");
  // step 3, group fds with the same lhs
  sort(fd.begin(),fd.end());
  for(var i=1;i<fd.size();){
    if(fd[i].left == fd[i-1].left){
      fd[i-1].right |= fd[i].right;
      fd.erase(fd.begin()+i);
    }else{
      i++;
    }
  }
  //prvarf("----------\n");
  //prvarFDs(fd,"Bernstein step 3");
  // set 4, find equivalent lhs, group them together
  var J;
  var H;
  for(var i=0;i<fd.size();i++)
    for(var j=i+1;j<fd.size();j++)
      if(equivalent(fd[i].left,fd[j].left,closure)){
        J.push_back(PII(fd[i].left,fd[j].left));
        J.push_back(PII(fd[j].left,fd[i].left));
      }
  for(var i=0;i<fd.size();i++){
    var id=-1;
    for(var j=0;j<H.size();j++){
      if(equivalent(H[j][0].left,fd[i].left,closure)){
        id=j;
        break;
      }
    }
    if(id==-1){
      //bug
  //    H.push_back(var(1,fd[i]));
    }else{
      //bug
  //    H[id].push_back(fd[i]);
    }
  }
  for(var i=0;i<H.size();i++){
    var t=0;
    for(var j=0;j<H[i].size();j++)
      t|=H[i][j].left;
    for(var j=0;j<H[i].size();j++)
      H[i][j].right=setExclude(H[i][j].right,t);
    removeEmptyFD(H[i]);
  }
  //prvarf("----------\n");
  //prvarf("Bernstein step 4\n");
  //prvarFDs(J,"J");
  for(var i=0;i<H.size();i++){
    var name;
    //sprvarf(name,"H%d",i+1);
    //prvarFDs(H[i],name);
  }
  // step 5, for each H[i], eliminate rhs attributes as much as possible without changing
  // closure of H union J
  var HJ;
  for(var i=0;i<H.size();i++) HJ.insert(HJ.end(),H[i].begin(),H[i].end());
  HJ.insert(HJ.end(),J.begin(),J.end());
  var ct=0;
  for(var i=0;i<H.size();i++){
    for(var j=0;j<H[i].size();j++){
      assert(HJ[ct].left==H[i][j].left);
      assert(HJ[ct].right==H[i][j].right);
      var rhs=H[i][j].right;
      for(var k=1;k<=rhs;k<<=1){
        if(rhs & k){
          HJ[ct].right ^= k;
          if(isMemberOf(PII(H[i][j].left,k),HJ)){
            H[i][j].right ^= k;
          }else{
            HJ[ct].right |= k;
          }
        }
      }
      ct++;
    }
  }
  //prvarf("----------\n");
  //prvarf("Bernstein step 5\n");
  //prvarFDs(J,"J");
  for(var i=0;i<H.size();i++){
    var name;
    //sprvarf(name,"H%d",i+1);
    //prvarFDs(H[i],name);
  }
  //step 6 
  // Add corresponding FD in J varo H[i]
  for(var i=0;i<H.size();i++)
    for(var j=0;j<H[i].size();j++)
      for(var k=0;k<J.size();)
        if(J[k].left == H[i][j].left){
          H[i].push_back(J[k]);
          J.erase(J.begin()+k);
        }else{
          k++;
        }
        
  for(var i=0;i<H.size();i++) removeEmptyFD(H[i]);
  //prvarf("----------\n");
  //prvarf("Bernstein step 6: %d tables\n",H.size());
  var tables;
  for(var i=0;i<H.size();i++){
    //prvarf("table %d\n",i+1);
    var attr=0;
    for(var j=0;j<H[i].size();j++){
      attr |= H[i][j].left;
      attr |= H[i][j].right;
    }
    cout<<"Attributes: "<<set2str(attr)<<endl;
    var ckeys = getCandidateKeys(attr,closure);
    cout<<"Candidate Keys: ";
    for(var i=0;i<ckeys.size();i++){
      if(i)cout<<", ";
      cout<<set2str(ckeys[i]);
    }
    cout<<endl;
    tables.push_back(attr);
  }
}


// var bernstein = (function () {
//   var bernstein = {};
//   bernstein.generateBernsteinAlgoResults = function (attrs, fds) {
//     var attrSet = utility.removeDuplicates(attrs);
//     var fdSet = utility.removeDuplicates(fds);
//     var tables = [];
//     var fd=fds;
//     var closure=getClosure(fd);

//     function removeExtraneousAttrs() {
//       // TODO
      
//       // step 1, for each A->B, find the smallest subset of A
//       // such that A'->B is within the closure
//       for(var i=0;i<fd.size();i++){
//           var l=allSubsets(fd[i].left);
//           for(var j=0;j<l.size();j++)
//           if(isSubsetOf(fd[i].right,closure[l[j]])){
//              fd[i].left=l[j];
//              break;
//             }
//           }   


//     }

//     function findCovering() {
//       // TODO
//       for(var i=0;i<fd.size();i++){
//           for(var j=0;(1<<j)<=fd[i].right;j++){
//               if((1<<j) & fd[i].right){
//                 fd[i].right ^= (1<<j);
//                 var p = PII(fd[i].left,1<<j);
//                 if(!isMemberOf(p,fd))
//                    fd[i].right |= (1<<j);
//                 }
//               }
//           }
//           removeEmptyFD(fd);
//     }

//     function partition() {
//       // TODO
//       sort(fd.begin(),fd.end());
//       for(var i=1;i<fd.size();){
//           if(fd[i].left == fd[i-1].left){
//              fd[i-1].right |= fd[i].right;
//              fd.erase(fd.begin()+i);
//             }else{
//                  i++;
//             }
//          }
//     }

//     function mergeEquivalentKeys() {
//       // TODO
//       var J;
//       var H;
//       for(var i=0;i<fd.size();i++)
//          for(var j=i+1;j<fd.size();j++)
//          if(equivalent(fd[i].left,fd[j].left,closure)){
//            J.push_back(PII(fd[i].left,fd[j].left));
//            J.push_back(PII(fd[j].left,fd[i].left));
//            }
//          for(var i=0;i<fd.size();i++){
//              var id=-1;
//              for(var j=0;j<H.size();j++){
//                 if(equivalent(H[j][0].left,fd[i].left,closure)){
//                    id=j;
//                    break;
//                   }
//                 }

//           }
//          for(var i=0;i<H.size();i++){
//              var t=0;
//              for(var j=0;j<H[i].size();j++)
//                 t|=H[i][j].left;
//                 for(var j=0;j<H[i].size();j++)
//                     H[i][j].right=setExclude(H[i][j].right,t);
//                     removeEmptyFD(H[i]);
//             }

//     }

//     function eliminateTransitiveDependencies() {
//       // TODO
//       var HJ;
//       for(var i=0;i<H.size();i++) HJ.insert(HJ.end(),H[i].begin(),H[i].end());
//           HJ.insert(HJ.end(),J.begin(),J.end());
//           var ct=0;
//           for(var i=0;i<H.size();i++){
//              for(var j=0;j<H[i].size();j++){
//                  assert(HJ[ct].left==H[i][j].left);
//                  assert(HJ[ct].right==H[i][j].right);
//                  var rhs=H[i][j].right;
//                  for(var k=1;k<=rhs;k<<=1){
//                     if(rhs & k){
//                       HJ[ct].right ^= k;
//                       if(isMemberOf(PII(H[i][j].left,k),HJ)){
//                          H[i][j].right ^= k;
//                         }
//                       else{
//                           HJ[ct].right |= k;
//                           }
//                                 }
//                     }
//                    ct++;
//                 }
//              }
//     }

//     function generateTables() {
//       // TODO
//       for(var i=0;i<H.size();i++)
//       for(var j=0;j<H[i].size();j++)
//       for(var k=0;k<J.size();)
//         if(J[k].left == H[i][j].left){
//           H[i].push_back(J[k]);
//           J.erase(J.begin()+k);
//         }else{
//           k++;
//         }
        
//       for(var i=0;i<H.size();i++) removeEmptyFD(H[i]);
//       }



//       //push into tables
//       for(var i=0;i<H.size();i++){
    
//           var attr=0;
//           for(var j=0;j<H[i].size();j++){
//              attr |= H[i][j].left;
//              attr |= H[i][j].right;
//           }
//           //cout<<"Attributes: "<<set2str(attr)<<endl;
//           var ckeys = getCandidateKeys(attr,closure);
//           //cout<<"Candidate Keys: ";
//           for(var i=0;i<ckeys.size();i++){
//           if(i)cout<<", ";
//              cout<<set2str(ckeys[i]);
//         }
//         cout<<endl;
//         tables[i]=attr;
//       }

//     function addBackLostAttrs() {
//       // TODO
//     }

//     removeExtraneousAttrs();
//     findCovering();
//     partition();
//     mergeEquivalentKeys();
//     eliminateTransitiveDependencies();
//     generateTables();
//     addBackLostAttrs();

//     return tables;
//   };
// }());

{'fraction_non_alphanumeric': 0.2219666474985624, 'fraction_numerical': 0.014318573893041978, 'mean_word_length': 1.7297127609480458, 'pattern_counts': {'":': 0, '<': 184, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4530700', 'n_tokens_mistral': 6814, 'n_tokens_neox': 6682, 'n_words': 1009}