Perforce scripts

This is useful Perforce old my scripts-helpers.

Common utils:

# Returns number of changelists, prints list of changelists
find_p4cl() {
    p4 changes -u $USER -s pending|awk '
        BEGIN { found=0 }
        /^Change / {
            p4cl[found, 0] = $2
            p4cl[found, 1] = $4
            w = match($0, /\*pending\* /)
            if (w) d = substr($0, w + length("*pending* "))
            else d = ""
            p4cl[found, 2] = d
            found++
        }
        END {
            if (found) {
                print "Available ChangeLists:"
                print "======================"
                for (i=0; i<found; i++) {
                    printf "  %s on %s: %s...\n",
                        p4cl[i, 0],
                        p4cl[i, 1],
                        p4cl[i, 2]
                }
            }
            exit found
        }
    '
}

# Input from user changelist (show default value if it one only).
# If no input, returns default
read_p4cl() {
    local changelists _p4cl p4clhint
    changelists=`find_p4cl`
    if [ $? -eq 1 ]; then
        _p4cl=`echo "$changelists"|awk 'NR==3{print $1}'`
        p4clhint=" [${_p4cl}]"
    else
        _p4cl=""
        p4clhint=""
    fi
    echo "$changelists"
    echo
    echo -n "Enter P4 ChangeList number${p4clhint}: "; read p4cl; : ${p4cl:=$_p4cl}
}

# if not Perforce workspace then report it
check_p4ws() {
    CF=${P4CONFIG:-.p4config}
    [ -f "$CF" ] || { echo 'Seems not P4 workspace!' >&2; return 1; }
    return 0
}

List of midified files without switch it to "Edit" mode (devs often forget to do it :)

#!/bin/sh
# List of locally modified files without put them into ChangeList

. .p4utils
check_p4ws || exit 1
p4 reconcile -e -n

Review sedning:

#!/bin/sh
# Send ChangeList review request

. .p4utils
check_p4ws || exit 1
read_p4cl
echo "Posting review now. Wait, please..."
post-review $p4cl

Simplest config file parser in the world!

Nothing then split/strip/filter "combinators":

cfg = '''
    a   = aa aaa = aaaa
b   = bbb
        c=cccccccccc


'''
split_pair = lambda s: s.split('=', 1)
strip_pair = lambda p: map(str.strip, p)
parse_rc = lambda s: map(strip_pair, map(split_pair, filter(None, s.splitlines())))
print dict(parse_rc(cfg))  # print lik in Python 2x

Logging library for Unix Shell

This library is similar to Log library for Python or Java. Here its code:

#!/bin/sh

# Simple logging facility for Unix /bin/sh
# ========================================
#
# Configuration
# -------------
#
#   _LOGGING_DATEFMT, _LOGGING_FMT variables are used for format of datetime
#   and log record
#
#   * _LOGGING_DATEFMT : uses the same format as date(1) and Python Lib
#
#   * _LOGGING_FMT : uses format similar to Python logging Lib
#
#       Available fields for _LOGGING_FMT are:
#         asctime, filename, levelname, levelno, message, name, pathname,
#         process, processName, user
#
# Example
# -------
#
#     getLogger prg1
#     getLogger prg2
#     
#     addLogHandler prg1 FileHandler /dev/stderr
#     addLogHandler prg2 ConsoleHandler
#     addLogHandler prg2 FileHandler /var/log/somefile
#     addLogHandler prg2 FileHandler /var/log/somefile_copy
#
#     setLogLevel prg1 DEBUG
#
#     prg1_debug DebugMessage
#     prg1_error ErrorMessage
#     echo InfoMessage|prg2_info
#
#   will produces on STDERR console:
#     ...
#     2014-07-18T17:09:52+0300 prg1 DEBUG DebugMessage
#     ...
#
#   will produces on console:
#     ...
#     2014-07-18T17:09:52+0300 prg1 ERROR ErrorMessage
#     2014-07-18T17:09:52+0300 prg2 INFO InfoMessage
#     ...
#
#   and in /var/log/somefile:
#     ...
#     2014-07-18T17:09:52+0300 prg2 INFO InfoMessage
#     ...
#
#   and in /var/log/somefile_copy:
#     ...
#     2014-07-18T17:09:52+0300 prg2 INFO InfoMessage
#     ...

# TODO: log levels per handlers


############################## Settings #####################################

# Global log record format and date format:
_LOGGING_DATEFMT="%Y-%m-%dT%H:%M:%S%z"
_LOGGING_FMT="%asctime %name %levelname %message"



################################### Code #####################################

_log_SCRIPT=`readlink -f $0`

_log_getLogAttr() {
  name=$1; attr=${1}_$2
  eval echo $`echo $attr`
}

################################### Handlers #################################

# SYNOPSIS: ...
#
# Nothing to do, all args are ignored
_log_NullHandler() {
  :
}

# SYNOPSIS: $name $level $msg
#
# Logs $msg with $level via logger(1) utility
_log_SyslogHandler() {
  local name level msg syslog_level
  name="$1"; level="$2"; msg="$3"
  syslog_level=`_log_syslogLevel $level`
  logger -p "local0.${syslog_level}" -t $name "$msg"
}

# SYNOPSIS: $name $level $msg
#
# Logs message $msg on console
_log_ConsoleHandler() {
  local name level msg
  name="$1"; level="$2"; msg="$3"
  echo "$msg"
}

# SYNOPSIS: $subject $address $msg
#
# If mail(1) exists, call it to send $msg via EMail
_log_MailHandler() {
  command -v mail >/dev/null 2>&1 || return 1
  local subj addr name level msg
  subj="$1"; addr="$2"; name="$3"; level="$4"; msg="$5"
  echo "$msg"|mail -s "${subj}${level}: $name" $addr
}

# SYNOPSIS: $filename $msg
#
# Append message $msg to file $filename
_log_FileHandler() {
  local filename name level msg
  filename="$1"; name="$2"; level="$3"; msg="$4"
  touch "$filename"
  echo "$msg" >> "$filename"
}

_log_syslogLevel() {
  case $1 in
    CRITICAL)
      echo crit;;
    FATAL)
      echo panic;;
    ERROR)
      echo error;;
    WARNING)
      echo warning;;
    INFO)
      echo info;;
    DEBUG)
      echo debug;;
    *)
      echo notice;;
  esac
}

