Monday, May 11, 2015

Digest for comp.lang.c++@googlegroups.com - 22 updates in 7 topics

ravas <ravas@outlook.com>: May 11 01:37AM -0700

I've been helping the open source 2D CAD project LibreCAD with some bug hunting; and found that the snap mode for intersections finds two intersections extremely close together instead of one point of tangency (regarding an incircle of a triangle).
 
The developer working on it has said:
"""
It's not a problem of detecting intersections.
 
the problem is that inscribed circle is generated correct up to relative precision of 1e-8, while the tangential points are test at a precision level of 1e-10. Therefore, the inscribed circle actually intersects with one line.
 
The reasonable way is to improve the equation solver to get the inscribed circle more accurate.
"""
 
and after some more investigation:
 
"""
the tolerance itself is always there, even if we can solve equations at higher precision:
 
currently, we can generate the tangential circle correct up to 10^-8, but intersection detection is up to 10^-10, causing a tangential point (by the definition of tangential circle) to be detected as intersection points.
 
because the actual precision is up to the floating point, there's no clear answer close to precision level.
 
One clear hint, if user specifies to draw with precision 10^-4(as in Current Drawing Preferences), there's no need to report two points 10^-8 apart.
 
Lots of work need to implement this idea;
"""
 
I'm wondering if anyone has any thoughts on this issue.
 
https://github.com/LibreCAD/LibreCAD/issues/523
Victor Bazarov <v.bazarov@comcast.invalid>: May 11 08:22AM -0400

On 5/11/2015 4:37 AM, ravas wrote:
> I've been helping the open source 2D CAD project LibreCAD with some
bug hunting; and found that the snap mode for intersections finds two
intersections extremely close together instead of one point of tangency
(regarding an incircle of a triangle).
 
[...]
 
> I'm wondering if anyone has any thoughts on this issue.
 
Immediate thought: How is that a C++ language issue?
 
Second thought: isn't there a discussion part to any open source
project? Post there.
 
Third thought: instead of creating a stand-alone point, model a point
that is "a point of tangency" with entities stored in it. Use
polymorphism to provide snapping behavior.
 
Fourth thought: (engineering solution) if you find two points (of
intersection) instead of the needed single one, find the average of the
two and use it.
 
V
--
I do not respond to top-posted replies, please don't ask
"Öö Tiib" <ootiib@hot.ee>: May 11 09:57AM -0700

On Monday, 11 May 2015 11:38:00 UTC+3, ravas wrote:
> bug hunting; and found that the snap mode for intersections finds two
> intersections extremely close together instead of one point of tangency
> (regarding an incircle of a triangle).
 
Any issues with floating points and accuracy of calculations are general
in computer science, not C++ specific. Perhaps that good old David
Goldberg's paper discusses it most nicely:
http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
 
Wherever we use floating point calculations we have to take these
issues into account and deal with those or we inevitably receive some
nuisances like you describe later.
"Chris M. Thomasson" <cristom@charter.net>: May 11 01:28PM -0700

> intersections extremely close together instead of one point of tangency
> (regarding an incircle of a triangle).
 
> [...]
 
FIWIW, you can get tangent circles if you move them together just right.
I have a method of finding circle intersections briefly described here:
 
http://webpages.charter.net/appcore/fractal/ttr/circle_isect/circle_isect_draft.pdf
 
I created a quick and dirty online app that can find tangencies:
 
http://webpages.charter.net/appcore/fractal/ttr/circle_isect
 
You can get it to display tangent by using these simple settings:
_________________________________
c0_x = 200
c0_y = 100
c0_r = 50
 
c1_x = 300
c1_y = 100
c1_r = 50
_________________________________
 
 
I have found many other tangents for different sized circles in different
positions
just by softly moving the circles closer to each other. I cannot remember
the settings,
but I will try again and give them to you.
 
Sorry if this is off base for your needs...
 
;^o
"Chris M. Thomasson" <cristom@charter.net>: May 11 01:59PM -0700

> > hunting; and found that the snap mode for intersections finds two
> > intersections extremely close together instead of one point of tangency
> > (regarding an incircle of a triangle).
 
[...]
 
> I have found many other tangents for different sized circles in different
> positions just by softly moving the circles closer to each other. I cannot
> remember the settings, but I will try again and give them to you.
 
FWIW, try these settings:
_______________________________
c0_x = 200
c0_y = 100
c0_r = 90
 
c1_x = 270
c1_y = 120
c1_r = 162.80109889280520001
_______________________________
 
in the online program:
 
