1 /*

     2 * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). 

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 * 

    14 * Description:

    15 *

    16 */

    17 using System;

    18 using System.Xml;

    19 using System.Collections;

    20 using System.Collections.Generic;

    21 

    22 namespace SymbianTree

    23 {

    24 	public abstract class SymNode : IEnumerable<SymNode>

    25 	{

    26 		#region Constructors

    27 		public SymNode()

    28 		{

    29 		}

    30 

    31 		public SymNode( SymNode aParent )

    32 		{

    33 			aParent.AppendChild( this );

    34 		}

    35 

    36 		public SymNode( object aData )

    37 		{

    38 			iData = aData;

    39 		}

    40 

    41 		public SymNode( object aData, SymNode aParent )

    42 		{

    43 			iData = aData;

    44 			aParent.AppendChild( this );

    45 		}

    46 		#endregion

    47 

    48         #region API - siblings

    49         public void InsertBeforeMe( SymNode aNode )

    50 		{

    51 			if	( aNode.HasParent )

    52 			{

    53 				// Ensure that aNode is no longer registered with any existing parent.

    54 				aNode.Parent.RemoveChild( aNode );

    55 			}

    56 

    57 			if	( HasPrevious )

    58 			{

    59 				// Need to link up my previous node with aNode and then

    60 				// link aNode with me

    61 				SymNode p = Previous;

    62 				p.Next = aNode;

    63 				aNode.Previous = p;

    64 			}

    65 			else

    66 			{

    67 				// I didn't have a previous node, so if I am inserting aNode

    68 				// before me, it won't have a previous node either.

    69 				aNode.Previous = null;

    70 			}

    71 

    72 			// Now prepend.

    73 			aNode.Next = this;

    74 			Previous = aNode;

    75 

    76 			// Ensure that my new brother is a child of my parent

    77 			if	( HasParent )

    78 			{

    79 				// Must insert the child at the correct position within 

    80 				// my parents children container. aNode should be

    81 				// inserted before me, i.e. after my *OLD* previous

    82 				// node which is now aNode's previous node (since it

    83 				// now sits in the middle).

    84 				Parent.InsertNodeAfterSpecificChild( aNode, aNode.Previous );

    85 			}

    86 			aNode.Parent = Parent;

    87 		}

    88 

    89 		public void AppendAfterMe( SymNode aNode )

    90 		{

    91 			if	( aNode.HasParent )

    92 			{

    93 				// Ensure that aNode is no longer registered with any existing parent.

    94 				aNode.Parent.RemoveChild( aNode );

    95 			}

    96 

    97 			if	( HasNext )

    98 			{

    99 				// Need to link up my next node with aNode and then

   100 				// link aNode with me

   101 				SymNode n = Next;

   102 				n.Previous = aNode;

   103 				aNode.Next = n;

   104 			}

   105 			else

   106 			{

   107 				// I didn't have a next node, so if I am inserting aNode

   108 				// after me, it won't have a next node either.

   109 				aNode.Next = null;

   110 			}

   111 

   112 			// Now prepend.

   113 			aNode.Previous = this;

   114 			Next = aNode;

   115 

   116 			// Ensure that my new brother is a child of my parent

   117 			if	( HasParent )

   118 			{

   119 				// Must insert the child at the correct position within 

   120 				// my parents children container. aNode should be

   121 				// inserted after me.

   122 				Parent.InsertNodeAfterSpecificChild( aNode, this );

   123 			}

   124 			aNode.Parent = Parent;

   125 		}

   126 

   127 		public void AppendSibling( SymNode aNode )

   128 		{

   129 			#region Example

   130 			// Find the last node in the current sibling branch, 

   131 			// e.g. if we have nodes:

   132 			// 

   133 			//         [A] [B] [C] 

   134 			//

   135 			// and this = [B] and aNode = [X]

   136 			// then we will create the resultant tree consisting of:

   137 			//

   138 			//         [A] [B] [C] [X]

   139 			#endregion

   140 			SymNode insertionPoint = this;

   141 			while( insertionPoint.HasNext )

   142 			{

   143 				insertionPoint = insertionPoint.Next;

   144 			}

   145 

   146 			// Now append.

   147 			insertionPoint.Next = aNode;

   148 			aNode.Previous = insertionPoint;

   149 			aNode.Next = null;

   150 

   151 			// Ensure that my new brother is a child of my parent

   152 			Parent.InsertChild( aNode, this );

   153 		}

   154 

   155 		public void PrependSibling( SymNode aNode )

   156 		{

   157 			#region Example

   158 			// Find the first node in the current sibling branch, 

   159 			// e.g. if we have nodes:

   160 			// 

   161 			//         [A] [B] [C] 

   162 			//

   163 			// and this = [B] and aNode = [X]

   164 			// then we will create the resultant tree consisting of:

   165 			//

   166 			//         [X] [A] [B] [C]

   167 			#endregion

   168 			SymNode insertionPoint = this;

   169 			while( insertionPoint.HasPrevious )

   170 			{

   171 				insertionPoint = insertionPoint.Previous;

   172 			}

   173 

   174 			// Now prepend.

   175 			insertionPoint.Previous = aNode;

   176 			aNode.Next = insertionPoint;

   177 			aNode.Previous = null;

   178 

   179 			// Ensure that my new brother is a child of my parent

   180 			Parent.InsertChild( aNode, null );

   181 		}

   182 

   183 		public void InsertSibling( SymNode aNode, SymNode aAfterNode )

   184 		{

   185 			if	( aAfterNode == null )

   186 			{

   187 				PrependSibling( aNode );

   188 			}

   189 			else

   190 			{

   191 				System.Diagnostics.Debug.Assert( aAfterNode.Parent == Parent );

   192 				System.Diagnostics.Debug.Assert( HasNext || HasPrevious );

   193 				System.Diagnostics.Debug.Assert( DbgCheckNodeIsASibling( aAfterNode ) );

   194 

   195 				#region Example

   196 				// Preconditions:

   197 				// ==============

   198 				// Siblings		= [A] [B] [C]

   199 				// aAfterNode	= [B]

   200 				//    aNode		= [X]

   201 				//

   202 				// Output:

   203 				// =======

   204 				// Siblings		= [A] [B] [X] [C]

   205 				#endregion

   206 

   207 				// We need to ensure that the linkage for

   208 				// B -> X -> C is persisted after the operation.

   209 				//

   210 				// First, obtain [C] by looking at [B]'s next node.

   211 				SymNode nextNode = aAfterNode.Next;

   212 

   213 				// Update [B]'s next node to point to [X]

   214 				aAfterNode.Next = aNode;

   215 

   216 				// Update [X]'s next and previous nodes

   217 				aNode.Previous = aAfterNode; // [B]

   218 				aNode.Next = nextNode; // [C]

   219 

   220 				// Update [C]'s previous node

   221 				nextNode.Previous = aNode;

   222 	

   223 				// Ensure that my new brother is a child of my parent

   224 				Parent.InsertChild( aNode, aAfterNode );

   225 			}

   226 		}

   227 

   228 		public bool SiblingExists( SymNode aNode )

   229 		{

   230 			bool found = false;

   231 			SymNodeEnumeratorSiblings iterator = new SymNodeEnumeratorSiblings( FirstSibling );

   232 			//

   233 			foreach( SymNode node in iterator )

   234 			{

   235 				if	( node == aNode )

   236 				{

   237 					found = true;

   238 					break;

   239 				}

   240 			}

   241 			//

   242 			return found;

   243 		}

   244 

   245 		public bool SiblingTypeExists( System.Type aType )

   246 		{

   247 			bool found = false;

   248 			SymNodeEnumeratorSiblings iterator = new SymNodeEnumeratorSiblings( FirstSibling );

   249 			//

   250 			foreach( SymNode node in iterator )

   251 			{

   252 				if	( node.GetType() == aType )

   253 				{

   254 					found = true;

   255 					break;

   256 				}

   257 			}

   258 			//

   259 			return found;

   260 		}

   261 		#endregion

   262 

   263 		#region API - children

   264 		public void AppendChild( SymNode aChild )

   265 		{

   266 			if	( aChild.HasParent )

   267 			{

   268 				// Ensure that aNode is no longer registered with any existing parent.

   269 				aChild.Parent.RemoveChild( aChild );

   270 			}

   271 

   272 			if	( HasChildren )

   273 			{

   274 				SymNode originalLastChild = LastChild;

   275 				originalLastChild.Next = aChild;

   276 				aChild.Previous = originalLastChild;

   277 			}

   278 			//

   279 			aChild.Parent = this;

   280 			aChild.Next = null;

   281 			Children.Add( aChild );

   282 		}

   283 

   284 		public void PrependChild( SymNode aChild )

   285 		{

   286 			if	( aChild.HasParent )

   287 			{

   288 				// Ensure that aNode is no longer registered with any existing parent.

   289 				aChild.Parent.RemoveChild( aChild );

   290 			}

   291 

   292 			if	( HasChildren )

   293 			{

   294 				SymNode originalFirstChild = FirstChild;

   295 				originalFirstChild.Previous = aChild;

   296 				aChild.Next = originalFirstChild;

   297 			}

   298 			//

   299 			aChild.Parent = this;

   300 			aChild.Previous = null;

   301 			Children.Insert( 0, aChild );

   302 		}

   303 

   304 		public void InsertChild( SymNode aNode, SymNode aAfterNode )

   305 		{

   306 			if	( aAfterNode == null )

   307 			{

   308 				PrependChild( aNode );

   309 			}

   310 			else

   311 			{

   312 				System.Diagnostics.Debug.Assert( aAfterNode.Parent == this );

   313 				System.Diagnostics.Debug.Assert( iChildren != null && iChildren.Count > 0 );

   314 				System.Diagnostics.Debug.Assert( DbgCheckNodeIsAChild( aAfterNode ) );

   315 

   316 				if	( aNode.HasParent )

   317 				{

   318 					// Ensure that aNode is no longer registered with any existing parent.

   319 					aNode.Parent.RemoveChild( aNode );

   320 				}

   321 

   322 				#region Example

   323 				// Input:

   324 				// ======

   325 				// Children		= [A] [B] [C]

   326 				// aAfterNode	= [B]

   327 				//    aNode		= [X]

   328 				//

   329 				// Output:

   330 				// =======

   331 				// Children		= [A] [B] [X] [C]

   332 				#endregion

   333 

   334 				// We need to ensure that the linkage for

   335 				// B -> X -> C is persisted after the operation.

   336 				//

   337 				// First, obtain [C] by looking at [B]'s next node.

   338 				SymNode nextNode = aAfterNode.Next;

   339 

   340 				// Update [B]'s next node to point to [X]

   341 				aAfterNode.Next = aNode;

   342 

   343 				// Update [X]'s next and previous nodes

   344 				aNode.Previous = aAfterNode; // [B]

   345 				aNode.Next = nextNode; // [C]

   346 

   347 				// Update [C]'s previous node

   348 				if	( nextNode != null )

   349 				{

   350 					nextNode.Previous = aNode; // [X]

   351 				}

   352 

   353 				// Ensure child is added to children array at

   354 				// the correct position.

   355 				aNode.Parent = this;

   356 				InsertNodeAfterSpecificChild( aNode, aAfterNode );

   357 			}

   358 		}

   359 

   360         public void RemoveChild( SymNode aChild )

   361 		{

   362 			if	( IsChild( aChild ) )

   363 			{

   364 				int index = ChildIndex( aChild );

   365 				Children.RemoveAt( index );

   366 				aChild.Parent = null;

   367 			}

   368 		}

   369 

   370 		public bool IsChild( SymNode aNode )

   371 		{

   372             bool found = false;

   373             //

   374             if ( iChildren != null )

   375             {

   376                 found = ( ChildIndex( aNode ) >= 0 );

   377             }

   378 			//

   379 			return found;

   380 		}

   381 		

   382 		public int ChildIndex( SymNode aNode )

   383 		{

   384             int index = iChildren.IndexOf( aNode );

   385 			return index;

   386 		}

   387 

   388 		public bool ChildTypeExists( System.Type aType )

   389 		{

   390 			bool found = false;

   391 			SymNodeEnumeratorChildren iterator = new SymNodeEnumeratorChildren( this );

   392 			//

   393 			foreach( SymNode node in iterator )

   394 			{

   395 				if	( node.GetType() == aType )

   396 				{

   397 					found = true;

   398 					break;

   399 				}

   400 			}

   401 			//

   402 			return found;

   403 		}

   404 

   405 		public object ChildByType( System.Type aType )

   406 		{

   407 			object ret = null;

   408 			SymNodeEnumeratorChildren iterator = new SymNodeEnumeratorChildren( this );

   409 			//

   410 			foreach( SymNode node in iterator )

   411 			{

   412 				if	( node.GetType() == aType )

   413 				{

   414 					ret = node;

   415 					break;

   416 				}

   417 			}

   418 			//

   419 			return ret;

   420 		}

   421 

   422 		public object ChildByType( System.Type aType, ref int aStartIndex )

   423 		{

   424 			object ret = null;

   425 			int count = iChildren.Count;

   426 			for(; aStartIndex<count; aStartIndex++ )

   427 			{

   428 				SymNode node = (SymNode) iChildren[ aStartIndex ];

   429 				//

   430 				if	( node.GetType() == aType )

   431 				{

   432 					ret = node;

   433 					break;

   434 				}

   435 			}

   436 			//

   437 			return ret;

   438 		}

   439 

   440 		public int ChildCountByType( System.Type aType )

   441 		{

   442 			int count = 0;

   443 			SymNodeEnumeratorChildren iterator = new SymNodeEnumeratorChildren( this );

   444 			//

   445 			foreach( SymNode node in iterator )

   446 			{

   447 				System.Type type = node.GetType();

   448 				//

   449 				bool isInstanceOf = type.IsInstanceOfType( aType );

   450 				bool isSubClassOf = type.IsSubclassOf( aType );

   451 				bool isSameType = type.Equals( aType );

   452 				//

   453 				if	( isInstanceOf || isSubClassOf || isSameType )

   454 				{

   455 					++count;

   456 				}

   457 			}

   458 			//

   459 			return count;

   460 		}

   461 		#endregion

   462 

   463 		#region API - copying / moving

   464 		public void AppendChildrenFrom( SymNode aNode )

   465 		{

   466 			while( aNode.HasChildren )

   467 			{

   468 				SymNode childToMove = aNode[ 0 ];

   469 				AppendChild( childToMove );

   470 			}

   471 		}

   472 

   473 		public void InsertChildrenFrom( SymNode aNode, SymNode aChildToInsertAfter )

   474 		{

   475 			while( aNode.HasChildren )

   476 			{

   477 				SymNode childToMove = aNode.LastChild;

   478 				InsertChild( childToMove, aChildToInsertAfter );

   479 			}

   480 		}

   481 		#endregion

   482 

   483 		#region API - removing from tree

   484 		public void Remove()

   485 		{

   486 			// Need to tidy up siblings

   487 			if	( HasPrevious )

   488 			{

   489 				SymNode p = Previous;

   490 				p.Next = Next;

   491 			}

   492 			if	( HasNext )

   493 			{

   494 				SymNode n = Next;

   495 				n.Previous = Previous;

   496 			}

   497 

   498 			// Need to unregister from parent

   499 			if	( HasParent )

   500 			{

   501 				Parent.RemoveChild( this );

   502 			}

   503 		}

   504 

   505 		public virtual void Replace( SymNode aReplacement )

   506 		{

   507 			InsertBeforeMe( aReplacement );

   508 			Remove();

   509 		}

   510 		#endregion

   511 

   512         #region API - adding to tree

   513         public abstract void Add( SymNode aNode );

   514 		#endregion

   515 

   516         #region API - XML

   517         protected virtual string XmlNodeName

   518         {

   519             get { return this.GetType().ToString(); }

   520         }

   521 

   522         protected virtual void Serialize( XmlWriter aSink )

   523         {

   524             string nodeName = XmlNodeName;

   525             //

   526             aSink.WriteStartElement( null, nodeName, null );

   527             SerializeChildren( aSink );

   528             aSink.WriteEndElement();

   529         }

   530 

   531         protected virtual void SerializeChildren( XmlWriter aSink )

   532         {

   533             SymNodeEnumeratorChildren iterator = new SymNodeEnumeratorChildren( this );

   534             foreach ( SymNode node in iterator )

   535             {

   536                 node.Serialize( aSink );

   537             }

   538         }

   539         #endregion

   540 

   541 		#region Properties - data

   542 		public object Data

   543 		{

   544 			get { return iData; }

   545 			set { iData = value; }

   546 		}

   547 		#endregion

   548 

   549 		#region Properties - parents, root, depth

   550 		public SymNode Parent

   551 		{

   552 			get { return iParent; }

   553 			set { iParent = value; }

   554 		}

   555 

   556 		public SymNode Root

   557 		{

   558 			get

   559 			{

   560 				SymNode node = this;

   561 				while( node.HasParent )

   562 				{

   563 					node = node.Parent;

   564 				}

   565 				//

   566 				return node;

   567 			}

   568 		}

   569 

   570 		public int Depth

   571 		{

   572 			get

   573 			{

   574 				int depth = 0;

   575 				//

   576 				SymNode node = this;

   577 				while( node.HasParent )

   578 				{

   579 					node = node.Parent;

   580 					++depth;

   581 				}

   582 				//

   583 				return depth;

   584 			}

   585 		}

   586 		#endregion

   587 

   588 		#region Properties - children

   589 		public List<SymNode> Children

   590 		{

   591 			get

   592 			{

   593 				if	( iChildren == null )

   594 				{

   595                     CreateChildrenListNow( Granularity );

   596 				}

   597                 //

   598 				return iChildren;

   599 			}

   600 		}

   601 

   602         public SymNode FirstChild

   603 		{

   604 			get

   605 			{

   606 				SymNode ret = null;

   607 				//

   608 				if	( iChildren != null && iChildren.Count > 0 )

   609 				{

   610 					ret = iChildren[ 0 ];

   611 				}

   612 				//

   613 				return ret;

   614 			}

   615 		}

   616 

   617 		public SymNode LastChild

   618 		{

   619 			get

   620 			{

   621 				SymNode ret = null;

   622 				//

   623                 if ( iChildren != null && iChildren.Count > 0 )

   624 				{

   625                     ret = iChildren[ iChildren.Count - 1 ];

   626 				}

   627 				//

   628 				return ret;

   629 			}

   630 		}

   631 

   632 		public int ChildCount

   633 		{

   634 			get

   635             {

   636                 int count = 0;

   637                 //

   638                 if ( iChildren != null )

   639                 {

   640                     count = Children.Count;

   641                 }

   642                 //

   643                 return count;

   644             }

   645 		}

   646 

   647 		public SymNode this[ int aIndex ]

   648 		{

   649 			get

   650 			{

   651 				return iChildren[ aIndex ];

   652 			}

   653 		}

   654 		#endregion

   655 

   656 		#region Properties - siblings

   657 		public SymNode Next

   658 		{

   659 			get { return iNext; }

   660 			set { iNext = value; }

   661 		}

   662 

   663 		public SymNode Previous

   664 		{

   665 			get { return iPrevious; }

   666 			set { iPrevious = value; }

   667 		}

   668 

   669 		public SymNode FirstSibling

   670 		{

   671 			get

   672 			{

   673 				SymNode sibling = this;

   674 				while( sibling.HasPrevious )

   675 				{

   676 					sibling = sibling.Previous;

   677 				}

   678 				//

   679 				return sibling;

   680 			}

   681 		}

   682 

   683 		public SymNode LastSibling

   684 		{

   685 			get

   686 			{

   687 				SymNode sibling = this;

   688 				while( sibling.HasNext )

   689 				{

   690 					sibling = sibling.Next;

   691 				}

   692 				//

   693 				return sibling;

   694 			}

   695 		}

   696 

   697         public int SiblingCount

   698 		{

   699 			get

   700 			{

   701 				int count = 1;

   702 			

   703 				// Work backwards first

   704 				SymNode node = this;

   705 				while( node.HasPrevious )

   706 				{

   707 					node = node.Previous;

   708 					++count;

   709 				}

   710 

   711 				// Try all nodes after the current one

   712 				node = this;

   713 				while( node.HasNext )

   714 				{

   715 					node = node.Next;

   716 					++count;

   717 				}

   718 

   719 				return count;

   720 			}

   721 		}

   722 		#endregion

   723 

   724 		#region Properties - relationships

   725 		public bool IsRoot

   726 		{

   727 			get { return Parent == null; }

   728 		}

   729 

   730 		public bool HasParent

   731 		{

   732 			get { return iParent != null; }

   733 		}

   734 

   735 		public bool HasNext

   736 		{

   737 			get { return iNext != null; }

   738 		}

   739 

   740 		public bool HasPrevious

   741 		{

   742 			get { return iPrevious != null; }

   743 		}

   744 

   745 		public bool HasChildren

   746 		{

   747 			get { return ( iChildren != null && iChildren.Count > 0 ); }

   748 		}

   749 		#endregion

   750 

   751         #region Properties - misc

   752         public static int Granularity

   753         {

   754             get { return iGranularity; }

   755             set { iGranularity = value; }

   756         }

   757         #endregion

   758 

   759         #region IEnumerable Members

   760         IEnumerator IEnumerable.GetEnumerator()

   761 		{

   762 			return new SymNodeEnumeratorChildren( this );

   763 		}

   764 

   765         IEnumerator<SymNode> IEnumerable<SymNode>.GetEnumerator()

   766         {

   767             return new SymNodeEnumeratorChildren( this );

   768         }

   769         #endregion

   770 

   771 		#region Internal constants

   772 		const int KSymNodeDefaultChildrenGranularity = 10;

   773 		#endregion

   774 

   775 		#region Internal methods

   776         protected void CreateChildrenListNow( int aGranularity )

   777         {

   778             iChildren = new List<SymNode>( aGranularity );

   779         }

   780 

   781 		private void InsertNodeAfterSpecificChild( SymNode aNode, SymNode aAfterNode )

   782 		{

   783 			int index = 0;

   784 			//

   785 			if	( aAfterNode != null )

   786 			{

   787 				System.Diagnostics.Debug.Assert( DbgCheckNodeIsAChild( aAfterNode ) );

   788 				index = ChildIndex( aAfterNode );

   789 			}

   790 			//

   791 			iChildren.Insert( index + 1, aNode );

   792 			aNode.Parent = this;

   793 		}

   794 		#endregion

   795 

   796 		#region Debug checks

   797 		private bool DbgCheckNodeIsAChild( SymNode aNode )

   798 		{

   799 			System.Diagnostics.Debug.Assert( aNode != this );

   800 			System.Diagnostics.Debug.Assert( iChildren != null && iChildren.Count > 0 );

   801 

   802 			int index = ChildIndex( aNode );

   803 			if	( index < 0 || index >= ChildCount )

   804 			{

   805 				System.Diagnostics.Debug.Assert( false, "The specified node is not a child of the current node" );

   806 			}

   807 			return (index >= 0 && index < ChildCount );

   808 		}

   809 

   810 		private bool DbgCheckNodeIsASibling( SymNode aNode )

   811 		{

   812 			System.Diagnostics.Debug.Assert( aNode != this );

   813 			System.Diagnostics.Debug.Assert( HasNext || HasPrevious );

   814 			

   815 			// Work backwards first

   816 			SymNode node = this;

   817 			while( node.HasPrevious )

   818 			{

   819 				node = node.Previous;

   820 				if	( node == aNode )

   821 				{

   822 					return true;

   823 				}

   824 			}

   825 

   826 			// Try all nodes after the current one

   827 			node = this;

   828 			while( node.HasNext )

   829 			{

   830 				node = node.Next;

   831 				if	( node == aNode )

   832 				{

   833 					return true;

   834 				}

   835 			}

   836 

   837 			System.Diagnostics.Debug.Assert( false, "The specified node is not a sibling of the current node" );

   838 			return false;

   839 		}

   840 		#endregion

   841 

   842 		#region Data members

   843         private object iData;

   844         private SymNode iParent;

   845 		private SymNode iNext;

   846 		private SymNode iPrevious;

   847         private List<SymNode> iChildren;

   848         private static int iGranularity = KSymNodeDefaultChildrenGranularity;

   849         #endregion

   850 	}

   851 }