Exercise 4: Solution

Parser.cs:

using System;
using System.Collections.Generic;
using System.Text;

namespace Plato.Core.Parser
{
    /// <summary>
    /// Parses textual statements and updates the core data structure.
    /// </summary>
    public class Parser
    {
        Brain brain;

        public Parser(Brain brain)
        {
            this.brain = brain;
        }

        /// <summary>
        /// Parse the lines of input into the core data structure.
        /// </summary>
        /// <param name="str">The text input.</param>
        /// <param name="brain">The core data structure.</param>
        public void Parse(string str)
        {
            string[] lines = str.Split('\n');

            // Process each line of input
            int lineNum = 0;
            foreach (string line in lines)
            {
                ++lineNum;
                line.Trim();

                if (String.IsNullOrEmpty(line))
                {
                    continue;
                }

                string[] tokens = line.Split(new char[] { ' ' },
                                             StringSplitOptions.RemoveEmptyEntries);

                try
                {
                    if (tokens.Length == 1)
                    {
                        // {entity}
                        ParseEntity(tokens[0]);
                    }
                    else if (tokens.Length == 3 &&
                             tokens[1] == "=")
                    {
                        // {enitity1}.{entity2} = {entity4}
                        // ie. object.parameter = value
                        ParseAssignment(tokens);
                    }
                    else if (tokens.Length == 3)
                    {
                        // {entity1} {relation} {entity2}
                        ParseRelationship(tokens, true);
                    }
                    else
                    {
                        throw new Exception(String.Format("Line {0}: Unrecognized input: {1}",
                                                          lineNum, line));
                    }
                }
                catch(Exception e)
                {
                    throw new Exception(String.Format("Line {0}: {1}", lineNum, e.Message));
                }
            }
        }

        /// <summary>
        /// Parse the entity and update the core data structure.
        /// </summary>
        /// <param name="id">The internal ID of the new entity.</param>
        public void ParseEntity(string id)
        {
            IEntity existingEntity = brain.Get(id);
            if (existingEntity != null)
            {
                throw new Exception(String.Format("The entity [{0}] already exists", id));
            }
            else
            {
                brain.CreateEntity(id);
            }
        }

        /// <summary>
        /// Parse the relationship and update the core data structure.
        /// </summary>
        /// <param name="tokens">The list of tokens.</param>
        /// <param name="brain">The core data structure.</param>
        public void ParseRelationship(string[] tokens, bool createEntities)
        {
            IEntity entity1 = brain.Get(tokens[0]);
            if (entity1 == null)
            {
                if (createEntities)
                {
                    brain.CreateEntity(tokens[0]);
                    entity1 = brain.Get(tokens[0]);
                }
                else
                {
                    throw new Exception(String.Format("Unrecognized entity [{0}]", tokens[0]));
                }
            }

            IEntity relation = brain.Get(tokens[1]);
            if (relation == null)
            {
                if (createEntities)
                {
                    brain.CreateEntity(tokens[1]);
                    relation = brain.Get(tokens[1]);
                }
                else
                {
                    throw new Exception(String.Format("Unrecognized entity [{0}]", tokens[1]));
                }
            }

            IEntity entity2 = brain.Get(tokens[2]);
            if (entity2 == null)
            {
                if (createEntities)
                {
                    brain.CreateEntity(tokens[2]);
                    entity2 = brain.Get(tokens[2]);
                }
                else
                {
                    throw new Exception(String.Format("Unrecognized entity [{0}]", tokens[2]));
                }
            }

            brain.CreateRelationship(entity1, relation, entity2);
        }

