Rosetta Code

Best shuffle: Difference between revisions

Page Discussion

Best shuffle (view source)

Revision as of 20:12, 22 April 2011

106 bytes added ,  13 years ago
Improved D version
(Removed some casts from C version)
(Improved D version)
Line 305:
 
pure nothrow void bestShuffle(in char[] txt, char[] result) {
enum intsize_t NCHAR = cast(intsize_t)char.max + 1;
enum intsize_t MAX_VLA_SIZE = 1024;
const intsize_t len = txt.length;
if (len == 0)
return;
Line 317:
 
// how many of each character?
intsize_t[NCHAR] counts;
intsize_t fmax = 0;
foreach (char c; txt) {
counts[c]++;
Line 325:
}
assert(fmax > 0 && fmax <= len);
 
// how long can our cyclic groups be?▼
const int grp = 1 + (len - 1) / fmax;▼
 
// how many of them are full length?▼
const int lng = 1 + (len - 1) % fmax;▼
 
// all character positions, grouped by character
intsize_t* ptr1 = null;
if ((len * intsize_t.sizeof) < MAX_VLA_SIZE)
ptr1 = cast(intsize_t*)alloca(len * intsize_t.sizeof);
intsize_t[] ndx1 = (ptr1 == null) ? new intsize_t[len] : ptr1[0 .. len];
for (intsize_t ch = 0, i = 0; ch < NCHAR; ch++)
if (counts[ch])
foreach (size_t j;, 0char ..c; lentxt)
if (chc == txt[j]ch) {
ndx1[i] = j;
i++;
Line 346 ⟶ 340:
 
// regroup them for cycles
intsize_t* ptr2 = null;
if ((len * intsize_t.sizeof) < MAX_VLA_SIZE)
ptr2 = cast(intsize_t*)alloca(len * intsize_t.sizeof);
intsize_t[] ndx2 = (ptr2 == null) ? new intsize_t[len] : ptr2[0 .. len];
for (intsize_t i = 0, n = 0, m = 0; i < len; i++) {
ndx2[i] = ndx1[n];
n += fmax;
Line 358 ⟶ 352:
}
}
 
▲ // how long can our cyclic groups be?
▲ const intsize_t grp = 1 + (len - 1) / fmax;
 
▲ // how many of them are full length?
▲ const intsize_t lng = 1 + (len - 1) % fmax;
 
// rotate each group
for (intsize_t i = 0, j = 0; i < fmax; i++) {
intconst size_t first = ndx2[j];
intconst size_t glen = grp - (i < lng ? 0 : 1);
foreach (size_t k; 1 .. glen)
ndx1[j + k - 1] = ndx2[j + k];
ndx1[j + glen - 1] = first;
Line 370:
 
// result is original permuted according to our cyclic groups
foreach (size_t i; 0 .. len)
result[ndx2[i]] = txt[ndx1[i]];
}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/166862"