Data Structures

/**
 * Doubly-linked list optimized for AST node collections
 */
class List<T> {
  /** Creates an empty list */
  constructor();
  
  /** Number of items in the list */
  readonly size: number;
  /** Whether the list is empty */
  readonly isEmpty: boolean;
  /** First item in the list */
  readonly first: T;
  /** Last item in the list */
  readonly last: T;
}

class List<T> {
  /**
   * Iterate over items from first to last
   * @param fn - Function called for each item
   * @param thisArg - Value to use as 'this' when executing fn
   */
  forEach(fn: (item: T, index: number, list: List<T>) => void, thisArg?: any): void;

  /**
   * Iterate over items from last to first
   * @param fn - Function called for each item
   * @param thisArg - Value to use as 'this' when executing fn
   */
  forEachRight(fn: (item: T, index: number, list: List<T>) => void, thisArg?: any): void;

  /**
   * Reduce list items from first to last
   * @param fn - Reducer function
   * @param initialValue - Initial accumulator value
   * @param thisArg - Value to use as 'this' when executing fn
   */
  reduce<U>(fn: (acc: U, item: T, index: number, list: List<T>) => U, initialValue: U, thisArg?: any): U;

  /**
   * Reduce list items from last to first
   * @param fn - Reducer function
   * @param initialValue - Initial accumulator value
   * @param thisArg - Value to use as 'this' when executing fn
   */
  reduceRight<U>(fn: (acc: U, item: T, index: number, list: List<T>) => U, initialValue: U, thisArg?: any): U;

  /**
   * Test whether at least one item passes the predicate
   * @param fn - Predicate function
   * @param thisArg - Value to use as 'this' when executing fn
   */
  some(fn: (item: T, index: number, list: List<T>) => boolean, thisArg?: any): boolean;
}

class List<T> {
  /**
   * Create new list with transformed items
   * @param fn - Transformation function
   * @param thisArg - Value to use as 'this' when executing fn
   */
  map<U>(fn: (item: T, index: number, list: List<T>) => U, thisArg?: any): List<U>;

  /**
   * Create new list with filtered items
   * @param fn - Predicate function
   * @param thisArg - Value to use as 'this' when executing fn
   */
  filter(fn: (item: T, index: number, list: List<T>) => boolean, thisArg?: any): List<T>;
}

class List<T> {
  /**
   * Populate list from array
   * @param array - Array to convert
   */
  fromArray(array: T[]): this;

  /**
   * Convert list to array
   * @returns Array containing all list items
   */
  toArray(): T[];

  /**
   * JSON serialization (same as toArray)
   * @returns Array for JSON serialization
   */
  toJSON(): T[];
}

class List<T> {
  /** Remove all items from the list */
  clear(): void;

  /** Create shallow copy of the list */
  copy(): List<T>;

  /**
   * Add item to the beginning of the list
   * @param item - List item to prepend
   */
  prepend(item: ListItem<T>): this;

  /**
   * Add data to the beginning of the list
   * @param data - Data to prepend
   */
  prependData(data: T): this;

  /**
   * Add item to the end of the list
   * @param item - List item to append
   */
  append(item: ListItem<T>): this;

  /**
   * Add data to the end of the list
   * @param data - Data to append
   */
  appendData(data: T): this;

  /**
   * Insert item at specific position
   * @param item - List item to insert
   * @param before - Item to insert before (null for end)
   */
  insert(item: ListItem<T>, before: ListItem<T> | null): this;

  /**
   * Insert data at specific position
   * @param data - Data to insert
   * @param before - Item to insert before (null for end)
   */
  insertData(data: T, before: ListItem<T> | null): this;

  /**
   * Remove specific item from the list
   * @param item - List item to remove
   * @returns The removed item
   */
  remove(item: ListItem<T>): ListItem<T>;
}

class List<T> {
  /**
   * Add data to end (alias for appendData)
   * @param data - Data to add
   */
  push(data: T): void;

  /**
   * Remove and return last item
   * @returns Last list item or null
   */
  pop(): ListItem<T> | null;

  /**
   * Add data to beginning (alias for prependData)
   * @param data - Data to add
   */
  unshift(data: T): void;

  /**
   * Remove and return first item
   * @returns First list item or null
   */
  shift(): ListItem<T> | null;
}