http://webpages.charter.net/appcore/fractal/ttr/circle_isect/
 
I happen to get a result of:
 
The circles c0 and c1 are tangent.
 
;^)
ram@zedat.fu-berlin.de (Stefan Ram): May 11 08:36PM

>A problem I've just solved is to write a boolean function to
>determine if the parentheses in the string are balanced.
 
Depends on the definition of »balanced parentheses« for strings!
 
I only know the term for source code, where
 
( ( ( 2 + ")" + )3; /* ) */
 
might not be deemed to have balanced parentheses.
 
>bool isBracket(char c)
 
When the term »parenthesis« was introduced (as above),
the function might also be called »isParenthesis«.
Doug Mika <dougmmika@gmail.com>: May 11 12:04PM -0700

The std::search function is a template function, however to invoke it, we do NOT need to specify the template parameters!! ie. we can call the function as follows:
std::search (haystack.begin(), haystack.end(), needle1, needle1+4);
 
So the question is, why in the following program that I have attached, why must I write
 
size_t nNumEvenElements = count_if(vecIntegers.begin(), vecIntegers.end(), IsEven<int>);
 
why can't I write
 
size_t nNumEvenElements = count_if(vecIntegers.begin(), vecIntegers.end(), IsEven);
 
 
The program:
#include <iostream>
#include <string>
#include <map>
#include <functional>
#include <algorithm>
#include <vector>
 
template <typename elementType>
bool IsEven (const elementType& number){
return ((number % 2)==0);
}
 
int main(int argc, char** argv) {

//The Program
using namespace std;
vector<int> vecIntegers;

for(int i=-9; i<10; ++i)
vecIntegers.push_back(i);

size_t nNumEvenElements = count_if(vecIntegers.begin(), vecIntegers.end(), IsEven<int>);

cout<<"Number of Even Elements is: "<<nNumEvenElements<<endl;

//after my code returns from test() should I avoid using y?)
return 0;
}
Victor Bazarov <v.bazarov@comcast.invalid>: May 11 03:44PM -0400

On 5/11/2015 3:04 PM, Doug Mika wrote:
> The std::search function is a template function, however to invoke
> it,
we do NOT need to specify the template parameters!! ie. we can call the
function as follows:
 
> //after my code returns from test() should I avoid using y?)
> return 0;
> }
 
Have you given any thought to a possibility of getting a decent book
that would explain those things? I mean, for example, "C++ Templates"
by Vandevoorde and Josuttis.
 
'IsEven' is not an expression that yields an object from which the
compiler can deduce the template argument when it instantiates the
'count_if' function template. 'IsEven<int>' *is* such an expression.
The function template 'count_if' is written to expect a *type* as its
second template argument. That type can be deduced from the third
argument of the function call, *if* that argument is an expression that
has a type.
 
I wonder how many times I would need to tell you that before you start
paying attention :-)
 
Get a decent book and *study*. Systematically and *attentively*.
 
V
--
I do not respond to top-posted replies, please don't ask
legalize+jeeves@mail.xmission.com (Richard): May 11 08:02PM

[Please do not mail me a copy of your followup]
 
Victor Bazarov <v.bazarov@comcast.invalid> spake the secret code
 
>Have you given any thought to a possibility of getting a decent book
>that would explain those things? I mean, for example, "C++ Templates"
>by Vandevoorde and Josuttis.
 
While I like that book, it's probably overkill for this sort of
problem. This stuff is covered pretty well in Stroustrup's "C++
Programming Language" 4th edition. This is a basic question about
templates, not something you need the extensive detail of "C++
Templates" to answer.
 
(Aside: "C++ Templates" came out in 2002 and I recently re-read it and
a bunch of the stuff mentioned about compilers and weak support, etc.,
is no longer true. Another reason it's probably not the best place to
send a n00bie. Josuttis's "The C++ Standard Library" has recently
been updated and seems to cover this pretty well in 6.8 Functions as
Algorithm Arguments.)
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
Paavo Helde <myfirstname@osa.pri.ee>: May 11 03:17PM -0500

Doug Mika <dougmmika@gmail.com> wrote in
 
> size_t nNumEvenElements = count_if(vecIntegers.begin(),
> vecIntegers.end(), IsEven<int>);
 
> why can't I write
[...]
> bool IsEven (const elementType& number){
> return ((number % 2)==0);
> }
[...]
 
> size_t nNumEvenElements = count_if(vecIntegers.begin(),
> vecIntegers.end(), IsEven);
 