_log_levelNo() {
  case $1 in
    CRITICAL|FATAL)
      echo 50;;
    ERROR)
      echo 40;;
    WARNING)
      echo 30;;
    INFO)
      echo 20;;
    DEBUG)
      echo 10;;
    *)
      echo 0;;
  esac
}

_log() {
  local name level msg handlers h closure_args skip no_closure_args levelno enabled_levelno
  name="$1"; level="$2"; msg="$3"

  levelno=`_log_levelNo $level`
  enabled_levelno=`_log_getLogAttr $name level`
  [ $levelno -lt $enabled_levelno ] && return

  handlers=`_log_getLogAttr $name handlers`
  handlers=`echo "$handlers"|sed 's/__COMMA__/\\ /g'`
  for h in $handlers; do
    echo $skip|grep $h >/dev/null && continue
    closure_args=`_log_getLogAttr $name ${h}_handler_args`
    closure_args=`echo "$closure_args"|sed 's/__COMMA__/\\ /g'`
    no_closure_args=1
    for ca in $closure_args; do
      eval "$h $ca $name $level \"$msg\""
      no_closure_args=0
    done
    [ $no_closure_args ] && eval "$h $name $level \"$msg\""
    skip="$h $skip"
  done
}

# SYNOPSIS: $name $h [$args...]
#
# Adds handler $h for logger $name with possible arguments
# (see handlers' implementations for concrete args)
addLogHandler() {
  local name handler oldhandlers exthandler args oldargs
  name=$1; exthandler="$2"; handler=_log_"$exthandler"; shift 2; args="$*"
  oldhandlers=`_log_getLogAttr $name handlers`
  oldargs=`_log_getLogAttr $name ${handler}_handler_args`
  # __COMMA__ is used to separate items in lists
  eval "${name}_handlers=${handler}__COMMA__${oldhandlers:-_log_NullHandler}"
  eval "${name}_${handler}_handler_args=\"$args\"__COMMA__$oldargs"
}

# SYNOPSIS: $name | $name $longname
#
# No return and no output but setups logger for this $name. In 2nd form $longname
# is used in message substitution
getLogger() {
  local asctime filename levelname levelno message name pathname process processName _lv user longname

  asctime=$_LOGGING_DATEFMT
  filename=`getScriptName`
  message='${1:-`tee`}'
  name="$1"
  longname=${2:-$name}
  pathname=`echo "$_log_SCRIPT"|sed 's/\\//\\\\\//g'`
  process='$$'
  processName=`ps -A -opid,comm | awk -v PID=$$ '$1 == PID { print $2 }'`
  processName=`echo "$processName"|sed 's/\\//\\\\\//g'`
  user="$USER"

  for _lv in debug info warning error fatal critical; do
    levelname=`echo -n $_lv|tr '[:lower:]' '[:upper:]'`
    levelno=`_log_levelNo $levelname`

    fmt=`echo $_LOGGING_FMT | \
      sed 's/%asctime/\`date +$_LOGGING_DATEFMT\`/g' | \
      sed "s/%filename/$filename/g" | \
      sed "s/%levelname/$levelname/g" | \
      sed "s/%levelno/$levelno/g" | \
      sed "s/%message/$message/g" | \
      sed "s/%pathname/$pathname/g" | \
      sed "s/%processName/$processName/g" | \
      sed "s/%process/$process/g" | \
      sed "s/%user/$user/g" | \
      sed "s/%name/$longname/g"`
    eval "${name}_${_lv} () { _log $name $levelname \"$fmt\"; }"
  done
  setLogLevel $name INFO
}

# SYNOPSIS: $name $level
#
# Sets the threshold for $name logger to $level (INFO, ERROR, etc.). Logging
# messages which are less severe than $level will be ignored.
# Default is INFO
setLogLevel() {
  local name level levelno
  name="$1"; level=`echo -n $2|tr '[:lower:]' '[:upper:]'`
  levelno=`_log_levelNo $level`
  eval "${name}_level=$levelno"
}

# SYNOPSIS:
#
# Echos name of script
getScriptName() {
  echo `basename "$_log_SCRIPT"`
}

Example of usage:

#!/bin/sh
. ./logging.sh

getLogger prg1 `getScriptName`
addLogHandler prg1 ConsoleHandler
addLogHandler prg1 FileHandler ./lll1.log
addLogHandler prg1 FileHandler ./lll2.log
setLogLevel prg1 DEBUG

prg1_debug Debugggg
prg1_error Errrrror
echo 'Message-INFO!!!!
1111
2222'|prg1_info

HFit - fitting algorithms in Haskell

It's very interesting class of tasks - fitting of some figure using several input points with noise. The simplest method is Least Squares Algorithm. Idea of algorithm is to find a and b of line equation a*x + b using sum's minimization of difference's squares: ∑(y_i - (a*x_i + b))². Result is 2 formulas:

$$ a=\frac{n \sum\limits_{i=1}^n x_i y_i - \sum\limits_{i=1}^n x_i \sum\limits_{i=1}^n y_i} {n \sum\limits_{i=1}^n x_i^2 - ({\sum\limits_{i=1}^n x_i})^2} $$

$$ b=\frac{\sum\limits_{i=1}^n y_i - a \sum\limits_{i=1}^n x_i} {n}$$

And when we know a and b we can generates (x0, y0) (x1, y1) points to create line...

Application initializes Tcl/Tk UI via sending Tcl code to wish interpreter:

...
  mainTcl <- readFile "ui.tcl"
  (Just si, Just so, Just sx, ph) <- createProcess (proc wish []) {
    std_in=CreatePipe, std_out=CreatePipe, std_err=CreatePipe, close_fds=False}
  hSetBuffering si NoBuffering
  hSetBuffering so NoBuffering
  hPutStrLn si mainTcl
...

Communication loop lives in separate process:

...
  forkIO $ ioLoop si so
  waitForProcess ph
  putStrLn "bye."
  where
    ioLoop si so = forever $ do
        resp <- (hGetLine so) `catchIOError` (\_ -> return "eof")
        case resp of
          "eof" -> exitSuccess
          _|resp `startsWith` "calc " ->
            putStrLn ("-> " ++ resp) >> 
            let res = calc resp in
            putStrLn ("<- " ++ res) >> hPutStrLn si res
          _ -> putStrLn resp >> return ()
