telling knock-knock jokes to a data sequence graph

https://github.com/ArtV/DataSequenceGraph. This is an experimental release whose quality is not assured. Data sequence graph represents a set of data value sequences (IEnumerable<>), called "chunks", as nodes and directed edges in a single graph. More introductory details.

Here are some sample executions of the data sequence graph CLI program at a PowerShell prompt.

function prompt { ">>" }
>>echo "Knock knock. Who's there? Closure. Closure who? Closure mouth when you eat." > closure.txt
>>.\DataSequenceGraphCLI.exe --verbose --splittext closure.txt --outedges edges.dat --outvalues values.txt

These are the long-form parameters; one-character parameters are also available. The line splits the contents of closure.txt into sentence chunks with word values, sends the resulting graph in binary+text format into two output files, and because of "verbose" also echoes back the entire graph contents, first node by node then chunk (route) by chunk...

Added sentence starting with Knock at start node 0
Added sentence starting with Who's at start node 3
Added sentence starting with Closure at start node 6
Added sentence starting with Closure at start node 8
Added sentence starting with Closure at start node 10

0 Gate
   ..1 if already -1..-1
1 Value: Knock
   ..2 if already 0..1
2 Value: knock
   ..0 if already 0..1
3 Gate
   ..4 if already -1..-1
4 Value: Who's
   ..5 if already 3..4
5 Value: there
   ..3 if already 3..4
6 Gate
   ..7 if already -1..-1
7 Value: Closure
   ..6 if already 6..7
   ..9 if already 8..7
   ..11 if already 10..7
8 Gate
   ..7 if already -1..-1
9 Value: who
   ..8 if already 8..7
10 Gate
   ..7 if already -1..-1
11 Value: mouth
   ..12 if already 7..11
12 Value: when
   ..13 if already 11..12
13 Value: you
   ..14 if already 12..13
14 Value: eat
   ..10 if already 10..7

------ Chunks in graph:
#1:
0..1:Knock..2:knock
#2:
3..4:Who's..5:there
#3:
6..7:Closure
#4:
8..7:Closure..9:who
#5:
10..7:Closure..11:mouth..12:when..13:you..14:eat

Now a second knock-knock joke. The previously generated graph for closure.txt is loaded by specifying the input files and the "missing" option requests output of the difference rather than showing the end result after adding...

>>echo "Knock knock. Who's there? Hugh. Hugh who? You, that's who!" > hugh.txt
>>.\DataSequenceGraphCLI.exe --loadedges edges.dat --loadvalues values.txt --splittext hugh.txt --missing --outedges hughdelta.dat --outvalues hughdelta.txt
Added sentence starting with Knock at start node 15
Added sentence starting with Who's at start node 16
Added sentence starting with Hugh at start node 17
Added sentence starting with Hugh at start node 19
Added sentence starting with You at start node 20

15 Gate (new) no requisite to next required
1 Value "Knock" requisite is route edge #0
2 Value "knock" no implied edge to next node
16 Gate (new) no requisite to next required
4 Value "Who's" requisite is route edge #0
5 Value "there" no implied edge to next node
17 Gate (new) no requisite to next required
18 Value "Hugh" (new) no implied edge to next node
19 Gate (new) no requisite to next required
18 Value "Hugh" requisite is route edge #0
9 Value "who" no implied edge to next node
20 Gate (new) no requisite to next required
21 Value "You" (new) requisite is route edge #0
22 Value "that's" (new) requisite is route edge #1
9 Value "who" no implied edge to next node

