Can I use class methods inside factory constructor via Dart

Question

I have the below code that is creating the PriortyQueue structure using Dart. But since I cannot use heapify function inside the Constructor or factory constructor I cannot initialize PQ with an existing set of List. Can somebody guide me and show me how I can use heapify while creating PQ instance so I can initialize it with an existing List? Also If you have any other suggestions against doing something like this please also help me as well. thank you

class PriorityQueue<T extends Comparable<T>> {
  List<T?> _tree;

  PriorityQueue._(List<T?> tree) : _tree = tree;

  factory PriorityQueue([List<T>? array]) {
    List<T?> newArray = [null, ...array ?? []];
    // ignore: todo
    //TODO: missing heapify
    return PriorityQueue._(newArray);
  }

  void insert(T node) {
    _tree.add(node);
    _swim(_tree.length - 1);
  }

  T getTop() {
    _swap(1, _tree.length - 1);
    T top = _tree.removeLast() as T;
    _sink(1);

    return top;
  }

  List<T> _heapify(List<T> array) {
    int sinkNodeIndex = (array.length - 1) ~/ 2;

    while (sinkNodeIndex >= 1) {
      _sink(sinkNodeIndex);
      sinkNodeIndex--;
    }
  }

  void _sink(int nodeIndex) {
    int leftChildIndex = nodeIndex * 2;
    int rightChildIndex = leftChildIndex + 1;
    int minNodeIndex = leftChildIndex;

    // index can be unreachable
    T? leftChild =
        leftChildIndex >= _tree.length ? null : _tree[leftChildIndex];
    T? rightChild =
        rightChildIndex >= _tree.length ? null : _tree[rightChildIndex];

    if (leftChild == null) {
      return;
    }

    if (rightChild != null && leftChild.compareTo(rightChild) > 0) {
      minNodeIndex = rightChildIndex;
    }

    if ((_tree[minNodeIndex] as T).compareTo(_tree[nodeIndex] as T) < 0) {
      _swap(nodeIndex, minNodeIndex);
      _sink(minNodeIndex);
    }
  }

  void _swim(int nodeIndex) {
    if (nodeIndex <= 1) return;

    int parentIndex = nodeIndex ~/ 2;

    if ((_tree[nodeIndex] as T).compareTo(_tree[parentIndex] as T) < 0) {
      _swap(nodeIndex, parentIndex);
      _swim(parentIndex);
    }
  }

  void _swap(int i, int j) {
    T temp = _tree[i] as T;
    _tree[i] = _tree[j];
    _tree[j] = temp;
  }

  @override
  String toString() {
    return _tree.toString();
  }
}

Answer 1

I ended up doing like Irn's first suggestion. But when I do functions static they lost Type of the class so I needed to specify for each function. Also, making List<T?> instead of List ended up with me fighting against the compiler.

class PriorityQueue<T extends Comparable<T>> {
  List<T?> _tree;

  PriorityQueue._(List<T?> tree) : _tree = tree;

  factory PriorityQueue([List<T>? array]) {
    List<T?> newArray = [null, ...array ?? []];
    _heapify(newArray);

    return PriorityQueue._(newArray);
  }

  bool get isNotEmpty {
    return _tree.isNotEmpty;
  }

  void insert(T node) {
    _tree.add(node);
    _swim(_tree, _tree.length - 1);
  }

  void insertMultiple(List<T> array) {
    for (var element in array) {
      insert(element);
    }
  }

  T? removeTop() {
    if (_tree.length == 1) return null;

    _swap(_tree, 1, _tree.length - 1);
    T top = _tree.removeLast() as T;
    _sink(_tree, 1);

    return top;
  }

  void removeAll() {
    _tree = [null];
  }

  static void _heapify<T extends Comparable<T>>(List<T?> array) {
    int sinkNodeIndex = (array.length - 1) ~/ 2;

    while (sinkNodeIndex >= 1) {
      _sink(array, sinkNodeIndex);
      sinkNodeIndex--;
    }
  }

  static void _sink<T extends Comparable<T>>(List<T?> tree, int nodeIndex) {
    int leftChildIndex = nodeIndex * 2;
    int rightChildIndex = leftChildIndex + 1;
    int minNodeIndex = leftChildIndex;

    T? leftChild = leftChildIndex >= tree.length ? null : tree[leftChildIndex];
    T? rightChild =
        rightChildIndex >= tree.length ? null : tree[rightChildIndex];

    if (leftChild == null) {
      return;
    }

    if (rightChild != null && leftChild.compareTo(rightChild) > 0) {
      minNodeIndex = rightChildIndex;
    }

    if ((tree[minNodeIndex] as T).compareTo(tree[nodeIndex] as T) < 0) {
      _swap(tree, nodeIndex, minNodeIndex);
      _sink(tree, minNodeIndex);
    }
  }

  static void _swim<T extends Comparable<T>>(List<T?> tree, int nodeIndex) {
    if (nodeIndex <= 1) return;

    int parentIndex = nodeIndex ~/ 2;

    if ((tree[nodeIndex] as T).compareTo(tree[parentIndex] as T) < 0) {
      _swap(tree, nodeIndex, parentIndex);
      _swim(tree, parentIndex);
    }
  }

  static void _swap<T extends Comparable<T>>(List<T?> tree, int i, int j) {
    T temp = tree[i] as T;
    tree[i] = tree[j];
    tree[j] = temp;
  }

  @override
  String toString() {
    return _tree.toString();
  }
}

Answer 2

I would make all the helper functions. _heapify, _sink/_swim, even _swap, be static functions which take the list as argument. Then you can use them from anywhere, including inside the factory constructor.

Alternatively, you can change the constructor to returning:

  return PriorityQueue._(newArray).._heapify();

This creates the PriorityQueue object, and then calls the _heapify method on it, before returning the value.

(I'd also make _tree have type List<T> and not insert the extra null at the beginning. It's more efficient to add/subtract 1 from indices than it is to cast to T.)