Click here to Skip to main content
15,867,756 members
Articles / Programming Languages / C#

Set Your Data and Code Free from the Constraints of Hierarchies and Tables

Rate me:
Please Sign up or sign in to vote.
4.62/5 (9 votes)
31 May 2010CPOL15 min read 20.6K   94   20   9
This article describes a base implementation of Ted Nelson's zzstructure in C#.
ZZDemo_screenshot.png

Introduction

Ted Nelson's article A Cosmology for a Different ComputerUniverse describes (among other things) a very high-level data structure, the zzstructure. If you haven't read Nelson's article, I recommend that you do so now - at least the parts that describe the zzstructure and zzviews - because until you do, it is unlikely that this article and the code that accompanies it will make much sense. And anyone who has read the article, but not recently, probably will benefit from reviewing it before continuing.

Herewith is presented a C# implementation of the zzstructure, along with a simple view that presents the ranks and cells of a single zzstructure dimension as a 2D table. This implementation is usable as-is for some conceivable purposes, and could provide a basis for the realization of many of the additional concepts mentioned in Nelson's article.

Background

When I first read about the zzstructure, in 2007, I wanted to implement it in C#. My first effort to do so failed because I did not read Nelson's article carefully enough; and I took liberties with his design that actually made it much more difficult, if not impossible, to implement [my distorted version of] the zzstructure. More recently, I returned to the article, read it with great care and considered how one might implement the zzstructure as Nelson describes it.

(Note that Nelson's description remains at a high level, for the most part - giving one, as a potential implementer, almost enough rope to hang oneself, but also inciting him or her to creative problem-solving and providing opportunities for harmonious elaboration on the basic concepts and constructs. The net result is a fairly steep, but potentially pleasant, challenge to the developer.)

Taking notes on Nelson's article, highlighting key sentences and phrases, led to my next developing descriptions of relevant classes and their properties and methods. I think that, for almost anyone, immediately diving in and coding after merely reading the article is a recipe for frustration and failure. The zzstructure is an entity of sufficient complexity, embodying a set of very precise ideas that work together like cogs in a sort of abstract machine, that the ways to implement it correctly are quite significantly fewer in number than the ways in which one may fail to do so.

In marked contrast to my previous effort to implement the zzstructure, this time the final product of my efforts (the source code that accompanies this article) came together fairly easily, and actually resembles the design document quite closely - although I did append a few helpful features that I hadn't anticipated while developing the basic design.

Using the Code

When and how might one use the zzstructure? There are many possibilities, as suggested and hinted at in Nelson's article and by others who have analyzed the zzstructure. See, for example, the paper A Comparison of Hyperstructures: Zzstructures, mSpaces, and Polyarchies by Michael J. McGuffin of the University of Toronto.

Basically, when limitations imposed by the use of conventional data structures and representations become problematic, it is time to consider possibly using a higher-level way of organizing and connecting data. Quite a lot could be written on this topic, and to be honest, I haven't yet done sufficient research on it, or given it enough careful thought, to do it justice; so let me just suggest to the reader the same things I intend to do: further research and thinking, combined with experimentation.

To quickly cite a couple of example applications, the zzstructure has been used to model, and facilitate visualization of, complex molecules, as well as human genealogies. (The latter departs from a neat hierarchical structure whenever two measurably close relatives marry or have a child together.)

Zzstructure Implementation

Ted Nelson identifies the "primitives," or fundamental components, of a zzstructure as: zzcell (cell), zzdim (dimension) and zzlink (link). He also lists several "emergent concepts," including "rank," which I chose to implement explicitly both for the client program's (or developer's) convenience and for internal simplification and optimization. Thus, in this implementation, a zzstructure is composed of the classes ZZStruct, ZZCell, ZZDim, ZZLink and ZZRank. A brief overview of each class's features (public properties and methods) follows.

ZZStruct - Constants

  • DCursorName - The system dimension name "d.cursor"
  • DCloneName - The system dimension name "d.clone"
  • D1Name - The system dimension name "d.1"
  • D2Name - The system dimension name "d.2"
  • D3Name - The system dimension name "d.3"