hughdelta.txt contains the string "Hugh|You|that's" (15 characters or 15 UTF-8 bytes). That end list of nodes/requisite information is what goes into hughdelta.dat, in the binary form that I described here. hughdelta.dat is 36 bytes. Each line in the list is a node/requisite record. There are 5 new gate nodes, one for each sentence/chunk/route, which consume 5 * 2 = 10 bytes. There are 7 lines that use preexisting value nodes, which consume 7 * 2 = 14 bytes, for a running total of 24 bytes. Finally, there are 3 lines of new value nodes, which consume 3 * 4 = 12 bytes (2 bytes for the usual sequence number and guide bits and 2 bytes for the index for the new values), to reach the final total of 36. Notice that since all requisites fall into one of "no requisite or no implied edge", "starting requisite" (lines with route edge #0), "the previous edge is the requisite" (lines with the route edge #1), the reader of the file can reconstruct the requisites without the requisites consuming actual file space as stated data values. One last knock-knock joke, this time just adding the new joke to the first graph and showing the result...

>>echo "Knock knock. Who's there? Eliza. Eliza who? Eliza lot. Don't trust em." > eliza.txt
>>.\DataSequenceGraphCLI.exe --loadedges edges.dat --loadvalues values.txt --splittext eliza.txt
Added sentence starting with Knock at start node 15
Added sentence starting with Who's at start node 16
Added sentence starting with Eliza at start node 17
Added sentence starting with Eliza at start node 19
Added sentence starting with Eliza at start node 20
Added sentence starting with Don't at start node 22

0 Gate
..1 if already -1..-1
1 Value: Knock
..2 if already 0..1
..2 if already 15..1
2 Value: knock
..0 if already 0..1
..15 if already 15..1
3 Gate
..4 if already -1..-1
4 Value: Who's
..5 if already 3..4
..5 if already 16..4
5 Value: there
..3 if already 3..4
..16 if already 16..4
6 Gate
..7 if already -1..-1
7 Value: Closure
..6 if already 6..7
..9 if already 8..7
..11 if already 10..7
8 Gate
..7 if already -1..-1
9 Value: who
..8 if already 8..7
..19 if already 19..18
10 Gate
..7 if already -1..-1
11 Value: mouth
..12 if already 7..11
12 Value: when
..13 if already 11..12
13 Value: you
..14 if already 12..13
14 Value: eat
..10 if already 10..7
15 Gate
..1 if already -1..-1
16 Gate
..4 if already -1..-1
17 Gate
..18 if already -1..-1
18 Value: Eliza
..17 if already 17..18
..9 if already 19..18
..21 if already 20..18
19 Gate
..18 if already -1..-1
20 Gate
..18 if already -1..-1
21 Value: lot
..20 if already 20..18
22 Gate
..23 if already -1..-1
23 Value: Don't
..24 if already 22..23
24 Value: trust
..25 if already 23..24
25 Value: em
..22 if already 22..23

------ Chunks in graph:
#1:
0..1:Knock..2:knock
#2:
3..4:Who's..5:there
#3:
6..7:Closure
#4:
8..7:Closure..9:who
#5:
10..7:Closure..11:mouth..12:when..13:you..14:eat
#6:
15..1:Knock..2:knock
#7:
16..4:Who's..5:there
#8:
17..18:Eliza
#9:
19..18:Eliza..9:who
#10:
20..18:Eliza..21:lot
#11:
22..23:Don't..24:trust..25:em

binary format of data sequence graph

https://github.com/ArtV/DataSequenceGraph. This is an experimental release whose quality is not assured. Data sequence graph represents a set of data value sequences (IEnumerable<>), called "chunks", as nodes and directed edges in a single graph. More introductory details.

The binary format of a data sequence graph has steadily become more complicated and abbreviated. Some demystifying is warranted. These details are accurate presently but could be partially or even fully obsolete at any date in the near or far future, since the code has no guarantees of format stability or compatibility.

Its overall structure is a chunk's route, containing node/requisite records in visitation order. Nodes that follow one another (in the route and consequently in the format) imply an edge in-between. The first item for each node is an unsigned short whose lower 12 bits are the actual unique node number. Unsigned numbers are almost perfect because valid node indexes are nonnegative. To make room for the official invalid node index, -1, all node numbers are incremented before writing and decremented after reading. 12 bits are a compromise between piddly 8-bit numbers and hulking 16-bit numbers. More on this here.

The leftover 4 bits in the first unsigned short are complete situational directions for interpretation and subsequent writes/reads of the record. These are the "guide bits". All-zero guide bits encode a gate node and therefore moving on to the next node in the route, i.e. the next record in the file.

When the guide bits indicate a value node, there may be other items for the node. If the value node is preexisting in the destination graph, the data value index is skipped. Alternatively, if the value node is new, then the index for its value, another unsigned short, comes next. There are two possibilities: 1) if the destination graph contains a different node that represents the same value, its index is used and the guide bits reflect this; 2) otherwise the value itself is new so it will go in the complementary delimited text file of string-converted values, and the guide bits indicate that the value index applies to the text file instead. A subcategory of #2 is a new node whose value isn't in the destination graph but is already in the text file, so that text file value index is reused for additional new nodes with an identical value.

Lastly comes the vital missing information for the implied edge between the node and its successor: the requisite edge. Given that a requisite edge occurs previously in the same route, this is an 8-bit index into the component edges of the route.

As it turns out, still greater space efficiency is possible for requisite edges in some simpler cases. First, if there isn't an implied edge between successive value nodes in the binary file, which is possible whenever the transmitted route can happily reuse preexisting nodes and edges in the destination graph and therefore omit one or more intermediate edges, then the guide bits can indicate that fact and completely skip the writing/reading of the requisite edge information.