...

and when new line is got from wish then it will be processed with calc function which gets request (here it's call resp from Wish, yep:) and parse coordinates like "1 2 3 4", ie. x0 y0 x1 y1 ... xn yn with parsePt (after splitting them into words):

...
-- Parse ["12", "34", "56", "78"] to [(12, 34), (56, 78)]
parsePt :: [String] -> [Pt]
parsePt [] = []
parsePt (k:v:t) = (read k, read v) : parsePt t
...

then done all calculation in Double domain. Result of calculation is Tcl command like "takeCalc x0 y0 x1 y1" with coordinates of found line 2 points:

    -> calc 119 285 194 235 379 64
    <- takeCalc 119  306  379  46

Wish will get this command and create line on canvas.

Actually it's initial state, so needs many improvement, adding new algorithms, etc...

algutils.h macros

Some useful macros for algorithms C/C++ (used early in related posts):

#ifndef _ALGUTILS_H_
#define _ALGUTILS_H_

/// Array numbers
#ifndef sizeofarray
#define sizeofarray(ARR) (sizeof(ARR) / sizeof(ARR[0]))
#endif

/// Division with ceil rounding
#define CEILDIV(X,Y) (((X)%(Y))? (1 + ((X)/(Y))) : ((X)/(Y)))

/// min, max, abs
#define MIN(X, Y) ((X)<(Y)?(X):(Y))
#define MAX(X, Y) ((X)>(Y)?(X):(Y))
#define ABS(X) ((X)<0?(-(X)):(X))

/// Swaps two variables via temporary var @a tmp
#define SWAP(x, y, tmp) do { \
    tmp = x; x = y; y = tmp; \
} while (0)

/// Print array @a ARR with length @a LEN by item format @a ELFMT
#define PRINTARRX(ARR, LEN, ELFMT) do { \
    printf("{ "); \
    for (unsigned int i=0; i<(LEN); i++) { \
        printf(ELFMT " ", (ARR)[i]); \
    } \
    printf("}\n"); \
} while (0)

/// Print array @a ARR by item format @a ELFMT
#define PRINTARR(ARR, ELFMT) PRINTARRX(ARR, sizeofarray(ARR), ELFMT)

/// Shift array @a ARR of length @a LEN by @a N positions to right
#define RSHIFT_ARR(ARR, LEN, N) do { \
    register int _rshift_arr_i_; \
    for (_rshift_arr_i_=(N)+(LEN)-1; \
         _rshift_arr_i_>(N)-1; \
         _rshift_arr_i_--) \
    { \
        *((ARR)+_rshift_arr_i_) = *((ARR)+(_rshift_arr_i_-(N))); \
    } \
} while (0)

#endif /* EOF */

General algorithm for allocation of series

Here is the generic algorithm of determining of the series from sequence by some feature SeriesFeature. Examples show usage of splitting series in camelCase strings (in the same case).

from abc import ABCMeta, abstractmethod
from itertools import groupby, imap

# a,b,c -> ((None, a), (a, b), (b, c)) (ie (prev, cur) pairs)
#preiter = lambda it: izip(chain([None], it), it)

class SeriesFeature(object):
    __metaclass__ = ABCMeta
    id = None # series id
    i = 0 # element index
    def __init__(self, serid):
        self.i = -1
        self.id = serid
    @abstractmethod
    def __series__(self, el, serid):
        """Check element `el` and return new/old series id. `serid`
        is current series id`
        """
    def __call__(self, el):
        self.i += 1
        self.id = self.__series__(el, self.id)
        return self.id

class CapitalizedSeries(SeriesFeature):
    def __init__(self):
        super(CapitalizedSeries, self).__init__(0)
    def __series__(self, el, serid):
        if self.i == 0 and el.isupper():
            return serid
        elif el.islower():
            return serid
        else:
            return (serid + 1)%2

CamelCaseSeries = CapitalizedSeries

def iseries(flt, it):
    series = (el[1] for el in groupby(it, flt()))
    if isinstance(it, str):
        return imap(''.join, series)
    else:
        return series

def camelcaseto(s, func):
    """Transform each CamelCase-string part with `func(ser)`"""
    return imap(func, iseries(CamelCaseSeries, s))

########################## test ##############################################
print list(iseries(CapitalizedSeries, 'AaaaBbbCcAaa'))
print list(iseries(CapitalizedSeries, 'abcDefGhi'))

print ' '.join(camelcaseto("noSuchUserError", str.lower)).capitalize()

Normal Markov Algorithm

Normal Markov algorithm - is the abstract rewriting system or method of algorithms description/writing. Here is simple Python implementation. Idea of this A. is in the foundation of Refal.

from __future__ import print_function

class Rule:
    def __init__(self, f, t, last=0):
        self.f = f  # from
        self.t = t  # to
        self.len = len(self.f)
        self.last = last  # last rule?

    def __str__(self):
        return "<Rule%s %s -> %s>" % ('.' if self.last else '', self.f, self.t)

    def sub(self, text):
        """ Substitution:
        >>> Rule('a', 'b').sub('qweaaannn')
        (1, 'qwebaannn')
        >>> Rule('a', 'b').sub('aaa')
        (1, 'baa')
        >>> Rule('a', '').sub('qweaba')
        (1, 'qweba')
        >>> Rule('', 'xyz').sub('qweaba')
        (1, 'xyzqweaba')
        >>> Rule('', '').sub('qweaba')
        (0, 'qweaba')
        """
        if not self.f and not self.t: return (0, text)
        for i in range(0, len(text)):
            end = i + self.len
            if self.f == text[i:end]:
                return (1, text[0:i] + self.t + text[end:])
        return (0, text)