        /// <summary>
        /// Parse the assignment and update the core data structure.
        /// </summary>
        /// <param name="tokens">The list of tokens.</param>
        /// <param name="brain">The core data structure.</param>
        public void ParseAssignment(string[] tokens)
        {
            string[] parts = tokens[0].Split('.');

            IEntity obj1 = brain.Get(parts[0]);
            if (obj1 == null)
            {
                throw new Exception(String.Format("Unrecognized entity [{0}]", parts[0]));
            }

            // Ensure implied "has_a" relationships exist.
            IEntity obj2 = null;
            for (int i = 1; i < parts.Length; ++i)
            {
                obj2 = brain.Get(parts[i]);
                if (obj2 == null)
                {
                    throw new Exception(String.Format("Unrecognized entity [{0}]", parts[i]));
                }

                // Ensure a "has_a" relationship exists between these entities.
                if (!obj1.HasA(obj2))
                {
                    throw new Exception(String.Format("has_a relationship doesn't exist " +
                                                      "between entities [{0}] and [{1}]",
                                                      parts[i-1], parts[i]));
                }

                if (i != parts.Length - 1)
                {
                    obj1 = obj2;
                }
            }

            IEntity obj = obj1;
            IEntity property = obj2;

            IEntity value = brain.Get(tokens[2]);
            if (value == null)
            {
                throw new Exception(String.Format("Unrecognized entity [{0}]", tokens[2]));
            }

            // TODO: Ensure types are valid

            obj.Set(property, value);
        }
    }
}

Brain.cs:

using System;
using System.Collections.Generic;
using System.Text;

namespace Plato.Core
{
    /// <summary>
    /// The set of entities.
    /// </summary>
    public class Brain
    {
        // The set of entities.
        private Dictionary<string, Entity> entities;

        public Brain()
        {
            entities = new Dictionary<string, Entity>();
        }

        /// <summary>
        /// Create/add a new entity.
        /// </summary>
        /// <param name="id">The entity's internal ID.</param>
        /// <returns>The new entity.</returns>
        public IEntity CreateEntity(string id)
        {
            if (entities.ContainsKey(id))
            {
                throw new Exception(String.Format("Entity [{0}] already exists.", id));
            }

            Entity newEntity = new Entity(id);
            entities.Add(id, newEntity);

            return newEntity;
        }

        /// <summary>
        /// Returns an entity given its ID.
        /// </summary>
        /// <param name="id">The entity's internal ID.</param>
        /// <returns>The entity, or null if not found.</returns>
        public IEntity Get(string id)
        {
            if (!entities.ContainsKey(id))
            {
                return null;
            }

            return entities[id];
        }

        /// <summary>
        /// Create/add a new relationship.
        /// </summary>
        /// <param name="entity1">The first entity.</param>
        /// <param name="entity2">The second entity.</param>
        /// <param name="relation">Defines how the entities are related.</param>
        /// <param name="args">Optional argument entities.</param>
        /// <param name="directed">Whether or not the relationship is directed.</param>
        /// <returns>The new relationship.</returns>
        public IRelationship CreateRelationship(IEntity entity1, IEntity relation,
                                                IEntity entity2, IEntity[] args,
                                                bool directed)
        {
            Relationship newRelationship = new Relationship(entity1, relation, entity2,
                                                            args, directed);
            entity1.AddRelationship(newRelationship);
            return newRelationship;
        }

        public IRelationship CreateRelationship(IEntity entity1, IEntity relation,
                                                IEntity entity2, bool directed)
        {
            return CreateRelationship(entity1, relation, entity2, null, directed);
        }

        public IRelationship CreateRelationship(IEntity entity1, IEntity relation,
                                                IEntity entity2)
        {
            return CreateRelationship(entity1, relation, entity2, null, true);
        }

        public IRelationship CreateRelationship(IEntity entity1, IEntity relation,
                                                IEntity entity2, IEntity[] args)
        {
            return CreateRelationship(entity1, relation, entity2, args, true);
        }
    }

    /// <summary>
    /// An entity.
    /// </summary>
    internal class Entity : IEntity
    {
        private string id;

        // Relationships, organized by target entity.
        private Dictionary<string, List<IRelationship>> relatedEntities;

