Skip to content

Commit 09d981f

Browse files
paramagparamag
paramag
authored and
paramag
committed
LRU cache design.
1 parent fa285e9 commit 09d981f

File tree

11 files changed

+241
-14
lines changed

11 files changed

+241
-14
lines changed

‎.gitignore‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,3 +11,6 @@
1111
/Design/ParkingLot/obj/Debug
1212
/Design/PriorityCalendar/obj/Debug
1313
/Design/PriorityCalendar/bin/Debug
14+
/Design/LRUCache/bin/Debug
15+
/Design/LRUCache/obj/Debug
16+
/Design/ParkingLot/bin/Debug

‎Algorithm/Heap/.vs/Heap/v14/.suo‎

2.5 KB
Binary file not shown.

‎Algorithm/Heap/Algorithm.Libraries.Heap.csproj‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,6 @@
4242
<ItemGroup>
4343
<Compile Include="Heap.cs" />
4444
<Compile Include="HeapType.cs" />
45-
<Compile Include="IHeap.cs" />
4645
<Compile Include="MinHeap.cs" />
4746
<Compile Include="Properties\AssemblyInfo.cs" />
4847
</ItemGroup>

‎Algorithm/Heap/IHeap.cs‎

Lines changed: 0 additions & 13 deletions
This file was deleted.

‎Design/.vs/Design/v14/.suo‎

14.5 KB
Binary file not shown.

‎Design/Design.sln‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,8 @@ Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Design.Libraries.PriorityCa
77
EndProject
88
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Design.Libraries.ParkingLot", "ParkingLot\Design.Libraries.ParkingLot.csproj", "{753E00AC-50BA-4244-854D-29068891EB17}"
99
EndProject
10+
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Design.Libraries.LRUCache", "LRUCache\Design.Libraries.LRUCache.csproj", "{69763EAE-C303-433E-8F32-82C85D7AD7D9}"
11+
EndProject
1012
Global
1113
GlobalSection(SolutionConfigurationPlatforms) = preSolution
1214
Debug|Any CPU = Debug|Any CPU
@@ -21,6 +23,10 @@ Global
2123
{753E00AC-50BA-4244-854D-29068891EB17}.Debug|Any CPU.Build.0 = Debug|Any CPU
2224
{753E00AC-50BA-4244-854D-29068891EB17}.Release|Any CPU.ActiveCfg = Release|Any CPU
2325
{753E00AC-50BA-4244-854D-29068891EB17}.Release|Any CPU.Build.0 = Release|Any CPU
26+
{69763EAE-C303-433E-8F32-82C85D7AD7D9}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
27+
{69763EAE-C303-433E-8F32-82C85D7AD7D9}.Debug|Any CPU.Build.0 = Debug|Any CPU
28+
{69763EAE-C303-433E-8F32-82C85D7AD7D9}.Release|Any CPU.ActiveCfg = Release|Any CPU
29+
{69763EAE-C303-433E-8F32-82C85D7AD7D9}.Release|Any CPU.Build.0 = Release|Any CPU
2430
EndGlobalSection
2531
GlobalSection(SolutionProperties) = preSolution
2632
HideSolutionNode = FALSE

‎Design/LRUCache/Design.Libraries.LRUCache.csproj‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
<?xml version="1.0" encoding="utf-8"?>
2+
<Project ToolsVersion="14.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3+
<Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
4+
<PropertyGroup>
5+
<Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
6+
<Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
7+
<ProjectGuid>{69763EAE-C303-433E-8F32-82C85D7AD7D9}</ProjectGuid>
8+
<OutputType>Library</OutputType>
9+
<AppDesignerFolder>Properties</AppDesignerFolder>
10+
<RootNamespace>Design.Libraries.LRUCache</RootNamespace>
11+
<AssemblyName>Design.Libraries.LRUCache</AssemblyName>
12+
<TargetFrameworkVersion>v4.5.2</TargetFrameworkVersion>
13+
<FileAlignment>512</FileAlignment>
14+
</PropertyGroup>
15+
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
16+
<DebugSymbols>true</DebugSymbols>
17+
<DebugType>full</DebugType>
18+
<Optimize>false</Optimize>
19+
<OutputPath>bin\Debug\</OutputPath>
20+
<DefineConstants>DEBUG;TRACE</DefineConstants>
21+
<ErrorReport>prompt</ErrorReport>
22+
<WarningLevel>4</WarningLevel>
23+
</PropertyGroup>
24+
<PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
25+
<DebugType>pdbonly</DebugType>
26+
<Optimize>true</Optimize>
27+
<OutputPath>bin\Release\</OutputPath>
28+
<DefineConstants>TRACE</DefineConstants>
29+
<ErrorReport>prompt</ErrorReport>
30+
<WarningLevel>4</WarningLevel>
31+
</PropertyGroup>
32+
<ItemGroup>
33+
<Reference Include="System" />
34+
<Reference Include="System.Core" />
35+
<Reference Include="System.Xml.Linq" />
36+
<Reference Include="System.Data.DataSetExtensions" />
37+
<Reference Include="Microsoft.CSharp" />
38+
<Reference Include="System.Data" />
39+
<Reference Include="System.Net.Http" />
40+
<Reference Include="System.Xml" />
41+
</ItemGroup>
42+
<ItemGroup>
43+
<Compile Include="ILRUCache.cs" />
44+
<Compile Include="DoubleLinkedList.cs" />
45+
<Compile Include="LRUCacheQueue.cs" />
46+
<Compile Include="Properties\AssemblyInfo.cs" />
47+
</ItemGroup>
48+
<Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
49+
<!-- To modify your build process, add your task inside one of the targets below and uncomment it.
50+
Other similar extension points exist, see Microsoft.Common.targets.
51+
<Target Name="BeforeBuild">
52+
</Target>
53+
<Target Name="AfterBuild">
54+
</Target>
55+
-->
56+
</Project>

