Default Dictionary

[jaegs]

See if you like it...
https://github.com/jaegs/MultiList/blob/master/DefaultDict.cobra

[Charles]

-- I like your count example. Very nice.

-- I would probably call the class DefaultDictionary instead of DefaultDict in order to match up better with the base classe.

-- As you point out, there are additional initializers in the base class that should be covered.

-- I disagree with this statement;

/# Should modify get(key as TKey, default as TValue) in ExtendDictionary.cobra
 # to throw NotImplementedException() if the type is a DefaultDict
 #/

There is no reason why the .get convenience method should throw an exception just because it's used on a DefaultDict. While it's less likely to be used, there is nothing invalid about it. When used, it means that the call site wants a specific default.

-- In my own applications, I rarely record the default back into the dictionary because I may change what the default is in the future. Typically, I want access of a missing key to imply getting the default at the time of access rather than what the default was in the past. I'm speaking mostly in terms of config files. Of course, recording has a speed advantage. And my stated preference may not be suitable for many applications.

A possibility is to have a "pro willRecordDefaults from var as bool".

-- For list literals, you don't need the line continuation character. Same with dictionaries and sets.

-- In the future, I plan on investigating the inference of type args for object instantiation. For example, Pair(5, 's') instead of Pair<of int, String>(5, 's'). Wouldn't that be nice?

-- Overall, looks good.

[jaegs]

I changed the class name and added more constructors. When I try to test the commented out code, the tester crashes. Perhaps you could take a look.

A possibility is to have a "pro willRecordDefaults from var as bool".

If I understand you correctly, this field would go in DefaultDictionary and there would be something like the extension method

def get(key as TKey, default as TValue) as TValue

that would insert the default value if willRecordDefaults is true. Except the method name would have to be different than "get" because the extension method cannot be overridden.

Consider the test case with the Dictionary of Lists. The new list is constructed by the defaultFactory only if the value doesn't exists. On the other hand, something like get('blue', []) will construct a list on every call.

I've also implemented a MultiSet class (link), except I called it Bag because MultiSet isn't the best name. 'Multi' would seem to make the class similar to MultiList and 'Set' would seem to make it similar to Set, neither of which are true. Bag.cobra is mostly inspired from the Python class Counter (link).

[Charles]

-- I'll look at the crash you mentioned.

-- My comments about .willRecordDefaults were separate from everything else. I wasn't thinking about the .get extension method, just the DefaultDict class in general. You are correct that .get constructs a default value on every call. That's basically its semantics and there isn't much we can change there. We could however contemplate an overload that takes a lambda and another one that takes a lambda and a record flag. Or maybe we're overguessing what people will need/want/use.

-- I skimmed through Bag. Here are things I noticed, but as I say, I was only skimming:

-- You linked to:
http://en.wikipedia.org/wiki/Multiset
Which is the math topic. Did you want to link to the comp sci topic instead?
http://en.wikipedia.org/wiki/Set_(computer_science)#Multiset

-- Re: name, Apple's name "CountedSet" seems like the best of all. "Bag" tells me almost nothing.

-- Why not have .counts return Pair<of T, int>* ? This is the type of thing I built it for!

-- Um, "cue enumerate" works? What?

-- The .add methods use = instead of +=. Isn't that wrong or do I misunderstand the purpose of the class (or the methods)? If it is wrong, you should add a test case first that fails and then fix. I guess I'm thinking about .add like in List where there is growth. Here it is assignment.

-- Hmm should a .remove('foo', 5) throw an exception if the bag has only 3 of them? If not, maybe the return value of "def remove(item, num) as bool" should be an int--how many values were removed. So instead of return values (false, true) you get numbers (0, 1, 2, 3, ...).

-- I think .removeAll is not correct.

-- There is a doc string that says "MultiList" when it means to say "Bag" (or CountedSet).

-- I suppose it is time for Cobra to allow an indentifier after "test":

#removeAll
test
    bag = Bag<of char>('mississippi')
    bag.removeAll(c'i')
    assert not bag.contains(c'i')
# -->
test removeAll
    bag = Bag<of char>('mississippi')
    bag.removeAll(c'i')
    assert not bag.contains(c'i')

Yes?

This paves the way for things like;
-- tell the test runner to run particular tests
-- or tell the test runner to exclude particular tests
-- parameterized tests which have their utility

I could probably sneak in the syntax for 0.9 even if we don't offer anything useful around it for now.

[Charles]

