private static int[][] regroupHistogram(int[][] matrix,int[] groups){
  long oldEntries=0;
  for (int i=0; i < matrix.length; i++) {
    oldEntries+=matrix[i].length - 1;
  }
  long newEntries=0;
  for (int ni=0; ni < groups.length; ni++) {
    newEntries+=groups[ni];
  }
  if (newEntries > oldEntries) {
    int newlen=groups.length;
    long ok=oldEntries;
    for (int ni=0; ni < groups.length; ni++) {
      if (ok < groups[ni]) {
        int[] newGroups=new int[ni + 1];
        System.arraycopy(groups,0,newGroups,0,ni + 1);
        groups=newGroups;
        groups[ni]=(int)ok;
        ok=0;
        break;
      }
      ok-=groups[ni];
    }
  }
 else {
    long excess=oldEntries - newEntries;
    int[] newGroups=new int[groups.length + 1];
    System.arraycopy(groups,0,newGroups,0,groups.length);
    newGroups[groups.length]=(int)excess;
    groups=newGroups;
  }
  int[][] newMatrix=new int[groups.length][];
  int i=0;
  int jMin=1;
  int jMax=matrix[i].length;
  for (int ni=0; ni < groups.length; ni++) {
    int groupLength=groups[ni];
    int[] group=new int[1 + groupLength];
    long groupWeight=0;
    newMatrix[ni]=group;
    int njFill=1;
    while (njFill < group.length) {
      int len=group.length - njFill;
      while (jMin == jMax) {
        jMin=1;
        jMax=matrix[++i].length;
      }
      if (len > jMax - jMin)       len=jMax - jMin;
      groupWeight+=(long)matrix[i][0] * len;
      System.arraycopy(matrix[i],jMax - len,group,njFill,len);
      jMax-=len;
      njFill+=len;
    }
    Arrays.sort(group,1,group.length);
    group[0]=(int)((groupWeight + groupLength / 2) / groupLength);
  }
  assert (jMin == jMax);
  assert (i == matrix.length - 1);
  return newMatrix;
}

private static int [ ] [ ] regroupHistogram ( int [ ] [ ] matrix , int [ ] groups ) { long oldEntries = 0 ; for ( int i = 0 ; i < matrix . length ; i ++ ) { oldEntries += matrix [ i ] . length - 1 ; } long newEntries = 0 ; for ( int ni = 0 ; ni < groups . length ; ni ++ ) { newEntries += groups [ ni ] ; } if ( newEntries > oldEntries ) { int newlen = groups . length ; long ok = oldEntries ; for ( int ni = 0 ; ni < groups . length ; ni ++ ) { if ( ok < groups [ ni ] ) { int [ ] newGroups = new int [ ni + 1 ] ; System . arraycopy ( groups , 0 , newGroups , 0 , ni + 1 ) ; groups = newGroups ; groups [ ni ] = ( int ) ok ; ok = 0 ; break ; } ok -= groups [ ni ] ; } } else { long excess = oldEntries - newEntries ; int [ ] newGroups = new int [ groups . length + 1 ] ; System . arraycopy ( groups , 0 , newGroups , 0 , groups . length ) ; newGroups [ groups . length ] = ( int ) excess ; groups = newGroups ; } int [ ] [ ] newMatrix = new int [ groups . length ] [ ] ; int i = 0 ; int jMin = 1 ; int jMax = matrix [ i ] . length ; for ( int ni = 0 ; ni < groups . length ; ni ++ ) { int groupLength = groups [ ni ] ; int [ ] group = new int [ 1 + groupLength ] ; long groupWeight = 0 ; newMatrix [ ni ] = group ; int njFill = 1 ; while ( njFill < group . length ) { int len = group . length - njFill ; while ( jMin == jMax ) { jMin = 1 ; jMax = matrix [ ++ i ] . length ; } if ( len > jMax - jMin ) len = jMax - jMin ; groupWeight += ( long ) matrix [ i ] [ 0 ] * len ; System . arraycopy ( matrix [ i ] , jMax - len , group , njFill , len ) ; jMax -= len ; njFill += len ; } Arrays . sort ( group , 1 , group . length ) ; group [ 0 ] = ( int ) ( ( groupWeight + groupLength / 2 ) / groupLength ) ; } assert ( jMin == jMax ) ; assert ( i == matrix . length - 1 ) ; return newMatrix ; }
regroup the histogram , so that it becomes an approximate histogram whose rows are of the given lengths . if matrix rows must be split , the latter parts ( larger values ) are placed earlier in the new matrix . if matrix rows are joined , they are resorted into ascending order . in the new histogram , the counts are averaged over row entries .
