//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        static string buffer = "";
        static int cacheMisses = 0;
        const int numberOfValuesCached = 4;
        const int maxNumberOf32BitsElements = 16; // 64B L1 cache
        
        class MemoryThing
        {
        }
        
        class Float : MemoryThing
        {
            private readonly float value;
            
            public Float(float value)
            {
                this.value = value;
            }

            public static implicit operator Float(float value)
            {
                return new Float(value);
            }

            public static Float operator +(Float first, Float second)
            {
                return new Float(first.value + second.value);
            }

            public static Float operator -(Float first, Float second)
            {
                return new Float(first.value - second.value);
            }
            
            public override string ToString()
            {
                return "{" + value + "}";
            }
        }
        
        class Int : MemoryThing
        {
            private readonly int value;
            
            public Int(int value)
            {
                this.value = value;
            }

            public static implicit operator Int(int value)
            {
                return new Int(value);
            }

            public static Int operator +(Int first, Int second)
            {
                return new Int(first.value + second.value);
            }

            public static Int operator -(Int first, Int second)
            {
                return new Int(first.value - second.value);
            }
            
            public override string ToString()
            {
                return "{" + value + "}";
            }
        }
        
        class Entity : MemoryThing
        {
            public Float x, y;
            public Int sprite;
            
            public Entity(float x, float y, int sprite)
            {
                this.x = x;
                this.y = y;
                this.sprite = sprite;
            }
            
            public override string ToString()
            {
                return  x.ToString() + y.ToString() + sprite.ToString();
            }
        }
        
        class Position : MemoryThing
        {
            public Float x, y;
            
            public Position(float x, float y)
            {
                this.x = x;
                this.y = y;
            }
            
            public override string ToString()
            {
                return  x.ToString() + y.ToString();
            }
        }
        
        class Entities
        {
            public List<MemoryThing> positions = new List<MemoryThing>();
            public List<MemoryThing> sprites = new List<MemoryThing>();
            
            public void NewEntity(float x, float y, int sprite)
            {
                positions.Add(new Position(x,y));
                sprites.Add(new Int(sprite));
            }
        }
        
        static void StoreValueInMemory(List<MemoryThing> objects, int pos)
        {
            // Add new values
            int cachedValues = 0;
            for(int i = pos; i < objects.Count; ++i)
            {
                string values = objects[i].ToString();

                int numValues = values.Count(f => f == '{');
                while(cachedValues < numberOfValuesCached)
                {
                    int indexToCopyTo = values.IndexOf('}');
                    if(indexToCopyTo >= 0)
                    {
                        string newValue = values.Substring(0, indexToCopyTo + 1);
                        if(buffer.IndexOf(newValue) < 0)
                        {
                            buffer += newValue;
                            cachedValues++;
                        }
                        values = values.Substring(indexToCopyTo + 1);
                    }
                    else
                    {
                        break;
                    }
                }
                
                if(cachedValues >= numberOfValuesCached)
                {
                    break;
                }
            }
            
            int count = buffer.Count(f => f == '{');

            while(count > maxNumberOf32BitsElements)
            {
                // Remove oldest values
                int indexToDeleteTo = buffer.IndexOf('}');
                if(indexToDeleteTo >= 0)
                {
                    buffer = buffer.Substring(indexToDeleteTo + 1);
                    count--;
                }
                else
                {
                    break;
                }
            }
            
            Console.WriteLine(string.Format("Stored in memory   : {0}", buffer));
        }
        
        static void GetValueInMemory(List<MemoryThing> objects, int pos)
        {
            MemoryThing yourObject = objects[pos];
            string values = yourObject.ToString();
            int numValues = values.Count(f => f == '{');
            
            for(int i = 0; i < numValues; ++i)
            {
                int indexToCopyTo = values.IndexOf('}');
                if(indexToCopyTo >= 0)
                {
                    string newValue = values.Substring(0, indexToCopyTo + 1);
                    if(buffer.IndexOf(newValue) != -1)
                    {
                        // Keep less recently used at the beginning and the most recently used at the end of the list
                        //buffer = buffer.Replace(newValue,"");
                        //buffer += newValue;

                        values = values.Substring(indexToCopyTo + 1);
                        
                        //Console.WriteLine(string.Format("Found in memory    : {0}", newValue));
                    }
                    else
                    {
                        //Console.WriteLine(string.Format("Not found in memory: {0}", newValue));
                        cacheMisses++;

                        StoreValueInMemory(objects, pos);
                    }
                }
                else
                {
                    break;
                }
            }
        }
        
        public static void Main(string[] args)
        {
            
            int numberOfEntities = 10;
            List<MemoryThing> entities = new List<MemoryThing>();
            for(int i = 0; i < numberOfEntities; ++i)
            {
                entities.Add(new Entity((float)i + 10000.0f , (float)i + 200000.0f, i));
            }
            
            // Lets say we update the positions...
            for(int i = 0; i < numberOfEntities; ++i)
            {
                GetValueInMemory(entities, i);
            }
                
            // ... and somewhere else in the code we increment the frame for their animation
            for(int i = 0; i < numberOfEntities; ++i)
            {
                GetValueInMemory(entities, i);
            }

            Console.WriteLine(string.Format("Number of cache misses for OOP: {0}", cacheMisses));
            
            cacheMisses = 0;
            buffer = "";
            Entities DoDEntities = new Entities();
            for(int i = 0; i < numberOfEntities; ++i)
            {
                DoDEntities.NewEntity((float)i + 10000.0f , (float)i + 200000.0f, i);
            }
            
            // Lets say we update the positions...
            for(int i = 0; i < numberOfEntities; ++i)
            {
                GetValueInMemory(DoDEntities.positions, i);
            }
                
            // ... and somewhere else in the code we increment the frame for their animation
            for(int i = 0; i < numberOfEntities; ++i)
            {
                GetValueInMemory(DoDEntities.sprites, i);
            }

            Console.WriteLine(string.Format("Number of cache misses for DOD: {0}", cacheMisses));
        }
    }
}