RopeReader.mesa
written by Bill Paxton, January 1981
last edit by Paxton, September 13, 1982 9:33 am
last edit by McGregor, June 10, 1982 2:30 pm
last edit by Maxwell, January 5, 1983 8:36 am
last edit by Russ Atkinson, July 22, 1983 9:33 am
RopeReader provides fast inline access to characters in ropes
designed for speed in reading a sequence of characters, either forwards or backwards
from packed arrays (such as created by RopeIO)
or from text ropes (the packed sequence of characters variant)
create a reader by RopeReader.Create
reader: RopeReader.Ref ← RopeReader.Create[];
position it where you want to read by SetPosition
RopeReader.SetPosition[reader,rope,index];
where rope is to the one to read from, and index is the initial position for the reader
you can reposition a reader at any time
read its position in any of the following ways:
[rope,index] ← RopeReader.Position[reader];
rope ← RopeReader.GetRope[reader];
index ← RopeReader.GetIndex[reader];
to read in ascending order (left to right)
initialize position at index of first character to be read
for example, use 0 to start at beginning of rope
then call Get which reads to the right and increments the position
char ← RopeReader.Get[reader];
to read in descending order (right to left)
initialize position after first character to be read
for example, use size of rope to start at end
then call Backwards which reads to the left and decrements the position
char ← RopeReader.Backwards[reader];
can also get a character without changing the reader position
to look at the next character that Get would return, call Peek
char ← RopeReader.Peek[reader];
to look at what Backwards would return, call PeekBackwards
char ← RopeReader.PeekBackwards[reader];
can intermix reading or peeking to left and right
don't need to reinitialize the reader to change direction
if read off either end of rope, you can choose either to get an error or a client-specified character
there are equality and comparison routines that use readers for efficiency
Equal, EqSubstr, EqSubstrs
Compare, CompareSubstr, CompareSubstrs
operations are also provided to read a block of characters
destination given by either a REF TEXT or a REF chars array
can read either forward or backwards from source
RopeReader: CEDAR DEFINITIONS = BEGIN
***** RopeReader Declarations
Ref: TYPE = REF Body; -- Body of reader is a private record (declared below)
ROPE: TYPE = Rope.ROPE;
Offset: TYPE = INT;
MaxLen: Offset = Rope.MaxLen;
ReadOffEnd: ERROR;
***** RopeReader Operations
Create: PROC RETURNS [Ref];
SetPosition:
PROC [reader: Ref, rope:
ROPE, index: Offset ← 0] =
INLINE {
IF GetRope[reader]#rope
OR GetIndex[reader]#index
THEN {
reader.current ← reader.first ← reader.after ← 0;
reader.chars ← NIL; reader.text ← NIL;
reader.rope ← rope; reader.index ← index}};
SetIndex:
PROC [reader: Ref, index: Offset ← 0] =
INLINE {
IF GetIndex[reader]#index
THEN {
reader.current ← reader.first ← reader.after ← 0;
reader.chars ← NIL; reader.text ← NIL; reader.index ← index}};
BackupIndex:
PROC [reader: Ref, amount: Offset] =
INLINE {
SetIndex[reader, GetIndex[reader]-amount] };
BumpIndex:
PROC [reader: Ref, amount: Offset] =
INLINE {
SetIndex[reader, GetIndex[reader]+amount] };
Position:
PROC [reader: Ref]
RETURNS [rope:
ROPE, index: Offset] =
INLINE {
RETURN [reader.rope, reader.index+reader.current-reader.first] };
GetRope:
PROC [reader: Ref]
RETURNS [rope:
ROPE] =
INLINE {
RETURN [reader.rope] };
GetIndex:
PROC [reader: Ref]
RETURNS [index: Offset] =
INLINE
{
RETURN [reader.index+reader.current-reader.first] };
GetEndChar:
PROC [reader: Ref]
RETURNS [endChar: CHAR] = INLINE { RETURN [reader.endChar] };
Returns the current end char. This will be returned rather than giving ReadOffEnd error if CharForEndOfRope is true.
CharForEndOfRope:
PROC [reader: Ref]
RETURNS [
BOOLEAN] =
INLINE { RETURN [reader.charForEndOfRope] };
SetCharForEndOfRope:
PROC [reader: Ref, char:
CHAR] =
INLINE {
reader.endChar ← char; reader.charForEndOfRope ← TRUE };
ClearCharForEndOfRope:
PROC [reader: Ref] =
INLINE {
reader.charForEndOfRope ← FALSE };
ReaderProc: TYPE = PROC [reader: Ref] RETURNS [CHAR];
Get: ReaderProc = INLINE {
get character, then increment reader location
current: NAT;
IF (current←reader.current) >= reader.after
THEN
RETURN[ReadChar[reader,get]];
reader.current ← current+1;
RETURN[IF reader.txtFlag THEN reader.text[current] ELSE reader.chars[current]]};
Backwards: ReaderProc = INLINE {
decrement reader location, then get character
current: NAT;
IF (current←reader.current) <= reader.first
THEN
RETURN[ReadChar[reader,backwards]];
reader.current ← current ← current-1;
RETURN[IF reader.txtFlag THEN reader.text[current] ELSE reader.chars[current]]};
Peek: ReaderProc = INLINE {
get character without incrementing reader location
current: NAT;
IF (current←reader.current) >= reader.after
THEN
RETURN[ReadChar[reader,peek]];
RETURN[IF reader.txtFlag THEN reader.text[current] ELSE reader.chars[current]]};
PeekBackwards: ReaderProc = INLINE {
like Backwards, but doesn't change position
current: NAT;
IF (current←reader.current) <= reader.first
THEN
RETURN[ReadChar[reader,peekbackwards]];
RETURN[IF reader.txtFlag THEN reader.text[current-1] ELSE reader.chars[current-1]]};
Mode: PRIVATE TYPE = {get, backwards, peek, peekbackwards};
ReadChar: PRIVATE PROC [reader: Ref, mode: Mode] RETURNS [CHAR];
Here are some rope comparison operations that make use of readers for efficiency.
Equal:
PROC [r1,r2:
ROPE, rdr1,rdr2: Ref ←
NIL]
RETURNS [
BOOLEAN] =
INLINE {
uses readers rdr1 and rdr2 to read ropes r1 and r2 to test for equality
RETURN [EqSubstrs[r1,r2,0,0,MaxLen,rdr1,rdr2]] };
EqSubstrs:
PROC [r1,r2:
ROPE, start1,start2,len: Offset, rdr1,rdr2: Ref ←
NIL]
RETURNS [BOOLEAN];
uses readers rdr1 and rdr2 to read ropes r1 and r2 to test for equality
returns TRUE if r1 starting at start1 is same as
len chars of r2 starting at start2
returns FALSE if not enough chars available in either rope
i.e., if start1+len > size[r1] or start2+len > size[r2]
if rdr1 or rdr2 is NIL, gets own readers from cache
Compare:
PROC [r1,r2:
ROPE, rdr1,rdr2: Ref ←
NIL, case:
BOOLEAN ←
TRUE]
RETURNS [Basics.Comparison] = INLINE {
uses readers rdr1 and rdr2 to compare ropes r1 and r2
returns less for r1 < r2; equal for r1 = r2; and greater for r1 > r2
if ~case then all characters forced lowercase for comparison
RETURN [CompareSubstrs[r1,r2,0,MaxLen,0,MaxLen,rdr1,rdr2,case]] };
CompareSubstrs:
PROC [
r1,r2: ROPE, start1,len1,start2,len2: Offset,
rdr1,rdr2: Ref ← NIL, case: BOOLEAN ← TRUE]
RETURNS [Basics.Comparison];
uses readers rdr1 and rdr2 to compare substrings of ropes r1 and r2
if rdr1 or rdr2 is NIL, gets own readers from cache
The following operations provide for reading blocks of characters
GetText:
PROC [reader: Ref, txt: Rope.Text, length:
NAT ←
LAST[
NAT]]
RETURNS [count:
NAT];
appends characters to text from rope; returns number of characters
updates txt.length
BackwardsGetText:
PROC [reader: Ref, txt: Rope.Text, length:
NAT ←
LAST[
NAT]]
RETURNS [count: NAT];
appends characters to text from rope; returns number of characters
updates txt.length
GetString:
PROC [reader: Ref, str:
REF TEXT, length:
NAT ←
LAST[
NAT]]
RETURNS [count: NAT];
appends characters to string from rope; returns number of characters
updates str.length
BackwardsGetString:
PROC [reader: Ref, str:
REF TEXT, length:
NAT ←
LAST[
NAT]]
RETURNS [count: NAT];
appends characters to string from rope; returns number of characters
updates str.length
***** Private declarations
Chars: TYPE = REF READONLY CharsArray; -- CharsArray is a packed array of characters
CharsRope:
PROC [chars: Chars]
RETURNS [
ROPE];
create a ROPE from a CharsArray; this routine is mainly for internal use
GetChars:
PROC [
reader: Ref,
chars: REF CharsArray,
length: NAT ← LAST[NAT],
offset: NAT ← 0]
RETURNS [count: NAT];
appends characters to CharsArray from rope; returns number of characters
BackwardsGetChars:
PROC [
reader: Ref,
chars: REF CharsArray,
length: NAT ← LAST[NAT],
offset: NAT ← 0]
RETURNS [count: NAT];
The next routines provide a small cache of rope readers
so can avoid creating a lot of garbage readers
don't use these unless you are certain to free the reader at most once
no harm if fail to free it, but total chaos if you free it more than once
GetRopeReader: PROC RETURNS [reader: Ref];
FreeRopeReader: PROC [reader: Ref];
Body:
TYPE =
PRIVATE
RECORD [
current: NAT ← 0, -- index of current character
first: NAT ← 0, -- index of first character to read
after: NAT ← 0, -- index beyond last character to read
chars: Chars, -- character array that we are currently reading
text: Rope.Text, -- text rope that we are currently reading
rope: ROPE, -- rope that we are reading
index: Offset ← 0, -- index in rope of first character
txtFlag: BOOLEAN ← FALSE, -- if true, read from text. else read from chars
charForEndOfRope:
BOOLEAN ←
FALSE,
if true, return endChar; else give ERROR ReadOffEnd
endChar: CHAR ← 0C -- char to return when reach end of rope
];
charsPerPage: NAT = 512;
pagesPerArray: NAT = 16;
charsPerArray: NAT = charsPerPage*pagesPerArray;
CharsArray: TYPE = PACKED ARRAY [0..charsPerArray) OF CHAR;
StartRopeReader, StartRopeReaderMisc, StartRopeReaderGet: PROC;
END.