forked from dylan-lang/collection-extensions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
vecsearch.dylan
83 lines (78 loc) · 3.6 KB
/
vecsearch.dylan
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
module: vector-search
author: Robert Stockton ([email protected])
synopsis: Provides a small assortment of specialized operations for
searching and modifying <vector>s. These
operations are analogous to existing collection operations but
provide keywords and efficiency improvements which are
meaningful only within the more limited domain.
//======================================================================
//
// Copyright (c) 1994 Carnegie Mellon University
// Copyright (c) 1998, 1999, 2000 Gwydion Dylan Maintainers
// All rights reserved.
//
// Use and copying of this software and preparation of derivative
// works based on this software are permitted, including commercial
// use, provided that the following conditions are observed:
//
// 1. This copyright notice must be retained in full on any copies
// and on appropriate parts of any derivative works.
// 2. Documentation (paper or online) accompanying any system that
// incorporates this software, or any part of it, must acknowledge
// the contribution of the Gwydion Project at Carnegie Mellon
// University, and the Gwydion Dylan Maintainers.
//
// This software is made available "as is". Neither the authors nor
// Carnegie Mellon University make any warranty about the software,
// its performance, or its conformity to any specification.
//
// Bug reports should be sent to <[email protected]>; questions,
// comments and suggestions are welcome at <[email protected]>.
// Also, see http://www.gwydiondylan.org/ for updates and documentation.
//
//======================================================================
//======================================================================
// The "vector-search" module provides basic search and replace capabilities
// upon restricted subsets of <sequence> -- primarily <vector>.
// Exploiting the known properties of these types yields
// substantially better performance than can be achieved for sequences in
// general.
//
// The following functions are supplied:
//
// find-first-key vector predicate? #key start end failure => key
// Find the index of first element (after start but before end) of a
// vector which satisfies the given predicate. If no matching element is
// found, return failure. The defaults for start, end and failure are,
// respectively, 0, size(vector), and #f. This function is like
// find-key, but accepts start: and end: rather than skip:.)
//
// find-last-key vector predicate? #key start end failure => key
// This is like find-first-key, but goes backward from end.
//======================================================================
// Find the index of first element (after "from") of a vector which
// satisfies the given predicate. (Like find-key, but accepts start: and end:
// rather than skip:.)
define method find-first-key(seq :: <vector>, pred? :: <function>,
#key start = 0, end: last, failure: fail)
block (return)
let sz = size(seq);
let last = if (last & last < sz) last else sz end if;
for (i :: <integer> from start below last)
if (pred?(seq[i])) return(i) end if;
finally fail
end for
end block
end method find-first-key;
// Like find-first-key, but goes backward from the end (or from before end:).
define method find-last-key(seq :: <vector>, pred? :: <function>,
#key start = 0, end: last, failure: fail)
block (return)
let sz = size(seq);
let last = if (last & last < sz) last else sz end if;
for (i from last - 1 to start by -1)
if (pred?(seq[i])) return(i) end if;
finally fail
end for
end block
end method find-last-key;