xanalogica.tumbler 0.2dev

=====================
General Information
=====================

.. include:: <isonum.txt>

.. sidebar:: A Brief Historical Note
:subtitle: Is this software part of Project Xanadu\ |trade|?

`Project Xanadu`_\ |trade| is a trademark and project of `Ted Nelson`_.
This software is an independent derivation from the C source of the Xanadu\
|trade| 88.1 version (renamed to `Udanax Green`_) of that project,
simplified by taking advantage of the power of Python in representing
tuples and infinite-precision integers. Tumblers are a generally useful
tool.

.. _`Project Xanadu`: http://www.xanadu.com/
.. _`Ted Nelson`: http://en.wikipedia.org/wiki/Ted_Nelson
.. _`Udanax Green`: http://www.udanax.com/green/index.html

.. contents::


Setting Up for Development
**************************

::

$ svn co https://www.taupro.com/pubsvn/Projects/Xanalogica/xanalogica.tumbler/trunk xanalogica.tumbler
$ cd xanalogica.tumbler
$ python2.5 bootstrap.py
$ bin/buildout
$ bin/test

Abstract
********

The xanalogica.tumbler package implements a basic one-dimensional coordinate
type for xanalogical storage systems. It is useful as keys in mappings and
B-trees, including xanalogical enfilades. It is written purely in Python but
there are old versions written in C that may be resurrected as 'cTumbler' if
more performance is needed.

.. epigraph::

Our Kingdom is already twice the size of Spain, and every day we drift
makes it bigger.

-- The Kaiser in Werner Herzog's film, "Aguirre, The Wrath of God"

Theory of Operation
*******************

Conceptual Overview
===================

A tumbler is an element of a coordinate system laid out along a number line,
acting as forking multipart integers representing an unbounded, countable but
finite address space. You've seen them in the numbering of an outline, as
versioning notation or the Dewey Decimal System. Mathematically they are
related to a field of study called "transfinite arithmetic".

Tumbler addressing is about storage management; the spontaneous creation of
places at which to put things, and to symbolically reference those locations
as individual points or ranges of points.

Some are the advantages of tumblers are:

1. There is always a tumbler between two different tumblers, so insertions
never require renumbering.

2. A set of tumblers can be ordered.

3. The tumblers can be arranged to form a hierarchy, making it easy to
specify all tumblers that start with a shorter tumbler. This is used in
the Xanadu green system for queries like "all documents of this
user". This is also useful for delegating assignment authority, in the
manner of the Domain Name System (DNS) of the Internet.

4. Arithmetic can be done with tumblers. Specifically addition and
subtraction, making it possible to compute ranges with tumblers.

.. sidebar:: Whence Humbers?
:subtitle: Leveraging Python in Providing Humungous Numbers

In Ted Nelson's book, **Literary Machines**, mention is made of Humbers,
which stand for *humungous numbers*. In the book they are used to
efficiently represent integers of unbounded magnitudes, as digits within a
tumbler. The Python language comes with a similar datatype called 'longs',
which can represent such large integers. And in Python 2.1 and later, the
language automatically converts traditional 'ints' to 'longs', as needed.

Your Basic Tumbler
==================

Tumblers are implemented as a subclass of tuple, with certain arithmetic
properties of integers. Being derived from tuples, tumblers are immutable.

Representation
--------------

In Project Xanadu\|trade| tumblers are represented as a series of (unsigned)
integers, separated by decimal points. Since this syntax is not possible in
the native Python syntax, a choice of two forms is provided, either a
dotted-digits string, or a comma-delimited tuple.

>>> from xanalogica.tumbler import Tumbler

>>> Tumbler('1')
Tumbler(1)

>>> Tumbler('1.2')
Tumbler(1,2)

>>> Tumbler('1.2.3')
Tumbler(1,2,3)

>>> Tumbler("1.1.0.3.1.0.3")
Tumbler(1,1,0,3,1,0,3)