Second, if a requisite edge happens unfortunately to be the one completely unique edge of the route that trumps all other requisites, i.e. the edge from its gate node to the very first value node, then once again the guide bits can convey this without more space.

Third, a more difficult yet straightforward and common pattern for requisite edges is the immediate predecessor edge. New edges tend to be added in clumps, so avoidance of (most) explicit requisite edges for the entire clump can be a significant savings indeed.

In summation, it's clear that the guide bits, the top 4 bits of the first unsigned short of the record, are overloaded with implications. The four node varieties are gate node, existing value node, new value node whose value duplicates an existing value node, new value node whose novel string-formatted value is in the complementary text file. These node types determine what to do with the node's recorded value index or whether to skip it altogether. For each of the three value node record types, either the general case of a stated requisite edge or one of the three special-case strategies for skipping the requisite edge data may be applicable. The total is 3 types of value handling for value nodes multiplied by 4 options for requisite handling plus 1 independent gate node possibility, or 13 numbered "instructions" that fit in 4 bits.

git graphs compared to data sequence graphs

https://github.com/ArtV/DataSequenceGraph. This is an experimental release whose quality is not assured. Data sequence graph represents a set of data value sequences (IEnumerable<>), called "chunks", as nodes and directed edges in a single graph. More details.

Git represents revision history as a graph of nodes and directed edges, where each node is a commit and each edge points back to an ancestor commit. However, the needs of git are different than the needs of a data sequence graph, which underline the differences in design.

• A git graph has no cycles/circles (a commit cannot be its own grandpa, for instance). A data sequence graph may, but never within a particular data chunk's route. The routes use the cycle like a traffic roundabout, jumping into the circle and then leaving before completing a circuit. This is possible because of the rules that an edge's requisite edge must be met and the edge to be passively followed is the one edge whose requisite occurs first/earliest in the route's history.
• Nodes in a git graph aren't centrally numbered like in a data sequence graph. It couldn't use that strategy and still be thoroughly decentralized. Instead, the renowned "content addressable filesystem" of git names the commit with a hash of its information including its immediate ancestors. Git avoids global name collisions, but at the unavoidable expense of the required space for the hash. Although in practice a short prefix of the hash/name suffices to be unambiguous. Since a global or decentralized data sequence graph would probably be useless (but it's an intriguing idea...), the same constraint isn't applicable.
• Git also requires immutable commits or nodes. Not in the sense that rewriting or amending is impossible, but that a commit's identifier must also change whenever the commit's information changes (well, if you have the know-how you can bend this a bit, but normally...). The state of the revision-tracked content must reflect its ancestors definitively at the point of any commit. A selected commit represents one and only one content state. Whereas a node in a data sequence graph non-uniquely represents an individual value, and many data chunks/routes could possibly include that value/node. This difference also implies that while the identifier of a git commit would need to be different if it were a destination of greater or fewer edges, the simplistic numeric identifier of a node in a data sequence graph must remain the same no matter how other edges and nodes change.

musings on information in data sequence graph

Github link: https://github.com/ArtV/DataSequenceGraph. This is an experimental release whose quality is not assured. Data sequence graph represents a set of data value sequences (IEnumerable<>), called "chunks", as nodes and directed edges in a single graph.

The idea behind a data sequence graph is to store information not only about each chunk and its data values but also about the order of the values. By storing information about order in the graph as edges, hopefully chunk routes can share edges as well as value nodes. For when routes share edges and nodes, the shared edges and nodes are an actualized model of mutual information between routes and by extension their represented chunks. If the routes are in two different data sequence graphs whose nodes/edges are subsets, then there's mutual information between the graphs. And if the proper-superset graph is the sender and the proper-subset graph is the receiver, the communication channel for route nodes/edges may exploit the mutual information.

Specifically, given a secondary/destination/subset graph (i.e. MasterNodeList<>), a chunk's route (i.e. DataChunkRoute<>) can figure out just what needs to be added for the chunk route to function normally there [i.e. the "*missingComponents*" method(s)]. For example, when chunk X already has a route in the data sequence graph, and chunk Q is equivalent to chunk X with one additional data value appended, sending a route for Q merely requires the communication of a new gate node, an additional node for the appended value (but only if a node with that value isn't already in the graph!), and a few edges to connect the new nodes to the existing route for chunk X. Using the space-conscious binary+text format, the necessary bytes could possibly be a quarter or less of the bytes for the original entire Q chunk.

