Skip to content
This repository
Fetching contributors…

Cannot retrieve contributors at this time

file 101 lines (86 sloc) 3.357 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2006-2011, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */


package scala.collection
package generic

/** Any collection (including maps) whose keys (or elements) are ordered.
*
* @author Sean McDirmid
* @since 2.8
*/
trait Sorted[K, +This <: Sorted[K, This]] {
  def ordering : Ordering[K]

  /** The current collection */
  protected def repr: This

  /** return as a projection the set of keys in this collection */
  def keySet: SortedSet[K]

  /** Returns the first key of the collection. */
  def firstKey: K

  /** Returns the last key of the collection. */
  def lastKey: K

  /** Comparison function that orders keys. */
  def compare(k0: K, k1: K): Int = ordering.compare(k0, k1);

  /** Creates a ranged projection of this collection. Any mutations in the
* ranged projection will update this collection and vice versa. Note: keys
* are not garuanteed to be consistent between this collection and the projection.
* This is the case for buffers where indexing is relative to the projection.
*
* @param from The lower-bound (inclusive) of the ranged projection.
* <code>None</code> if there is no lower bound.
* @param until The upper-bound (exclusive) of the ranged projection.
* <code>None</code> if there is no upper bound.
*/
  def rangeImpl(from: Option[K], until: Option[K]): This

  /** Creates a ranged projection of this collection with no upper-bound.
*
* @param from The lower-bound (inclusive) of the ranged projection.
*/
  def from(from: K): This = rangeImpl(Some(from), None)

  /** Creates a ranged projection of this collection with no lower-bound.
*
* @param until The upper-bound (exclusive) of the ranged projection.
*/
  def until(until: K): This = rangeImpl(None, Some(until))

  /** Creates a ranged projection of this collection with both a lower-bound
* and an upper-bound.
*
* @param from The upper-bound (exclusive) of the ranged projection.
* @param until ...
* @return ...
*/
  def range(from: K, until: K): This = rangeImpl(Some(from), Some(until))

  /** Create a range projection of this collection with no lower-bound.
* @param to The upper-bound (inclusive) of the ranged projection.
*/
  def to(to: K): This = {
    // tough!
    val i = keySet.from(to).iterator
    if (i.isEmpty) return repr
    val next = i.next
    if (next == to)
      if (i.isEmpty) repr
      else until(i.next)
    else
      until(next)
  }

  protected def hasAll(j: Iterator[K]): Boolean = {
    val i = keySet.iterator
    if (i.isEmpty) return j.isEmpty

    var in = i.next;
    while (j.hasNext) {
      val jn = j.next;
      while ({
        val n = compare(jn, in);
        if (n == 0) false;
        else if (n < 0) return false;
        else if (!i.hasNext) return false;
        else true;
      }) in = i.next;
    }
    true
  }
}
Something went wrong with that request. Please try again.