‎Design/LRUCache/DoubleLinkedList.cs‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Design.Libraries.LRUCache
8+
{
9+
public class DoubleLinkedListNode
10+
{
11+
public int PageNumber;
12+
public DoubleLinkedListNode Previous { get; set; }
13+
public DoubleLinkedListNode Next { get; set; }
14+
15+
public DoubleLinkedListNode(int pageNumber)
16+
{
17+
this.PageNumber = pageNumber;
18+
this.Previous = null;
19+
this.Next = null;
20+
}
21+
}
22+
}

‎Design/LRUCache/ILRUCache.cs‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Design.Libraries.LRUCache
8+
{
9+
public interface ILRUCache
10+
{
11+
void AddOrRemovePageNumber(int pageNumber);
12+
13+
void Enqueue(int pageNumber);
14+
15+
void Dequeue();
16+
}
17+
}

‎Design/LRUCache/LRUCacheQueue.cs‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Design.Libraries.LRUCache
8+
{
9+
public class LRUCacheQueue
10+
{
11+
public Dictionary<int, DoubleLinkedListNode> lruCacheHashSet = new Dictionary<int, DoubleLinkedListNode>();
12+
public const int CacheSize = 5;
13+
14+
public int Counter = 0;
15+
public DoubleLinkedListNode head;
16+
public DoubleLinkedListNode rear;
17+
18+
public bool IsEmpty()
19+
{
20+
return this.head == null
21+
&& this.rear == null
22+
&& this.Counter == 0;
23+
}
24+
25+
public bool CheckIfElementExists(int pageNumber, out DoubleLinkedListNode node)
26+
{
27+
return this.lruCacheHashSet.TryGetValue(pageNumber, out node);
28+
}
29+
30+
public DoubleLinkedListNode CreateCacheElement(int pageNumber)
31+
{
32+
var newElement = new DoubleLinkedListNode(pageNumber);
33+
34+
return newElement;
35+
}
36+
37+
public void AddOrRemovePageNumber(int pageNumber)
38+
{
39+
DoubleLinkedListNode existingElement;
40+
41+
if (this.CheckIfElementExists(pageNumber, out existingElement))
42+
{
43+
// Detach the element from the queue.
44+
if (existingElement != null && existingElement.Previous != null)
45+
{
46+
existingElement.Previous.Next = existingElement.Next;
47+
this.Counter -= 1;
48+
}
49+
}
50+
51+
if (this.Counter == LRUCacheQueue.CacheSize)
52+
{
53+
// Remove the rear element.
54+
this.Dequeue();
55+
}
56+
57+
// Insert to the head of the queue.
58+
this.Enqueue(pageNumber);
59+
}
60+
61+
public void Enqueue(int pageNumber)
62+
{
63+
// Create the new cache element to be enqueued.
64+
DoubleLinkedListNode newElement = this.CreateCacheElement(pageNumber);
65+
66+
// If the cache is empty both head and rear point to the new element.
67+
if (this.IsEmpty())
68+
{
69+
this.head = newElement;
70+
this.rear = newElement;
71+
return;
72+
}
73+
74+
// Insert the new element to the head.
75+
newElement.Next = this.head;
76+
newElement.Previous = null;
77+
this.head = newElement;
78+
79+
this.Counter += 1;
80+
81+
// Add to the cache.
82+
lruCacheHashSet.Add(pageNumber, newElement);
83+
}
84+
85+
public void Dequeue()
86+
{
87+
if (this.IsEmpty())
88+
{
89+
return;
90+
}
91+
92+
// Remove the element from the queue.
93+
DoubleLinkedListNode elementToRemove = this.rear;
94+
95+
this.rear = elementToRemove.Previous;
96+
97+
// Reove the element from dictionary.
98+
this.lruCacheHashSet.Remove(elementToRemove.PageNumber);
99+
}
100+
}
101+
}

0 commit comments

Comments
 (0)