4 ms·

Well, they haven't approved the patent yet, so give them a chance.

• easytiger 12y ago
  Yea but that linked list patent... no excuse really. I trolled the vendor once by trying to find out how much they would license the use of the linked list in my existing deployment would be. I got as far as a lawyer who was able to smell something fishy; because at the time I didn't own a company. Perhaps i should try again...
  • pbhjpbhj 12y ago
    A deployment prior to the priority date is beyond any doubt not infringing that granted patent. If you can prove the date somehow then you can take on anyone quite easily in court by simply saying "this technical implementation preceded the priority date of the patent it is alleged to infringe, see". What's the linked list patent in question (publication number preferably)?
    • SloopJon 12y ago
      I believe the patent in question is 7028023. Prior discussions: https://news.ycombinator.com/item?id=1165089 https://news.ycombinator.com/item?id=1165089 https://news.ycombinator.com/item?id=1165471 https://news.ycombinator.com/item?id=1165471 https://news.ycombinator.com/item?id=4664243 https://news.ycombinator.com/item?id=4664243
  • throwawaykf05 12y ago
    The infamous "linked list" patent didn't cover any version of linked lists we are familiar with. It covered a linked list where each node had multiple "next" pointers that allowed different traversal orders, beyond just back-and-forth like doubly-linked lists. I'm not even sure why anybody would use a single data structure to hold what should really be different lists, so I highly doubt you or anybody else is infringing that one.
    • icholy 12y ago
      skip lists?
    • chockey 12y ago
      That's just a graph.
      • throwawaykf05 12y ago
        It's not a skip-list, though it is some kind of a graph. I once tried to think of what kind of a graph it is, because it has some weird properties. It is a directed acyclic graph with 1) a fixed number of paths, 2) and each vertex occurs on each path exactly once, and 3) the paths are mutually exclusive, i.e. you cannot traverse one path half-way to a vertex and then follow another path from that vertex. I'm not sure if "mutually exclusive" is the right term... maybe a formal Graph Theoretic definition could be created based on some sort of coloring or labeling of edges. But when you put these properties together you essentially get a single structure representing multiple lists. That is, given items 1 - 5, you could arrange the pointers to traverse them in orders [1, 2, 3, 4, 5] or [1, 3, 5, 4, 2] or [5, 4, 1, 2, 3], but not [1, 5, 2] or [1, 2, 3, 2, 1]. What I don't understand is why anyone would put what is essentially a number of different lists into a single list. I see no advantages either in algorithmic complexity (traversal and addition/insertion/deletion operations are still the same complexity) or implementation. In fact, I can easily see the implementation being a nightmare. It's tricky enough deleting a node from a singly-linked list. I cannot imagine a problem this was invented to solve that could not have been solved more easily with multiple linked lists. Maybe the problem was non-technical, e.g. "get a patent to put on my résumé".
        • bonzini 12y ago
          You could use the two lists to cache respectively a pre-order and a post-order visit of a graph. E.g. if you have 1->2 1->4 2->3 3->5 4->5 the lists could be [1,2,4,3,5] and [5,4,3,2,1].
          • throwawaykf05 12y ago