Collections Framework

/**
 * Root trait for all collections
 * Provides basic iteration and transformation operations
 */
trait Iterable[+A] {
  /** Iterator over collection elements */
  def iterator: Iterator[A]
  
  /** Apply function to each element */
  def foreach[U](f: A => U): Unit
  
  /** Transform each element */
  def map[B](f: A => B): Iterable[B]
  
  /** Filter elements by predicate */
  def filter(p: A => Boolean): Iterable[A]
  
  /** Fold left with accumulator */
  def foldLeft[B](z: B)(op: (B, A) => B): B
  
  /** Check if collection is empty */
  def isEmpty: Boolean
  
  /** Get collection size */
  def size: Int
  
  /** Convert to List */
  def toList: List[A]
  
  /** Convert to Array */
  def toArray[B >: A: ClassTag]: Array[B]
}

/**
 * Collections that can be traversed multiple times
 */
trait Traversable[+A] extends Iterable[A] {
  /** Partition elements by predicate */
  def partition(p: A => Boolean): (Iterable[A], Iterable[A])
  
  /** Group elements by key function */
  def groupBy[K](f: A => K): Map[K, Iterable[A]]
  
  /** Find first element matching predicate */
  def find(p: A => Boolean): Option[A]
  
  /** Test if any element matches predicate */
  def exists(p: A => Boolean): Boolean
  
  /** Test if all elements match predicate */
  def forall(p: A => Boolean): Boolean
}

/**
 * Immutable singly-linked list - the fundamental Scala collection
 * Implemented using JavaScript objects for optimal performance
 */
sealed abstract class List[+A] extends LinearSeq[A] {
  /** Prepend element (O(1) operation) */
  def ::[B >: A](elem: B): List[B]
  
  /** Get head element (throws on empty list) */
  def head: A
  
  /** Get tail list (throws on empty list) */
  def tail: List[A]
  
  /** Safe head access */
  def headOption: Option[A]
  
  /** Test if list is empty */
  def isEmpty: Boolean
  
  /** Get list length (O(n) operation) */
  def length: Int
  
  /** Reverse list */
  def reverse: List[A]
  
  /** Append another list */
  def :::[B >: A](prefix: List[B]): List[B]
  
  /** Transform each element */
  def map[B](f: A => B): List[B]
  
  /** Filter elements */
  def filter(p: A => Boolean): List[A]
  
  /** Fold left */
  def foldLeft[B](z: B)(op: (B, A) => B): B
  
  /** Fold right */
  def foldRight[B](z: B)(op: (A, B) => B): B
}

/**
 * Non-empty list node
 */
final case class ::[+A](head: A, tail: List[A]) extends List[A]

/**
 * Empty list singleton
 */
case object Nil extends List[Nothing]

/**
 * Factory methods for List creation
 */
object List {
  /** Create list from variable arguments */
  def apply[A](elems: A*): List[A]
  
  /** Empty list */
  def empty[A]: List[A] = Nil
  
  /** Create list filled with element */
  def fill[A](n: Int)(elem: A): List[A]
  
  /** Create list by applying function to indices */
  def tabulate[A](n: Int)(f: Int => A): List[A]
  
  /** Create list from range */
  def range(start: Int, end: Int): List[Int]
  def range(start: Int, end: Int, step: Int): List[Int]
}

/**
 * Resizable array implementation using JavaScript arrays
 * Provides O(1) append and random access operations
 */
class ArrayBuffer[A] extends mutable.Buffer[A] {
  /** Append element to end */
  def +=(elem: A): this.type
  
  /** Prepend element to beginning */
  def +=:(elem: A): this.type
  
  /** Insert element at index */
  def insert(n: Int, elems: A*): Unit
  
  /** Remove element at index */
  def remove(n: Int): A
  def remove(n: Int, count: Int): Unit
  
  /** Get/set element by index */
  def apply(n: Int): A
  def update(n: Int, elem: A): Unit
  
  /** Current size */
  def length: Int
  
