text: from algs14_hashtable.entry import LinkedEntry
  
  
  class SortedLinkedListsHashtable:
      """
      Hashtable using array of M linked lists where keys appear in sorted order.
      """
  
      def __init__(self, M=10):
          self.table = [None] * M
          if M < 1:
              raise ValueError('Hashtable storage must be at least 1.')
          self.M = M
          self.N = 0
  
      def __len__(self):
          return self.N
  
      def get(self, k):
          """
          Retrieve value associated with key, k. STOP when entry is bigger than key.
          """
          # First place it could be
          hc = hash(k) % self.M
          entry = self.table[hc]
          while entry:
              # Doesn't exist since keys in sorted order
              if entry.key > k:
                  return None
              if entry.key == k:
                  return entry.value
              entry = entry.next
          # Couldn't find
          return None
  
      def put(self, k, v):
          """
          Associate value, v, with the key, k.
          """
          # First place it could be
          hc = hash(k) % self.M
          entry = self.table[hc]
          if entry is None:
              self.N += 1
              self.table[hc] = LinkedEntry(k, v, self.table[hc])
              return
          prev = None
          while entry:
              # Can insert since we didn't find
              if entry.key > k:
                  self.N += 1
                  # new First
                  if prev is None:
                      self.table[hc] = LinkedEntry(k, v, entry)
                  else:
                      prev.next = LinkedEntry(k, v, entry)
                  return
              # Overwrite if already here
              if entry.key == k:
                  entry.value = v
                  return
              prev, entry = entry, entry.next
          # If we get here, key is largest among all, so append to end
          prev.next = LinkedEntry(k, v)
          self.N += 1
  
      def remove(self, k):
          """
          Remove (k,v) entry associated with k.
          """
          # First place it could be
          hc = hash(k) % self.M
          entry = self.table[hc]
          prev = None
          while entry:
              if entry.key == k:
                  if prev:
                      prev.next = entry.next
                  else:
                      self.table[hc] = entry.next
                  self.N -= 1
                  return entry.value
              prev, entry = entry, entry.next
          # Nothing was removed
          return None
  
      def __iter__(self):
          """
          Generate all (k, v) tuples for entries in all linked lists table.
          """
          for entry in self.table:
              while entry:
                  yield (entry.key, entry.value)
                  entry = entry.next
  
  
  def evaluate_hashtable_sorted_chains(output=True, decimals=4):
      """
      Evaluate performance of separate chaining Hashtable with sorted entries.
      """
      import timeit
      from common.table import DataTable
      print('Best Case Build Time')
      tbl = DataTable([8, 20, 20, 20], ['M', 'Open Addressing',
                      'Separate Chaining', 'Sorted Chains'], output=output, decimals=decimals)
  
      for size in [214129, 524287, 999983]:
          timing_oa = min(timeit.repeat(stmt='''
  ht = OpenHashtable({})
  for w in reversed(words[:160564]):
      ht.put(w,w)'''.format(size), setup='''
  from algs14_hashtable.hashtable_open import OpenHashtable
  from resources.english import english_words
  words = english_words()''', repeat=7, number=5))/5
  
          timing_sc = min(timeit.repeat(stmt='''
  ht = LinkedHashtable({})
  for w in reversed(words[:160564]):
      ht.put(w,w)'''.format(size), setup='''
  from algs14_hashtable.hashtable_linked import LinkedHashtable
  from resources.english import english_words
  words = english_words()''', repeat=7, number=5))/5
  
          timing_sorted = min(timeit.repeat(stmt='''
  ht = SortedLinkedListsHashtable({})
  for w in reversed(words[:160564]):
      ht.put(w,w)'''.format(size), setup='''
  from algs14_hashtable.hashtable_linked_sorted import SortedLinkedListsHashtable
  from resources.english import english_words
  words = english_words()''', repeat=7, number=5))/5
          tbl.row([size, timing_oa, timing_sc, timing_sorted])
  
      print('Worst Case Build Time')
      tbl = DataTable([8, 20, 20, 20], ['M', 'Open Addressing',
                      'Separate Chaining', 'Sorted Chains'], output=output, decimals=decimals)
  
      for size in [214129, 524287, 999983]:
          timing_oa = min(timeit.repeat(stmt='''
  ht = OpenHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), setup='''
  from algs14_hashtable.hashtable_open import OpenHashtable
  from resources.english import english_words
  words = english_words()''', repeat=7, number=5))/5
  
          timing_sc = min(timeit.repeat(stmt='''
  ht = LinkedHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), setup='''
  from algs14_hashtable.hashtable_linked import LinkedHashtable
  from resources.english import english_words
  words = english_words()''', repeat=7, number=5))/5
  
          timing_sorted = min(timeit.repeat(stmt='''
  ht = SortedLinkedListsHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), setup='''
  from algs14_hashtable.hashtable_linked_sorted import SortedLinkedListsHashtable
  from resources.english import english_words
  words = english_words()''', repeat=7, number=5))/5
          tbl.row([size, timing_oa, timing_sc, timing_sorted])
  
      print('Search First Half')
      tbl = DataTable([8, 20, 20, 20], ['M', 'Open Addressing',
                      'Separate Chaining', 'Sorted Chains'], output=output, decimals=decimals)
  
      for size in [214129, 524287, 999983]:
          search_oa = min(timeit.repeat(stmt='''
  for w in words[:160564]:
      ht.get(w)''', setup='''
  from algs14_hashtable.hashtable_open import OpenHashtable
  from resources.english import english_words
  words = english_words()
  ht = OpenHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), repeat=7, number=5))/5
  
          search_sc = min(timeit.repeat(stmt='''
  for w in words[:160564]:
      ht.get(w)''', setup='''
  from algs14_hashtable.hashtable_linked import LinkedHashtable
  from resources.english import english_words
  words = english_words()
  ht = LinkedHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), repeat=7, number=5))/5
  
          search_sorted = min(timeit.repeat(stmt='''
  for w in words[:160564]:
      ht.get(w)''', setup='''
  from algs14_hashtable.hashtable_linked_sorted import SortedLinkedListsHashtable
  from resources.english import english_words
  words = english_words()
  ht = SortedLinkedListsHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), repeat=7, number=5))/5
          tbl.row([size, search_oa, search_sc, search_sorted])
  
      print('Search Back Half')
      tbl = DataTable([8, 20, 20, 20], ['M', 'Open Addressing',
                      'Separate Chaining', 'Sorted Chains'], output=output, decimals=decimals)
  
      for size in [214129, 524287, 999983]:
          search_oa = min(timeit.repeat(stmt='''
  for w in words[160564:]:
      ht.get(w)''', setup='''
  from algs14_hashtable.hashtable_open import OpenHashtable
  from resources.english import english_words
  words = english_words()
  ht = OpenHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), repeat=7, number=5))/5
  
          search_sc = min(timeit.repeat(stmt='''
  for w in words[160564:]:
      ht.get(w)''', setup='''
  from algs14_hashtable.hashtable_linked import LinkedHashtable
  from resources.english import english_words
  words = english_words()
  ht = LinkedHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), repeat=7, number=5))/5
  
          search_sorted = min(timeit.repeat(stmt='''
  for w in words[160564:]:
      ht.get(w)''', setup='''
  from algs14_hashtable.hashtable_linked_sorted import SortedLinkedListsHashtable
  from resources.english import english_words
  words = english_words()
  ht = SortedLinkedListsHashtable({})
  for w in words[:160564]:
      ht.put(w,w)'''.format(size), repeat=7, number=5))/5
          tbl.row([size, search_oa, search_sc, search_sorted])
  