The template which you need to explicitly instantiate is not
std::count_if(), but your own IsEven. If you don't like to do this, then
one option is simply to not use a template.
 
More to the point, template parameters can be omitted if the compiler is
able to deduce them from the types of passed function arguments. In the
above line no arguments are passed to IsEven, so the compiler cannot
deduce its template parameters. So it does not know what type is the
argument for the count_if and so in turn it is not able to deduce the
template paramters for the count_if itself.
 
You can "fix" this by specifying the count_if template parameters
explicitly. Then you don't need to specify them for IsEven:
 
size_t nNumEvenElements =
count_if<vector<int>::iterator, bool (*)(const int&)>(
vecIntegers.begin(), vecIntegers.end(), IsEven);
 
 
hth
Paavo
Paul <pepstein5@gmail.com>: May 11 11:30AM -0700

A problem I've just solved is to write a boolean function to determine if the parentheses in the string are balanced. My solution is substantially different from my text's suggested solution and I'd like people to offer opinions as to which solution they prefer.
 
Thank you.
 
Paul.
 
My solution:
 
#include <string>
 
using namespace std;
 
bool isBracket(char c)
{
return c=='(' || c == ')' ;
}
 
 
// A function which returns true if the parentheses in a string are balanced and false otherwise.
 
bool balanced(string str)
{
if(str.empty())
return true;
 
if(!isBracket(str[0]))
return balanced(str.substr(1, str.size()-1));
 
if(!isBracket(str[str.size()-1]))
return balanced(str.substr(0, str.size()-1));
 
return str[0] == '(' && str[str.size()-1] == ')' && balanced(str.substr(1, str.size()-2));
}
 
Text solution:
#include <string>
#include <stack>
 
using namespace std;
 
bool is_par_balanced(const string input)
{
 
stack<char> par_stack;
for(auto & c : input)
{
 
if(c == ')')
{
 
if(par_stack.empty())
return false;
 
else if (par_stack.top() == '(' )
par_stack.pop();
 
}
 
else if(c == '(' )
par_stack.push(c);
 
}
 
 
return par_stack.empty();
 
}
Christopher Pisz <nospam@notanaddress.com>: May 11 02:06PM -0500

On 5/11/2015 1:30 PM, Paul wrote:
 
> return par_stack.empty();
 
> }
 
Text solution is faster and uses way less memory. You are essentially
taking one string and making new string copies for each character.
Consider what is happening in both if the string is say 10MB long.
 
I would pass the argument as const string & input though rather than by
value, for the text solution.
 
 
--
I have chosen to troll filter/ignore all subthreads containing the
words: "Rick C. Hodgins", "Flibble", and "Islam"
So, I won't be able to see or respond to any such messages
---
Martin Shobe <martin.shobe@yahoo.com>: May 11 02:11PM -0500

On 5/11/2015 1:30 PM, Paul wrote:
> return balanced(str.substr(0, str.size()-1));
 
> return str[0] == '(' && str[str.size()-1] == ')' && balanced(str.substr(1, str.size()-2));
> }
 
While premature optimization can be a problem, one still shouldn't be
wasteful of ones resources. This will make a copy of (part of) the
string for each non-parenthesis in the string. There's no need to copy
any of it at all. Even if you want to keep the recursive algorithm, pass
iterators into the string instead of copies.
 
 
> }
 
> return par_stack.empty();
 
> }
 
Again, there's some unnecessary resource use. The only characters that
can be pushed onto the stack are '('. Therefore, we can get by with just
counting the number of unmatched '(' so far, return false if that count
ever goes negative or if it's non-zero when we reach the end of the string.
 
As a bonus, using iterators (Warning: not tested)
 
#include <string>
 
using namespace std;
 
bool is_par_balanced(string::const_iterator start,
string::const_iterator end)
{
string::size_type unmatchedParens{0};
 
while (start != end)
{
if (*start == ')')
{
if (unmatchedParens == 0)
{
return false;
}
 
--unmatchedParens;
}
else if (*start == '(' )
{
++unmatchedParens;
}
 
++start;
}
 
return unmatchedParens == 0;
}
 
Martin Shobe
Jorgen Grahn <grahn+nntp@snipabacken.se>: May 11 07:12PM

On Mon, 2015-05-11, Paul wrote:
 
> determine if the parentheses in the string are balanced. My solution
> is substantially different from my text's suggested solution and I'd
> like people to offer opinions as to which solution they prefer.
 
Neither.
 
> return balanced(str.substr(0, str.size()-1));
 
> return str[0] == '(' && str[str.size()-1] == ')' && balanced(str.substr(1, str.size()-2));
> }
 