I changed the class name and added more constructors. When I try to test the commented out code, the tester crashes. Perhaps you could take a look.

It's a stack overflow. Your indexer uses .tryGetValue and your .tryGetValue uses the indexer. You could break out a _get method or duplicate the few lines of code.

Btw I have found that Mono is not very good at reporting a stack overflow like .NET is. But then I now know that most of the time, a crashed Cobra program on Mono means stack overflow. However, you can confirm with this:

Code: Select all

$ cobra -detailed-stack-trace DefaultDictionary.cobra
Cobra detected stack overflow:
  Last 20 frames:
    480. def DefaultDictionary<of,>.tryGetValue at line 50
    481. def DefaultDictionary<of,>.[].get at line 41
    482. def DefaultDictionary<of,>.tryGetValue at line 50
    483. def DefaultDictionary<of,>.[].get at line 41
    484. def DefaultDictionary<of,>.tryGetValue at line 50
    485. def DefaultDictionary<of,>.[].get at line 41
    486. def DefaultDictionary<of,>.tryGetValue at line 50
    487. def DefaultDictionary<of,>.[].get at line 41
    488. def DefaultDictionary<of,>.tryGetValue at line 50
    489. def DefaultDictionary<of,>.[].get at line 41
    490. def DefaultDictionary<of,>.tryGetValue at line 50
    491. def DefaultDictionary<of,>.[].get at line 41
    492. def DefaultDictionary<of,>.tryGetValue at line 50
    493. def DefaultDictionary<of,>.[].get at line 41
    494. def DefaultDictionary<of,>.tryGetValue at line 50
    495. def DefaultDictionary<of,>.[].get at line 41
    496. def DefaultDictionary<of,>.tryGetValue at line 50
    497. def DefaultDictionary<of,>.[].get at line 41
    498. def DefaultDictionary<of,>.tryGetValue at line 50
    499. def DefaultDictionary<of,>.[].get at line 41
    500. def DefaultDictionary<of,>.tryGetValue at line 48
Fail fast: Stack Overflow
Exiting with -1


The main purpose of that flag is to collect information, such as the value of locals. But I threw in the overflow detection as a bonus since doing so could be done easily with what I was already having to do to implement that option. See cobra -help for info. And -dst is the abbrev.

[jaegs]

Thanks, I fixed the stack overflow.

Patch for DefaultDictionary submitted - http://cobra-language.com/trac/cobra/ticket/290

Also found what looks like a defect - http://cobra-language.com/trac/cobra/ticket/291

I had also ran into this http://cobra-language.com/trac/cobra/ticket/286 when writing DefaultDictionary (I don't know if you get notifications whenever a ticket is filed.)

[jaegs]

With regard to Bag/CountedSet

I added a link the CS MultiSet Wikipedia page.

CountedSet is a better name than MultiSet but it's still a contradiction. A set is a collection of unique items, and this class is not. Bag is a mathematical term and is used by Apache (Java). On the other hand, I bet a lot of Java programmers don't know what the Bag class does. Anyway, I went with CountedSet.

Yup, cue enumerate seems to work. I used it for the .toString method. However, the .getEnumerator method is still necessary to satisfy IEnumerable which seems redundant.

AFAIK, the add method works. However, I did implement the set indexer in a really weird way.

pro [item as T] as int
  get
    return _data.get(item, 0)
  set
    require value > 0
    _data[item] = this[item] + value

I have switched it to something more reasonable.

Also, removeAll seems to be correct.

def removeAll(item as T) as bool
  return _data.remove(item)

The class stores one dictionary entry for each unique element in the CountedSet where the dictionary value is the number of times that the element appears in the CountedSet. Removing the item from the dictionary effectively removes all items from the CountedSet.

I created a ticket. Let me know if you have any more comments
http://cobra-language.com/trac/cobra/at ... icket/292/

[Charles]

I'll take a look later this week.

[Charles]

CountedSet has been added.

http://cobra-language.com/trac/cobra/ticket/292

http://cobra-language.com/trac/cobra/changeset/2781

http://cobra-language.com/trac/cobra/br ... dSet.cobra

I threw in a couple more to-do's but nothing urgent. I used the new namespace allowance to skip indenting underneath it.

[jaegs]

Has the default dictionary been added? Also, I was thinking of making one collection class equivalent to PriorityQueue (java) / HeapQ (Python) and another class equivalent to BiMap (Google Guava), which is a dictionary where the keys are one-to-one with the values.