  /** Clear all elements */
  def clear(): Unit
  
  /** Convert to immutable List */
  def toList: List[A]
}

/**
 * Hash-based mutable map using JavaScript objects
 */
class mutable.Map[A, B] extends mutable.MapLike[A, B, mutable.Map[A, B]] {
  /** Get value by key */
  def get(key: A): Option[B]
  
  /** Set key-value pair */
  def update(key: A, value: B): Unit
  
  /** Add key-value pair */
  def +=(kv: (A, B)): this.type
  
  /** Remove key */
  def -=(key: A): this.type
  
  /** Test if key exists */
  def contains(key: A): Boolean
  
  /** Get all keys */
  def keys: Iterable[A]
  
  /** Get all values */
  def values: Iterable[B]
  
  /** Clear all entries */
  def clear(): Unit
  
  /** Number of entries */
  def size: Int
}

/**
 * Immutable hash-based map
 * Uses structural sharing for efficient copying
 */
trait Map[A, +B] extends Iterable[(A, B)] {
  /** Get value by key */
  def get(key: A): Option[B]
  
  /** Get value or default */
  def getOrElse[B1 >: B](key: A, default: => B1): B1
  
  /** Add key-value pair (returns new map) */
  def +[B1 >: B](kv: (A, B1)): Map[A, B1]
  
  /** Remove key (returns new map) */
  def -(key: A): Map[A, B]
  
  /** Test if key exists */
  def contains(key: A): Boolean
  
  /** Transform values */
  def mapValues[C](f: B => C): Map[A, C]
  
  /** Get all keys */
  def keys: Iterable[A]
  
  /** Get all values */  
  def values: Iterable[B]
  
  /** Number of entries */
  def size: Int
  
  /** Test if empty */
  def isEmpty: Boolean
}

/**
 * Immutable hash-based set
 */
trait Set[A] extends Iterable[A] {
  /** Test if element is in set */
  def contains(elem: A): Boolean
  
  /** Add element (returns new set) */
  def +(elem: A): Set[A]
  
  /** Remove element (returns new set) */
  def -(elem: A): Set[A]
  
  /** Set union */
  def ++(that: Set[A]): Set[A]
  
  /** Set intersection */
  def intersect(that: Set[A]): Set[A]
  
  /** Set difference */
  def diff(that: Set[A]): Set[A]
  
  /** Test if subset */
  def subsetOf(that: Set[A]): Boolean
  
  /** Number of elements */
  def size: Int
  
  /** Test if empty */
  def isEmpty: Boolean
}

import scala.collection._

// List operations
val numbers = List(1, 2, 3, 4, 5)
val doubled = numbers.map(_ * 2)
val evens = numbers.filter(_ % 2 == 0)
val sum = numbers.foldLeft(0)(_ + _)

// List construction
val prepended = 0 :: numbers  // List(0, 1, 2, 3, 4, 5)
val combined = List(1, 2) ::: List(3, 4)  // List(1, 2, 3, 4)

// ArrayBuffer for mutable operations
val buffer = mutable.ArrayBuffer[Int]()
buffer += 1
buffer += 2
buffer ++= List(3, 4, 5)
buffer.insert(0, 0)  // Insert at beginning
val removed = buffer.remove(1)  // Remove second element

// Immutable Map operations
val scores = Map("Alice" -> 95, "Bob" -> 87, "Carol" -> 92)
val updated = scores + ("Dave" -> 88)  // Add new entry
val withoutBob = scores - "Bob"  // Remove entry
val aliceScore = scores.getOrElse("Alice", 0)

// Set operations
val fruits = Set("apple", "banana", "cherry")
val moreFruits = fruits + "date"
val tropical = Set("banana", "mango", "pineapple")
val common = fruits intersect tropical  // Set("banana")
val unique = fruits diff tropical  // Set("apple", "cherry")

// Mutable Map for efficient updates
val cache = mutable.Map[String, Int]()
cache("key1") = 100
cache += ("key2" -> 200)
if (cache.contains("key1")) {
  println(s"Found: ${cache("key1")}")
}

