[boost] Conflict with patent

Subject: [boost] Conflict with patent
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2010-07-20 11:09:44

 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_at_[hidden]