Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

How can I improve this code (elegance, best practices, etc)?

""" Simple in-memory database as a response to the Thumbtack coding challenge. """


class SimpleDb(object):

    """ Simple in-memory database as a response to the Thumbtack coding challenge. """

    def __init__(self):
        """ Initialize SimpleDb instance. """
        self.__db = {}
        self.__num_equal_to_cache = {}
        self.__transactions = []  # Stores previous values to allow rollback

    def assign(self, name, value):
        """ Sets value of name to value. Inserts name into database if it doesn't already exist. """
        current_value = self.get(name)
        if current_value == value:
            return
        self.__update_num_equal_to(current_value, value)
        self.__update_current_transaction(name, current_value)
        self.__db[name] = value

    def get(self, name):
        """ Returns value of name if it exists in the database, otherwise returns None. """
        return self.__db[name] if name in self.__db else None

    def get_num_equal_to(self, value):
        """ Returns number of entries in the database that have the specified value. """
        return self.__num_equal_to_cache[value] if value in self.__num_equal_to_cache else 0

    def unset(self, name):
        """ Removes name from database if it's present. """
        current_value = self.__db.pop(name, None)
        if current_value is None:
            return
        self.__update_num_equal_to(current_value)
        self.__update_current_transaction(name, current_value)

    def begin(self):
        """ Opens transaction block. """
        self.__transactions += [{}]

    def rollback(self):
        """
        Reverts database to its state before most current transaction.
        Returns True on success, returns False if there aren't any open transactions.
        """
        if not self.__transactions:
            return False
        for name, value in self.__transactions.pop().iteritems():
            current_value = self.get(name)
            if current_value == value:
                continue
            self.__update_num_equal_to(current_value, value)
            if value is None:
                del self.__db[name]
            else:
                self.__db[name] = value
        return True

    def commit(self):
        """
        Commits all transactions to database. Returns True on success,
        returns False if there aren't any open transactions.
        """
        if not self.__transactions:
            return False
        self.__transactions = []
        return True

    def __update_num_equal_to(self, current_value, new_value=None):
        """
        Decrements by one the number items present with current_value (if current_value
        is not equal to None) and increments by one the number present with new_value
        (if new_value is not equal to None).
        """
        for amount_to_add, value in [(-1, current_value), (1, new_value)]:
            if value is not None:
                self.__num_equal_to_cache.setdefault(value, 0)
                self.__num_equal_to_cache[value] += amount_to_add

    def __update_current_transaction(self, name, value):
        """
        Stores current value of name if not already stored to most recent transaction
        (if any transactions open) to enable restoration of previous state on rollback.
        """
        if self.__transactions and name not in self.__transactions[-1]:
            self.__transactions[-1][name] = value


def display(value, default=None):
    """
    Prints value to stdout. If value is None and a default value is
    specified (and not None), then the default value is printed instead. Otherwise
    the None value is printed.
    """
    if value is None and default is not None:
        value = default
    print value


OPS = {
        'GET':        (2, lambda db, name:  display(db.get(name), "NULL")),
        'NUMEQUALTO': (2, lambda db, value: display(db.get_num_equal_to(value))),
        'UNSET':      (2, lambda db, name:  db.unset(name)),
        'BEGIN':      (1, lambda db:        db.begin()),
        'ROLLBACK':   (1, lambda db:        db.rollback() or display("NO TRANSACTION")),
        'COMMIT':     (1, lambda db:        db.commit() or display("NO TRANSACTION")),
        'END':        (1, lambda db:        False),
        'SET':        (3, lambda db, name, value: db.assign(name, value)),
}


def process_command(simpleDb, command):
    """
    Parses string commands and applies them to the database.
    Returning False indicates that no more commands should be passed in.
    """
    command = command.split()
    opcode = command.pop(0).upper() if len(command) > 0 else None
    if opcode is None or opcode not in OPS or len(command) != (OPS[opcode][0] - 1):
        print "INVALID COMMAND"
    elif 'END' == opcode:
        return False
    else:
        OPS[opcode][1](simpleDb, *command)
    return True


def run():
    """ Reads database command from the command line and passes it through for processing. """
    # BEGIN \n SET a 30 \n BEGIN \n SET a 40 \n COMMIT \n GET a \n ROLLBACK \n END
    simpleDb = SimpleDb()
    while process_command(simpleDb, raw_input()):
        pass

run()

(As suggested in comments, code re-written to not touch database until user sends commit command.)

"Simple in-memory database as a response to the Thumbtack coding challenge."

from collections import OrderedDict


