Backported Collections

abstract class ArraySeq[+T] extends IndexedSeq[T] {
  protected[this] def elemTag: ClassTag[T]
  def length: Int
  def apply(index: Int): T
  def unsafeArray: Array[T @uncheckedVariance]
  override def clone(): ArraySeq[T]
}

object ArraySeq {
  /**
   * Create ArraySeq from elements
   * @param elems Elements to include
   * @param elemTag ClassTag for element type
   * @return New ArraySeq containing elements
   */
  def apply[T](elems: T*)(implicit elemTag: ClassTag[T]): ArraySeq[T]
  
  /**
   * Create ArraySeq from a collection (available through compat import)
   * Note: This method is provided via implicit extension from scala.collection.compat._
   * @param source Source collection
   * @param elemTag ClassTag for element type
   * @return New ArraySeq with elements from source
   */
  def from[T](source: TraversableOnce[T])(implicit elemTag: ClassTag[T]): ArraySeq[T]
  
  /**
   * Create empty ArraySeq
   * @return Empty ArraySeq
   */
  def empty[T <: AnyRef]: ArraySeq[T]
  
  /**
   * Wrap existing array without copying (unsafe - array must not be mutated)
   * @param x Source array to wrap
   * @return ArraySeq wrapping the array
   */
  def unsafeWrapArray[T](x: Array[T]): ArraySeq[T]
  
  /**
   * Create builder for ArraySeq
   * @param elemTag ClassTag for element type
   * @return Builder for constructing ArraySeq
   */
  def newBuilder[T](implicit elemTag: ClassTag[T]): Builder[T, ArraySeq[T]]
  
  /**
   * Pattern matching extractor
   * @param seq ArraySeq to extract from
   * @return Some(seq) for pattern matching
   */
  def unapplySeq[T](seq: ArraySeq[T]): Some[ArraySeq[T]]
}

final class ofRef[T <: AnyRef](val unsafeArray: Array[T]) extends ArraySeq[T]
final class ofByte(val unsafeArray: Array[Byte]) extends ArraySeq[Byte]  
final class ofShort(val unsafeArray: Array[Short]) extends ArraySeq[Short]
final class ofChar(val unsafeArray: Array[Char]) extends ArraySeq[Char]
final class ofInt(val unsafeArray: Array[Int]) extends ArraySeq[Int]
final class ofLong(val unsafeArray: Array[Long]) extends ArraySeq[Long]
final class ofFloat(val unsafeArray: Array[Float]) extends ArraySeq[Float]
final class ofDouble(val unsafeArray: Array[Double]) extends ArraySeq[Double]
final class ofBoolean(val unsafeArray: Array[Boolean]) extends ArraySeq[Boolean]
final class ofUnit(val unsafeArray: Array[Unit]) extends ArraySeq[Unit]

import scala.collection.compat.immutable.ArraySeq
import scala.collection.compat._  // Required for .from method

// Create from elements
val numbers = ArraySeq(1, 2, 3, 4, 5)
val strings = ArraySeq("hello", "world")

// Create from existing collection (requires compat import for .from method)
val fromList = ArraySeq.from(List(1, 2, 3))
val fromRange = ArraySeq.from(1 to 10)

// Efficient indexed access
val third = numbers(2)  // 3
val length = numbers.length  // 5

// Wrap existing array (unsafe - don't mutate the source array!)
val array = Array(1, 2, 3)
val wrapped = ArraySeq.unsafeWrapArray(array)

// Builder pattern
val builder = ArraySeq.newBuilder[Int]
builder += 1
builder += 2  
val built = builder.result()

// Pattern matching
ArraySeq(1, 2, 3) match {
  case ArraySeq(first, rest @ _*) => println(s"First: $first, Rest: $rest")
}

final class LazyList[+A] extends LinearSeq[A] {
  /**
   * Size if known, -1 otherwise (avoids forcing evaluation)
   * @return Known size or -1
   */
  def knownSize: Int
  
  /**
   * Test if LazyList is empty
   * @return true if empty
   */
  override def isEmpty: Boolean
  
  /**
   * Get first element (forces evaluation of head)
   * @return First element
   * @throws NoSuchElementException if empty
   */
  override def head: A
  
  /**
   * Get remaining elements (forces evaluation of head only)
   * @return Tail LazyList
   * @throws UnsupportedOperationException if empty
   */
  override def tail: LazyList[A]
  
  /**
   * Force evaluation of all elements
   * @return This LazyList with all elements evaluated
   */
  def force: this.type
  
  /**
   * Lazy concatenation with another collection
   * @param suffix Collection to append lazily
   * @return New LazyList with suffix appended
   */
  def lazyAppendedAll[B >: A](suffix: => GenTraversableOnce[B]): LazyList[B]
  
  /**
   * Apply side effect while preserving laziness
   * @param f Side effect function
   * @return LazyList with side effects applied during traversal
   */
  def tapEach[U](f: A => U): LazyList[A]
  
  /**
   * Partition and map simultaneously (lazy evaluation)
   * @param f Function returning Either for partitioning and transformation
   * @return Tuple of (left LazyList, right LazyList)
   */
  def partitionMap[A1, A2](f: A => Either[A1, A2]): (LazyList[A1], LazyList[A2])
  
  /**
   * Remove duplicates by function (lazy evaluation)
   * @param f Function to extract comparison key  
   * @return LazyList with duplicates removed
   */
  def distinctBy[B](f: A => B): LazyList[B]
}