class NM:
    """ Normal Markov's Algorithm
    >>> nm = NM([Rule("ba", "ab"),])
    >>> nm('aababbbabababbaaa')
    'aaaaaaaaabbbbbbbb'
    >>> nm = NM([Rule("c", ""), Rule("bb", "ddd", last=1)])
    >>> nm('abbcabbca')
    'adddabba'
    >>> nm('dcacb')
    'dab'
    >>> nm = NM([Rule("*a", "", last=1),
    ...          Rule("*b", "", last=1),
    ...          Rule("*", "", last=1),
    ...          Rule("", "*"),
    ... ])
    >>> nm('bbaba')
    'baba'
    >>> nm = NM([Rule("*0", "00*"),
    ...          Rule("*1", "01*"),
    ...          Rule("*2", "10*"),
    ...          Rule("*3", "11*"),
    ...          Rule("*", "", last=1),
    ...          Rule("", "*"),
    ... ])
    >>> nm('0123')
    '00011011'
    >>> nm = NM([Rule("*a", "a*"),
    ...          Rule("*b", "b*"),
    ...          Rule("*", "a", last=1),
    ...          Rule("", "*"),
    ... ])
    >>> nm('bbab')
    'bbaba'
    """
    def __init__(self, rules):
        self.rules = rules

    def eval(self, text):
        while 1:
            changed = 0
            for rule in self.rules:
                oldtext = text
                applied, text = rule.sub(text)
                #print("%s -> %s [by %s]" % (oldtext, text, rule))
                if applied:
                    changed = 1
                    if rule.last: return text
                    else: break
            if not changed:
                return text
    __call__ = eval

import doctest
doctest.testmod()

Select sorting in C

We are searching for the least item and insert it into head of array. But on its place - head, i.e. swaps head and this item. Then we are shift head by 1 and make the same. Very simple algorithm :)

#include <stdio.h>
#include "algutils.h"

template<typename T>
int selsort(T* arr, unsigned int len)
{
    T elmin;
    int i, off, imin;
    if (!arr||!len) return (0);

    for (off=0; off<len; off++) {
        for (i=off, elmin=arr[off], imin=-1; i<len; i++) {
            if (elmin > arr[i]) {
                elmin = arr[i];
                imin = i;
            }
        }
        if (imin != -1) {
            arr[imin] = arr[off];
            arr[off] = elmin;
        }
    }
    return (1);
}

/*****************************************
                    Main
 *****************************************/
int main(void)
{
    int arr[] = {2, 1, 0, 10, 9, 99, 8, -1, 6, 15, 15};
    PRINTARR(arr, "%d");
    selsort(arr, sizeofarray(arr));
    PRINTARR(arr, "%d");
    return (0);
}

Regexps and Finite State Machines (FSM)

Actually regular expressions can be represented as FSM in easy way. Here is simple implementation of regexp ".*(.*007.*).*". Idea is simple: we are matching more concrete case, if no success - more wide (less concrete), any symbol. If no success again then return to previous state. reduce() processes all FSM, result of reducing is checking - this must be final FSM state, in example it must be 5 which means that we processing to the end and pattern is matched.

from functools import reduce

def fsm(s0, c):
    _ = None        # any symbol
    rules = (
        ( 0, '(', 1 ),
        ( 0,  _,  0 ),
        ( 1, '0', 2 ),
        ( 1,  _,  1 ),
        ( 2, '0', 3 ),
        ( 2,  _,  1 ),
        ( 3, '7', 4 ),
        ( 3, '0', 3 ),
        ( 3,  _,  1 ),
        ( 4, ')', 5 ),
        ( 4,  _,  4 ),
        ( 5,  _,  5 ),
    )
    for _s0, _c, _s1 in rules:
        if s0 == _s0 and (_c is _ or c == _c):
            return _s1
    raise Exception("Unexpected symbol '%s'" % c)

def match007(s):
    return 5 == reduce(fsm, s, 0)

Quick sorting in C

This is the implementation of quick sort algorithm in C.

#include <stdio.h>
#include "algutils.h"

template<class T>
void qsort(T* a, long len)
{
    printf("call\n");
    long l = 0, r = len, mid = len/2;
    T temp, p;

    p = a[mid]; // central item

    /* Swap: items less than p will go to left, above - to right,
       l going from the left, r - from the right, before the item,
       which denies this rule. After finding of such items we will
       swap them
    do {
        // looking for item from the left which > p
        while (a[l] < p) l++;
        // looking for item from the right < p
        while (a[r] > p) r--;

        // swap them if no wrapping
        if (l <= r) {
            SWAP(a[l], a[r], temp);
            l++; r--; // go to next - without it - hang up!
        }
    } while (l<=r); // XXX may be better is l<r ?


    /* Recursive calls if there is what to sort.
    Both cases works, upper makes about 2 times lesser calls!
    Split by the point where on left side are all < p, on right:
    all > p. If to choice another point of splitting, result
    of pre-sorting will be lost - ordering on one of the sides
    will be denied
    */
    if (r > 0) qsort(a, r);
    if (len > l) qsort(a+l, len-l);

    /*if (len>1) {
        qsort(a, mid);
        qsort(a + mid, len - mid);
    }*/
}


/*****************************************
                   main
 ****************************************/
int main(void)
{
    int arr[] = {10, 9, 4, 5, 11, 45, 6, 7, 88, 1, 0, 1};
    PRINTARR(arr, "%d");
    qsort(arr, sizeofarray(arr));
    PRINTARR(arr, "%d");
    return (0);
}

Postfix marshaling format

Implementation of simple marshaling of nested data structures. Supports: int, float, string, nested lists. Serialized data is presented as string. It's not difficult to serialize into binary...

# POSTPACK -- packing the data in postfix notation (nested typed items)
#
# Format: item '!' type,
#   where type may be 'i' (int), 'f' (float), 's' (string), 'l' (list),
#   num 'l' (list with num items)
#
# Example: 1!i2!i!l3!i4!i!2l => [[1, 2], [3, 4]]
#
# To escape '!' '!' is used: 'Hello!!' => 'Hello!'

from __future__ import print_function
import string

DIGITS = string.digits