Recursion. Looks complicated -- especially when you touch both ends
of the string -- and I'm not convinced it's correct.
 
It probably is though: you're saying when you've shaved off
non-brackets at both ends, the string is either empty or you have a
balanced string enclosed in (), or it's not balanced at all.
 
On second thought, it's not. Try "(foo)(bar)". You can't claim
"foo)(bar" is balanced, can you?
 
 
> bool is_par_balanced(const string input)
> {
 
> stack<char> par_stack;
 
Weird. Whose text is that? What's wrong with this one? Seems pretty
straightforward, once you've defined your terms.
 
/**
* True if parenthesis are balanced in [a, e), meaning no group is
* closed which isn't started, and no group is left unclosed in the
* end.
*/
template<class Iter>
bool balanced(Iter a, Iter e)
{
unsigned d = 0;
while(a != e) {
if (*a == '(') {
d++;
}
if (*a == ')') {
if(d==0) return false;
d--;
}
a++;
}
return d==0;
}
 
Way more efficient and general than your solution. And unless I'm
mistaken, correct too.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Paavo Helde <myfirstname@osa.pri.ee>: May 11 02:29PM -0500

Paul <pepstein5@gmail.com> wrote in
 
> return str[0] == '(' && str[str.size()-1] == ')' &&
> balanced(str.substr(1, str.size()-2));
> }
 
This is extremely inefficient (recursion plus zillions of string copies).
 
 
 
> }
 
> return par_stack.empty();
 
> }
 
This is also a bit inefficient. There is no need to use a stack, a simple
integer counter which is incremented and decremented would be enough.
 
This kind of stack would become handy if there are more than one kind of
parens and one wants to check that they are matched correctly. Most
probably this will be discussed in the next chapter of the textbook and
that's the only reason to use a stack here.
 
Cheers
Paavo
Paavo Helde <myfirstname@osa.pri.ee>: May 11 02:31PM -0500

Paul <pepstein5@gmail.com> wrote in
 
> return str[0] == '(' && str[str.size()-1] == ')' &&
> balanced(str.substr(1, str.size()-2));
> }
 
Oh, and it fails on "(a+b)*(c+d)".
 
Cheers
Paavo
legalize+jeeves@mail.xmission.com (Richard): May 11 08:11PM

[Please do not mail me a copy of your followup]
 
Paul <pepstein5@gmail.com> spake the secret code
>if the parentheses in the string are balanced. My solution is
>substantially different from my text's suggested solution and I'd like
>people to offer opinions as to which solution they prefer.
 
The functional problems with your code would easily have been
discovered by writing some unit tests. If you don't know how to do
this, look at my presentation from C++ Now! 2014:
<https://github.com/boostcon/cppnow_presentations_2014/tree/master/files/test_driven>
 
>{
> return c=='(' || c == ')' ;
>}
 
This is a misleading name. A better name: isParenthesis. Here you've
chosen camelCase identifiers for your function and later you choose
underscore_words identifiers for your function. Pick one identifier
convention and use it consistently.
 
Even in this one line you're not using whitespace consistently.
Either omit the whitespace around comparison operators, or use it
around them consistently. For some reason you've also got extra
whitespace before the semi-colon, but nowhere else.
 
>bool balanced(string str)
 
Strings should be passed by const reference.
 
> if(!isBracket(str[0]))
> return balanced(str.substr(1, str.size()-1));
 
Even when strings are passed by const reference, this makes a copy of
the entire string every time you invoke your routine recursively. As
already suggested, using a pair of iterators would be an algorithm
that more naturally fits with the standard library. I might have a
std::vector<char> or std::list<char> that I'd like to know if it's
balanced. With your code I'd first have to copy that into a string,
just to know a read-only property of the sequence. That seems
wasteful and awkward.
 
Also, I see no justification for stripping the trailing character
simply because the first character is a parenthesis. Why isn't
"(foo) " balanced?
 
 
> }
 
> return par_stack.empty();
 
>}
 
It's still doing unnecessary data copying, but this solution is better
than yours because it's only copying the parenthesis around and not
the entire string. In this case the stack is only acting as a counter
and a boolean (was the last thing an open paren or a close paren?) and
it would be clearer to me if the code simply tracked the count and a
boolean. This solution also feels easier to understand than yours
because your code is using misleading identifiers (what's a bracket
got to do with a parenthesis?) and syntactically noisy substring
extraction that is not only irrelevant to the problem, but also
erroneous.
 