object LazyList {
  /**
   * Empty LazyList
   * @return Empty LazyList
   */
  def empty[A]: LazyList[A]
  
  /**
   * Create LazyList from elements
   * @param elems Elements to include
   * @return LazyList containing elements
   */
  def apply[A](elems: A*): LazyList[A]
  
  /**
   * Create LazyList from collection
   * @param coll Source collection
   * @return LazyList with elements from collection
   */
  def from[A](coll: GenTraversableOnce[A]): LazyList[A]
  
  /**
   * Create infinite LazyList by iteration
   * @param start Starting value (call-by-name)
   * @param f Function to generate next value
   * @return Infinite LazyList
   */
  def iterate[A](start: => A)(f: A => A): LazyList[A]
  
  /**
   * Create infinite numeric sequence
   * @param start Starting number
   * @param step Step size
   * @return Infinite LazyList of numbers
   */
  def from(start: Int, step: Int): LazyList[Int]
  
  /**
   * Create infinite numeric sequence with step 1
   * @param start Starting number
   * @return Infinite LazyList of numbers
   */
  def from(start: Int): LazyList[Int]
  
  /**
   * Create infinite LazyList repeating element
   * @param elem Element to repeat (call-by-name)
   * @return Infinite LazyList of repeated element
   */
  def continually[A](elem: => A): LazyList[A]
  
  /**
   * Create LazyList with n copies of element
   * @param n Number of copies
   * @param elem Element to repeat (call-by-name)
   * @return LazyList with n copies
   */
  def fill[A](n: Int)(elem: => A): LazyList[A]
  
  /**
   * Create LazyList by tabulation
   * @param n Number of elements
   * @param f Function from index to element
   * @return LazyList created by applying function to indices
   */
  def tabulate[A](n: Int)(f: Int => A): LazyList[A]
  
  /**
   * Create LazyList by unfolding from seed value
   * @param init Initial seed value
   * @param f Function that produces (element, next seed) or None to stop
   * @return LazyList created by unfolding
   */
  def unfold[A, S](init: S)(f: S => Option[(A, S)]): LazyList[A]
  
  /**
   * Concatenate multiple iterables into LazyList
   * @param xss Iterables to concatenate
   * @return LazyList containing all elements
   */
  def concat[A](xss: collection.Iterable[A]*): LazyList[A]
}

/**
 * Alternative cons construction
 */
object cons {
  def unapply[A](xs: LazyList[A]): Option[(A, LazyList[A])]
}

/**
 * Pattern matching cons extractor  
 */
object #:: {
  def unapply[A](xs: LazyList[A]): Option[(A, LazyList[A])]
}

/**
 * Implicit conversion to enable #:: syntax
 * @param l LazyList (call-by-name)
 * @return Deferrer for cons operations
 */
implicit def toDeferrer[A](l: => LazyList[A]): Deferrer[A]

final class Deferrer[A] {
  /**
   * Prepend element to LazyList
   * @param elem Element to prepend (call-by-name)
   * @return New LazyList with element prepended
   */
  def #::[B >: A](elem: => B): LazyList[B]
  
  /**
   * Prepend LazyList to LazyList
   * @param prefix LazyList to prepend
   * @return Combined LazyList
   */
  def #:::[B >: A](prefix: LazyList[B]): LazyList[B]
}

import scala.collection.compat.immutable.LazyList

// Create finite LazyList
val finite = LazyList(1, 2, 3, 4, 5)
val fromRange = LazyList.from(1 to 100)

// Create infinite LazyList
val naturals = LazyList.from(1)  // 1, 2, 3, 4, ...
val evens = LazyList.from(0, 2)  // 0, 2, 4, 6, ...
val fibonacci = LazyList.iterate((0, 1)) { case (a, b) => (b, a + b) }.map(_._1)

// Cons syntax
val list1 = 1 #:: 2 #:: 3 #:: LazyList.empty
val list2 = 0 #:: list1  // Prepend element
val list3 = LazyList(-2, -1) #::: list2  // Prepend LazyList

// Lazy operations (elements computed on demand)
val squares = naturals.map(n => n * n)
val first10Squares = squares.take(10).toList

// Pattern matching
fibonacci match {
  case a #:: b #:: rest => println(s"First two: $a, $b")
  case _ => println("Not enough elements")
}

// Force evaluation
val evaluated = LazyList(1, 2, 3).force

// Infinite data processing
val primes = naturals.drop(1).filter(isPrime)
val first100Primes = primes.take(100).toList

// Lazy concatenation  
val combined = finite.lazyAppendedAll(naturals)

// Side effects with preserved laziness
val logged = naturals.tapEach(n => if (n % 1000 == 0) println(s"Processed $n"))

// Memory-efficient processing of large datasets
def processLargeFile(lines: LazyList[String]): LazyList[ProcessedData] =
  lines
    .filter(_.nonEmpty)
    .map(parseLine)
    .tapEach(validateData)
    .distinctBy(_.id)

// Scala 2.13 compatibility aliases
package scala.collection.compat.immutable {
  type ArraySeq[+A] = scala.collection.immutable.ArraySeq[A]
  val ArraySeq = scala.collection.immutable.ArraySeq
  
  type LazyList[+A] = scala.collection.immutable.LazyList[A]  
  val LazyList = scala.collection.immutable.LazyList
}