class Postpack:
    def __init__(self, fmt={}):
        self.fmt = {int: "%d", float: "%f", str: "%s"}
        self.fmt.update(fmt)

    def decode(self, input):
        ''' Decodes input string into internal representation (list of items,
        possible nested):

        >>> Postpack().decode("Hello, world!!!!!s2.1!f!2l3!i4!i!2l5!i!2l")
        [['Hello, world!!', 2.1], [[3, 4], 5]]
        '''
        buf = ""        # item chars buffer
        instr = ""      # instruction chars buffer
        items = []      # items
        st = "data"     # FSM state
        for ch in input:
            if st == "instr":
                if ch in DIGITS:
                    instr += ch
                elif ch == '!':
                    buf += ch
                    st = "data"
                else:
                    if ch == 'i':
                        items.append(int(buf))
                    elif ch == 'f':
                        items.append(float(buf))
                    elif ch == 's':
                        items.append(str(buf))
                    elif ch == 'l':
                        nitems = len(items)
                        count = int(instr) if instr else nitems
                        first = nitems - count
                        if first < 0:
                            raise ValueError("Wrong count: %d" % count)
                        items[first:] = [items[first:]]
                    else:
                        raise ValueError("Wrong instruction: %s" % ch)
                    st = "data"
                    buf = ""
            elif st == "data":
                if ch == "!":
                    instr = ""
                    st = "instr"
                else:
                    buf += ch
        return items


    @staticmethod
    def escape(s):
        '''
        >>> Postpack().escape('Qwe!rty!!')
        'Qwe!!rty!!!!'
        '''
        return s.replace('!', '!!')

    def encode(self, items):
        ''' Encodes list of items (may be nested):

        >>> Postpack(fmt={float: '%.1f'}).encode([['Hello, world!!', 2.1], [[3, 4], 5]])
        'Hello, world!!!!!s2.1!f!2l3!i4!i!2l5!i!2l'
        '''
        output = ""
        for it in items:
            ittype = type(it)
            if ittype is int:
                output += self.fmt[int] % it + "!i"
            elif ittype is float:
                output += self.fmt[float] % it + "!f"
            elif ittype is str:
                output += self.fmt[str] % self.escape(it) + "!s"
            elif ittype is list:
                output += self.encode(it) + "!%dl" % len(it)
            else:
                raise ValueError("Wrong type: %s" % ittype)
        return output




##############################################################################
if __name__ == "__main__":
    import doctest
    doctest.testmod()

Merge sorting in Python

Early subject was implemented in C/C++, but actually I do prototyping usually in Python, so this was first :)

def MergerSort(a):
    def MergerGroup(a, left, m, right):
        if left >= right: return None
        if m < left or right < m: return None
        print "left:", left, "m:", m, "right:", right
        t = left
        for j in xrange(m+1, right+1):
            for i in xrange(t, j):
                if a[j] < a[i]:
                    r = a[j]
                    for k in xrange(j, i, -1):
                        a[k] = a[k - 1]
                    a[i] = r
                    t = i
                    break
    if len(a) < 2: return None
    k=1
    while k<len(a):
       g=0
       while g<len(a):
            z = g + k + k - 1
            r = z if z < len(a) else len(a) - 1
            print "k =", k, "g =", g, "z =", z, "r =", r, " | "\
                    "left:", g, "m:", g+k-1, "right:", r
            MergerGroup(a, g, g + k - 1, r)
            g+=2*k
       k*=2

def mergsort(arr):
    arrlen = len(a)
    k = 2
    while k < 2*arrlen:
        left = 0
        while left < arrlen:
            right = min(left + k - 1, arrlen-1)
            print left, right, "|", k
            left += k
        k *= 2

a = [10, 19, 1, 2, 10, 450, 6, 7, 8, 100, 120, 121]
print a, len(a)
MergerSort(a)
print a

Insert sorting

We take 2nd item and compare it with the next. If it less than next, then insert it in appropriate position. Then we are taking 3d item and it's comparing with previous two items and is inserting into appropriate position. Then we are taking 4th item and etc. By the way, the inserting actually is shifting all items by one position to right and then is inserting into free position.

#include <stdio.h>
#include "algutils.h"

template<typename T>
void inssort_insert(T *arr, T item, unsigned int pielen, unsigned int pos)
{
    for (int i=pielen-1; i>pos; i--)
        arr[i] = arr[i-1];
    arr[pos] = item;
}

template<typename T>
int inssort(T *arr, unsigned int len)
{
    if (!arr||!len) return (0);
    for (int pie=1; pie<len; pie++) {
        for (int i=0; i<=pie-1; i++) {
            if (arr[pie] < arr[i]) {
                inssort_insert(arr, arr[pie], pie+1, i);
                break;
            }
        }
    }
    return (1);
}

/*****************************************
                   main
 ****************************************/
int main(void)
{
    int arr[] = {10, 9, 4, 5, 11, 45, 6, 7, 88, 1, 0, 1};
    PRINTARR(arr, "%d");
    inssort(arr, sizeofarray(arr));
    PRINTARR(arr, "%d");
    return (0);
}

Imperative Eratosthenes sieve

Algorithm is very-very simple and is learning at the school :)

def erato(m):
    # list of all numbers to m: 1 - free cell, 0 - aliquot to prime
    lst = [1 for i in range(m)]
    n = 2 # starts from 2
    while n < m: # take next prime
        for i in range(n, m): # looking for free cell
            if lst[i]: break # 1 - free, i.e. not aliquot to others
        if i == m-1: return # no more free, stop
        n = i # keep found free
        yield n # and it's prime!
        j = 2 # multiplier: 2, 3, 4, 5...
        while i < m: # checks aliquot to found prime n
            lst[i] = 0
            i = n*j # checks 2n, 3n, 4n, 5n, 6n, ...
            j += 1 # multipliers: 2, 3, 4, 5...

print list(erato(300))

Generic lists processing

lst_tmpl() is the generic function of processing lists, all other functions may be implemented in easy way with using of it. Actually it's ported from Haskell:

from operator import add, mul, concat

def lst_tmpl(f1, f2, f3, f4, f5, l):
    "Generic recursive processing of list (head, tail, empty list, etc)"
    if not l: return f1([])
    else:
        x = l[0]
        xs = l[1:]
        return f2(f3(x), f4(lst_tmpl(f1, f2, f3, f4, f5, f5(xs))))

lst_const = lambda n: lambda _: n
lst_id = lambda x: x
lst_swap = lambda op: lambda x, y: op(y, x)
lst_list = lambda x: [x]
lst_cons = lambda x, xs: [x] + xs

lst_len = lambda l: lst_tmpl(lst_const(0), add, lst_const(1), lst_id, lst_id, l)

