def get_history(self, addr):
     out = []
     o = self.listunspent(addr)
     for item in o:
         out.append((item['height'], item['tx_hash']))
     index = 0
     h = self.db_hist_get_index(addr, index)
     while h:
         item = h[0:80]
         h = h[80:]
         txi = item[0:32].encode('hex')
         hi = hex_to_int(item[36:40])
         txo = item[40:72].encode('hex')
         ho = hex_to_int(item[76:80])
         out.append((hi, txi))
         out.append((ho, txo))
         if not h:
             index += 1
             h = self.db_hist_get_index(addr, index)
     # uniqueness
     out = set(out)
     # sort by height then tx_hash
     out = list(out)
     out.sort()
     return map(lambda x: {'height':x[0], 'tx_hash':x[1]}, out)

    def get_history(self, addr):
        out = []

        o = self.listunspent(addr)
        for item in o:
            out.append((item['tx_hash'], item['height']))

        h = self.db_hist.get(addr)
        
        while h:
            item = h[0:80]
            h = h[80:]
            txi = item[0:32].encode('hex')
            hi = hex_to_int(item[36:40])
            txo = item[40:72].encode('hex')
            ho = hex_to_int(item[76:80])
            out.append((txi, hi))
            out.append((txo, ho))

        # sort
        out.sort(key=lambda x:x[1])

        # uniqueness
        out = set(out)

        return map(lambda x: {'tx_hash':x[0], 'height':x[1]}, out)

 def set_spent(self, addr, txi, txid, index, height, undo):
     key = self.address_to_key(addr)
     leaf = key + txi
     s = self.delete_key(leaf)
     value = hex_to_int(s[0:8])
     in_height = hex_to_int(s[8:12])
     undo[leaf] = value, in_height
     # delete backlink txi-> addr
     self.db_addr.delete(txi)
     # add to history
     txo = (txid + int_to_hex(index,4) + int_to_hex(height,4)).decode('hex')
     self.db_hist_add(addr, txi + int_to_hex(in_height,4).decode('hex') + txo)

 def set_spent(self, addr, txi, txid, index, height, undo):
     key = self.address_to_key(addr)
     leaf = key + txi
     s = self.delete_key(leaf)
     value = hex_to_int(s[0:8])
     in_height = hex_to_int(s[8:12])
     undo[leaf] = value, in_height
     # delete backlink txi-> addr
     self.db_addr.delete(txi)
     # add to history
     s = self.db_hist.get(addr)
     if s is None: s = ''
     txo = (txid + int_to_hex(index,4) + int_to_hex(height,4)).decode('hex')
     s += txi + int_to_hex(in_height,4).decode('hex') + txo
     s = s[ -80*self.pruning_limit:]
     self.db_hist.put(addr, s)

    def listunspent(self, addr):
        key = self.address_to_key(addr)

        out = []
        for k, v in self.db_utxo.iterator(start=key):
            if not k.startswith(key):
                break
            if len(k) == KEYLENGTH:
                txid = k[20:52].encode('hex')
                txpos = hex_to_int(k[52:56])
                h = hex_to_int(v[8:12])
                v = hex_to_int(v[0:8])
                out.append({'tx_hash': txid, 'tx_pos':txpos, 'height': h, 'value':v})

        out.sort(key=lambda x:x['height'])
        return out

    def listunspent(self, addr):
        key = self.address_to_key(addr)
        if key is None:
            raise BaseException('Invalid Gamecredits address', addr)
        out = []
        with self.db_utxo.lock:
            for k, v in self.db_utxo.db.iterator(start=key):
                if not k.startswith(key):
                    break
                if len(k) == KEYLENGTH:
                    txid = k[20:52].encode('hex')
                    txpos = hex_to_int(k[52:56])
                    h = hex_to_int(v[8:12])
                    v = hex_to_int(v[0:8])
                    out.append({'tx_hash': txid, 'tx_pos':txpos, 'height': h, 'value':v})

        out.sort(key=lambda x:x['height'])
        return out

    def listunspent(self, addr):
        key = self.address_to_key(addr)
        if key is None:
            raise BaseException("Invalid Bitcoin address", addr)

        out = []
        for k, v in self.db_utxo.iterator(start=key):
            if not k.startswith(key):
                break
            if len(k) == KEYLENGTH:
                txid = k[20:52].encode("hex")
                txpos = hex_to_int(k[52:56])
                h = hex_to_int(v[8:12])
                v = hex_to_int(v[0:8])
                out.append({"tx_hash": txid, "tx_pos": txpos, "height": h, "value": v})

        out.sort(key=lambda x: x["height"])
        return out

    def delete_key(self, leaf):
        path = self.get_path(leaf)
        #print "delete key", leaf.encode('hex'), map(lambda x: x.encode('hex'), path)

        s = self.db_utxo.get(leaf)
        self.db_utxo.delete(leaf)

        if leaf in self.hash_list:
            self.hash_list.pop(leaf)

        parent = path[-1]
        letter = leaf[len(parent)]
        parent_node = self.get_node(parent)
        parent_node.remove(letter)

        # remove key if it has a single child
        if parent_node.is_singleton(parent):
            #print "deleting parent", parent.encode('hex')
            self.db_utxo.delete(parent)
            if parent in self.hash_list:
                self.hash_list.pop(parent)

            l = parent_node.get_singleton()
            _hash, value = parent_node.get(l)
            skip = self.get_skip(parent + l)
            otherleaf = parent + l + skip
            # update skip value in grand-parent
            gp = path[-2]
            gp_items = self.get_node(gp)
            letter = otherleaf[len(gp)]
            new_skip = otherleaf[len(gp)+1:]
            gp_items.set(letter, None, 0)
            self.set_skip(gp+ letter, new_skip)
            #print "gp new_skip", gp.encode('hex'), new_skip.encode('hex')
            self.put_node(gp, gp_items)

            # note: k is not necessarily a leaf
            if len(otherleaf) == KEYLENGTH:
                ss = self.db_utxo.get(otherleaf)
                _hash, value = otherleaf[20:52], hex_to_int(ss[0:8])
            else:
                _hash, value = None, None
            self.update_node_hash(otherleaf, path[:-1], _hash, value)

        else:
            self.put_node(parent, parent_node)
            _hash, value = None, None
            self.update_node_hash(parent, path[:-1], _hash, value)
        return s

    def delete_address(self, leaf):
        path = self.get_path(leaf)
        if path is False:
            print_log("addr not in tree", leaf.encode('hex'),
                      self.key_to_address(leaf[0:20]), self.db_utxo.get(leaf))
            raise

        s = self.db_utxo.get(leaf)

        self.db_utxo.delete(leaf)
        if leaf in self.hash_list:
            self.hash_list.pop(leaf)

        parent = path[-1]
        letter = leaf[len(parent)]
        items = self.get_node(parent)
        items.pop(letter)

        # remove key if it has a single child
        if len(items) == 1:
            letter, v = items.items()[0]

            self.db_utxo.delete(parent)
            if parent in self.hash_list:
                self.hash_list.pop(parent)

            # we need the exact length for the iteration
            i = self.db_utxo.iterator()
            i.seek(parent + letter)
            k, v = i.next()

            # note: k is not necessarily a leaf
            if len(k) == KEYLENGTH:
                _hash, value = k[20:52], hex_to_int(v[0:8])
            else:
                _hash, value = None, None

            self.update_node_hash(k, path[:-1], _hash, value)

        else:
            self.put_node(parent, items)
            _hash, value = None, None
            self.update_node_hash(parent, path[:-1], _hash, value)

        return s

 def get_hash(self, x, parent):
     if x:
         assert self.k != 0
     skip_string = x[len(parent)+1:] if x != '' else ''
     x = 0
     v = 0
     hh = ''
     for i in xrange(256):
         if (self.k&(1<<i)) != 0:
             ss = self.s[x:x+40]
             hh += ss[0:32]
             v += hex_to_int(ss[32:40])
             x += 40
     try:
         _hash = Hash(skip_string + hh)
     except:
         _hash = None
     if x:
         assert self.k != 0
     return _hash, v

    def get_node(self, key):

        s = self.db_utxo.get(key)
        if s is None: 
            return 

        #print "get node", key.encode('hex'), len(key), s.encode('hex')

        k = int(s[0:32].encode('hex'), 16)
        s = s[32:]
        d = {}
        for i in range(256):
            if k % 2 == 1: 
                _hash = s[0:32]
                value = hex_to_int(s[32:40])
                d[chr(i)] = (_hash, value)
                s = s[40:]
            k = k/2

        #cache
        return d

 def get_utxo_value(self, addr, txi):
     key = self.address_to_key(addr)
     leaf = key + txi
     s = self.db_utxo.get(leaf)
     value = hex_to_int(s[0:8])
     return value

 def get(self, c):
     x = self.indexof(c)
     ss = self.s[x:x+40]
     _hash = ss[0:32]
     value = hex_to_int(ss[32:40])
     return _hash, value

    def decode_answer(self, cmd, answer):
        # this will receive only valid answers
        value = None
        unit = None
        payload = self.extract_payload(cmd, answer)
        if cmd == "0100":
            value = payload

        elif cmd == "0101":
            mil_state = []
            num_dtcs = []
            supported_tests = []
            while 1:
                if len(payload) >= 8:
                    # index = string.find(test_pattern,'4101')
                    payload_databyte_1A = payload[0]
                    payload_databyte_2A = payload[1]
                    code = utils.hex_to_bin(payload_databyte_1A)[0]
                    if code:
                        mil_state.append("ON")
                    else:
                        mil_state.append("OFF")
                    partial1 = str(utils.hex_to_bin(payload_databyte_1A[0]))
                    partial2 = str(utils.hex_to_bin(payload_databyte_2A))
                    num_dtcs.append(str(int(partial1[1:] + partial2, 2)))
                    tests = ""
                    for i in range(2, 6):
                        tests = tests + utils.hex_to_bin(payload[i])
                    supported_tests.append(tests)
                try:
                    payload = payload[16:]  # jump ahead checksum and headers of next frame
                    if payload[0:4] != "4101":  # verify answer of next frame
                        break
                    else:
                        payload = payload[4:]
                except IndexError:
                    break

            value = [mil_state, num_dtcs, supported_tests]

        elif cmd == "0102":
            value = self.decode_dtc(payload)

        elif cmd == "0103":
            # OL: open loop. CL: closed loop.
            description = {
                "00000000": "Wrong state",
                "00000001": "OL",
                "00000010": "CL",
                "00000100": "OL-Drive",
                "00001000": "OL-Fault",
                "00010000": "CL-Fault",
                "0010000": "ISO Reserved",
                "01000000": "ISO Reserved",
                "10000000": "ISO Reserved",
            }
            fuel_system1_status = utils.hex_to_bin(payload[0]) + utils.hex_to_bin(payload[1])
            fuel_system2_status = utils.hex_to_bin(payload[2]) + utils.hex_to_bin(payload[3])
            try:
                value = [description[fuel_system1_status], description[fuel_system2_status]]
            except KeyError:
                value = "Unknown"

        elif cmd in ["0104", "012F", "0152"]:
            code = utils.hex_to_int(payload)
            value = code * 100.0 / 255.0
            unit = "Percent scale"

        elif cmd == "0105" or cmd == "010F":
            code = utils.hex_to_int(payload)
            value = code - 40
            unit = "Degrees Celsius"

        elif cmd in ["0106", "0107", "0108", "0109"]:
            code = utils.hex_to_int(payload)
            value = (code - 128.0) * 100.0 / 128
            unit = "Percent scale"

        elif cmd == "010A":
            code = utils.hex_to_int(payload)
            value = code * 3
            unit = "KPa"

        elif cmd == "010B":
            value = utils.hex_to_int(payload)
            unit = "KPa"

        elif cmd == "010C":
            code = utils.hex_to_int(payload)
            value = code / 4
            unit = "RPM"

        elif cmd == "010D":
            value = utils.hex_to_int(payload)
            unit = "Km/h"

        elif cmd == "010E":
            code = utils.hex_to_int(payload)
            value = (code - 128) / 2.0
            unit = "Degrees"