Naturally, as easy as it is to think of situations in which a data sequence graph leads to efficiencies, it's easy to think of inefficient situations. Since the purpose of all the many edges is to encode sequencing information, chunks of data values that occur more or less independently and randomly result in edges that are fruitless and wasteful. Placing data with no pattern into a graph yields a graph packed with huge quantities of both nodes and edges. The counterpart to the previous example would be an infinitesimal chance of known route X having a profitably-similar resemblance to new route Q. In the worst case, Q has nothing in common with its predecessor chunks, neither the order of its values nor any of the values themselves, and as a result the overhead of the node/edge definitions makes the route larger in space than the data it represents. This pathological case of a data sequence graph route is a cousin of the familiar pathological cases for data compression algorithms ("compression" enlargement). True randomness won't be denied or masked or neatly summarized; it can only be confronted in its full glorious ugliness.

But it's a broad domain between the perfect and worst sets of data chunks to encode as routes in a data sequence graph. The choice of how to break up the data into chunks is vital. Similarity within a chunk results in excessive numbers of nodes to recapture the identical repetitious values. Similarity between chunks results in effective reuse of each other's nodes and edges. Thus, for data that's in some way periodic or recurring, the period boundaries should be the chunk boundaries. Chunks that are too large or too small will fail to maximize the benefits of sharing redundant pieces of the overall graph.

That's the goal: to encode one route in terms of another route and thereby one chunk in terms of another chunk. By considering a route as an aggregate of data value nodes and the edges as relations, two routes in the graph with significant overlap are a partial "isomorphism" in the mathematically-unrigorous sense of the rambling post that Metamagical Themas inspired me to write: mapping one aggregate (route) onto the other "preserves" certain relations (edges). Furthermore, a data sequence graph whose nodes/edges form a proper superset of a second's is a partial isomorphism. As I outlined in the rambling post's "communication" section, when an isomorphism exists among communicators, the knowledge about correspondence of aggregates/parts/relations reduces uncertainty about related messages and therefore reduces the absolute necessary message length for the recipient to infer the whole. The *missingComponents* methods of the DataChunkRoute<> demonstrate this truism.

introduction to data sequence graph

Github link: https://github.com/ArtV/DataSequenceGraph. This is an experimental release whose quality is not assured. Data sequence graph represents a set of data value sequences (IEnumerable<>), called "chunks", as nodes and directed edges in a single graph.

Motivation

The importance of context shouldn't be underestimated. When interpretation of an ordered stream of information happens, even to the point of one person preemptively finishing another's sentence, previously communicated data items set up the expectations or probabilities for the following data items. To state the same idea differently, the history of the ordered stream continuously prepares a frame of reference for the informed interpreter. For example, "Java" then "Virtual" often precede "Machine", but "Java" then "Volcano" often precede "Alert". To a suitably knowledgeable agent, an information stream has path-dependence. Why not represent this with actual one-way routes through an abstract graph?

Abstract Model

• In a data sequence graph, a sequence of data values, called a "chunk", corresponds to one of many possible node-to-node routes over the one-way edges. 
• Most nodes in the graph are "data value" nodes that represent one and only one data value. A value node in the route represents the value in the chunk. Many value nodes may represent the same data value.
• A route starts and ends at exactly one route-specific special node called a "gate" node. No route contains more than one gate node, and no route includes gate nodes of other routes. The gate node functions as an entry/exit point into the graph. It doesn't represent a data value.
• Other than the gate node, a route never includes a node more than once. Data values that occur more than once in the chunk must be represented by separate value nodes in the route.
• Nodes are numbered for unique identification, whether gate or value nodes.
• A value node may have any number of connecting graph edges to other nodes. An edge can only be traveled in one direction, although there may be a separate edge between the same two nodes that goes in the reverse direction.
• Due to its function, a gate node has exactly one outgoing edge to a node that represents the first data value of the chunk, and exactly one incoming edge from a node that represents the last data value of the chunk.
• An edge has exactly one explicit requisite edge. A route must have already traversed the requisite edge in order to traverse the edge. The exception is the one edge from a gate node to a route's first value node.
• If a route is being passively followed (i.e. reproducing a chunk from a route) rather than actively created (i.e. creating a route to represent a chunk), the outgoing edge to follow next is the edge whose requisite occurs first/earliest in the route.

Implementation

Platform is .Net 4 in C#. The implementation is generic on the data value type, which must have a correct Equals implementation and otherwise work as a Dictionary key. The most important classes are

