fig linear arrangement of the partially ordered set of fig how do we proceed to find one of the possible linear orderingsthe recipe is quite simple we start by choosing any item that is not preceded by another item (there must be at least oneotherwise loop would existthis object is placed at the head of the resulting list and removed from the set the remaining set is still partially orderedand so the same algorithm can be applied again until the set is empty in order to describe this algorithm more rigorouslywe must settle on data structure and representation of and its ordering the choice of this representation is determined by the operations to be performedparticularly the operation of selecting elements with zero predecessors every item should therefore be represented by three characteristicsits identification keyits set of successorsand count of its predecessors since the number of elements in is not given priorithe set is conveniently organized as linked list consequentlyan additional entry in the description of each item contains the link to the next item in the list we will assume that the keys are integers (but not necessarily the consecutive integers from to nanalogouslythe set of each item' successors is conveniently represented as linked list each element of the successor list is described by an identification and link to the next item on this list if we call the descriptors of the main listin which each item of occurs exactly onceleadersand the descriptors of elements on the successor chains trailerswe obtain the following declarations of data typestype leader pointer to leaderdesctrailer pointer to trailerdescleaderdesc record keycountintegertrailtrailernextleader endtrailerdesc record idleadernexttrailer end assume that the set and its ordering relations are initially represented as sequence of pairs of keys in the input file the input data for the example in fig are shown belowin which the symbols are added for the sake of claritysymbolizing partial order < < < < < < < < < < < the first part of the topological sort program must read the input and transform the data into list structure this is performed by successively reading pair of keys and ( ylet us denote the pointers to their representations on the linked list of leaders by and these records must be located by list search andif not yet presentbe inserted in the list this task is perfomed by function procedure called find subsequentlya new entry is added in the list of trailers of xalong with an identification of qthe count of predecessors of is incremented by this algorithm is called input phase figure illustrates the data structure generated during processing the given input data the function find(wyields the pointer to the list element with key in the following poece of program we make use of text scanninga feature of the oberon system' text concept instead of considering text (fileas sequence of charactersa text is considered as sequence of tokenswhich are identifiersnumbersstringsand special characters (such as +*<etc the procedure texts scan(sscans the textreading the next token the scanner plays the role of text rider