>>> Tumbler(1,1,0,3,1,0,3)
Tumbler(1,1,0,3,1,0,3)

>>> str(Tumbler(1,1,0,3,1,0,3))
'1.1.0.3.1.0.3'

>>> str(Tumbler('1'))
'1'

>>> str(Tumbler('1.2'))
'1.2'

>>> str(Tumbler('1.2.3'))
'1.2.3'

>>> Tumbler([1,2,3]) # accept a list
Tumbler(1,2,3)

>>> Tumbler((1,2,3)) # accept a distinct tuple
Tumbler(1,2,3)

>>> Tumbler(1,'a',2,3) # 0,'a',2 -> throw a TypeError exception
Traceback (most recent call last):
...
TypeError: 'a' in (1, 'a', 2, 3) is not an integer

The Tumbler class behaves like other primitive types in Python, in that
constructing one without a value results in a zero.

>>> int()
0

>>> float()
0.0

>>> Tumbler()
Tumbler(0)

Kinds of Tumblers
-----------------

A tumbler can be of either of two kinds: an address along the number line or a
difference between two such addresses. Certain mathematical operations do not
make sense between the different kinds.

Comparison of two tumblers for which is further to the right only makes sense
for address tumblers and not for difference tumblers. Similarly, comparing
two difference tumblers for