class SimpleDb(object):

    "Simple in-memory database as a response to the Thumbtack coding challenge."

    def __init__(self):
        "Initialize SimpleDb instance."
        self.__db = {}
        self.__value_frequency = {}
        self.__num_open_transactions = 0
        self.__transactions = {}
        self.__transaction_value_frequency = {}

    def assign(self, name, value):
        "Inserts/updates value of name in database."
        self.__update_value(name, value)

    def get(self, name):
        "Returns value of name if it exists in the database, otherwise returns None."
        if self.__isTransactionOpen() and name in self.__transactions:
            return self.__transactions[name][self.__getLastKey(self.__transactions[name])]
        elif name in self.__db:
            return self.__db[name]
        else:
            return None

    def get_num_equal_to(self, value):
        "Returns number of entries in the database that have the specified value."
        t_v_freq = self.__transaction_value_frequency
        return ((self.__value_frequency[value] if value in self.__value_frequency else 0) +
                (t_v_freq[value] if self.__isTransactionOpen() and value in t_v_freq else 0))

    def unset(self, name):
        "Removes name from database if it's present."
        self.__update_value(name, None)

    def begin(self):
        "Opens transaction block."
        self.__num_open_transactions += 1

    def rollback(self):
        "Rolls back most recent transaction, returning False if no open transactions."
        if not self.__isTransactionOpen():
            return False
        for name in self.__transactions.keys():
            if self.__num_open_transactions in self.__transactions[name]:
                value = self.__transactions[name].pop(self.__num_open_transactions)
                self.__transactions[name] or self.__transactions.pop(name)
                self.__update_num_equal_to(value, self.get(name))
        self.__num_open_transactions -= 1
        return True

    def commit(self):
        "Commits all transactions, returning False if no open transactions."
        if not self.__isTransactionOpen():
            return False
        self.__num_open_transactions = 0
        any(self.__update_value(name, values[self.__getLastKey(values)])
            for name, values in self.__transactions.iteritems())
        self.__transactions = {}
        self.__transaction_value_frequency = {}
        return True

    def __getLastKey(self, ordered):
        "Returns key (or value if list, etc) most recently added to ordered."
        return next(reversed(ordered)) if ordered else None

    def __isTransactionOpen(self):
        "Returns True if there is currently a pending transaction. Returns False otherwise."
        return self.__num_open_transactions > 0

    def __update_num_equal_to(self, current_value, new_value=None):
        "Swaps current_value (lowers count by 1) with new_value (add 1). Skips None values."
        target = (self.__transaction_value_frequency if self.__isTransactionOpen() else
                  self.__value_frequency)
        for amount_to_add, value in [(-1, current_value), (1, new_value)]:
            if value is not None:
                target.setdefault(value, 0)
                target[value] += amount_to_add

    def __update_value(self, name, value):
        "Updates value (adding/editing/deleting) in database."
        current_value = self.get(name)
        if current_value == value:
            return
        elif self.__isTransactionOpen():
            self.__transactions.setdefault(name, OrderedDict())
            self.__transactions[name][self.__num_open_transactions] = value
        elif value is None:
            del self.__db[name]
        else:
            self.__db[name] = value
        self.__update_num_equal_to(current_value, value)


def display(value, default=None):
    "Prints value to stdout, or default if value is None and default is not None."
    print value if value is not None or default is None else default


OPS = {
    'GET':        (2, lambda db, name:        display(db.get(name), "NULL")),
    'NUMEQUALTO': (2, lambda db, value:       display(db.get_num_equal_to(value))),
    'UNSET':      (2, lambda db, name:        db.unset(name)),
    'BEGIN':      (1, lambda db:              db.begin()),
    'ROLLBACK':   (1, lambda db:              db.rollback() or display("NO TRANSACTION")),
    'COMMIT':     (1, lambda db:              db.commit() or display("NO TRANSACTION")),
    'END':        (1, lambda db:              False),
    'SET':        (3, lambda db, name, value: db.assign(name, value)),
}


def process_command(simpleDb, command):
    "Applies command to the database. Returns False when stream of commands should end."
    command = command.split()
    opcode = command.pop(0).upper() if command else None
    if opcode is None or opcode not in OPS or len(command) != (OPS[opcode][0] - 1):
        print "INVALID COMMAND"
    elif 'END' == opcode:
        return False
    else:
        OPS[opcode][1](simpleDb, *command)
    return True


def run():
    "Reads commands from the command line and passes them through for processing."
    simpleDb = SimpleDb()
    all(iter(lambda: process_command(simpleDb, raw_input()), False))

run()
share|improve this question
3  
Do you want to add thumbtack.com/challenges/software-engineer#simple-db to the question as a definition of the program's specification? –  ChrisW Feb 18 at 2:30
1  
If you want to edit the code, put your edited code after (not replacing) the existing code; otherwise that invalidates existing answers: see Can I edit my own question to include suggested changes from answers? for further details. –  ChrisW Feb 18 at 12:03
add comment

1 Answer 1

I find your treatment of transactions odd. I would expect that when a transaction is in progress, data modifications commands get buffered; queries would consult the state stored in the current transaction for any relevant data, then any stacked transactions, then finally consulting the "real" database. Instead, you immediately "auto-commit" each command, and add an entry to the undo list; a commit simply discards the undo list. That's not a realistic model of a database: one would expect that a commit either succeeds atomically or has no effect at all on the database.

share|improve this answer
    
I was thinking just that. I've re-written the code such that no changes are made until the user sends the commit command. –  Joel Feb 18 at 6:49
1  
You might want to post the revised code as a second question, referencing this one. –  200_success Feb 18 at 6:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.