Welcome, guest | Sign In | My Account | Store | Cart

This class implements a two-dimensional ragged array using nested dictionaries.

As written this class requires Python 2.2 or later. This meets my requirements, but it may not meet yours.

Klaus Alexander Seistrup has described a way to get around this restriction by substituting "UserDict.UserDict" for "dictionary" as the base class. I believe this solves the problem for Python versions at least as far back as 1.5.2. This approach will require some editing of the insertion and retrieval functions to make it work.

Thanks Klaus!

Python, 154 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import exceptions
import sys
import types

def copyright():
    print("""Copyright 2001 by Peter Olsen, P.E., p@sigmaxi.org
            May be used for any purpose without payment of royalty
            provided this copyright is retained.
            
            This code is provided in the hope that it may be useful
            but with WITH ABSOLUTELY NO WARRANTY WHATSOEVER,
            including any warranty of merchantability or fitness for any
            particular purpose.

            If this code works, fine; if it doesn't, I'm not responsible.""") 
          
class RaggedArray2D(dictionary):

    """This class implements 2-dimensional ragged arrays as nested Dictionaries.

    Keys are 2-tuples, conceptually "rows" and "columns."

    Each "row" is a subdictionary returned by the first key in a
    keyTuple.  Each "column" is a subdictionary built by extracting
    appropriate elements from each row.  So, for faster code, try to
    access first by row, then by column rather than the other way around

    This class is implemented as two layers of nested dictionaries instead of
    as a single dictionary keyed by the tuples directly because I'm writing it
    for an application in which I want to operate entire rows.  This  approach
    makes it much easier.

    Note: This implementation subclasses a built-in data type, and so requires 
    Python 2.2 or later.  This meets my requirements, but it may not meet
    yours. 
 
    Klaus Alexander Seistrup has described a way to get around this 
    restriction by substituting UserDict.UserDict for dictionary as 
    the base class.  I believe this solves the problem for versions at least
    as far back as 1.5.2.  This approach will require some editing of
    the insertion and retrieval functions to make it work.  

    Thanks Klaus!"""

    def insert(self, keyTuple, newThing):
        """Stores newThing in place specified by keyTuple, returns oldThing.

        keyTuple is a 2-tuple of coordinates.
        thing is any object that can be stored in a dictionary.

        Returns None if there was no old thing at key."""

        if not self.checkKeyTuple(keyTuple):
            raise RaggedArrayException, "Bad keyTuple."
        else:
            # Key was a tuple of length 2
            # So, extract two keys.
            key1 = keyTuple[0]
            key2 = keyTuple[1]

            # So, now we have a sub-dictionary in the right position of
            # raggedArray.  Let's save the oldThing and insert the newThing.
            row = self.getRow(key1)
            oldThing = row.get(key2, None)
            row[key2] = newThing
        # We've saved the oldThing and inserted the newThing.  We're done!
        return oldThing

    def retrieve(self, keyTuple):
        """Retrieves oldThing from place specified by keyTuple.

        keyTuple is a 2-tuple of coordinates."""

        # FIXME: can retrieve() share more code with insert()?
        if not self.checkKeyTuple(keyTuple):
            raise RaggedArrayException, "Bad keyTuple."
        else:
            # Key was a tuple of length 2
            # So, extract two keys.
            key1 = keyTuple[0]
            key2 = keyTuple[1]

            # So, now we have a sub-dictionary in the right position of
            # raggedArray.
            row = self.getRow(key1)
            oldThing = row.get(key2, None)
        return oldThing

    def checkKeyTuple(self, keyTuple):
        """Checks keyTuple validity. Returns boolean."""
        
        # Is the key a tuple?  If not, it's an error.
        if not isinstance(keyTuple, types.TupleType):
            result = 0
            raise RaggedArrayException, "checkKeyTuple: keyTuple not a tuple."
        # Does the keyTuple have two keys?  If not, it's an error.
        elif len(keyTuple) != 2:
            result = 0
            raise RaggedArrayException, "checkKeyTuple: keyTuple wrong length."
        else:
            result = 1
        return result

    def getRow(self, key):
        """Gets or creates the row subdirectory matching key.

        Note that the "rows" returned by this method need not be complete.
        They will contain only the items corresponding to the keys that
        have actually been inserted.  Other items will not be present,
        in particular they will not be represented by None."""
        
        # Get whatever is located at the first key
        thing = self.get(key, None)

        # If thing is a dictionary, return it.
        if isinstance(thing, dictionary):
            row = thing

        # If thing is None, create a new dictionary and return that.
        elif isinstance(thing, types.NoneType):
            row = {}
            self[key] = row

        # If thing is neither a dictionary nor None, then it's an error.
        else:
            row = None
            raise RaggedArrayException, "getRow: thing was not a dictionary."
        return row  

    def getColumn(self, columnKey):
        """Gets or creates the column subdirectory matching key.

        Note that the "columns" returned by this method need not be complete.
        They will contain only the items corresponding to the keys that
        have actually been inserted.  Other items will not be present,
        in particular they will not be represented by None."""
        
        # Get a list of the keys to the primary dictionary
        rows = self.keys()

        # Create the empty column dictionary
        column = {}

        # Now index through the rows, retrieving the appropriate "column"
        # entries and adding them to the column
        for row in rows:
            thisRow = self.getRow(row)
            if thisRow.has_key(columnKey):
                column[row] = thisRow[columnKey]
        return column
    
class RaggedArrayException(exceptions.Exception):
    def __init__(self, args=None):
        self.args = "RaggedArray: " + args
        

       

5 comments

Klaus Alexander Seistrup 20 years, 2 months ago  # | flag

Which "dictionary"? 'Xcuse me, but which "dictionary" class are you subclassing? My Python interpreter doesn't come with any dictionary class...?

Peter Olsen (author) 20 years, 2 months ago  # | flag

Which dictionary... I'm subclassing the class used for native dictionaries. I'm new to Python, so this may not be as clear (or as accurate) as I would like.

As I understand it, in Python, everything is an object. In particular, the "built-in" data types, such as dictionaries, are objects too. This means that they have classes. I believe that I have seen specific references to the classes for native objects, but I could not find them when I wrote this, so I tried the simplest thing and inserted "dictionary" as the superclass.

The script ran, so I first tested it and then posted it.

I would be pleased if someone with more knowledge would correct, extend, amend, or generally improve on this explanation.

Simon Brunning 20 years, 2 months ago  # | flag

Subclassing built-in types. You can subclass the built-in types in Python 2.2, not in 2.1 or earlier.

Klaus Alexander Seistrup 20 years, 2 months ago  # | flag

The UserDict class might solve the problem. Substituting UserDict.UserDict for dictionary solves the problem with the missing dictionary class, but the RaggedArray2D class needs minor rewriting to make it work.

I've tried it now, it's need. Thanks for the inspiration.

Klaus Alexander Seistrup 20 years, 2 months ago  # | flag

Oops. s/need/neat/

Created by Peter Olsen on Sun, 23 Sep 2001 (PSF)
Python recipes (4591)
Peter Olsen's recipes (1)

Required Modules

Other Information and Tasks