• the MasterNodeList<>, which holds all graph nodes and in effect the entire graph, is the gateway for most client requests and queries
• the DataChunkRouteBlazer<>, which is responsible for translating a chunk into a new route through the graph, has a computeFullRoute() method to ensure a functioning graph route for its chunk from start to finish
• the DataChunkRoute<>, which models a chunk route in the graph, has a followToEnd() method to walk the route (starting/finishing at the gate node) to regenerate the chunk

External Formats

The XML format is a relatively straightforward verbose listing of all the nodes and edges in a graph. The binary+text format uses a number of strategies to concisely store a graph as a binary file of nodes/edges and a delimited text file of node data values. Each format relies on two interfaces to translate the node values back and forth to strings: NodeValueExporter<> and NodeValueParser<>. There are implementations for string node values to be treated as-is: ToStringNodeValueExporter<> and StringNodeValueParser. (ToStringNodeValueExporter<> is directly reusable by any type for which ToString() is a working storage translation.) As written, the binary+text format exploits several hard assumptions for efficiency: 1) the number of nodes and therefore their unique serial numbers must be no greater than 4095, 2) the string translation of any node value must be no greater than 120 characters, 3) the string translation of any node value must not contain "|".

Command Line Interface

The included program uses the above code to manipulate data sequence graphs of sentence chunks and individual word values (i.e. each sentence is a route and each word is a value node). It has options for displaying, reading, writing, and comparing data sequence graphs in either format, as well as the option to restrict operation to a passed graph chunk/route.

reactions to unit test failures

I suspect that deepest dedication to a suite of automated unit tests isn't proven by having a test that touches each public class. Nor by a test for each public method. Nor by a test coverage tool that reports a proportion as close to 100% as is reasonable for that codebase. Nor even by strict test-first methodology.

The deepest dedication is only proven later in the code's life, when changes happen. Code changes of significance should lead to test failure or stark test compilation (or interpreter-parse) failure. That moment is when dedication takes effect. What will be the programmer's reaction? If it's a tiny test that broke, then a rapid and focused adjustment to the test or the code is likely to be the happy outcome. (Sidebar: this argues for not skipping trivial tests that probably are redundant to big tests. A failing trivial test is easier to interpret than a failing big test!) If it's a complex test or a large subset of tests that failed, then the reaction might not be as, er, placid.

• The worst reaction is to impulsively eliminate the failing test(s). Better but not by much is to turn the test(s) into comments or otherwise force a skip. A disabled/skipped test is always a temporary measure of compromise to reduce mental clutter during the thick of an intense task. It carries an implicit promise to enable the test at the next possible opportunity. Excessive distracting nagging is awful but permanently removing a safety net clearly falls into the "cure worse than disease" category.
• Assuming the motivation for the code change was a real change in requirements rather than code refactoring and improvement, then direct elimination may be correct. Before doing so, remember that unit tests act like executable specifications for that unit, and ask yourself "Does this test correspond to a code specification that still applies to the changed code but in a different form?" When the answer is "yes", the test should be replaced with a corresponding test for the transformed specification. Consider previous tests that caught corner cases and boundary conditions. If an object previously contained a singular member, but due to changes in the problem domain it now contains a collection, then the test for handling a NullObject singular member might correspond to a replacement test for an empty member collection. 
• On the other hand, whenever the change's purpose is to improve the code while leaving intact all existing functions/interfaces of importance, elimination or fundamental rewrites aren't the right course. The test stays, regardless of its inconvenience in pointing out the shortcomings of the redesign. The right answer may be to rethink part of the code redesign or in a pinch to add on to it in some small way with some unfortunate adapter code until other modules finish migrating. Sometimes a big fat legitimate test failure is the endpoint and "smoking gun" of an evolutionary mistake of the code, and the professional reaction is to disregard personal/emotional attachment by cutting off or reshaping the naive changes. Never forget that to users the code is a semi-mysterious black box that fills specific needs. Sacrificing its essential features (rather than unused feature bloat) is too high a price for code that's more gorgeous to programmers. Granted, skillful negotiators can counter by pledging sophisticated future features that the redesigned code will support, in which case the pledges must turn out to be more than vaporware for the trick to ever work again.
• With any luck, the ramifications are not so dire. A confusing unit test failure may not be a subtle lesson for the design; it may be nothing more than a lesson to write more (small) tests and/or test assertions. It seems counterintuitive to throw tests at failing tests, yet it makes a lot of sense given that tests are coded expectations. In effect, confront the failing test by asking "What did I expect?" immediately followed by "Why did I expect that?" Expectations build on simpler expectations. Attack the expectation in top-down step-wise analysis. The expected final outcome was 108, because the expected penultimate outcome was 23, because the expected count was 69, etc. Write tests for those other, lesser expectations. Now the tests narrow down the problem for you at the earliest point of error, as if being an automatic debugger with predefined breakpoints and watch-expressions.
• It's a well-known recommendation to write an additional unit test for a bug discovered "in the wild". This test confirms that the bug is fixed and then reconfirms that the bug doesn't resurface, assuming frequent runs of the entire suite. After a few unsuccessful tries at passing this novel test, don't be too rigid in your thought habits to ponder the possibility that the untested test is buggy! In the prior items my encouragement was to not react by blaming the tests, since an unmodified test that passed before a code change and fails afterward logically indicates that what changed, i.e. the code, must be to blame. Philosophically man is the measure of all things and a unit's tests are the measure of the unit. Not so during the introduction of a test. At this special time, the test isn't a fixed ruler for measuring code errors. It's its own work in progress in a co-dependent relationship with the code it measures. Initially the code and the test are at danger of dragging the other down through bugs. A buggy test is a false premise that can lead to a false conclusion of fine code that appears to be buggy or worse buggy code that appears to be fine. Be careful to write tests as minimal, unassuming, and straightforward as is practical. Complex tests that check for complex behavior are acceptable (and hugely important!). Complex tests that are intended to check for simple behavior are less justifiable and trustworthy. Tests are miniature software projects. The more convoluted and intricate and lengthy a test becomes, the greater opportunity for bugs to sneak in and set up shop.

