digitalmars.D - Latest string_token Code
- Ben Hanson (324/324) Jun 22 2010 Hi there,
- bearophile (6/8) Jun 22 2010 T.sizeof gives the size of the init of a variable of type T.
- Ben Hanson (8/16) Jun 22 2010 D'oh! I think I've seen that about now you mention it...
- bearophile (22/26) Jun 22 2010 But once your program works well you can change the variable names a lit...
- Ben Hanson (12/36) Jun 22 2010 CamelCase. And variable names are written in camelCase with a starting l...
- Ben Hanson (3/8) Jun 22 2010 Actually, I may as well convert as I go.
- Ben Hanson (346/346) Jun 22 2010 Here's the latest with naming convention (hopefully) followed. I've impl...
- Rory McGuire (4/352) Jun 22 2010 "the string"w
- Ben Hanson (4/404) Jun 22 2010 Thanks. The problem now is that sort() corrupts the strings. Does anyone...
- Rory McGuire (4/411) Jun 22 2010 perhaps from mixing wide chars with CharT if CharT is 8bits?
- Ben Hanson (21/436) Jun 22 2010 I don't think so:
- Rory McGuire (5/446) Jun 22 2010 hmm, that does seem strange, it seems to work with char and dchar but no...
- Andrei Alexandrescu (10/12) Jun 22 2010 I suggest you to look into using the range primitives (empty, front,
- Ben Hanson (10/22) Jun 22 2010 OK, thanks.
- Rory McGuire (12/341) Jun 22 2010 I think sizeof is a property, e.g. char.sizeof or:
- Ben Hanson (2/12) Jun 22 2010 Thanks Rory.
- bearophile (62/62) Jun 22 2010 Ben Hanson:
- Ben Hanson (368/429) Jun 22 2010 your code, to show how to program in D (here I comment only the first ex...
- bearophile (10/17) Jun 22 2010 Do you mean the dmd optimizer or the llvm one?
- Lars T. Kyllingstad (9/15) Jun 23 2010 Probably not always, but there is no reason it shouldn't. In the cases
- Rory McGuire (5/454) Jun 23 2010 While you are using pointers to do all the copying, comparing etc... are...
Hi there,
I've basically got the string_token class working now. Thanks to everyone who
helped. It still needs some work as memmove works with bytes so I need the
equivalent of 'sizeof' in D for this.
'squeeze' doesn't work with wide chars, so I will write my own version.
When I shrink or grow char arrays, I'd like to know if I should re-set my
pointers into them accordingly.
If anyone can point out any other obvious issues, bad style etc. that would be
appreciated. Please bear in mind that I'd like the code to be as fast as
possible.
Here's the source:
Regards,
Ben
module main;
import std.algorithm;
import std.array;
import std.c.string;
import std.string;
import std.stdio;
template regex(CharT)
{
struct basic_string_token
{
bool _negated = false;
CharT[] _charset;
enum size_t MAX_CHARS = CharT.max + 1;
enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0;
this(const bool negated_, ref CharT[] charset_)
{
_negated = negated_;
_charset = charset_;
}
void remove_duplicates()
{
_charset.sort;
_charset = squeeze(_charset.idup).dup;
}
void normalise()
{
if (_charset.length == MAX_CHARS)
{
_negated = !_negated;
_charset.clear();
}
else if (_charset.length > MAX_CHARS / 2)
{
negate();
}
}
void negate()
{
CharT curr_char_ = START_CHAR;
CharT[] temp_;
CharT *ptr_;
CharT *curr_ = _charset.ptr;
CharT *end_ = curr_ + _charset.length;
size_t i_ = 0;
_negated = !_negated;
temp_.length = MAX_CHARS - _charset.length;
ptr_ = temp_.ptr;
while (curr_ < end_)
{
while (*curr_ > curr_char_)
{
*ptr_ = curr_char_;
++ptr_;
++curr_char_;
++i_;
}
++curr_char_;
++curr_;
++i_;
}
for (; i_ < MAX_CHARS; ++i_)
{
*ptr_ = curr_char_;
++ptr_;
++curr_char_;
}
_charset = temp_;
}
bool empty()
{
return _charset.length == 0 && !_negated;
}
bool any()
{
return _charset.length == 0 && _negated;
}
void clear()
{
_negated = false;
_charset.length = 0;
}
void intersect(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if ((any() && rhs_.any()) || (_negated == rhs_._negated &&
!any() && !rhs_.any()))
{
intersect_same_types(rhs_, overlap_);
}
else
{
intersect_diff_types(rhs_, overlap_);
}
}
private:
void intersect_same_types(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (any())
{
clear();
overlap_._negated = true;
rhs_.clear();
}
else
{
CharT *iter_ = _charset.ptr;
CharT *end_ = iter_ + _charset.length;
CharT *rhs_iter_ = rhs_._charset.ptr;
CharT *rhs_end_ = rhs_iter_ + rhs_._charset.length;
overlap_._negated = _negated;
while (iter_ != end_ && rhs_iter_ != rhs_end_)
{
if (*iter_ < *rhs_iter_)
{
++iter_;
}
else if (*iter_ > *rhs_iter_)
{
++rhs_iter_;
}
else
{
overlap_._charset ~= *iter_;
memmove(iter_, iter_ + 1, _charset.ptr + _charset.length - iter_);
--end_;
_charset.length -= 1;
memmove(rhs_iter_, rhs_iter_ + 1, rhs_._charset.ptr +
rhs_._charset.length - rhs_iter_);
--rhs_end_;
rhs_._charset.length -= 1;
}
}
if (_negated)
{
// duplicates already merged
// src, dest
merge(_charset, overlap_._charset);
// duplicates already merged
// src, dest
merge(rhs_._charset, overlap_._charset);
_negated = false;
rhs_._negated = false;
swap(_charset, rhs_._charset);
normalise();
overlap_.normalise();
rhs_.normalise();
}
else if (!overlap_._charset.length == 0)
{
normalise();
overlap_.normalise();
rhs_.normalise();
}
}
}
void intersect_diff_types(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (any())
{
intersect_any(rhs_, overlap_);
}
else if (_negated)
{
intersect_negated(rhs_, overlap_);
}
else // _negated == false
{
intersect_charset(rhs_, overlap_);
}
}
void intersect_any(ref basic_string_token rhs_, ref basic_string_token
overlap_)
{
if (rhs_._negated)
{
rhs_.intersect_negated(this, overlap_);
}
else // rhs._negated == false
{
rhs_.intersect_charset(this, overlap_);
}
}
void intersect_negated(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (rhs_.any())
{
overlap_._negated = true;
overlap_._charset = _charset;
rhs_._negated = false;
rhs_._charset = _charset;
clear();
}
else // rhs._negated == false
{
rhs_.intersect_charset(this, overlap_);
}
}
void intersect_charset(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (rhs_.any())
{
overlap_._charset = _charset;
rhs_._negated = true;
rhs_._charset = _charset;
clear();
}
else // rhs_._negated == true
{
CharT *iter_ = _charset.ptr;
CharT *end_ = iter_ + _charset.length;
CharT *rhs_iter_ = rhs_._charset.ptr;
CharT *rhs_end_ = rhs_iter_ + rhs_._charset.length;
while (iter_ != end_ && rhs_iter_ != rhs_end_)
{
if (*iter_ < *rhs_iter_)
{
overlap_._charset ~= *iter_;
rhs_._charset.length += 1;
rhs_iter_ = rhs_._charset.ptr;
rhs_end_ = rhs_iter_ + rhs_._charset.length;
memmove(rhs_iter_ + 1, rhs_iter_, rhs_._charset.length -
(rhs_end_ - rhs_iter_ - 1));
++rhs_iter_;
memmove(iter_, iter_ + 1, _charset.ptr + _charset.length - iter_);
_charset.length -= 1;
--end_;
}
else if (*iter_ > *rhs_iter_)
{
++rhs_iter_;
}
else
{
++iter_;
++rhs_iter_;
}
}
if (iter_ != end_)
{
CharT[] temp_;
temp_.length = end_ - iter_;
memmove(temp_.ptr, iter_, temp_.length);
// nothing bigger in rhs_ than iter_
// src, dest
merge(temp_, overlap_._charset);
memmove(iter_, iter_ + 1, _charset.ptr + _charset.length - iter_);
_charset.length -= 1;
}
if (!overlap_._charset.empty())
{
merge(overlap_._charset, rhs_._charset);
// possible duplicates, so check for any and erase.
rhs_._charset = squeeze(rhs_._charset.idup).dup;
normalise();
overlap_.normalise();
rhs_.normalise();
}
}
}
void merge(ref CharT[] src_, ref CharT[] dest_)
{
CharT[] temp_;
CharT *ptr_;
CharT *iter_ = src_.ptr;
CharT *end_ = iter_ + src_.length;
CharT *dest_iter_ = dest_.ptr;
CharT *dest_end_ = dest_iter_ + dest_.length;
temp_.length = src_.length + dest_.length;
ptr_ = temp_.ptr;
while (iter_ != end_ && dest_iter_ != dest_end_)
{
if (*iter_ < *dest_iter_)
{
*ptr_++ = *iter_++;
}
else
{
*ptr_++ = *dest_iter_++;
}
}
while (iter_ != end_)
{
*ptr_++ = *iter_++;
}
while (dest_iter_ != dest_end_)
{
*ptr_++ = *dest_iter_++;
}
dest_ = temp_;
}
};
}
int main(char[][]argv)
{
regex!(char).basic_string_token lhs_;
regex!(char).basic_string_token rhs_;
regex!(char).basic_string_token intersect_;
lhs_._charset = "abc".dup;
lhs_._negated = true;
rhs_._charset = "bcd".dup;
rhs_._negated = true;
writeln(lhs_._charset, '(', lhs_._negated, ") intersect ",
rhs_._charset, '(', rhs_._negated, ") =");
lhs_.intersect(rhs_, intersect_);
writeln(lhs_._charset, '(', lhs_._negated, "), ",
rhs_._charset, '(', rhs_._negated, "), ",
intersect_._charset, '(', intersect_._negated, ')');
return 0;
}
Jun 22 2010
Ben Hanson:It still needs some work as memmove works with bytes so I need the equivalent of 'sizeof' in D for this.T.sizeof gives the size of the init of a variable of type T. If T is a dynamic array it returns wordsSize*2, so if you need the item size you can write T[0].sizeof. Why do you use so many underscores? Bye, bearophile
Jun 22 2010
== Quote from bearophile (bearophileHUGS lycos.com)'s articleBen Hanson:can write T[0].sizeof.It still needs some work as memmove works with bytes so I need the equivalent of 'sizeof' in D for this.T.sizeof gives the size of the init of a variable of type T. If T is a dynamic array it returns wordsSize*2, so if you need the item size youWhy do you use so many underscores? Bye, bearophileD'oh! I think I've seen that about now you mention it... The underscores thing just comes from the C++ source. I was recommended that approach, as not wanting to use Reverse Polish Notation (i.e. MFC style), the underscores allow you to have a type the same name as a member var or local var. Thanks, Ben
Jun 22 2010
Ben Hanson:The underscores thing just comes from the C++ source.But once your program works well you can change the variable names a little, or even before if you have some kind of IDE. In D style guide structs and classes need to start with an upper case, in CamelCase. And variable names are written in camelCase with a starting lower case: http://www.digitalmars.com/d/2.0/dstyle.html Following a common style guide is important.I was recommended that approach, as not wanting to use Reverse Polish Notation (i.e. MFC style),I think you mean polish with no reverse :-)the underscores allow you to have a type the same name as a member var or local var.I don't understand. Why can't you write the code like this? struct BasicStringToken { enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; private bool negated = false; private CharT[] charset; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } I have kept the underscores in the arguments of the method because they have a limited scope/life, so they don't add a lot of noise to the whole code. Bye, bearophile
Jun 22 2010
== Quote from bearophile (bearophileHUGS lycos.com)'s articleBen Hanson:even before if you have some kind of IDE.The underscores thing just comes from the C++ source.But once your program works well you can change the variable names a little, orIn D style guide structs and classes need to start with an upper case, inCamelCase. And variable names are written in camelCase with a starting lower case:http://www.digitalmars.com/d/2.0/dstyle.html Following a common style guide is important.I'm happy to change the naming style when things are running.RPN is for compilers isn't it?! I think it was called Hungarian Notation (possibly)...I was recommended that approach, as not wanting to use Reverse Polish Notation (i.e. MFC style),I think you mean polish with no reverse :-)local var.the underscores allow you to have a type the same name as a member var orI don't understand. Why can't you write the code like this? struct BasicStringToken { enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; private bool negated = false; private CharT[] charset; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } I have kept the underscores in the arguments of the method because they have alimited scope/life, so they don't add a lot of noise to the whole code. The code so far isn't a good example of that, but it's generally when you typedefed a template and then wanted to name a var with the same name as the type. Regardles, as you pointed out, D does things differently, which is fine. Regards, Ben
Jun 22 2010
Ben Hanson <Ben.Hanson tfbplc.co.uk> == Quote from bearophile (bearophileHUGS lycos.com)'s articleActually, I may as well convert as I go. Regards, BenIn D style guide structs and classes need to start with an upper case, inCamelCase. And variable names are written in camelCase with a starting lower case:http://www.digitalmars.com/d/2.0/dstyle.html Following a common style guide is important.
Jun 22 2010
Here's the latest with naming convention (hopefully) followed. I've implemented
my
own squeeze() function and used sizeof in the memmove calls.
How can I specify wide strings for the literals?
Thanks,
Ben
module main;
import std.algorithm;
import std.array;
import std.c.string;
import std.string;
import std.stdio;
template regex(CharT)
{
struct BasicStringToken
{
bool negated = false;
CharT[] charset;
enum size_t MAX_CHARS = CharT.max + 1;
enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0;
this(const bool negated_, ref CharT[] charset_)
{
negated = negated_;
charset = charset_;
}
void removeDuplicates()
{
charset.sort;
squeeze(charset);
}
void normalise()
{
if (charset.length == MAX_CHARS)
{
negated = !negated;
charset.clear();
}
else if (charset.length > MAX_CHARS / 2)
{
negate();
}
}
void negate()
{
CharT curr_char = START_CHAR;
CharT[] temp;
CharT *ptr = cast(CharT *) 0;
CharT *curr = charset.ptr;
CharT *end = curr + charset.length;
size_t i = 0;
negated = !negated;
temp.length = MAX_CHARS - charset.length;
ptr = temp.ptr;
while (curr < end)
{
while (*curr > curr_char)
{
*ptr = curr_char;
++ptr;
++curr_char;
++i;
}
++curr_char;
++curr;
++i;
}
for (; i < MAX_CHARS; ++i)
{
*ptr = curr_char;
++ptr;
++curr_char;
}
charset = temp;
}
bool empty()
{
return charset.length == 0 && !negated;
}
bool any()
{
return charset.length == 0 && negated;
}
void clear()
{
negated = false;
charset.length = 0;
}
void intersect(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if ((any() && rhs.any()) || (negated == rhs.negated &&
!any() && !rhs.any()))
{
intersectSameTypes(rhs, overlap);
}
else
{
intersectDiffTypes(rhs, overlap);
}
}
private:
void intersectSameTypes(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (any())
{
clear();
overlap.negated = true;
rhs.clear();
}
else
{
CharT *iter = charset.ptr;
CharT *end = iter + charset.length;
CharT *rhs_iter = rhs.charset.ptr;
CharT *rhs_end = rhs_iter + rhs.charset.length;
overlap.negated = negated;
while (iter != end && rhs_iter != rhs_end)
{
if (*iter < *rhs_iter)
{
++iter;
}
else if (*iter > *rhs_iter)
{
++rhs_iter;
}
else
{
overlap.charset ~= *iter;
memmove(iter, iter + 1, (charset.ptr +
charset.length - iter) * CharT.sizeof);
--end;
charset.length -= 1;
memmove(rhs_iter, rhs_iter + 1, (rhs.charset.ptr +
rhs.charset.length - rhs_iter) * CharT.sizeof);
--rhs_end;
rhs.charset.length -= 1;
}
}
if (negated)
{
// duplicates already merged
// src, dest
merge(charset, overlap.charset);
// duplicates already merged
// src, dest
merge(rhs.charset, overlap.charset);
negated = false;
rhs.negated = false;
swap(charset, rhs.charset);
normalise();
overlap.normalise();
rhs.normalise();
}
else if (!overlap.charset.length == 0)
{
normalise();
overlap.normalise();
rhs.normalise();
}
}
}
void intersectDiffTypes(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (any())
{
intersectAny(rhs, overlap);
}
else if (negated)
{
intersectNegated(rhs, overlap);
}
else // negated == false
{
intersectCharset(rhs, overlap);
}
}
void intersectAny(ref BasicStringToken rhs, ref BasicStringToken overlap)
{
if (rhs.negated)
{
rhs.intersectNegated(this, overlap);
}
else // rhs.negated == false
{
rhs.intersectCharset(this, overlap);
}
}
void intersectNegated(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (rhs.any())
{
overlap.negated = true;
overlap.charset = charset;
rhs.negated = false;
rhs.charset = charset;
clear();
}
else // rhs.negated == false
{
rhs.intersectCharset(this, overlap);
}
}
void intersectCharset(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (rhs.any())
{
overlap.charset = charset;
rhs.negated = true;
rhs.charset = charset;
clear();
}
else // rhs.negated == true
{
CharT *iter = charset.ptr;
CharT *end = iter + charset.length;
CharT *rhs_iter = rhs.charset.ptr;
CharT *rhs_end = rhs_iter + rhs.charset.length;
while (iter != end && rhs_iter != rhs_end)
{
if (*iter < *rhs_iter)
{
overlap.charset ~= *iter;
rhs.charset.length += 1;
rhs_iter = rhs.charset.ptr;
rhs_end = rhs_iter + rhs.charset.length;
memmove(rhs_iter + 1, rhs_iter, (rhs.charset.length -
(rhs_end - rhs_iter - 1)) * CharT.sizeof);
++rhs_iter;
memmove(iter, iter + 1, (charset.ptr +
charset.length - iter) * CharT.sizeof);
charset.length -= 1;
--end;
}
else if (*iter > *rhs_iter)
{
++rhs_iter;
}
else
{
++iter;
++rhs_iter;
}
}
if (iter != end)
{
CharT[] temp;
temp.length = end - iter;
memmove(temp.ptr, iter, temp.length * CharT.sizeof);
// nothing bigger in rhs than iter
// src, dest
merge(temp, overlap.charset);
memmove(iter, iter + 1, (charset.ptr +
charset.length - iter) * CharT.sizeof);
charset.length -= 1;
}
if (!overlap.charset.empty())
{
merge(overlap.charset, rhs.charset);
// possible duplicates, so check for any and erase.
squeeze(rhs.charset);
normalise();
overlap.normalise();
rhs.normalise();
}
}
}
void squeeze(ref CharT[] str)
{
if (str.length > 1)
{
CharT *write = str.ptr;
CharT *end = write + str.length;
CharT *read = write + 1;
while (read != end)
{
while (read != end && *read == *write)
{
++read;
}
if (read == end) break;
++write;
if (read > write)
{
*write = *read;
}
++read;
}
str.length = write + 1 - str.ptr;
}
}
void merge(ref CharT[] src, ref CharT[] dest)
{
CharT[] temp;
CharT *ptr;
CharT *iter = src.ptr;
CharT *end = iter + src.length;
CharT *dest_iter = dest.ptr;
CharT *dest_end = dest_iter + dest.length;
temp.length = src.length + dest.length;
ptr = temp.ptr;
while (iter != end && dest_iter != dest_end)
{
if (*iter < *dest_iter)
{
*ptr++ = *iter++;
}
else
{
*ptr++ = *dest_iter++;
}
}
while (iter != end)
{
*ptr++ = *iter++;
}
while (dest_iter != dest_end)
{
*ptr++ = *dest_iter++;
}
dest = temp;
}
};
}
int main(char[][]argv)
{
regex!(char).BasicStringToken lhs;
regex!(char).BasicStringToken rhs;
regex!(char).BasicStringToken intersect;
lhs.charset = "aaabbc".dup;
lhs.negated = true;
lhs.removeDuplicates();
rhs.charset = "bccddd".dup;
rhs.negated = true;
rhs.removeDuplicates();
writeln(lhs.charset, '(', lhs.negated, ") intersect ",
rhs.charset, '(', rhs.negated, ") =");
lhs.intersect(rhs, intersect);
writeln(lhs.charset, '(', lhs.negated, "), ",
rhs.charset, '(', rhs.negated, "), ",
intersect.charset, '(', intersect.negated, ')');
return 0;
}
Jun 22 2010
"the string"w
gives you 16bit I believe. postfix with a 'd' should give you 32bit.
On Tue, 22 Jun 2010 15:13:06 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk>
wrote:
Here's the latest with naming convention (hopefully) followed. I've
implemented my
own squeeze() function and used sizeof in the memmove calls.
How can I specify wide strings for the literals?
Thanks,
Ben
module main;
import std.algorithm;
import std.array;
import std.c.string;
import std.string;
import std.stdio;
template regex(CharT)
{
struct BasicStringToken
{
bool negated = false;
CharT[] charset;
enum size_t MAX_CHARS = CharT.max + 1;
enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0;
this(const bool negated_, ref CharT[] charset_)
{
negated = negated_;
charset = charset_;
}
void removeDuplicates()
{
charset.sort;
squeeze(charset);
}
void normalise()
{
if (charset.length == MAX_CHARS)
{
negated = !negated;
charset.clear();
}
else if (charset.length > MAX_CHARS / 2)
{
negate();
}
}
void negate()
{
CharT curr_char = START_CHAR;
CharT[] temp;
CharT *ptr = cast(CharT *) 0;
CharT *curr = charset.ptr;
CharT *end = curr + charset.length;
size_t i = 0;
negated = !negated;
temp.length = MAX_CHARS - charset.length;
ptr = temp.ptr;
while (curr < end)
{
while (*curr > curr_char)
{
*ptr = curr_char;
++ptr;
++curr_char;
++i;
}
++curr_char;
++curr;
++i;
}
for (; i < MAX_CHARS; ++i)
{
*ptr = curr_char;
++ptr;
++curr_char;
}
charset = temp;
}
bool empty()
{
return charset.length == 0 && !negated;
}
bool any()
{
return charset.length == 0 && negated;
}
void clear()
{
negated = false;
charset.length = 0;
}
void intersect(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if ((any() && rhs.any()) || (negated == rhs.negated &&
!any() && !rhs.any()))
{
intersectSameTypes(rhs, overlap);
}
else
{
intersectDiffTypes(rhs, overlap);
}
}
private:
void intersectSameTypes(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (any())
{
clear();
overlap.negated = true;
rhs.clear();
}
else
{
CharT *iter = charset.ptr;
CharT *end = iter + charset.length;
CharT *rhs_iter = rhs.charset.ptr;
CharT *rhs_end = rhs_iter + rhs.charset.length;
overlap.negated = negated;
while (iter != end && rhs_iter != rhs_end)
{
if (*iter < *rhs_iter)
{
++iter;
}
else if (*iter > *rhs_iter)
{
++rhs_iter;
}
else
{
overlap.charset ~= *iter;
memmove(iter, iter + 1, (charset.ptr +
charset.length - iter) * CharT.sizeof);
--end;
charset.length -= 1;
memmove(rhs_iter, rhs_iter + 1, (rhs.charset.ptr +
rhs.charset.length - rhs_iter) * CharT.sizeof);
--rhs_end;
rhs.charset.length -= 1;
}
}
if (negated)
{
// duplicates already merged
// src, dest
merge(charset, overlap.charset);
// duplicates already merged
// src, dest
merge(rhs.charset, overlap.charset);
negated = false;
rhs.negated = false;
swap(charset, rhs.charset);
normalise();
overlap.normalise();
rhs.normalise();
}
else if (!overlap.charset.length == 0)
{
normalise();
overlap.normalise();
rhs.normalise();
}
}
}
void intersectDiffTypes(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (any())
{
intersectAny(rhs, overlap);
}
else if (negated)
{
intersectNegated(rhs, overlap);
}
else // negated == false
{
intersectCharset(rhs, overlap);
}
}
void intersectAny(ref BasicStringToken rhs, ref BasicStringToken
overlap)
{
if (rhs.negated)
{
rhs.intersectNegated(this, overlap);
}
else // rhs.negated == false
{
rhs.intersectCharset(this, overlap);
}
}
void intersectNegated(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (rhs.any())
{
overlap.negated = true;
overlap.charset = charset;
rhs.negated = false;
rhs.charset = charset;
clear();
}
else // rhs.negated == false
{
rhs.intersectCharset(this, overlap);
}
}
void intersectCharset(ref BasicStringToken rhs,
ref BasicStringToken overlap)
{
if (rhs.any())
{
overlap.charset = charset;
rhs.negated = true;
rhs.charset = charset;
clear();
}
else // rhs.negated == true
{
CharT *iter = charset.ptr;
CharT *end = iter + charset.length;
CharT *rhs_iter = rhs.charset.ptr;
CharT *rhs_end = rhs_iter + rhs.charset.length;
while (iter != end && rhs_iter != rhs_end)
{
if (*iter < *rhs_iter)
{
overlap.charset ~= *iter;
rhs.charset.length += 1;
rhs_iter = rhs.charset.ptr;
rhs_end = rhs_iter + rhs.charset.length;
memmove(rhs_iter + 1, rhs_iter, (rhs.charset.length -
(rhs_end - rhs_iter - 1)) * CharT.sizeof);
++rhs_iter;
memmove(iter, iter + 1, (charset.ptr +
charset.length - iter) * CharT.sizeof);
charset.length -= 1;
--end;
}
else if (*iter > *rhs_iter)
{
++rhs_iter;
}
else
{
++iter;
++rhs_iter;
}
}
if (iter != end)
{
CharT[] temp;
temp.length = end - iter;
memmove(temp.ptr, iter, temp.length * CharT.sizeof);
// nothing bigger in rhs than iter
// src, dest
merge(temp, overlap.charset);
memmove(iter, iter + 1, (charset.ptr +
charset.length - iter) * CharT.sizeof);
charset.length -= 1;
}
if (!overlap.charset.empty())
{
merge(overlap.charset, rhs.charset);
// possible duplicates, so check for any and erase.
squeeze(rhs.charset);
normalise();
overlap.normalise();
rhs.normalise();
}
}
}
void squeeze(ref CharT[] str)
{
if (str.length > 1)
{
CharT *write = str.ptr;
CharT *end = write + str.length;
CharT *read = write + 1;
while (read != end)
{
while (read != end && *read == *write)
{
++read;
}
if (read == end) break;
++write;
if (read > write)
{
*write = *read;
}
++read;
}
str.length = write + 1 - str.ptr;
}
}
void merge(ref CharT[] src, ref CharT[] dest)
{
CharT[] temp;
CharT *ptr;
CharT *iter = src.ptr;
CharT *end = iter + src.length;
CharT *dest_iter = dest.ptr;
CharT *dest_end = dest_iter + dest.length;
temp.length = src.length + dest.length;
ptr = temp.ptr;
while (iter != end && dest_iter != dest_end)
{
if (*iter < *dest_iter)
{
*ptr++ = *iter++;
}
else
{
*ptr++ = *dest_iter++;
}
}
while (iter != end)
{
*ptr++ = *iter++;
}
while (dest_iter != dest_end)
{
*ptr++ = *dest_iter++;
}
dest = temp;
}
};
}
int main(char[][]argv)
{
regex!(char).BasicStringToken lhs;
regex!(char).BasicStringToken rhs;
regex!(char).BasicStringToken intersect;
lhs.charset = "aaabbc".dup;
lhs.negated = true;
lhs.removeDuplicates();
rhs.charset = "bccddd".dup;
rhs.negated = true;
rhs.removeDuplicates();
writeln(lhs.charset, '(', lhs.negated, ") intersect ",
rhs.charset, '(', rhs.negated, ") =");
lhs.intersect(rhs, intersect);
writeln(lhs.charset, '(', lhs.negated, "), ",
rhs.charset, '(', rhs.negated, "), ",
intersect.charset, '(', intersect.negated, ')');
return 0;
}
Jun 22 2010
== Quote from Rory McGuire (rmcguire neonova.co.za)'s articleOn Tue, 22 Jun 2010 15:13:06 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:Here's the latest with naming convention (hopefully) followed. I've implemented my own squeeze() function and used sizeof in the memmove calls. How can I specify wide strings for the literals? Thanks, Ben module main; import std.algorithm; import std.array; import std.c.string; import std.string; import std.stdio; template regex(CharT) { struct BasicStringToken { bool negated = false; CharT[] charset; enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } void removeDuplicates() { charset.sort; squeeze(charset); } void normalise() { if (charset.length == MAX_CHARS) { negated = !negated; charset.clear(); } else if (charset.length > MAX_CHARS / 2) { negate(); } } void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT *ptr = cast(CharT *) 0; CharT *curr = charset.ptr; CharT *end = curr + charset.length; size_t i = 0; negated = !negated; temp.length = MAX_CHARS - charset.length; ptr = temp.ptr; while (curr < end) { while (*curr > curr_char) { *ptr = curr_char; ++ptr; ++curr_char; ++i; } ++curr_char; ++curr; ++i; } for (; i < MAX_CHARS; ++i) { *ptr = curr_char; ++ptr; ++curr_char; } charset = temp; } bool empty() { return charset.length == 0 && !negated; } bool any() { return charset.length == 0 && negated; } void clear() { negated = false; charset.length = 0; } void intersect(ref BasicStringToken rhs, ref BasicStringToken overlap) { if ((any() && rhs.any()) || (negated == rhs.negated && !any() && !rhs.any())) { intersectSameTypes(rhs, overlap); } else { intersectDiffTypes(rhs, overlap); } } private: void intersectSameTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { clear(); overlap.negated = true; rhs.clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; overlap.negated = negated; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { ++iter; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { overlap.charset ~= *iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); --end; charset.length -= 1; memmove(rhs_iter, rhs_iter + 1, (rhs.charset.ptr + rhs.charset.length - rhs_iter) * CharT.sizeof); --rhs_end; rhs.charset.length -= 1; } } if (negated) { // duplicates already merged // src, dest merge(charset, overlap.charset); // duplicates already merged // src, dest merge(rhs.charset, overlap.charset); negated = false; rhs.negated = false; swap(charset, rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } else if (!overlap.charset.length == 0) { normalise(); overlap.normalise(); rhs.normalise(); } } } void intersectDiffTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { intersectAny(rhs, overlap); } else if (negated) { intersectNegated(rhs, overlap); } else // negated == false { intersectCharset(rhs, overlap); } } void intersectAny(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.negated) { rhs.intersectNegated(this, overlap); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectNegated(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.negated = true; overlap.charset = charset; rhs.negated = false; rhs.charset = charset; clear(); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectCharset(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.charset = charset; rhs.negated = true; rhs.charset = charset; clear(); } else // rhs.negated == true { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { overlap.charset ~= *iter; rhs.charset.length += 1; rhs_iter = rhs.charset.ptr; rhs_end = rhs_iter + rhs.charset.length; memmove(rhs_iter + 1, rhs_iter, (rhs.charset.length - (rhs_end - rhs_iter - 1)) * CharT.sizeof); ++rhs_iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; --end; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { ++iter; ++rhs_iter; } } if (iter != end) { CharT[] temp; temp.length = end - iter; memmove(temp.ptr, iter, temp.length * CharT.sizeof); // nothing bigger in rhs than iter // src, dest merge(temp, overlap.charset); memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; } if (!overlap.charset.empty()) { merge(overlap.charset, rhs.charset); // possible duplicates, so check for any and erase. squeeze(rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } } } void squeeze(ref CharT[] str) { if (str.length > 1) { CharT *write = str.ptr; CharT *end = write + str.length; CharT *read = write + 1; while (read != end) { while (read != end && *read == *write) { ++read; } if (read == end) break; ++write; if (read > write) { *write = *read; } ++read; } str.length = write + 1 - str.ptr; } } void merge(ref CharT[] src, ref CharT[] dest) { CharT[] temp; CharT *ptr; CharT *iter = src.ptr; CharT *end = iter + src.length; CharT *dest_iter = dest.ptr; CharT *dest_end = dest_iter + dest.length; temp.length = src.length + dest.length; ptr = temp.ptr; while (iter != end && dest_iter != dest_end) { if (*iter < *dest_iter) { *ptr++ = *iter++; } else { *ptr++ = *dest_iter++; } } while (iter != end) { *ptr++ = *iter++; } while (dest_iter != dest_end) { *ptr++ = *dest_iter++; } dest = temp; } }; } int main(char[][]argv) { regex!(char).BasicStringToken lhs; regex!(char).BasicStringToken rhs; regex!(char).BasicStringToken intersect; lhs.charset = "aaabbc".dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd".dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }"the string"w gives you 16bit I believe. postfix with a 'd' should give you 32bit.Thanks. The problem now is that sort() corrupts the strings. Does anyone know why? Regards, Ben
Jun 22 2010
On Tue, 22 Jun 2010 15:31:14 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:== Quote from Rory McGuire (rmcguire neonova.co.za)'s articleperhaps from mixing wide chars with CharT if CharT is 8bits? Honestly I havn't read your code but that is just the likely scenario.On Tue, 22 Jun 2010 15:13:06 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:Here's the latest with naming convention (hopefully) followed. I've implemented my own squeeze() function and used sizeof in the memmove calls. How can I specify wide strings for the literals? Thanks, Ben module main; import std.algorithm; import std.array; import std.c.string; import std.string; import std.stdio; template regex(CharT) { struct BasicStringToken { bool negated = false; CharT[] charset; enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } void removeDuplicates() { charset.sort; squeeze(charset); } void normalise() { if (charset.length == MAX_CHARS) { negated = !negated; charset.clear(); } else if (charset.length > MAX_CHARS / 2) { negate(); } } void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT *ptr = cast(CharT *) 0; CharT *curr = charset.ptr; CharT *end = curr + charset.length; size_t i = 0; negated = !negated; temp.length = MAX_CHARS - charset.length; ptr = temp.ptr; while (curr < end) { while (*curr > curr_char) { *ptr = curr_char; ++ptr; ++curr_char; ++i; } ++curr_char; ++curr; ++i; } for (; i < MAX_CHARS; ++i) { *ptr = curr_char; ++ptr; ++curr_char; } charset = temp; } bool empty() { return charset.length == 0 && !negated; } bool any() { return charset.length == 0 && negated; } void clear() { negated = false; charset.length = 0; } void intersect(ref BasicStringToken rhs, ref BasicStringToken overlap) { if ((any() && rhs.any()) || (negated == rhs.negated && !any() && !rhs.any())) { intersectSameTypes(rhs, overlap); } else { intersectDiffTypes(rhs, overlap); } } private: void intersectSameTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { clear(); overlap.negated = true; rhs.clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; overlap.negated = negated; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { ++iter; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { overlap.charset ~= *iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); --end; charset.length -= 1; memmove(rhs_iter, rhs_iter + 1, (rhs.charset.ptr + rhs.charset.length - rhs_iter) *CharT.sizeof);--rhs_end; rhs.charset.length -= 1; } } if (negated) { // duplicates already merged // src, dest merge(charset, overlap.charset); // duplicates already merged // src, dest merge(rhs.charset, overlap.charset); negated = false; rhs.negated = false; swap(charset, rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } else if (!overlap.charset.length == 0) { normalise(); overlap.normalise(); rhs.normalise(); } } } void intersectDiffTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { intersectAny(rhs, overlap); } else if (negated) { intersectNegated(rhs, overlap); } else // negated == false { intersectCharset(rhs, overlap); } } void intersectAny(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.negated) { rhs.intersectNegated(this, overlap); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectNegated(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.negated = true; overlap.charset = charset; rhs.negated = false; rhs.charset = charset; clear(); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectCharset(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.charset = charset; rhs.negated = true; rhs.charset = charset; clear(); } else // rhs.negated == true { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { overlap.charset ~= *iter; rhs.charset.length += 1; rhs_iter = rhs.charset.ptr; rhs_end = rhs_iter + rhs.charset.length; memmove(rhs_iter + 1, rhs_iter,(rhs.charset.length -(rhs_end - rhs_iter - 1)) * CharT.sizeof); ++rhs_iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; --end; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { ++iter; ++rhs_iter; } } if (iter != end) { CharT[] temp; temp.length = end - iter; memmove(temp.ptr, iter, temp.length * CharT.sizeof); // nothing bigger in rhs than iter // src, dest merge(temp, overlap.charset); memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; } if (!overlap.charset.empty()) { merge(overlap.charset, rhs.charset); // possible duplicates, so check for any and erase. squeeze(rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } } } void squeeze(ref CharT[] str) { if (str.length > 1) { CharT *write = str.ptr; CharT *end = write + str.length; CharT *read = write + 1; while (read != end) { while (read != end && *read == *write) { ++read; } if (read == end) break; ++write; if (read > write) { *write = *read; } ++read; } str.length = write + 1 - str.ptr; } } void merge(ref CharT[] src, ref CharT[] dest) { CharT[] temp; CharT *ptr; CharT *iter = src.ptr; CharT *end = iter + src.length; CharT *dest_iter = dest.ptr; CharT *dest_end = dest_iter + dest.length; temp.length = src.length + dest.length; ptr = temp.ptr; while (iter != end && dest_iter != dest_end) { if (*iter < *dest_iter) { *ptr++ = *iter++; } else { *ptr++ = *dest_iter++; } } while (iter != end) { *ptr++ = *iter++; } while (dest_iter != dest_end) { *ptr++ = *dest_iter++; } dest = temp; } }; } int main(char[][]argv) { regex!(char).BasicStringToken lhs; regex!(char).BasicStringToken rhs; regex!(char).BasicStringToken intersect; lhs.charset = "aaabbc".dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd".dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }"the string"w gives you 16bit I believe. postfix with a 'd' should give you 32bit.Thanks. The problem now is that sort() corrupts the strings. Does anyone know why? Regards, Ben
Jun 22 2010
== Quote from Rory McGuire (rmcguire neonova.co.za)'s articleOn Tue, 22 Jun 2010 15:31:14 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:I don't think so: int main(char[][]argv) { regex!(wchar).BasicStringToken lhs; regex!(wchar).BasicStringToken rhs; regex!(wchar).BasicStringToken intersect; lhs.charset = "aaabbc"w.dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd"w.dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }== Quote from Rory McGuire (rmcguire neonova.co.za)'s articleperhaps from mixing wide chars with CharT if CharT is 8bits? Honestly I havn't read your code but that is just the likely scenario.On Tue, 22 Jun 2010 15:13:06 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:Here's the latest with naming convention (hopefully) followed. I've implemented my own squeeze() function and used sizeof in the memmove calls. How can I specify wide strings for the literals? Thanks, Ben module main; import std.algorithm; import std.array; import std.c.string; import std.string; import std.stdio; template regex(CharT) { struct BasicStringToken { bool negated = false; CharT[] charset; enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } void removeDuplicates() { charset.sort; squeeze(charset); } void normalise() { if (charset.length == MAX_CHARS) { negated = !negated; charset.clear(); } else if (charset.length > MAX_CHARS / 2) { negate(); } } void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT *ptr = cast(CharT *) 0; CharT *curr = charset.ptr; CharT *end = curr + charset.length; size_t i = 0; negated = !negated; temp.length = MAX_CHARS - charset.length; ptr = temp.ptr; while (curr < end) { while (*curr > curr_char) { *ptr = curr_char; ++ptr; ++curr_char; ++i; } ++curr_char; ++curr; ++i; } for (; i < MAX_CHARS; ++i) { *ptr = curr_char; ++ptr; ++curr_char; } charset = temp; } bool empty() { return charset.length == 0 && !negated; } bool any() { return charset.length == 0 && negated; } void clear() { negated = false; charset.length = 0; } void intersect(ref BasicStringToken rhs, ref BasicStringToken overlap) { if ((any() && rhs.any()) || (negated == rhs.negated && !any() && !rhs.any())) { intersectSameTypes(rhs, overlap); } else { intersectDiffTypes(rhs, overlap); } } private: void intersectSameTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { clear(); overlap.negated = true; rhs.clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; overlap.negated = negated; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { ++iter; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { overlap.charset ~= *iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); --end; charset.length -= 1; memmove(rhs_iter, rhs_iter + 1, (rhs.charset.ptr + rhs.charset.length - rhs_iter) *CharT.sizeof);--rhs_end; rhs.charset.length -= 1; } } if (negated) { // duplicates already merged // src, dest merge(charset, overlap.charset); // duplicates already merged // src, dest merge(rhs.charset, overlap.charset); negated = false; rhs.negated = false; swap(charset, rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } else if (!overlap.charset.length == 0) { normalise(); overlap.normalise(); rhs.normalise(); } } } void intersectDiffTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { intersectAny(rhs, overlap); } else if (negated) { intersectNegated(rhs, overlap); } else // negated == false { intersectCharset(rhs, overlap); } } void intersectAny(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.negated) { rhs.intersectNegated(this, overlap); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectNegated(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.negated = true; overlap.charset = charset; rhs.negated = false; rhs.charset = charset; clear(); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectCharset(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.charset = charset; rhs.negated = true; rhs.charset = charset; clear(); } else // rhs.negated == true { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { overlap.charset ~= *iter; rhs.charset.length += 1; rhs_iter = rhs.charset.ptr; rhs_end = rhs_iter + rhs.charset.length; memmove(rhs_iter + 1, rhs_iter,(rhs.charset.length -(rhs_end - rhs_iter - 1)) * CharT.sizeof); ++rhs_iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; --end; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { ++iter; ++rhs_iter; } } if (iter != end) { CharT[] temp; temp.length = end - iter; memmove(temp.ptr, iter, temp.length * CharT.sizeof); // nothing bigger in rhs than iter // src, dest merge(temp, overlap.charset); memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; } if (!overlap.charset.empty()) { merge(overlap.charset, rhs.charset); // possible duplicates, so check for any and erase. squeeze(rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } } } void squeeze(ref CharT[] str) { if (str.length > 1) { CharT *write = str.ptr; CharT *end = write + str.length; CharT *read = write + 1; while (read != end) { while (read != end && *read == *write) { ++read; } if (read == end) break; ++write; if (read > write) { *write = *read; } ++read; } str.length = write + 1 - str.ptr; } } void merge(ref CharT[] src, ref CharT[] dest) { CharT[] temp; CharT *ptr; CharT *iter = src.ptr; CharT *end = iter + src.length; CharT *dest_iter = dest.ptr; CharT *dest_end = dest_iter + dest.length; temp.length = src.length + dest.length; ptr = temp.ptr; while (iter != end && dest_iter != dest_end) { if (*iter < *dest_iter) { *ptr++ = *iter++; } else { *ptr++ = *dest_iter++; } } while (iter != end) { *ptr++ = *iter++; } while (dest_iter != dest_end) { *ptr++ = *dest_iter++; } dest = temp; } }; } int main(char[][]argv) { regex!(char).BasicStringToken lhs; regex!(char).BasicStringToken rhs; regex!(char).BasicStringToken intersect; lhs.charset = "aaabbc".dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd".dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }"the string"w gives you 16bit I believe. postfix with a 'd' should give you 32bit.Thanks. The problem now is that sort() corrupts the strings. Does anyone know why? Regards, Ben
Jun 22 2010
On Tue, 22 Jun 2010 16:37:38 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:== Quote from Rory McGuire (rmcguire neonova.co.za)'s articlehmm, that does seem strange, it seems to work with char and dchar but not wchar. -RoryOn Tue, 22 Jun 2010 15:31:14 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:I don't think so: int main(char[][]argv) { regex!(wchar).BasicStringToken lhs; regex!(wchar).BasicStringToken rhs; regex!(wchar).BasicStringToken intersect; lhs.charset = "aaabbc"w.dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd"w.dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }== Quote from Rory McGuire (rmcguire neonova.co.za)'s article<Ben.Hanson tfbplc.co.uk>On Tue, 22 Jun 2010 15:13:06 +0200, Ben Hanson(rhs.charset.ptr +wrote:Here's the latest with naming convention (hopefully) followed. I've implemented my own squeeze() function and used sizeof in the memmove calls. How can I specify wide strings for the literals? Thanks, Ben module main; import std.algorithm; import std.array; import std.c.string; import std.string; import std.stdio; template regex(CharT) { struct BasicStringToken { bool negated = false; CharT[] charset; enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } void removeDuplicates() { charset.sort; squeeze(charset); } void normalise() { if (charset.length == MAX_CHARS) { negated = !negated; charset.clear(); } else if (charset.length > MAX_CHARS / 2) { negate(); } } void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT *ptr = cast(CharT *) 0; CharT *curr = charset.ptr; CharT *end = curr + charset.length; size_t i = 0; negated = !negated; temp.length = MAX_CHARS - charset.length; ptr = temp.ptr; while (curr < end) { while (*curr > curr_char) { *ptr = curr_char; ++ptr; ++curr_char; ++i; } ++curr_char; ++curr; ++i; } for (; i < MAX_CHARS; ++i) { *ptr = curr_char; ++ptr; ++curr_char; } charset = temp; } bool empty() { return charset.length == 0 && !negated; } bool any() { return charset.length == 0 && negated; } void clear() { negated = false; charset.length = 0; } void intersect(ref BasicStringToken rhs, ref BasicStringToken overlap) { if ((any() && rhs.any()) || (negated == rhs.negated && !any() && !rhs.any())) { intersectSameTypes(rhs, overlap); } else { intersectDiffTypes(rhs, overlap); } } private: void intersectSameTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { clear(); overlap.negated = true; rhs.clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; overlap.negated = negated; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { ++iter; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { overlap.charset ~= *iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); --end; charset.length -= 1; memmove(rhs_iter, rhs_iter + 1,BasicStringTokenrhs.charset.length - rhs_iter) *CharT.sizeof);--rhs_end; rhs.charset.length -= 1; } } if (negated) { // duplicates already merged // src, dest merge(charset, overlap.charset); // duplicates already merged // src, dest merge(rhs.charset, overlap.charset); negated = false; rhs.negated = false; swap(charset, rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } else if (!overlap.charset.length == 0) { normalise(); overlap.normalise(); rhs.normalise(); } } } void intersectDiffTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { intersectAny(rhs, overlap); } else if (negated) { intersectNegated(rhs, overlap); } else // negated == false { intersectCharset(rhs, overlap); } } void intersectAny(ref BasicStringToken rhs, refCharT.sizeof);overlap) { if (rhs.negated) { rhs.intersectNegated(this, overlap); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectNegated(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.negated = true; overlap.charset = charset; rhs.negated = false; rhs.charset = charset; clear(); } else // rhs.negated == false { rhs.intersectCharset(this, overlap); } } void intersectCharset(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.charset = charset; rhs.negated = true; rhs.charset = charset; clear(); } else // rhs.negated == true { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhs_iter = rhs.charset.ptr; CharT *rhs_end = rhs_iter + rhs.charset.length; while (iter != end && rhs_iter != rhs_end) { if (*iter < *rhs_iter) { overlap.charset ~= *iter; rhs.charset.length += 1; rhs_iter = rhs.charset.ptr; rhs_end = rhs_iter + rhs.charset.length; memmove(rhs_iter + 1, rhs_iter,(rhs.charset.length -(rhs_end - rhs_iter - 1)) * CharT.sizeof); ++rhs_iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; --end; } else if (*iter > *rhs_iter) { ++rhs_iter; } else { ++iter; ++rhs_iter; } } if (iter != end) { CharT[] temp; temp.length = end - iter; memmove(temp.ptr, iter, temp.length *anyone// nothing bigger in rhs than iter // src, dest merge(temp, overlap.charset); memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; } if (!overlap.charset.empty()) { merge(overlap.charset, rhs.charset); // possible duplicates, so check for any and erase. squeeze(rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } } } void squeeze(ref CharT[] str) { if (str.length > 1) { CharT *write = str.ptr; CharT *end = write + str.length; CharT *read = write + 1; while (read != end) { while (read != end && *read == *write) { ++read; } if (read == end) break; ++write; if (read > write) { *write = *read; } ++read; } str.length = write + 1 - str.ptr; } } void merge(ref CharT[] src, ref CharT[] dest) { CharT[] temp; CharT *ptr; CharT *iter = src.ptr; CharT *end = iter + src.length; CharT *dest_iter = dest.ptr; CharT *dest_end = dest_iter + dest.length; temp.length = src.length + dest.length; ptr = temp.ptr; while (iter != end && dest_iter != dest_end) { if (*iter < *dest_iter) { *ptr++ = *iter++; } else { *ptr++ = *dest_iter++; } } while (iter != end) { *ptr++ = *iter++; } while (dest_iter != dest_end) { *ptr++ = *dest_iter++; } dest = temp; } }; } int main(char[][]argv) { regex!(char).BasicStringToken lhs; regex!(char).BasicStringToken rhs; regex!(char).BasicStringToken intersect; lhs.charset = "aaabbc".dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd".dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }"the string"w gives you 16bit I believe. postfix with a 'd' should give you 32bit.Thanks. The problem now is that sort() corrupts the strings. Doesknow why? Regards, Benperhaps from mixing wide chars with CharT if CharT is 8bits? Honestly I havn't read your code but that is just the likely scenario.
Jun 22 2010
On 06/22/2010 08:13 AM, Ben Hanson wrote:Here's the latest with naming convention (hopefully) followed. I've implemented my own squeeze() function and used sizeof in the memmove calls.I suggest you to look into using the range primitives (empty, front, back, popFront, and popBack) with strings of any width. Your code assumes that all characters have the same width and therefore will behave erratically on UTF-8 and UTF-16 encodings. In the particular case of squeeze(), you may want to use uniq instead, which works on any forward range and will therefore decode characters properly: http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#uniq Andrei
Jun 22 2010
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleOn 06/22/2010 08:13 AM, Ben Hanson wrote:OK, thanks. Don't forget these are regular expressions though. I was wondering whether people really want to pass regular expressions UTF encoded, but I suppose it could happen. It's certainly a good idea to get used to using UTF compatible functions anyway. Is there is any support for Unicode continuation characters yet? Do you agree that (ideally) Unicode text should be normalised before searching? Regards, BenHere's the latest with naming convention (hopefully) followed. I've implemented my own squeeze() function and used sizeof in the memmove calls.I suggest you to look into using the range primitives (empty, front, back, popFront, and popBack) with strings of any width. Your code assumes that all characters have the same width and therefore will behave erratically on UTF-8 and UTF-16 encodings. In the particular case of squeeze(), you may want to use uniq instead, which works on any forward range and will therefore decode characters properly: http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#uniq Andrei
Jun 22 2010
I think sizeof is a property, e.g. char.sizeof or:
struct A {
int a;
char[10] b;
}
A.sizeof
A a;
a.sizeof
you get the picture. (Have I got it?)
-Rory
On Tue, 22 Jun 2010 12:07:37 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk>
wrote:
Hi there,
I've basically got the string_token class working now. Thanks to
everyone who
helped. It still needs some work as memmove works with bytes so I need
the
equivalent of 'sizeof' in D for this.
'squeeze' doesn't work with wide chars, so I will write my own version.
When I shrink or grow char arrays, I'd like to know if I should re-set my
pointers into them accordingly.
If anyone can point out any other obvious issues, bad style etc. that
would be
appreciated. Please bear in mind that I'd like the code to be as fast as
possible.
Here's the source:
Regards,
Ben
module main;
import std.algorithm;
import std.array;
import std.c.string;
import std.string;
import std.stdio;
template regex(CharT)
{
struct basic_string_token
{
bool _negated = false;
CharT[] _charset;
enum size_t MAX_CHARS = CharT.max + 1;
enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0;
this(const bool negated_, ref CharT[] charset_)
{
_negated = negated_;
_charset = charset_;
}
void remove_duplicates()
{
_charset.sort;
_charset = squeeze(_charset.idup).dup;
}
void normalise()
{
if (_charset.length == MAX_CHARS)
{
_negated = !_negated;
_charset.clear();
}
else if (_charset.length > MAX_CHARS / 2)
{
negate();
}
}
void negate()
{
CharT curr_char_ = START_CHAR;
CharT[] temp_;
CharT *ptr_;
CharT *curr_ = _charset.ptr;
CharT *end_ = curr_ + _charset.length;
size_t i_ = 0;
_negated = !_negated;
temp_.length = MAX_CHARS - _charset.length;
ptr_ = temp_.ptr;
while (curr_ < end_)
{
while (*curr_ > curr_char_)
{
*ptr_ = curr_char_;
++ptr_;
++curr_char_;
++i_;
}
++curr_char_;
++curr_;
++i_;
}
for (; i_ < MAX_CHARS; ++i_)
{
*ptr_ = curr_char_;
++ptr_;
++curr_char_;
}
_charset = temp_;
}
bool empty()
{
return _charset.length == 0 && !_negated;
}
bool any()
{
return _charset.length == 0 && _negated;
}
void clear()
{
_negated = false;
_charset.length = 0;
}
void intersect(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if ((any() && rhs_.any()) || (_negated == rhs_._negated &&
!any() && !rhs_.any()))
{
intersect_same_types(rhs_, overlap_);
}
else
{
intersect_diff_types(rhs_, overlap_);
}
}
private:
void intersect_same_types(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (any())
{
clear();
overlap_._negated = true;
rhs_.clear();
}
else
{
CharT *iter_ = _charset.ptr;
CharT *end_ = iter_ + _charset.length;
CharT *rhs_iter_ = rhs_._charset.ptr;
CharT *rhs_end_ = rhs_iter_ + rhs_._charset.length;
overlap_._negated = _negated;
while (iter_ != end_ && rhs_iter_ != rhs_end_)
{
if (*iter_ < *rhs_iter_)
{
++iter_;
}
else if (*iter_ > *rhs_iter_)
{
++rhs_iter_;
}
else
{
overlap_._charset ~= *iter_;
memmove(iter_, iter_ + 1, _charset.ptr + _charset.length - iter_);
--end_;
_charset.length -= 1;
memmove(rhs_iter_, rhs_iter_ + 1, rhs_._charset.ptr +
rhs_._charset.length - rhs_iter_);
--rhs_end_;
rhs_._charset.length -= 1;
}
}
if (_negated)
{
// duplicates already merged
// src, dest
merge(_charset, overlap_._charset);
// duplicates already merged
// src, dest
merge(rhs_._charset, overlap_._charset);
_negated = false;
rhs_._negated = false;
swap(_charset, rhs_._charset);
normalise();
overlap_.normalise();
rhs_.normalise();
}
else if (!overlap_._charset.length == 0)
{
normalise();
overlap_.normalise();
rhs_.normalise();
}
}
}
void intersect_diff_types(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (any())
{
intersect_any(rhs_, overlap_);
}
else if (_negated)
{
intersect_negated(rhs_, overlap_);
}
else // _negated == false
{
intersect_charset(rhs_, overlap_);
}
}
void intersect_any(ref basic_string_token rhs_, ref basic_string_token
overlap_)
{
if (rhs_._negated)
{
rhs_.intersect_negated(this, overlap_);
}
else // rhs._negated == false
{
rhs_.intersect_charset(this, overlap_);
}
}
void intersect_negated(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (rhs_.any())
{
overlap_._negated = true;
overlap_._charset = _charset;
rhs_._negated = false;
rhs_._charset = _charset;
clear();
}
else // rhs._negated == false
{
rhs_.intersect_charset(this, overlap_);
}
}
void intersect_charset(ref basic_string_token rhs_,
ref basic_string_token overlap_)
{
if (rhs_.any())
{
overlap_._charset = _charset;
rhs_._negated = true;
rhs_._charset = _charset;
clear();
}
else // rhs_._negated == true
{
CharT *iter_ = _charset.ptr;
CharT *end_ = iter_ + _charset.length;
CharT *rhs_iter_ = rhs_._charset.ptr;
CharT *rhs_end_ = rhs_iter_ + rhs_._charset.length;
while (iter_ != end_ && rhs_iter_ != rhs_end_)
{
if (*iter_ < *rhs_iter_)
{
overlap_._charset ~= *iter_;
rhs_._charset.length += 1;
rhs_iter_ = rhs_._charset.ptr;
rhs_end_ = rhs_iter_ + rhs_._charset.length;
memmove(rhs_iter_ + 1, rhs_iter_, rhs_._charset.length -
(rhs_end_ - rhs_iter_ - 1));
++rhs_iter_;
memmove(iter_, iter_ + 1, _charset.ptr + _charset.length - iter_);
_charset.length -= 1;
--end_;
}
else if (*iter_ > *rhs_iter_)
{
++rhs_iter_;
}
else
{
++iter_;
++rhs_iter_;
}
}
if (iter_ != end_)
{
CharT[] temp_;
temp_.length = end_ - iter_;
memmove(temp_.ptr, iter_, temp_.length);
// nothing bigger in rhs_ than iter_
// src, dest
merge(temp_, overlap_._charset);
memmove(iter_, iter_ + 1, _charset.ptr + _charset.length - iter_);
_charset.length -= 1;
}
if (!overlap_._charset.empty())
{
merge(overlap_._charset, rhs_._charset);
// possible duplicates, so check for any and erase.
rhs_._charset = squeeze(rhs_._charset.idup).dup;
normalise();
overlap_.normalise();
rhs_.normalise();
}
}
}
void merge(ref CharT[] src_, ref CharT[] dest_)
{
CharT[] temp_;
CharT *ptr_;
CharT *iter_ = src_.ptr;
CharT *end_ = iter_ + src_.length;
CharT *dest_iter_ = dest_.ptr;
CharT *dest_end_ = dest_iter_ + dest_.length;
temp_.length = src_.length + dest_.length;
ptr_ = temp_.ptr;
while (iter_ != end_ && dest_iter_ != dest_end_)
{
if (*iter_ < *dest_iter_)
{
*ptr_++ = *iter_++;
}
else
{
*ptr_++ = *dest_iter_++;
}
}
while (iter_ != end_)
{
*ptr_++ = *iter_++;
}
while (dest_iter_ != dest_end_)
{
*ptr_++ = *dest_iter_++;
}
dest_ = temp_;
}
};
}
int main(char[][]argv)
{
regex!(char).basic_string_token lhs_;
regex!(char).basic_string_token rhs_;
regex!(char).basic_string_token intersect_;
lhs_._charset = "abc".dup;
lhs_._negated = true;
rhs_._charset = "bcd".dup;
rhs_._negated = true;
writeln(lhs_._charset, '(', lhs_._negated, ") intersect ",
rhs_._charset, '(', rhs_._negated, ") =");
lhs_.intersect(rhs_, intersect_);
writeln(lhs_._charset, '(', lhs_._negated, "), ",
rhs_._charset, '(', rhs_._negated, "), ",
intersect_._charset, '(', intersect_._negated, ')');
return 0;
}
Jun 22 2010
== Quote from Rory McGuire (rmcguire neonova.co.za)'s article
I think sizeof is a property, e.g. char.sizeof or:
struct A {
int a;
char[10] b;
}
A.sizeof
A a;
a.sizeof
you get the picture. (Have I got it?)
-Rory
Thanks Rory.
Jun 22 2010
Ben Hanson:
Even if you are an expert C++ programmer, I can express few more comments about
your code, to show how to program in D (here I comment only the first example
of each thing. More cases can follow).
------------------
You can write this:
template regex(CharT)
{
struct BasicStringToken
{
Like this:
template regex(CharT)
{
struct BasicStringToken
{
------------------
In this part:
void negate()
{
CharT curr_char = START_CHAR;
CharT[] temp;
CharT *ptr = cast(CharT *) 0;
This is closer to normal D code, because in D there is "null", and in D the *
of pointer definitions is better written on the left, because it's part of the
type:
void negate()
{
CharT curr_char = START_CHAR;
CharT[] temp;
CharT* ptr = null;
But the idiomatic D code is this because pointers are automatically initialized
to null, and nornally in D variable names are camelCase with a starting
lowercase (sometimes I'd like to use underscores, but this is the D style.
Constant names can contain underscores in D, I presume):
void negate()
{
CharT currChar = START_CHAR;
CharT[] temp;
CharT* ptr;
------------------
This line:
else if (!overlap.charset.length == 0)
I don't like it a lot, maybe this is better:
else if (overlap.charset.length)
------------------
This code:
else if (negated)
{
intersectNegated(rhs, overlap);
}
else // negated == false
{
intersectCharset(rhs, overlap);
}
There is no need of that comment, never add useless noise to the code:
else if (negated)
{
intersectNegated(rhs, overlap);
}
else
{
intersectCharset(rhs, overlap);
}
------------------
I see that in your code you lot of pointers. Pointers can be used in D, but I
suggest you to use them only when necessary. Maybe some usage of pointers can
be replaced by normal array indexes, that are safer too (because in D in
nonrelease mode array bounds are tested).
For some situations I have created in D2 a "safer pointer" that in release mode
is as efficient as a pointer but in nonrelease mode asserts if you make it step
out of a pre-specified memory interval. I don't think lot of people here has
appreciated it, but I have used it to catch some of my pointer-releated bugs.
Bye,
bearophile
Jun 22 2010
== Quote from bearophile (bearophileHUGS lycos.com)'s articleBen Hanson: Even if you are an expert C++ programmer, I can express few more comments aboutyour code, to show how to program in D (here I comment only the first example of each thing. More cases can follow). It's hard to be an expert in C++ these days, particularly when posting to a group frequented by Andrei! :-D------------------ You can write this: template regex(CharT) { struct BasicStringToken { Like this: template regex(CharT) { struct BasicStringToken { ------------------ In this part: void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT *ptr = cast(CharT *) 0; This is closer to normal D code, because in D there is "null", and in D the * ofpointer definitions is better written on the left, because it's part of the type:void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT* ptr = null; But the idiomatic D code is this because pointers are automatically initializedto null, and nornally in D variable names are camelCase with a starting lowercase (sometimes I'd like to use underscores, but this is the D style. Constant names can contain underscores in D, I presume):void negate() { CharT currChar = START_CHAR; CharT[] temp; CharT* ptr; ------------------I forgot about auto initialisation in D. D'oh!This line: else if (!overlap.charset.length == 0) I don't like it a lot, maybe this is better: else if (overlap.charset.length)This is just a bug. Should be: else if (!overlap.charset.length)------------------ This code: else if (negated) { intersectNegated(rhs, overlap); } else // negated == false { intersectCharset(rhs, overlap); } There is no need of that comment, never add useless noise to the code: else if (negated) { intersectNegated(rhs, overlap); } else { intersectCharset(rhs, overlap); }Those comments were deliberate as a 'yes I do mean that', but I've removed them anyway.------------------ I see that in your code you lot of pointers. Pointers can be used in D, but Isuggest you to use them only when necessary. Maybe some usage of pointers can be replaced by normal array indexes, that are safer too (because in D in nonrelease mode array bounds are tested).For some situations I have created in D2 a "safer pointer" that in release modeis as efficient as a pointer but in nonrelease mode asserts if you make it step out of a pre-specified memory interval. I don't think lot of people here has appreciated it, but I have used it to catch some of my pointer-releated bugs.Bye, bearophileAll the code for this library needs to absolutely as fast as it can be. As it turns out, by intersecting regex charsets once in the code then it won't take that many cycles, but the only question I have is: Will the optimiser create as fast code if you use indexes compared to pointers? Updated code follows. Thanks, Ben module main; import std.algorithm; import std.array; import std.c.string; import std.string; import std.stdio; template regex(CharT) { struct BasicStringToken { bool negated = false; CharT[] charset; enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } void removeDuplicates() { charset.sort; squeeze(charset); } void normalise() { if (charset.length == MAX_CHARS) { negated = !negated; charset.clear(); } else if (charset.length > MAX_CHARS / 2) { negate(); } } void negate() { CharT currChar = START_CHAR; CharT[] temp; CharT *ptr; CharT *curr = charset.ptr; CharT *end = curr + charset.length; size_t i = 0; negated = !negated; temp.length = MAX_CHARS - charset.length; ptr = temp.ptr; while (curr < end) { while (*curr > currChar) { *ptr = currChar; ++ptr; ++currChar; ++i; } ++currChar; ++curr; ++i; } for (; i < MAX_CHARS; ++i) { *ptr = currChar; ++ptr; ++currChar; } charset = temp; } bool empty() { return charset.length == 0 && !negated; } bool any() { return charset.length == 0 && negated; } void clear() { negated = false; charset.length = 0; } void intersect(ref BasicStringToken rhs, ref BasicStringToken overlap) { if ((any() && rhs.any()) || (negated == rhs.negated && !any() && !rhs.any())) { intersectSameTypes(rhs, overlap); } else { intersectDiffTypes(rhs, overlap); } } private: void intersectSameTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { clear(); overlap.negated = true; rhs.clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhsIter = rhs.charset.ptr; CharT *rhsEnd = rhsIter + rhs.charset.length; overlap.negated = negated; while (iter != end && rhsIter != rhsEnd) { if (*iter < *rhsIter) { ++iter; } else if (*iter > *rhsIter) { ++rhsIter; } else { overlap.charset ~= *iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); --end; charset.length -= 1; memmove(rhsIter, rhsIter + 1, (rhs.charset.ptr + rhs.charset.length - rhsIter) * CharT.sizeof); --rhsEnd; rhs.charset.length -= 1; } } if (negated) { // duplicates already merged // src, dest merge(charset, overlap.charset); // duplicates already merged // src, dest merge(rhs.charset, overlap.charset); negated = false; rhs.negated = false; swap(charset, rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } else if (!overlap.charset.length) { normalise(); overlap.normalise(); rhs.normalise(); } } } void intersectDiffTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { intersectAny(rhs, overlap); } else if (negated) { intersectNegated(rhs, overlap); } else { intersectCharset(rhs, overlap); } } void intersectAny(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.negated) { rhs.intersectNegated(this, overlap); } else { rhs.intersectCharset(this, overlap); } } void intersectNegated(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.negated = true; overlap.charset = charset; rhs.negated = false; rhs.charset = charset; clear(); } else { rhs.intersectCharset(this, overlap); } } void intersectCharset(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.charset = charset; rhs.negated = true; rhs.charset = charset; clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhsIter = rhs.charset.ptr; CharT *rhsEnd = rhsIter + rhs.charset.length; while (iter != end && rhsIter != rhsEnd) { if (*iter < *rhsIter) { overlap.charset ~= *iter; rhs.charset.length += 1; rhsIter = rhs.charset.ptr; rhsEnd = rhsIter + rhs.charset.length; memmove(rhsIter + 1, rhsIter, (rhs.charset.length - (rhsEnd - rhsIter - 1)) * CharT.sizeof); ++rhsIter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; --end; } else if (*iter > *rhsIter) { ++rhsIter; } else { ++iter; ++rhsIter; } } if (iter != end) { CharT[] temp; temp.length = end - iter; memmove(temp.ptr, iter, temp.length * CharT.sizeof); // nothing bigger in rhs than iter // src, dest merge(temp, overlap.charset); memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; } if (!overlap.charset.empty()) { merge(overlap.charset, rhs.charset); // possible duplicates, so check for any and erase. squeeze(rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } } } void squeeze(ref CharT[] str) { if (str.length > 1) { CharT *write = str.ptr; CharT *end = write + str.length; CharT *read = write + 1; while (read != end) { while (read != end && *read == *write) { ++read; } if (read == end) break; ++write; if (read > write) { *write = *read; } ++read; } str.length = write + 1 - str.ptr; } } void merge(ref CharT[] src, ref CharT[] dest) { CharT[] temp; CharT *ptr; CharT *iter = src.ptr; CharT *end = iter + src.length; CharT *destIter = dest.ptr; CharT *destEnd = destIter + dest.length; temp.length = src.length + dest.length; ptr = temp.ptr; while (iter != end && destIter != destEnd) { if (*iter < *destIter) { *ptr++ = *iter++; } else { *ptr++ = *destIter++; } } while (iter != end) { *ptr++ = *iter++; } while (destIter != destEnd) { *ptr++ = *destIter++; } dest = temp; } }; } int main(char[][]argv) { regex!(char).BasicStringToken lhs; regex!(char).BasicStringToken rhs; regex!(char).BasicStringToken intersect; lhs.charset = "aaabbc".dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd".dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }
Jun 22 2010
Ben Hanson:Will the optimiser create as fast code if you use indexes compared to pointers?Do you mean the dmd optimizer or the llvm one? LLVM is able to digest array indexes and pointers about equally efficiently. In one important case dmd seems to produce slower code with pointers compared to arrays :-) In some situations it's better to use pointers because they allow a richer semantics, but in many situations arrays give better-looking (and a bit safer) code. If you have some free time you can create an array-based version and compare their performance. Otherwise if your original C++ code uses pointers then maybe it's better to keep them, to avoid translation bugs. You need lot of care to translate code between two different languages, you need a strong rigour. Another small thing I've seen in your code:template regex(CharT) { struct BasicStringToken {...}; }D struct definitions don't need an ending semicolon, so it's better to not add it in D code. Bye, bearophile
Jun 22 2010
On Tue, 22 Jun 2010 20:59:55 +0000, Ben Hanson wrote:All the code for this library needs to absolutely as fast as it can be. As it turns out, by intersecting regex charsets once in the code then it won't take that many cycles, but the only question I have is: Will the optimiser create as fast code if you use indexes compared to pointers?Probably not always, but there is no reason it shouldn't. In the cases where it doesn't, I'd say it is a compiler bug. In my opinion, you should always go the clean and safe route, and use arrays. And if someone complains that your code is slow, blame the compiler. ;) "Premature optimization is the root of all evil." -- Donald Knuth -Lars
Jun 23 2010
On Tue, 22 Jun 2010 22:59:55 +0200, Ben Hanson <Ben.Hanson tfbplc.co.uk> wrote:== Quote from bearophile (bearophileHUGS lycos.com)'s articleWhile you are using pointers to do all the copying, comparing etc... are you taking into account that the characters may span multiple CharTs?Ben Hanson: Even if you are an expert C++ programmer, I can express few more comments aboutyour code, to show how to program in D (here I comment only the first example of each thing. More cases can follow). It's hard to be an expert in C++ these days, particularly when posting to a group frequented by Andrei! :-D------------------ You can write this: template regex(CharT) { struct BasicStringToken { Like this: template regex(CharT) { struct BasicStringToken { ------------------ In this part: void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT *ptr = cast(CharT *) 0; This is closer to normal D code, because in D there is "null", and in D the * ofpointer definitions is better written on the left, because it's part of the type:void negate() { CharT curr_char = START_CHAR; CharT[] temp; CharT* ptr = null; But the idiomatic D code is this because pointers are automatically initializedto null, and nornally in D variable names are camelCase with a starting lowercase (sometimes I'd like to use underscores, but this is the D style. Constant names can contain underscores in D, I presume):void negate() { CharT currChar = START_CHAR; CharT[] temp; CharT* ptr; ------------------I forgot about auto initialisation in D. D'oh!This line: else if (!overlap.charset.length == 0) I don't like it a lot, maybe this is better: else if (overlap.charset.length)This is just a bug. Should be: else if (!overlap.charset.length)------------------ This code: else if (negated) { intersectNegated(rhs, overlap); } else // negated == false { intersectCharset(rhs, overlap); } There is no need of that comment, never add useless noise to the code: else if (negated) { intersectNegated(rhs, overlap); } else { intersectCharset(rhs, overlap); }Those comments were deliberate as a 'yes I do mean that', but I've removed them anyway.------------------ I see that in your code you lot of pointers. Pointers can be used in D, but Isuggest you to use them only when necessary. Maybe some usage of pointers can be replaced by normal array indexes, that are safer too (because in D in nonrelease mode array bounds are tested).For some situations I have created in D2 a "safer pointer" that in release modeis as efficient as a pointer but in nonrelease mode asserts if you make it step out of a pre-specified memory interval. I don't think lot of people here has appreciated it, but I have used it to catch some of my pointer-releated bugs.Bye, bearophileAll the code for this library needs to absolutely as fast as it can be. As it turns out, by intersecting regex charsets once in the code then it won't take that many cycles, but the only question I have is: Will the optimiser create as fast code if you use indexes compared to pointers? Updated code follows. Thanks, Ben module main; import std.algorithm; import std.array; import std.c.string; import std.string; import std.stdio; template regex(CharT) { struct BasicStringToken { bool negated = false; CharT[] charset; enum size_t MAX_CHARS = CharT.max + 1; enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0; this(const bool negated_, ref CharT[] charset_) { negated = negated_; charset = charset_; } void removeDuplicates() { charset.sort; squeeze(charset); } void normalise() { if (charset.length == MAX_CHARS) { negated = !negated; charset.clear(); } else if (charset.length > MAX_CHARS / 2) { negate(); } } void negate() { CharT currChar = START_CHAR; CharT[] temp; CharT *ptr; CharT *curr = charset.ptr; CharT *end = curr + charset.length; size_t i = 0; negated = !negated; temp.length = MAX_CHARS - charset.length; ptr = temp.ptr; while (curr < end) { while (*curr > currChar) { *ptr = currChar; ++ptr; ++currChar; ++i; } ++currChar; ++curr; ++i; } for (; i < MAX_CHARS; ++i) { *ptr = currChar; ++ptr; ++currChar; } charset = temp; } bool empty() { return charset.length == 0 && !negated; } bool any() { return charset.length == 0 && negated; } void clear() { negated = false; charset.length = 0; } void intersect(ref BasicStringToken rhs, ref BasicStringToken overlap) { if ((any() && rhs.any()) || (negated == rhs.negated && !any() && !rhs.any())) { intersectSameTypes(rhs, overlap); } else { intersectDiffTypes(rhs, overlap); } } private: void intersectSameTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { clear(); overlap.negated = true; rhs.clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhsIter = rhs.charset.ptr; CharT *rhsEnd = rhsIter + rhs.charset.length; overlap.negated = negated; while (iter != end && rhsIter != rhsEnd) { if (*iter < *rhsIter) { ++iter; } else if (*iter > *rhsIter) { ++rhsIter; } else { overlap.charset ~= *iter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); --end; charset.length -= 1; memmove(rhsIter, rhsIter + 1, (rhs.charset.ptr + rhs.charset.length - rhsIter) * CharT.sizeof); --rhsEnd; rhs.charset.length -= 1; } } if (negated) { // duplicates already merged // src, dest merge(charset, overlap.charset); // duplicates already merged // src, dest merge(rhs.charset, overlap.charset); negated = false; rhs.negated = false; swap(charset, rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } else if (!overlap.charset.length) { normalise(); overlap.normalise(); rhs.normalise(); } } } void intersectDiffTypes(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (any()) { intersectAny(rhs, overlap); } else if (negated) { intersectNegated(rhs, overlap); } else { intersectCharset(rhs, overlap); } } void intersectAny(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.negated) { rhs.intersectNegated(this, overlap); } else { rhs.intersectCharset(this, overlap); } } void intersectNegated(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.negated = true; overlap.charset = charset; rhs.negated = false; rhs.charset = charset; clear(); } else { rhs.intersectCharset(this, overlap); } } void intersectCharset(ref BasicStringToken rhs, ref BasicStringToken overlap) { if (rhs.any()) { overlap.charset = charset; rhs.negated = true; rhs.charset = charset; clear(); } else { CharT *iter = charset.ptr; CharT *end = iter + charset.length; CharT *rhsIter = rhs.charset.ptr; CharT *rhsEnd = rhsIter + rhs.charset.length; while (iter != end && rhsIter != rhsEnd) { if (*iter < *rhsIter) { overlap.charset ~= *iter; rhs.charset.length += 1; rhsIter = rhs.charset.ptr; rhsEnd = rhsIter + rhs.charset.length; memmove(rhsIter + 1, rhsIter, (rhs.charset.length - (rhsEnd - rhsIter - 1)) * CharT.sizeof); ++rhsIter; memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; --end; } else if (*iter > *rhsIter) { ++rhsIter; } else { ++iter; ++rhsIter; } } if (iter != end) { CharT[] temp; temp.length = end - iter; memmove(temp.ptr, iter, temp.length * CharT.sizeof); // nothing bigger in rhs than iter // src, dest merge(temp, overlap.charset); memmove(iter, iter + 1, (charset.ptr + charset.length - iter) * CharT.sizeof); charset.length -= 1; } if (!overlap.charset.empty()) { merge(overlap.charset, rhs.charset); // possible duplicates, so check for any and erase. squeeze(rhs.charset); normalise(); overlap.normalise(); rhs.normalise(); } } } void squeeze(ref CharT[] str) { if (str.length > 1) { CharT *write = str.ptr; CharT *end = write + str.length; CharT *read = write + 1; while (read != end) { while (read != end && *read == *write) { ++read; } if (read == end) break; ++write; if (read > write) { *write = *read; } ++read; } str.length = write + 1 - str.ptr; } } void merge(ref CharT[] src, ref CharT[] dest) { CharT[] temp; CharT *ptr; CharT *iter = src.ptr; CharT *end = iter + src.length; CharT *destIter = dest.ptr; CharT *destEnd = destIter + dest.length; temp.length = src.length + dest.length; ptr = temp.ptr; while (iter != end && destIter != destEnd) { if (*iter < *destIter) { *ptr++ = *iter++; } else { *ptr++ = *destIter++; } } while (iter != end) { *ptr++ = *iter++; } while (destIter != destEnd) { *ptr++ = *destIter++; } dest = temp; } }; } int main(char[][]argv) { regex!(char).BasicStringToken lhs; regex!(char).BasicStringToken rhs; regex!(char).BasicStringToken intersect; lhs.charset = "aaabbc".dup; lhs.negated = true; lhs.removeDuplicates(); rhs.charset = "bccddd".dup; rhs.negated = true; rhs.removeDuplicates(); writeln(lhs.charset, '(', lhs.negated, ") intersect ", rhs.charset, '(', rhs.negated, ") ="); lhs.intersect(rhs, intersect); writeln(lhs.charset, '(', lhs.negated, "), ", rhs.charset, '(', rhs.negated, "), ", intersect.charset, '(', intersect.negated, ')'); return 0; }
Jun 23 2010