User:Jorge Stolfi/make-hash-table-figure
- ! /usr/bin/python -t
- _*_ coding: iso-8859-1 _*_
- Last edited on 2009-04-12 18:29:53 by stolfilocal
PROG_NAME = "make-hash-table-figure" PROG_DESC = "Generates an SVG illustration for the Wikipedia hash table article" PROG_VERS = "1.0"
import sys import re import os sys.path[1:0] = [ sys.path[0] + '/../lib', os.path.expandvars('${STOLFIHOME}/lib'), '.' ] import argparser; from argparser import ArgParser
from decimal import * from datetime import date
PROG_COPYRIGHT = "Copyright © 2009-04-04 by the State University of Campinas (UNICAMP)"
PROG_HELP = \
PROG_NAME+ " \\\n" \ " -back {BOOL} \\\n" \ " -funcbox {BOOL} \\\n" \ " -sparse {BOOL} \\\n" \ " -keys {BOOL} \\\n" \ " -values {BOOL} \\\n" \ " -collisions {BOOL} \\\n" \ " -links {BOOL} \\\n" \ " -overflow { \"SP\" | \"LL\" } \\\n" \ +argparser.help_info_HELP+ " \\\n" \ " > {FIGURE}.svg"
PROG_INFO = \
"NAME\n" \ " " +PROG_NAME+ " - " +PROG_DESC+ ".\n" \ "\n" \ "SYNOPSIS\n" \ " " +PROG_HELP+ "\n" \ "\n" \ "DESCRIPTION\n" \ " Writes an SVG illustration for the Wikipedia article on hash tables.\n" \ "\n" \ "OPTIONS\n" \ " -back {BOOL} \n" \ " If {BOOL} is 1, paints the background with a nonwhite color. If {BOOL} is 0," \ " leaves it transparent. This option is meant to debug the image size.\n" \ "\n" \ " -nkeys {INT} \n" \ " Number of keys to show in the key column. Only some values" \ " are implemented (currently 3 and 5).\n" \ "\n" \ " -funcbox {BOOL} \n" \ " If {BOOL} is 1, there will be a box labeled \"hash function\" behind the hash arrows.\n" \ "\n" \ " -sparse {BOOL} \n" \ " If {BOOL} is 1, the table will have a largish range with many vacant" \ " slots. If {BOOL} is 0, it will be compact, with no vacant slots.\n" \ "\n" \ " -collisions {BOOL} \n" \ " If {BOOL} is 0, there will be no collisions. If {BOOL} is 1, there will" \ " be at least one collision.\n" \ "\n" \ " -keys {BOOL} \n" \ " If {BOOL} is 1, every stored entry record contains a copy of the key.\n" \ "\n" \ " -values {BOOL} \n" \ " If {BOOL} is 1, every stored entry record has a non-empty value field.\n" \ "\n" \ " -links {BOOL} \n" \ " If {BOOL} is 1, the buckets are only links to separate entry" \ " records; in that case, if neither keys nor values are stored," \ " there is no overflow column and the buckets only record" \ " presence/absence. If {BOOL} is 0, the buckets themselves" \ " are entries; in that case, if neither keys nor values are" \ " stored, there are no bucket boxes, there is no overflow" \ " area, and collisions are not handled.\n" \ "\n" \ " -overflow { \"SP\" | \"LL\" } \n" \ " Specifies how collisions are resolved:\n" \ " \"SP\" -- sequential probing.\n" \ " \"LL\" -- linear linked lists. The buckets may or may not be" \ " If there are collisions, every record contains a link field.\n" \ "\n" \ "DOCUMENTATION OPTIONS\n" \ +argparser.help_info_INFO+ "\n" \ "\n" \ "SEE ALSO\n" \ " cat(1).\n" \ "\n" \ "AUTHOR\n" \ " Created 2009-04-04 by Jorge Stolfi, IC-UNICAMP.\n" \ "\n" \ "MODIFICATION HISTORY\n" \ " 2009-04-04 by J. Stolfi, IC-UNICAMP: created.\n" \ "\n" \ "WARRANTY\n" \ " " +argparser.help_info_NO_WARRANTY+ "\n" \ "\n" \ "RIGHTS\n" \ " " +PROG_COPYRIGHT+ ".\n" \ "\n" \ " " +argparser.help_info_STANDARD_RIGHTS
- COMMAND ARGUMENT PARSING
pp = ArgParser(sys.argv, sys.stderr, PROG_HELP, PROG_INFO)
class Options :
back = None; nkeys = None; funcbox = None; sparse = None; keys = None; values = None; collisions = None; links = None; overflow = None; err = None;
def arg_error(msg):
"Prints the error message {msg} about the command line arguments, and aborts." sys.stderr.write("%s\n" % msg); sys.stderr.write("usage: %s\n" % PROG_HELP); sys.exit(1)
def parse_args(pp) :
"Parses command line arguments.\n" \ "\n" \ " Expects an {ArgParser} instance {pp} containing the arguments," \ " still unparsed. Returns an {Options} instance {op}, where" \ " {op.err} is an error message, if any (a string) or {None}." op = Options(); # Being optimistic: op.err = None
pp.get_keyword("-back") op.back = pp.get_next_int(0, 1) pp.get_keyword("-nkeys") op.nkeys = pp.get_next_int(3, 5) pp.get_keyword("-funcbox") op.funcbox = pp.get_next_int(0, 1) pp.get_keyword("-sparse") op.sparse = pp.get_next_int(0, 1) pp.get_keyword("-keys") op.keys = pp.get_next_int(0, 1) pp.get_keyword("-values") op.values = pp.get_next_int(0, 1) pp.get_keyword("-collisions") op.collisions = pp.get_next_int(0, 1) pp.get_keyword("-links") op.links = pp.get_next_int(0, 1) pp.get_keyword("-overflow") op.overflow = pp.get_next()
return op ################################################################
def dts(x) :
"Converts the decimal number {x} to string." return ("%r" % x) ################################################################
class HashTable :
"Describes the contents of a hash table.\n" \ "\n" \ " Fields are:\n" " {tb.nkeys} = number of VISIBLE key boxes in \"keys\" column.\n" \ " {tb.nbucs} = number of VISIBLE hash/bucket boxes in bucket array, including \":\" entries.\n" \ " {tb.novfs} = number of VISIBLE entry boxes in \"overflow\" column.\n" \ "\n" \ " {tb.key_str[0..nkeys-1]} = the strings to show in each visible key box.\n" \ " {tb.val_str[0..nkeys-1]} = the corresponding values.\n" \ " {tb.key_sty[0..nkeys-1]} = the style of each key box (\'N\', \'C\').\n" \ " {tb.key_hsh[0..nkeys-1]} = (int) the hash value of each key.\n" \ " {tb.key_bix[0..nkeys-1]} = (int) the index of each key\'s bucket among the VISIBLE bucket entries.\n" \ "\n" \ " {tb.buc_hsh[0..nbucs-1]} = (int) the hash (index) of each VISIBLE bucket, or -1 if none.\n" \ " {tb.buc_kix[0..nbucs-1]} = (int) the index of a key associated to the bucket, or -1 if vacant.\n" \ " {tb.buc_hsh_sty[0..nbucs-1]} = the style of each hash box (\'N\', \'U\', \'C\') or \':\' for a vdots box.\n" \ " {tb.buc_oix[0..nbucs-1]} = (int) the index of the ovflow entry box which the bucket points to, or -1 if none.\n" \ "\n" \ " {tb.buc_has_key} = (bool) 1 iff buckets have keys.\n" \ " {tb.buc_has_val} = (bool) 1 iff buckets have values.\n" \ " {tb.buc_has_ptr} = (bool) 1 iff buckets have pointers.\n" \ " {tb.has_buc_box} = (bool) 1 iff bucket column has bucket boxes, 0 iff has only the hashes.\n" \ "\n" \ " {tb.ovf_kix[0..novfs-1]} = (int) the index of the key which is stored in each overflow entry, or -1 if vacant.\n" \ "\n" \ " {tb.ovf_has_key} = (bool) 1 iff overflow entries have keys.\n" \ " {tb.ovf_has_val} = (bool) 1 iff overflow entries have values.\n" \ " {tb.ovf_has_ptr} = (bool) 1 iff overflow entries have pointers.\n" \ "\n" \ " For \'SP\' type tables, {tb.buc_kix[j]} is the index of the key which is" \ " actualy stored in the bucket, which may or may not hash into it. For" \ " all other table types, {tb.buc_kix[j]} is one of the entries that hashed into that" \ " bucket. The meaning of {tb.buc_kix[j]} is independent of whether the bucket elements" \ " are actual entries or just links or." def __init__(tb, op) :
assert(op.nkeys >= 3) assert(op.nkeys <= 5)
tb.choose_keys_and_hashes(op) tb.choose_and_assign_buckets(op) tb.gather_overflow_entries(op) # Decide what goes into the buckets: tb.buc_has_key = op.keys and (not op.links) tb.buc_has_val = op.values and (not op.links) if op.collisions : if op.keys : # Figure showing a dynamic set or dynamic table with collisions: tb.buc_has_ptr = op.links or (op.overflow == 'LL') else : # Figure makes no sense as a table or set. # It must show a hash function with collisions: assert(not op.values) assert(not op.links) tb.buc_has_ptr = 0 else : if op.keys or op.values or op.links : # Figure shows a collision-less table or dynamic set: tb.buc_has_ptr = op.links else : # Figure shows a collision-less hash function: tb.buc_has_ptr = 0 tb.has_buc_box = tb.buc_has_key or tb.buc_has_val or tb.buc_has_ptr # Decide what goes into the overflow records: if tb.novfs == 0 : # There is no overfow block: tb.ovf_has_key = 0 tb.ovf_has_val = 0 tb.ovf_has_ptr = 0 else : assert(op.links or (op.collisions and (op.overflow != 'SP'))) tb.ovf_has_key = op.keys tb.ovf_has_val = op.values tb.ovf_has_ptr = op.collisions and (op.overflow == 'LL') ################################################################
def choose_keys_and_hashes(tb, op) : "Chooses the keys and their hashes, as requested in {op}.\n" \ "\n" \ " Sets {tb.nkeys} to {op.nkeys}, and fills the arrays that describe the" \ " keys column, namely {tb.key_str[i]}, {tb.key_val[i]}, and" \ " {tb.key_hsh[i]} for {i} in {0..tb.nkeys-1}.\n"
sys.stderr.write("entering {choose_keys_and_hashes}\n") # Fill {tb.key_str,tb.key_val} with 5 keys: tb.key_str = [ 'John Smith', 'Lisa Smith', 'Sam Doe', 'Sandra Dee', 'Ted Baker' ] tb.val_str = [ '521-1234', '521-8976', '521-5030', '521-9655', '418-4165' ] tb.nkeys = len(tb.key_str)
# Choose the max hash value {tb.max_hsh}: if op.sparse : if op.nkeys <= 4 : tb.max_hsh = 15 else: tb.max_hsh = 255 else : if op.collisions : tb.max_hsh = int(tb.nkeys - 2) else : tb.max_hsh = int(tb.nkeys - 1)
# Hashes of the keys and their positions: if tb.max_hsh <= op.nkeys : tb.key_hsh = [ 1, 0, 4, 3, 2 ] elif tb.max_hsh == 15 : tb.key_hsh = [ 02, 01, 04, 14, 03 ] else : tb.key_hsh = [ 152, 001, 254, 154, 153 ]
if op.collisions : # Make "Sandra Dee" collide with "John Smith": tb.key_hsh[3] = tb.key_hsh[0]
# Eliminate excess keys: if op.nkeys <= 4 : # Delete "Ted Baker": tb.exclude_candidate_key(op, 4) if op.nkeys <= 3 : # Delete "Sam Doe": tb.exclude_candidate_key(op, 2)
sys.stderr.write("tb.key_str = %r\n" % tb.key_str) sys.stderr.write("tb.val_str = %r\n" % tb.val_str) sys.stderr.write("tb.key_hsh = %r\n" % tb.key_hsh) sys.stderr.write("tb.max_hsh = %r\n" % tb.max_hsh) assert(tb.nkeys == op.nkeys) ################################################################
def exclude_candidate_key(tb, op, k) : "Excludes a key from the key tables.\n" \ "\n" \ " Excludes key number {k} from {tb.key_str[],tb.val_str[],tb.key_hsh[]}. If {op.sparse}" \ " is false, adjusts {tb.key_hsh[]} so that it remains surjective after the deletion." h = tb.key_hsh[k] tb.key_str[k:k+1] = [] tb.val_str[k:k+1] = [] tb.key_hsh[k:k+1] = [] tb.nkeys = tb.nkeys - 1 if op.sparse : return for i in range(tb.nkeys) : if tb.key_hsh[i] == h : # Some other key maps to the hash {h}, so no adjustment is needed. return # Eliminate {h} from the hash function's range: for i in range(tb.nkeys) : if tb.key_hsh[i] > h : tb.key_hsh[i] = tb.key_hsh[i] - 1 tb.max_hsh = tb.max_hsh - 1
def choose_and_assign_buckets(tb, op) : "Chooses which hashes and buckets to show, and assigns them to the keys.\n" \ "\n" \ " Defines {tb.nbucs}, the number of slots to show in the hash/bucket" \ " column (including the \"vdots\" slots). Sets {tb.buc_hsh[j]} to the" \ " hash value to be shown for the slot (or -1 for \"vdots\")\n" \ "\n" \ " Simulates the hash table algorithm for the key" \ " hashes {tb.key_hsh[0..tb.nkeys-1]}.\n" \ "\n" \ " For each key index {i}, sets {tb.key_bix[i]} to the index of the bucket where the" \ " key hashes to, and {tb.key.sty[i]} to the style to use for the key ('N' or 'C').\n" \ "\n" \ " For each bucket index {j}, sets {tb.buc_kix[j]} to the index of the key" \ " that is stored in the bucket (if any). Also sets {tb.buc_hsh_sty[j]} to" \ " the style to use for the bucket ('U', 'C', 'N', or ':').\n" \ "\n" \ " The indices {j} are indices into the bucket-related arrays, such" \ " as {tb.buc_hsh[]}, which are a compressed subset of the actual table buckets." sys.stderr.write("entering {choose_and_assign_buckets}\n") # Initially assume that all buckets are visible: tb.buc_hsh = [] tb.nbucs = tb.max_hsh + 1 for h in range(tb.nbucs) : tb.buc_hsh[h:h] = [ h ] # Initialize {tb.key_bix[i],tb.key.sty[i],tb.buc_kix[j],tb.buc_hsh_sty[j]} with all nulls: tb.key_sty = [ 'N' ]*tb.nkeys tb.key_bix = [ -1 ]*tb.nkeys tb.buc_kix = [ -1 ]*tb.nbucs tb.buc_hsh_sty = [ 'U' ]*tb.nbucs # Assign buckets to keys: for i in range(tb.nkeys) : tb.assign_bucket_to_key(i)
# Set {bvs[h]} to 1 iff bucket {h} of the table is to be shown: bvs = [ 0 ] * (tb.max_hsh + 1) # Initially all invisible. for h in range(tb.nbucs) : i = tb.buc_kix[h] if i >= 0 : # Mark bucket {h} and its two neighbors as visible: assert(i < tb.nkeys) bvs[h] = 1; if h > 0 : bvs[h-1] = 1 if h < tb.max_hsh : bvs[h+1] = 1 # The first and last buckets must be shown in any case: bvs[0] = 1 bvs[tb.max_hsh] = 1
sys.stderr.write("--- before squeezing ---\n") sys.stderr.write("tb.key_bix = %r\n" % tb.key_bix) sys.stderr.write("tb.buc_hsh = %r\n" % tb.buc_hsh) sys.stderr.write("tb.buc_hsh_sty = %r\n" % tb.buc_hsh_sty) sys.stderr.write("tb.buc_kix = %r\n" % tb.buc_kix)
# Now squeeze the bucket column entries, set {tb.buc_hsh_sty}: h = 0 # Next hash to consider tb.nbucs = 0 # Number of squeezed buckets while h <= tb.max_hsh : if (h < tb.max_hsh) and bvs[h+1] : # No use to omit a single slot: bvs[h] = 1 if bvs[h] : # Slot {h} is to be shown: sys.stderr.write("relocating slot %d (kix = %d) to slot %d\n" % (h,tb.buc_kix[h],tb.nbucs)) # Fix all ket-to-buck pointers: for i in range(tb.nkeys) : if tb.key_bix[i] == h : # Relocate the key-to-bucket pointer: sys.stderr.write(" key %d was hashed to bucket %d, now %d\n" % (i,tb.key_bix[i],tb.nbucs)) tb.key_bix[i] = tb.nbucs # Relocate bucket {h} to bucket {tb.nbucs}, increment {h}: tb.buc_hsh[tb.nbucs] = h tb.buc_hsh_sty[tb.nbucs] = tb.buc_hsh_sty[h] tb.buc_kix[tb.nbucs] = tb.buc_kix[h] h = h + 1 else : # {h} is the start of 2 or more slots that are not relevant: # Append -1 to the list, skip all invisible buckets: sys.stderr.write("slot %d starts a gap; squeezed to slot %d\n" % (h,tb.nbucs)) tb.buc_hsh[tb.nbucs] = -1 tb.buc_hsh_sty[tb.nbucs] = ':' tb.buc_kix[tb.nbucs] = -1 while (h <= tb.max_hsh) and not bvs[h] : h = h + 1 tb.nbucs = tb.nbucs + 1
# Truncate the bucket arrays: tb.buc_hsh[tb.nbucs:len(tb.buc_hsh)] = [] tb.buc_kix[tb.nbucs:len(tb.buc_kix)] = [] tb.buc_hsh_sty[tb.nbucs:len(tb.buc_hsh_sty)] = []
sys.stderr.write("--- after squeezing ---\n") sys.stderr.write("tb.key_bix = %r\n" % tb.key_bix) sys.stderr.write("tb.buc_hsh = %r\n" % tb.buc_hsh) sys.stderr.write("tb.buc_hsh_sty = %r\n" % tb.buc_hsh_sty) sys.stderr.write("tb.buc_kix = %r\n" % tb.buc_kix) assert(tb.nbucs == len(tb.buc_hsh)) ################################################################
def gather_overflow_entries(tb, op) : "Gathers the overflow entries of each bucket, and sets bucket-overflow pointers.\n" \ "\n" \ " Sets sets {tb.novfs} to the number of entries to show in the overflow column.\n" \ "\n" \ " For each overflow entry {k}, sets {tb.ovf_kix[k]} to the index of the key" \ " that is stored in that entry, or -1 if none. Also sets {tb.ovf.pix[k]} to" \ " the indes {k'} of the next slot in the bucket's chain, or -1 if none.\n" \ "\n" \ " For each bucket index {j}, sets {tb.buc_oix[j]} to the index of the overflow" \ " slot where the first entry of that bucket is stored, or -1 if none." \ " increments" tb.buc_oix = [ -1 ]*tb.nbucs tb.novfs = 0 tb.ovf_kix = [ ] tb.ovf_pix = [ ] for j in range(tb.nbucs) : if tb.buc_hsh[j] == -1 : tb.buc_hsh_sty[j] = ':' tb.gather_bucket_overflow(j) ################################################################
def assign_bucket_to_key(tb,i) : "Finds the bucket where key number {i} hashes to and its the hash arrow.\n" \ "\n" \ " Finds the index {bix} of the bucket where key number {i} hashes to. Sets" \ " {tb.key_bix[i]} to {bix}. If no one has hashed or is living there yet, sets" \ " {tb.buc_kix[bix]} to {i}; otherwise leaves {tb.buc_kix[bix]} unchanged" \ " and sets the styles of the bucket and of the two keys to 'C'.\n" \ "\n" \ " If the table uses sequential probing and the bucket {bix} is occupied,\n" \ " finds the next free slot {bsx} and stores the key there, setting {tb.buc_kix[bsx]} to {i}" \ "\n" \ " If key {i} has hash -1, returns -1."
sys.stderr.write("key %d = %s hash = %d\n" % (i, tb.key_str[i], tb.key_hsh[i])) if tb.key_hsh[i] == -1 : # A hashless key? tb.key_sty[i] = 'C'; tb.key_bix[i] = -1 sys.stderr.write(" hashless key\n") else : # Find the index {tb.key_bix[i]} of bucket where this key is hashed into: bix = -1 for j in range(tb.nbucs) : if tb.key_hsh[i] == tb.buc_hsh[j] : bix = j sys.stderr.write(" hashed to slot %d = %d\n" % (bix, tb.buc_kix[bix])) assert (bix != -1) # The hash of every key must be visible. assert (tb.buc_hsh[bix] == tb.key_hsh[i]) # Paranoia. # Remember the bucket where the key is hashed to: tb.key_bix[i] = bix # Update the key and bucket styles, then set {bsx} to the # index of the bucket where the entry can be stored, or to -1: if tb.buc_kix[bix] == -1 : # No key has hashed into this bucket yet. sys.stderr.write(" first hash to this slot\n") tb.buc_kix[bix] = i tb.buc_hsh_sty[bix] = 'N' else : # Some other key was previously hashed to this bucket. sys.stderr.write(" hashed slot %d is occupied by key %d = %s\n" % (bix, tb.buc_kix[bix], tb.key_str[tb.buc_kix[bix]])) # Flag the collision: tb.key_sty[i] = 'C'; tb.key_sty[tb.buc_kix[bix]] = 'C'; tb.buc_hsh_sty[bix] = 'C' if op.overflow == 'SP' : # Must assign the next available bucket to key {i}. bsx = (bix + 1) % tb.nbucs while (bsx < tb.nbucs) and (bsx != bix) : # Try allocating to bucket {bsx}: sys.stderr.write(" trying slot %d = %d\n" % (bsx, tb.buc_kix[bsx])) assert (tb.buc_hsh[bsx] != -1) # Cannot store into invisible buckets. if tb.buc_kix[bsx] == -1 : break tb.buc_hsh_sty[bsx] = 'C' bsx = (bsx + 1) % tb.nbucs assert (bsx != bix) tb.buc_kix[bsx] = i tb.buc_hsh_sty[bsx] = 'N' sys.stderr.write(" finally assigned to slot %d hash = %d\n" % (bsx, tb.buc_hsh[bsx])) ################################################################
def gather_bucket_overflow(tb,j) : "Allocates the overflow records of bucket {j}.\n" \ "\n" \ " If the table does not store keys nor values, there is no point in" \ " having a overflow column.\n" \ "\n" \ " For \'LL\' type tables, gathers all keys that hash into bucket {j}" \ " and allocates records in the overflow column. If buckets are not" \ " links, excludes the first of those entries.\n" \ "\n" \ " For \'SP\' type tables, if the buckets are just links, allocates" \ " the record coresponding to bucket {j} in the overflow" \ " column. If buckets are whole entries, does nothing.\n" \ "\n" \ " In any case, sets {tb.buc_oix[j],tb.ovf_kix[k],tb.ovf.pix[k]} and" \ " increments {tb.novfs} as appropriate."
# Default case: tb.buc_oix[j] = -1 if tb.buc_kix[j] == -1 : return
if not (op.keys or op.values) : # There is no point in having overflow records: return if op.overflow == 'SP' : if op.links : # Make link to single entry: tb.buc_oix[j] = tb.alloc_overflow_record(tb.buc_kix[j]) else : # Nothing to gather: return elif op.overflow == 'LL' : # Gather all keys that hash to this bucket: for i in range(tb.nkeys) : if tb.key_bix[i] == j and (op.links or (tb.buc_kix[j] != i)) : # This key should go to overflow: eix = tb.alloc_overflow_record(i) if (tb.buc_oix[j] == -1) : # First overflow of this bucket: tb.buc_oix[j] = eix else : # Append overflow record to previous record: tb.ovf_pix[eix-1] = eix else : assert(0) # Should have caught this when parsing the command args. ################################################################ def alloc_overflow_record(tb,i) : "Allocates a record for key number {i} in the overflow column.\n" \ "\n" \ " Allocates a record for key number {i} at the next available" \ " position {k = tb.novfs} in the overflow column. Sets" \ " {tb.ovf_kix[k]} to {i}, {tb.ovf_pix[k]} to -1, and" \ " increments {tb.novfs}. Returns {k}." k = tb.novfs tb.novfs = tb.novfs + 1 tb.ovf_kix[k:k] = [ i ] tb.ovf_pix[k:k] = [ -1 ] return k ################################################################ ################################################################
class Dimensions :
def __init__(dim, op,tb) :
# All Y positions are relative to the figure minus headers and margins. # Number of digits in hash value: if tb.max_hsh < 10 : dim.hsh_ndg = 1 # Number of digits in hash value. elif tb.max_hsh < 100 : dim.hsh_ndg = 2 # Number of digits in hash value. elif tb.max_hsh < 1000 : dim.hsh_ndg = 3 # Number of digits in hash value. else : assert(0)
# --- Determine widths of main items ---
# Determine the width of the key, value, and pointer boxes: dim.key_box_wx = 90 # X size of key box. dim.val_box_wx = 80 # X size of value box. dim.ptr_box_wx = 20 # X size of pointer box.
# Determine the width of the function box: if op.funcbox : dim.fun_box_wx = 70 # X size of hash function box (if visible). else: dim.fun_box_wx = 30 # X size of hash function box (if invisible).
# Determine the width of the hashval box: dim.hsh_box_wx = 10 + 10*dim.hsh_ndg # X size of hashval box. # Determine the width of the bucket box: dim.buc_box_wx = 0 if tb.buc_has_key : dim.buc_box_wx = dim.buc_box_wx + dim.key_box_wx if tb.buc_has_val : dim.buc_box_wx = dim.buc_box_wx + dim.val_box_wx if tb.buc_has_ptr : dim.buc_box_wx = dim.buc_box_wx + dim.ptr_box_wx assert((tb.has_buc_box == 0) == (dim.buc_box_wx == 0))
# Determine the width of the overflow entry box: dim.ovf_box_wx = 0 if tb.ovf_has_key : dim.ovf_box_wx = dim.ovf_box_wx + dim.key_box_wx if tb.ovf_has_val : dim.ovf_box_wx = dim.ovf_box_wx + dim.val_box_wx if tb.ovf_has_ptr : dim.ovf_box_wx = dim.ovf_box_wx + dim.ptr_box_wx assert((tb.novfs == 0) == (dim.ovf_box_wx == 0)) # --- Determine th X spacings between main items ---
# This should be zero if {dim.buc_box_wx} is zero: dim.buc_col_sx = 0 # X spacing between hashes column and buckets column.
# Padding needed after key box: key_pad_x = 10
# Padding needed around function box: if op.funcbox : # Need padding for column header: fun_pad_x = max(80 - dim.fun_box_wx, 0) / 2 else : # Minimal padding: fun_pad_x = 10
# Padding needed around hash+bucket column (for header): hbu_pad_x = max(90 - (dim.hsh_box_wx + dim.buc_col_sx + dim.buc_box_wx), 20)/2 # Padding needed before overflow column (for header): ovf_pad_x = max(90 - (dim.ovf_box_wx), 20)/2 # X spacing between key boxes and function box: dim.fun_col_sx = key_pad_x + fun_pad_x
# X spacing between function box and hash box: dim.hsh_col_sx = fun_pad_x + hbu_pad_x
# Choose the X spacing between bucket box and the overflow boxes. # This should be zero if {dim.ovf_box_wx} is zero: if dim.ovf_box_wx == 0 : dim.ovf_col_sx = 0 else : dim.ovf_col_sx = hbu_pad_x + ovf_pad_x
# X size of diagram proper (minus margins): dim.diag_wx = \ dim.key_box_wx + \ dim.fun_col_sx + dim.fun_box_wx + \ dim.hsh_col_sx + dim.hsh_box_wx + \ dim.buc_col_sx + dim.buc_box_wx + \ dim.ovf_col_sx + dim.ovf_box_wx
# Find padding needed for rightmost column with title: if tb.novfs > 0 : last_pad_x = ovf_pad_x + 10 else : last_pad_x = hbu_pad_x + 10
dim.diag_wx = dim.diag_wx + last_pad_x
# --- Determine item and column heights and Y spacings --- dim.box_wy = 20 # Y size of all text boxes.
dim.key_col_sy = 20 # Y spacing between boxes in key column.
# Choose {dim.ovf_col_sy}, the Y spacing between boxes in overflow entry column: if tb.novfs < 2 : dim.ovf_col_sy = dim.key_col_sy # Not used, but just in case... else : # Try to use the whole spce available: key_tmp_wy =tb.nkeys*(dim.box_wy + dim.key_col_sy) buc_tmp_wy =tb.nbucs*dim.box_wy tmp_wy = max(key_tmp_wy, buc_tmp_wy) tmp_sy = (tmp_wy - tb.novfs*dim.box_wy)/(tb.novfs + 1) if tmp_sy < 10 : dim.ovf_col_sy = 10 else : dim.ovf_col_sy = 10*int((tmp_sy + 9)/10)
# Compute minimum column heights: keys, function, hashes&buckets, overflow: key_col_raw_wy = tb.nkeys*dim.box_wy + (tb.nkeys - 1)*dim.key_col_sy hsh_col_raw_wy = tb.nbucs*dim.box_wy fun_col_raw_wy = max(key_col_raw_wy, hsh_col_raw_wy) ovf_col_raw_wy = tb.novfs*dim.box_wy + (tb.novfs - 1)*dim.ovf_col_sy
dim.fun_box_wy = fun_col_raw_wy # Y size of function box.
# Y size of diagram proper (minus margins and column headers): dim.diag_wy = max(fun_col_raw_wy, key_col_raw_wy, hsh_col_raw_wy, ovf_col_raw_wy)
# Top Y positions (relative to the figure minus headers and margins): dim.fun_col_ty = (dim.diag_wy - fun_col_raw_wy)/2 # Y position of function box. dim.key_col_ty = (dim.diag_wy - key_col_raw_wy)/2 # Y position of topmost key box. dim.hsh_col_ty = (dim.diag_wy - hsh_col_raw_wy)/2 # Y position of first hash value box. dim.buc_col_ty = dim.hsh_col_ty # Y position of first bucket box. dim.ovf_col_ty = (dim.diag_wy - ovf_col_raw_wy)/2 # Y position of first overflow entry box. # Column header dimensions: dim.tit_wy = 20 # Baseline spacing for column headers. dim.tit_sy = 10 # Spacing between bottom of headers and top of diagram proper.
dim.mrg_wx = 10 # X width of figure margin. dim.mrg_wy = 10 # Y width of figure margin.
# Total X and Y size of figure: dim.fig_wx = \ dim.mrg_wx + \ dim.diag_wx + \ dim.mrg_wx
dim.fig_wy = \ dim.mrg_wy + \ 2*dim.tit_wy + dim.tit_sy + \ dim.diag_wy + \ dim.mrg_wy
# Overall scale (after all dimensions): dim.scale = 1.0 ################################################################
################################################################
def output_figure(op) :
"Writes the figure to {stdout}." "\n" \ " Expects an {Options} instance {op}."
# Create the table: tb = HashTable(op)
# Computes the sizes of things: dim = Dimensions(op,tb)
output_figure_preamble(op,tb,dim) sys.stdout.write('\n') output_figure_obj_defs(op,tb,dim) sys.stdout.write('\n') output_figure_body(op,tb,dim) sys.stdout.write('\n') output_figure_postamble(op,tb,dim) sys.stderr.write("done.\n") ################################################################
def output_figure_preamble(op,tb,dim) :
"Writes the SVG preamble to {stdout}." sys.stdout.write( \ '<?xml version="1.0" encoding="UTF-8" standalone="no"?>\n' \ '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">\n' \ '\n' \ '\n' \ '<svg\n' \ ' xmlns="http://www.w3.org/2000/svg"\n' \ ' xmlns:xlink="http://www.w3.org/1999/xlink"\n' \ ' width="'+ dts(dim.scale*dim.fig_wx) +'"\n' \ ' height="'+ dts(dim.scale*dim.fig_wy) +'"\n' \ ' id="fig"\n' \ ' stroke-width="1px"\n' \ ' stroke-linejoin="round"\n' \ ' stroke-opacity="1"\n' \ ' stroke-linecap="round"\n' \ ' fill-opacity="1"\n' \ ' fill-rule="evenodd"\n' \ ' font-family="Bitstream Courier"\n' \ ' font-style="normal"\n' \ ' font-weight="normal"\n' \ ' pagecolor="#ffff00"\n' \ ' pageopacity="0.0">\n' \ ) sys.stdout.write('\n') if (op.back) : sys.stdout.write( \ ' \n' \ ' <rect x="000" y="000" width="'+ dts(dim.scale*dim.fig_wx) +'" height="'+ dts(dim.scale*dim.fig_wy) +'"' \ ' stroke="#000000" fill="#ffcc55"' \ ' />\n' \ ) sys.stdout.write('\n')
# Scale everything and position the diagram: diag_dx = dim.mrg_wx diag_dy = dim.mrg_wy + 2*dim.tit_wy + dim.tit_sy sys.stdout.write( \ ' <g\n' \ ' font-size="12px"\n' \ ' transform="scale('+ dts(dim.scale)+ ') translate('+ dts(diag_dx) + ','+ dts(diag_dy) + ')"\n' \ ' >\n' \ ) ################################################################
def output_figure_obj_defs(op,tb,dim) :
"Writes the main object definitions to {stdout}."
sys.stdout.write( \ ' <defs>\n' \ ' \n' \ ' <marker id="linkdot_N" viewBox="0 0 8 8" refX="4" refY="4" markerWidth="8" markerHeight="8" orient="auto">\n' \ ' <circle cx="4" cy="4" r="3" stroke="#000000" fill="#000000" />\n' \ ' </marker>\n' \ ' \n' \ ' <marker id="linkdot_U" viewBox="0 0 8 8" refX="4" refY="4" markerWidth="8" markerHeight="8" orient="auto">\n' \ ' <line x1="1" y1="1" x2="7" y2="7" stroke="#000000" />\n' \ ' <line x1="1" y1="7" x2="7" y2="1" stroke="#000000" />\n' \ ' </marker>\n' \ '\n' \ ' \n' \ ' <marker id="arrowtip_N" viewBox="0 0 14 8" refX="13" refY="4" markerWidth="14" markerHeight="8" orient="auto">\n' \ ' <polygon points="1,4 1,1 13,4 1,7" stroke="#000000" fill="#000000" />\n' \ ' </marker>\n' \ ' \n' \ ' <marker id="arrowtip_C" viewBox="0 0 14 8" refX="13" refY="4" markerWidth="14" markerHeight="8" orient="auto">\n' \ ' <polygon points="1,4 1,1 13,4 1,7" stroke="#cc0000" fill="#cc0000" />\n' \ ' </marker>\n' \ '\n' \ ' \n' \ ' <rect id="key_box_N" y="0" x="0" width="'+ dts(dim.key_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#00ffff" stroke-width="0px" stroke="none"' \ ' />\n' \ ' \n' \ ' <rect id="key_box_C" y="0" x="0" width="'+ dts(dim.key_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#00ffff" stroke-width="0px" stroke="none"' \ ' />\n' \ ' \n' \ ' <rect id="key_box_E" y="0" x="0" width="'+ dts(dim.key_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#9cff9c" stroke="#000000"' \ ' />\n' \ ' \n' \ ' <rect id="key_box_U" y="0" x="0" width="'+ dts(dim.key_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#ddeedd" stroke="#000000"' \ ' />\n' \ '\n' \ ' \n' \ ' <rect id="val_box_E" y="0" x="0" width="'+ dts(dim.val_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#9cff9c" stroke="#000000"' \ ' />\n' \ ' \n' \ ' <rect id="val_box_U" y="0" x="0" width="'+ dts(dim.val_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#ddeedd" stroke="#000000"' \ ' />\n' \ '\n' \ ' \n' \ ' <rect id="ptr_box_E" y="0" x="0" width="'+ dts(dim.ptr_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#9cff9c" stroke="#000000"' \ ' />\n' \ ' \n' \ ' <rect id="ptr_box_U" y="0" x="0" width="'+ dts(dim.ptr_box_wx) +'" height="'+ dts(dim.box_wy) +'"' \ ' fill="#ddeedd" stroke="#000000"' \ ' />\n' \ '\n' \ ' \n' \ ' <rect id="hsh_box_U" x="3" y="1" width="'+ dts(dim.hsh_box_wx-6) +'" height="'+ dts(dim.box_wy-2) +'"' \ ' fill="#ddeedd" stroke-width="0px" stroke="none"' \ ' />\n' \ ' \n' \ ' <rect id="hsh_box_N" x="3" y="1" width="'+ dts(dim.hsh_box_wx-6) +'" height="'+ dts(dim.box_wy-2) +'"' \ ' fill="#a8a8ff" stroke-width="0px" stroke="none"' \ ' />\n' \ ' \n' \ ' <rect id="hsh_box_C" x="3" y="1" width="'+ dts(dim.hsh_box_wx-6) +'" height="'+ dts(dim.box_wy-2) +'"' \ ' fill="#ee4444" stroke-width="0px" stroke="none"' \ ' />\n' \ '\n' \ ' \n' \ ' <g id="vdots">\n' \ ' <rect x="0" y="06" width="2" height="2" />\n' \ ' <rect x="0" y="12" width="2" height="2" />\n' \ ' </g>\n' \ ' </defs>\n' \ ) ################################################################
def output_figure_body(op,tb,dim) :
"Writes the body of the figure to {stdout}."
# All dimensions computed here are relative to the figure body (excluding titles and left margin).
# X positions and widths of the major sub-blocks: key_fun_block_dx = 0 key_fun_block_wx = dim.key_box_wx + dim.fun_col_sx + dim.fun_box_wx hsh_buc_block_dx = key_fun_block_dx + key_fun_block_wx + dim.hsh_col_sx hsh_buc_block_wx = dim.hsh_box_wx + dim.buc_col_sx + dim.buc_box_wx ovf_block_dx = hsh_buc_block_dx + hsh_buc_block_wx + dim.ovf_col_sx ovf_block_wx = dim.ovf_box_wx
# Key boxes, hash function box, and hash function arrows: sys.stdout.write( \ ' \n' \ ' <g transform="translate('+ dts(key_fun_block_dx) +',000)"\n' \ ' text-anchor="middle"\n' \ ' >\n' \ ) sys.stdout.write('\n') output_key_fun_block(op,tb,dim) sys.stdout.write('\n') sys.stdout.write( \ ' </g>\n' \ )
sys.stdout.write('\n')
# Hash values and bucket array: sys.stdout.write( \ ' \n' \ ' <g transform="translate('+ dts(hsh_buc_block_dx) + ',000)"\n' \ ' text-anchor="middle"\n' \ ' >\n' \ ) ovf_dx = ovf_block_dx - hsh_buc_block_dx # Displacment of overflow entries col relative to hashes col. sys.stdout.write('\n') output_hsh_buc_block(op,tb,dim, ovf_dx) sys.stdout.write('\n') sys.stdout.write( \ ' </g>\n' \ ) sys.stdout.write('\n')
if tb.novfs > 0 : # Overflow entries: sys.stdout.write( \ ' \n' \ ' <g transform="translate('+ dts(ovf_block_dx) + ',000)"\n' \ ' text-anchor="middle"\n' \ ' >\n' \ ) sys.stdout.write('\n') output_ovf_block(op,tb,dim) sys.stdout.write('\n') sys.stdout.write( \ ' </g>\n' \ ) ################################################################
def output_key_fun_block(op,tb,dim) :
"Writes the key and hash-function block to {stdout}."
# All dimensions computed here are relative to the hash function block. # Assumes that the top of the bucket block is aligned with the top of the key block.
# baselines of the two header lines: tit_dy_top = - dim.tit_sy - dim.tit_wy tit_dy_bot = - dim.tit_sy # X positions of the key and function boxes: key_box_dx = 0 key_box_tit_ax = key_box_dx + dim.key_box_wx/2
fun_box_dx = key_box_dx + dim.key_box_wx + dim.fun_col_sx fun_box_tit_ax = fun_box_dx + dim.fun_box_wx/2 # X position of function box title's anchor point.
if op.funcbox : # Title for function box: sys.stdout.write( \ ' <text x="'+ dts(fun_box_tit_ax) +'" y="'+ dts(tit_dy_top) +'" font-size="15px"' \ ' font-weight="bold" fill="#000000" stroke-width="0px" stroke="none">' \ ' hash ' \ ' </text>\n' \ ' <text x="'+ dts(fun_box_tit_ax) +'" y="'+ dts(tit_dy_bot) +'" font-size="15px"' \ ' font-weight="bold" fill="#000000" stroke-width="0px" stroke="none">' \ ' function' \ ' </text>\n' \ ) sys.stdout.write('\n')
# Function box (must paint it first to get correct layer depth): fun_ty = dim.fun_col_ty sys.stdout.write( \ ' <rect x="'+ dts(fun_box_dx) +'" y="'+ dts(fun_ty) +'"' \ ' width="'+ dts(dim.fun_box_wx) +'" height="'+ dts(dim.fun_box_wy) +'"' \ ' fill="#aaeecc" stroke-width="0px" stroke="none"' \ ' />\n' \ ) sys.stdout.write('\n') # Title for column of key boxes: sys.stdout.write( \ ' <text x="'+ dts(key_box_tit_ax) +'" y="'+ dts(tit_dy_bot) +'" font-size="15px"' \ ' font-weight="bold" fill="#000000" stroke-width="0px" stroke="none">' \ ' keys\n' \ ' </text>\n' \ ) sys.stdout.write('\n')
# Column of key boxes: key_ty = dim.key_col_ty # Y position of next key box. for i in range(tb.nkeys) : # Compute top Y {hsh_ty} of corresponding hash value box: hsh_ty = dim.hsh_col_ty + dim.box_wy*tb.key_bix[i] sys.stdout.write( \ ' <g transform="translate('+ dts(key_box_dx) + ','+ dts(key_ty) +')">\n' \ ) output_key_fun_block_item(op,tb,dim, tb.key_str[i], tb.key_sty[i], hsh_ty - key_ty) sys.stdout.write( \ ' </g>\n' \ ) key_ty = key_ty + dim.box_wy + dim.key_col_sy ################################################################
def output_key_fun_block_item(op,tb,dim, kstr, ksty, hsh_box_dy) :
"Writes one key box and its function arrow to {stdout}." "\n" \ " Expects the key string {kstr}, its style {ksty} ('N', 'C', etc.)" \ " and the Y displacement {hsh_box_dy} between" \ " the top of the key box and the top of the correspondng hash value box."
# All positions computed here are relative to the upper left corner of the key box.
# X positions of main points of of hash arrow: arr_B_x = dim.key_box_wx + dim.fun_col_sx/2 # Start of bent arrow arr_L_x = dim.key_box_wx + dim.fun_col_sx # First bend. arr_R_x = arr_L_x + dim.fun_box_wx # Second bend. arr_T_x = arr_R_x + dim.hsh_col_sx # End of arrow.
if op.funcbox : # Move the bends inwards: arr_L_x = arr_L_x + 5 # First bend. arr_R_x = arr_R_x - 5 # Second bend. # Y positions of left and right ends of of hash arrow: arr_L_y = dim.box_wy/2 arr_R_y = arr_L_y - dim.box_wy/2 + hsh_box_dy + dim.box_wy/2 if ksty == 'C' : arr_color = '#dd0000' else : arr_color = '#000000' key_str_ax = dim.key_box_wx/2 # X position of key string anchor point rel to key box. sys.stdout.write( \ ' <use xlink:href="#key_box_'+ ksty +'" />\n' \ ' <text x="'+ dts(key_str_ax) +'" y="14" stroke-width="0px" stroke="none">'+ kstr +'</text>\n' \ ' <line' \ ' x1="'+ dts(arr_B_x) +'" y1="'+ dts(arr_L_y) +'"' \ ' x2="'+ dts(arr_L_x) +'" y2="'+ dts(arr_L_y) +'"' \ ' stroke="'+ arr_color +'"' \ ' />\n' \ ' <line' \ ' x1="'+ dts(arr_L_x) +'" y1="'+ dts(arr_L_y) +'"' \ ' x2="'+ dts(arr_R_x) +'" y2="'+ dts(arr_R_y) +'"' \ ' stroke="'+ arr_color +'"' \ ' />\n' \ ' <line' \ ' x1="'+ dts(arr_R_x) +'" y1="'+ dts(arr_R_y) +'"' \ ' x2="'+ dts(arr_T_x) +'" y2="'+ dts(arr_R_y) +'"' \ ' stroke="'+ arr_color +'"' \ ' marker-end="url(#arrowtip_'+ ksty +')"' \ ' />\n' \ ) ################################################################
def output_hsh_buc_block(op,tb,dim, ovf_dx) :
"Writes the hash-value and bucket-array block to {stdout}." # All dimensions computed here are relative to the hash function block.
# X positions of the hash and bucket boxes: hsh_box_dx = 0
# baselines of the two header lines: tit_dy_top = - dim.tit_sy - dim.tit_wy tit_dy_bot = - dim.tit_sy
if dim.buc_box_wx > 0 : tit_str = 'buckets' tit_ax = hsh_box_dx + dim.hsh_box_wx + dim.buc_col_sx + dim.buc_box_wx/2 else : tit_str = 'hashes' tit_ax = hsh_box_dx + dim.hsh_box_wx/2 # Title for column of hash values: sys.stdout.write( \ ' <text x="'+ dts(tit_ax) +'" y="'+ dts(tit_dy_bot) +'" font-size="15px"' \ ' font-weight="bold" fill="#000000" stroke-width="0px" stroke="none">\n' \ ' '+ tit_str + '\n' \ ' </text>\n' \ ) sys.stdout.write('\n')
# Column of hash boxes and buckets: hsh_ty = dim.hsh_col_ty # Y position of next hash box. for j in range(tb.nbucs) : sys.stdout.write( \ ' <g transform="translate(000,'+ dts(hsh_ty) + ')">\n' \ ) # Compute Y displacement {ovf_dy} between top of bucket box and top of overflow box (if any): if tb.buc_oix[j] != -1 : ovf_ty = dim.ovf_col_ty + tb.buc_oix[j]*(dim.box_wy + dim.ovf_col_sy) # Top of overflow box. ovf_dy = ovf_ty - hsh_ty else : ovf_dy = None if tb.buc_hsh[j] < 0 : hsh_str = ':' else : hsh_str = ("%0*d" % (dim.hsh_ndg, tb.buc_hsh[j])) output_hsh_buc_block_item(op,tb,dim, hsh_str, tb.buc_hsh_sty[j], tb.buc_kix[j], tb.buc_oix[j], ovf_dx, ovf_dy) sys.stdout.write( \ ' </g>\n' \ ) hsh_ty = hsh_ty + dim.box_wy ################################################################
def output_hsh_buc_block_item(op,tb,dim, hstr, hsty, kix, oix, ovf_dx, ovf_dy) :
"Writes one hash value box, its bucket box, and the pointer (if any) to {stdout}." "\n" \ " Expects the formatted hash value string {hstr}, its style {hsty} ('N', 'C', 'U', or ':')" \ " and the Y displacement {ovf_dy} between the top of the bucket box and" \ " the top of the pointed entry box. Also gets the index {kix} of" \ " the key which is stored into the bucket, or -1 if the bucket" \ " is vacant or a vdots. This index is used to obtain the" \ " entry's key and/or value.\n" \ "\n" \ " Also requires index {oix} of the overflow entry that the bucket points to, or -1 if" \ " not applicable. If {oix} is not -1, also expects the displacements {ovf_dx,ovf_dy} from" \ " the top left corner of the hash box to the top left corner of that overflow box." box_dx = 0;
# Hash value box: box_wx = dim.hsh_box_wx; output_box(op,tb,dim, box_dx, 'hsh_box', hsty, box_wx, hstr) box_dx = box_dx + box_wx
# Choose the style for the bucket box and null pointers in it: if hsty == ':' : bsty = ':' psty = ':' elif kix == -1 : bsty = 'U' psty = 'U' else : bsty = 'E' psty = 'N'
if tb.buc_has_key : # Stored key box: box_wx = dim.key_box_wx; if kix == -1 : bstr = else : bstr = tb.key_str[kix] output_box(op,tb,dim, box_dx, 'key_box', bsty, box_wx, bstr) box_dx = box_dx + box_wx
if tb.buc_has_val : # Stored value box: box_wx = dim.val_box_wx; if kix == -1 : bstr = else : bstr = tb.val_str[kix] output_box(op,tb,dim, box_dx, 'val_box', bsty, box_wx, bstr) box_dx = box_dx + box_wx
if tb.buc_has_ptr : # Pointer box in bucket: box_wx = dim.ptr_box_wx; output_box(op,tb,dim, box_dx, 'ptr_box', bsty, box_wx, ) if bsty != ':' : output_buc_ovf_arrow(op,tb,dim, box_dx, box_wx, psty, oix, ovf_dx, ovf_dy) box_dx = box_dx + box_wx ################################################################
def output_buc_ovf_arrow(op,tb,dim, box_dx, box_wx, psty, oix, ovf_dx, ovf_dy) :
"Writes an arrow from a bucket pointer to an overflow entry {stdout}.\n" \ "\n" \ " Requires the X position and width of the link box, and the index {oix}" \ " of the overflow entry that the bucket points to. If {oix} is -1, assumes" \ " that the link is null, and draws a marker \"linkdot_{psty}\" where {psty} should" \ " be either \"N\" or \"U\". If {oix} is not -1, also" \ " expects the displacements {ovf_dx,ovf_dy} from the top left corner of the hash box" \ " to the top left corner of that overflow box; in that case {psty} had better be \"N\"."
# All positions computed here are relative to the upper left corner of the key box.
# X positions of main points of of hash arrow: arr_B_x = box_dx + box_wx/2 # Start X of arrow arr_B_y = dim.box_wy/2 # Start Y of arrow if oix < 0 : # Null pointer - use a very short arrow with base but not tip: arr_T_x = arr_B_x + 0.001 # End X of arrow. arr_T_y = arr_B_y # End Y of arrow. else : # Non-null pointer: point to the mille of the left side of the target box: arr_T_x = ovf_dx # End X of arrow. arr_T_y = ovf_dy + dim.box_wy/2 # End Y of arrow.
sys.stdout.write( \ ' <line' \ ' x1="'+ dts(arr_B_x) +'" y1="'+ dts(arr_B_y) +'"' \ ' x2="'+ dts(arr_T_x) +'" y2="'+ dts(arr_T_y) +'"' \ ' stroke="#000000"' \ ' marker-start="url(#linkdot_'+ psty + ')"' \ ) if oix >= 0 : sys.stdout.write( \ ' marker-end="url(#arrowtip_N)"' \ ) sys.stdout.write( \ ' />\n' \ ) ################################################################
def output_ovf_block(op,tb,dim) :
"Writes the overflow entries block to {stdout}." # All dimensions computed here are relative to the overflow entries block.
# X positions of the overflow boxes: ovf_box_dx = 0
# Baselines and alignment of the two header lines: tit_dy_top = - dim.tit_sy - dim.tit_wy tit_dy_bot = - dim.tit_sy tit_ax = dim.ovf_box_wx/2 # Title for column of overflow entries: if op.links == 0 : sys.stdout.write( \ ' <text x="'+ dts(tit_ax) +'" y="'+ dts(tit_dy_top) +'" font-size="15px"' \ ' font-weight="bold" fill="#000000" stroke-width="0px" stroke="none">\n' \ ' overflow\n' \ ' </text>\n' \ ) sys.stdout.write( \ ' <text x="'+ dts(tit_ax) +'" y="'+ dts(tit_dy_bot) +'" font-size="15px"' \ ' font-weight="bold" fill="#000000" stroke-width="0px" stroke="none">\n' \ ' entries\n' \ ' </text>\n' \ ) sys.stdout.write('\n')
# Column of overflow entries: ovf_ty = dim.ovf_col_ty # Y position of next overflow entry. for j in range(tb.novfs) : sys.stdout.write( \ ' <g transform="translate(000,'+ dts(ovf_ty) + ')">\n' \ ) output_ovf_block_item(op,tb,dim, tb.ovf_kix[j], tb.ovf_pix[j]) sys.stdout.write( \ ' </g>\n' \ ) ovf_ty = ovf_ty + dim.box_wy + dim.ovf_col_sy ################################################################
def output_ovf_block_item(op,tb,dim, kix, pix) :
"Writes one overflow entry box and its pointer (if any) to {stdout}." "\n" \ " Expects the index {kix} of the key to which the entry belongs. Also expects" " the index {pix} of the next block in the chain, or -1 if none." box_dx = 0;
assert (kix != -1)
# Overfow entries are never vacant or ':': bsty = 'E'
if tb.ovf_has_ptr : # Entry pointer box: box_wx = dim.ptr_box_wx; output_box(op,tb,dim, box_dx, 'ptr_box', bsty, box_wx, ) ptr_dy = dim.box_wy + dim.ovf_col_sy output_ovf_ptr_arrow(op,tb,dim, box_dx, box_wx, pix, ptr_dy) box_dx = box_dx + box_wx if tb.ovf_has_key : # Stored key box: box_wx = dim.key_box_wx; bstr = tb.key_str[kix] output_box(op,tb,dim, box_dx, 'key_box', bsty, box_wx, bstr) box_dx = box_dx + box_wx
if tb.ovf_has_val : # Stored value box: box_wx = dim.val_box_wx; bstr = tb.val_str[kix] output_box(op,tb,dim, box_dx, 'val_box', bsty, box_wx, bstr) box_dx = box_dx + box_wx ################################################################
def output_ovf_ptr_arrow(op,tb,dim, box_dx, box_wx, pix, ptr_dy) :
"Writes an arrow from an overflow entry to the entry below it {stdout}.\n" \ "\n" \ " Requires the X position and width of the link box, and the index {pix}" \ " of the next overflow entry. If {pix} is -1, assumes that the link is null, and" \ " draws some appropriate symbol. If {pix} is not -1, also expects the" \ " Y displacement {ptr_dy} from the top left corner of the link box" \ " to the top left corner of the link box of the linked-to entry.\n" \ "\n" \ " At present, uses a straight arrow, so the two entries must be" \ " consecutive in the overflow column."
# All positions computed here are relative to the upper left corner of the key box.
# X positions of main points of of hash arrow: arr_B_x = box_dx + box_wx/2 # Start X of arrow arr_B_y = dim.box_wy/2 # Start Y of arrow if pix < 0 : # Null pointer - use a very short arrow with base but not tip: arr_T_x = arr_B_x # End X of arrow. arr_T_y = arr_B_y + 0.001 # End Y of arrow. else : # Non-null pointer: point to the mille of the left side of the target box: arr_T_x = arr_B_x # End X of arrow. arr_T_y = ptr_dy # End Y of arrow.
sys.stdout.write( \ ' <line' \ ' x1="'+ dts(arr_B_x) +'" y1="'+ dts(arr_B_y) +'"' \ ' x2="'+ dts(arr_T_x) +'" y2="'+ dts(arr_T_y) +'"' \ ' stroke="#000000"' \ ) if pix < 0 : sys.stdout.write( \ ' marker-start="url(#linkdot_U)"' \ ) else : sys.stdout.write( \ ' marker-start="url(#linkdot_N)"' \ ' marker-end="url(#arrowtip_N)"' \ ) sys.stdout.write( \ ' />\n' \ )
################################################################
def output_box(op,tb,dim, box_dx, btyp, bsty, box_wx, str) :
"Outputs a single box of an entry in the bucket array or overflow area.\n" \ "\n" \ " Takes the box X position {box_dx}, the box type {btyp}" \ " (\'key_box\', \'hsh_box\', etc.), the box style" \ " {bsty} (\'N\', \'C\',etc.),the box width {box_wx}, and" \ " the string to display inside the box. If {bsty} is \':\', omits" \ " the box and shows only the \':\' in bold type." str_ax = box_dx + box_wx/2 # X position of key string anchor point rel to key box. if bsty == ':' : sys.stdout.write( \ ' <text x="'+ dts(str_ax) +'" y="14" font-weight="bold">:</text>\n' \ ) else: sys.stdout.write( \ ' <use x="'+ dts(box_dx) +'" xlink:href="#'+ btyp + '_'+ bsty + '" />\n' \ ) if (str != ':') and (str != ) : sys.stdout.write( \ ' <text x="'+ dts(str_ax) +'" y="14">' + str +'</text>\n' \ ) ################################################################
def output_figure_postamble(op,tb,dim) :
"Writes the SVG postamble to {stdout}."
sys.stdout.write( \ ' </g>\n' \ '</svg>\n' \ )
- Main program:
op = parse_args(pp) output_figure(op)