Coverage report for lib/src/line_splitting/solve_state_queue.dart

// Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file

// for details. All rights reserved. Use of this source code is governed by a

// BSD-style license that can be found in the LICENSE file.

library dart_style.src.line_splitting.solve_state_queue;

import 'line_splitter.dart';

import 'solve_state.dart';

/// A priority queue of [SolveStates] to consider while line splitting.

///

/// This is based on the [HeapPriorityQueue] class from the "collection"

/// package, but is modified to handle the "overlap" logic that allows one

/// [SolveState] to supercede another.

///

/// States are stored internally in a heap ordered by cost, the number of

/// overflow characters. When a new state is added to the heap, it will be

/// discarded, or a previously enqueued one will be discarded, if two overlap.

class SolveStateQueue {

  /// Initial capacity of a queue when created, or when added to after a [clear].

  /// Number can be any positive value. Picking a size that gives a whole

  /// number of "tree levels" in the heap is only done for aesthetic reasons.

  static const int _INITIAL_CAPACITY = 7;

  LineSplitter _splitter;

  /// List implementation of a heap.

  List<SolveState> _queue = new List<SolveState>(_INITIAL_CAPACITY);

  /// Number of elements in queue.

  /// The heap is implemented in the first [_length] entries of [_queue].

  int _length = 0;

    // Only do this once.

  }

  /// Add [state] to the queue.

  ///

  /// Grows the capacity if the backing list is full.

    }

  }

    // Remove the highest priority state.

    // Fill the gap with the one at the end of the list and re-heapify.

    }

    return result;

  }

  /// Orders this state relative to [other].

  ///

  /// This is a best-first ordering that prefers cheaper states even if they

  /// overflow because this ensures it finds the best solution first as soon as

  /// it finds one that fits in the page so it can early out.

    // TODO(rnystrom): It may be worth sorting by the estimated lowest number

    // of overflow characters first. That doesn't help in cases where there is

    // a solution that fits, but may help in corner cases where there is no

    // fitting solution.

  }

  /// Compares the overflow and cost of [a] to [b].

    }

  }

  /// Distinguish states based on the rule values just so that states with the

  /// same cost range but different rule values don't get considered identical

  /// and inadvertantly merged.

    }

    // The way SolveStates are expanded should guarantee that we never generate

    // the exact same state twice. Getting here implies that that failed.

    throw "unreachable";

  }

  /// Determines if any already enqueued state overlaps [state].

  ///

  /// If so, chooses the best and discards the other. Returns `true` in this

  /// case. Otherwise, returns `false`.

    // Count positions from one instead of zero. This gives the numbers some

    // nice properties. For example, all right children are odd, their left

    // sibling is even, and the parent is found by shifting right by one.

    // Valid range for position is [1.._length], inclusive.

    var position = 1;

    // Pre-order depth first search, omit child nodes if the current node has

    // lower priority than [object], because all nodes lower in the heap will

    // also have lower priority.

    do {

          // The old state is better, so just discard the new one.

          return true;

          // The new state is better than the enqueued one, so replace it.

          return true;

        } else {

          // We can't merge them, so sort by their bound rule values.

        }

      }

        // Element may be in subtree. Continue with the left child, if any.

          position = leftChildPosition;

          continue;

        }

      }

      // Find the next right sibling or right ancestor sibling.

      do {

          // While position is a right child, go to the parent.

        }

        // Then go to the right sibling of the left child.

    return false;

  }

  /// Place [element] in heap at [index] or above.

  ///

  /// Put element into the empty cell at `index`. While the `element` has

  /// higher priority than the parent, swap it with the parent.

      index = parentIndex;

    }

  }

  /// Place [element] in heap at [index] or above.

  ///

  /// Put element into the empty cell at `index`. While the `element` has lower

  /// priority than either child, swap it with the highest priority child.

      var minChildIndex;

      var minChild;

        minChild = leftChild;

        minChildIndex = leftChildIndex;

      } else {

        minChild = rightChild;

        minChildIndex = rightChildIndex;

      }

        return;

      }

      index = minChildIndex;

    }

        index = leftChildIndex;

      }

    }

  }

}