lst_sum = lambda l: lst_tmpl(lst_const(0), add, lst_id, lst_id, lst_id, l)
lst_mul = lambda l: lst_tmpl(lst_const(1), mul, lst_id, lst_id, lst_id, l)
lst_rev = lambda l: lst_tmpl(lst_id, lst_swap(concat), lst_list, lst_id, lst_id, l)
lst_map = lambda f, l: lst_tmpl(lst_id, lst_cons, f, lst_id, lst_id, l)


###### test ############
print lst_len([1, 2, 3, 4, 5])
print lst_sum([1, 2, 3, 4, 5])
print lst_mul([1, 2, 3, 4, 5])
print lst_rev([1, 2, 3, 4, 5])
print lst_map(lambda x: x*100, [1, 2, 3, 4, 5])

Functional Eratosthenes sieve

Three implementations of subject on Python/Haskell/Ocaml

Python version:

# coding: cp1251

# Idea: 2 is simple, so check in the list 2..m all 2, 4, 6... - 2*j,
# j=2,3,4,5,6,7... Then we are searching next unchecked, check all.
# Each first unchecked is the prime number.

#####################################################
# С tail recursion ;)
#####################################################

def tag2(lst, n, m, j=2, i=1):
    ''' Returns list with 0s - i.e. checked numbers in `lst` which
    are multiple of n (m - max number, j - multiplier 2, 3, 4...,
    i - serial number of our number :)
    '''
    if not lst: return []
    elif i != n*j: return lst[0:1] + tag2(lst[1:], n, m, j, i+1)
    else: return [0] + tag2(lst[1:], n, m, j+1, i+1)

def tag(lst, n): return tag2(lst, n, len(lst))

def erato2(lst, m, i):
    if i >= m:
        return []
    elif lst[i]:
        if i >= 1: lst = tag(lst, lst[i])
        return [lst[i]] + erato2(lst, m, i+1)
    else:
        return erato2(lst, m, i+1)

def erato(lst): return erato2(lst, len(lst), 0)
lst = range(1, 200)
print erato(lst)

Haskell:

tag::[Int] -> Int -> [Int]
tag lst n = [if 0 == x `rem` n then 0 else x | x <- lst]

erato2::[Int] -> Int -> Int -> [Int]
erato2 lst m i =
  if i >= m then []
  else if (lst!!i) /= 0 then
      [lst!!i] ++ erato2 (if i>=1 then tag lst (lst!!i) else lst) m (i+1)
  else
      erato2 lst m (i+1)

-- Returns all primes from 1 to m
erato::Int -> [Int]
erato m = erato2 lst (length lst) 0 where lst = [1..m]

main::IO()
main = putStrLn $ show $ erato 200

and Ocaml version:

open List

let tag lst n = map (fun x -> if 0 == x mod n then 0 else x) lst

let rec erato2 lst m i =
    if i >= m then []
    else if (nth lst i) <> 0 then
        [nth lst i] @ erato2 (if i >= 1 then tag lst (nth lst i) else lst) m (i+1)
    else
        erato2 lst m (i+1)

let prn_int n = print_int n; print_char ','
let print_int_list lst = map prn_int lst
let rec range i j = if i > j then [] else i :: (range (i+1) j)

(* Returns all primes from 1 to m *)
let erato m = let lst = range 1 m in erato2 lst (length lst) 0
let _ = print_int_list (erato 200)

Bubble sort

Bubble search (with exchanging items). We compares neighboring items: if they needs exchanging - they have wrong order - do it. Then we do the same for next neighboring items, i.e. 0-1, 1-2, 2-3, ... After first pass over array the last item will be the biggest (like bubble fly to up :). So, in next pass over items we will process all without the last item. Then again, new last (pre-last actually) item will be biggest in current pass, so in next pass we must skip it, etc... Processing will stop when we are skipping all items OR when no more items swaps.

#include <stdio.h>
#include "algutils.h"

template<typename T>
int bubsort(T *arr, unsigned int len)
{
    if (!arr||!len) return (0);
    T tmp;
    int pie = len, nswaps;
    do {
        nswaps = 0;
        for (int i=0; i<pie; i++) {
            if (arr[i] > arr[i+1]) {
                SWAP(arr[i], arr[i+1], tmp);
                nswaps++;
            }
        }
        pie--;
    } while (pie && nswaps);
    return (1);
}

/*****************************************
                   main
 ****************************************/
int main(void)
{
    int arr[] = {10, 9, 4, 5, 11, 45, 6, 7, 88, 1, 0, 1};
    PRINTARR(arr, "%d");
    bubsort(arr, sizeofarray(arr));
    PRINTARR(arr, "%d");
    return (0);
}

Binary search

Input is - ordered array. Comparison is with middle item, if matched it then we found target, if middle is greater then we must check in the same way all items from the left side of the middle item, otherwise - on right side.

#include <stdio.h>
#include "algutils.h"

template<typename T>
int binsearch(T *arr, int len, const T& target)
{
    int mid, off = 0;
    while (1) {
        if (!len) return (-1);
        mid = len/2;
        if (arr[mid] == target) return (off + mid);
        len = mid;
        if (arr[mid] < target) {
            off += mid + 1;
            arr = &arr[mid+1];
        }
    }
}

/***********************************************************************
                                  Main
 ***********************************************************************/

int main(void)
{
#define LIST(...) {__VA_ARGS__}
#define TEST(EL, RESULT, L) do { \
    int arr[] = L; \
    int s = binsearch(arr, sizeofarray(arr), (EL)); \
    printf("Binary search of %d: %d (%s)\n", (EL), s, \
            s==(RESULT)?"true":"FALSE"); \
} while (0)

    TEST(1, 0, LIST(1,2,3,4,5,6,8,9,10,14,15,24,55));
    TEST(2, 1, LIST(1,2,3,4,5,6,8,9,10,14,15,24,55));
    TEST(14, 9, LIST(1,2,3,4,5,6,8,9,10,14,15,24,55));
    TEST(15, 10, LIST(1,2,3,4,5,6,8,9,10,14,15,24,55));
    TEST(24, 11, LIST(1,2,3,4,5,6,8,9,10,14,15,24,55));
    TEST(55, 12, LIST(1,2,3,4,5,6,8,9,10,14,15,24,55));
    TEST(240, -1, LIST(1,2,3,4,5,6,8,9,10,14,15,24,55));

    return (0);
}

