2

我正在实现一个类,它充当依赖于同一数组的三个堆栈(来自 Gayle Laakmann 的破解编码采访)。

我无法理解为什么此代码会导致类型不匹配:

class ThreeStacks[A, B, C ](val stackSize:Int  = 1000) {

  /**
   * Push a value on to the first stack
   * @param value value of type A */
  def push1[A](value :A): Unit = stack1.push(value)

  /**
   * Push a value on to the second stack
   * @param value value of type B */
  def push2[B](value: B): Unit = stack2.push(value)

  /**
  * Push a value on to the third stack
  * @param value value of type C */
  def push3[C](value: C): Unit = stack3.push(value)

  /**
   * Pops the top value off the first stack
   * @return Some(value) at the top of the stack, None if the stack is empty */
  def pop1[A](): Option[A] = stack1.pop()

  /**
   * Pops the top value off the second stack
   * @return Some(value) at the top of the stack, None if the stack is empty */
  def pop2[B](): Option[B] = stack2.pop()

  /**
   * Pops the top value off the second stack
   * @return Some(value) at the top of the stack, None if the stack is empty */
  def pop3[C](): Option[C]  = stack3.pop()

  // the shared stacks
  private val stack1 = SharedStack[A]()
  private val stack2 = SharedStack[B]()
  private val stack3 = SharedStack[C]()

  // the shared stack class is simply a container for push and pop functions
  class SharedStack[T](val push: T => Unit, val pop: () => Option[T])

  // the sharedstack object is a factory setups a shared stack object with its proper push/pop functions that are received
  // from the stackmemory instance
  private object SharedStack{
    val stackMemory = new StackMemory(stackSize)

    def apply[T](): SharedStack[T] = {
      val stackTuple = stackMemory.registerStack[T]()
      new SharedStack(stackTuple._1, stackTuple._2)
    }
  }


  // the memory object responsible for handling the sharing of the array
  private class StackMemory(val stackSize: Int = 1000){

    // helps prevent the conflict warnings with immutable and mutable collections
    private val MutableMap = scala.collection.mutable.Map

    // the array that contains the stack nodes
    private val array = new Array[Option[StackNode[Any]]](stackSize)


    // keeps track of the heads of all the stacks
    private val registeredStackHeads = MutableMap[Int, Int]()

    // an index to help assign every new stack a unique key
    private var nextRegistrationIndex = 1

    // a list of indices in the array that have been freed
    private var freedIndices = List[Int]()

    // the next available free index, increments till it reaches the end of the array, different from the freeIndices list
    // in that it only is concerned with free cells while they are available at the end of the array
    private var nextFreeIndex = 0


    /**
     * Registers a stack within the memory object and returns the push/pop functions
     * @return the push/pop functions relevant for that stack */
    def registerStack[T](): (T  => Unit, () => Option[T]) = {
      val index = nextRegistrationIndex
      val noPreviousValueIndex = -1

      // register the index in the stack heads with an empty value
      registeredStackHeads(index) = noPreviousValueIndex

      nextRegistrationIndex += 1
      (push[T](index), pop[T](index) )
    }

    /**
     * Returns the push function for a stack at the given index
     * @param stackIndex the index of the requesting stack
     * @return  the push function for the stack */
    def push[T](stackIndex: Int) = {
      (value: T) =>  {

        // get the indices and initialize a stack node
        val headIndex = registeredStackHeads(stackIndex)
        val index = nextAvailableIndex()
        val stackNode = new StackNode[T](headIndex, value)

        // store the new stack head and place it in to the array
        registeredStackHeads(stackIndex) = index
        array(index) = Some(stackNode)
      }
    }

    /**
     * The pop function for the stack at a given index
     * @param stackIndex  the index of the requesting stack
     * @return the pop function for the stack */
    def pop[T](stackIndex: Int): () => Option[T] = {
      () => {
        val headIndex = registeredStackHeads(stackIndex)

        if(headIndex < 0) None else {
          array(headIndex) match {
            case Some(s : StackNode[T]) => {
              registeredStackHeads(stackIndex) = s.previousIndex
              freeIndex(headIndex)
              Some(s.value)
            }
            case _ => None
          }
        }
      }
    }

    // retrieve the next available index, throws an exception if there are no available indices
    private def nextAvailableIndex():Int = {

      // return a new index if the array isn't full otherwise throw an exception
      def newIndex() : Int = {
        if(nextFreeIndex >= stackSize){
          throw new Exception("No more room in stack array available")
        }
        else{
          val index = nextFreeIndex
          nextFreeIndex += 1
          index
        }
      }

      // first check if any of the old indices have been freed
      freedIndices match {
        case Nil => newIndex()
        case head::tail => freedIndices = tail; head
      }
    }

    // frees an index and adds it to the free indices list
    private def freeIndex(i: Int): Unit = {
      if (i >= array.length) throw new ArrayIndexOutOfBoundsException("The index to be freed does not exist in the array")
      array(i) = None
      freedIndices = i::freedIndices
    }

    // covariant node that helps keep track of the previous index of the stack
    private class StackNode[+S](val previousIndex: Int, val value: S)

  }
}

如果我调用 stack1.push 或 stack1.pop,代码的工作方式与假设相同,但它会导致包装器 push1 和 pop1 上的类型不匹配,为什么会发生这种情况?

example for push1: 
type mismatch;
 found   : value.type (with underlying type A)
 required: A
  def push1[A](value :A): Unit = stack1.push(value)

example for pop1: 
type mismatch;
 found   : Option[A(in class ThreeStacks)]
 required: Option[A(in method pop1)]
 def pop1[A](): Option[A] = stack1.pop()
4

1 回答 1

15

您的代码中的问题是类型参数阴影。

你有:

class ThreeStacks[A, B, C](val stackSize:Int  = 1000) {
  def push1[A](value: A): Unit = stack1.push(value)
  ...
}

它应该是:

class ThreeStacks[A, B, C](val stackSize:Int  = 1000) {
  def push1(value: A): Unit = stack1.push(value)
  ...
}

您这样做的方式,A类的ThreeStacks类型参数A和方法的类型参数push1是完全不同的,因此彼此不兼容。这同样适用于BC

于 2013-08-25T20:57:30.313 回答