#.........这里部分代码省略.........

def decode_answer(cmd, answer):
    # TODO: migrate all of these functions to "elmdb.py" dictionary
    # TODO: use elmdb.ELMdb[cmd]['unit']

    # this will receive only valid answers
    value = None
    unit = None
    payload = extract_payload(cmd, answer)
    if cmd in ['0100', '0120', '0140', '0160', '0180', '01A0', '01C0']:
        value = payload

    elif cmd == '0101':
        mil_state = []
        num_dtcs = []
        supported_tests = []
        while 1:
            if len(payload) >= 8:
                # index = string.find(test_pattern,'4101')
                payload_databyte_1A = payload[0]
                payload_databyte_2A = payload[1]
                code = utils.hex_to_bin(payload_databyte_1A)[0]
                if code:
                    mil_state.append('ON')
                else:
                    mil_state.append('OFF')
                partial1 = str(utils.hex_to_bin(payload_databyte_1A[0]))
                partial2 = str(utils.hex_to_bin(payload_databyte_2A))
                num_dtcs.append(str(int(partial1[1:] + partial2, 2)))
                tests = ''
                for i in range(2, 6):
                    tests = tests + utils.hex_to_bin(payload[i])
                supported_tests.append(tests)
            try:
                # jump ahead checksum and headers of next frame
                payload = payload[16:]
                if payload[0:4] != '4101':   # verify answer of next frame
                    break
                else:
                    payload = payload[4:]
            except IndexError:
                break

        value = [mil_state, num_dtcs, supported_tests]

    elif cmd == '0102':
        value = decode_dtc(payload)

    elif cmd == '0103':
        #OL: open loop. CL: closed loop.
        description = {
            '00000000': 'Wrong state',
            '00000001': 'OL',
            '00000010': 'CL',
            '00000100': 'OL-Drive',
            '00001000': 'OL-Fault',
            '00010000': 'CL-Fault',
            '0010000': 'ISO Reserved',
            '01000000': 'ISO Reserved',
            '10000000': 'ISO Reserved'
        }
        fuel_system1_status = utils.hex_to_bin(payload[0]) + \
            utils.hex_to_bin(payload[1])
        fuel_system2_status = utils.hex_to_bin(payload[2]) + \
            utils.hex_to_bin(payload[3])
        try:
            value = [description[fuel_system1_status],
                     description[fuel_system2_status]]
        except KeyError:
            value = 'Unknown'

    elif cmd in ['0104', '012F', '0152']:
        code = utils.hex_to_int(payload)
        value = code * 100.0 / 255.0
        unit = 'Percent scale'

    elif cmd == '0105' or cmd == '010F':
        code = utils.hex_to_int(payload)
        value = code - 40
        unit = 'Degrees Celsius'

    elif cmd in ['0106', '0107', '0108', '0109']:
        code = utils.hex_to_int(payload)
        value = (code - 128.0) * 100.0 / 128
        unit = 'Percent scale'

    elif cmd == '010A':
        code = utils.hex_to_int(payload)
        value = code * 3
        unit = 'KPa'

    elif cmd == '010B':
        value = utils.hex_to_int(payload)
        unit = 'KPa'

    elif cmd == '010C':
        code = utils.hex_to_int(payload)
        value = code / 4
        unit = 'RPM'

    elif cmd == '010D':
#.........这里部分代码省略.........