Как удалить повторяющиеся элементы из итератора?

Question

Это продолжение моего предыдущего вопроса .
Как бы вы написали функцию для фильтрации смежных дубликатов из данного итератора?

def remove[A](it: Iterator[A]): Iterator[A] = ???
remove("aaabccbbad".iterator).toList.map(_.mkString) // "abcbad"

PS Функция должно работать, когда весь ввод не помещается в памяти. Вот почему функция использует итераторы.

Answer 1

Слишком низкий уровень. Но это гарантирует, что он будет потреблять элементы только по мере необходимости.

def remove[A](it: Iterator[A]): Iterator[A] =
  new Iterator[A] {
    private[this] var current: Option[A] = None

    override def hasNext: Boolean =
      it.hasNext || (current ne None)

    override def next(): A = {
      @annotation.tailrec
      def loop(): A = (it.nextOption(), current) match {
        case (Some(a), Some(c)) if (a == c) =>
          loop()

        case (sa @ Some(a), Some(c)) =>
          current = sa
          c

        case (sa @ Some(a), None) =>
          current = sa
          loop()

        case (None, Some(c)) =>
          current = None
          c

        case (None, None) =>
          Iterator.empty[A].next()
      }

      loop()
    }
  }

---

Более или менее так же, как указано выше, но вместо этого используется unfold.

def remove[A](it: Iterator[A]): Iterator[A] = {
  type State = (Option[A], Option[A]) // value -> current

  def process(state: State): Option[State] = state match {
    case (Some(a), sc @ Some(c)) if (a == c) =>
      Some(None -> sc)

    case (sa @ Some(a), sc @ Some(c)) =>
      Some(sc -> sa)

    case (sa @ Some(a), None) =>
      Some(None -> sa)

    case (None, sc @ Some(c)) =>
      Some(sc -> None)

    case (None, None) =>
      None
  }

  Iterator.unfold(it.nextOption() -> Option.empty[A]) { state =>
    process(state).map {
      case (value, current) =>
        (value -> (it.nextOption() -> current))
    }
  } collect {
    case Some(a) => a
  }
}

---

(их можно сделать более эффективными, используя null вместо Option , но это требует специальной обработки примитивов)

Answer 2

Вы можете использовать следующее:

"aaabccbbad"
    .map(ch => s"${ch}")
    .reduce((s1, s2) => if(s1.takeRight(1) == s2) s1 else s1 + s2)

Это приводит к

res0: String = abcbad

Сначала для удобства я литье символов в строки. Затем я сравниваю последний символ того, что у меня уже есть, с последовательными символами, и если они отличаются, я добавляю его.

В более общем смысле это может быть так:

stream.map(el => ListBuffer.empty.addOne(el))
    .reduce((lb1, lb2) => if(lb1.last == lb2.last) lb1 else lb1.addAll(lb2))
    .toList

Answer 3

Я думаю, что это проще с хвостовой рекурсией:

def remove[A](it: Iterator[A]): Iterator[A] = {
  def removeLoop(result: Iterator[A], remaining: Iterator[A]): Iterator[A] = {
    if(remaining.isEmpty) {
      result
    } else {
      val e = remaining.next();
      removeLoop(result ++ Iterator(e), remaining.dropWhile(a => a == e))
    }  
  }

  removeLoop(Iterator.empty[A], it)
}

remove("aaabccbbad".iterator).toList.map(_.toString).mkString // "abcbad"

---

Редактировать: Согласно комментарию, приведенная выше реализация не ленива.

Возможная ленивая реализация будет выглядеть примерно так:

def remove[A](it: Iterator[A]): Iterator[A] = new AbstractIterator[A] {
  var lastElement: A = _

  def hasNext: Boolean = it.hasNext

  def next(): A = {
    @scala.annotation.tailrec
    def nextLoop(lastElement: A, it: Iterator[A]): A = {
      val temp = it.next
      if(lastElement == temp)
        nextLoop(lastElement, it)
      else
        temp
    }
    lastElement = nextLoop(lastElement, it)
    lastElement
  }
}

remove("aaabccbbad".iterator).take(2).foreach(print) // "ab"
remove("aaabccbbad".iterator).foreach(print) // "abcbad"

Answer 4

Я бы преобразовал входной итератор в итератор списков дубликатов, а затем просто сопоставил бы каждый список с его заголовком. Чтобы сделать это, я бы использовал две функции из моих предыдущих вопросов:

• функция splitDupes: Iterator[A] => (List[A], Iterator[A]) (предлагается здесь ) для выделения префикса дубликатов и возврата пара префикса и остальные

• функция split: Iterator[A] => Iterator[List[A]] (предлагается здесь ) для преобразования данного итератора в итератор списков дубликатов с использованием splitDupes .

Большое спасибо Kolmar за эти предложения. Используя их, я могу реализовать remove следующим образом:

def remove[A](it: Iterator[A]): Iterator[A] = split(it).flatMap(_.headOption)

См. Ниже реализации splitDupes и split только для справки:

def splitDupes[A](it: Iterator[A]): (List[A], Iterator[A]) = {
  if (it.isEmpty) {
    (Nil, Iterator.empty)
  } else {
    val head = it.next()
    val (dupes, rest) = it.span(_ == head)
    (head +: dupes.toList, rest)
  }
}

def split[A](it: Iterator[A]): Iterator[List[A]] = {
  Iterator.iterate(splitDupes(it))(x => splitDupes(x._2)).map(_._1).takeWhile(_.nonEmpty)
}