ZZStruct - Properties

  • DimensionRange - Gets all system and non-system dimensions in the zzstructure, returning them as an array ("range"). The dimensions are returned in the order in which they were added.
  • CellRange - Gets all cells in the zzstructure, returning them as an array ("range"). The cells are returned in the order in which they were added.
  • AccursedCell - Gets the cell that is the current object-of-focus via (or focal cell of) the d.cursor dimension. Sets the specified cell as the current object-of-focus via / focal cell of d.cursor.

ZZStruct - Methods

  • ZZStruct() - Initializes a new instance of the ZZStruct class. The default system dimensions d.cursor, d.clone, d.1, d.2 and d.3 are created automatically. (Notice that none of the component classes - ZZDim, ZZCell, ZZRank or ZZLink - has a public constructor.)
  • AddDimension(string id, bool addAsSystemDimension = false) - Adds a dimension with the specified ID. Client code has the option of defining a new dimension as a system dimension. (A system dimension cannot subsequently be removed.)
  • RemoveDimension(ZZDim dimToRemove) - Removes the specified dimension from the ZZStruct.
  • GetDimension(string id) - Gets the dimension with the specified ID if it exists in the zzstructure. If a dimension with the specified ID is not found, returns null.
  • AddCell(object content, string id = <internally-generated identifier>) - Adds a cell with the specified content, which may be null. The new cell is added to d.clone automatically. (In this implementation, every cell in a zzstructure is a member of d.clone.)
    [Added 30-May-2010: Originally - as shown in the introductory screenshot - the internally-generated identifiers were GUIDs. But as a reader pointed out, using GUIDs as strings results in a needless waste of memory; so the GUIDs have been superseded by another scheme, which represents values of an internal sequence number compactly, in base 64 notation.]
  • RemoveCell(ZZCell cellToRemove) - Removes the specified cell from the zzstructure.
  • GetCell(string id) - Gets the cell with the specified ID if it exists in the zzstructure. If a cell with the specified ID does not exist in the zzstructure, returns null.
  • CursorMoveNegward(int count = 1) - Moves the cursor the specified number of steps in the negward direction or to the first-accursed cell in d.cursor (i.e. the cursor's history). If the count argument's value is greater than the number of steps available, returns null; otherwise, returns AccursedCell.
  • CursorMovePosward(int count = 1) - Moves the cursor the specified number of steps in the posward direction or to the last-accursed cell in d.cursor (the cursor's history). If the count argument's value is greater than the number of steps available, returns null; otherwise, returns AccursedCell.
  • CursorMoveNegmost() - Moves the cursor the specified number of steps in the negward direction or to the first-accursed cell in d.cursor the cursor's history) and returns AccursedCell.
  • CursorMovePosmost() - Moves the cursor the specified number of steps in the posward direction or to the last-accursed cell in d.cursor (the cursor's history) and returns AccursedCell.
  • CursorClear() - Clears the cursor's history and sets AccursedCell to null.

Notice that the properties and methods listed above fall into three categories: They are concerned either with dimensions, or with cells, or with the cursor (d.cursor and the "accursed" cell). The cursor is designed to behave like the Back and Forward buttons on a Web browser. (I couldn't tell from Ted Nelson's article exactly what behavior he had in mind, but this is a reasonable implementation that follows a behavioral standard with which people are familiar.)

It's also notable that clients cannot create dimensions or cells directly; they can only be created by calling methods of the ZZStruct class, and within the context of a ZZStruct.

ZZCell - Properties

  • Structure - Gets the ZZStruct within (or by) which the cell was created
  • ID - Gets the cell's string ID, that is unique within its ZZStruct
  • Content - Gets the object (or null) that is the content or payload of the cell
  • IsRemoved - Gets indication of whether the cell has been removed from Structure
  • LinkRange - Gets the links for all dimensions in which the cell is present, returned as an array

ZZCell - Methods

  • IsPresentInDimension(ZZDim dimension) - Gets indication of whether the cell is present in the specified dimension
  • IsPresentInRank(ZZRank rank) - Gets indication of whether the cell is present in the specified rank
  • GetLink(ZZDim dimension) - Gets the ZZLink that registers the cell's presence, and neighbor(s) if any, in the specified dimension. If the cell in not present in the specified dimension, returns null.
  • GetRank(ZZDim dimension) - Gets the rank in which the cell is present within the specified dimension. If the cell in not present in the specified dimension, returns null.
  • GetNegwardNeighbor(ZZDim dimension) - Gets the cell's negward neighbor (which may be null) in the specified dimension.
  • GetPoswardNeighbor(ZZDim dimension) - Gets the cell's posward neighbor (which may be null) in the specified dimension.

ZZDim - Properties

  • Structure - Gets the ZZStruct by which the dimension was created
  • ID - Gets the dimension's unique string ID
  • IsSystemDimension - Gets indication of whether the dimension can be removed from the ZZStruct that created it
  • IsRemoved - Gets indication of whether the cell has been removed from Structure
  • RankRange - Gets the ranks present in the dimension, returned as an array
  • CellRange - Gets the cells present in the dimension, returned as an array

ZZDim - Methods

  • AddRank(ZZCell cell, object tag = null, bool makeRing = false) - Adds a new rank to the dimension that contains the specified cell. An arbitrary object may be attached to the rank via the tag argument. If makeRing is true, the cell will be its own negward and posward neighbor in the new rank; otherwise, the cell will have no neighbors.
  • RemoveRank(ZZRank rankToRemove) - Removes the specified rank from the dimension
  • InsertAfter(ZZCell cellToInsert, ZZCell after, bool autoClone = false) - Inserts cellToInsert into the dimension following after
  • InsertBefore(ZZCell cellToInsert, ZZCell before, bool autoClone = false) - Inserts cellToInsert into the dimension preceding before
  • Append(ZZCell cellToAppend, ZZRank rank, bool autoClone = false) - Appends cellToAppend to rank
  • ReplaceCell(ZZCell cellToRemove, ZZCell cellToInsert, bool autoClone = false) - Replaces cellToRemove with cellToInsert
  • RemoveCell(ZZCell cellToRemove) - Removes cellToRemove from the dimension
  • GetNegwardNeighbor(ZZCell navigateFrom) - Gets the specified cell's negward neighbor (which may be null) in the dimension
  • GetPoswardNeighbor(ZZCell navigateFrom) - Gets the specified cell's posward neighbor (which may be null) in the dimension

The autoClone argument of the methods listed above that insert cells ( InsertAfter, InsertBefore, Append, and ReplaceCell) specifies whether or not the cell to be inserted should automatically be cloned if it found already present in the target dimension.

ZZLink - Properties

  • Rank - Gets the rank context of the link
  • SubjectCell - Gets the cell that the link applies to
  • NegwardNeighbor - Gets the cell that is SubjectCell's negward neighbor within Rank. Returns null if SubjectCell has no negward neighbor within Rank.
  • NegwardNeighbor - Gets the cell that is SubjectCell's posward neighbor within Rank. Returns null if SubjectCell has no posward neighbor within Rank.
  • IsRemoved - Gets indication of whether the link has been removed from SubjectCell

ZZLink has no public methods.

[Added 30-May-2010:] This implementation deviates from Nelson's definition in making the ZZLink objects visible to clients, though read-only, since there is no harm in doing so and the information thus provided conceivably could be useful for debugging.

ZZRank - Properties

  • Dimension - Gets the dimension context of the rank
  • Tag - Gets an arbitrary object attached to the rank by a client. Ranks are anonymous by definition; however, the Tag object may be used to attach metadata that can be used for ordering (sorting) and other purposes.
  • IsRing - Gets indication of whether the rank is a ringrank
  • IsRemoved - Gets indication of whether the rank has been removed from Dimension
  • CellRange - Gets the cells of the rank, returned as an array. The cells are ordered negmost to posmost
  • HeadCell - If the rank is not a ringrank, gets the negmost cell of the rank. If the rank if a ringrank, gets or sets a cell possibly assigned by the user to be regarded as negmost; the value gotten or set can be null. If the rank is not a ringrank, assigning to HeadCell does not cause an exception to be thrown, but it has no effect.
  • SystemHeadCell - Gets a specific cell of the rank, guaranteed to be non-null even if the rank is a ringrank and HeadCell has not been assigned a value.

ZZRank - Methods

  • MakeRing() - If the rank is not already a ringrank, makes the HeadCell and the posmost cell neighbors - at which point there is no longer a HeadCell, unless / until the client assigns one. Returns indication of success or failure.
  • BreakRing(ZZCell headCell) - If the ring is a ringrank, breaks the link between headCell and its negward neighbor; thus headCell becomes the new HeadCell.

The IsRemoved indicator (common to all of the above classes except ZZStruct) can be very important, since conditions that normally hold for components of a ZZStruct may not longer hold after an object has been removed. Further, querying or operating on an object that is no longer a part of the structure makes no sense (and causes an InvalidOperationException to be thrown).

Conditions that cause exceptions are usually obvious: in addition to the common condition on IsRemoved, ZZDim, ZZRank, ZZCell and ZZLink arguments must be non-null for semantic and functional reasons, and an exception is thrown when an object that should be present in a parent object is not, or when an object that should not be present is in fact present.

The reader may have noticed that no events are mentioned above. The absence of events from the implementation does not indicate that events are undesirable, for some reason - just that I haven't gotten around to adding them yet, or to considering scenarios in which they would be useful or necessary.

Zzview Implementation

A single view is provided, which is just a 2D array of ZZCell instances (ZZCell[,]) with the number of cells in each dimension determined by the client program. The ZZ2DViewBuilder class calculates this view.

ZZ2DViewBuilder could be documented just as ZZStruct and its components were above; instead, I will just recommend reading the code, which is quite straightforward and easy to understand once one has grokked the zzstructure implementation.

The ZZDemo program

Yes, the screenshot shows a console program, and that is what you get with the downloadable project. I frequently find it convenient, when developing library code, to use a console program to test and exercise the code without the time-and-effort investment required to create a graphic user interface. Of course, some formatting must be done, but to me it seems easier and faster to just use formatted text output with Console.WriteLine. (If I had added a graphical UI, its principal feature would have been a display of scrolling text, so "Why bother?")

Here is what the console demo program does "out-of-the-box." (Of course, you can easily modify it to exhibit slightly, or radically, different behavior.)

The program uses a zzstructure to build (represent, store), manipulate and display goofy sentences - and when working with the view, sentence fragments. Here is what happens, in detail:

  1. First, a ZZStruct is created and 40+ words of various types are added to it as cells, to serve as a palette from which "sentences" can be constructed. Then three sentences are built in two different user-defined dimensions (one sentence in one dimension and two in the other), using a process that is haphazard by design so that a variety of ZZStruct methods and properties can be exercised and tested. [Notice that sentences in different dimensions can share the same word(s) but a word must be cloned each time it is re-used within the same dimension. This behavior follows Nelson's specifications, per careful reading of his article.] Then a textual representation of the zzstructure's current state is printed.
  2. A view that provides a "window" into the group of sentences that have been stored in the zzstructure is built and displayed.
  3. The program plays around a bit with the cursor feature, and then prints the d.cursor dimension to facilitate examination of its state.

Conclusion

This (until now, purely personal) project was/is a very compelling exercise in several ways. Perhaps it will grab some reader's interest as it did mine. Are you the person who will take this zzstructure implementation in C# to the next level of refinement, and/or the one who will find an application for the zzstructure in your own work, perhaps putting a refined / extended version of this implementation to work in some practical way? I hope that anyone who does either or both of those things will add comments to this article, or perhaps post her or his own article to share the knowledge and wisdom gained.

History

  • 16th May, 2010: Initial version
  • 30th May, 2010: Article updated

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior) Concur
United States United States
George Henry has worked as a software developer for more than 20 years. He is currently employed by Concur in Bellevue, Washington, USA.

Comments and Discussions

 
QuestionToo much time on my hands? Pin
George Henry 195413-Feb-11 13:29
George Henry 195413-Feb-11 13:29 
GeneralSome thoughts Pin
Qwertie28-May-10 4:31
Qwertie28-May-10 4:31 
GeneralRe: Some thoughts Pin
George Henry 195429-May-10 10:17
George Henry 195429-May-10 10:17 
GeneralRe: Some thoughts [modified] Pin
Qwertie29-May-10 19:18
Qwertie29-May-10 19:18 
GeneralRe: Some thoughts Pin
George Henry 195429-May-10 21:13
George Henry 195429-May-10 21:13 
GeneralRe: Some thoughts Pin
Qwertie30-May-10 4:14
Qwertie30-May-10 4:14 
GeneralRe: Some thoughts Pin
George Henry 195430-May-10 8:38
George Henry 195430-May-10 8:38 
GeneralWow Pin
James Huebsch19-May-10 19:48
James Huebsch19-May-10 19:48 
GeneralRe: Wow Pin
George Henry 195419-May-10 20:05
George Henry 195419-May-10 20:05 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.