Implement lists data structures

[tshemsedinov]

Desired lists (or more)

• List and Queue
• DoublyList or Deque (I'd prefer Deque name)
• Stack
• CurcularList or CircularBuffer
• Heap
• Trees
• SkipList

But we may implement universal classes if some of data structures may be combined into universal abstractions. For

We need to implement:

• unittests (node native test runner and asserts)
• documentation in README.md
• typings in .d.ts

[tshemsedinov]

@timursevimli Please write short task description for data structures with links to node implementation

[tshemsedinov]

@timursevimli Please prepare interfaces for: Stack, Queue, Dequeue and classes implementing them: SinglyLinkedList, DoublyLinkedList, CircularLinkedList

[tshemsedinov]

class List<T> {
  readonly size: number;
  constructor(size: number);
  static fromArray(values: Array<T>): List<T>;
  static fromIterator(iterator: Iterator<T>): List<T>;
  static empty<T>(): List<T>;
  static range(start: number, end: number, step?: number): List<number>;
  static merge(lists: Array<List>): List<T>;

  push(value: T): void;
  pop(): T | undefined;
  shift(): T | undefined;
  unshift(value: T): void;

  append(value: T): void; // Alias for push
  prepend(value: T): void; // Alias for unshift

  enqueue(value: T): void; // Alias for push
  dequeue(): T | undefined; // Alias for shift

  insert(index: number, value: T, count?: number): void;
  remove(index: number, count?: number): void;

  get(index: number): T | undefined;
  set(index: number, value: T): void;

  top(): T | undefined;
  tail(): List<T>; // List without first element
  last(): T | undefined;
  initial(): List<T>; // List without last element

  drop(n: number): void; // Drops n from top or -n from bottom
  take(n: number): List<T>; // Take n from top or -n from bottom
  slice(start?: number, end?: number): List<T>;

  rotateLeft(steps?: number): void;
  rotateRight(steps?: number): void;

  contains(value: T): boolean;
  indexOf(value: T): number;
  lastIndexOf(value: T): number;
  equals(other: List<T>): boolean;

  addAll(values: Iterable<T>): void;
  removeAll(values: Iterable<T>): void;
  fill(value: T, start?: number, end?: number): void;
  replace(oldValue: T, newValue: T): void;

  distinct(): void; // Remove duplicates
  toDistinct(): List<T>;

  shuffle(): void;
  toShuffled(): List<T>;

  reverse(): void;
  toReversed(): List<T>;

  sort(fn?: (a: T, b: T) => number): void;
  toSorted(fn?: (a: T, b: T) => number): List<T>;

  map<U>(fn: (value: T, index: number) => U): List<U>; 
  lazyMap<U>(fn: (value: T, index: number) => U): Iterator<U>;

  filter(fn: (value: T, index: number) => boolean): List<T>;
  lazyFilter(fn: (value: T, index: number) => boolean): Iterator<T>;

  reduce<U>(fn: (acc: U, value: T, index: number) => U, initial: U): U;
  lazyReduce<U>(fn: (acc: U, value: T, index: number) => U, initial: U): Iterator<U>;

  some(fn: (value: T, index: number) => boolean): boolean;
  every(fn: (value: T, index: number) => boolean): boolean;
  find(fn: (value: T, index: number) => boolean): T | undefined;
  findIndex(fn: (value: T, index: number) => boolean): number;
  
  [Symbol.iterator](): Iterator<T>;
  toArray(): Array<T>;
  join(separator?: string): string;
  clone(): List<T>;
  clear(): void;
}

[tshemsedinov]

Ideas

• We need to research possibility of separation of List into Vector and List
• Think about checking type homogeneity, throw on different object shapes to avoid polymorphic code