FixedSizeLinkedList.cs

/*
FixedSizeLinkedList.cs

UPLOADED HERE FOR DEBUGGING PURPOSE ONLY!!

Description: A linkedlist that has a fixed size. When the list is full, adding item removes previous item (based on eviction policy).
Author: Yu Long
Created: Saturday, February 04 2023
Unity Version: 2021.3.3f1
Contact: long_yu@berkeley.edu
*/

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

namespace Reimirno
{
    public enum FixedSizeLinkedListEvictionPolicy
    {
        FIFO,
        FILO,
        LRU,
        Clock,
        MRU,
    }

    public class FixedSizeLinkedList<T> : ICollection<T>
    {
        private FixedSizeLinkedListEvictionPolicy evictionPolicy;
        private int capacity;
        private readonly LinkedList<T> list;
        private readonly Dictionary<T, LinkedListNode<T>> dict;

        public FixedSizeLinkedList(int capacity, FixedSizeLinkedListEvictionPolicy evictionPolicy)
        {
            this.capacity = capacity;
            this.evictionPolicy = evictionPolicy;
            list = new LinkedList<T>();
            dict = new Dictionary<T, LinkedListNode<T>>();
        }

        public void Add(T item)
        {
            //Check repeat
            if (dict.ContainsKey(item))
            {
                switch (evictionPolicy)
                {
                    case FixedSizeLinkedListEvictionPolicy.FIFO:
                    case FixedSizeLinkedListEvictionPolicy.FILO:
                        // Don't care about repeat, don't account for use frequency in FIFO and FILO
                        return;
                    case FixedSizeLinkedListEvictionPolicy.LRU:
                        // Remove the old one; later, the new one will be added to the end of the list
                        PlaceToBack(item);
                        break;
                    case FixedSizeLinkedListEvictionPolicy.Clock:
                    case FixedSizeLinkedListEvictionPolicy.MRU:
                        throw new NotImplementedException("Not implemented yet");
                    default:
                        throw new ArgumentException("Invalid eviction policy");
                }
            }

            // //Check capacity
            // ControlCapacity();

            // Actually add
            if (!dict.ContainsKey(item))
            {
                switch (evictionPolicy)
                {
                    case FixedSizeLinkedListEvictionPolicy.FIFO:
                    case FixedSizeLinkedListEvictionPolicy.FILO:
                    case FixedSizeLinkedListEvictionPolicy.LRU:
                        dict.Add(item, list.AddLast(item));
                        break;
                    case FixedSizeLinkedListEvictionPolicy.Clock:
                    case FixedSizeLinkedListEvictionPolicy.MRU:
                        throw new NotImplementedException("Not implemented yet");
                    default:
                        throw new ArgumentException("Invalid eviction policy");
                }
            }

            ControlCapacity();

            OnAddOrRefresh(item);
        }

        public void AddRange(IEnumerable<T> items)
        {
            foreach (T i in items)
            {
                Add(i);
            }
        }

        public bool Remove(T item)
        {
            if (dict.ContainsKey(item))
            {
                list.Remove(dict[item]);
                dict.Remove(item);
                OnRemove(item);
                return true;
            }
            return false;
        }

        public void PlaceToBack(T item)
        {
            if (dict.ContainsKey(item))
            {
                list.Remove(dict[item]);
                dict[item] = list.AddLast(item);
            }
        }

        public T MoveFrontToBack()
        {
            T item = Front;
            PlaceToBack(item);
            return item;
        }

        public void RemoveRange(IEnumerable<T> items)
        {
            foreach (T i in items)
            {
                Remove(i);
            }
        }

        public T PopFront()
        {
            T item = Front;
            Remove(item);
            return item;
        }

        public T PopBack()
        {
            T item = Back;
            Remove(item);
            return item;
        }

        protected virtual void OnAddOrRefresh(T item) { }

        protected virtual void OnRemove(T item) { }

        public void Clear()
        {
            list.Clear();
            dict.Clear();
        }

        public bool Contains(T item)
        {
            return dict.ContainsKey(item);
        }

        public bool SetCapacity(int newCapacity)
        {
            if (newCapacity <= 0)
            {
                return false;
            }
            capacity = newCapacity;
            ControlCapacity();
            return true;
        }

        private void ControlCapacity()
        {
            while (Count > capacity)
            {
                switch (evictionPolicy)
                {
                    case FixedSizeLinkedListEvictionPolicy.FIFO:
                        Remove(Front);
                        break;
                    case FixedSizeLinkedListEvictionPolicy.FILO:
                        Remove(Back);
                        break;
                    case FixedSizeLinkedListEvictionPolicy.LRU:
                        Remove(Front);
                        break;
                    case FixedSizeLinkedListEvictionPolicy.Clock:
                    case FixedSizeLinkedListEvictionPolicy.MRU:
                        throw new NotImplementedException("Not implemented yet");
                    default:
                        throw new ArgumentException("Invalid eviction policy");
                }
            }
        }

        public int Count => list.Count;
        public T Front => list.First.Value;
        public T Back => list.Last.Value;
        public bool IsReadOnly => false;

        public void CopyTo(T[] array, int arrayIndex)
        {
            list.CopyTo(array, arrayIndex);
        }

        public IEnumerator<T> GetEnumerator()
        {
            return list.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
    }
}