Simple backtracking implementation

Classical task: you have numbers 1,5,6,7 and operations (),+,-,*,/,^. You have to build arithmetical expression which result will be 21 (without repeats!). For searching is solutions tree we'll use backtracking, for arithmetics - stack machine, like Forth. Search extracts element of each level with extract_e() from rest of variants cases, all other ones will be searching recursively. Function goal() is the predicate, which determines do we need to add found path into solutions list found. It has empiric: must be more than 1 numbers on the stack!

from functools import *

# split seq by element index, returns element and all other elements
extract_e = lambda seq, i: (seq[i], seq[:i] + seq[i+1:])
# all indexes of sequence
indexes = lambda seq: range(len(seq))

# backtracking
def bt(cases, goal, found=[], level=0, path=[]):
    if goal(path, level): found.append(path)
    for i in indexes(cases):
        c, rest = extract_e(cases, i)
        bt(rest, goal, found, level+1, path + [c])
    if 0 == level: return found

# Solver - uses postfix arithm.
class Solver:
    VALUES, OPERATORS = (1,5,6,7), ('+', '-', '*', '/', '^')

    @staticmethod
    def _binop(stack, op_ch):
        ops = { "+": lambda a, b: b+a, "-": lambda a, b: b-a,
                "*": lambda a, b: b*a, "/": lambda a, b: b/a,
                "^": lambda a, b: b**a, }
        stack.append(ops[op_ch](stack.pop(), stack.pop()))

    def eval(self, state, default=None):
        try:
            stack = []
            for c in state:
                if c in self.VALUES: stack.append(int(c))
                else: self._binop(stack, c)
            return stack.pop()
        except:
            return default

    def __call__(self):
        def goal(path, level):
            if len(path) > 2 and all(e in self.VALUES for e in path[:2]):
                try: return 21 == int(self.eval(path))
                except: return
        return bt(self.VALUES + self.OPERATORS, goal)

print("Found:", Solver()())

The same BT-search may be used for sorting:

# predicate: is seq ordered?
ordered = lambda seq: reduce(lambda i,e: (i[0] and e>=i[1], e), seq, (1, seq[0]))[0]
seq = [9,1,5,4]
print("In:", seq)
def completed(path, level): return level==len(seq) \
    and ordered(path)
print(bt(seq, completed))

SIOD Scheme shell for image processing algorithms

