A Python Implementation Of the Fixed-Size Queue

"""
A homogeneous fixed-size queue.
"""


from array import array

class FixedsizeQueue(object):
"""
A fixed size queue is a homogeneous FIFO queue that can't grow.
"""

def __init__(self, max_size, typecode='i'):
self.size = 0
self.head = 0
self.tail = 0
self.typecode = typecode
self.max = max_size
self._data = None
return

@property
def data(self):
"""
:return: an array of size self.max, type self.typecode
"""

if self._data is None:
self._data = array(self.typecode, [0 for i in range(self.max)])
return self._data

def enqueue(self, item):
"""
:param:

- `item`: the item to add to the queue

:return: True if added, False if full
"""

if self.size == self.max:
return False

self.data[self.tail] = item

self.size += 1
self.tail += 1

if self.tail == self.max:
self.tail = 0
return True

def dequeue(self):
"""
:return: oldest item or None
"""

if self.size == 0:
return
item = self.data[self.head]

self.size -= 1
self.head += 1

if self.head == self.max:
self.head = 0
return item

def reset(self):
"""
:postcondition: head, tail and size reset to 0
"""

self.size = 0
self.tail = 0
self.head = 0
return

def empty(self):
"""
:return: True if the queue is empty.
"""

return self.size == 0

def full(self):
"""
:return: True if the queue is full.
"""

return self.size == self.max
# end class FixedsizeQueue

The Fixed-Size Queue

This is an abstract data type given in Udacity's Software Testing course.

Description

A First-In-First-Out (FIFO) queue whose size is preset and not allowed to grow and which has a homogeneous type.

Reason

The fixed size and type allows for better performance, particularly when removing items from the start of the queue.

Fixed-Size Queue Class Diagram

Python Imp Experiments

The importing of classes using imp was tested with:


from unittest import TestCase

import os
import imp
import importer

class TestSource(TestCase):
def test_import(self):
"""
module `source` contains class `SourceCase` with attribute cow set to 'pie'
"""

path = os.path.dirname(__file__)
f, package, description = imp.find_module("source", [path])
source = imp.load_module('source', f, package, description)
SourceCase = getattr(source, "SourceCase")
case_o = SourceCase()
expected = importer.source.SourceCase()
self.assertEqual(expected.cow, case_o.cow)

# this won't work - using imp gets source.SourceCase, but import gets importer.source.SourceCase
#self.assertIsInstance(case_o, source.SourceCase)
return

def test_subdirectory_import(self):
"""
module `subsource` contains a class Subsource with attribute `apropos` set to 'nothing'
"""

top = os.path.dirname(__file__)
f, package_path, d = imp.find_module("subdir", [top])
f, mod_path, description = imp.find_module('subsource', [package_path])
subsource = imp.load_module('subdir.subsource', f, mod_path, description)
Subsource = getattr(subsource, "Subsource")
source_obj = Subsource()
expected = importer.subdir.subsource.Subsource()
self.assertEqual(expected.apropos, source_obj.apropos)
return
# end class TestSource

Python's imp.load_module

imp.load_module(name, file, pathname, description)

parameters

  • name: module name using dot-notation for sub-directories (e.g. directory.module)
  • file: Opened file (module)
  • pathname: The path to the file.
  • description: The tuple returned by imp.find_module

Examples

Same Directory

The equivalent of import module:


f, p, d = find_module('module')
module = load_module('module', f, p, d)
Sub-Directory

The equivalent of import package.module:


path_to_importer = os.path.dirname(__file__)
f, p, d = find_module('package', [path_to_importer])
f2, p2, d2 = find_module('module', [p])
o = load_module('package.module', f2, p2, d2)
Close the File

The importer won't close the file, even if there is an exception. To make sure it gets closed:


try:
return load_module('package.module', f2, p2, d2)
finally:
if f2:
f2.close()

What Is Software Testing?

What is Acceptability Testing?

An acceptability test is one where a set of inputs is run through the System Under Test (SUT) and checked to make sure the correct outputs are produced.

What is a Bug?

  • An execution error
  • Incorrect output

What are the possible sources of bugs?

  1. The SUT
  2. The Acceptability Test
  3. The Specification
  4. The System in which the software is run

How do you find the source of a bug?

Check the possible sources of bugs in order.
  • SUT: syntax, logic, etc.
  • Acceptability Test: same as SUT plus the input set
  • Specification: Understanding of what the SUT is supposed to do
  • System: Unfixable, look for workarounds and ways to report the problem

Python's imp.find_module

imp.find_module(name [, path])

Parameters

name
The name of the module (directory or file without extension).
Path
  • If ommitted checks builtins first, then the sys.path directories
  • If given:
    • must be a list of directory names
    • Searches directories for the module

Return