"""Compare two tumblers.

Note that you only compare address tumblers with other address
tumblers, and difference tumblers with difference tumblers.
Comparing an address and a difference tumbler makes no mathematical
sense.

A difference tumbler always begins with one or more leading zeros,
except where it designates the entire docuverse, in which case it
is 1.

Every address tumbler
starts with a digit of 1, to permit referring to the entire docuverse.


Comparison and Boolean Behavior
-------------------------------

Being conceptually laid out along a number line, tumblers can be compared to
each other.

>>> Tumbler(1,2) < Tumbler(4,5,6)
True

>>> Tumbler(1,2,3) < Tumbler(4,5,6)
True

>>> Tumbler(4,5,6) > Tumbler(1,2,3)
True

>>> Tumbler(4,5,6) < Tumbler(1,2,3)
False

>>> Tumbler(1,2,3) == Tumbler(1,2,3)
True

>>> Tumbler(1,2,3) != Tumbler(1,2,4)
True

And they interact with Python's boolean mechanism as expected:

>>> bool(Tumbler(1)) # a non-zero tumbler is true
True

>>> bool(Tumbler(0)) # a zero tumbler is false
False

Sequence Behavior
-----------------

subscripting them returns a digit, slices return a tuple of their digits

Tumbler Length
--------------

>>> len(Tumbler(1,2,3))
3

>>> len(Tumbler(1))
1

>>> len(Tumbler(0))
1


Tumbler Subscripting
--------------------

>>> Tumbler(1,2,3)[0]
1

>>> Tumbler(1,2,3)[1]
2

>>> Tumbler(1,2,3)[2]
3

>>> Tumbler(1,2,3)[-1]
3

>>> Tumbler(1,2,3)[-2]
2

>>> Tumbler(1,2,3)[-3]
1

>>> Tumbler(1,2,3)[1:]
(2, 3)







Arithmetic Behavior
-------------------

they follow the numeric protocol of Python, for addition and subtraction
to be coordinates rather than labels, operations can be performed on them











Tweak Digits
------------

>>> Tumbler(1,2,3).tweakdigit(-1, 1)
Tumbler(1,3,3)

>>> Tumbler(1,2,3).tweakdigit(-2, 1)
Tumbler(2,2,3)

>>> Tumbler(1,2,3).tweakdigit(-3, 1)
Tumbler(1,2,4,1,2,3)

>>> Tumbler(1,2,3).tweakdigit(0, 1)
Tumbler(1,2,4)

>>> Tumbler(1,2,3).tweakdigit(1, 1)
Tumbler(1,2,3,1)

>>> Tumbler(1,2,3).tweakdigit(2, 1)
Tumbler(1,2,3,0,1)

>>> Tumbler(0).tweakdigit(0, 1)
Tumbler(1)

>>> Tumbler(0).tweakdigit(0, 2)
Tumbler(2)

>>> Tumbler(0).tweakdigit(1, 1)
Tumbler(0,1)


Length Adjusts
--------------

>>> Tumbler(1,2,3).setlength(5)
Tumbler(1,2,3,0,0)

>>> Tumbler(1,2,3).setlength(4)
Tumbler(1,2,3,0)

>>> Tumbler(1,2,3).setlength(3)
Tumbler(1,2,3)

>>> Tumbler(1,2,3).setlength(2)
Tumbler(1,2)

>>> Tumbler(1,2,3).setlength(1)
Tumbler(1)

>>> isinstance(Tumbler(1,2,3).setlength(1), Tumbler)
True



Address Tumblers
================

tumblers can be divided into two kinds; those that specify a position along
the number line, called an Address Tumbler, and those representing the result
of subtracting two such positions, called Difference Tumblers.

I defined a couple of subclasses to constrain the arithmetic operations to
those that have meaning.

Default Value
-------------

>>> from xanalogica.tumbler import AddrTumbler, DiffTumbler
>>> str(AddrTumbler())
'0'

Parsing and Formatting
----------------------

>>> repr(AddrTumbler('1'))
'AddrTumbler(1)'

>>> repr(AddrTumbler('1.2'))
'AddrTumbler(1,2)'

>>> repr(AddrTumbler('1.2.3'))
'AddrTumbler(1,2,3)'

>>> str(AddrTumbler('1'))
'1'

>>> str(AddrTumbler('1.2'))
'1.2'

>>> str(AddrTumbler('1.2.3'))
'1.2.3'

Length Adjust
-------------

>>> isinstance(AddrTumbler(1,2,3).setlength(1), AddrTumbler)
True

Addition
--------

>>> AddrTumbler(1,2,3) + DiffTumbler(0)
AddrTumbler(1,2,3)

>>> AddrTumbler(1,2,3) + DiffTumbler(0,1)
AddrTumbler(1,3)

>>> AddrTumbler(1,2,3) + DiffTumbler(0,1,2)
AddrTumbler(1,3,2)

>>> AddrTumbler(1,2,3) + DiffTumbler(0,1,2,3)
AddrTumbler(1,3,2,3)

>>> AddrTumbler(1,2,3) + DiffTumbler(0,1,2,3,4)
AddrTumbler(1,3,2,3,4)

>>> isinstance(AddrTumbler(1,2,3) + DiffTumbler(0,1,2,3,4), AddrTumbler)
True

>>> try:
... AddrTumbler(1,2,3) + Tumbler(4)
... except TypeError, exc:
... print exc
Tumbler(4) is not a DiffTumbler

..

## def test():
## return AddrTumbler(1,2,3) + AddrTumbler(4)
## self.failUnlessRaises(TypeError, test)

>>> AddrTumbler(1,2,3) + DiffTumbler(0,0,0)
AddrTumbler(1,2,3)

>>> AddrTumbler(1,2,3) + DiffTumbler(0,0,1)
AddrTumbler(1,2,4)

Subtraction
-----------

..

self.failUnless(AddrTumbler(1,2,3) - AddrTumbler(1,1) == DiffTumbler(0,1,3))
self.failUnless(AddrTumbler(1,2,3) - AddrTumbler(1,1,1) == DiffTumbler(0,1,3))
self.failUnless(AddrTumbler(1,2,3) - AddrTumbler(1,1,1,1) == DiffTumbler(0,1,3))

self.failUnless(AddrTumbler(1,2,3) - AddrTumbler(0,0,0) == DiffTumbler(1,2,3))
self.failUnless(AddrTumbler(1,2,3) - AddrTumbler(0,0,1) == DiffTumbler(1,2,3))
self.failUnless(isinstance(AddrTumbler(1,2,3) - AddrTumbler(0,0,1), DiffTumbler))

## def test():
## AddrTumbler(1,2,3) - DiffTumbler(1,1)
## self.failUnlessRaises(TypeError, test)

IntDiff
-------

..

self.failUnless(AddrTumbler(1,2,3).intdiff(AddrTumbler(1,2,3)) == 0)
self.failUnless(AddrTumbler(1,2,3).intdiff(AddrTumbler(1,2,4)) == 1)
self.failUnless(AddrTumbler(1,2,3,4).intdiff(AddrTumbler(1,2,4)) == 1)

Classification
--------------

..

self.failUnless(AddrTumbler(1,2,3).isaNodeAddress())
self.failUnless(not AddrTumbler(1,2,3,0,4,5,6).isaNodeAddress())

self.failUnless(AddrTumbler(1,2,3,0,4,5,6).isaAccountAddress())
self.failUnless(not AddrTumbler(1,2,3).isaAccountAddress())
self.failUnless(not AddrTumbler(1,2,3,0,4,5,6,0,7,8,9).isaAccountAddress())

self.failUnless(not AddrTumbler(1,2,3,0,4,5,6).isaDocumentAddress())
self.failUnless(not AddrTumbler(1,2,3).isaDocumentAddress())
self.failUnless(AddrTumbler(1,2,3,0,4,5,6,0,7,8,9).isaDocumentAddress())

self.failUnless(not AddrTumbler(1,2,3,0,4,5,6).isaAtomAddress())
self.failUnless(not AddrTumbler(1,2,3).isaAtomAddress())
self.failUnless(not AddrTumbler(1,2,3,0,4,5,6,0,7,8,9).isaAtomAddress())
self.failUnless(AddrTumbler(1,2,3,0,4,5,6,0,7,8,9,0,1,35).isaAtomAddress())

Relational Comparison
---------------------

..

## def test():
## AddrTumbler(1,2) < DiffTumbler(0,1) # Non-Comparable Types
## self.failUnlessRaises(TypeError, test)

Difference Tumblers
===================

Default Value
-------------

..

self.failUnless(str(DiffTumbler()) == '0')

Parsing and Formatting
----------------------

..

self.failUnless(repr(DiffTumbler('1')) == 'DiffTumbler(1)')
self.failUnless(repr(DiffTumbler('1.2')) == 'DiffTumbler(1,2)')
self.failUnless(repr(DiffTumbler('1.2.3')) == 'DiffTumbler(1,2,3)')
self.failUnless(str(DiffTumbler('1')) == '1')
self.failUnless(str(DiffTumbler('1.2')) == '1.2')
self.failUnless(str(DiffTumbler('1.2.3')) == '1.2.3')

Addition
--------

..

## def test():
## DiffTumbler(1,2,3) + DiffTumbler(1,1)
## self.failUnlessRaises(TypeError, test)

## def test():
## DiffTumbler(1,2,3) + AddrTumbler(1,1)
## self.failUnlessRaises(TypeError, test)

## def test():
## DiffTumbler(1,2,3) + Tumbler(1,1)
## self.failUnlessRaises(TypeError, test)

Subtraction
-----------

..

## def test():
## DiffTumbler(1,2,3) - DiffTumbler(1,1)
## self.failUnlessRaises(TypeError, test)

## def test():
## DiffTumbler(1,2,3) - AddrTumbler(1,1)
## self.failUnlessRaises(TypeError, test)

## def test():
## DiffTumbler(1,2,3) - Tumbler(1,1)
## self.failUnlessRaises(TypeError, test)

Relational Comparison
---------------------

..

## def test():
## AddrTumbler(1,2) < DiffTumbler(0,1) # Non-Comparable Types
## self.failUnlessRaises(TypeError, test)


Span Arithmetic
---------------

..

# def test_001_span_parsing_and_formatting(self):
# pass
# self.failUnless(repr(Span(AddrTumbler(1,2,3), DiffTumbler(1))) == 'Span((1,2,3), (1)')
# self.failUnless(repr(DiffTumbler('1.2')) == 'DiffTumbler(1,2)')
# self.failUnless(repr(DiffTumbler('1.2.3')) == 'DiffTumbler(1,2,3)')
# self.failUnless(str(DiffTumbler('1')) == '1')
# self.failUnless(str(DiffTumbler('1.2')) == '1.2')
# self.failUnless(str(DiffTumbler('1.2.3')) == '1.2.3')

# def test_002_span_inrange(self):
# self.failUnless(AddrTumbler(1,2,2) not in Span(AddrTumbler(1,2,3), DiffTumbler(0,0,5)))
# self.failUnless(AddrTumbler(1,2,3) in Span(AddrTumbler(1,2,3), DiffTumbler(0,0,5)))
# self.failUnless(AddrTumbler(1,2,4) in Span(AddrTumbler(1,2,3), DiffTumbler(0,0,5)))
# self.failUnless(AddrTumbler(1,2,5) not in Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)))
# self.failUnless(AddrTumbler(1,2,6) not in Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)))

# def test_003_span_relational_compare_LT(self):
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) < AddrTumbler(1,1,1))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) < AddrTumbler(1,2,2))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) < AddrTumbler(1,2,3))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) < AddrTumbler(1,2,4))
# self.failUnless( Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) < AddrTumbler(1,2,5))
# self.failUnless( Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) < AddrTumbler(1,2,6))
# self.failUnless( Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) < AddrTumbler(1,2,7))

# def test_004_span_relational_compare_GT(self):
# self.failUnless( Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) > AddrTumbler(1,1,1))
# self.failUnless( Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) > AddrTumbler(1,2,2))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) > AddrTumbler(1,2,3))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) > AddrTumbler(1,2,4))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) > AddrTumbler(1,2,5))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) > AddrTumbler(1,2,6))
# self.failUnless(not Span(AddrTumbler(1,2,3), DiffTumbler(0,0,2)) > AddrTumbler(1,2,7))

Basic Theory
============

About tumblers...

Arithmetic Operations
=====================

>>> print 5
5
>>> 5 == 4
False

entire docuverse placed between 1 and 2

all differences placed between 0 and 1

zero digits separate URI fields

four URI fields: server/user/document/version
allows for delegation of numbering to independent entities
allows to range specifiers to encompass sections of the number line

The tumbler has two primary functions: to represent addresses in the docuverse
and to represent *spans* of addresses. A span is represented by a pair of
tumblers, either a pair of address tumblers or an address and difference
tumbler.

To-Do List
**********

* support comparison of tumbler to span
* support comparison of span to tumbler
* provide a tumbler-to-int converter that raises an exception if not possible __int__
* how to reconcile addition with concatenation
* study os.path and create equivalents for tumblers
* AddrTumbler attributes: .node .account .document .atom .atomtype .atomsuffix
* consider: summation of spans creates a spec/vspec/sporgl/???

Changes
*******

0.1 (2008-09-14)
================

Features Added
--------------

Initial check-in for new Python egg/buildout distribution methology.

Download
********
All packaged distributions can be found on the package `home page`_ in
the Python Package Index. Scroll to the very bottom of the page to find
the links. In addition to these PyPI downloads, the development
versions are available from the Tau Productions Inc. `public Subversion
repository`_.

.. _`home page`: http://pypi.python.org/pypi/xanalogica.tumbler
.. _`public Subversion repository`: https://www.taupro.com/pubsvn/Projects/Xanalogica/xanalogica.tumbler/trunk/#egg=xanalogica.tumbler-dev