home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Bitmap Libraries 2.0 / Examples / Digraph / Digraph.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-02-27  |  13.6 KB  |  498 lines  |  [TEXT/MPS ]
  1. /* File Example.c Copyright (C) 1996 by John R. Montbriand.  All Rights Reserved. */
  2.  
  3. /* File Example.c
  4.  
  5.     Copyright (C) 1996 by John Montbriand.  All Rights Reserved.
  6.     
  7.     Distribute freely in areas where the laws of copyright apply.
  8.     
  9.     Use at your own risk.
  10.     
  11.     Do not distribute modified copies.
  12.     
  13.     These various BitMap libraries and examples are for free!
  14.     
  15.     See the accompanying file BitMap.txt for details.
  16.     
  17. */
  18.  
  19. /* written in Geneva 9, tabs at 4 */
  20.  
  21. /* •••••••••••••••••••••• INCLUDES •••••••••••••••••••••• */
  22.  
  23. #include <Types.h>
  24. #include <QuickDraw.h>
  25. #include <Fonts.h>
  26. #include <Windows.h>
  27. #include <Menus.h>
  28. #include <TextEdit.h>
  29. #include <Dialogs.h>
  30. #include <AppleEvents.h>
  31. #include <TextUtils.h>
  32. #include <OSUtils.h>
  33. #include <ToolUtils.h>
  34. #include <Desk.h>
  35. #include <Memory.h>
  36. #include <Errors.h>
  37. #include <Gestalt.h>
  38. #include <Resources.h>
  39. #include <Traps.h>
  40. #include <SegLoad.h>
  41.  
  42. #include "BitMap.h"
  43.  
  44. /* •••••••••••••••••••••• CONSTANTS •••••••••••••••••••••• */
  45.  
  46. #define kAboutBoxID 128
  47. #define kErrorBoxID 129
  48. #define kMainWindID 128
  49. #define kMenuBarID 128
  50.  
  51. #define mApple 128
  52. #define iAbout 1
  53. #define iAccessoryOne 3
  54.  
  55. #define mFile 129
  56. #define iQuit 1
  57.  
  58. #define mEdit 130
  59. #define iUndo 1
  60. #define iCut 3
  61. #define iCopy 4
  62. #define iPaste 5
  63. #define iClear 6
  64.  
  65. /* •••••••••••••••••••••• GLOBALS •••••••••••••••••••••• */
  66.  
  67. Boolean PROGRAM_RUNNING = true;
  68. Boolean PROGRAM_FRONT = true;
  69. Boolean HAS_APPLEEVENTS = false;
  70. Boolean HAS_WAITNEXTEVENT = false;
  71.  
  72. QDGlobals    qd;
  73.  
  74. DialogPtr gABOUTBOX = NULL;
  75. WindowPtr gMAIN_WINDOW = NULL;
  76.  
  77.  
  78. /* •••••••••••••••••••••• ERROR HANDLER •••••••••••••••••••••• */
  79.  
  80. /* Terminate, displays an error box containing the error number and then terminates
  81.     the application. */
  82. void Terminate(OSErr err) {
  83.     Str255 s;
  84.     NumToString(err, s);
  85.     ParamText(s, NULL, NULL, NULL);
  86.     Alert(kErrorBoxID, NULL);
  87.     ExitToShell();
  88. }
  89.  
  90. /* •••••••••••••••••••••• THE EXAMPLE PART •••••••••••••••••••••• */
  91. /* NOTE:  all of the example code to do with bitmaps is included in this part of the
  92. program.  The rest of the program has to do with the usual things that go into
  93. applications.  */
  94.  
  95. BitMap *adjacencies, *graphimage;
  96. long **path, start, finish, vertcount;
  97. Rect gBounds, *vertices;
  98.  
  99. /*DrawWindowContents is called in response to every update event for the main
  100.     window.  this is the part where we do drawing in the bitmaps */
  101. void DrawWindowContents(WindowPtr wp) {
  102.     BitMap *drawn_bits;
  103.     long i, n, the_vertex;
  104.     BitMapPort* bmp;
  105.     
  106.         /* make a copy of the image for drawing */
  107.     drawn_bits = DuplicateBitMap(graphimage);
  108.     if (drawn_bits == NULL) return;
  109.     
  110.         /* hilite the vertices in the current path */
  111.     n = GetHandleSize((Handle) path) / sizeof(long);
  112.     WithBitMap(drawn_bits, bmp) {
  113.         for (i=0; i<n; i++) {
  114.             the_vertex = (*path)[i];
  115.             InvertRect(vertices + the_vertex);
  116.         }
  117.     }
  118.     
  119.         /* put it on the screen */
  120.     PlotBitMap(drawn_bits, 5, 5, srcCopy);
  121.  
  122.     KillBitMap(drawn_bits);
  123. }
  124.  
  125.  
  126. /* herein we use an iterative deepening method for searching the graph
  127.     for paths between two vertices.  in other words, this is a depth
  128.     first algorithm that looks only so far and it looks a little further
  129.     every time it's called until it has exhaused every possibility. */
  130. long *gVisited, gNVertices, **gThePath;
  131. BitMap *gDiGraph;
  132.  
  133. Boolean IterativePathSearch(long a, long b, short max_depth) {
  134.     long i, n;
  135.     if (max_depth <= 0) return false;
  136.     if (a == b) {
  137.         if (PtrToXHand(&a, (Handle) gThePath, sizeof(long)) != noErr)
  138.             Terminate(memFullErr);
  139.         return true;
  140.     } else {
  141.         gVisited[a] = 1;
  142.         for (i=0; i<gNVertices; i++)
  143.             if (!gVisited[i] && BitMapTest(gDiGraph, a, i))
  144.                 if (IterativePathSearch(i, b, max_depth - 1)) {
  145.                     if (PtrAndHand(&a, (Handle) gThePath, sizeof(long)) != noErr)
  146.                         Terminate(memFullErr);
  147.                     return true;
  148.                 }
  149.         gVisited[a] = 0;
  150.     }
  151.     return false;
  152. }
  153.  
  154. /* calculates the shortest path from a to b using the adjacency matrix stored in
  155.     the_graph.  if a path is found, CalculateNewPath is set to true and the_path
  156.     is set to a list of long integers representing the vertices along the path
  157.     from a to b in reverse order.  if no path is found,  false is returned and
  158.     the_path is set to a zero length block. */
  159. Boolean CalculateNewPath(BitMap *the_graph, long** the_path, long a, long b) {
  160.     long i;
  161.     Boolean result;
  162.     result = false;
  163.     gDiGraph = the_graph;
  164.     gThePath = the_path;
  165.     gNVertices = the_graph->bounds.right;
  166.     gVisited = (long*) NewPtrClear(gNVertices*sizeof(long));
  167.     if (gVisited == NULL) Terminate(memFullErr);
  168.     SetHandleSize((Handle) the_path, 0);
  169.     for (i = 1; i < gNVertices; i++)
  170.         if (IterativePathSearch(a, b, i)) {
  171.             result = true;
  172.             break;
  173.         }
  174.     DisposePtr((Ptr) gVisited);
  175.     return result;
  176. }
  177.  
  178. /*ClickWindowContents is called every time a mouse down event occurs in the
  179.     main program window allowing for some interaction. */
  180. void ClickWindowContents(WindowPtr wp, Point where) {
  181.     long i, pathlength, first;
  182.     if (PtInRect(where, &gBounds)) {
  183.         MapPt(&where, &gBounds, &graphimage->bounds);
  184.         pathlength = GetHandleSize((Handle) path)/sizeof(long);
  185.         for ( i=0; i < vertcount; i++) {
  186.             if (PtInRect(where, vertices + i)) {
  187.                 if (pathlength != 1) {
  188.                     if (PtrToXHand(&i, (Handle) path, sizeof(long)) != noErr)
  189.                         Terminate(memFullErr);
  190.                 } else {
  191.                     CalculateNewPath(adjacencies, path, (*path)[0], i);
  192.                 }
  193.                 DrawWindowContents(wp);
  194.                 return;
  195.             }
  196.         }
  197.     }
  198. }
  199.  
  200. /* AddBiDirectionalPath adds a path to the matrix indicating that there
  201.     is a path from a to b and from b to a */
  202. void AddBiDirectionalPath(BitMap *matrix, short a, short b) {
  203.     BitMapSet(matrix, a, b);
  204.     BitMapSet(matrix, b, a);
  205. }
  206.  
  207. /* InitExample is called at program startup after the main window has been
  208.     created to allow the example to set itself up.  I put it here so all the example
  209.     code would be together in one section. */
  210. OSErr InitExample(WindowPtr wp) {
  211.     PicHandle pic;
  212.     Handle vertResource;
  213.         
  214.         /* get the vertices rectangles */
  215.     vertResource = GetResource('RECT', 129);
  216.     if (vertResource == NULL) return resNotFound;
  217.     MoveHHi(vertResource);
  218.     HLock(vertResource);
  219.     vertices = (Rect*) (*vertResource);
  220.     vertcount = GetHandleSize(vertResource)/sizeof(Rect);
  221.     
  222.         /* set up the adjacency matrix */
  223.     adjacencies = NewBitMap(vertcount, vertcount);
  224.     if (adjacencies == NULL) return memFullErr;
  225.     AddBiDirectionalPath(adjacencies, 0, 1);
  226.     AddBiDirectionalPath(adjacencies, 1, 2);
  227.     AddBiDirectionalPath(adjacencies, 1, 4);
  228.     AddBiDirectionalPath(adjacencies, 1, 10);
  229.     AddBiDirectionalPath(adjacencies, 2, 3);
  230.     AddBiDirectionalPath(adjacencies, 3, 4);
  231.     AddBiDirectionalPath(adjacencies, 4, 8);
  232.     AddBiDirectionalPath(adjacencies, 4, 11);
  233.     AddBiDirectionalPath(adjacencies, 5, 8);
  234.     AddBiDirectionalPath(adjacencies, 5, 6);
  235.     AddBiDirectionalPath(adjacencies, 5, 9);
  236.     AddBiDirectionalPath(adjacencies, 7, 8);
  237.     AddBiDirectionalPath(adjacencies, 8, 12);
  238.     AddBiDirectionalPath(adjacencies, 9, 13);
  239.     AddBiDirectionalPath(adjacencies, 10, 11);
  240.     AddBiDirectionalPath(adjacencies, 11, 12);
  241.     AddBiDirectionalPath(adjacencies, 11, 17);
  242.     AddBiDirectionalPath(adjacencies, 12, 13);
  243.     AddBiDirectionalPath(adjacencies, 13, 14);
  244.     AddBiDirectionalPath(adjacencies, 13, 19);
  245.     AddBiDirectionalPath(adjacencies, 15, 16);
  246.     AddBiDirectionalPath(adjacencies, 16, 17);
  247.     AddBiDirectionalPath(adjacencies, 16, 21);
  248.     AddBiDirectionalPath(adjacencies, 17, 18);
  249.     AddBiDirectionalPath(adjacencies, 17, 21);
  250.     AddBiDirectionalPath(adjacencies, 18, 20);
  251.     AddBiDirectionalPath(adjacencies, 19, 20);
  252.     AddBiDirectionalPath(adjacencies, 20, 22);
  253.     AddBiDirectionalPath(adjacencies, 21, 22);
  254.     AddBiDirectionalPath(adjacencies, 22, 23);
  255.     
  256.         /* get the graph image */
  257.     pic = GetPicture(129);
  258.     if (pic == NULL) return resNotFound;
  259.     graphimage = PICTToBitMap(pic);
  260.     if (graphimage == NULL) return memFullErr;
  261.  
  262.         /* set up the graph variables */
  263.     start = finish = -1;
  264.     path = (long**) NewHandle(0);
  265.     if (path == NULL) return memFullErr;
  266.     
  267.         /* adjust the window size */
  268.     SizeWindow(wp, graphimage->bounds.right+10, graphimage->bounds.bottom+10, true);
  269.     gBounds = graphimage->bounds;
  270.     OffsetRect(&gBounds, 5, 5);
  271.  
  272.         /* done */
  273.     return noErr;
  274. }
  275.  
  276.  
  277. /* •••••••••••••••••••••• MENU COMMANDS •••••••••••••••••••••• */
  278.  
  279. /* HandleMenuCommand is called after MenuKey or MenuSelect to handle the processing
  280.      of menu commands.  Here there aren't too many, just the standard ones */
  281. void HandleMenuCommand(short menu, short item) {
  282.     if (menu == mApple) {
  283.         if (item == iAbout) {
  284.             if (gABOUTBOX != NULL)
  285.                 SelectWindow(gABOUTBOX);
  286.             else gABOUTBOX = GetNewDialog(kAboutBoxID, NULL, (WindowPtr) (-1));
  287.         } else if (item >= iAccessoryOne) {
  288.             Str255 itemString;
  289.             GetItem(GetMHandle(menu), item, itemString);
  290.             OpenDeskAcc(itemString);
  291.         }
  292.     } else if (menu == mFile) {
  293.         switch (item) {
  294.             case iQuit:
  295.                 PROGRAM_RUNNING = false;
  296.                 break;
  297.         }
  298.     } else if (menu == mEdit) {
  299.         SystemEdit(item-1);
  300.     }
  301.     HiliteMenu(0);
  302. }
  303.  
  304. /* MenuPreflightCheck is called immediately before MenuKey or MenuSelect.  In your
  305.     application you would use this routine to appropriately enable or disable different
  306.     commands depending on what can be done at the time of the mouse click or key
  307.     command. */
  308. void MenuPreflightCheck(void) {
  309.     /* none here*/
  310. }
  311.  
  312.  
  313. /* •••••••••••••••••••••• EVENT HANDLING •••••••••••••••••••••• */
  314.  
  315. /* HandleMouseDownEvent is called to process mouse down events */
  316. void HandleMouseDownEvent(EventRecord *ev) {
  317.     WindowPtr target;
  318.     switch ( FindWindow(ev->where, &target) ) {
  319.         case inDesk:
  320.             break;
  321.         case inSysWindow:
  322.             SystemClick(ev, target);
  323.             break;
  324.         case inContent:
  325.             if (target != FrontWindow())
  326.                 SelectWindow(target);
  327.             else if (target == gMAIN_WINDOW) {
  328.                 Point where;
  329.                 where = ev->where;
  330.                 SetPort(target);
  331.                 GlobalToLocal(&where);
  332.                 ClickWindowContents(target, where);
  333.             }
  334.             break;
  335.         case inDrag:
  336.             {    Rect r = qd.screenBits.bounds;
  337.                 if (target != FrontWindow()) SelectWindow(target);
  338.                 SetPort(target);
  339.                 InsetRect(&r, 4, 4);
  340.                 r.top += 20;
  341.                 DragWindow(target, ev->where, &r);
  342.             }
  343.             break;
  344.         case inGoAway:
  345.             if (TrackGoAway(target, ev->where)) {
  346.                 if (target == gABOUTBOX) {
  347.                     DisposeDialog(gABOUTBOX);
  348.                     gABOUTBOX = NULL;
  349.                 } else PROGRAM_RUNNING = false;
  350.             }
  351.             break;
  352.         case inMenuBar:
  353.             {    long mnRes;
  354.                 MenuPreflightCheck();
  355.                 if (HiWord(mnRes = MenuSelect(ev->where)) != 0)
  356.                     HandleMenuCommand(HiWord(mnRes), LoWord(mnRes));
  357.             }
  358.             break;
  359.     }
  360. }
  361.  
  362. /* SystemSwapTask can be called from anywhere in your application.  basically it collects
  363.     events and gives the system time to do its thing. */
  364. void SystemSwapTask(void) {
  365.     EventRecord ev;
  366.     
  367.         /* get the next event */
  368.     if (HAS_WAITNEXTEVENT) {
  369.         if (!WaitNextEvent(everyEvent, &ev, 0, NULL)) ev.what = nullEvent;
  370.     } else {
  371.         if (!GetNextEvent(everyEvent, &ev)) ev.what = nullEvent;
  372.         SystemTask();
  373.     }
  374.     
  375.     if ((ev.what == keyDown || ev.what == autoKey) && (ev.modifiers & cmdKey) != 0) {
  376.         long mnRes;
  377.         MenuPreflightCheck();
  378.         if (HiWord(mnRes = MenuKey((char) (ev.message & charCodeMask))) != 0)
  379.             HandleMenuCommand(HiWord(mnRes), LoWord(mnRes));
  380.     } else if (IsDialogEvent(&ev)) {
  381.         DialogPtr theDialog;
  382.         short itemHit;
  383.         DialogSelect(&ev, &theDialog, &itemHit);
  384.     } else if (ev.what == mouseDown) {
  385.         HandleMouseDownEvent(&ev);
  386.     } else if (ev.what == updateEvt) {
  387.         WindowPtr wp;
  388.         wp = (WindowPtr) ev.message;
  389.         SetPort(wp);
  390.         BeginUpdate(wp);
  391.         DrawWindowContents(wp);
  392.         EndUpdate(wp);
  393.     } else if (ev.what == kHighLevelEvent) {
  394.         if (HAS_APPLEEVENTS)
  395.             AEProcessAppleEvent(&ev);
  396.     } else if (ev.what == osEvt) {
  397.         if (((ev.message >> 24) & 0x0FF) == suspendResumeMessage)
  398.             PROGRAM_FRONT = (ev.message & resumeFlag) != 0;
  399.     }
  400.     
  401. }
  402.  
  403.  
  404. /* •••••••••••••••••••••• APPLE EVENTS •••••••••••••••••••••• */
  405.  
  406. /* QuitEventHandler called for quit apple events.  all we do here is set the running
  407.     flag to false */
  408. pascal OSErr QuitEventHandler(const AppleEvent *appleEvt, AppleEvent* reply, long refcon) {
  409.     DescType retType;
  410.     Size actSize;
  411.     OSErr err;
  412.     err = AEGetAttributePtr(appleEvt, keyMissedKeywordAttr, typeWildCard, &retType, NULL, 0, &actSize);
  413.     if (err == errAEDescNotFound) {
  414.         PROGRAM_RUNNING = false;
  415.         return noErr;
  416.     } else if (err == noErr)
  417.         return errAEEventNotHandled;
  418.     else return err;
  419. }
  420.  
  421.  
  422. /* •••••••••••••••••••••• TEST FOR TRAPS •••••••••••••••••••••• */
  423.  
  424. unsigned short NumToolboxTraps(void) {
  425.     if (NGetTrapAddress(_InitGraf, ToolTrap) == NGetTrapAddress(0xAA6E, ToolTrap))
  426.         return 0x0200;
  427.     else return 0x0400;
  428. }
  429.  
  430. TrapType FindTrapType(unsigned short theTrap) {
  431.     if (theTrap & 0x0800)
  432.         return ToolTrap;
  433.     else return OSTrap;
  434. }
  435.  
  436. Boolean TrapAvailable(unsigned short theTrap) {
  437.     unsigned short localTrap = theTrap;
  438.     TrapType tType = FindTrapType(localTrap);
  439.     if ( tType == ToolTrap ) {
  440.         localTrap &= 0x07FF;
  441.         if ( localTrap >= NumToolboxTraps() )
  442.             localTrap = _Unimplemented;
  443.     }
  444.     return NGetTrapAddress(localTrap, tType) != NGetTrapAddress(_Unimplemented, ToolTrap);
  445. }
  446.  
  447.  
  448. /* •••••••••••••••••••••• MAIN PROGRAM •••••••••••••••••••••• */
  449.  
  450. void main(void) {
  451.     OSErr err;
  452.     long response;
  453.  
  454.         /* determine features of the machine */
  455.     if (Gestalt(gestaltAppleEventsAttr, &response) != noErr) response = 0;
  456.     HAS_APPLEEVENTS = ((response & (1<<gestaltAppleEventsPresent)) != 0);
  457.     HAS_WAITNEXTEVENT = TrapAvailable(_WaitNextEvent);
  458.     
  459.         /* initialize the toolbox, etc.. */
  460.     SetApplLimit( GetApplLimit() - (8*1024) );
  461.     MaxApplZone();
  462.     InitGraf(&qd.thePort);
  463.     InitFonts();
  464.     InitWindows();
  465.     TEInit();
  466.     InitMenus();
  467.     InitDialogs(NULL);
  468.     InitCursor();
  469.     if (HAS_APPLEEVENTS) {
  470.         err = AEInstallEventHandler(kCoreEventClass, kAEQuitApplication,
  471.                     NewAEEventHandlerProc(QuitEventHandler), 0, false);
  472.         if (err != noErr) goto bail;
  473.     }
  474.     SetMenuBar(GetNewMBar(kMenuBarID));
  475.     AddResMenu(GetMHandle(mApple), 'DRVR');
  476.     DrawMenuBar();
  477.     gMAIN_WINDOW = GetNewWindow(kMainWindID, NULL, (WindowPtr) (-1));
  478.     SetPort(gMAIN_WINDOW);
  479.     err = InitExample(gMAIN_WINDOW);
  480.  
  481.         /* set up some globals */
  482.     PROGRAM_RUNNING = true;
  483.     PROGRAM_FRONT = true;
  484.     
  485.         /* loop until PROGRAM_RUNNING is false */
  486.     while (PROGRAM_RUNNING)
  487.         SystemSwapTask();
  488.     
  489.     return;
  490.     
  491. bail:
  492.     Terminate(err);
  493. }
  494.  
  495.  
  496. /* end File BitMap.c */
  497.  
  498.