To play with such algorithms, with them parameters, I wrote SIOD (Scheme) based shell with exposed C implementations to it, so they can be parametrized on Scheme. This post is report of all results :) All base algorithm blocks are written in C (see this) and are called from SIOD scripts (test*.scm) which produce some output images in out/* directory. C code is very simple and does not target perfomance goals.

Algorithm 1: Grey scale, negative

This very simple test demonstrates grey scale and negative of input images. Grey scaling calculate length of RGB vector then constructs vector with the same length but R, G, B components have the same length each. Negative uses fact that max R, G, or B value is 255 and calculates difference between color component and 255.

see: test01.scm

(define b (img_open "in/ngirl.jpg"))
(img_gr b)
(img_neg b)
(img_save b "out/gr.jpg")

Input images:


Output images:

Algorithm 2: Emboss

It's classical image processing method: applying of 2D filter on each pixel. More about convolution matrix read: this. Main idea is the same as in other filters: each original samples gives some value to common result but all of thees values has different amount which depend of filter formula. There are 2 main notes on this filter. First: no recursion, so original pixels (samples) - are real original and temporary clean copy of original image should be allocated and used for calculation. Second: normalization of result is need. Result is divided by special value (div) and shifted by another (shift or bias). And if now it's lesser then 0, 0 should be used instead of, if bigger then 255, 255 should be placed as result. This test uses convolution matrix to implement emboss filter. Other tests use c.m. for other goals.

see: test02.scm

(load "imsh.scm")
(define b (img_open "in/ngirl.jpg"))
(img_conv b emboss-matrix emboss-div emboss-shift)
(img_save b "out/emboss.jpg")

Input images:


Output images:

Algorithm 3: Color mask

This is also simple algorithm which applies color mask on image: with 3 bits user select one of 3 channels (R, G, B) to show, other will be hidden. This looks like broken TV when picture is blown in some color (green often). For example, bits "3" means "011", i.e. R channel will be hidden, G, B - shown.

see: test03.scm

(define b (img_open "in/ngirl.jpg"))
(img_ch b 3)
(img_save b "out/ch.jpg")

Input images:


Output images:

Algorithm 4: Edge detection

This test uses convolution matrix to implement edge detection of image. There are different algorithms for edge detection also, not only based on c.m.

see: test04.scm

(load "imsh.scm")
(define b (img_open "in/ngirl.jpg"))
(img_conv b edge-matrix 3 60)
(img_save b "out/edge.jpg")

Input images:


Output images:

Algorithm 5: Grey levels

This test implements converting to grey levels with custom number of levels. Resulting image looks like picture from Windows 3.1 - colors are approximated with grey levels only. When there are only 2 levels, all looks like black-and-white image, more levels show more realistic graduations of colors.

see: test05.scm

(load "imsh.scm")
(define b (img_open "in/ngirl.jpg"))
(img_grl b 6)
(img_save b "out/grl.jpg")

Input images:


Output images:

Algorithm 6: B/w conversion + edge detection

This test runs edge detection with c.m. too, but image is converted to black-and-white first.

see: test06.scm

(load "imsh.scm")
(define b (img_open "in/ngirl.jpg"))
(img_bw b 50)
(img_conv b edge-matrix 3 40)
(img_save b "out/bwedge.jpg")

Input images:


Output images:

Algorithm 7: B/w conversion + dilation

This test converts input image to black-and-white then applies dilation matrix (which is c.m. too).

see: test07.scm

(load "imsh.scm")
(define b (img_open "in/ngirl.jpg"))
(img_bw b 60)
(img_conv b dilat-matrix dilat-div dilat-shift)
(img_conv b dilat-matrix dilat-div dilat-shift)
(img_save b "out/dilat2.jpg")

Input images:


Output images:

Algorithm 8: Pixalization

This test runs pixalization. Main idea is to cut original image on squares with some side and to replace pixels of this squared area with one-color square. Which color to use? If black and white version is applied then result color is calculated like in Black-and-White filter with threshold = 50%. If color version of pixalization is applied, then average color of squared area is used.

see: test08.scm

(load "imsh.scm")
(define b (img_open "in/ngirl.jpg"))
(img_pix b 10 1)
(img_save b "out/pix1.jpg")

(define b (img_open "in/ngirl.jpg"))
(img_pix b 5 0)
(img_save b "out/pix2.jpg")

Input images:


Output images:

Algorithm 9: Median filter

This filter is based on c.m. filter also but instead of calculate central point in filter window (in aperture) with special formula, it's sort all points and use central point of sorted points and central point of window. So, if there is big impulse in window's central point then it will be replaced by "median" point. It's good to filter "salt and piper" noise.

see: test09.scm

(load "imsh.scm")
(define b (img_open "in/ngirl.jpg"))
(img_med b 9)
(img_save b "out/med.jpg")

Input images:


Output images:

Algorithm 10: Dilation + erosion

This test makes dilation and erosion. Dilation is - application of structural element (like kernel in c.m.) on binary image to get more "fat" image. See more here. Erosion is - application of structural element (like kernel in c.m.) on binary image to get more "thick" image. See more here.

see: test10.scm

(define b1 (img_open "in/foo.jpg"))
(img_bw b1 50)

(define matrix1 '(1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1 1 1))

(define matrix2 '(1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1
                  1 1 1 1 1 1 1 1 1))

(img_bindilate b1 matrix1)
(img_save b1 "out/bindilate.jpg")

(define b2 (img_open "in/boo.jpg"))
(img_bw b1 50)
(img_binerode b2 matrix2)
(img_save b2 "out/binerode.jpg")

Input images:



Output images:

Algorithm 11: More complex dilation + erosion

This test runs dilation and erosion too, but on more complex input image.

see: test11.scm

(define b (img_open "in/thing.jpg"))
(img_bw b 50)

(define matrix '(1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1))

(img_binerode b matrix)
(img_bindilate b matrix)
(img_save b "out/open.jpg")

(define b (img_open "in/thing.jpg"))
(img_bw b 50)

(define matrix '(1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1
                 1 1 1 1 1 1 1 1 1 1 1))

(img_bindilate b matrix)
(img_binerode b matrix)
(img_save b "out/close.jpg")

Input images:


Output images:

Algorithm 12: Edge detection on bold font

This test runs edge-detection algorithm with c.m. on bold weight font. Result looks interesting and with coloring can get base for neon effect (need also shadowing)

see: test12.scm

(load "imsh.scm")
(define b (img_open "in/boo.jpg"))
(img_conv b edge-matrix 3 60)
(img_bw b 50)
(img_save b "out/booedge.jpg")

Input images:


Output images:

Algorithm 13: Set operations

This test shows set operations but on image: OR, XOR, AND, NOT, SUB (complement).

see: test13.scm

(define b1 (img_open "in/a.jpg"))
(define b2 (img_open "in/b.jpg"))
(img_bw b1 50)
(img_bw b2 50)
(img_binand b1 b2)
(img_save b1 "out/and.jpg")

(define b1 (img_open "in/a.jpg"))
(define b2 (img_open "in/b.jpg"))
(img_bw b1 50)
(img_bw b2 50)
(img_binor b1 b2)
(img_save b1 "out/or.jpg")

(define b1 (img_open "in/a.jpg"))
(define b2 (img_open "in/b.jpg"))
(img_bw b1 50)
(img_bw b2 50)
(img_binxor b1 b2)
(img_save b1 "out/xor.jpg")

(define b1 (img_open "in/a.jpg"))
(define b2 (img_open "in/b.jpg"))
(img_bw b1 50)
(img_bw b2 50)
(img_binsub b1 b2)
(img_save b1 "out/sub.jpg")

(define b (img_open "in/a.jpg"))
(img_bw b 50)
(img_binnot b)
(img_save b "out/not.jpg")

Input images:



Output images:

Algorithm 14: Morphological edge detection

Edges can be detected also with morphological operations. Edge := IMG0 `sub` ERODE(IMG0). SUB - is substraction/complements.

see: test14.scm

(define b1 (img_open "in/boo.jpg"))
(define b2 (img_open "in/boo.jpg"))
(img_bw b1 50)
(img_bw b2 50)

(define matrix '(0 1 0 1 1 1 0 1 0))

(img_binerode b2 matrix)
(img_binsub b1 b2)
(img_save b1 "out/morphedge.jpg")

Input images:


Output images:

Algorithm 15: Dithering

Dithering is the algorithm for preparing of image to black-white printing (old newspapers, old books) or for old displays systems. Here is 2 different implementations: * general purpose with using of matrixes defined in imsh.scm library * special dithering algorithms.

see: test15.scm

(load "imsh.scm")

(define i (img_open "in/stalin.jpg"))
(img_gendith i sierra-dith-matrix)
(img_save i "out/dithgen_sierra.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i sierra2-dith-matrix)
(img_save i "out/dithgen_sierra2.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i sierralow-dith-matrix)
(img_save i "out/dithgen_sierralow.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i floyd-dith-matrix)
(img_save i "out/dithgen_floyd.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i falsefloyd-dith-matrix)
(img_save i "out/dithgen_falsefloyd.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i jarvis-dith-matrix)
(img_save i "out/dithgen_jarvis.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i stucki-dith-matrix)
(img_save i "out/dithgen_stucki.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i atkinson-dith-matrix)
(img_save i "out/dithgen_atkinson.jpg")

(define i (img_open "in/stalin.jpg"))
(img_gendith i burkes-dith-matrix)
(img_save i "out/dithgen_burkes.jpg")

(define i (img_open "in/stalin.jpg"))
(img_dith i 0)
(img_save i "out/dith_atkinson.jpg")

(define i (img_open "in/stalin.jpg"))
(img_dith i 1)
(img_save i "out/dith_floyd.jpg")

(define i (img_open "in/stalin.jpg"))
(img_dith i 2)
(img_save i "out/dith_ordered.jpg")

(define i (img_open "in/stalin.jpg"))
(img_dith i 3)
(img_save i "out/dith_random.jpg")

Input images:


Output images: