Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /smlnj-lib/trunk/Util/bit-array-sig.sml
ViewVC logotype

Annotation of /smlnj-lib/trunk/Util/bit-array-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2144 - (view) (download)

1 : monnier 2 (* bit-array-sig.sml
2 :     *
3 :     * COPYRIGHT (c) 1995 by AT&T Bell Laboratories. See COPYRIGHT file for details.
4 :     *
5 :     * Signature for mutable bit array. The model here treats bit array as an
6 :     * array of bools.
7 :     *)
8 :    
9 :     signature BIT_ARRAY =
10 :     sig
11 :    
12 :     include MONO_ARRAY
13 :    
14 :     val fromString : string -> array
15 :     (* The string argument gives a hexadecimal
16 :     * representation of the bits set in the
17 :     * array. Characters 0-9, a-f and A-F are
18 :     * allowed. For example,
19 :     * fromString "1af8" = 0001101011111000
20 :     * (by convention, 0 corresponds to false and 1 corresponds
21 :     * to true, bit 0 appears on the right,
22 :     * and indices increase to the left)
23 :     * The length of the array will be 4*(size string).
24 :     * Raises LibBase.BadArg if a non-hexadecimal character
25 :     * appears in the string.
26 :     *)
27 :    
28 :     val bits : (int * int list) -> array
29 :     (* Create array of the given length with the indices of its set bits
30 :     * given by the list argument.
31 :     * Raises Subscript if a list item is < 0 or >= length.
32 :     *)
33 :    
34 :     val getBits : array -> int list
35 :     (* Returns list of bits set in bit array, in increasing
36 :     * order of indices.
37 :     *)
38 :    
39 :     val toString : array -> string
40 :     (* Inverse of stringToBits.
41 :     * The bit array is zero-padded to the next
42 :     * length that is a multiple of 4.
43 :     *)
44 :    
45 :     val isZero : array -> bool
46 :     (* Returns true if and only if no bits are set. *)
47 :    
48 :     val extend0 : (array * int) -> array
49 :     val extend1 : (array * int) -> array
50 :     (* Extend bit array by 0's or 1's to given length.
51 :     * If bit array is already >= argument length, return a copy
52 :     * of the bit array.
53 :     * Raises Size if length < 0.
54 :     *)
55 :    
56 :     val eqBits : (array * array) -> bool
57 :     (* true if set bits are identical *)
58 :     val equal : (array * array) -> bool
59 :     (* true if same length and same set bits *)
60 :    
61 :     val andb : (array * array * int) -> array
62 :     val orb : (array * array * int) -> array
63 :     val xorb : (array * array * int) -> array
64 :     (* Create new array of the given length
65 :     * by logically combining bits of original
66 :     * array using and, or and xor, respectively.
67 :     * If necessary, the array are
68 :     * implicitly extended by 0 to be the same length
69 :     * as the new array.
70 :     *)
71 :    
72 :     val notb : array -> array
73 :     (* Create new array with all bits of original
74 :     * array inverted.
75 :     *)
76 :    
77 :     val lshift : (array * int) -> array
78 :     (* lshift(ba,n) creates a new array by
79 :     * inserting n 0's on the right of ba.
80 :     * The new array has length n + length ba.
81 :     *)
82 :    
83 :     val rshift : (array * int) -> array
84 :     (* rshift(ba,n) creates a new array of
85 :     * of length max(0,length ba - n) consisting
86 :     * of bits n,n+1,...,length ba - 1 of ba.
87 :     * If n >= length ba, the new arraarray has length 0.
88 :     *)
89 :    
90 :     (* mutable operations for array *)
91 :    
92 :     val setBit : (array * int) -> unit
93 :     val clrBit : (array * int) -> unit
94 :     (* Update value at given index to new value.
95 :     * Raises Subscript if index < 0 or >= length.
96 :     * setBit(ba,i) = update(ba,i,true)
97 :     * clrBit(ba,i) = update(ba,i,false)
98 :     *)
99 :    
100 :     val union : array -> array -> unit
101 :     val intersection : array -> array -> unit
102 :     (* Or (and) second bitarray into the first. Second is
103 :     * implicitly truncated or extended by 0's to match
104 :     * the length of the first.
105 :     *)
106 :    
107 :     val complement : array -> unit
108 :     (* Invert all bits. *)
109 :    
110 :     end (* BIT_ARRAY *)
111 :     where type elem = bool

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0