when 255 is too little and 65535 is too much

Before I begin, yes, I do realize that low-level bit twiddling is often not worth the time any more. When storage and memory is so cheap, and the sheer scale of processing has progressed so far even on a "smart" phone, little micro-optimizations may...just...not....matter. Switching to an alternative high-level algorithm/strategy better suited to the specific scenario is generally a much more promising route. However, network transmission and/or mass data record layout are two prominent exceptions to this rule. The fewer bytes that must be sent between computers on potentially high-latency and congested networks, the better, and the fewer average bytes per record that is multiplied by a potential quantity of thousands up to millions of records, the better. So there still is some life yet for bit twiddling.

One unsigned byte represents nonnegative integers up to 255 (including 0). Two unsigned bytes represent nonnegative integers up to 65535. The storage doubles, but the representational range squares. In basic-arithmetic-speak the range is "256 times its original amount". In science-speak the difference might be called "an approximate difference of 2.40824 on a logarithmic (lg) scale". In marketing-speak the difference might be called "an increase of 25,500%". The upshot is that this exponential jump could very well be overkill in particular cases. For instance, if data values never are less than zero or greater than 4000, 12 bits or one-and-half bytes is sufficient (2^12 -1 = 4095).

Yet reading and writing an arbitrary number of bits like 12 isn't well-supported, for valid performance reasons. Manipulating 12 bits in practice implies manipulating the next-greatest number of bytes, 2 or 16 bits. And that implies 4 wasted bits for "spacing" or "alignment". Why not use these bits? Two of these 12-bit unsigned integers sum to 24 bits or 3 bytes. When each of the two 12-bit number is stored in 16 bits, the fourth overall byte, consisting of the top 4 unused bits from the first number and the top 4 unused bits from the second, are waste. Avoidance of that fourth byte reduces total storage needs by 25%. Whether this substantial relative space savings amounts to a substantial absolute/raw space savings depends on the application and other factors. I'd venture that in the majority of the time it doesn't. But when it does...

Each 12-bit integer is a byte-and-half. For two, just combine their two half-bytes (4 bits) into byte number three (8 bits). The conversion procedure from two nonnegative 12-bit integers, originally stored as two 16-bit integers (i.e. unsigned short) or 4 total bytes originally:

