check if 2 linked list have the same elements regardless of order

Question

Is there any way to check if 2 linked lists have the same elements regardless of order.

edit question: I have fixed the code and given some more details:

this is the method that compares 2 lists

 compare: object2
     ^ ((mylist asBag) = ((objetc2 getList) asBag)).

the method belongs to the class myClass that has a field : myLList. myList is a linkedList of type element.

I have compiled it in the workspace:

  a: = element new id:1.
  b:= element new id:2.
  c:=element new id:3.

  d: = element new id:1.
  e:= element new id:2.
  f:=element new id:3.

  elements1 := myClass new. 
  elements addFirst:a.
   elements addFirst:b.
   elements addFirst:c.

   elements2 := myClass new. 
   elements addFirst:d.
   elements addFirst:e.
   elements addFirst:f. 
   Transcript show: (elements1 compare:elements2).

so I am getting false.. seems like it checks for equality by reference rather than equality by value..

So I think the correct question to ask would be: how can I compare 2 Bags by value? I have tried the '=='..but it also returned false.

Answer 1

EDIT: The question changed too much - I think it deserves a new question for itself.

The whole problem here is that (element new id: 1) = (element new id: 1) is giving you false. Unless it's particular class (or superclasses) redefine it, the = message is resolved comparing by identity (==) by default. That's why your code only works with a collection being compared with itself.

Test it with, for example, lists of numbers (which have the = method redefined to reflect what humans understand by numeric equality), and it will work.

You should redefine your element's class' = (and hashCode) methods for this to work.

Smalltalk handles everything by reference: all there exist is an object, which know (reference) other objects.

---

It would be wrong to say that two lists are equivalent if they are in different order, as the order is part of what a list means. A list without an order is what we call a bag.

The asBag message (as all of the other as<anotherCollectionType> messages) return a new collection of the named type with all the elements of the receiver. So, #(1 2 3 2) is an Array of four elements, and #(1 2 3 2) asBag is a bag containing those four elements. As it's a Bag, it doesn't have any particular order.

When you do bagA := Bag new. you are creating a new Bag instance, and reference it with bagA variable. But then you do bagA := myList asBag, so you lose the reference to the previous bag - the first assignment doesn't do anything useful in your code, as you don't use that bag.

Saying aBool ifTrue: [^true] ifFalse: [^false] has exactly the same meaning as saying ^aBool - so we prefer just to say that. And, as you only create those two new bags to compare them, you could simplify your whole method like this:

compareTo: anotherList
  ^ myList asBag = anotherList asBag

Read it out loud: this object (whatever it is) compares to another list if it's list without considering order is the same than the other list without order.

The name compareTo: is kind of weird for returning a boolean (containsSameElements: would be more descriptive), but you get the point much faster with this code.

---

Just to be precise about your questions:

1) It doesn't work because you're comparing bag1 and bag2, but just defined bagA and bagB.

2) It's not efficient to create those two extra bags just because, and to send the senseless ifTrue: message, but other way it's OK. You may implement a better way to compare the lists, but it's way better to rely on the implementation of asBag and the Bag's = message being performant.

3) I think you could see the asBag source code, but, yes, you can assume it to be something like:

Collection>>asBag
  |instance|
  instance := Bag new.
  instance addAll: self.
  ^instance

And, of course, the addAll: method could be:

Collection>>addAll: anotherCollection
  anotherCollection do: [ :element | self add: element ]

So, yes - it creates a new Bag with all the receiver's elements.

Answer 2

mgarciaisaia's answer was good... maybe too good! This may sound harsh, but I want you to succeed if you're serious about learning, so I reiterate my suggestion from another question that you pick up a good Smalltalk fundamentals textbook immediately. Depending on indulgent do-gooders to rework your nonsensical snippets into workable code is a very inefficient way to learn to program ;)

EDIT: The question has changed dramatically. The following spoke to the original three-part question, so I paraphrased the original questions inline.

1. Q: What is the problem? A: The problem is lack of fundamental Smalltalk understanding.
2. Q: Is converting to bags an efficient way to make the comparison? A: Although it's probably not efficient, don't worry about that now. In general, and especially at the beginning when you don't have a good intuition about it, avoid premature optimization - "make it work", and then only "make it fast" if justified by real-world profiling.
3. Q: How does #asBag work? A: The implementation of #asBag is available in the same living world as your own code. The best way to learn is to view the implementation directly (perhaps by "browsing implementors" if you aren't sure where it's defined") and answer your own question!! If you can't understand that implementation, see #1.