diff options
Diffstat (limited to 'src/library/scalax/collection/generic/covartest/SequenceTemplate.scala')
-rwxr-xr-x | src/library/scalax/collection/generic/covartest/SequenceTemplate.scala | 382 |
1 files changed, 0 insertions, 382 deletions
diff --git a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala deleted file mode 100755 index eab7904af8..0000000000 --- a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala +++ /dev/null @@ -1,382 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -// $Id: Sequence.scala 16092 2008-09-12 10:37:06Z nielsen $ - - -package scalax.collection.generic.covartest - -import util.control.Breaks._ -import scalax.collection.immutable.{List, Nil, ::} - -import Sequence._ - -trait SequenceTemplate[+CC[+B] <: SequenceTemplate[CC, B] with Sequence[B], +A] extends PartialFunction[Int, A] with OrderedIterableTemplate[CC, A] { -self /*: CC[A]*/ => - - /** Returns the length of the sequence. - * - * @return the sequence length. - */ - def length: Int - - /** Result of comparing <code>length</code> with operand <code>len</code>. - * returns <code>x</code> where - * <code>x < 0</code> iff <code>this.length < len</code> - * <code>x == 0</code> iff <code>this.length == len</code> - * <code>x > 0</code> iff <code>this.length > len</code>. - * - * The method as implemented here does not call length directly; its running time - * is O(length min len) instead of O(length). The method should be overwritten - * if computing length is cheap. - */ - def lengthCompare(len: Int): Int = { - var i = 0 - breakable { - for (_ <- this) { - i += 1 - if (i > len) break - } - } - i - len - } - - /** Should always be <code>length</code> */ - def size = length - - /** Is this partial function defined for the index <code>x</code>? - */ - def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length) - - /** Returns index of the first element satisying a predicate, or -1, if none exists. - * - * @note may not terminate for infinite-sized collections. - * @param p the predicate - */ - def indexWhere(p: A => Boolean): Int = indexWhere(p, 0) - - /** Returns length of longest segment starting from a start index `from` - * such that every element of the segment satisfies predicate `p`. - * @note may not terminate for infinite-sized collections. - * @param p the predicate - * @param from the start index - */ - def segmentLength(p: A => Boolean, from: Int): Int = { - var result = 0 - var i = from - breakable { - for (x <- this) { - if (i >= from && !p(x)) { result = i - from; break } - else i += 1 - } - } - result - } - - /** Returns length of longest prefix of this seqence - * such that every element of the prefix satisfies predicate `p`. - * @note may not terminate for infinite-sized collections. - * @param p the predicate - */ - def prefixLength(p: A => Boolean) = segmentLength(p, 0) - - /** Returns index of the first element starting from a start index - * satisying a predicate, or -1, if none exists. - * - * @note may not terminate for infinite-sized collections. - * @param p the predicate - * @param from the start index - */ - def indexWhere(p: A => Boolean, from: Int): Int = { - var result = -1 - var i = from - breakable { - for (x <- this) { - if (i >= from && p(x)) { result = i; break } - else i += 1 - } - } - result - } - - /** Returns index of the first element satisying a predicate, or -1. - * - * @deprecated Use `indexWhere` instead - */ - @deprecated def findIndexOf(p: A => Boolean): Int = indexWhere(p) - - /** Returns the index of the first occurence of the specified - * object in this iterable object. - * - * @note may not terminate for infinite-sized collections. - * @param elem element to search for. - * @return the index in this sequence of the first occurence of the - * specified element, or -1 if the sequence does not contain - * this element. - */ - def indexOf[B >: A](elem: B): Int = indexOf(elem, 0) - - /** Returns the index of the first occurence of the specified - * object in this iterable object, starting from a start index, or - * -1, if none exists. - * - * @note may not terminate for infinite-sized collections. - * @param elem element to search for. - */ - def indexOf[B >: A](elem: B, from: Int): Int = indexWhere(elem ==, from) - - /** Returns the index of the last occurence of the specified element - * in this sequence, or -1 if the sequence does not contain this element. - * - * @param elem element to search for. - * @return the index in this sequence of the last occurence of the - * specified element, or -1 if the sequence does not contain - * this element. - */ - def lastIndexOf[B >: A](elem: B): Int = lastIndexOf(elem, length - 1) - - /** Returns the index of the last - * occurence of the specified element in this sequence - * before or at a given end index, - * or -1 if the sequence does not contain this element. - * - * @param elem element to search for. - * @param end the end index - */ - def lastIndexOf[B >: A](elem: B, end: Int): Int = { - var i = end - val it = reversedElements - while (it.hasNext && it.next != elem) i -= 1 - i - } - - /** Returns index of the last element satisying a predicate, or -1, if none exists. - * - * @param p the predicate - * @return the index of the last element satisfying <code>p</code>, - * or -1 if such an element does not exist - */ - def lastIndexWhere(p: A => Boolean): Int = lastIndexWhere(p, length - 1) - - /** Returns index of the last element not exceeding a given end index - * and satisying a predicate, or -1 if none exists. - * - * @param end the end index - * @param p the predicate - */ - def lastIndexWhere(p: A => Boolean, end: Int): Int = { - var i = end - val it = reversedElements - while (it.hasNext && (i > end || !p(it.next))) i -= 1 - i - } - - /** A sequence of type <code>C</code> consisting of all elements of - * this sequence in reverse order. - * @note the operation is implemented by building a new sequence - * from <code>this(length - 1), ..., this(0)</code> - * If random access is inefficient for the given sequence implementation, - * this operation should be overridden. - */ - def reverse: CC[A] = { - var xs: List[A] = List() - for (x <- this) - xs = x :: xs - val b = newBuilder[A] - for (x <- xs) - b += x - b.result - } - - /** The elements of this sequence in reversed order - */ - def reversedElements: Iterator[A] = reverse.elements - - /** - * Checks whether the argument sequence is contained at the - * specified index within the receiver object. - * - * If the both the receiver object, <code>this</code> and - * the argument, <code>that</code> are infinite sequences - * this method may not terminate. - * - * @return true if <code>that</code> is contained in - * <code>this</code>, at the specified index, otherwise false - * - * @see String.startsWith - */ - def startsWith[B](that: Sequence[B], offset: Int): Boolean = { - val i = elements.drop(offset) - val j = that.elements - while (j.hasNext && i.hasNext && i.next == j.next) {} - !j.hasNext - } - - /** - * Check whether the receiver object starts with the argument sequence. - * - * @return true if <code>that</code> is a prefix of <code>this</code>, - * otherwise false - * - * @see Sequence.startsWith - */ - def startsWith[B](that: Sequence[B]): Boolean = startsWith(that, 0) - - /** @return true if this sequence end with that sequence - * @see String.endsWith - */ - def endsWith[B](that: Sequence[B]): Boolean = { - val i = this.elements.drop(length - that.length) - val j = that.elements - while (i.hasNext && j.hasNext && i.next == j.next) () - !j.hasNext - } - - /** @return -1 if <code>that</code> not contained in this, otherwise the - * index where <code>that</code> is contained - * @see String.indexOf - */ - def indexOf[B >: A](that: Sequence[B]): Int = { - var i = 0 - var s: Sequence[A] = thisCC - while (!s.isEmpty && !(s startsWith that)) { - i += 1 - s = s drop 1 - } - if (!s.isEmpty || that.isEmpty) i else -1 - } - - /** Tests if the given value <code>elem</code> is a member of this - * sequence. - * - * @param elem element whose membership has to be tested. - * @return <code>true</code> iff there is an element of this sequence - * which is equal (w.r.t. <code>==</code>) to <code>elem</code>. - */ - def contains(elem: Any): Boolean = exists (_ == elem) - - /** Computes the union of this sequence and the given sequence - * <code>that</code>. - * - * @param that the sequence of elements to add to the sequence. - * @return an sequence containing the elements of this - * sequence and those of the given sequence <code>that</code> - * which are not contained in this sequence. - */ - def union[B >: A](that: Sequence[B]): CC[B] = this ++ (that diff thisCC) - - /** Computes the difference between this sequence and the given sequence - * <code>that</code>. - * - * @param that the sequence of elements to remove from this sequence. - * @return this sequence without the elements of the given sequence - * <code>that</code>. - */ - def diff[B >: A](that: Sequence[B]): CC[A] = this remove (that contains _) - - /** Computes the intersection between this sequence and the given sequence - * <code>that</code>. - * - * @param that the sequence to intersect. - * @return the sequence of elements contained both in this sequence and - * in the given sequence <code>that</code>. - */ - def intersect[B >: A](that: Sequence[B]): CC[A] = this filter(that contains _) - - /** Builds a new sequence from this sequence in which any duplicates (wrt to ==) removed. - * Among duplicate elements, only the first one is retained in the result sequence - */ - def removeDuplicates: CC[A] = { - val b = newBuilder[A] - var seen = Set[A]() - for (x <- this) { - if (!(seen contains x)) { - b += x - seen += x - } - } - b.result - } - - /** Returns a sequence of given length containing the elements of this sequence followed by zero - * or more occurrences of given elements. If this sequence is already at least as long as given - * length, it is returned directly. Otherwise, a new sequence is created consisting of the elements - * of this sequence followed by enough occurrences of the given elements to reach the given length. - */ - def padTo[B >: A](len: Int, elem: B): CC[B] = { - var diff = len - length - val b = newBuilder[B] //!!! drop [B] and get surprising results! - b ++= thisCC - while (diff > 0) { - b += elem - diff -=1 - } - b.result - } - - /** - * Overridden for efficiency. - * - * @return the sequence itself - */ - override def toSequence: Sequence[A] = thisCC - - def indices: Range = 0 until length - - /** Creates a view of this iterable @see OrderedIterable.View - */ - override def view: SequenceView[CC, A] = new SequenceView[CC, A] { // !!! Martin: We should maybe infer the type parameters here? - val origin: Sequence[_] = thisCC - val elements: Iterator[A] = self.elements - val length: Int = self.length - def apply(idx: Int): A = self.apply(idx) - } - - /** A sub-sequence view starting at index `from` - * and extending up to (but not including) index `until`. - * - * @param from The index of the first element of the slice - * @param until The index of the element following the slice - * @note The difference between `view` and `slice` is that `view` produces - * a view of the current sequence, whereas `slice` produces a new sequence. - * - * @note view(from, to) is equivalent to view.slice(from, to) - */ - override def view(from: Int, until: Int): SequenceView[CC, A] = view.slice(from, until) - - /** Returns index of the last element satisying a predicate, or -1. - * @deprecated use `lastIndexWhere` instead - */ - @deprecated def findLastIndexOf(p: A => Boolean): Int = lastIndexWhere(p) - - /** A sub-sequence starting at index <code>from</code> - * and extending up to the length of the current sequence - * - * @param from The index of the first element of the slice - * @throws IndexOutOfBoundsException if <code>from < 0</code> - * @deprecated use <code>drop</code> instead - */ - @deprecated def slice(from: Int): Sequence[A] = slice(from, length) - - /** @deprecated Should be replaced by - * - * <code>(s1, s2) forall { case (x, y) => f(x, y) }</code> - */ - @deprecated def equalsWith[B](that: Sequence[B])(f: (A,B) => Boolean): Boolean = { - val i = this.elements - val j = that.elements - while (i.hasNext && j.hasNext && f(i.next, j.next)) () - !i.hasNext && !j.hasNext - } - - /** Is <code>that</code> a slice in this? - * @deprecated Should be repaced by <code>indexOf(that) != -1</code> - */ - @deprecated def containsSlice[B](that: Sequence[B]): Boolean = indexOf(that) != -1 - -} |