// Collection transformations
val words = List("hello", "world", "scala", "js")
val lengths = words.map(_.length)
val longWords = words.filter(_.length > 4)
val grouped = words.groupBy(_.charAt(0))

// Advanced operations
val nested = List(List(1, 2), List(3, 4), List(5))
val flattened = nested.flatten  // List(1, 2, 3, 4, 5)

val pairs = List(1, 2, 3).zip(List("a", "b", "c"))  // List((1,"a"), (2,"b"), (3,"c"))
val (odds, evens2) = List(1, 2, 3, 4, 5).partition(_ % 2 == 1)

/**
 * Iterator providing lazy traversal of collections
 * Consumes elements on-demand for memory efficiency
 */
trait Iterator[+A] {
  /** Test if more elements available */
  def hasNext: Boolean
  
  /** Get next element (consuming) */
  def next(): A
  
  /** Transform elements lazily */
  def map[B](f: A => B): Iterator[B]
  
  /** Filter elements lazily */
  def filter(p: A => Boolean): Iterator[A]
  
  /** Take first n elements */
  def take(n: Int): Iterator[A]
  
  /** Drop first n elements */
  def drop(n: Int): Iterator[A]
  
  /** Convert to List (materializes all elements) */
  def toList: List[A]
  
  /** Fold left over elements */
  def foldLeft[B](z: B)(op: (B, A) => B): B
  
  /** Apply function to each element (consuming) */
  def foreach[U](f: A => U): Unit
}

/**
 * Lazy list with memoization (Scala 2.13+)
 * Elements computed on-demand and cached
 */
class LazyList[+A] extends LinearSeq[A] {
  /** Get head element (computed lazily) */
  def head: A
  
  /** Get tail (computed lazily) */
  def tail: LazyList[A]
  
  /** Test if empty */
  def isEmpty: Boolean
  
  /** Prepend element */
  def #::[B >: A](elem: B): LazyList[B]
  
  /** Transform elements (lazy) */
  def map[B](f: A => B): LazyList[B]
  
  /** Filter elements (lazy) */
  def filter(p: A => Boolean): LazyList[A]
  
  /** Take elements (lazy) */
  def take(n: Int): LazyList[A]
  
  /** Drop elements (lazy) */
  def drop(n: Int): LazyList[A]
}

/**
 * Factory methods for LazyList
 */
object LazyList {
  /** Create LazyList from elements */
  def apply[A](elems: A*): LazyList[A]
  
  /** Empty LazyList */
  def empty[A]: LazyList[A]
  
  /** Create infinite sequence */
  def continually[A](elem: => A): LazyList[A]
  
  /** Create sequence by iterating function */
  def iterate[A](start: A)(f: A => A): LazyList[A]
  
  /** Create sequence from range */
  def range(start: Int, end: Int): LazyList[Int]
  def range(start: Int, end: Int, step: Int): LazyList[Int]
  
  /** Create from iterator */
  def from(iterator: Iterator[A]): LazyList[A]
}

// Iterator for memory-efficient processing
val largeData = (1 to 1000000).iterator
val processed = largeData
  .filter(_ % 2 == 0)
  .map(_ * 2)
  .take(100)
  .toList

// LazyList for infinite sequences
val fibonacci: LazyList[Int] = 0 #:: 1 #:: fibonacci.zip(fibonacci.tail).map { case (a, b) => a + b }
val first10Fib = fibonacci.take(10).toList

// Lazy evaluation benefits
val expensiveOperation = LazyList.continually {
  println("Computing...")  // Only printed when accessed
  scala.util.Random.nextInt(100)
}

val firstThree = expensiveOperation.take(3).toList  // Prints "Computing..." 3 times

// Stream processing pipeline
val numbers = LazyList.range(1, 1000000)
val result = numbers
  .filter(_ % 3 == 0)
  .map(n => n * n)
  .takeWhile(_ < 10000)
  .sum  // Only computes what's needed