5 ms·

For the average layperson, you are correct and I'll probably use this analogy myself in conversation. Legally, however, your analogy doesn't hold water. Yes, it

by delinka 16y ago

For the average layperson, you are correct and I'll probably use this analogy myself in conversation. Legally, however, your analogy doesn't hold water. Yes, it's an analogy and many times they aren't 100% analogous, but I feel it's worth pointing out the legalistic differences. And here's the reason: Aunt Marge isn't using a linked list. That is, each coupon doesn't point to the next coupon in the list. It's simply a collection (or array) of coupons. Now, let's bring this back to a point that's somewhat more relevant. If you did implement something more analogous to Aunt Marge's coupon collection (say an array), and trimmed out items as the code noticed they were expired, would you infringe this patent? Maybe not. I haven't tried reading the details of the patent, but if the article is correct and if, as in every other case, every detail of the patent matters, then I'd wager your array-with-expiring-items would not infringe. And that is what's wrong with software patents. Maybe we've been expiring items from collections, dictionaries and arrays for a long time. But suddenly, apply it to a linked list and you've infringed the patent. Nonsense. [spelling edit]

viraptor 16y ago
Example that is even more silly: Project A contains a generic collection. Project B contains an abstraction of objects with expiry times. Project C instantiates A's collection for B's objects. Now assuming A implements the collection using linked lists and C uses A and B as black box, linked libraries, does anyone infringe on the patent?
- caf 16y ago
  No, because the key point of this patent appears to be removing expired objects as a side-effect of searching the linked list for an unrelated object. So unless Project A's generic collection implements an optional callback that is called on every object seen while searching the collection, project C uses that callback to delete expired objects, you'd seem to be in the clear.
jws 16y ago
A linked list of course has no direct analogy in the physical world, but I think the analogy has a workable definition of "next(couponX)" which is "put your finger on the back of couponX, move your finger away from yourself, if you touch the face of another coupon, that is the next coupon". The slot is not an array, it is not directly accessible by index number or key. It is close to a doubly linked list with a head and tail pointer, but it has more operations than a linked list though. You can flip through by "a bunch" and easily start at a randomish middle point which doesn't map back to linked lists, but also isn't important for this example.
- droz 16y ago
  "A linked list of course has no direct analogy in the physical world" First few that come to mind: conga line, necklace, bike chain and DNA. Tangentially, lines of people forming a queue or a push down stack of dishes or the number you pick at the deli counter for your turn forming a circular buffer. All of these are examples of physical world linked lists.
  - jws 16y ago
    I like these. You can embody the "link" nature, but the physical analogies also gain operations that make them not match linked list[1], such as: • The examples all seem to include back links as well. • Most of them you can access an interior element in constant time. • Most of them you can get a size estimate without traversing. • The dishes are more stack like. Traversal is destructive, but it doesn't add operations. (I think) • The deli numbers give you a constant time "distance between" operator (unless the deli has lost a lot of the tags), and require a global method dispatch to find "next". 37? 37?… 38? [1] Somewhere in the '80s, Dr. Roman[2] was explaining binary search to a class of 'us' and started to use a phone book analogy, until he realized that people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. That's stuck with me as a caution of the difficulty of analogy. [2] Oh look, he is department chair now. Well done! (Warning to students: if you are having trouble in CSE425S (formerly CS 455) with the programming-language-of-the-week being prolog, and you figure out how to build yourself variables, he will see through you and give you a bad grade, my poor little grid bugs.)
    - cpeterso 16y ago
      > people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. Perhaps a better analogy would be binary searching in a phone book or dictionary for a foreign language.
      - arghnoname 16y ago
        A reverse directory (sorted by phone number) probably defeats frequency knowledge.

by delinka 16y ago

viraptor 16y ago

Example that is even more silly: Project A contains a generic collection. Project B contains an abstraction of objects with expiry times. Project C instantiates A's collection for B's objects. Now assuming A implements the collection using linked lists and C uses A and B as black box, linked libraries, does anyone infringe on the patent?

caf 16y ago
No, because the key point of this patent appears to be removing expired objects as a side-effect of searching the linked list for an unrelated object. So unless Project A's generic collection implements an optional callback that is called on every object seen while searching the collection, project C uses that callback to delete expired objects, you'd seem to be in the clear.

jws 16y ago

A linked list of course has no direct analogy in the physical world, but I think the analogy has a workable definition of "next(couponX)" which is "put your finger on the back of couponX, move your finger away from yourself, if you touch the face of another coupon, that is the next coupon". The slot is not an array, it is not directly accessible by index number or key. It is close to a doubly linked list with a head and tail pointer, but it has more operations than a linked list though. You can flip through by "a bunch" and easily start at a randomish middle point which doesn't map back to linked lists, but also isn't important for this example.

droz 16y ago
"A linked list of course has no direct analogy in the physical world" First few that come to mind: conga line, necklace, bike chain and DNA. Tangentially, lines of people forming a queue or a push down stack of dishes or the number you pick at the deli counter for your turn forming a circular buffer. All of these are examples of physical world linked lists.
- jws 16y ago
  I like these. You can embody the "link" nature, but the physical analogies also gain operations that make them not match linked list[1], such as: • The examples all seem to include back links as well. • Most of them you can access an interior element in constant time. • Most of them you can get a size estimate without traversing. • The dishes are more stack like. Traversal is destructive, but it doesn't add operations. (I think) • The deli numbers give you a constant time "distance between" operator (unless the deli has lost a lot of the tags), and require a global method dispatch to find "next". 37? 37?… 38? [1] Somewhere in the '80s, Dr. Roman[2] was explaining binary search to a class of 'us' and started to use a phone book analogy, until he realized that people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. That's stuck with me as a caution of the difficulty of analogy. [2] Oh look, he is department chair now. Well done! (Warning to students: if you are having trouble in CSE425S (formerly CS 455) with the programming-language-of-the-week being prolog, and you figure out how to build yourself variables, he will see through you and give you a bad grade, my poor little grid bugs.)
  - cpeterso 16y ago
    > people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. Perhaps a better analogy would be binary searching in a phone book or dictionary for a foreign language.
    - arghnoname 16y ago
      A reverse directory (sorted by phone number) probably defeats frequency knowledge.