I am a teacher of programming in a Technical Professional Training School in Madrid ( Spain). I had wrote a counter balanced red-black tree in C++. The balanced trees have a counter in each node, which represent the number of nodes under it including itself. This counter permit to access to the nodes by their position in the tree. Due to this you can use a counter tree as a vector, access by position and insert and delete by position. Of course, the iterators of this trees have random access, an you can add or decrement the iterators any value . vector_tree<int>::iterator Alfa, Beta ; Alfa = Beta + 17 ; The algorithms are built from zero,without any book or article, because you need in each operation , not only modify the pointers, you must modify the counters too. The speed is good. In the worst case the delay respect to the equivalent STL functions is around 20%. I had checked in windows ( Visual Studio ) and Linux (GCC). My version have a 5 classes interface : vector_tree : This class is a counter balanced red-black tree and have the same interface than the STL class vector. The insertion , deletion and access to elements are log(N) operations. The other four classes are set , multiset , map and multimap. Internally they have a vector_tree. They have the same interface than the STL classes, plus the access by position and the random access iterators. My idea is to send you to examine , and if you think useful, make a new boost library. Today is finished to 95% . I hope have all finished by the first weeks of September. I am writing you because today, looking for other think I discovered a US patent “Positional access using a B-tree” ( US patent Number 7,120,637B2 Oct, 10, 2006), and I don't know if this patent prevent the publication of the code in your library, because you can consider the red-black trees an simplification of B-trees If prevent, and you don't have an idea about the utility of the code, I will stop the develop, and I will spend my time with new ideas The idea about the counter trees you can find in “The art of computer Programming “ Donald Knuth, and I have a previous version of this code wrote 10 years ago and presented in my exposition in the Oposiciones a Catedrático de Informática ( Madrid 2001) If you are interested in the code, mail me and I will send you. Francisco José Tapia E-Mail : fjtapia@gmail.com
Le 20/07/2010 16:09, Francisco José Tapia wrote:
I am writing you because today, looking for other think I discovered a US patent “Positional access using a B-tree” ( US patent Number 7,120,637B2 Oct, 10, 2006), and I don't know if this patent prevent the publication of the code in your library, because you can consider the red-black trees an simplification of B-trees If prevent, and you don't have an idea about the utility of the code, I will stop the develop, and I will spend my time with new ideas
The idea about the counter trees you can find in “The art of computer Programming “ Donald Knuth, and I have a previous version of this code wrote 10 years ago and presented in my exposition in the Oposiciones a Catedrático de Informática ( Madrid 2001)
Patents become invalid if you can demonstrate prior art. I wouldn't worry too much about it in this case.
Mathias Gaunard wrote:
Patents become invalid if you can demonstrate prior art. I wouldn't worry too much about it in this case.
Patent invalidation is a very difficult thing to do, and not a good way to build a defense. Attempting to invalidate a patent can bankrupt you with legal fees, and finding prior art that legally works can be tricky. Also remember that to invalidate a patent, you will have to convince a jury -- a jury of people who likely have no technical knowledge -- that your algorithm does not infringe on a patent, and that's very difficult. You'll have to go through every claim in the patent, and every dependent claim, and make sure that the prior art either eliminates those claims, or that you are not infringing on that claim. Certainly having prior art is good, but I'm just saying it's important to be aware of the legal system, and that even though you have what probably is prior art, and are probably right, attempting to invalidate a patent can lead you down a very difficult road. It's unfortunate that the system works this way.
Le 20/07/2010 21:19, schnarf@optonline.net wrote:
Mathias Gaunard wrote:
Patents become invalid if you can demonstrate prior art. I wouldn't worry too much about it in this case.
Patent invalidation is a very difficult thing to do, and not a good way to build a defense. Attempting to invalidate a patent can bankrupt you with legal fees, and finding prior art that legally works can be tricky.
It only matters if the patent holder tries to enforce the patent, which is realistically not going to happen in this case, because they would ultimately lose. The relation to his work is fairly remote, there is a massive amount of prior art (it's in TAoCP for god's sake), and it's a quite trivial addition to a widely known technique. For these reasons, my opinion is that the Boost community shouldn't care about that particular patent if the code was ever considered for review. Of course that opinion is just that of a simple developer with no corporate experience, and I'm far from being a lawyer. I do not know if there ever have been pieces of code rejected due to such far-fetched patents. I think there were discussions with a few atomic concurrency things and people managed to work around the patents, so surely some people know about subject very well.
On Jul 20, 2010, at 6:51 PM, Mathias Gaunard wrote:
It only matters if the patent holder tries to enforce the patent, which is realistically not going to happen in this case, because they would ultimately lose. The relation to his work is fairly remote, there is a massive amount of prior art (it's in TAoCP for god's sake), and it's a quite trivial addition to a widely known technique.
For these reasons, my opinion is that the Boost community shouldn't care about that particular patent if the code was ever considered for review. Of course that opinion is just that of a simple developer with no corporate experience, and I'm far from being a lawyer.
I do not know if there ever have been pieces of code rejected due to such far-fetched patents. I think there were discussions with a few atomic concurrency things and people managed to work around the patents, so surely some people know about subject very well.
I agree with you for sure. I just wanted to make the point that trying to invalidate a patent is a very difficult thing to do. As software developers, we can read a patent and find prior art and see very clearly that the patent ought not to be valid. My point is just that the legal system is not as simple as that, and it's important to be aware of the risks.
On Jul 20, 2010, at 8:22 PM, Aaron Wishnick wrote:
I just wanted to make the point that trying to invalidate a patent is a very difficult thing to do. As software developers, we can read a patent and find prior art and see very clearly that the patent ought not to be valid. My point is just that the legal system is not as simple as that, and it's important to be aware of the risks.
For sure, it's a painful process. Also, unless I'm mistaken, none of us on this list are lawyers. If you are actually concerned about this, you should talk to one. -- David Abrahams BoostPro Computing http://boostpro.com
Mathias Gaunard wrote:
Le 20/07/2010 21:19, schnarf@optonline.net wrote:
Mathias Gaunard wrote:
Patents become invalid if you can demonstrate prior art. I wouldn't worry too much about it in this case.
Patent invalidation is a very difficult thing to do, and not a good way to build a defense. Attempting to invalidate a patent can bankrupt you with legal fees, and finding prior art that legally works can be tricky.
It only matters if the patent holder tries to enforce the patent, which is realistically not going to happen in this case, because they would ultimately lose. The relation to his work is fairly remote, there is a massive amount of prior art (it's in TAoCP for god's sake), and it's a quite trivial addition to a widely known technique.
Are we sure that the patent holder is in no way associated with SCO? :-) Some parties don't care about losing, because they have nothing more to lose. The odd chance of winning against all odds can perhaps be worth 10 years in court? Bo Persson
Thank you very much. I will finish the code, and if the community think useful, create a new boost library 2010/7/20 Mathias Gaunard <mathias.gaunard@ens-lyon.org>
Le 20/07/2010 16:09, Francisco José Tapia wrote:
I am writing you because today, looking for other think I discovered a US patent “Positional access using a B-tree” ( US patent Number 7,120,637B2 Oct, 10, 2006), and I don't know if this patent prevent the publication of the code in your library, because you can consider the red-black trees an simplification of B-trees If prevent, and you don't have an idea about the utility of the code, I will stop the develop, and I will spend my time with new ideas
The idea about the counter trees you can find in “The art of computer Programming “ Donald Knuth, and I have a previous version of this code wrote 10 years ago and presented in my exposition in the Oposiciones a Catedrático de Informática ( Madrid 2001)
Patents become invalid if you can demonstrate prior art. I wouldn't worry too much about it in this case.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
From: Francisco José Tapia <fjtapia@gmail.com> Subject: [boost] Conflict with patent
I am a teacher of programming in a Technical Professional Training School in Madrid ( Spain).
Few notes in addition to what was said: 1. As you and others had clearly shown the idea and the code was created a long before this patent. So if "patent holders" would like to sue you they have no basis to do this, and likely they would loose their patent in such case. In such case, if this "patent" somehow related to the code your write they will shoot themselves a foot as it can't be valid due to prior existence. 2. They need to sue you in US. They US patent laws are not valid in Spain. and AFAIK such "patent" is not even patentable in Europe. 3. If everyone would search full patents list to find out if his idea is patented in US he will spend much more time on searching then coding. My suggestion forget about all this patent insanity... Especially it has no real basis and somehow may be relevant in US only.
I am writing you because today, looking for other think I discovered a US patent “Positional access using a B-tree” ( US patent Number 7,120,637B2 Oct, 10, 2006), and I don't know if this patent prevent the publication of the code in your library,
Even if the patent had basis (which it has not) it does not prevent publishing the code as you are not under jurisdiction of US, so actually this code can be fully and legally used outside of US. As for example MP3 encoders can be used and distributed outside US without limitations. And if you are worried about you may add a notice that ensures that users would be aware of the fact that the code may be violate some patents (which it does not)
The idea about the counter trees you can find in “The art of computer Programming “ Donald Knuth, and I have a previous version of this code wrote 10 years ago and presented in my exposition in the Oposiciones a Catedrático de Informática ( Madrid 2001)
In such case the patent holders should be afraid of you and not you of them :-) My $0.02 Artyom
Artyom wrote:
3. If everyone would search full patents list to find out if his idea is patented in US he will spend much more time on searching then coding.
On a side note, I'd like to point out that even if you do spend the time searching the patents list and find some patent that *possibly* covers your work, then it is a bad idea to write to a public list describing your work and identifying the patent. All these lists are easily searchable and your legal position can't be better if it can be shown you were aware of the patent.
On Wed, 2010-07-21 at 08:32 +0100, John Reid wrote:
Artyom wrote:
3. If everyone would search full patents list to find out if his idea is patented in US he will spend much more time on searching then coding.
On a side note, I'd like to point out that even if you do spend the time searching the patents list and find some patent that *possibly* covers your work, then it is a bad idea to write to a public list describing your work and identifying the patent. All these lists are easily searchable and your legal position can't be better if it can be shown you were aware of the patent.
Maybe. On the other hand, a credible invalidity argument does help in avoiding willful infringement. In that vein I thought it might be worth mentioning this http://web.archive.org/web/20010508065835/http://www.chiark.greenend.org.uk/... ianal
Darryl Green wrote:
On Wed, 2010-07-21 at 08:32 +0100, John Reid wrote:
Artyom wrote:
3. If everyone would search full patents list to find out if his idea is patented in US he will spend much more time on searching then coding. On a side note, I'd like to point out that even if you do spend the time searching the patents list and find some patent that *possibly* covers your work, then it is a bad idea to write to a public list describing your work and identifying the patent. All these lists are easily searchable and your legal position can't be better if it can be shown you were aware of the patent.
Maybe. On the other hand, a credible invalidity argument does help in avoiding willful infringement. In that vein I thought it might be worth mentioning this http://web.archive.org/web/20010508065835/http://www.chiark.greenend.org.uk/...
How can wilfull infringement be shown, if no one knows you were of the patent?
John Reid wrote:
Darryl Green wrote:
On Wed, 2010-07-21 at 08:32 +0100, John Reid wrote:
Artyom wrote:
3. If everyone would search full patents list to find out if his idea is patented in US he will spend much more time on searching then coding. On a side note, I'd like to point out that even if you do spend the time searching the patents list and find some patent that *possibly* covers your work, then it is a bad idea to write to a public list describing your work and identifying the patent. All these lists are easily searchable and your legal position can't be better if it can be shown you were aware of the patent.
Maybe. On the other hand, a credible invalidity argument does help in avoiding willful infringement. In that vein I thought it might be worth mentioning this http://web.archive.org/web/20010508065835/http://www.chiark.greenend.org.uk/...
How can wilfull infringement be shown, if no one knows you were of the patent? Sorry that should read:
How can wilfull infringement be shown, if no one knows you were aware of the patent?
On Thu, 2010-07-22 at 18:42 +0100, John Reid wrote:
John Reid wrote:
Darryl Green wrote:
On Wed, 2010-07-21 at 08:32 +0100, John Reid wrote:
... it is a bad idea to write to a public list describing your work and identifying the patent. All these lists are easily searchable and your legal position can't be better if it can be shown you were aware of the patent.
Maybe. On the other hand, a credible invalidity argument does help in avoiding willful infringement. In that vein I thought it might be worth mentioning this http://web.archive.org/web/20010508065835/http://www.chiark.greenend.org.uk/...
How can wilfull infringement be shown, if no one knows you were aware of the patent?
It can't. I was only suggesting that your concern was presumably around the willful infringement issue and that (given that the work is already being discussed on a public list) a constructive thing to do would be to provide a credible invalidity argument (something the OP would seem to have started to do in hist first post, but there wasn't any citation of any public record/disclosure of his earlier work). The "maybe" is that I am personally unsure, in the circumstances we are talking about (software patents in general, and broad claims on algorithms not specific to a particular/narrow field of application in particular) whether the risk to an individual in the OPs circumstances is actually significant. This applies even more when that individual is Spanish, not in the US. Beyond all that, I think it is helpful that these sorts of issues are discussed openly, when they relate to submission of open source code (to Boost or anywhere else). I also belatedly realised that the patent examiner for the patent in question had cited the same web page I did. This has its good and bad points... Looking at it optimistically, unless Francisco's code uses something not disclosed on that page, but that is disclosed in the patent claims, it would seem there is no issue. But - whatever - ianal - don't rely on any of this....
participants (11)
-
Aaron Wishnick -
Artyom -
Bo Persson -
Darryl Green -
David Abrahams -
Francisco José Tapia -
John Maddock -
John Reid -
Mathias Gaunard -
Robert Ramey -
schnarf＠optonline.net