class List<T> {
  /**
   * Prepend entire list to beginning
   * @param list - List to prepend
   */
  prependList(list: List<T>): this;

  /**
   * Append entire list to end
   * @param list - List to append
   */
  appendList(list: List<T>): this;

  /**
   * Insert entire list at position
   * @param list - List to insert
   * @param before - Item to insert before
   */
  insertList(list: List<T>, before: ListItem<T> | null): this;

  /**
   * Replace item with new item or list
   * @param oldItem - Item to replace
   * @param newItemOrList - Replacement item or list
   */
  replace(oldItem: ListItem<T>, newItemOrList: T | List<T>): this;
}

class List<T> {
  /**
   * Iterate forward until condition is met
   * @param start - Starting item
   * @param fn - Function called for each item (return true to stop)
   * @param thisArg - Value to use as 'this' when executing fn
   */
  nextUntil(start: ListItem<T>, fn: (item: T, item: ListItem<T>, list: List<T>) => boolean, thisArg?: any): void;

  /**
   * Iterate backward until condition is met
   * @param start - Starting item
   * @param fn - Function called for each item (return true to stop)
   * @param thisArg - Value to use as 'this' when executing fn
   */
  prevUntil(start: ListItem<T>, fn: (item: T, item: ListItem<T>, list: List<T>) => boolean, thisArg?: any): void;
}

interface ListItem<T> {
  /** Previous item in the list */
  prev: ListItem<T> | null;
  /** Next item in the list */
  next: ListItem<T> | null;
  /** The actual data */
  data: T;
}

/**
 * Creates a new list item
 * @param data - Data for the item
 * @returns New list item
 */
List.createItem<T>(data: T): ListItem<T>;

import { List } from 'css-tree';

// Create and populate list
const list = new List();
list.appendData('first');
list.appendData('second');
list.appendData('third');

console.log(list.size);     // 3
console.log(list.first);    // 'first'
console.log(list.last);     // 'third'

// Iterate over items
list.forEach((item, index) => {
  console.log(`${index}: ${item}`);
});

// Transform list
const upperList = list.map(item => item.toUpperCase());

// Filter list
const longItems = list.filter(item => item.length > 5);

// Convert to/from array
const array = list.toArray();
const newList = new List().fromArray(['a', 'b', 'c']);

// Advanced manipulation
const item = List.createItem('inserted');
list.insert(item, list.first.next); // Insert after first item

// Remove items conditionally
list.forEach((data, index, list) => {
  if (data === 'second') {
    list.remove(list.getItemAt(index));
  }
});

import { parse, walk, List } from 'css-tree';

const ast = parse('.a, .b { color: red; margin: 10px; }');

// AST nodes use List for children
walk(ast, (node) => {
  if (node.children && node.children instanceof List) {
    console.log(`${node.type} has ${node.children.size} children`);
    
    // Iterate over child nodes
    node.children.forEach((child, index) => {
      console.log(`  Child ${index}: ${child.type}`);
    });
    
    // Modify children
    if (node.type === 'SelectorList') {
      // Add new selector
      node.children.appendData({
        type: 'Selector',
        children: new List().fromArray([
          { type: 'ClassSelector', name: 'new-class' }
        ])
      });
    }
    
    // Remove children conditionally
    node.children.forEach((child, index, list) => {
      if (child.type === 'WhiteSpace') {
        list.remove(list.getItemAt(index));
      }
    });
  }
});

// Lists are optimized for:
// - Frequent insertions/deletions at any position: O(1)
// - Iteration: O(n)
// - Size access: O(1)

// Arrays are better for:
// - Random access by index: O(1) vs O(n)
// - Memory efficiency for small collections

// Use List.toArray() for index-based operations
function findNodeByIndex(list, index) {
  if (index >= 0 && index < list.size) {
    return list.toArray()[index];
  }
  return null;
}

// Use List methods for structural modifications
function insertNodes(list, nodes, position) {
  const nodeList = new List().fromArray(nodes);
  const targetItem = findItemByIndex(list, position);
  list.insertList(nodeList, targetItem);
}

// Efficient list merging
function mergeLists(...lists) {
  const result = new List();
  lists.forEach(list => {
    if (list instanceof List) {
      result.appendList(list);
    } else if (Array.isArray(list)) {
      result.appendList(new List().fromArray(list));
    }
  });
  return result;
}