Необходимо реализовать неизменяемый стек через список на языке Scala, у которого в случае, если тип параметра является числовым, должна быть доступна операция average
, возвращающая среднее арифметическое элементов стека и работающая за константное время.
Для реализации такого стека я создал абстрактный класс MegaStackAbs[T]
и объект-компаньон для него (пока что только для одного из числовых типов Int, в дальнейшем легко обобщается на другие числовые типы).
abstract class MegaStackAbs[T](val values: List[T]) {
val countedAverage: Double
def average: Double
}
object MegaStackAbs {
implicit object MegaStackInt extends MegaStackAbs[Int](???) {
override val countedAverage: Double = values.sum.asInstanceOf[Double] / values.length
override def average: Double = countedAverage
}
}
В переменной values
предполагается хранение элементов стека. В переменной countedAverage
мной предполагается хранение заранее вычисленного среднего арифметического всех элементов стека, для того чтобы функция average
возвращала данное вычисленное значение за константное время.
Затем я создал класс MegaStack[T]
, наследник абстрактного класса MegaStackAbs[T]
, в котором уже определил нужные мне стандартные операции для работы со стеком - push
, pop
, empty
.
class MegaStack[T: MegaStackAbs](values: List[T]) extends MegaStackAbs[T](values) {
override val countedAverage: Double = implicitly[MegaStackAbs[T]].countedAverage
def push(value: T): MegaStack[T] = new MegaStack[T](values.appended(value))
def pop: (MegaStack[T], T) = {
if (empty) {
throw new Exception("Stack is empty")
}
(new MegaStack[T](values.dropRight(1)), values.last)
}
def empty: Boolean = values.isEmpty
override def average: Double = implicitly[MegaStackAbs[T]].average
override def toString: String = values.toString()
}
Также я написал тесты на реализованный мной стек.
import org.scalatest.FunSuite
class MegaStackTest extends FunSuite {
test("MegaStack[String]") {
var stack = new MegaStack(List[String]("1", "2"))
assert(!stack.empty)
var result = stack.pop
stack = result._1
assert(result._2 == "2")
assert(!stack.empty)
stack = stack.push("3")
assert(!stack.empty)
result = stack.pop
stack = result._1
assert(result._2 == "3")
assert(!stack.empty)
result = stack.pop
stack = result._1
assert(result._2 == "1")
assert(stack.empty)
}
test("MegaStack[Int]") {
var stack = new MegaStack(List[Int](1, 2))
assert(!stack.empty)
assert(stack.average == 1.5)
var result = stack.pop
stack = result._1
assert(result._2 == 2)
assert(!stack.empty)
assert(stack.average == 1)
stack = stack.push(3)
assert(!stack.empty)
assert(stack.average == 2)
result = stack.pop
stack = result._1
assert(result._2 == 3)
assert(!stack.empty)
assert(stack.average == 1)
result = stack.pop
stack = result._1
assert(result._2 == 1)
assert(stack.empty)
}
}
Но при запуске тестов появляется две ошибки вида an implementation is missing
, где первая появляется при объявлении стека в первом тесте, вторая при объявлении стека во втором тесте соответственно.
Подскажите, пожалуйста, что я сделал некорректно. Я полагаю, что ошибка в использовании ???
в объекте-компаньоне при передаче аргумента конструктору абстрактного класса. У меня совсем нет идей, как можно сделать так, чтобы среднее арифметическое всех элементов стека вычислялось заранее только для стеков с числовым типом параметра T
и чтобы метод average
был доступен только для них же. При помощи отладки моей программы я убедился, что переменная countedAverage
в объекте-компаньоне вычисляется до того, как создаётся объект класса MegaStack[T]
. Но тогда непонятно, как сделать так, чтобы в объекте-компаньоне получить доступ к актуальному значению переменной values
объекта класса MegaStack[T]
, поскольку values
в объекте-компаньоне будет равняться тому значению, которое я укажу вместо ???
при наследовании абстрактного класса MegaStackAbs[T]
. Насколько мне известно, в Scala нельзя создать object
с конструктором с аргументами, куда можно было бы передать актуальное значение переменной values
.
P.S. Запрещено использовать ключевое слово var
, поскольку необходимо придерживаться объектно-функциональной парадигмы в коде.