The Weird and The Wonderful

Andrew Rissing19-Jul-13 7:06

Andrew Rissing

19-Jul-13 7:06

I'm not sure if you were showcasing a weird or a wonderful here, because the second method won't perform as expected.

Brisingr Aerowing wrote:
public static void RemoveAllBut(this ICollection source, params object[] notRemove)
{
RemoveAllBut<object>(source.OfType<object>().ToArray(), notRemove);
}

Richard Deeming19-Jul-13 7:20

Richard Deeming

19-Jul-13 7:20

With any decent implementation of ICollection<T> your method will produce an InvalidOperationException with the message: "Collection was modified; enumeration operation may not execute."

You'll need to store the items to remove in a separate list, and remove them outside of any enumeration of the source list:

public static void RemoveAllBut<T>(this ICollection<T> source, params T[] notRemove)
{
   var itemsToRemove = source.Except(notRemove).ToList();
   itemsToRemove.ForEach(item => source.Remove(item));
}

As Andrew pointed out, your non-generic version won't work. It would need to be:

public static void RemoveAllBut(this IList source, params object[] notRemove)
{
   var itemsToRemove = source.Cast<object>().Except(notRemove).ToList();
   itemsToRemove.ForEach(source.Remove);
}

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Gary Wheeler19-Jul-13 7:21

Gary Wheeler

19-Jul-13 7:21

At least in .NET 3.5, your first function will throw an exception, since you are modifying the collection being enumerated.

Software Zen: delete this;

TnTinMn19-Jul-13 8:00

TnTinMn

19-Jul-13 8:00

In addition to the comments above, each of those Remove statements will incur an array copy cost. Count the occurrence of each item in notRemove, clear the collection, then add the items in notRemove by their respective counts.

Possibly something like this:

public static void RemoveAllBut<T>(this ICollection<T> source, params T[] notRemove)
{
    Int32[] counts = new Int32[notRemove.Length];
    EqualityComparer<T> comparer = EqualityComparer<T>.Default;

    foreach (T itm in source)
    {
        for (Int32 i = 0; i <= counts.Length - 1; i++)
        {
            if (comparer.Equals(notRemove[i], itm))
            {
                counts[i] += 1;
                break;
            }
        }
    }
    source.Clear();
    for (Int32 i = 0; i <= counts.Length - 1; i++)
    {
        for (Int32 j = 1; j <= counts[i]; j++)
        {
            source.Add(notRemove[i]);
        }
    }

}

Lutosław19-Jul-13 8:08

Lutosław

19-Jul-13 8:08

Posting in this particular forum triggers a find-what-is-bad thinking. Sorry. Wink | ;)

1. It's O(n^3) which is not good. Did you consider working on sorted collections? Then it would be just O(n). (more precisely, O(max{n,m})).
Why O(n^3):
1. foreach loop
2. Contains method which searches notRemove
3. Remove(itm) method which has to find index of itm (in worst case, n calls to Equals method) and, if it's an array list, it has to shift all elements by one which makes it even worse.
Besides, I though that you cannot edit a collection inside foreach.

2. I method 2: Why copy all elements to a new array? Without it, it would be memory complexity of Ω(1), in situ operation. Now it's Ω(n) because it allocates a new array in the process.

3. Formatting horror, but maybe it was screwed up during pastying*.

if (notRemove.Contains(itm)) continue;
    source.Remove(itm);

Shouldn't it be:

if (notRemove.Contains(itm))
     continue;
source.Remove(itm);

IF it is known that all items in notRemoves appear in the source exactly once, then what about:

public static void RemoveAllBut<T>(this ICollection<T> source, params T[] notRemove)
{
  source.Clear();
  foreach(var x in notRemove) 
    source.Add(x);
  // because we don't have source.AddAll, unfortunately
}

which is O(m) and Ω(1).
* -- "pastying" - is it a correct spelling? (derived from a verb "paste").

Greetings - Jacek

Richard Deeming19-Jul-13 8:55

Richard Deeming

19-Jul-13 8:55

Jacek Gajek wrote:
* -- "pastying" - is it a correct spelling? (derived from a verb "paste").

The word you're looking for is "pasting".

However, I like the idea of using "pastying" when referring to anything connected to the Cornish foodstuff[^]. Smile | :)

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Lutosław19-Jul-13 9:06

Lutosław

19-Jul-13 9:06

Thanks. Finally I know it. I didn't write "pasting" because it seemed to be related to "the past" and made no sense to me (or did it?).

Greetings - Jacek

PIEBALDconsult19-Jul-13 8:09

PIEBALDconsult

19-Jul-13 8:09

Yeah, what they said. Plus I'd avoid ToArray.

And see whether or not a HashSet might be of use:

HashSet<T>.IntersectWith Method[^]

Or not, whatever. Sigh | :sigh:

lewax0019-Jul-13 9:35

lewax00

19-Jul-13 9:35

Brisingr Aerowing wrote:
Message ~~Automatically~~ Manually Removed

FTFY

ZurdoDev19-Jul-13 10:22

ZurdoDev

19-Jul-13 10:22