1. 1) Get the first output byte by truncating/coercing/casting the first 16-bit integer. This grabs the 8 low bits of the first number, leaving the remaining 4 high bits to be stored separately.
2. 2) In the same way as #1, get the second output byte by truncating/coercing/casting the second 16-bit integer.
3. 3) Get the remaining 4 high bits of the first integer by right-shifting it by 8 and then coercing to a byte. The result is the top 4 bits of the first integer stored in a byte as-is. All the lower 8 bits of the first integer, that were previously stored in #1 and became the first output byte, are right-shifted out completely into oblivion and zeroes take the place of the shifted bits. This byte is now the "top byte" of the two bytes in the original 16-bit storage of the integer.
4. 4) In the same way as #3, get the remaining 4 high bits of the second integer by right-shifting by 8 and then coercing to a byte.
5. 5) The third and last output byte will be a concatenation of the two integers' top 4 bits, which after #3 and #4 are now themselves stored as bytes in which the top 4 bits are waste. The lower 4 bits of the output byte will come from the #3 byte, in which the correct bits are already at the correct lower position. But the higher 4 bits of the output byte will come from the #4 byte, in which the correct bits are also in the lower position, which is incorrect for those 4 bits. Therefore, left-shift #4 byte by 4 to get the bits in final position.
6. 6) Finally the two parts of the third byte, the #3 byte and #5 byte, are ready, with correct bits in correct positions and zeroes everywhere else. Thus each bit in each byte must "override" the zeroed-out bit in the other. If corresponding bits are both 0, then 0. If corresponding bits are 0 and 1, then 1. Since this is the definition of a bitwise OR (|), perform that operation on the #3 byte and #5 byte to get the third byte.

The conversion from three unsigned bytes back to two 12-bit integers, stored individually in two unsigned 16-bit variables:

1. 1) The lower 8 bits of the first integer is the first input byte. Expand/coerce/cast the first input byte to 16-bit storage.
2. 2) The lower 8 bits of the second integer is the second input byte. Also expand/coerce/cast to 16 bits.
3. 3) The third byte has the top 4 bits of the first integer in lower position, and the top 4 bits of the second integer in higher position. To get the top 4 bits of the first integer as a byte all to itself, just the top 4 bits of the third byte must be replaced with zeroes. For each of those top 4 bits, 0 must result in 0 and 1 must result in 0. For each of the lower bits, the bits that must remain undisturbed, 0 must result in 0 and 1 must result in 1. A bitwise operation that sometimes turns the first bit into 0 and sometimes into 1, depending on the second bit, is AND (&). Any time the second bit of an AND is 0, the result will be 0. Any time the second bit of an AND is 1, the result will equal the first bit. Bitwise AND fits the purpose, provided all the bits in the second byte are set accordingly. This second byte for the AND operation, known as a bitmask because the zeroes in it will "mask" or hide bits while the ones in it will "pass through" bits, must simply have zeroes in the 4 higher bits and ones in the 4 lower bits. Expressed as a byte, the bitmask is "0000 1111" in binary or "0F" in hexadecimal or "15" in decimal. In any case, the result of the AND operation between the third input byte and the bitmask is the upper 4 bits of the original first 12-bit integer.
4. 4) The higher 4 bits of the third input byte are the top 4 bits of the original second 12-bit integer. To get these 4 bits as a byte all to itself, right-shift the third input byte by 4. This pushes out the lower 4 bits of the third input byte, that was stored in #3, and leaves the higher 4 bits (with replacement zeroes in higher position).
5. 5) The #3 byte, in which the higher 4 bits of the original first12-bit integer are in lower position within one byte, equals the original higher byte of the 16-bit storage of the original first 12-bit integer. All that's necessary is to put the #4 byte into correct 16-bit position, which is precisely one byte or 8 bits higher. Expand/coerce/cast the #3 byte into 16-bit storage and then left shift by 8.
6. 6) In the same way as #5, expand/coerce/cast the #4 byte into 16-bit storage and then left shift by 8.
7. 7) #1 and #5 are 16-bit unsigned integers whose bits are all in the right locations for the original first 12-bit integer stored in two bytes. And any bits in #1 and #5 that don't match are zero. This means that a bitwise OR between the two will "override" the placeholder zeroes with the real bits in the other and get the original two bytes of the first 12-bit integer.
8. 8)  In the same way as #7, #2 and #6 after bitwise OR will be the original two bytes of the second 12-bit integer.

information hiding applied to generic types

Over time, I have a growing preference for the term information hiding over encapsulation. Encapsulation communicates the idea of wrapping data in an object or protecting privileged access through managed methods. But design analysis shouldn't stop there. Information and/or knowledge can leak and spread through a design in more subtle ways. For instance, I previously wrote that the HTML page's DOM is an overlooked example of shared state in Javascript. When many code pieces, each meant to serve separate and independent goals, have accidental dependencies outside themselves, both code reuse and intelligibility suffer. A part can no longer be understood without understanding the whole.

The purpose of information hiding, interpreted in a more general sense than encapsulation, is to thwart the natural tendency for code to not only collaborate but conjoin into the dreaded big ball of mud. Information hiding preserves metaphorical distance between expert objects with well-defined responsibilities. Then whenever a question arises, there's one answer and that one answer comes from the expert. The opposite outcome is several answers, found by wandering through the system, and one can never be quite certain that all the right generalists have been duly consulted and cross-checked.

