@q file: set.w@>
@q%   Copyright Dave Bone 1998 - 2015@>
@q% /*@>
@q%    This Source Code Form is subject to the terms of the Mozilla Public@>
@q%    License, v. 2.0. If a copy of the MPL was not distributed with this@>
@q%    file, You can obtain one at http://mozilla.org/MPL/2.0/.@>
@q% */@>
@q output wset.cpp@>
@** Set handling. This is an interesting section.\fbreak
 The original
Yacco2 generated code to create each thread's tables at startup time by \CPLUSPLUS/ templates.
Well the 10 megabyte gorilla thumped its chest.
By use of the marvelous book ``Efficient \CPLUSPLUS/'' by Bulka and Mayhew,
Yacco2 became a diet marvel. Have you heard any testimonials?
No, well I'm now one. Go groan and sweat, your software will thank you for it and so will its
life span.

As lookahead sets are rather sparse, to make set processing reasonably efficient,
the following approach was implemented.
The out-of-the-box binary search function is used to search a set.
To minimize set size, the range of enumerated elements is divided up into
8 elements per partition where the remainder is the specific element.

Now why an 8 element partition?
As Yacco2 currently uses 8 bit ASCII encoding and the density of the sets are sparse
and my machine has 8 bits per byte, I
felt that this was a reasonable compromise in the age of Aquarius. 
If the sets were more dense, then the 
number of elements per partition could be 16 or greater. 
As always, there is a compromise between space and speed.
It's upto the person porting the software to decide.
Hash tables were considered but I decided that space would be 
too wasteful.

Thought: Is there a dynamic hash faclity that 
rivals the set space but beats it in accessing speed?
Other thoughts: use of complement sets if set size too big.

Elements are ordered in ascending sequence
 such that the set becomes a binary array of partitions.
The binary functor takes two set structures: one is the key that
is being searched within the set table, and the set table.
To shrink the set size, |LR1_Eolr| is a special element used to signify
`use all terminals defined including self'. It's grammar tag is ``eolr''.

Output is directed to |wset.cpp|.
@d SET_ELEM_NO_BITS 8
@(wset.cpp@>=
@<copyright notice@>;
@<iyacco2@>;
@<accrue set code@>;

@ Accrue set code.
@<accrue set code@>= // acrue set code

@ Some set types used in constructing search sets.
@<Type def...@>=
typedef std::map<yacco2::USINT,yacco2::USINT> yacco2_set_type;
typedef yacco2_set_type::iterator yacco2_set_iter_type;

@*2 Structure of a set.\fbreak
 Current implementation uses 2 bytes of 8 bit size.
The first byte is the partition number with a range of 0..255.
The 2nd byte is the elements where x in ${2^x}$ indicates its position within
the byte. An element's position within the byte is 
its remainder of modulo |SET_ELEM_NO_BITS|.
This set structure supports 2048 elements --- 256 partitions by 8 elements.
If there are more terminals to be supported, then there is
2 ways to increase the supported number of terminals: increase
the partition size from a byte to an integer 
or expand the size of the number of elements per partition.

@<Structure...@>=
struct Set_entry {// set structure: byte no of set pairs, |partition,set| pair(s)
  yacco2::UCHAR    partition__;// whole no
  yacco2::UCHAR    elements__;// 7..0 in bit order due to remainder: 0 = 1 while 7 = 128 value
};
struct Set_tbl {
  yacco2::UCHAR      no_entries__;
  yacco2::Set_entry  first_entry__[1];
};@/

@*2 Set element compare functor.\fbreak
This is just your basic binary search functor whose address is passed
to the binary search routine.
The only interesting part is c's bitwise logical `and' to determine
if the element is in the 2nd byte of the structure.
If the element is not found, it forces the search to continue down a cul-du-sac
by returning a false `less than'  comparison.

Now i roll my own bsearch to speed things up. 
The compare functor is just too expensive in run time so out damn spot.
@<External rtns and variables@>+=
extern void create_set_entry(yacco2::USINT Enum_id,yacco2::Set_entry& Set);

@*2 From a terminal's enumeration create a set's key for searching.\fbreak
This routine maps an enumeration into a set's co-ordinates.
@<accrue set code@>+=
extern void
yacco2::create_set_entry(yacco2::USINT Enum_id,yacco2::Set_entry& Set){
  INT R = Enum_id % SET_ELEM_NO_BITS;
  Set.partition__ = Enum_id / SET_ELEM_NO_BITS;  
  Set.elements__ = 1 << R;  
}

@ |create_set_entry|.
@<|create_set_entry|@>=
  INT R = Enum_id % SET_ELEM_NO_BITS;
  la_set.partition__ = Enum_id / SET_ELEM_NO_BITS;  
  la_set.elements__ = 1 << R; 
 
@ |create_set_entry for RC|.
@<|create_set_entry for Rc|@>=
  INT R = sym->enumerated_id__ % SET_ELEM_NO_BITS;
  sym->tok_co_ords__.set_entry__.partition__ 
          = sym->enumerated_id__ / SET_ELEM_NO_BITS;  
  sym->tok_co_ords__.set_entry__.elements__ = 1 << R; 
 
@ |create_set_entry for CAbs_lr1_sym|.
@<|create_set_entry for CAbs_lr1_sym|@>=
  INT R = Enum_id % SET_ELEM_NO_BITS;
  tok_co_ords__.set_entry__.partition__ = Enum_id / SET_ELEM_NO_BITS;  
  tok_co_ords__.set_entry__.elements__ = 1 << R;