<> <> <> <<>> <> <<>> DIRECTORY Ascii USING [Upper], RefID USING [ID, Release, Seal, Unseal], RegularExpression USING [CreateFromRope, Finder, SearchRope], Rope USING [Compare, Equal, Fetch, InlineFetch, Length, ROPE, SkipTo, Substr], Soundex USING [NameToCode], LoganBerry, LoganQuery; LoganQueryImpl: CEDAR PROGRAM IMPORTS Ascii, RefID, RegularExpression, Rope, Soundx: Soundex, LoganBerry EXPORTS LoganQuery ~ BEGIN OPEN LoganQuery; ROPE: TYPE ~ Rope.ROPE; <> <> NextEntry: PUBLIC PROC [cursor: ComplexCursor, dir: CursorDirection _ increasing] RETURNS [entry: LoganBerry.Entry] = { <> <> IF cursor.class.retrieve = NIL THEN RETURN[NIL]; RETURN[cursor.class.retrieve[cursor, dir]]; }; EndGenerate: PUBLIC PROC [cursor: ComplexCursor] RETURNS [] = { <> IF cursor.class.destroy = NIL THEN RETURN; cursor.class.destroy[cursor]; }; <> <<$Simple>> SimpleClass: QueryClass = NEW[QueryClassRec _ [$Simple, SimpleRetrieve, SimpleDestroy]]; <<>> <> SimpleRetrieve: RetrieveProc = { <<[cursor: ComplexCursor, dir: CursorDirection _ increasing] RETURNS [entry: LoganBerry.Entry]>> RETURN[LoganBerry.NextEntry[cursor: cursor.data, dir: dir]]; }; SimpleDestroy: DestroyProc = { <<[cursor: ComplexCursor] RETURNS []>> LoganBerry.EndGenerate[cursor: cursor.data]; }; GenerateEntries: PUBLIC PROC [db: LoganBerry.OpenDB, key: LoganBerry.AttributeType, start: LoganBerry.AttributeValue _ NIL, end: LoganBerry.AttributeValue _ NIL] RETURNS [cursor: ComplexCursor] = { <> <> cursor.class _ SimpleClass; cursor.data _ LoganBerry.GenerateEntries[db: db, key: key, start: start, end: end]; }; <<>> <<$Filter>> FilterClass: QueryClass = NEW[QueryClassRec _ [$Filter, FilterRetrieve, FilterDestroy]]; <<>> FilterCursor: TYPE = REF FilterCursorRec; FilterCursorRec: TYPE = RECORD [ input: ComplexCursor, pattern: ROPE, filter: FilterProc, atype: LoganBerry.AttributeType, stopNG: BOOLEAN _ FALSE ]; FilterRetrieve: RetrieveProc = { <<[cursor: ComplexCursor, dir: CursorDirection _ increasing] RETURNS [entry: LoganBerry.Entry]>> fc: FilterCursor = NARROW[RefID.Unseal[cursor.data]]; match, nothingGreater: BOOLEAN _ FALSE; numAtypes: INT; entry _ NextEntry[fc.input, dir]; UNTIL match OR entry = NIL DO <> numAtypes _ 0; FOR e: LoganBerry.Entry _ entry, e.rest WHILE e # NIL DO IF e.first.type = fc.atype THEN { numAtypes _ numAtypes + 1; [match, nothingGreater] _ fc.filter[e.first.value, fc.pattern]; IF match THEN EXIT; }; ENDLOOP; IF NOT match THEN IF nothingGreater AND fc.stopNG AND dir = increasing AND numAtypes = 1 THEN entry _ NIL -- can stop before actual end of input ELSE entry _ NextEntry[fc.input, dir]; ENDLOOP; }; FilterDestroy: DestroyProc = { <<[cursor: ComplexCursor] RETURNS []>> fc: FilterCursor = NARROW[RefID.Unseal[cursor.data]]; EndGenerate[fc.input]; [] _ RefID.Release[cursor.data]; }; FilterEntries: PUBLIC PROC [input: ComplexCursor, pattern: ROPE, filter: FilterProc, atype: LoganBerry.AttributeType, stopIfNothingGreater: BOOLEAN _ FALSE] RETURNS [output: ComplexCursor] = { <> fc: FilterCursor _ NEW[FilterCursorRec]; fc.input _ input; fc.pattern _ pattern; fc.filter _ filter; fc.atype _ atype; fc.stopNG _ stopIfNothingGreater; output.class _ FilterClass; output.data _ RefID.Seal[fc]; }; <<$Merger>> MergerClass: QueryClass = NEW[QueryClassRec _ [$Merger, MergerRetrieve, MergerDestroy]]; <<>> MergerCursor: TYPE = REF MergerCursorRec; MergerCursorRec: TYPE = RECORD [ input: ARRAY [0..1] OF ComplexCursor, atype: LoganBerry.AttributeType, prefetch: BOOLEAN _ FALSE, -- is there a prefetched entry? prefetchEntry: LoganBerry.Entry, -- prefetched entry if one exists prefetchValue: LoganBerry.AttributeValue, -- value saved for performance reasons prefetchInput: [0..1] _ 0, -- which input the prefetch came from prefetchDir: CursorDirection _ increasing -- direction of prefetch ]; MergerRetrieve: RetrieveProc = { <<[cursor: ComplexCursor, dir: CursorDirection _ increasing] RETURNS [entry: LoganBerry.Entry]>> mc: MergerCursor = NARROW[RefID.Unseal[cursor.data]]; newInput: [0..1]; newEntry: LoganBerry.Entry; newValue: LoganBerry.AttributeValue; returnNew: BOOLEAN; IF mc.prefetch AND NOT mc.prefetchDir = dir THEN { -- prefetched in wrong direction <> [] _ NextEntry[mc.input[mc.prefetchInput], dir]; mc.prefetch _ FALSE; }; IF NOT mc.prefetch THEN { -- go ahead and get an entry mc.prefetchEntry _ NextEntry[mc.input[0], dir]; mc.prefetchValue _ GetAttributeValue[mc.prefetchEntry, mc.atype]; mc.prefetchInput _ 0; mc.prefetchDir _ dir; mc.prefetch _ TRUE; }; newInput _ ABS[1-mc.prefetchInput]; newEntry _ NextEntry[mc.input[newInput], dir]; IF mc.prefetchEntry = NIL THEN -- one input already exhausted RETURN[newEntry]; IF newEntry = NIL THEN { -- just exhausted input entry _ mc.prefetchEntry; mc.prefetchEntry _ NIL; mc.prefetchInput _ newInput; RETURN[entry]; }; newValue _ GetAttributeValue[newEntry, mc.atype]; returnNew _ SELECT Rope.Compare[newValue, mc.prefetchValue, FALSE] FROM less => (dir = increasing), greater => (dir = decreasing), ENDCASE => TRUE; IF returnNew THEN { entry _ newEntry; } ELSE { entry _ mc.prefetchEntry; mc.prefetchEntry _ newEntry; mc.prefetchValue _ newValue; mc.prefetchInput _ newInput; }; }; MergerDestroy: DestroyProc = { <<[cursor: ComplexCursor] RETURNS []>> mc: MergerCursor = NARROW[RefID.Unseal[cursor.data]]; EndGenerate[mc.input[0]]; EndGenerate[mc.input[1]]; [] _ RefID.Release[cursor.data]; }; MergeEntries: PUBLIC PROC [input1, input2: ComplexCursor, atype: LoganBerry.AttributeType] RETURNS [output: ComplexCursor] = { <> mc: MergerCursor _ NEW[MergerCursorRec]; mc.input[0] _ input1; mc.input[1] _ input2; mc.atype _ atype; mc.prefetch _ FALSE; output.class _ MergerClass; output.data _ RefID.Seal[mc]; }; <> Equal: PUBLIC FilterProc = { <<[value: ROPE, pattern: ROPE] RETURNS [match: BOOLEAN, nothingGreater: BOOLEAN _ FALSE]>> <> SELECT Rope.Compare[s1: value, s2: pattern, case: FALSE] FROM less => match _ FALSE; equal => match _ TRUE; greater => {match _ FALSE; nothingGreater _ TRUE}; ENDCASE => ERROR; }; Prefix: PUBLIC FilterProc = { <<[value: ROPE, pattern: ROPE] RETURNS [match: BOOLEAN, nothingGreater: BOOLEAN _ FALSE]>> <> SELECT Rope.Compare[s1: Rope.Substr[value, 0, Rope.Length[pattern]], s2: pattern, case: FALSE] FROM less => match _ FALSE; equal => match _ TRUE; greater => {match _ FALSE; nothingGreater _ TRUE} ENDCASE => ERROR; }; Wildcard: PUBLIC FilterProc = { <<[value: ROPE, pattern: ROPE] RETURNS [match: BOOLEAN, nothingGreater: BOOLEAN _ FALSE]>> <> <> SubMatch: PROC [pstart: INT, plen: INT, vstart: INT, vlen: INT] RETURNS [match: BOOLEAN, nothingGreater: BOOLEAN _ FALSE] = { <> pchar, vchar: CHAR; WHILE plen > 0 DO pchar _ Ascii.Upper[pattern.Fetch[pstart]]; IF pchar = '* THEN { <> IF plen = 1 THEN RETURN [match: TRUE]; <> { -- first, accept the * newpstart: INT = pstart + 1; newplen: INT = plen - 1; newvstart: INT _ vstart; newvlen: INT _ vlen; WHILE newvlen >= 0 DO IF SubMatch[newpstart, newplen, newvstart, newvlen].match THEN RETURN [match: TRUE]; newvstart _ newvstart + 1; newvlen _ newvlen - 1; ENDLOOP; }; RETURN [match: FALSE]; }; IF vlen = 0 THEN RETURN [match: FALSE]; <> vchar _ Ascii.Upper[value.Fetch[vstart]]; IF pchar # vchar THEN RETURN [match: FALSE, nothingGreater: vchar > pchar]; pstart _ pstart + 1; plen _ plen - 1; vstart _ vstart + 1; vlen _ vlen - 1; ENDLOOP; IF vlen = 0 THEN RETURN [match: TRUE] ELSE RETURN [match: FALSE, nothingGreater: TRUE]; }; [match, nothingGreater] _ SubMatch [0, pattern.Length[], 0, value.Length[]]; }; finderCache: RECORD[ -- cache last RE finder to improve performance pattern: ROPE, finder: RegularExpression.Finder ]; RE: PUBLIC FilterProc = { <<[value: ROPE, pattern: ROPE] RETURNS [match: BOOLEAN, nothingGreater: BOOLEAN _ FALSE]>> <> finder: RegularExpression.Finder; purePrefix: ROPE; i: INT; IF Rope.Equal[s1: pattern, s2: finderCache.pattern, case: FALSE] THEN -- get from cache finder _ finderCache.finder ELSE { finder _ RegularExpression.CreateFromRope[pattern: pattern, ignoreCase: TRUE, addBounds: TRUE]; finderCache.pattern _ pattern; finderCache.finder _ finder; }; match _ RegularExpression.SearchRope[finder, value].found; IF NOT match THEN { -- see if something greater might match i _ Rope.SkipTo[s: pattern, skip: "\'#[^$*+(\\<{!"]; -- look for special chars IF NOT i = Rope.Length[pattern] AND Rope.InlineFetch[pattern, i] = '* THEN -- could be zero of previous char i _ i-1; purePrefix _ Rope.Substr[base: pattern, len: i]; IF Rope.Compare[s1: Rope.Substr[value, 0, Rope.Length[purePrefix]], s2: purePrefix, case: FALSE] = greater THEN nothingGreater _ TRUE; }; }; Soundex: PUBLIC FilterProc = { <<[value: ROPE, pattern: ROPE] RETURNS [match: BOOLEAN, nothingGreater: BOOLEAN _ FALSE]>> <> ch: CHAR _ Ascii.Upper[Rope.InlineFetch[pattern,0]]; <> SELECT Ascii.Upper[Rope.InlineFetch[value,0]] FROM = ch => match _ Rope.Equal[Soundx.NameToCode[value], Soundx.NameToCode[pattern]]; < ch => match _ FALSE; > ch => {match _ FALSE; nothingGreater _ TRUE}; ENDCASE => ERROR; }; <> GetAttributeValue: PROC [entry: LoganBerry.Entry, type: LoganBerry.AttributeType] RETURNS [LoganBerry.AttributeValue] ~ { FOR e: LoganBerry.Entry _ entry, e.rest WHILE e # NIL DO IF e.first.type = type THEN RETURN[e.first.value]; ENDLOOP; RETURN[NIL]; }; END. <> <> << >> <> <> <<>> <> <> <<>> <> <> <<>> <> <> <<>> <> <> <<>> <> <> <> <> <> <> <<>>