If I was interviewing candidates for a job and this was a question I'd
asked them to cdoe for me, I'd prefer the book over you for the job.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
legalize+jeeves@mail.xmission.com (Richard): May 11 05:52PM

[Please do not mail me a copy of your followup]
 
Marcel Mueller <news.5.maazl@spamgourmet.org> spake the secret code
 
>Is the code below valid and portable?
 
No. Use std::vector<char> if you want a writable buffer of characters.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
1971 powerChina <chinapower1971@gmail.com>: May 11 02:01AM -0700

Title: use and examples of C++ "pwwhashmap", "memmap" and "diskmap" associative containers.
Author: pengwenwei
Email: pww71 foxmail.com
Language: c++
Platform: Windows, linux
Technology: Perfect hash algorithm
Level: Advanced
Description: A high performance map algorithm
Section MFC c++ map stl
SubSection c++ algorithm
License: (GPLv3)
 
 
Map is widely used in c++ programs. Its performance is critical to programs' performance. Especially in big data and the scenarios which can't realize data distribution and parallel processing.
 
I have been working on big data analysis for many years in telecommunition and information security industry. The data analysis is so complicated that they can't work without map. Especially in information security industry, the data is much more complicated than others. For example, ip table, mac table, telephone numbers table, dns table etc.
 
 
Currently, the STL map and Google's hash map are the most popular maps. But they have some disadvantages. The STL map is based on binary chop, which causes a bad performance. Google Hash map has the best performance at present, but it has probability of collision. For big data analysis, the collision probability is unacceptable.
 
Now I would like to publish pwwMap. It includes three different maps for different scenarios:
1. Memory Map(memMap): It has a good access speed. But its size is limited by memory size.
2. Harddisk Map(diskMap): It utilizes hard disk to store data. So it could accept much more data than memory map.
3. Hashmap(hashMap): It has the best performance and a great lookup speed, but it doesn't have 'insert' and 'delete' functionality.
 
MemMap and diskMap could be converted to hashMap by function memMap2HashMap and diskMap2HashMap. According to the test result, my algorithms' collision probability is zero. About performance, memMap has a comparable performance with google, and hashMap's performance is 100 times better than Google's hashmap.
 
In summary, pwwhash are perfect hash algorithms with zero collision probability. You can refer to following artical to find the key index and compress algorithm theory:
http://blog.csdn.net/chixinmuzi/article/details/1727195
 
Source code and documents:
https://sourceforge.net/projects/pwwhashmap/files/?source=navbar
n.musolino@gmail.com: May 11 05:45AM -0700

Your Sourceforge repository doesn't contain the source code in browse-able form. Instead, it contains a zip file.
 
You should post your source code to Sourceforge or Github in the traditional way: unzipped, and readable by any visitor to the repo.
legalize+jeeves@mail.xmission.com (Richard): May 11 05:51PM

[Please do not mail me a copy of your followup]
 
n.musolino@gmail.com spake the secret code
 
>You should post your source code to Sourceforge or Github in the
>traditional way: unzipped, and readable by any visitor to the repo.
 
...and avoid posting essentially the same content in multiple posts.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
legalize+jeeves@mail.xmission.com (Richard): May 11 05:50PM

[Please do not mail me a copy of your followup]
 
Doug Mika <dougmmika@gmail.com> spake the secret code
 
>Hi, what would be a good book that would cover intermediate to advanced
>c++ thoroughly?
 
"Modern C++ Design" by Andrei Alexandrescu
<http://amzn.to/1Exaqb4>
 
This one is a little older, but I really like it one because it opens
your eyes up to the possibility of templates as a design tool without
getting lost in template meta-programming for meta-programming's sake.
 
"Modern C++ Programming with Test-Driven Development" by Jeff Langr
<http://amzn.to/1EtNZ7F>
 
This one came out in late 2013 and is also really good. It focuses on TDD
but TDD has come late to the C++ culture (my opinion), so it's worthwhile.
The author sticks to modern C++11 throughout which is refreshing. If
you think TDD is all about testing, then read this book. (Hint: IMO
testing is a not the primary benefit of TDD.)
 
"The Boost C++ Libraries" by Boris Schaling
<http://theboostcpplibraries.com/>
 
A survey of most of the Boost libraries with short examples of each.
It's more of a brief tutorial of each library than a linear progression.
Given the scope of the libraries in Boost it's a fairly Herculean effort
to even do this much, for which Boris Schaling is to be congratulated.
It is available for free on Boris's web site, but I encourage you to
purchase an e-book edition to reward Boris for his hard efforts.
 
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)