There was no need to remove your message. Your idea was a good one but I am guessing you didn't test it. And with all of the egos on this site (not saying anyone who responded necessarily has one) if you say something wrong or that can be perceived as wrong there are many who jump at the opportunity to attack. Lots of vultures.

Smile | :)

There are only 10 types of people in the world, those who understand binary and those who don't.

lewax0021-Jul-13 11:03

lewax00

21-Jul-13 11:03

And in this case, most of the posts looked like they were trying to help (except mine Poke tongue | ;-P

This one is for the Java experts

pkfox29-Jul-13 22:26

pkfox

29-Jul-13 22:26

As CM says "Leave the egos at the door"

When the going gets weird the weird turn pro - Hunter S Thompson RIP

Dennis_E18-Jul-13 0:56

Dennis_E

18-Jul-13 0:56

I bumped into this Java code in a project I'm supposed to 'make work correctly'.
Every method in the class works like this. (userBase checks if the user with the given email is allowed to execute the action and then fetched stuff out of the database.)
How many weird things can you spot? It's not hilarious or something, just weird.

Java

public class Controller
{
    //Lots of other methods left out...

    public User getUserByID(String email, long id) throws Exception
    {
        final ObjectHolder<User> userHolder = new ObjectHolder();
        final AtomicBoolean done = new AtomicBoolean(false);

        userBase.handleAction(email, new GetUserByIDAction(), new GetUserByIDActionExecutionDetails(id), new IActionListener<User>()
        {
            @Override
            public void actionFinished(User user) throws Exception
            {
                synchronized (done)
                {
                    userHolder.set(user);
                    done.set(true);
                    done.notifyAll();
                }
            }

            @Override
            public void exception(Exception exception) throws Exception
            {
                synchronized (done)
                {
                    done.set(true);
                    done.notifyAll();
                    throw exception;
                }
            }
        });
        
        synchronized (done)
        {
            while (!done.get()) {
                done.wait(100);
            }

            if (userHolder.get() == null) {
                throw new UserNotFoundException(id);
            } else {
                return userHolder.get();
            }
        }
    }
    
    private class ObjectHolder<T>
    {
        private T t;
        
        public ObjectHolder(T t)
        {
            set(t);
        }
        
        public void set(T t)
        {
            this.t = t;
        }
        
        public T get()
        {
            return t;
        }
    }

}

Nagy Vilmos18-Jul-13 1:52

Nagy Vilmos

18-Jul-13 1:52

WTE does ObjectHolder do? That I can see no value to.
The userBase model is common. You use an execution container to encapsulate permissions etc. The use of an anonymous class is, however, poor work.
Why aren't the methods synchronized, instead of filling the method with a synchronise block? Damned weird, but there may be a reason.

Reality is an illusion caused by a lack of alcohol
"Nagy, you have won the internets." - Keith Barrow

Fredrik Bornander18-Jul-13 2:10

Fredrik Bornander

18-Jul-13 2:10

I guess ObjectHolder is to make the variable assignable from inside the anonymous code as that can only use final variables.

My Android apps in Google Play; Oakmead Apps

Dennis_E18-Jul-13 2:27

Dennis_E

18-Jul-13 2:27

Yes, i thought that's what it was for.
However, I was more puzzled by:
- The double synchronization of the AtomicBoolean. It is synchronized in the method itself (waiting for it to become true) AND in the listener. Since the method returns, something is smelly.
- The throwing of 2 exceptions (one in the listener and the other in the method)

Nagy Vilmos18-Jul-13 3:54

Nagy Vilmos

18-Jul-13 3:54

I wanted to mention that, the point of an AtomicBoolean is that it doesn't need synchronisation because it's, well, atomic. Big Grin | :-D

Reality is an illusion caused by a lack of alcohol
"Nagy, you have won the internets." - Keith Barrow

svella23-Jul-13 3:57

svella

23-Jul-13 3:57

Nagy Vilmos wrote:
I wanted to mention that, the point of an AtomicBoolean is that it doesn't need synchronisation because it's, well, atomic.

The synchronization isn't necessarily for the setting/getting, but for the wait()/notifyAll(). They are using the variable both as a flag and a synchronization object, though it is a little unusual to wait with a relatively short timeout and then loop if you are going to signal the monitor as well.

I personally would have used CountDownLatch or CyclicBarrier.

Brisingr Aerowing18-Jul-13 6:40

Brisingr Aerowing

18-Jul-13 6:40

brisingr_aerowing@Gryphon-PC $ rake in_the_dough

Raking in the dough

brisingr_aerowing@Gryphon-PC $ make lots_of_money

Making lots_of_money

AlphaDeltaTheta18-Jul-13 15:53

AlphaDeltaTheta

18-Jul-13 15:53

WTE the coder has done? AtomicBoolean is already atomic and doesn't need a syncd block

Beauty cannot be defined by abscissas and ordinates; neither are circles and ellipses created by their geometrical formulas.

~ Carl von Clausewitz ~

Source

ExcellentOrg22-Jul-13 21:30

ExcellentOrg

22-Jul-13 21:30

Believe it or not, this reminds me of one UI programmed in Java that I saw about a year ago. It was demo of a software meant for lawyers. Somewhere in UI, there was was a search window and the user was expected to enter the Primary Key (a 10 digit number), the name of person and part of his phone number.