        // Relationships, organized by relation type.
        private Dictionary<string, List<IRelationship>> relationTypes;

        // Values which have been assigned to properties
        private Dictionary<string, List<IEntity>> values;

        public Entity(string id)
        {
            this.id = id;
            this.values = new Dictionary<string, List<IEntity>>();
            this.relatedEntities = new Dictionary<string, List<IRelationship>>();
            this.relationTypes = new Dictionary<string, List<IRelationship>>();
        }

        public override string ToString()
        {
            return id;
        }

        /// <summary>
        /// The ID by which the entity is internally referenced.
        /// </summary>
        public string Id
        {
            get { return id; }
            set { id = value; }
        }

        /// <summary>
        /// Add a relationship between this entity and another entity.
        /// </summary>
        /// <param name="relationship">The relationship.</param>
        public void AddRelationship(IRelationship relationship)
        {
            if (relationship.Entity1.Id != this.id)
            {
                throw new ArgumentException("The relationship's source entity " +
                                            "doesn't match this entity.");
            }

            List<IRelationship> list;
            string entity2 = relationship.Entity2.Id;
            string relationType = relationship.Relation.Id;

            // Update relationships, ordered by target entity and
            // relation type.

            if (relatedEntities.ContainsKey(entity2))
            {
                // One or more relationships already exist with this
                // entity. Add the new relationship.
                relatedEntities[entity2].Add(relationship);
            }
            else
            {
                // No relationships yet exist with this entity.
                // Add this first relationship.
                list = new List<IRelationship>();
                list.Add(relationship);
                relatedEntities[entity2] = list;
            }

            if (relationTypes.ContainsKey(relationType))
            {
                // One or more relationships already exist for this
                // relation type. Add the new relationship.
                relationTypes[relationType].Add(relationship);
            }
            else
            {
                // No relationships yet exist for this relation type.
                // Add this first relationship.
                list = new List<IRelationship>();
                list.Add(relationship);
                relationTypes[relationType] = list;
            }
        }

        /// <summary>
        /// Assign a value to a property.
        /// </summary>
        /// <param name="property">The property.</param>
        /// <param name="value">The value.</param>
        public void Set(IEntity property, IEntity value)
        {
            if (!HasA(property))
            {
                throw new PropertyNotFoundException(
                    String.Format("Entity [{0}] does not have property [{1}].",
                        Id, property.Id),
                    this, property);
            }

            List<IEntity> list = new List<IEntity>();
            list.Add(value);

            // Overwrite any existing value
            values[property.Id] = list;
        }

        /// <summary>
        /// Get a property's value.
        /// </summary>
        /// <param name="property">The property.</param>
        /// <returns>The value if set, or null otherwise.</returns>
        public IEntity Get(IEntity property)
        {
            if (!HasA(property))
            {
                throw new PropertyNotFoundException(
                    String.Format("Entity [{0}] does not have property [{1}].",
                        Id, property.Id),
                    this, property);
            }

            if (values.ContainsKey(property.Id))
            {
                return values[property.Id][0];
            }
            else
            {
                return null;
            }
        }

        /// <summary>
        /// Perform a depth-first search on is_a relationships to determine whether
        /// an entity has a direct or indirect is_a relationship with another entity.
        /// </summary>
        /// <param name="type">The type.</param>
        /// <returns>True if the relationship exists.</returns>
        public bool IsA(IEntity type)
        {
            if (Id == type.Id)
            {
                return true;
            }
            else
            {
                // Depth-first, recursive search
                foreach (List<IRelationship> relationshipList in relatedEntities.Values)
                {
                    foreach (IRelationship relationship in relationshipList)
                    {
                        if (relationship.Relation.Id == "is_a")
                        {
                            if (relationship.Entity2.IsA(type))
                            {
                                return true;
                            }
                        }
                    }
                }
            }

            return false;
        }