Generic types may be susceptible to violations of information hiding. For in order to concretely consume a class with a generic type parameter, the type for the parameter must be specified (of course). But the conscientious designer should frankly ask whether the type parameter information belongs in the consuming class. By including it, the consuming class must either be coupled to a type-specific instance of the generic class or itself become a generic class that requires and passes on the same type parameter. The first option makes the consuming class less reusable/flexible while the second option leads to greater implementation complexity and further propagation of the type parameter information.

The third option is to hide the generic type information from the consuming class altogether. Some possibilities:

• Have the generic class implement a minimal non-generic interface. Then couple the consumer class to this interface. Creating/obtaining new instances of the generic class for the interface would happen through a separate factory/service locator/dependency injector.
• If the generic class is part of an inheritance hierarchy, then move the non-generic portions into a superclass. It's permissible for a non-generic superclass to have generic subclasses. Now the consuming class can work with instances of the generic subclasses by typing them at the non-generic superclass level.
• Assuming the generic class doesn't have generically typed state, consider making the class non-generic with some methods that are generic only when necessary. In such situations the compiler probably can infer the methods' type parameter based on which types the consuming class passes to the methods, so not even calls to the remaining generic methods need to have the complexity of "looking generic". 

As with any usage of generic types, consider the trade-offs carefully. Generic types sacrifice some clarity and usability. In particular, when code isn't getting anything back out of a class, the information of how to fill in the generic type parameter tends to be irrelevant, distracting, and potentially too restrictive. Generic types in one part of a project shouldn't cause the entire project to take on needless generic types everywhere.

quick tip for using gitextensions with git svn

I imagine some others have already noticed this, but git svn commands can be added as "Scripts" that are available from the history context menu. For instance, for "git svn rebase": Go to Settings > tab Scripts, click Add, enter a Name and be sure to click "Add to revision grid context menu", enter "C:\Program Files\Git\bin\git.exe" for the Command, "svn rebase" for the Arguments, then click Save. Now, with a right-click on the history graph in gitextensions, the new command should show up down at the bottom with the entered Name. Choosing it will bring up the expected output window. Similar steps apply for "git svn dcommit --dry-run" and "git svn dcommit".

It's a small change, yes. And for the full glory of git you still must click on the little terminal icon on the gitextensions toolbar and use the command line. But repetitive tasks should be made as rapid and unobtrusive as possible to conserve the programmer's cognitive load (which is why running one's unit test suite should also be extremely easy and painless). Of course, even the tiniest enhancement to workflow adds up over many times thereafter. Just as a mostly-positive monthly cash flow is the key to long-term financial sustainability, a mostly-frictionless development flow allows programmers to expend their valuable time on stuff that matters, like design.

git is a VCS for the imperfect programmer

I just recently had a workday in which I realized how appropriate git can be for imperfect programmers. My department had released a project to the users for the first time, so I was working through the inevitable few tickets and/or change requests that ensue when software leaves a controlled development phase and collides with people.

I'd completed several commits on top of the release when I got a call about a bug related to a highly exceptional set of data. "No problem," I thought. "I can work it in with all these other commits and it will go out with them on the next scheduled full redeployment to the website." So I started working, but after designing a fix I discovered that it had so few systemic dependencies that I could easily push it out on its own without disruption, and enable the user who called to continue her work on the problematic data set. In another VCS this might have been unwieldy, but not with git. I stashed my work, created and checked out a branch at the last-released commit, popped the fix off the stash, and committed it.

Unfortunately it was only after that point that I noticed a possible weakness of the fix (and also the original code). Once again, with git this wasn't cause for alarm. I corrected the fix by amending the commit I'd just made. Finally, I had a file whose only difference from the last release was the fix. I deployed the file.

I should mention that an older edition of Subversion is the official VCS of my team, and we simply don't use branches or tags (it's not my decision). As a small team in a small organization with lots of informal communication, it's mostly sufficient for our needs, although I imagine that we'll need to become more sophisticated in the future. Thus, my fresh branch for the isolated bug-fix had to be a local git branch only. In order to ensure that the next deployment included that commit, I had to incorporate it into the Subversion trunk. With git, a rebase of my branch onto the HEAD of master was easy, and of course the actual merge of it into master was then a fast-forward. After a quick delete of the merged local branch and "git svn dcommit", everything matched up again.

A number of things about the procedure were imperfect. I'm an imperfect individual who made missteps. And I work in an imperfect setup with a decidedly imperfect team VCS. But it turns out that git fits these conditions just fine.