A 3-tuple of (file, pathname, description).
File
An opened file or None if the module is a package (directory);
Pathname
The path to the file or directory.
Description
A 3-tuple of (suffix, mode, type):
  • suffix is the file extension (e.g. .py)
  • mode is one of r or rb (file was opened as readable text or binary)
  • type is one of PY_SOURCE, PY_COMPILED, C_EXTENSION, or PKG_DIRECTORY

Raise

ImportError if the module isn't found.

Subdirectories

The method doesn't accept dotted notation to indicate that the module is in a sub-package. Instead you have to find the package first then the module:
path = os.path.dirname(__file__)
f, p, d = find_module('directory', [path])
f_2, p_2, d_2 = find_module('module_name', [p]))

The State Pattern [HFDP]

What is the State Pattern?

  • It allows an object to alter its behavior when the internal state changes
  • The object will appear to change its class

How Does It Work?

  • A State interface is created that has all the actions the main class needs.
  • A concrete class is created for each state the system can be in (implementing the State)
  • Each state knows when a state change happens and sets the container's state class to the new state (object)
  • The container always calls state.method()
  • The states have to have a reference to the container since they changed its State

State Vs Strategy

  • User of context in state isn't aware of state objects
  • User of Strategy specifies objects to change the algorithm
  • Strategy is a more flexible alternative to subclassing (changing the composition changes the behavior)
  • State is an alternative to using conditionals

Context Transitions Vs State Transitions

  • You can decouple the states from the Context by having the Context choose the next state
    • If Transitions are fixed, put in Context
    • If Transitions are dynamic, put in state (state knows the Transition to the next state)

Do States Maintain State?

  • No, they choose Transitions
  • This means contexts can share the same strategies

The Template Method Pattern [HFDP]

What is the Template Method Pattern?

  • Defines the skeleton of an algorithm in a method
  • Defers some steps to a subclass
  • Lets subclasses change some steps in the algorithm without changing the structure
  • The Template Method contains an ordered series of primitive operations -- by (re)defining the primitive operations, subclasses change the algorithm

What Are Hooks?

  • A Hook is a method defined in the base class with a default or empty operation
  • Because it's not abstract, subclasses can ignore it
  • Because it's there, subclasses can re-define it without changing the structure of the template
  • If the hook returns a boolean for a conditional, it allows subclasses to change the flow of the algorithm

Abstract Vs Hooks

  • Abstract Methods are requirements
  • Hooks are optional

What Is the 'Hollywood Principle'?

  • Don't call us, we'll call you.
  • High-level components call low-level ones, not the other way around

Strategy Vs Template

  • Strategy composes other objects chosen at runtime
  • Template uses sub-classes
  • Template provides better code re-use and strictly defines the algorithm
  • Strategy provides better decoupling but the algorithm is provided by the composed objects

Optimization

What is Optimization?

Optimization means to find the set of parameters that minimize the cost of a solution to a problem.

What is a Global Optimization?

A Global Optimization is the optimal solution out of all possible solutions. [PSOAI]

What is a Local Optimization?

A Local Optimization is a solution that may not be the global optimum but is good enough. [PSOAI]

What Are the Three Types of Optimization?

  • Exhaustive: Try all the combinations.
  • Stochastic: Try a random subset and pick the best.
  • Learning: Pick random solutions that improve as you go.

What Is the First Phase of Optimization?

The first phase is to create a mathematical model of the system.

How Do You Create a Model of the System?

  • Translate parameters for the solution to numbers.
  • Represent solutions as vectors of parameters.
  • Create a cost function that maps the global minimizing parameters to the optimal solution. [PSOAI]

What is a Solution In Optimization?

A set of parameters that solves the problem with the least cost while still meeting constraints. [IIS]

What is the Domain?

The set of valid parameters (those that solve the problem no matter the cost). [IIS]

What is the Feasible Domain?

The subset of valid parameters that meet the constraints of the problem. [IIS]

What is a Feasible Solution?

A solution that meets all the constraints. [PSOAI]

What is the Cost Function?

A function that maps solutions to their cost (maps the best solution to the best outcome and the worst solution to the worst outcome).

What is a Design Pattern?

What is a pattern?

Sources
  • a recurring design problem that occurs in a specific context whose solution can be re-used [POSAV1 p. 8]
  • a 3-part rule giving a relationship between a context, a problem, and a solution [RTP p. 23]
  • patterns are discovered general solutions to design problems that provide a language to share them between designers [HFDP p. 32]
  • a pattern is a solution to a problem in context [HFDP p. 579]
Restatement
A Design Pattern is a re-usable design solution for a given context and problem.

What are the parts of a pattern?

  • Context, Problem, Solution [POSAV1 p. 8]

What is a problem?

  • A problem is a set of competing forces that arise in a given context [POSAV1 p. 11]
  • The goal and constraints of the context [HFDP p. 579]

What are forces?

  • goals and constraints [HFDP p. 582]

What is a solution?

  • A general design that resolves the goal and constraints [HFDP p. 579]
  • A static structure of components as well as runtime behavior that balances the forces [POSAV1 p. 11]