Last active
June 2, 2022 12:06
-
-
Save DedSec256/8751d68c932082b36f33b222c3a3b821 to your computer and use it in GitHub Desktop.
Queue
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| namespace FSharpControl | |
| module Task3 = | |
| open System | |
| (* Task 3 *) | |
| /// <summary> | |
| /// Последовательность ячеек c приоритетом внутри очереди | |
| /// </summary> | |
| type Element<'a> = | |
| | Element of 'a * int * Element<'a> | |
| | Empty | |
| with | |
| member this.GetValue() = | |
| match this with | |
| | Element(x, p, n) -> Some(x) | |
| | Empty -> None | |
| /// <summary> | |
| /// FIFO - очередь | |
| /// </summary> | |
| type PriorityQueue<'a>() = | |
| let mutable start = Empty | |
| let mutable size = 0 | |
| /// <summary> | |
| /// Размер очереди | |
| /// </summary> | |
| member this.Size | |
| with get() = size | |
| /// <summary> | |
| /// Пуста ли очередь | |
| /// </summary> | |
| member this.IsEmpty() = | |
| start = Empty | |
| override this.ToString() = | |
| start.ToString() | |
| /// <summary> | |
| /// Добавить элемент в очередь. | |
| /// С текучим синтаксисом .Enqueue(10, 1).Enqueue(20, 2) | |
| /// <param name="item">Добавляемый элемент</param> | |
| /// <param name="priority">Приоритет элемента (большее число соответствует большему приоритету)</param> | |
| /// </summary> | |
| member this.Enqueue (item, priority) = | |
| let rec recEnqueue data node = | |
| match node with | |
| | Empty -> Element(item, priority, Empty) | |
| | Element(x, p, n) -> | |
| match p with | |
| | p when (p >= priority) -> | |
| match n with | |
| | Empty -> Element(x, p, Element(item, priority, Empty)) | |
| | Element(_, np, _) -> | |
| match np with | |
| | np when np >= priority -> Element(x, p, recEnqueue item n) | |
| | _ -> Element(x, p, Element(item, priority, n)) | |
| | _ -> Element(item, priority, node) | |
| start <- recEnqueue item start | |
| size <- size + 1 | |
| this | |
| /// <summary> | |
| /// Получить первого в очереди и удалить его из неё | |
| /// </summary> | |
| member this.Dequeue() = | |
| let getStart() = | |
| match start with | |
| | Empty -> raise (InvalidOperationException("Очередь пуста")) | |
| | Element(x, p, n) -> (x, n) | |
| let (data, newStart) = getStart() | |
| start <- newStart | |
| size <- size - 1 | |
| data |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment