Problem #2: DictList Class (operators) |
Problem Summary:
The DictList class represents a list of dict, with some
keys appearing in more than one dict: think of the later dicts
as representing updates to the earlier ones, but the earlier ones are still
remembered earlier in the list.
For example, if we define either
d = DictList(dict(a=1,b=2,c=3), dict(c=13,d=14,e=15), dict(e=25,f=26,g=27))
or
d = DictList({'a':1, 'b':2, 'c':3}, {'c':13, 'd':14, 'e':15}, {'e':25, 'f':26, 'g':27})
the key 'c' appears in the first and second dictionary; the key
'e' appears in the second and third dictionary.
The other keys ('a', 'b', 'd', 'f', and 'g')
appear in only a single dictionary.
In methods below, we will overload __getitem__ so that
d['c'] returns 13, because the last (highest index) dictionary
that contains 'c' as a key associates with the value
13.
Details
- Define a class named DictList in a module named
dictlist.py.
- Define an __init__ method that has one parameter: it matches
one or more arguments, where each argument is expected to be a dictionary.
See the example above, which creates a DictList object with three
dictionaries.
If there are no dictionaries or if any argument is not a dictionary, or if
any dictionary is empty, this method must raise an
AssertionError exception with an appropiate message.
For example, in my code writing DictList(1) raises
AssertionError with the message
DictList.__init__: 1 is not a dictionary.
If there are one or more dictionaries as arguments, store them in a
list in the same order: e.g., first argument dictionary
is stored at index 0..
IMPORTANT: You must use the name self.dl (lower-case
D followed by L) to store the list constructed
from the argument dictionaries.
The name self.dl is used in some tests in the batch self-check file.
Store only this attribute: store no other self variables in
this class.
- Define a __len__ method that returns the number of distinct keys in
all the dictionaries in the DictList.
For example len(d) for
d = DictList({'a':1, 'b':2, 'c':3}, {'c':13, 'd':14, 'e':15}, {'e':25, 'f':26, 'g':27})
is 7, because there are seven distinct keys in d:
'a', 'b', 'c', 'd', 'e', 'f',
and 'g'.
- Define a __bool__ method that returns False if the
DictList object stores only one dictionary; it returns
True if it stores more than one dictionary.
- Define a __repr__ method that returns a string, which when
passed to eval returns a newly constructed DictList with
the same dictionary arguments the DictList object __repr__
was called on.
The DictList example above, might (because the order of the
keys/values in each dictionary makes no difference) return the string.
"DictList({'a':1, 'c':3, 'b':2}, {'c':13, 'e':15, 'd':14}, {'g':27, 'f':26, 'e':25})"
- Define a __contains__ method so that in returns whether or
not its first argument is a key in any of the dictionaries in a
DictList; it returns True if such a key is in any
dictionary and False if such a key is not in any of the
dictionaries.
Do not create any new data structures; iterate through the data
structure returning the correctly value as quickly as possible.
- Define a __getitem__ method so that calling d[k]
on DictList d returns the value associated with the
latest dictionary (the one with the highest index) in d's
list that has k as a key.
If the key is in no dictionaries in the list, this method
must raise the KeyError exception with an appropriate message.
For example, in the DictList
d = DictList({'a':1, 'b':2, 'c':3}, {'c':13, 'd':14, 'e':15}, {'e':25, 'f':26, 'g':27})
- d['a'] returns 1
('a' is only in the first dictionary)
- d['d'] returns 14
('d' is only in the second dictionary)
- d['g'] returns 27
('g' is only in the second dictionary)
- d['c'] returns 13
('c' appears in the first and second dictionary: it returns the
associated value from the second dictionary).
- d['e'] returns 25
('e' appears in the second and third dictionary: it returns the
associated value from the third dictionary).
- d['x'] raises KeyError
('x' appears in no dictionaries).
- Define a __setitem__ method so that executing d[k] = v
on DictList d works as follows:
- if k is in at least one dictionary, then change
the association of k to v, only in the last dictionary
(highest index) in which k is a key;
the number of dictionaries in the list remains the same
- if k is not in any dictionaries, then create a new
dictionary at the end of the list of dictionaries, with only
one item: associating k with v in that dictionary; the
number of dictionaries in the list increases by one.
For example, in the DictList d
d = DictList({'a':1, 'b':2, 'c':3}, {'c':13, 'd':14, 'e':15}, {'e':25, 'f':26, 'g':27})
if we wrote d['c'] = 'new' then only the dictionary in index 1 (the
last one/highest index with key 'c') would change 'c's to
associate with 'new'.
It would now be
DictList({'a':1, 'b'2, 'c':3}, {'c':'new', 'd':14, 'e':15}, {'e':25, 'f':26, 'g':27})
In the example above, if we instead wrote d['x'] = 'new' then a new
dictionary would be appended to the list (with 'x' associated with
'new' in that dictionary).
It would now be
DictList({'a':1,'b':2,'c':3},{'c':13,'d':14,'e':15},{'e':25,'f':26,'g':27},{'x':'new'})
- Define a __delitem__ method so that executing del d[k]
on DictList d works as follows:
- if k is in at least one dictionary, then delete
the key k only in the last dictionary (highest index) in
which k is a key; if that dictionary becomes empty, remove
it from the list (the number of dictionaries in the list decreases
by one).
- if k is not in any dictionaries, then raise a
KeyError exception with an appropriate message.
For example, in the DictList d
d = DictList({'a':1, 'b':2, 'c':3}, {'c':13, 'd':14, 'e':15}, {'e':25, 'f':26, 'g':27})
if we wrote del d['c'] then only the dictionary in index 1 (the
last one/highest index with key 'c') would delete 'c' from
its keys.
It would now be
DictList({'a':1, 'b'2, 'c':3}, {'d':14, 'e':15}, {'e':25, 'f':26, 'g':27})
In the example above, if we instead wrote del d['x'] then Python
would raise a KeyError exceptiohn.
- Define ae __call__ method so that calling d(k)
on DictList d returns a list of 2-tuples: the list index
for every dictionary in which k is a key and its associated value
in that dictionary.
If the key is in no dictionaries in the list, it returns [].
In the example above
- d('a') returns [(0, 1)]
(it is only in the list's index-0 dictionary, with an
associated value of 1)
- d('e') returns [(1, 15), (2, 25)]
(it is in the list's index-1 dictionary, with an
associated value of 15 and
it is in the list's index-2 dictionary, with an
associated value of 25)
- d('x') returns []
(it is in no dictionaries)
Note that the indexes that appear first in the the 2-tuple must be
increasing: for d('e') the uniquely correct answer is
[(1, 15), (2, 25)]; the following answer is wrong:
[(2, 25), (1, 15)].
- Define an __iter__ method so that it produces keys according to the
following rules.
- Each key is produced only once, from the last (highest) index
dictionary in which it appears.
- All the keys in each dictionary are produced in alphabetically sorted
order.
These requirements ensure that there is only one correct sequence of
values produced by the iterator.
For the DictList d
d = DictList(dict(a=1,b=2,c=3), dict(c=13,d=14,e=15), dict(e=25,f=26,g=27)
the values are produced in the order
'e', 'f', 'g', 'c', 'd', 'a', 'b'
Note that the keys 'e', 'f', and 'g' are produced
in alphabetical order from the index-2 dictionary;
the keys 'c' and 'd' are produced in alphabetical order from
the index-1 dictionary (key 'e' has already been produced);
they keys 'a' and 'b' are produced in alphabetical order from
the index-0 dictionary (key 'c' has already been produced).
Hints:
- Use a generator to write this method.
- You may use another local data structure to ensure that you don't produce
the same key twice (given that the same key may appear in many
dictionaries in the list).
- Define an items method (taking no arguments) so that it produces
2-tuples (containing key-value pairs) according to the following rules.
- Each key is produced only once, from the last (highest) index
dictionary in which it appears.
- All the keys in each dictionary are produced in alphabetically sorted
order.
These requirements ensure that there is only one correct sequence of
values produced by the iterator.
For the DictList d
d = DictList(dict(a=1,b=2,c=3), dict(c=13,d=14,e=15), dict(e=25,f=26,g=27)
the values are produced in the order
('e', 25), ('f', 26), ('g', 27), ('c', 13), ('d', 14), ('a', 1), ('b', 2)
Note that the keys 'e', 'f', and 'g' are produced
in alphabetical order from the index-2 dictionary;
the keys 'c' and 'd' are produced in alphabetical order from
the index-1 dictionary (key 'e' has already been produced);
the keys 'a' and 'b' are produced in alphabetical order from
the index-0 dictionary (key 'c' has already been produced).
Hints: See above (or just use the __iter__ method).
- Define a collapse method (taking no arguments) that returns a
dict that is equivalent to the DictList: it has the same
keys, and each key is associated with the value in the last dictionary
in which the key appears.
For the DictList d
d = DictList(dict(a=1,b=2,c=3), dict(c=13,d=14,e=15), dict(e=25,f=26,g=27)
d.collapse() would return
{'a':1, 'b':2,'c':13, 'd':14, 'e':25, 'f':26, 'g':27}
- Define the == operator for comparing two DictLists or for
comparing a DictList and a dict for equality.
We define the meaning of d1 == d2 as follows:
- The keys in the left operand are the same as the keys in the right
operand. Here, the keys in a DictList are all the keys
appearing in any of the its dictionaries; the keys in a dict
operand are all the keys in that dictionary (the standard meaning).
and
- For all of the keys k computed above, d1[k] == d2[k].
[k] in a DictList is the value associated with k
in the latest dictionary (the one with the highest index in the list);
[k] in a dict is the value assocated with key k
(the standard meaning).
If the right operand is neither a DictList nor a dict, raise
the TypeError exception with an appropriate message.
For example, if d1 = DictList(dict(a=1,b=2), dict(b=12,c=13)) and
d2 = DictList(dict(a=1,b=12), dict(c=13)) then
d1 == d2 is True:
both have keys a, b, and c; and, both have
['a'] == 1, ['b'] == 12, and ['c'] == 13.
For the same reasons, d1 == dict(a=1,b=12,c=13) would also be
True.
But d1 == dict(a=1,c=13) is False because the dict
operand has no 'b' key; and d1 == dict(a=1,b=2,c=13) is
False because the d1['b'] == 12 but the dict operand
associates 'b' with the value 2.
Hint:
If you have implemented __getitem__ correctly (in part 7), use it
here.
- Define the < operator for comparing two DictLists or for
comparing a DictList and a dict for equality.
We define the meaning of d1 < d2 as follows:
- The keys in the left operand are a strict subset of the keys in the
right operand.
See above for the defintion of "keys".
Strict subset means there are fewer keys in the left operand than the
right operand (and every key in the left operand is also in the right
operand).
and
- For all of the keys k in the left operand, d1[k] == d2[k].
If the right operand is neither a DictList nor a dict, raise
the TypeError exception with an appropriate message.
For example, if d1 = DictList(dict(a=1,b=2), dict(b=12,c=13)) and
d2 = DictList(dict(a=1,b=12), dict(c=13,d=14) then
d1 < d2 is True:
d1's keys (a, b, and c) are a strict
subset of d2's keys (a, b, c, and d);
for d1's keys, all have the same associated values in d1
and d2.
But dict(a=1,x=13) < d2 is False because the d2
operand has no 'x' key; and dict(a=1,b=2) < d2 is
False because the the dict operand associates 'b'
with the value 2 but d2['b'] == 12.
- Define the > operator for comparing two DictLists or for
comparing a DictList and a dict for equality.
For any DictLists and dicts, di and d2,
d1 < d2 exactly when d2 > d1.
By defining both these operators, we can successfully compute expressions
involving dicts as the first operand, like {} < d1 and
{} > d1 and
Note that the law of trichotomy does not hold for DictLists:
one can have two DictLists where the first is not less than, equal
to, or greater than the second.
- Define adding two DictLists and adding a DictList and a
dict as follows.
- To add two DictLists, create a new DictList with a
list of dictionaries that contains a copy of all the
dicts in the left DictList operand (in order) followed
by a copy of all the dicts in the right DictList
operand (in order).
For example, if d1 = DictList(dict(a=1,b=2), dict(b=12,c=13)) and
d2 = DictList(dict(a='one',b='two'), dict(b='twelve',c='thirteen')) then
d1+d2 would be equivalent to
DictList({'a': 1, 'b': 2}, {'b': 12, 'c': 13}, {'a': 'one', 'b': 'two'}, {'b': 'twelve', 'c': 'thirteen'})
and d2+d1 would be equivalent to
DictList({'a': 'one', 'b': 'two'}, {'b': 'twelve', 'c': 'thirteen'}, {'a': 1, 'b': 2}, {'b': 12, 'c': 13})
So addition is not commutative for the DictList class:
d1+d2 produces a different result than d2+d1.
Note the use of copy in the specifications above: changing an
argument dictionary after + should not affect the resulting
dictionary.
For example, if we declare d1 and d2 as above, and compute
d = d1+d2 and then write d1['c'] = 'new' nothing is
changed in d.
- To add DictList + dict, create a new DictList with a
list of dictionaries that contains a copy of all the
dicts in the DictList operand (in order) followed by a
copy of the dict operand.
For example, if adl = DictList(dict(a=1,b=2), dict(b=12,c=13)) and
adict = dict(a='one',b='two') then
adl+adict would return the equivalent to
DictList({'a': 1, 'b': 2}, {'b': 12, 'c': 13}, {'a': 'one', 'b': 'two'})
- To add dict + DictList, create a new DictList with a
list of dictionaries that contains a copy of dict operand
followed a copy of all the dicts in the DictList
operand (in order).
For example, if adl = DictList(dict(a=1,b=2), dict(b=12,c=13)) and
adict = dict(x='anx',b='two') then
adict+adl would be return the equivalent to
DictList({'x': 'anx', 'b': 'two'}, {'a': 1, 'b': 2}, {'b': 12, 'c': 13})
If the right operand isn't a a DictList or a dict, raise
TypeError with an appropriate message.
- Define a __setattr__ method that ensures objects in the
DictList class cannot store new attributes: they store
only dl.
The methods you will write should never bind any instance names
(except in __init__, which initializes dl) but
exclusively returns newly constructed DictList objects with the
correct values.
If an attempt is made to add new attributes to an object (by defining a new
attribute or rebinding an existing attribute), raise an
AssertionError with an appropriate message.
Do not attempt to solve this part of the problem until all other parts
are working correctly.
If you fail to solve this part correctly comment out this method so that
the other batch self-check tests pass.
- You may define other (helper) Python methods in this class, but you do not
have to define any.
Testing
The dictlist.py module includes a script that does some simple
DictList manipulations and then calls driver.driver().
The project folder contains a bsc2.txt file (examine it) to use for
batch-self-checking your class.
These are rigorous but not exhaustive tests.
Incrementally write and test your class: writing some methods may create a
pattern you can reuse for the others.
Note that when exceptions are raised, they are printed by the driver but the
Command: prompt sometimes appears misplaced.
You can also test code you type into the driver as illustrated below; but if you
want to perform the same test over and over again when debugging, it is
better to put this code in the script before the driver is called.
Notice the default for each command (printed in the square brackets) is the
command previously entered.
Driver started
Command[!]: from dictlist import DictList
Command[from dictlist import DictList]: d = DictList(dict(a=1,b=2), dict(b=12,c=13))
Command[d = DictList(dict(a=1,b=2), dict(b=12,c=13))]: print(d)
DictList({'b': 2, 'a': 1}, {'c': 13, 'b': 12})
Command[print(d)]: print(d['b'])
12
Command[print(d['b'])]: print(d('b'))
[(0, 2), (1, 12)]
Command[print(d('b'))]: print(d.collapse())
{'c': 13, 'b': 12, 'a': 1}
Command[print(d.collapse())]: print( (d+dict(b=22)).collapse() )
{'c': 13, 'b': 22, 'a': 1}
Command[print( (d+dict(b=22)).collapse() )]: quit
Driver stopped
|