浅析Family Show 2.0的数据结构及基本算法

作者：Tony Qu

Family Show虽然是用WPF做的，但不管怎么说它都只是一款家谱软件，其数据结构自然应该是一个树型结构，那么在这款软件中是如何实现的呢？（这里也顺便提醒一些初学者，不要觉得技术高级了，就不需要基础的东西了，数据结构和算法永远都是软件开发的核心要素，所以一定要学好学扎实了，否则就算有再高级的技术你也不知道如何使用。）

首先我们来讲讲最基础的Person类。Person顾名思义就是一个人，按照正常的思路，既然是树型结构，那么就应该把每一个Person看作一个结点，然后不断地添加子结点和相邻结点。对没错，思路很好，但是很可惜Family Show并不是这么做的，其实存储用的东西是Collection而已，当然最后做呈现的时候自然还是要还原为树的，至于怎么还原，我会在最后讲解。先来看看Person、PeopleCollection和People这三个类。

第一次看到这三个类，我也很困惑，既然People已经是复数了，为什么还要有一个PeopleCollection，莫名其妙。。。读了代码之后才理解其含义，其实PeopleCollection在这里才是真正放Person的集合，而People这个类当中也使用一个私有的PeopleCollection来作存储的，并提供了一个PeopleCollection类型的PeopleCollection属性（这里属性名与类名同名），用于返回那个私有的PeopleCollection。我们来看下面一段代码：

[System.Diagnostics.CodeAnalysis.SuppressMessage( " Microsoft.Usage " ,  " CA2211:NonConstantFieldsShouldNotBeVisible " )]
         public   static  People FamilyCollection  =   new  People();
        [System.Diagnostics.CodeAnalysis.SuppressMessage( " Microsoft.Usage " ,  " CA2211:NonConstantFieldsShouldNotBeVisible " )]
         public   static  PeopleCollection Family  =  FamilyCollection.PeopleCollection;

这是FamilyShow的App全局类中定义的成员，这里的Family成员在整个程序中到处都用到，就是用来存储家谱数据的，那么这里的FamilyCollection又是干嘛用的呢？其实用到FamilyCollection的代码并不多，比如：

             if  (Family.IsDirty  &&   ! string .IsNullOrEmpty(FamilyCollection.FullyQualifiedFilename))
                FamilyCollection.Save();

让我们再来看看Save里面的代码：

         public   void  Save()
         {
            // Return right away if nothing to save.
            if (this.PeopleCollection == null || this.PeopleCollection.Count == 0)
                return;
            
            // Set the current person id and name before serializing
            this.CurrentPersonName = this.PeopleCollection.Current.FullName;
            this.CurrentPersonId = this.PeopleCollection.Current.Id;

            // Use the default path and filename if none was provided
            if (string.IsNullOrEmpty(this.FullyQualifiedFilename))
                this.FullyQualifiedFilename = People.DefaultFullyQualifiedFilename;

            XmlSerializer xml = new XmlSerializer(typeof(People));
            using (Stream stream = new FileStream(this.FullyQualifiedFilename,
                   FileMode.Create, FileAccess.Write, FileShare.None))
            {                   
                xml.Serialize(stream, this);
            }
            
            this.PeopleCollection.IsDirty = false;
        }

这下你应该明白了吧——FamilyCollection就是用来保存数据到文件的，这也是为什么在People类的定义上面有 [ XmlRoot ( "Family" )]，其他的大部分属性 都是忽略的（都用了[XmlIgnore]），而PeopleCollection属性什么也没有用，这就表示需要做XML序列化，其实说白了，People类就是一个序列化封装类，这样才可以把PeopleCollection有效地做序列化。注意，要完全实现序列化，必须保证People中所用到的类都带有[Serializable]标志，否则可能导致数据丢失，这也是为什么你可以在PeopleCollection、Relationship、Person这样的类上找到[Serializable]标志。（这一块涉及到.NET对象序列化方面的知识，这里就不做展开了。）

至于用Save保存的文件是个什么样，大家可以看Sample Files目录下的.family文件，比如Windsor.family，这里就不贴出来了。

有了以上这段分析，我想大家对基本的数据构成已经理解了，接下来我就来讲讲这些数据是如何还原为树型结构的。

在FamilyShow的主项目中我们会看到一个Diagram目录，里面都是以Diagram开头的类，这就是我们要找的用来还原树型结构的一些类。那大家可能会问FamilyData目录里面的东西是干嘛用的？这些类也是用来呈现家谱数据的，但是这里面所用到的数据并不需要树型结构，都只是一些List之类的数据显示，而Diagram则是用来显示一个树状结构的。细心的人可能已经发现了，Diagram是FrameworkElement的派生类，如果把整个家谱变成了一棵元素树，WPF就会自动把这棵树显示出来，但在以前要实现这一点并不容易。

Diagram是根元素，其中可以包含许多DiagramRow，这里的Row其实就等同于树中的层概念，即一行等于一层，在这个程序中看起来应该会很直观，一代人都是在同一行的。而一个DiagramRow中又会有很多DiagramGroup，而一个DiagramGroup中可以包含一个或多个DiagramNode。这里的Group概念略微有些难理解——因为它在每行的定义有些不同，对于primary row，它必定有两个Group，即leftGroup和primaryGroup（primaryGroup位于右侧，个人觉得叫rightGroup也可以），其中primaryGroup放的必定是当前的Family成员，即logic.Family.Current，而leftGroup中放的则是配偶、兄弟（这些都放在一个组中）；而对于非primary row，其算法则有些不同，一行中DiagramGroup的数量是不确定的，还要具体问题具体分析，大家有兴趣的话可以看DiagramLogic.CreateParentRow和DiagramLogic.CreateChildrenRow这两个方法。为了帮助大家理解上面讲的这些概念，下面配一张图例：


看了这张图，大家可能会有一种恍然大悟的感觉——原来这棵树不是从根开始建立的阿，primary row也不是位于第一行的，对咯！这棵树其实是从primary row开始，一层层构建parent row和children row的。所以我们才会看到下面这段代码：

         private   void  UpdateDiagram()
         {

            // Primary row.
            Person primaryPerson = logic.Family.Current;
            DiagramRow primaryRow = logic.CreatePrimaryRow(primaryPerson, 1.0, Const.RelatedMultiplier);
            primaryRow.GroupSpace = Const.PrimaryRowGroupSpace;
            AddRow(primaryRow);



            DiagramRow childRow = primaryRow;
            DiagramRow parentRow = primaryRow;

            while (nodeCount < Const.MaximumNodes && (childRow != null || parentRow != null))
            {
                // Child Row.
                if (childRow != null)
                    childRow = AddChildRow(childRow);

                // Parent row.
                if (parentRow != null)
                {
                    nodeScale *= Const.GenerationMultiplier;
                    parentRow = AddParentRow(parentRow, nodeScale);
                }

                // See if reached node limit yet.                                       
                nodeCount = this.NodeCount;
            }

        }

DiagramLogic有点类似于业务逻辑层，它提供了一些构建这棵树所需要的基本操作，如AddSiblingNodes、AddSpouseNodes、CreateNode，这些方法极大地简化了构建这棵树的难度。那么DiagramLogic和Diagram又是如何关联在一起的呢？Diagram会在构造函数中初始化一个实例化一个DiagramLogic，以后的操作中就会直接用这个叫做logic的DiagramLogic实例来构造这棵树，至于从.family文件读出来的数据则由DiagramLogic直接从App.Family中获得，现在大家知道App.Famliy多么有用了吧。

好了，先写到这，有分析得不对的地方还请大家纠正。