        /// <summary>
        /// Perform a depth-first search on the is_a relationship followed by
        /// a depth of one search of the has_a relationship.
        /// </summary>
        /// <param name="type">The property.</param>
        /// <returns>True if the relationship exists.</returns>
        public bool HasA(IEntity property)
        {
            // If an immediate relationship does not exist, consider
            // the has_a relationships of is_a relatives.
            if (ImmediateHasA(property))
            {
                return true;
            }

            // Otherwise, consider has_a relationships of is_a
            // relatives.

            // Depth-first, recursive search
            foreach (List<IRelationship> relationshipList in relatedEntities.Values)
            {
                foreach (IRelationship relationship in relationshipList)
                {
                    if (relationship.Relation.Id == "is_a")
                    {
                        if (relationship.Entity2.ImmediateHasA(property))
                        {
                            return true;
                        }
                    }
                }
            }

            return false;
        }

        /// <summary>
        /// Examine this entity's immediate has_a relationships.
        /// </summary>
        /// <param name="entity">The entity.</param>
        /// <returns>True if the relationship exists.</returns>
        public bool ImmediateHasA(IEntity property)
        {
            if (relationTypes.ContainsKey("has_a"))
            {
                List<IRelationship> relationshipList = relationTypes["has_a"];

                foreach (IRelationship relationship in relationshipList)
                {
                    if (relationship.Entity2.Id == property.Id)
                    {
                        return true;
                    }
                }
            }

            return false;
        }
    }

    /// <summary>
    /// A relationship.
    /// </summary>
    internal class Relationship : Entity, IRelationship
    {
        // The 'source' entity
        private IEntity entity1;

        // The target entity
        private IEntity entity2;

        private IEntity relation;
        private IEntity[] args;
        private bool directed;

        public Relationship(IEntity entity1, IEntity relation, IEntity entity2,
                            IEntity[] args)
            : base(null)
        {
            if (entity1 == null)
            {
                throw new ArgumentNullException("entity1");
            }
            if (entity2 == null)
            {
                throw new ArgumentNullException("entity2");
            }
            if (relation == null)
            {
                throw new ArgumentNullException("relation");
            }

            this.entity1 = entity1;
            this.entity2 = entity2;
            this.relation = relation;
            this.args = args;
            directed = true;

            // Create a reference from the first entity
            // to this relationship.
            entity1.AddRelationship(this);

        }

        public Relationship(IEntity entity1, IEntity relation, IEntity entity2,
                            IEntity[] args, bool directed)
            : this(entity1, relation, entity2, args)
        {
            this.directed = directed;
        }

        public override string ToString()
        {
            return entity1.Id + " " + relation.Id + " " + entity2.Id;
        }

        /// <summary>
        /// The first entity of the relationship.
        /// </summary>
        public IEntity Entity1
        {
            get { return entity1; }
        }

        /// <summary>
        /// The second Entity of the relationship.
        /// </summary>
        public IEntity Entity2
        {
            get { return entity2; }
        }

        /// <summary>
        /// The relation defines how the two entities relate.
        /// </summary>
        public IEntity Relation
        {
            get { return relation; }
        }

        /// <summary>
        /// Optional entity arguments.
        /// </summary>
        public IEntity[] Args
        {
            get { return args; }
        }

        /// <summary>
        /// Is the relationship directed?
        /// </summary>
        public bool Directed
        {
            get { return directed; }
        }
    }

    public class PropertyNotFoundException : Exception
    {
        private IEntity entity;
        private IEntity property;

        public PropertyNotFoundException(string message, IEntity entity, IEntity property)
            :base(message)
        {
            this.entity = entity;
            this.property = property;
        }

        /// <summary>
        /// The entity to which the property was said to belong.
        /// </summary>
        public IEntity Entity
        {
            get { return entity; }
        }

        /// <summary>
        /// The property.
        /// </summary>
        public IEntity Property
        {
            get { return property; }
        }
    }

}