blob: c062ea5b48061050543e2ab975b2ba9de2040ba0 [file] [log] [blame]
// Copyright 2016 Google Inc. All rights reserved
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// http://ci.nii.ac.jp/naid/110006613087
#include "lcp_msort.h"
#include <stdlib.h>
#include "strutil.h"
#define DO_SORT_AND_UNIQ_AT_ONCE
namespace {
struct AnnotatedString {
const unsigned char* s;
int l;
};
inline int LcpCompare(const unsigned char* s1,
const unsigned char* s2,
int b,
int& i) {
for (i = b; s1[i] || s2[i]; i++) {
unsigned char c1 = s1[i];
unsigned char c2 = s2[i];
if (c1 < c2) {
return -1;
}
else if (c1 > c2) {
return 1;
}
}
return 0;
}
#ifdef DO_SORT_AND_UNIQ_AT_ONCE
int StringMergeSortAndUniq(const vector<const unsigned char*>& data,
int begin,
int end,
AnnotatedString* work,
AnnotatedString* out) {
if (begin + 1 == end) {
out[begin] = AnnotatedString{ data[begin], 0 };
return 1;
}
int mid = (begin + end) / 2;
int s1_len = StringMergeSortAndUniq(data, begin, mid, work, out);
int s2_len = StringMergeSortAndUniq(data, mid, end, work, out);
memcpy(work, out + begin, s1_len * sizeof(AnnotatedString));
AnnotatedString* s1 = work;
AnnotatedString* s2 = out + mid;
int i = 0, j = 0, k = 0;
AnnotatedString* d = out + begin;
for (; i < s1_len && j < s2_len; k++) {
if (s1[i].l > s2[j].l) {
d[k] = s1[i];
i++;
} else if (s1[i].l < s2[j].l) {
d[k] = s2[j];
j++;
} else {
int m;
int r = LcpCompare(s1[i].s, s2[j].s, s1[i].l, m);
if (r < 0) {
d[k] = s1[i];
i++;
s2[j].l = m;
} else if (r > 0) {
d[k] = s2[j];
j++;
s1[i].l = m;
} else {
// Discard a unique string.
d[k] = s1[i];
i++;
j++;
}
}
}
if (i < s1_len) {
memcpy(&d[k], &s1[i], (s1_len - i) * sizeof(AnnotatedString));
k += s1_len - i;
}
else if (j < s2_len) {
memcpy(&d[k], &s2[j], (s2_len - j) * sizeof(AnnotatedString));
k += s2_len - j;
}
return k;
}
#else
void StringMergeSort(const vector<const unsigned char*>& data,
int begin,
int end,
AnnotatedString* work,
AnnotatedString* out) {
if (begin + 1 == end) {
out[begin] = AnnotatedString{ data[begin], 0 };
return;
}
int mid = (begin + end) / 2;
StringMergeSort(data, begin, mid, work, out);
StringMergeSort(data, mid, end, work, out);
memcpy(work, out + begin, (mid - begin) * sizeof(AnnotatedString));
AnnotatedString* s1 = work;
int s1_len = mid - begin;
AnnotatedString* s2 = out + mid;
int s2_len = end - mid;
int i = 0, j = 0, k = 0;
AnnotatedString* d = out + begin;
for (; i < s1_len && j < s2_len; k++) {
if (s1[i].l > s2[j].l) {
d[k] = s1[i];
i++;
} else if (s1[i].l < s2[j].l) {
d[k] = s2[j];
j++;
} else {
int m;
int r = LcpCompare(s1[i].s, s2[j].s, s1[i].l, m);
if (r < 0) {
d[k] = s1[i];
i++;
s2[j].l = m;
} else {
d[k] = s2[j];
j++;
s1[i].l = m;
}
}
}
if (i < s1_len)
memcpy(&d[k], &s1[i], (s1_len - i) * sizeof(AnnotatedString));
else if (j < s2_len)
memcpy(&d[k], &s2[j], (s2_len - j) * sizeof(AnnotatedString));
}
#endif
} // namespace
void StringSortByLcpMsort(string* buf, string* out) {
vector<const unsigned char*> toks;
for (StringPiece tok : WordScanner(*buf)) {
const_cast<char*>(tok.data())[tok.size()] = 0;
toks.push_back(reinterpret_cast<const unsigned char*>(tok.data()));
}
if (toks.empty())
return;
if (toks.size() == 1) {
*out += reinterpret_cast<const char*>(toks[0]);
return;
}
AnnotatedString* as = static_cast<AnnotatedString*>(
malloc(toks.size() * sizeof(AnnotatedString)));
AnnotatedString* work = static_cast<AnnotatedString*>(
malloc((toks.size() / 2 + 1) * sizeof(AnnotatedString)));
#ifdef DO_SORT_AND_UNIQ_AT_ONCE
int len = StringMergeSortAndUniq(toks, 0, toks.size(), work, as);
#else
int len = static_cast<int>(toks.size());
StringMergeSort(toks, 0, toks.size(), work, as);
#endif
WordWriter ww(out);
#ifdef DO_SORT_AND_UNIQ_AT_ONCE
for (int i = 0; i < len; i++) {
ww.MaybeAddWhitespace();
*out += reinterpret_cast<const char*>(as[i].s);
}
#else
StringPiece prev;
for (int i = 0; i < len; i++) {
StringPiece tok = reinterpret_cast<const char*>(as[i].s);
if (prev != tok) {
ww.Write(tok);
prev = tok;
}
}
#endif
free(as);
free(work);
}